Class DPTable

java.lang.Object
  DPTable

public class DPTable
extends java.lang.Object

Class DPTable maintains a representation of the state of a dynamic programming table for the lcs problem. It maintains two strings a and b, of length aLen and bLen, and the lower bounds (offset by an arbitrary constant) for the corresponding portion of the lcs table as illustrated in Figures 5 and 6. It also provides methods for encoding (resp. decoding) states into (resp. from) the four-tuple illustrated in Figure 5.

Field Summary

(package private) int[]	a The currently remembered characters from the top input string.
(package private) int	aLen The length of the input string remembered in a; note that aLen is less than the size of the array a.
(package private) int[]	b The currently remembered characters from the bottom input string.
(package private) int	bLen The length of the input string remembered in b
(package private) int	h The value of the history parameter
(package private) int[][]	lcs The currently remembered portion of the lcs table.
(package private) static boolean	verbose Set this value to true to obtain verbose output

Constructor Summary

DPTable(State s)
Decode the four integers comprising State s into a table.

Method Summary

void	appendPair(int c, int l) Append the minimal match pair Tc,l to the strings a and b, and update the lcs table; see the overview of the code for the definition of Tc,l.
void	computeEntryFromRecurrence(int i, int j) Compute the entry lcs[i][j] based on the values in a[i], b[j], lcs[i-1][j-1], lcs[i-1][j], and lcs[i][j-1].
void	decodeHorzDiffs(int i, int j, int dy) Decode a bitstring into horizontal differences in a table.
void	decodeString(int x, int[] a) Interpreting x as an h-bit integer, place the successive bits into a[1],a[2],...,a[h].
void	decodeVertDiffs(int i, int j, int dx) Decode a bitstring into vertical differences in a table.
State	encode() Encode the last h entries in strings a and b, and the last h vertical and horizontal differences in lcs, into a State four-tuple.
short	encodeHorzDiffs(int i, int j) Encode horizontal differences from the table into a short.
short	encodeVertDiffs(int i, int j) Encode vertical differences from the table into a short.
static void	error(java.lang.String s) Print an error message and terminate.
(package private) boolean	isCanonical() Return true if backtracking canonically from lcs[aLen][bLen] leads to lcs[h][h].
static void	main(java.lang.String[] args) Perform some tests of the methods.
void	show() Display the current contents of a, b, and the lcs table.
short	suffix(int[] a, int aLen) Return the integer represented in binary by the sequence of bits a[aLen-h+1],a[aLen-h+2],...,a[aLen].

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

verbose

static boolean verbose

Set this value to true to obtain verbose output

a

int[] a

The currently remembered characters from the top input string. These are stored in a[1] thru a[aLen].

b

int[] b

The currently remembered characters from the bottom input string. These are stored in b[1] thru b[bLen].

aLen

int aLen

The length of the input string remembered in a; note that aLen is less than the size of the array a.

bLen

int bLen

The length of the input string remembered in b

lcs

int[][] lcs

The currently remembered portion of the lcs table. These values are lower bounds, offset by a constant.

h

int h

The value of the history parameter

Constructor Detail

DPTable

public DPTable(State s)

Decode the four integers comprising State s into a table.

Method Detail

error

public static void error(java.lang.String s)

Print an error message and terminate.

decodeString

public void decodeString(int x,
                         int[] a)

Interpreting x as an h-bit integer, place the successive bits into a[1],a[2],...,a[h].

suffix

public short suffix(int[] a,
                    int aLen)

Return the integer represented in binary by the sequence of bits a[aLen-h+1],a[aLen-h+2],...,a[aLen].

decodeVertDiffs

public void decodeVertDiffs(int i,
                            int j,
                            int dx)

Decode a bitstring into vertical differences in a table. Make the differences of the subcolumn of entries from lcs[i-h][j] to lcs[i][j] be the last h bits of dx; leave lcs[i][j] unchanged. (See Figure 7 in the paper.)

decodeHorzDiffs

public void decodeHorzDiffs(int i,
                            int j,
                            int dy)

Decode a bitstring into horizontal differences in a table. Make the differences of the subrow of entries from lcs[i][j-h] to lcs[i][j] be the last h bits of dy; leave lcs[i][j] unchanged. (See Figure 7 in the paper.)

encodeVertDiffs

public short encodeVertDiffs(int i,
                             int j)

Encode vertical differences from the table into a short. Return an integer whose last h bits are the successive differences of the subcolumn of entries from lcs[i-h][j] to lcs[i][j].

encodeHorzDiffs

public short encodeHorzDiffs(int i,
                             int j)

Encode horizontal differences from the table into a short. Return an integer whose last h bits are the successive differences of the subrow of entries from lcs[i][j-h] to lcs[i][j].

encode

public State encode()

Encode the last h entries in strings a and b, and the last h vertical and horizontal differences in lcs, into a State four-tuple.

computeEntryFromRecurrence

public void computeEntryFromRecurrence(int i,
                                       int j)

Compute the entry lcs[i][j] based on the values in a[i], b[j], lcs[i-1][j-1], lcs[i-1][j], and lcs[i][j-1].

appendPair

public void appendPair(int c,
                       int l)

Append the minimal match pair T_c,l to the strings a and b, and update the lcs table; see the overview of the code for the definition of T_c,l.

isCanonical

boolean isCanonical()

Return true if backtracking canonically from lcs[aLen][bLen] leads to lcs[h][h].

show

public void show()

Display the current contents of a, b, and the lcs table.

main

public static void main(java.lang.String[] args)

Perform some tests of the methods.