[boost] Re: Small lib proposal

From: Bohdan (warever_at_[hidden])
Date: 2002-10-21 11:26:55

"Craig Henderson" <cdm.henderson_at_[hidden]> wrote in message
news:ap09tf$lq7$1_at_main.gmane.org...
> try searching for "levenshtein distance" in Google, rather than "edit
> distance". The site I used most for my reference during developing the
> algorithm was http://www.merriampark.com/ld.htm This has a java applet
> aswell, so you can compare the results.
>
> I'll put the edit distance algo in the sandbox asap, but not untill Tuesday
> evening UK time at the earliest, I'm afraid

Thanks for links.
I don't think that using matrix for string comparison is a good idea.
Memory for matrix should be allocated dynamically, this doesn't allow
to implement fast algorithm. Besides all it has O(n*n) speed and doesn't fit
well
for two sequence difference ( parameters: 2 pairs of forward iterators ).
I think that lavenstain difference should be in boost, but it is not enough.
More interesting is some kind algorithm with some limitations and better
perfomance. I'm not ready for more detailed conversation yet. i'll read theory
about various edit-differences when i have more time and i hope to propose
alternative ways.
 But maybe your implementaion alredy doesn't use dynamic memory and is O(n) ?
Than i'm wasting time :)

regards,
bohdan.