Levenshtein distance: Difference between revisions

</lang>

{{out}}

<pre>kitten, sitting: 3

rosettacode, raisethysword: 8

</pre>

=={{header|ATARI ACTION!}}==

<lang action>

DEFINE STRING="CHAR ARRAY" ; sys.act

DEFINE width="15" ; max characters 14

DEFINE MatrixSize="225" ; 15*15

PROC Set2Dm(INT ARRAY matrix, INT x,y, val)

matrix(x+y*width)=val

RETURN

INT FUNC Get2Dm(INT ARRAY matrix, INT x,y)

INT res

res=matrix(x+y*width)

RETURN(res)

INT FUNC DamerauLevenshteinDistance(STRING str1, str2)

INT ARRAY matrix(MatrixSize)

BYTE Result, tmp, Min, K, L, I, J, M, N

Result=0

M=str1(0)

N=str2(0)

FOR I=0 TO MatrixSize-1 DO matrix(I)=0 OD

FOR I=0 TO M DO Set2Dm(matrix, I,1, I) OD

FOR J=0 TO N DO Set2Dm(matrix, 1,J, J) OD

FOR J=1 TO N DO

FOR I=1 TO M DO

IF str1(I) = str2(J) THEN

tmp=Get2Dm(matrix, I-1, J-1)

Set2Dm(matrix, I,J, tmp) ; no operation required

ELSE

Min = Get2Dm(matrix, I-1,J)+1 ; REM delete

K = Get2Dm(matrix, I,J-1)+1 ; REM insert

L = Get2Dm(matrix, I-1, J-1)+1 ; REM substitution

IF K < Min THEN Min=K FI

IF L < Min THEN Min=L FI

Set2Dm(matrix, I,J, Min)

;transposition for Damerau Levenshtein Distance

;IF I>1 AND J>1 THEN

; IF str1(I) = str2(J-1) AND str1(I-1) = str2(J) THEN

; Min=Get2Dm(matrix, I,J)

; tmp=Get2Dm(matrix, I-2,J-2)+1

; IF Min>tmp THEN Min=tmp FI

; Set2Dm(matrix, I,J, Min) ; REM transposition

; FI

;FI

FI

OD

OD

Result=Get2Dm(matrix, M,N)

RETURN(Result)

PROC MAIN()

INT result

STRING Word_1(15), Word_2(15)

PUT(125)

PUTE()

SCopy(Word_1,"kitten") SCopy(Word_2,"sitting")

PrintF("%S - %S%E",Word_1,Word_2)

result=DamerauLevenshteinDistance(Word_1,Word_2)

PrintF("Levenshtein Distance=%U%E%E",result)

;PrintF("Damerau Levenshtein Distance=%U%E%E",result)

SCopy(Word_1,"rosettacode") SCopy(Word_2,"raisethysword")

PrintF("%S - %S%E",Word_1,Word_2)

result=DamerauLevenshteinDistance(Word_1,Word_2)

PrintF("Levenshtein Distance=%U%E%E",result)

;PrintF("Damerau Levenshtein Distance=%U%E%E",result)

SCopy(Word_1,"qwerty") SCopy(Word_2,"qweryt")

PrintF("%S - %S%E",Word_1,Word_2)

result=DamerauLevenshteinDistance(Word_1,Word_2)

PrintF("Levenshtein Distance=%U%E%E",result)

;PrintF("Damerau Levenshtein Distance=%U%E%E",result)

RETURN