1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
package morfologik.speller;
/**
* Keeps track of already computed values of edit distance.<br/>
* Remarks: To save space, the matrix is kept in a vector.
*/
public class HMatrix {
private int[] p; /* the vector */
private int rowLength; /* row length of matrix */
int columnHeight; /* column height of matrix */
int editDistance; /* edit distance */
/**
* Allocates memory and initializes matrix (constructor).
*
* @param distance (int) max edit distance allowed for
* candidates;
* @param maxLength (int) max length of words.
*
* Remarks: See Oflazer. To save space, the matrix is
* stored as a vector. To save time, additional rows and
* columns are added. They are initialized to their distance in
* the matrix, so that no bound checking is necessary during
* access.
*/
public HMatrix(final int distance, final int maxLength) {
rowLength = maxLength + 2;
columnHeight = 2 * distance + 3;
editDistance = distance;
final int size = rowLength * columnHeight;
p = new int[size];
// Initialize edges of the diagonal band to distance + 1 (i.e.
// distance too big)
for (int i = 0; i < rowLength - distance - 1; i++) {
p[i] = distance + 1; // H(distance + j, j) = distance + 1
p[size - i - 1] = distance + 1; // H(i, distance + i) = distance
// + 1
}
// Initialize items H(i,j) with at least one index equal to zero to
// |i - j|
for (int j = 0; j < 2 * distance + 1; j++) {
p[j * rowLength] = distance + 1 - j; // H(i=0..distance+1,0)=i
// FIXME: fordistance == 2 we exceed the array size here.
// there's a bug in spell.cc, Jan Daciuk has been notified about it.
p[Math.min(p.length - 1, (j + distance + 1) * rowLength + j)] = j; // H(0,j=0..distance+1)=j
}
}
/**
* Provide an item of hMatrix indexed by indices.
*
* @param i
* - (int) row number;
* @param j
* - (int) column number.
* @return Item H[i][j] <br/>
* Remarks: H matrix is really simulated. What is needed is only
* 2 * edit_distance + 1 wide band around the diagonal. In fact
* this diagonal has been pushed up to the upper border of the
* matrix.
*
* The matrix in the vector looks likes this:
*
* <pre>
* +---------------------+
* 0 |#####################| j=i-e-1
* 1 | | j=i-e
* : :
* e+1 | | j=i-1
* +---------------------+
* e+2 | | j=i
* +---------------------+
* e+3 | | j=i+1
* : :
* 2e+2| | j=i+e
* 2e+3|#####################| j=i+e+1
* +---------------------+
* </pre>
*/
public int get(final int i, final int j) {
return p[(j - i + editDistance + 1) * rowLength + j];
}
/**
* Set an item in hMatrix.
*
* @param i
* - (int) row number;
* @param j
* - (int) column number;
* @param val
* - (int) value to put there.
*
* No checking for i & j is done. They must be correct.
*/
public void set(final int i, final int j, final int val) {
p[(j - i + editDistance + 1) * rowLength + j] = val;
}
}
|
