Re: [boost] [algorithm] Review Request: edit_distance

Subject: Re: [boost] [algorithm] Review Request: edit_distance
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2014-02-04 06:09:56

Hi Erik,

Erik Erlandson <eje_at_[hidden]> wrote:
>> > *) Runs of 'equal' dominate the script in most larger-scale applications
>> > of interest.  Actual insertions, deletions, etc, are relatively small.
>> 
>> I can't agree with that; for me, a common case is where the two inputs
>> are entirely different.
>
> Something of a tangent, but I'm curious how that works for you.   When 
> two strings are entirely different, the algorithm cost is O(NxM).  On 
> larger data, say a million elements, that's terabytes of working data, 
> and tera-ops.

This is what the max-cost / max-memory / max-time is useful for.  I just
give up and return the "trivial" output.

Regards,  Phil.