On Wed, Jan 15, 2014 at 10:18 AM, Matthias BUSSONNIER < bussonniermatth...@gmail.com> wrote:
> > Le 14 janv. 2014 à 16:57, John Myles White a écrit : > > > Thanks! > > > > I'll have to check that out. I was able to translate some of the > Wikipedia code fast enough to get something working for my purposes. > > > > That was more or less what I did, > > I just found that trying to consume the minimal memory (n+1) was > significantly > slower than using (2n) IIRC. > Just someone curious here. Assuming two strings of length M and N, we can do the naive edit distance via dynamic programming, in O (MN) time and O (MN) space. However since only last row is used to determine the result, we can save the space by using O (N) memory, which is basically 2*N memory. What I don't understand is, what is this minimal memory (n + 1) you just mentioned ? > I tried a little to look into what else could be done in the literature, > but was most of the time you need some assumption on the alphabet, > or the overhead seem too significant for short strings. > > You could also try to mimic how Python difflib and SequenceMatcher works, > it's much faster but does not always give the right result[1]. > > > While you are woking on diff, interested on trying to diff IPython > notebooks ? :-) > -- > M > > > > > [1]: http://carreau.github.io/posts/08-Dear-DiffLib.html > > > > -- John > > > > On Jan 14, 2014, at 3:18 PM, Matthias BUSSONNIER < > bussonniermatth...@gmail.com> wrote: > > > >> > >> Le 14 janv. 2014 à 15:08, John Myles White a écrit : > >> > >>> Is there a package out there to compute edit distances between strings? > >> > >> I started at some point, never really finished. > >> > >> https://github.com/carreau/Diff.jl > >> > >> -- > >> M > >> > >>> > >>> -- John > >>> > >> > > > >
