2 ms·
I think practical solution to this is to return all words that are within a Levenshtein distance[1] of 2*number_accented_characters of the original word, ranke
by nl 7y ago
I think practical solution to this is to return all words that are within a Levenshtein distance[1] of 2*number_accented_characters of the original word, ranked by the distance.
Levenshtein distance can be calculated using a trie[2] so it's fast enough for most purposes.
If you wanted to get fancy you could modify the Levenshtein to reduce the distance penalty on accented characters, and/or only apply the Levenshtein calculation within 1 character of an accented character or the equivalent ASCII substitution sequence.
[1] https://en.wikipedia.org/wiki/Levenshtein_distance https://en.wikipedia.org/wiki/Levenshtein_distance
[2] http://stevehanov.ca/blog/?id=114 http://stevehanov.ca/blog/?id=114