C Determine Weighted Levenshtein (or Edit) Distance. CHARACTER*1 A(6), B(6) INTEGER*4 D(7,7), DIR(7,7) DATA A/'M','U','L','L','E','R'/ DATA B/'H','U','L','E','R','T'/ N=6 ! len(A) M=6 ! len(B) C---------------------------------------------------------------------- C ALGORITHM. Ref: T. Kohonen, "Self-Organization & Associative Memory", C Springer-Verlag, 1988, p. 66. (Here, notation slightly simplified.) C D(0,0)=0 C for i=1 to len(A) do D(i,0)=D(i-1,0)+r(Ai) ! r(Ai)=1 C for j=1 to len(B) do D(0,j)=D(0,j-1)+q(Bj) ! q(Bj)=1 C for i=1 to len(A) do C for j=1 to len(B) do C m1=D(i-1,j-1)+p(Ai,Bj) ! p=1 if Ai=Bj; else 0 C m2=D(i,j-1)+q(Bj) C m3=D(i-1,j)+r(Ai) C D(i,j)=min(m1,m2,m3) C end C WLD=D(len(A),len(B)) C----------------------------------------------------------------------- D(1,1)=0 DO I=1,N D(I+1,1)=D(I,1)+1 ENDDO DO J=1,M D(1,J+1)=D(1,J)+1 ENDDO DO I=1,N DO J=1,M IP=1 IF (A(I).EQ.B(J)) IP=0 M1=D(I,J)+IP M2=D(I+1,J)+1 M3=D(I,J+1)+1 D(I+1,J+1)=MIN(M1,M2,M3) C NEW: det. directions followed; in case of ties, favour "diag" direction. IF (M2.LE.M1.AND.M2.LE.M3) DIR(I+1,J+1)=2 ! "rightwards" IF (M3.LE.M1.AND.M3.LE.M2) DIR(I+1,J+1)=3 ! "downwards" IF (M1.LE.M2.AND.M1.LE.M3) DIR(I+1,J+1)=1 ! "diag. right/down" ENDDO ENDDO WRITE(6,10) (A(I),I=1,N) 10 FORMAT(' String-1: ',70A1) WRITE(6,20) (B(J),J=1,M) 20 FORMAT(' String-2: ',70A1) WRITE(6,*) ' Weighted Levenshtein Distance:',D(N+1,M+1) WRITE(6,*) ' Best match:' C Trace-back: I=N+1 J=M+1 100 CONTINUE IF (I.LT.2.OR.J.LT.2) GOTO 200 WRITE(6,*) A(I-1),B(J-1) IF (DIR(I,J).EQ.1) THEN I=I-1 J=J-1 GOTO 100 ENDIF IF (DIR(I,J).EQ.2) THEN J=J-1 GOTO 100 ENDIF IF (DIR(I,J).EQ.3) THEN I=I-1 GOTO 100 ENDIF C Here, DIR(I,J)=0; we have finished the trace-back. 200 CONTINUE END