Re: Edit distance implementation

There is a pack that implements longest common subsequence at
http://www.swi-prolog.org/pack/list?p=lcs You can build edit distance on
that.

For now it's a naive algorithm with memoization.  I'll gladly accept
patches that implement a better algorithm.

Michael
On Aug 24, 2013 1:47 PM, "Free Speech" <[email protected]> wrote:

> I forgot to mention that I need the edit ops in addition to the minimum
> distance so I need to store the ops in an array. But now I realized that to
> compute the cost alone I could just use lists if I arrange the recursion as
> loops.
>
>
> On Sat, Aug 24, 2013 at 11:03 AM, Free Speech <[email protected]>
> wrote:
>
> > It is interesting that this basic question does not seem to have a ready
> > answer yet according to Google. (swipl +edit +distance returned 0).
> >
> > A naive implementation of edit distance using iterative deepening of
> depth
> > first search runs into combinatorial blowup. The text book solution is to
> > provide memoization by building a table of intermediate results,
> basically
> > recursion through:
> >  cost(i, j) = min(cost(i-1, j)+del, cost(i, j-1)+ins, cost(i-1, j-1)+sub)
> >
> > So the question comes to how best to emulate this two dimensional array
> in
> > swipl. I am thinking of using arg/3 on an arbitrarily large term. This
> has
> > to be more efficient than dynamic predicates? Any suggestion?
> >
> > Thanks in advance.
> >
> -------------- next part --------------
> HTML attachment scrubbed and removed
> _______________________________________________
> SWI-Prolog mailing list
> [email protected]
> https://lists.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
>
-------------- next part --------------
HTML attachment scrubbed and removed