On 30 May 2011 22:19, joshua-choi <rbysam...@gmail.com> wrote: > Thanks for the reply. Levenshtein distance would be especially useful > for when I need to compare general strings, with a general amount of > edits between them. > > Unfortunately, the problem isn't so much determining whether any two > strings are one edit apart: that can be done just by checking if the > first two, first and third, or last two characters of one string > equals those of the other. > > The problem is which strings you compare with to determine which ones > are one edit apart. Right now, I have to compare every string with > every other string, but it seems really wasteful, seemingly being in > O(n^2) time. I just can't figure out how to make it more efficient, > though.
Perhaps you could use nilsimsa and the string length to find similar strings and then compare only those to each other? Just a guess :) > I'm hoping that this a common problem with a common solution, like > using some data structure I haven't thought of. > > On May 30, 1:01 pm, Laurent PETIT <laurent.pe...@gmail.com> wrote: >> Hi, >> >> there's the levenshtein distance algorithm which will help you >> determine which string is one "edit" close to another (since all your >> strings are of length 3, then the distance will inevitably be a single >> replacement if of size one). >> >> Don't know if that helps, anyway here's a compact functional >> implementation:https://gist.github.com/828413 >> >> 2011/5/30 joshua-choi <rbysam...@gmail.com>: >> >> >> >> >> >> >> >> > Let's say that I have a set of strings, each three English letters >> > long. >> >> > How can I determine which strings differ only at one location (e.g. >> > "xxe" and "xbe")? >> >> > Right now, I'm writing a loop that sequentially compares every string >> > to every other string. I think that there's a better way, but I don't >> > know where to start. -- Michael Wood <esiot...@gmail.com> -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
