core :: Text :: levenshtein_distance
assert "abcd".levenshtein_distance("abcd") == 0
assert "".levenshtein_distance("abcd") == 4
assert "abcd".levenshtein_distance("") == 4
assert "abcd".levenshtein_distance("xyz") == 4
assert "abcd".levenshtein_distance("xbdy") == 3
# Return the Levenshtein distance between two strings
#
# ~~~
# assert "abcd".levenshtein_distance("abcd") == 0
# assert "".levenshtein_distance("abcd") == 4
# assert "abcd".levenshtein_distance("") == 4
# assert "abcd".levenshtein_distance("xyz") == 4
# assert "abcd".levenshtein_distance("xbdy") == 3
# ~~~
fun levenshtein_distance(other: String): Int
do
var slen = self.length
var olen = other.length
# fast cases
if slen == 0 then return olen
if olen == 0 then return slen
if self == other then return 0
# previous row of distances
var v0 = new Array[Int].with_capacity(olen+1)
# current row of distances
var v1 = new Array[Int].with_capacity(olen+1)
for j in [0..olen] do
# prefix insert cost
v0[j] = j
end
for i in [0..slen[ do
# prefix delete cost
v1[0] = i + 1
for j in [0..olen[ do
# delete cost
var cost1 = v1[j] + 1
# insert cost
var cost2 = v0[j + 1] + 1
# same char cost (+0)
var cost3 = v0[j]
# change cost
if self[i] != other[j] then cost3 += 1
# keep the min
v1[j+1] = cost1.min(cost2).min(cost3)
end
# Switch columns:
# * v1 become v0 in the next iteration
# * old v0 is reused as the new v1
var tmp = v1
v1 = v0
v0 = tmp
end
return v0[olen]
end
lib/core/text/abstract_text.nit:1156,2--1213,4