Re: Edit distance implementation

Thanks for the help, Michael. Jan responded as well (not sure if it was
sent to the mailing list as I am not a subscriber):

<quote>
see http://eculture.cs.vu.nl/**europeana/pldoc/doc/srv/vnc/**
europeana/src/ClioPatria/util/**fuzzy.pl?source=true<http://eculture.cs.vu.nl/europeana/pldoc/doc/srv/vnc/europeana/src/ClioPatria/util/fuzzy.pl?source=true>
cheapest_edit_path/2.  Also node isub/3 in the NLP package.  Neither answer
your question completely, both may help.

        ---- Jan
</quote>


On Sat, Aug 24, 2013 at 4:46 PM, Michael Hendricks <[email protected]>wrote:

> 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