Re: Looking for "diff" algorithm.

tmp123 wrote:
> I'm looking for an implementation of a difference algorithm.
> Example, to compare:
> [a,b,c,d,e,f] vs [a,b,d,e,g,h,i,f]
> the result can be :
> [a,b,del([c]),d,e,add([g,h,i]),f].

In order to close the query. Google for "minimal edit distance". One of
the algorithms is the O2 "Levenshtein Distance". There are a very good
explanation in the pages of Dr. M.Guilleland.

The translation to prolog gives the following results:
?- lev(['G','U','M','B','O'],['G','A','M','B','O','L'],R).
R = ['G', chg('U', 'A'), 'M', 'B', 'O', ins('L')]

This is the code (sorry for the long post, comments and improvements
are welcome, "|" is only to keep indentation):

|lev_matrix_aux2( M, N, L, R ) :-
| M=n(DM,_,_),
| N=n(DN,_,_),
| DT is DN+1,
| ( DM > DT ->
| R=n(DT,L,N)
| ;
| R=M
| ).
|
|lev_matrix_aux(_LU,U,[],_P,[],U).
|lev_matrix_aux(LU,U,[LH|LQ],[PD,PL|PQ],[RH|RQ],R) :-
| PD=n(DD,_,_),
| ( LU = LH ->
| T1=n(DD,LU,PD)
| ;
| DT1 is DD+1,
| T1=n(DT1,chg(LU,LH),PD)
| ),
| lev_matrix_aux2(T1,PL,rem(LU),T2),
| lev_matrix_aux2(T2,U,ins(LH),RH),
| lev_matrix_aux(LU,RH,LQ,[PL|PQ],RQ,R).
|
|lev_matrix([],_,_,L,L).
|lev_matrix([LH|LQ],S2,[PH|PQ],_,R) :-
| PH=n(DH,_,_),
| DT is DH+1,
| UH=n(DT,rem(LH),PH),
| lev_matrix_aux(LH,UH,S2,[PH|PQ],RH,L),
| lev_matrix(LQ,S2,[UH|RH],L,R).
|
|lev_init([],_,[]).
|lev_init([H|Q],U,[RH|RQ]) :-
| U=n(D,_,_),
| DT is D+1,
| RH=n(DT,ins(H),U),
| lev_init(Q,RH,RQ).
|
|lev_result(n(0,fail,fail),R,R).
|lev_result(n(_,L,Q),P,R) :-
| lev_result(Q,[L|P],R).
|
|lev(S1,S2,R) :-
| N0=n(0,fail,fail),
| lev_init(S2,N0,I),
| lev_matrix(S1,S2,[N0|I],_,T),
| lev_result(T,[],R).

where lev_matrix calculates the distance matrix. Each element of the
matrix contains the distance, a description of the edition, and the
previuos minimal node. Lev_result extracts the list result.

.

Relevant Pages

  • Re: Distributing n points in space
    ... distance matrix por each pair of points distance from one to the ... The n x n positive semidefinite matrix G ... negative eigenvalues or rank> k, the best approximation, in some sense, ... Now given the distance matrix D: ...
    (sci.math)
  • Re: Understanding Array indexing and the find command
    ... % diagonal of DM are zero, DM may not necessary symetric (distance from a to ... so i can get the total tour distance from the distance matrix, DM, by ... or the maximum distance between two stops as, ...
    (comp.soft-sys.matlab)
  • Re: Finding similar entries
    ... then you don't need the interpoint distance ... the huge interpoint distance matrix. ... also for free at least in SOM toolbox ...
    (comp.soft-sys.matlab)
  • Re: fast curve similarity needed
    ... For a cuve defined by N points, the distance matrix would be the NxN array of all the pairwise distances. ... The distance matrix is invariant under rotations of the curve, and by normalizing the distances you can make it invariant under uniform scaling as well. ... The functions should have the option to match curves regardless of rotation in 3D space, and be preferably invariant in terms of uniform scale as well. ...
    (comp.graphics.algorithms)