On Mar 22, 2011, at 12:30 PM, Mark Engelberg wrote: > Of course, in most languages the Levenshtein distance is computed using the > bottom-up Dynamic Programming strategy of filling in a matrix left-to-right, > one row at a time, thus ensuring that all the entries needed to compute a > given entry are already available. There is pseudocode for this approach on > the Wikipedia, and I think I've seen both a Perl and Scheme solution that > improve upon that by storing only one row's worth of data, rather than the > full matrix. Clojure certainly would support such a strategy, and in fact, > that's probably the better way to solve this problem. One way to implement > the DP solution would be to pass the grid in an accumulator, and for such a > strategy you wouldn't need memoization, so perhaps that's what Tim had in > mind.
A pretty sizable set of example LD implementations are available here: http://www.merriampark.com/ld.htm (applet warning! :-/) The advantage of the single row of data is that you're not limited in the size of strings you can compare -- constructing a full matrix will very large strings will blow your heap in most cases. I implemented a flavour of LD that uses an array instead of a matrix to get around this problem years ago; I *think* it's in apache commons-lang still. In any case, the implementation is here, with some explanatory verbiage: http://www.merriampark.com/ldjava.htm - Chas -- 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
