Database Reference
In-Depth Information
Algorithm 2.1.1:
Edit Distance Verification (
s, r, θ
)
if
>θ
:
return
false
Construct a table
T
of 2 rows and
||
s
|−|
r
||
|
r
|
+ 1 columns
for
j
=1
to
min(
|
r
|
+1
,
1+
θ
):
T
[1][
j
]=
j
−
1
Set
m
=
θ
+1
for
i
=2
to
|
s
|
+1
for
j
= min(1
,i − θ
)
to
min(
|r|
+1
,i
+
θ
)
d
1
=(
j<i
+
θ
)?
T
[1][
j
]+1 :
∞
d
2
=(
j>
1) ?
T
[2][
j
−
1] + 1 :
∞
d
3
=(
j>
1) ?
T
[1][
j −
1]+
(
s
[
i
do
−
1] =
r
[
j
−
1]) ? 0 : 1) :
∞
T
[2][
j
] = min(
d
1
,d
2
,d
3
)
m
= min(
m, T
[2][
j
])
if
m>θ
:
return false
for
j
=0
to
|
r
|
+1:
T
[1][
j
]=
T
[2][
j
]
return
true
Table 2.1. Sample execution of the dynamic pro-
gramming verification algorithm for edit distance
with threshold
θ
= 2. The algorithm returns false.
∅
One
Laptop
∅
012
11123
22233
L
3
3
3
4
3
a
44443
p
55543
t
66543
o
76543
p
76543
A plethora of extensions to the basic edit distance exist. For exam-
ple, one can extend the primitive edit operations to include a transposi-
tion of two consecutive characters. This extended edit distance has been
shown to cover most spelling mistakes made by humans in written text.
One can also compute a normalized edit distance, defined as
E
(
s,r
)
max
,
|
s
|
,
|
r
|
