I found an algorithm on
the wikipedia page so thought I'd convert it to DBC.
hide mouse
print "This program calculates the Levenshtein distance between two strings."
print "PRESS ANY KEY TO PROCEED"
wait key
do
cls
input "Please enter the source string: "; a$
input "Please enter the target string: "; b$
print
print "String A: "; a$
print "String B: "; b$
print "Levenshtein Distance from A to B: "; LevDist(a$, b$)
print
print "PRESS ANY KEY TO RESTART OR ESC TO EXIT"
wait key
loop
end
rem Levenshtein Distance
function LevDist(s$, t$)
m = len(s$)
n = len(t$)
rem for all i and j, d[i,j] will hold the Levenshtein distance between
rem the first i characters of s$ and the first j characters of t$
rem note that d has (m+1)*(n+1) values.
dim d(m, n)
rem source prefixes can be transformed into empty string by dropping all characters
for i = 1 to m
d(i, 0) = i
next i
rem target prefixes can be reached from empty source prefix by inserting every characters
for j = 1 to n
d(0, j) = j
next j
for j = 1 to n
for i = 1 to m
if mid$(s$, i) = mid$(t$, j)
d(i, j) = d(i-1, j-1) :`no operation required
else
rem find the lowest of the three values
del = d(i-1, j) + 1 :` a deletion
ins = d(i, j-1) + 1 :` an insertion
sub = d(i-1, j-1) + 1 :` a substitution
if del < ins then min = del else min = ins
if min > sub then min = sub
d(i, j) = min
endif
next i
next j
endfunction d(m, n)
I don't entirely understand it but it works.
It can be used in spell-checkers, search engines, text adventures, etc. to allow a degree of error.