0 added
0 removed
Original
2026-01-01
Modified
2026-03-10
1
<p>Теги: symspell, исправление опечаток в тексте, data scientist, bigdata, спеллчекер, расстояние дамерау-левенштейна, питер норвиг, вольф гарби, симметричные удаления</p>
1
<p>Теги: symspell, исправление опечаток в тексте, data scientist, bigdata, спеллчекер, расстояние дамерау-левенштейна, питер норвиг, вольф гарби, симметричные удаления</p>
2
<p>Концептуально логика работы<strong>спеллчекеров</strong>(программ для поиска и исправления ошибок в тексте) такова: слово, содержащее ошибку, нужно заменить на максимально похожее на него слово из числа правильных (в словаре).</p>
2
<p>Концептуально логика работы<strong>спеллчекеров</strong>(программ для поиска и исправления ошибок в тексте) такова: слово, содержащее ошибку, нужно заменить на максимально похожее на него слово из числа правильных (в словаре).</p>
3
<p>Для того, чтобы определить, какие слова "похожи", можно использовать, к примеру, расстояние<a>Дамерау-Левенштейна</a>. Если вкратце, то слово может отличаться от другого одним из четырёх способов: - вставка буквы, - удаление буквы, - замена буквы, - перестановка двух соседних букв.</p>
3
<p>Для того, чтобы определить, какие слова "похожи", можно использовать, к примеру, расстояние<a>Дамерау-Левенштейна</a>. Если вкратце, то слово может отличаться от другого одним из четырёх способов: - вставка буквы, - удаление буквы, - замена буквы, - перестановка двух соседних букв.</p>
4
<p>Каждая такая операция добавляет единицу к расстоянию Дамерау-Левенштейна. Очевидно, что подходящих кандидатов может в итоге оказаться несколько - лучший вариант в этом случае выбирается с помощью модели языка, модели ошибок и так далее. Но основную сложность с вычислительной точки зрения составляет именно генерация и обработка большого числа кандидатов.</p>
4
<p>Каждая такая операция добавляет единицу к расстоянию Дамерау-Левенштейна. Очевидно, что подходящих кандидатов может в итоге оказаться несколько - лучший вариант в этом случае выбирается с помощью модели языка, модели ошибок и так далее. Но основную сложность с вычислительной точки зрения составляет именно генерация и обработка большого числа кандидатов.</p>
5
<h2>Рассмотрим подробнее этот аспект</h2>
5
<h2>Рассмотрим подробнее этот аспект</h2>
6
<p>Подход состоит в том, чтобы вычислить расстояние для целевого слова и каждого термина из словаря, а потом выбрать замену с наименьшим значением. Но понятно, что с вычислительной точки зрения этот подход исключительно дорогой и потому непрактичный.</p>
6
<p>Подход состоит в том, чтобы вычислить расстояние для целевого слова и каждого термина из словаря, а потом выбрать замену с наименьшим значением. Но понятно, что с вычислительной точки зрения этот подход исключительно дорогой и потому непрактичный.</p>
7
<p>Более рационален подход,<a>сформулированный</a>Питером Норвигом. Его уже можно применять в реальных приложениях. Идея состоит в том, чтобы сгенерировать для каждого слова из текста все возможные редакции с нужным расстоянием (например, два), а потом посмотреть, какие из получившихся редакций есть в словаре. Этот подход намного лучше, однако тоже достаточно затратен, что особенно ярко проявляется при использовании языков с большими алфавитами (так как генерация редакций основана на алфавите).</p>
7
<p>Более рационален подход,<a>сформулированный</a>Питером Норвигом. Его уже можно применять в реальных приложениях. Идея состоит в том, чтобы сгенерировать для каждого слова из текста все возможные редакции с нужным расстоянием (например, два), а потом посмотреть, какие из получившихся редакций есть в словаре. Этот подход намного лучше, однако тоже достаточно затратен, что особенно ярко проявляется при использовании языков с большими алфавитами (так как генерация редакций основана на алфавите).</p>
8
<h2>Альтернативный подход</h2>
8
<h2>Альтернативный подход</h2>
9
<p><a>Предлагаемый</a>Вольфом Гарби (Wolf Garbe) способ основан на использовании симметричных удалений. Симметрия состоит в том, что кандидаты генерируются и на основании терминов словаря, и на основании целевого слова. На предварительном этапе для каждого термина создаются редакции с нужным расстоянием (с помощью только операции удаления символа) и включаются в словарь вместе с исходным термином. Эту операцию можно считать экономной, так как она выполняется только один раз.</p>
9
<p><a>Предлагаемый</a>Вольфом Гарби (Wolf Garbe) способ основан на использовании симметричных удалений. Симметрия состоит в том, что кандидаты генерируются и на основании терминов словаря, и на основании целевого слова. На предварительном этапе для каждого термина создаются редакции с нужным расстоянием (с помощью только операции удаления символа) и включаются в словарь вместе с исходным термином. Эту операцию можно считать экономной, так как она выполняется только один раз.</p>
10
<p>Для проверяемого слова тоже генерируются редакции с нужным расстоянием также с помощью только удалений и сравниваются со словарем. Таким образом, получается на три порядка меньше кандидатов, чем при использовании редакций всех типов для того же самого расстояния. Например, для слова длины 7 символов получится только 7 редакций при расстоянии 1. Тогда как с использованием всех четырех операций редакций будет</p>
10
<p>Для проверяемого слова тоже генерируются редакции с нужным расстоянием также с помощью только удалений и сравниваются со словарем. Таким образом, получается на три порядка меньше кандидатов, чем при использовании редакций всех типов для того же самого расстояния. Например, для слова длины 7 символов получится только 7 редакций при расстоянии 1. Тогда как с использованием всех четырех операций редакций будет</p>
11
7+<число букв в алфавите>*(7+1)+(<число букв в алфавите>-1)*7+(7-1)<p>А при увеличении максимального расстояния до 2, количество кандидатов может достигать десятков тысяч.</p>
11
7+<число букв в алфавите>*(7+1)+(<число букв в алфавите>-1)*7+(7-1)<p>А при увеличении максимального расстояния до 2, количество кандидатов может достигать десятков тысяч.</p>
12
<h2>Почему это работает?</h2>
12
<h2>Почему это работает?</h2>
13
<p>Для каждой редакции с удалением в словаре сохраняется исходный термин, из которого она была получена. При этом добавление символа в проверяемом слове с точки зрения изменения расстояния эквивалентно удалению символа в словарном слове и наоборот. Например, если в тексте встречается слово "домк" (добавлена буква "к"), одной из редакций с удалением будет правильный вариант "дом", который найдётся в словаре. С другой стороны, если в тексте пропущена буква ("дм" вместо "дом"), то слово "дм" найдётся среди редакций с удалениями в словаре и опять же приведёт к слову "дом".</p>
13
<p>Для каждой редакции с удалением в словаре сохраняется исходный термин, из которого она была получена. При этом добавление символа в проверяемом слове с точки зрения изменения расстояния эквивалентно удалению символа в словарном слове и наоборот. Например, если в тексте встречается слово "домк" (добавлена буква "к"), одной из редакций с удалением будет правильный вариант "дом", который найдётся в словаре. С другой стороны, если в тексте пропущена буква ("дм" вместо "дом"), то слово "дм" найдётся среди редакций с удалениями в словаре и опять же приведёт к слову "дом".</p>
14
<p>Используя подход Гарби (называнным им<strong>SymSpell</strong>), можно значительно увеличить скорость работы системы поиска/исправления опечаток, не усложняя её логику.</p>
14
<p>Используя подход Гарби (называнным им<strong>SymSpell</strong>), можно значительно увеличить скорость работы системы поиска/исправления опечаток, не усложняя её логику.</p>
15
<p><em>Есть вопрос? Напишите в комментариях!</em></p>
15
<p><em>Есть вопрос? Напишите в комментариях!</em></p>
16
16