Talk:Approximate string matching

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated C-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.

What is a transposition?[edit]

This article says "transpositions" are not considered primitive operations. What is a transposition? Danielx 05:39, 13 August 2006 (UTC)

A transposition is a swap in the position of two letters. I've added the definition to the article.Bill 16:51, 7 September 2006 (UTC)

Serious flaw?[edit]

In the article, one sentence is "For example, if the pattern is coil, foil differs by one substitution, coils by one insertion, oil by one deletion, and coal by two subsitutions." "coil" and "coal" differ by 2 subsitutions? How? I can only see the "i" is subsitute by "a".

Yes, you're right. "coal" should have been "foal". I've fixed it.Bill 16:51, 7 September 2006 (UTC)

Citations needed[edit]

I've flagged the assertions in this article that likely hold "as is" or with some rewording with {{citationneeded}} tags, but which I feel would be best backed up with specific citations. The citationneeded tags are not intended to be challenges -- I won't be removing the assertions.

I'll see what I can do about tracking down some specific citations in the spirit of {{sofixit}}. -- QTJ 21:15, 10 November 2006 (UTC)


I think this article should be expanded somewhat. I'd like to have at least 1) a formal definition of the problem, 2) a brute-force algorithm, 3) a better algorithm (which one?)

Any suggestions? Offliner (talk) 23:52, 27 December 2008 (UTC)

I added the three things I mentioned. Not sure if my explanation is very readable, but at least it's a start. One could also provide pseudocode for the algorithm (it's essentially the same algorithm as in the Levenshtein distance article; one must only initialize the first row with zeros, save the computational path somewhere and add the backwards-working phase), but I don't have the time at the moment. Offliner (talk) 09:02, 1 January 2009 (UTC)