in Blog

Porovnávanie reťazcov

Možno by nebolo zlé zohľadnovať v textovkách preklepy. Ako na to? Na meranie rozdielnosti dvoch reťazcov sa dajú použiť rôzne metódy, ale najviac sa mi osvedčili dve nasledujúce.

1) Levenshteinova vzdialenosť je algoritmus na nájdenie minimálneho počtu zmien znakov, ktoré treba urobiť, aby sme docielili zhodu zdrojových textov. Využívajú sa na to operácie ako vloženie, zmazanie znaku a substitúcia s rovnakou váhou. Odvodená Damerau Levenshteinova vzdialenosť podporuje naviac transpozíciu písmen, ktorú považuje za jednu úpravu.

2) Jaro Distance podporuje len transpozíciu písmen a zobrazuje vzdialenosti slov v intervale <0,1>. Jednotka predstavuje identické slová. Od toho odvodená Jaro-Winkler Distance zohľadňuje navyše aj dĺžku spoločného prefixu. Vďaka tomu dáva presnejšie výsledky pre reťazce so spoločným prefixom a je vhodnejšia na meranie vzdialeností slovenských slov.

Presnejší matematický popis sa dá ľahko nájsť na Wikipédii Damerau–Levenshtein distance a Jaro–Winkler distance. Rovnako aj zdrojové kódy nie je veľký problém nájsť. Nenašiel som však verziu pre Atari a Pedro ich pre mňa prepísal do Turbo-BASIC XL a keď už bol rozbehnutý urobil rovno aj verziu pre Action!.

 

Verzia pre Turbo-BASIC XL (veľkosť reťazcov 20 znakov)

 

Damerau Levenshtein Distance v Turbo-BASIC XL
download: Damerau Levenshtein Distance Turbo-BASIC XL

10 DIM Word_1$(20), Word_2$(20), DLDm(21, 21)
11 CLS
20 Word_1$="kitten" : Word_2$="sitting" : ? Word_1$;" - ";Word_2$ : EXEC _DLD_ : ?
30 Word_1$="rosettacode" : Word_2$="raisethysword" : ? Word_1$;" - ";Word_2$ : EXEC _DLD_ : ?
40 Word_1$="qwerty" : Word_2$="qweryt" : ? Word_1$;" - ";Word_2$ : EXEC _DLD_ : ?
 
11000 END
11600 REM DamerauLevenshteinDistance INPUT(Word_1$, Word_2$, DLDm[]) USE(I, J, K, L, M, N, Min) RETURN(INT Result)
11600 PROC _DLD_
11610   Result=0 : M=LEN(Word_1$) : N=LEN(Word_2$)
11620   FOR I=0 TO M : DLDm(I,1)=I : NEXT I
11630   FOR J=0 TO N : DLDm(1,J)=J : NEXT J
11640   FOR J=1 TO N
11650     FOR I=1 TO M
11660       IF Word_1$(I,I) = Word_2$(J,J)
11670         DLDm(I,J) = DLDm(I-1, J-1) : REM no operation required
11680       ELSE
11690         Min = DLDm(I-1, J)+1 : REM delete
11700         K = DLDm(I, J-1)+1   : REM insert
11710         L = DLDm(I-1, J-1)+1 : REM substitution
11720         IF K &lt; Min THEN Min=K
11730         IF L &lt; Min THEN Min=L 11740 DLDm(I,J) = Min 11750 REM IF I&gt;1 AND J&gt;1 
11760 REM          IF Word_1$(I,I) = Word_2$(J-1,J-1) AND Word_1$(I-1,I-1) = Word_2$(J,J)
11770 REM              Min=DLDm(I,J) : IF Min&gt;(DLDm(I-2,J-2)+1) THEN Min=(DLDm(I-2,J-2)+1)
11780 REM              DLDm(I,J) = Min : REM transposition
11790 REM          ENDIF
11800 REM     ENDIF
11810       ENDIF
11820     NEXT I
11830   NEXT J
11840   Result=DLDm(M,N)
11845   REM ? "Damerau Levenshtein Distance=";Result
11846   ? "Levenshtein Distance=";Result
11850 ENDPROC

Príklad ráta Levenshtein Distance a pokiaľ chcete Damerau Levenshtein Distance je nutné odkomentovať riadky 11750 až 11800.

Jaro Winkler Distance v Turbo-BASIC XL
download: Jaro Winkler Distance Turbo-BASIC XL

10 DIM Word_1$(20), Word_2$(20), Z$(20)
11 CLS
20 Word_1$="MARTHA" : Word_2$="MARHTA" : ? Word_1$;" - ";Word_2$ : EXEC _JWD_ : ?
30 Word_1$="DIXON" : Word_2$="DICKSONX" : ? Word_1$;" - ";Word_2$ : EXEC _JWD_ : ?
40 Word_1$="JELLYFISH" : Word_2$="SMELLYFISH" : ? Word_1$;" - ";Word_2$ : EXEC _JWD_ : ?
 
