-
Notifications
You must be signed in to change notification settings - Fork 0
/
DamerauLevenshteinDistance.act
86 lines (72 loc) · 2.5 KB
/
DamerauLevenshteinDistance.act
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
DEFINE STRING="CHAR ARRAY" ; sys.act
DEFINE width="15" ; 14 znakov max
DEFINE MatrixSize="225" ; 15*15
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=1 TO M DO matrix(I+width)=I OD
FOR J=1 TO N DO matrix(J*width)=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)
matrix(I+J*15)=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
matrix(I+J*15)=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
matrix(I+J*15)=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("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("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("Damerau Levenshtein Distance=%U%E%E",result)
SCopy(Word_1,"MARTHA") SCopy(Word_2,"MARHTA")
PrintF("%S - %S%E",Word_1,Word_2)
result=DamerauLevenshteinDistance(Word_1,Word_2)
PrintF("Damerau Levenshtein Distance=%U%E%E",result)
SCopy(Word_1,"DIXON") SCopy(Word_2,"DICKSONX")
PrintF("%S - %S%E",Word_1,Word_2)
result=DamerauLevenshteinDistance(Word_1,Word_2)
PrintF("Damerau Levenshtein Distance=%U%E%E",result)
SCopy(Word_1,"JELLYFISH") SCopy(Word_2,"SMELLYFISH")
PrintF("%S - %S%E",Word_1,Word_2)
result=DamerauLevenshteinDistance(Word_1,Word_2)
PrintF("Damerau Levenshtein Distance=%U%E%E",result)
RETURN