Допустим есть две текстовые строки введенные человеком. В каждой из строк возмножны разнообразные ошибки: пропуск букв, неправильно напечатанная буква, перестановки и пр. Как можно определить (конечно с определенной погрешностью), что эти две строки являются попыткой ввода одной и той же строки?
То есть, скажем qwerty,wqrty и qwerty,qsedft. Очевидно, что в первом случае вероятность того, что это одна и та же строка гораздо выше.
Здравствуйте, 8086, Вы писали:
8>Допустим есть две текстовые строки введенные человеком. В каждой из строк возмножны разнообразные ошибки: пропуск букв, неправильно напечатанная буква, перестановки и пр. Как можно определить (конечно с определенной погрешностью), что эти две строки являются попыткой ввода одной и той же строки?
8>То есть, скажем qwerty,wqrty и qwerty,qsedft. Очевидно, что в первом случае вероятность того, что это одна и та же строка гораздо выше.
Здравствуйте, 8086, Вы писали:
8>Допустим есть две текстовые строки введенные человеком. В каждой из строк возмножны разнообразные ошибки: пропуск букв, неправильно напечатанная буква, перестановки и пр.
Шанс, что past это ошибка в написании post МНОГО ниже, чем что это ошибка в написании last, хотя по этой сферической метрике расстояние между обоими — 1. Алгоритм должен учитывать расстояние между буквами на раскладке.
Здравствуйте, Кодёнок, Вы писали:
Кё>Шанс, что past это ошибка в написании post МНОГО ниже, чем что это ошибка в написании last, хотя по этой сферической метрике расстояние между обоими — 1. Алгоритм должен учитывать расстояние между буквами на раскладке.
Possible improvements to this algorithm include: * We can give different penalty costs to insertion, deletion and substitution. We can also give penalty costs that depend on which characters are inserted, deleted or substituted
Изменения в алгоритме минимальны. Когда-то делал что-то подобное для сравнения результатов распознавания текста с эталоном.
Здравствуйте, 8086, Вы писали:
8>... Как можно определить (конечно с определенной погрешностью), что эти две строки являются попыткой ввода одной и той же строки? 8>То есть, скажем qwerty,wqrty и qwerty,qsedft. Очевидно, что в первом случае вероятность того, что это одна и та же строка гораздо выше.
Я как то писал похожий алгоритм на скорую руку (требования к качеству и призводительности были не высокие).
1) Определяется множество букв в каждом слове (т.е без учета порядка следования). Затем находится пересечение множеств. Затем мощность пересечения(число элементов) делится на среднее арифметическое мощностей исходных множеств для двух слов. Возможны разные вариации. Получается степень похожести множеств букв.
2) Затем строятся множества всех последовательностей из двух букв. И также находятся степени соответствия этих множеств.
3) Затем для трех и т.д.
...
Потом эти показатели для последовательностей разных длин сращиваются с оперделенными весовыми коэфицентами.
Получается, вроде, неплохой результат.
...Хотя конечно вероятность ошибки при наборе, и вероятность распознать слово при чтении(похожесть) это немного разное.
При восприятии, если первая буква и последняя на своих местах, а остальные переставлены, то слово очень похоже. А при наборе маловероятно что больше 3 букв будут случайно переставлены.
...Еще надо учитывать похожесть букв "a" больше похожа на "о", чем на "и" ... Гласные больше похожи на гласные...
Здравствуйте, 8086, Вы писали:
8>Допустим есть две текстовые строки введенные человеком. В каждой из строк возмножны разнообразные ошибки: пропуск букв, неправильно напечатанная буква, перестановки и пр. Как можно определить (конечно с определенной погрешностью), что эти две строки являются попыткой ввода одной и той же строки?
8>То есть, скажем qwerty,wqrty и qwerty,qsedft. Очевидно, что в первом случае вероятность того, что это одна и та же строка гораздо выше.
Думаю можно посмотреть триграмы и суффиксные деревья, на их основе сделана орфография в nigma.ru
