The algorithm for allocation errors?


Warning: count(): Parameter must be an array or an object that implements Countable in /home/styllloz/public_html/qa-theme/donut-theme/qa-donut-layer.php on line 274
0 like 0 dislike
6 views
Could you tell me the algorithm for allocation errors.


At the input there are two words, one correct and the other not quite, you need to correct the word, highlight the letters that are missing, there is still a lot of things to consider, for example, one may be omitted.


For example

jahn => j^o^hn

Odnoklassniki => one^o^graders

Odnoklassniki => agnola^s^sneaky


Yandex does yandex.ru/yandsearch?text=sphix&lr=2


For links and descriptions would be appreciated.
by | 6 views

2 Answers

0 like 0 dislike
To calculate the Levenshtein distance between words, at each step the dynamics of remembering how he got there (the omission of letters, addition, replacement, matching the letter). Illumination to build the path, which obtained the minimum distance. If several vocabulary words have the same distance, choose from them the most common.
by
0 like 0 dislike
And you know in advance that the "jahn" — krivosheinym "john"? Or know, only that pair is a word from the dictionary? If the first — the easiest way stupid character for character.
If the latter — you can try a wildcard search. For example looking for the equivalent of "reccursion":
\r
r*n — too a lot of options?(+1 character)
re*n — still?
re*on... etc.
\r
accordingly, if you do not succeed, and error in the extreme letters — acting reverse(tecursion):
*ecursion -> *ecursio* -> *cursi* (for example — the correct version is found in the first iteration)
\r
This option usable SQL-LIKE tion and for a grep'
by

Related questions

0 like 0 dislike
3 answers
asked May 13, 2019 by DarkByte2015
0 like 0 dislike
1 answer
0 like 0 dislike
1 answer
110,608 questions
257,186 answers
0 comments
25,738 users