Assert 100% correctness of implementation

[lmas]

Source: #1

• Find a known good source and/or original research paper, preferably with a list of test cases and their results, so I can verify that my own implementation is 100% correct.
• Document everything for future claims

[lmas]

Exact same issue as this one, and there's probably lots more similar issues in other libs/langs :)

For now, the tests written by Nicolas Reynis is a lot more exhaustive than my own tests, so I'm porting them over here. Never found any better, prepared test cases I could use during my limited research.

Paper trail

• Damerau-Levenshtein Distance on wikipedia

• On the page is a reference to A technique for computer detection and correction of spelling errors (by Fred J. Damerau, 1964), which describes the original "Technique" (but contains no code implementation)

• Another reference on the wikipedia page is Spelling-error tolerant, order-independent pass-phrases via the damerau-levenshtein string-edit distance metric (by Gregory V. Bard, 2007), which seems to have a promising implementation. Alt. link

• That paper references An Extension of the String-to-String Correction Problem (by Roy Lowrance and Robert A. Wagner, 1975), which is a variant of the Wagner–Fischer algorithm (with the transposition extension, a la Damerau–Levenshtein)

• Wagner–Fischer algorithm on wikipedia

These papers feels a lot more safer to use as a base for a new code implementation, compared to random blog posts and other implementations found in the wild.