-
Notifications
You must be signed in to change notification settings - Fork 39
/
LCS.scala
140 lines (123 loc) · 3.32 KB
/
LCS.scala
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
package reactive
/**
* Based on Java code by Neil Jones at http://bix.ucsd.edu/bioalgorithms/downloads/code/LCS.java
*/
object LCS {
object Direction extends Enumeration {
val Neither, Up, Left, UpAndLeft = Value
}
import Direction._
def lcs[T](a: Seq[T], b: Seq[T]): Seq[T] = {
val n = a.length
val m = b.length
val S = Array.ofDim[Int](n + 1, m + 1)
val R = Array.ofDim[Direction.Value](n + 1, m + 1)
// It is important to use to, not until. The next two for-loops are initialization
for (ii <- 0 to n) {
S(ii)(0) = 0
R(ii)(0) = Up
}
for (jj <- 0 to m) {
S(0)(jj) = 0
R(0)(jj) = Left
}
// This is the main dynamic programming loop that computes the score and
// backtracking arrays.
for (ii <- 1 to n) {
for (jj <- 1 to m) {
if (a(ii - 1) == b(jj - 1)) {
S(ii)(jj) = S(ii - 1)(jj - 1) + 1
R(ii)(jj) = UpAndLeft
} else {
S(ii)(jj) = S(ii - 1)(jj - 1) + 0
R(ii)(jj) = Neither
}
if (S(ii - 1)(jj) >= S(ii)(jj)) {
S(ii)(jj) = S(ii - 1)(jj)
R(ii)(jj) = Up
}
if (S(ii)(jj - 1) >= S(ii)(jj)) {
S(ii)(jj) = S(ii)(jj - 1)
R(ii)(jj) = Left
}
}
}
var lcs = List[T]()
// Trace the backtracking matrix.
var ii = n
var jj = m
while (ii > 0 || jj > 0) {
if (R(ii)(jj) == UpAndLeft) {
ii -= 1
jj -= 1
lcs ::= a(ii)
} else if (R(ii)(jj) == Up) {
ii -= 1 // remove
} else if (R(ii)(jj) == Left) {
jj -= 1 // insert
}
}
lcs
}
//TODO only compare from the first different element to the last different element
def lcsdiff[T, U](a: Seq[T], b: Seq[U], equals: (T, U) => Boolean): Seq[SeqDelta[T, U]] = {
val n = a.length
val m = b.length
val S = Array.ofDim[Int](n + 1, m + 1)
val R = Array.ofDim[Direction.Value](n + 1, m + 1)
// It is important to use to, not until. The next two for-loops are initialization
for (ii <- 0 to n) {
S(ii)(0) = 0
R(ii)(0) = Up
}
for (jj <- 0 to m) {
S(0)(jj) = 0
R(0)(jj) = Left
}
// This is the main dynamic programming loop that computes the score and
// backtracking arrays.
for (ii <- 1 to n) {
for (jj <- 1 to m) {
if (equals(a(ii - 1), b(jj - 1))) {
S(ii)(jj) = S(ii - 1)(jj - 1) + 1
R(ii)(jj) = UpAndLeft
} else {
S(ii)(jj) = S(ii - 1)(jj - 1) + 0
R(ii)(jj) = Neither
}
if (S(ii - 1)(jj) >= S(ii)(jj)) {
S(ii)(jj) = S(ii - 1)(jj)
R(ii)(jj) = Up
}
if (S(ii)(jj - 1) >= S(ii)(jj)) {
S(ii)(jj) = S(ii)(jj - 1)
R(ii)(jj) = Left
}
}
}
var diffs = List[IncludeOrRemove[T, U]]()
// Trace the backtracking matrix.
var ii = n
var jj = m
while (ii > 0 || jj > 0) R(ii)(jj) match {
case UpAndLeft =>
ii -= 1
jj -= 1
case Up =>
ii -= 1 // remove
diffs ::= Remove(ii, a(ii))
case Left =>
jj -= 1 // insert
diffs ::= Include(jj, b(jj))
}
var off = 0
diffs map {
case Include(i, e) =>
off += 1
Include(i, e)
case Remove(i, e) =>
off -= 1
Remove(i + off + 1, e)
}
}
}