Re: Edit distance implementation

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