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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
package com.wcohen.ss;
import com.wcohen.ss.api.*;
import org.apache.log4j.Logger;
/**
* Variant of MemoMatrix that only stores values near the diagonal,
* for better efficiency.
*/
// to do: export scale, loJNearDiag(i), hiJNearDiag(i)
//
public abstract class ApproxMemoMatrix extends MemoMatrix
{
private static Logger log=Logger.getLogger(ApproxMemoMatrix.class);
// explicitly stored values
private double[][] valuesNearDiagonal;
private boolean[][] wasComputed;
// value used for entries not explicitly stored
private double defaultValue;
//
// these define which values are explicitly stored
//
// since the matrix is not necessarily square, the 'diagonal'
// entry for i is not i, but i*scale.
private double scale;
// store m[i,i*scale-width] thru store m[i,i*scale+width]
private int width;
ApproxMemoMatrix(StringWrapper s,StringWrapper t,int width,double defaultValue)
{
super(new BasicStringWrapper(""),new BasicStringWrapper(""));
this.s = s;
this.t = t;
this.valuesNearDiagonal = new double[s.length()+1][2*width];
this.wasComputed = new boolean[s.length()+1][2*width];
this.defaultValue = defaultValue;
this.width = width;
this.scale = (t.length()+1.0)/(s.length()+1.0);
}
private int offsetFromDiagonal(int i,int j)
{
int diagForI = (int)Math.round( i*scale );
int k = diagForI-j + width;
return k;
}
private boolean nearDiagonal(int k)
{
return k>=1 && k<2*width;
}
double get(int i,int j)
{
// value for i,j is stored in valuesNearDiagonal[i][k]
int k = offsetFromDiagonal(i,j);
if (!nearDiagonal(k)) {
return defaultValue;
} else if (wasComputed[i][k]) {
return valuesNearDiagonal[i][k];
} else {
valuesNearDiagonal[i][k] = compute(i,j);
wasComputed[i][k] = true;
return valuesNearDiagonal[i][k];
}
}
public boolean outOfRange(int i, int j)
{
boolean out = i<1 || i>s.length() || j<1 || j>t.length();
if (out) log.error("out of range: |s|="+s.length()+" |t|="+t.length()+" s = '"+s+"' t="+t+"'");
return out;
}
//
// low-level access to the stored part of the matrix
//
int getWidth() { return width; }
double getScale() { return scale; }
int getFirstStoredEntryInRow(int i)
{
int diagForI = (int)Math.round( i*scale );
return Math.max(1, (diagForI - width));
}
int getLastStoredEntryInRow(int i)
{
int diagForI = (int)Math.round( i*scale );
return Math.min(t.length(), (diagForI + width));
}
/** Print the matrix, for debugging and/or explanation. */
public String toString()
{
PrintfFormat fmt = new PrintfFormat(cellFormat);
StringBuffer buf = new StringBuffer();
// line 1 - a ruler
buf.append(" "); buf.append(" ");
for (int i=1; i<=s.length(); i++) buf.append(fmt.sprintf((double)i));
buf.append("\n");
// line 2 - the string
buf.append(" "); buf.append(" ");
for (int i=1; i<=s.length(); i++) buf.append(" "+trapNewline(sAt(i))+" ");
buf.append("\n");
// line 2 - an hrule
buf.append(" "); buf.append(" ");
for (int i=1; i<=s.length(); i++) buf.append("---");
buf.append("\n");
// remaining lines
for (int j=1; j<=t.length(); j++) {
buf.append(fmt.sprintf((double)j));
buf.append(" "+trapNewline(tAt(j))+"|");
for (int i=1; i<=s.length(); i++) {
if (!nearDiagonal(offsetFromDiagonal(i,j)) || defaultValue==get(i,j)) {
buf.append(" * ");
} else {
double v = printNegativeValues ? -get(i,j) : get(i,j);
buf.append(fmt.sprintf(v));
}
}
buf.append("\n");
}
return buf.toString();
}
private char trapNewline(char ch)
{
return Character.isWhitespace(ch) ? ' ' : ch;
}
}
|
