Description: Resources on the Levenshtein Algorithm for fault-tolerant search. Website contains efficient implementations.
search (8652) fuzzy (39) phonetic (31) fault-tolerant (16) online demo (13) soundex (7) levenshtein (3) approximate (2) algorithmu (1) error tolerant (1)
The Levenshtein algorithm (also called Edit-Distance) calculates the least number of edit operations that are necessary to modify one string to obtain another string. The most common way of calculating this is by the dynamic programming approach. A matrix is initialized measuring in the (m,n)-cell the Levenshtein distance between the m-character prefix of one with the n-prefix of the other word. The matrix can be filled from the upper left to the lower right corner. Each jump horizontally or vertically corr
There are two possible paths through the matrix that actually produce the least cost solution. Namely
"=" Match; "o" Substitution; "+" Insertion; "-" Deletion