this was a vb basic source until gfa altercation.
https://www.google.com/search?q=levenshtein+distance&
can dim operate properly in a sub routine as illustrated?
Code: Select all
' sof
LIST "a:\levens2.lst"
' ********************************
' * Compute Levenshtein Distance/Edit Distance *
' * GFA Basic *
' ********************************
' * see description *
' ********************************
'
PRINT @ld("GSSBO","GUSB")
'
END
'
> FUNCTION ld(s$,t$)
' m& length of t
' n& length of s
' i& iterates through s
' j& iterates through t
' s_i$ ith character of s
' t_j$ jth character of t
' cost& cost
'
LOCAL m&,n&,i&,j&,s_i$,t_j$,cost&
'
DIM d3&(2)
'
' = Step 1
n&=LEN(s$)
m&=LEN(t$)
'
IF n&=0 THEN
RETURN m&
ENDIF
IF m&=0 THEN
RETURN n&
ENDIF
'
DIM d&(n&,m&)
'
' = Step 2
FOR i&=0 TO n&
d&(i&,0)=i&
NEXT i&
FOR j&=0 TO m&
d&(0,j&)=j&
NEXT j&
'
' = Step 3
FOR i&=1 TO n&
s_i$=MID$(s$,i&,1)
'
' = Step 4
FOR j&=1 TO m&
t_j$=MID$(t$,j&,1)
'
' = Step 5
' IF s_i$=t_j$
' cost&=0
' ELSE
' cost&=1
' ENDIF
'
cost&=succ(s_i$=t_j$)
'
' = Step 6
d3&(0)=SUCC(d&(PRED(i&),j&))
d3&(1)=SUCC(d&(i&,PRED(j&)))
d3&(2)=ADD(d&(PRED(i&),PRED(j&)),cost&)
'
QSORT d3&()
'
d&(i&,j&)=d3&(0)
'
NEXT j&
NEXT i&
'
' = Step 7
levenshtein&=d&(n&,m&)
ERASE d&(),d3&()
RETURN levenshtein&
'
ENDFUNC
> PROCEDURE description
' The Algorithm steps
' Step Description
' 1 Set n to be the length of s.
' Set m to be the length of t.
' If n = 0, return m and exit.
' If m = 0, return n and exit.
' Construct a matrix containing 0..m rows and 0..n columns.
' 2 Initialize the first row to 0..n.
' Initialize the first column to 0..m.
' 3 Examine each character of s (i from 1 to n).
' 4 Examine each character of t (j from 1 to m).
' 5 If s[i] equals t[j], the cost is 0.
' If s[i] doesn't equal t[j], the cost is 1.
' 6 Set cell d[i,j] of the matrix equal to the minimum of:
' a. The cell immediately above plus 1: d[i-1,j] + 1.
' b. The cell immediately to the left plus 1: d[i,j-1] + 1.
' c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost.
' 7 After the iteration steps (3, 4, 5, 6) are complete, the distance is found in cell d[n,m].
example
' This section shows how the Levenshtein distance
' is computed when the source string
' is "GUMBO" and the target string is "GAMBOL".
' Steps 1 and 2
' G U M B O
' 0 1 2 3 4 5
' G 1
' A 2
' M 3
' B 4
' O 5
' L 6
' Steps 3 to 6 When i = 1
' G U M B O
' 0 1 2 3 4 5
' G 1 0
' A 2 1
' M 3 2
' B 4 3
' O 5 4
' L 6 5
' Steps 3 to 6 When i = 2
' G U M B O
' 0 1 2 3 4 5
' G 1 0 1
' A 2 1 1
' M 3 2 2
' B 4 3 3
' O 5 4 4
' L 6 5 5
' Steps 3 to 6 When i = 3
' G U M B O
' 0 1 2 3 4 5
' G 1 0 1 2
' A 2 1 1 2
' M 3 2 2 1
' B 4 3 3 2
' O 5 4 4 3
' L 6 5 5 4
' Steps 3 to 6 When i = 4
' G U M B O
' 0 1 2 3 4 5
' G 1 0 1 2 3
' A 2 1 1 2 3
' M 3 2 2 1 2
' B 4 3 3 2 1
' O 5 4 4 3 2
' L 6 5 5 4 3
' Steps 3 to 6 When i = 5
' G U M B O
' 0 1 2 3 4 5
' G 1 0 1 2 3 4
' A 2 1 1 2 3 4
' M 3 2 2 1 2 3
' B 4 3 3 2 1 2
' O 5 4 4 3 2 1
' L 6 5 5 4 3 2
' Step 7
' The distance is in the lower right hand corner of
' the matrix, i.e. 2. This corresponds to our intuitive
' realization that "GUMBO" can be transformed into "GAMBOL"
' by substituting "A" for "U" and adding "L"
' (one substitution and 1 insertion = 2 changes
RETURN
' eof