11000 END
12000 REM JaroWinklerDistance INPUT(Word_1$, Word_2$) USE(Z$, I, J, K, L, M, N, S1, S2, Min, Max) RETURN(FLOAT Result)
12000 PROC _JWD_
12010   Result=0 : S1=LEN(Word_1$) : S2=LEN(Word_2$)
12020   IF S1&gt;S2 THEN Z$=Word_1$ : Word_1$=Word_2$ : Word_2$=Z$ : M=S1 : S1=S2 : S2=M
12030   J=1: M=0 : N=0 : L=INT(S2/2) : Z$=Word_2$
12040   FOR I=1 TO S1
12050     IF Word_1$(I,I)=Word_2$(J,J) THEN M=M+1: Word_2$(J,J)=" ": GO# JMP_JWD
12060     Max=1 : IF Max&lt;(I-L) THEN Max=I-L 12070 Min=S2 : IF Min&gt;(I+L) THEN Min=I+L
12080     FOR K=Max TO Min
12090       IF Word_1$(I,I)=Word_2$(K,K) THEN N=N+1: M=M+1: Word_2$(K,K)=" ": IF K&gt;J THEN J=K
12100     NEXT K
12110     #JMP_JWD : IF JS2 THEN Min=S2
12210   M=Min : IF M&gt;3 THEN M=3
12220   M=M+1 : L=0 : Word_2$=Z$ : IF M&gt;Min THEN M=Min
12230   FOR I=1 TO M
12240     IF Word_1$(I,I)=Word_2$(I,I)
12250       L=L+1
12260     ELSE
12270       EXIT
12280     ENDIF
12290   NEXT I
12300   Result=Result + (L*0.1*(1.0 - Result)) : REM Winkler
12310   ? "Jaro Winkler Distance=";Result
12320 ENDPROC

 

Verzia pre Action! (veľkosť reťazcov 14 znakov)

 

Damerau Levenshtein Distance v Action!
download: Damerau Levenshtein Distance Action!

DEFINE STRING="CHAR ARRAY" ; sys.act
DEFINE width="15" ; 14 znakov max
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 &lt; Min THEN Min=K FI
        IF L &lt; Min THEN Min=L FI Set2Dm(matrix, I,J, Min) ;transposition for Damerau Levenshtein Distance ;IF I&gt;1 AND J&gt;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&gt;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

Opäť sa ráta Levenshtein Distance a pokiaľ chcete Damerau Levenshtein Distance je nutné odkomentovať zopár riadkov. Len tak mimochodom, tá rýchlosť oproti Basicu je celkom slušný rozdiel 😉

Jaro Winkler Distance v Action!
S Jaro Winkler Distance nastupuje malá komplikácia. Action! podporuje len celé čísla 🙂 je preto nutné posunúť vhodne desatinnú čiarku a zaokrúhliť. Iste dalo by sa využiť matematické funkcie uložené v ROMke, ale to je zbytočne pracné.
download: Jaro Winkler Distance Action!

DEFINE STRING="CHAR ARRAY" ; sys.act
DEFINE ASCII_SpaceBar="32"
 
INT FUNC JaroWinklerDistance(STRING str1, str2)
  STRING Z(15)
  INT S1, S2, J, M, N, L, I, K, skip, Max, Min
  INT Result
  Result=0
  S1=str1(0)
  S2=str2(0)
  IF S1&gt;S2 THEN
    SCopy(Z,str1)
    SCopy(str1,str2)
    SCopy(str2,Z)
    M=S1
    S1=S2
    S2=M
  FI
  J=1 M=0 N=0 L=S2/2 SCopy(Z,str2)
  FOR I=1 TO S1 DO
    skip=0
    IF str1(I)=str2(J) THEN
      M==+1
      str2(J)=ASCII_SpaceBar
      skip=1
    FI
    IF skip=0 THEN
      Max=1
      IF Max&lt;(I-L) THEN Max=I-L FI Min=S2 IF Min&gt;(I+L) THEN Min=I+L FI
      FOR K=Max TO Min DO
        IF str1(I)=str2(K) THEN
          N==+1
          M==+1
          str2(K)=ASCII_SpaceBar
          IF K&gt;J THEN J=K FI
        FI
      OD
    FI
    IF JS2 THEN Min=S2 FI
  M=Min IF M&gt;3 THEN M=3 FI
  M==+1 L=0 SCopy(str2,Z)
  IF M&gt;Min THEN M=Min FI
  FOR I=1 TO M DO
    IF str1(I)=str2(I) THEN
      L==+1
    ELSE
      EXIT
    FI
  OD
  Result=Result*100 + (((L*100)/10)*(100 - Result)) ; Winkler  
  Result=(Result+49)/100
RETURN(Result)
 
PROC MAIN()
  INT result
  STRING Word_1(15), Word_2(15)
  PUT(125)
  PUTE()
 
  SCopy(Word_1,"MARTHA") SCopy(Word_2,"MARHTA")
  PrintF("%S - %S%E",Word_1,Word_2)
  result=JaroWinklerDistance(Word_1,Word_2)
  PrintF("Jaro Winkler Distance=%U%E%E",result)
 
  SCopy(Word_1,"DIXON") SCopy(Word_2,"DICKSONX")
  PrintF("%S - %S%E",Word_1,Word_2)
  result=JaroWinklerDistance(Word_1,Word_2)
  PrintF("Jaro Winkler Distance=%U%E%E",result)
 
  SCopy(Word_1,"JELLYFISH") SCopy(Word_2,"SMELLYFISH")
  PrintF("%S - %S%E",Word_1,Word_2)
  result=JaroWinklerDistance(Word_1,Word_2)
  PrintF("Jaro Winkler Distance=%U%E%E",result)
RETURN

Ukážka výpočtu Damerau Distance a Damerau Levenshtein Distance v oboch jazykoch:


Na príklade s QWERTY je pekne vydieť rozdiel v oboch spôsoboch výpočtu.

Ukážka výpočtu Jaro Winkler Distance v oboch jazykoch:

Ktorý z nich je Action! je myslím jasné 🙂

Príklady prihodil aj na Rosetta Code
https://rosettacode.org/wiki/Levenshtein_distance
https://rosettacode.org/wiki/Jaro_distance

Write a Comment

Comment

Táto webová stránka používa Akismet na redukciu spamu. Získajte viac informácií o tom, ako sú vaše údaje z komentárov spracovávané.