The Edit Distance Problem
rjlipton.wordpress.com
The Edit Distance Problem
1–10 of 14 posts
Re: The Edit Distance Problem
#2For a bit-parallel approach to this problem, see: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.4...
Re: The Edit Distance Problem
#3Dick Lipton's blog has a huge collection of really amazing kiddie pool tastes and pointers within awesome nuggets of theoretical computer science, one of his posts that I want to walk through carefully when i have the time is the one on the quantum method, for proving various nifty algorithmic complexity results etc.
http://rjlipton.wordpress.com/2009/03/28/erds-and-the-quantu...
sexy stuff
Re: The Edit Distance Problem
#4Dick Lipton's blog has a huge collection of really amazing kiddie pool tastes and pointers within awesome nuggets of theoretical computer science, one of his posts that I want to walk through carefully when i have the time is the one on the quantum method, for proving various nifty algorithmic complexity results etc. http://rjlipton.wordpress.com/2009/03/28/erds-and-the-quantu... sexy stuff
It is indeed amazing. But why put so much effort into a blog? Makes you wonder whether this blog is intended primarily to attract more PhD students to the field.
Re: The Edit Distance Problem
#5Dick Lipton's blog has a huge collection of really amazing kiddie pool tastes and pointers within awesome nuggets of theoretical computer science, one of his posts that I want to walk through carefully when i have the time is the one on the quantum method, for proving various nifty algorithmic complexity results etc. http://rjlipton.wordpress.com/2009/03/28/erds-and-the-quantu... sexy stuff
It is indeed amazing. But why put so much effort into a blog? Makes you wonder whether this blog is intended primarily to attract more PhD students to the field.
Prof. Lipton is, after all, a professor. From his blog, it seems that he truly likes teaching and exposing ideas. An excerpt from his blog:
"I have worked in the area of theory of computation since 1973. I find the whole area exciting and want to share some of that excitement with you."
Many times, interesting ideas which can be explained to a non-expert are scattered in countless papers and books, and it's hard for someone new in the field to put all the pieces together by himself. Thus, a blog seems a great idea:
* it's much faster and more informal than peer-reviewed publications.
* it allows one to communicate ideas to a broader audience.
* it allows one to have almost immediate feedback from the readers.
* it's open to everyone who happens to be interested!
Re: The Edit Distance Problem
#6Dick Lipton's blog has a huge collection of really amazing kiddie pool tastes and pointers within awesome nuggets of theoretical computer science, one of his posts that I want to walk through carefully when i have the time is the one on the quantum method, for proving various nifty algorithmic complexity results etc. http://rjlipton.wordpress.com/2009/03/28/erds-and-the-quantu... sexy stuff
It is indeed amazing. But why put so much effort into a blog? Makes you wonder whether this blog is intended primarily to attract more PhD students to the field.
I think it can be more accurately thought of as a way to make it easier for students to start learning new topics that aren't nearly textbook ready
Re: The Edit Distance Problem
#7Dick Lipton's blog has a huge collection of really amazing kiddie pool tastes and pointers within awesome nuggets of theoretical computer science, one of his posts that I want to walk through carefully when i have the time is the one on the quantum method, for proving various nifty algorithmic complexity results etc. http://rjlipton.wordpress.com/2009/03/28/erds-and-the-quantu... sexy stuff
It is indeed amazing. But why put so much effort into a blog? Makes you wonder whether this blog is intended primarily to attract more PhD students to the field.
It makes a lot more sense to publish scientific results on the web than on paper. Hyperlinks, more graphs, more data, less costs, more feedback. Scientists still publish in journals because of inertia and an antiquated incentive structure (grant money is proportional to the number of published papers, esp. in high-profile journals). I hope we'll eventually make the transition, and possibly, so does the author of that blog.
Re: The Edit Distance Problem
#8I thought I would post a practical application, FWIW. I recently applied edit distance to a problem I was facing on my free dating site. Being free, we attract an inordinate number of scammers. I've been developing an arsenal of tools to help identify and track suspects in order to delete their accounts before they do too much damage. The most successful to date has used edit distance.
Scammers tend to post identical or slightly altered messages to a large number of users. As you might expect, this has the effect of quickly polluting the valid ecosystem. The solution I employed was to delay sending messages between users long enough to capture spammer patterns and compare the messages to one another.
I use the Levenshtein distance algorithm (which has O(n^2) performance). If I get a similarity over a certain threshold. I quarantine the message for further analysis. To work around the performance, I bound the problem by capping the number of messages used for analysis.
It has been incredibly effective.
Re: The Edit Distance Problem
#9What a coincidence! I have been looking at the edit distance problem, because it can be applied to computer vision. One of the uses is if you have a stereo image pair you can figure out the depth of the objects in the scene, by matching corresponding features. The edit distance problem helps with figuring out which pixels in one stereo image correspond to pixels in the other stereo image.
I am hoping with a bit more effort I can understand the dynamic programming side of it better.
Re: The Edit Distance Problem
#10I 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 designing algorithms with dynamic programming.