The Edit Distance Problem • Hacker News Board

Re: The Edit Distance Problem

#11

Post by albertcardona » Tue, Apr 21, 2009, 2:36 PM UTC

The edit distance and the algorithms to solve it have been of great use in my research work in neuroscience. The places where I can apply them are as surprising as 3D mesh reconstruction from a stack of outlines ( http://www.blender.org/community/blender-conference/blender-... ), to neuronal recognition (I'm currently finishing a paper on that; see some images here: http://albert.rierol.net/doodle_programming.html#11 ).

I know of other labs using edit distance to compare people's timelines (to estimate cost of shifting from one lifestyle to another). And the most widely use application of edit distances is in the comparison of any DNA/RNA/protein sequence for similarity, both for identification purposes and for the study of their evolution.

Re: The Edit Distance Problem

#12

Post by ovi256 » Tue, Apr 21, 2009, 4:58 PM UTC

keefe wrote: post #10

I spent a year and a half as an undergraduate converting a custom C edit distance implementation into Java for a computer assisted language instruction system. This is a really nice article discussing the topic. I think the interesting facet of dynamic programming is how it shows the dynamic between space and time. In his creative book on algorithms, Udi Manber gives a nice description of a general approach to design…

A year and a half ? How many SLOCs was that ?

Re: The Edit Distance Problem

#13

Post by jrschulz » Tue, Apr 21, 2009, 6:57 PM UTC

A completely different approach to the problem is to minimize the number of necessary distance computation in the first place. There are various indexing algorithms which make finding nearest neighbours feasible in large datasets. Incidentally, I implemented two of them. :)

http://well-adjusted.de/mspace.py

For real usage, you would probably want to reimplement them with performance in mind (and in a different language), though. My implementation is dog slow. But on the plus side, it is very readable and heavily documented.

Re: The Edit Distance Problem

#14

Post by keefe » Wed, Apr 22, 2009, 10:49 PM UTC

ovi256 wrote: post #12

keefe wrote: post #10

I spent a year and a half as an undergraduate converting a custom C edit distance implementation into Java for a computer assisted language instruction system. This is a really nice article discussing the topic. I think the interesting facet of dynamic programming is how it shows the dynamic between space and time. In his creative book on algorithms, Udi Manber gives a nice description of a general approach to design…

A year and a half ? How many SLOCs was that ?

I haven't a clue this was like 99-01, it wasn't just edit distance algorithm but also all the UI code surrounding it and optimizing things for learning a foreign language. Basically it was a quiz program in (e.g.) German which compared the student's answer to the proper answer and then generated suggestions when appropriate. We did a lot of tweaking of that code, iterating through versions starting with an attempt to just port some C code and onward - I was pretty green at that time and it wasn't a full time job, so it's not like implementing edit distance took you know, 70 man weeks...