Boost logo

Boost :

Subject: Re: [boost] RFC: edit_distance / edit_alignment library
From: Bjorn Reese (breese_at_[hidden])
Date: 2013-12-18 05:45:08


On 12/17/2013 10:22 PM, Erik Erlandson wrote:

> I did a few experiments trying to cajole the algorithms into outputting edit operations in some kind of canonical ordering. Getting the algorithms to do this natively didn't look very promising, and it left me feeling like the best solution would be to collect operations in the output-object, and then sort them after-the-fact into some desired ordering, for cases where that is important.

You are probably right. I can think of two solutions, but both are
rather complex. One solution would be to have a path-dependent cost
function (as you suggested earlier in issue #5), and the other to prune
the insert-delete combinations from the internal search tree.

Regarding your suggestion, AFAIK, the contraint is always between
adjacent path elements, and it therefore can be handled in O(1) time
in the output object via element swapping. So it seems like a feasible
solution.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk