5 странных уловок для хорошей проверки правописания

Проверка орфографии является неотъемлемой частью многих продуктов и бизнес-приложений. Однако его рабочие характеристики (скорость, качество, потребление памяти) часто не оптимальны - давайте посмотрим, как сделать простую проверку орфографии быстрой и быстрой.

Краткое введение

Питер Норвиг вот уже более 10 лет вложил свою безупречно простую проверку орфографии в 21 строку кода Python. Чисто вероятностная модель выбирает наиболее вероятную замену неизвестному слову из списка слов, собранных в книге - этот минималистичный подход по-прежнему весьма актуален и может рассматриваться как базовый уровень и прототип для дальнейшей разработки, однако у него есть номер недостатков:

если ваш словарь достаточно велик (например, миллионы слов), список кандидатов будет слишком большим, чтобы правильно его ранжировать с помощью этой простой техники
никаких ограничений по скорости и памяти для данного решения не предусмотрено
он не может найти ошибки в реальном слове

Мы могли бы, конечно, назвать другие проблемы исходного кода, но давайте рассмотрим эти две основные, поскольку это всего лишь прототип - и теперь мы должны уточнить, как адаптировать алгоритм, чтобы он мог стать производственным решением.

Итак, если мы просто хотим, чтобы наша проверка орфографии работала быстро, несмотря на большой словарь (что является обычной ситуацией, когда вы собираете словарь из большого веб-корпуса или ваш язык имеет богатую морфологию - например, русский, венгерский и т. Д.) , то вам нужно найти более вежливый способ уточнить хранилище словаря и время, когда новое слово сравнивается со словарными словами, которые у вас есть.

Сейчас я попытаюсь представить 5 новых алгоритмов и структур данных, которые я использую для оптимизации проверки орфографии - trie, bk-tree, metaphone, меры расстояния, средства обнаружения RWE.

Итак, приступим: есть два шага исправления орфографии:

во-первых, вы получаете словарь и находите ошибки в тексте,
во-вторых, вы выбираете лучшую коррекцию, ранжируя словари-кандидаты

Хранение словаря

Поиск того, есть ли слово в простом словаре или структуре списка, может занять некоторое время, а может потребоваться еще больше, если вы должны измерить расстояние между словом вне словарного запаса и каждым словом в словаре, чтобы найти исправления.

1. Трие

Trie, также известное как дерево счисления или префиксное дерево, представляет собой своего рода дерево поиска - упорядоченную древовидную структуру данных, используемую для хранения динамического набора или ассоциативного массива, где ключи обычно представляют собой строки. Это похоже на двоичное дерево поиска, но для языковых данных - у вас нет ›‹ условий, но есть варианты - какая подстрока будет следующей:

Итак, все потомки узла имеют общий префикс строки, связанной с этим узлом, а корень связан с пустой строкой. В логике Python это соответствует рекурсивному словарю в словаре, где ключи - это буквы. Такая структура чрезвычайно полезна, когда вам нужно сохранить словарь в памяти, чтобы проверить, есть ли слово в словаре - вы не только объем памяти, но и время поиска уменьшается в десятки раз, так как поиск ключа в словаре, состоящем из миллионов слов, это на порядки медленнее, чем последовательный поиск в нисходящих встроенных словарях.

Вы можете создать независимый словарь-словарь для каждого списка слов, начинающихся с одной и той же буквы (A-, B- и т. Д.) Или имеющих эту букву последней и т. Д., И, таким образом, ограничить поиск кандидатов только этими trie-структурами.

Реализации:

Python C Java

Приблизительное соответствие строк

Теперь перейдем к хитростям с расстоянием между словами и оптимальным ранжированием кандидатов.

2. Bk-деревья

BK-дерево - это метрическое дерево, предложенное Уолтером Остином Буркхардом и Робертом М. Келлером [1], специально адаптированное для дискретных метрических пространств. Для простоты рассмотрим целочисленную дискретную метрику d (x, y). Тогда BK-дерево определяется следующим образом: в качестве корневого узла выбирается произвольный элемент a. У корневого узла может быть ноль или более поддеревьев. K-е поддерево рекурсивно строится из всех элементов b таких, что d (a, b) = k. BK-деревья можно использовать для приблизительного сопоставления строк в словаре:

Основная выгода от использования bk-деревьев вместо простых словарей заключается в том, что измерение расстояния между словом вне словарного запаса и каждым словом в словаре намного быстрее в такой структуре - теперь это O (log n) вместо O (п).

Реализации:

Python C Ruby Java

3. Фонетические алгоритмы

Фонетические алгоритмы широко используются при проверке орфографии, поскольку они могут значительно повысить точность поиска близкого словарного слова:

если вы используете стандартную меру расстояния, основанную на выравнивании букв, поиск обычно ограничивается кандидатами, стоящими 1-2 буквы от слова с ошибкой. Если вы увеличите это расстояние, вы, вероятно, получите слишком много нерелевантных кандидатов.
Множество типичных ошибок, вызванных преднамеренным искажением или сленговым геймификацией, отличаются от подходящего кандидата на расстоянии более двух букв: riiiiigtht - ›right, donut - ›пончик, авеню -› авеню
эти далеко не правильные примеры кандидатов кажутся каким-то образом систематически локализованными: на самом деле, эти ошибки мы можем назвать «фонетическими» или «сокращенными», и вместо использования обычных мер расстояния мы можем определить новое, фонетическое расстояние. Фонетические алгоритмы неплохо решают эту проблему.
Метафон

Алгоритм метафона [2] - [3] - один из самых популярных фонетических алгоритмов исправления орфографии. Он создает фонетический хеш для каждого слова в словаре, и, получив такой хеш для слова с ошибкой, вы можете искать лучшего кандидата через свой хешированный словарь, используя стандартные меры расстояния.

В исходных кодах метафона используются 16 согласных символов 0BFHJKLMNPRSTWXY. «0» представляет «th» (как приближение ASCII к Θ), «X» представляет «sh» или «ch», а остальные представляют их обычное английское произношение. Гласные AEIOU также используются, но только в начале кода. Текст ниже суммирует большинство правил исходной реализации:

Drop duplicate adjacent letters, except for C.
If the word begins with 'KN', 'GN', 'PN', 'AE', 'WR', drop the first letter.
Drop 'B' if after 'M' at the end of the word.
'C' transforms to 'X' if followed by 'IA' or 'H' (unless in latter case, it is part of '-SCH-', in which case it transforms to 'K'). 'C' transforms to 'S' if followed by 'I', 'E', or 'Y'. Otherwise, 'C' transforms to 'K'.
'D' transforms to 'J' if followed by 'GE', 'GY', or 'GI'. Otherwise, 'D' transforms to 'T'.
Drop 'G' if followed by 'H' and 'H' is not at the end or before a vowel. Drop 'G' if followed by 'N' or 'NED' and is at the end.
'G' transforms to 'J' if before 'I', 'E', or 'Y', and it is not in 'GG'. Otherwise, 'G' transforms to 'K'.
Drop 'H' if after vowel and not before a vowel.
'CK' transforms to 'K'.
'PH' transforms to 'F'.
'Q' transforms to 'K'.
'S' transforms to 'X' if followed by 'H', 'IO', or 'IA'.
'T' transforms to 'X' if followed by 'IA' or 'IO'. 'TH' transforms to '0'. Drop 'T' if followed by 'CH'.
'V' transforms to 'F'.
'WH' transforms to 'W' if at the beginning. Drop 'W' if not followed by a vowel.
'X' transforms to 'S' if at the beginning. Otherwise, 'X' transforms to 'KS'.
Drop 'Y' if not followed by a vowel.
'Z' transforms to 'S'.
Drop all vowels unless it is the beginning.

Алгоритм фонетического кодирования Double Metaphone является вторым поколением этого алгоритма. По сравнению с исходным алгоритмом Metaphone, он вносит ряд фундаментальных улучшений в дизайн - он использует гораздо более сложный набор правил для кодирования, чем его предшественник; например, он проверяет примерно 100 различных контекстов использования одной только буквы C.

Реализации: (вы можете написать правила для вашего собственного языка с реализациями ниже)

C (от португальского) Java (португальский) Python (испанский) Ruby (русский)

Подход с рейтингом соответствия

Подход с рейтингом соответствия (MRA) - это фонетический алгоритм, разработанный в 1977 году и впервые использованный для индексации и сравнения гомофонных имен. В отличие от Metaphone, MRA включает в себя как правила хеширования, так и их меру расстояния. Он подходит для небольших словарей и поиска сокращений и акронимов.

Правила кодирования

Delete all vowels unless the vowel begins the word
Remove the second consonant of any double consonants present
Reduce codex to 6 letters by joining the first 3 and last 3 letters only

Правила сравнения

В этом разделе слова «строка (и)» и «имя (а)» означают «закодированные строки» и «закодированные имена».

If the length difference between the encoded strings is 3 or greater, then no similarity comparison is done.
Obtain the minimum rating value by calculating the length sum of the encoded strings and using table A
Process the encoded strings from left to right and remove any identical characters found from both strings respectively.
Process the unmatched characters from right to left and remove any identical characters found from both names respectively.
Subtract the number of unmatched characters from 6 in the longer string. This is the similarity rating.
If the similarity rating equal to or greater than the minimum rating then the match is considered good.

Реализации:

C # Javascript

4. Дистанционные меры

Помимо расстояния Левенштейна, существуют некоторые нестандартные меры расстояния между строками, которые рассчитываются с использованием другого набора допустимых операций редактирования. В зависимости от того, какие ошибки вы хотите исправить, при ранжировании кандидатов с помощью функции расстояния вы можете выбрать более сложную метрику расстояния. Например, есть

Сходство Яро – Винклера измеряет минимальное количество односимвольных транспозиций, необходимых для преобразования одного слова в другое, давая более благоприятные оценки строкам, совпадающим с самого начала.
расстояние Левенштейна допускает удаление, вставку и замену;
расстояние Дамерау – Левенштейна позволяет вставку, удаление, замену и транспозицию двух соседних символов;
расстояние самая длинная общая подпоследовательность (LCS) допускает только вставку и удаление, но не замену;
Расстояние Хэмминга допускает только замену, следовательно, оно применимо только к строкам одинаковой длины.

Вы, конечно, можете реализовать свою собственную функцию - например, взять за основу расстояние Дамерау – Левенштейна и добавить к нему некоторые специальные операции, такие как перестановка кандидатов в соответствии с расстояниями клавиатуры.

Поиск ошибок в реальном слове

5. Немного базового ML для проверки орфографии.

«Увидимся через пять минут» - этот тип ошибок, когда орфографическая ошибка приводит к появлению другого нормального слова, называется ошибкой реального слова. Ошибки реального слова (RWE) найти сложнее, поскольку вы не можете обнаружить их с помощью поиска по словарю, но наиболее распространенный подход к их поиску основан на контексте.

Я не буду рекомендовать этот тип алгоритма для проверки орфографии с ограничениями скорости в реальном времени, поскольку перепроверка каждого слова в предложении и определение того, является ли контекст типичным для него или нет, не является быстрым способом проверки орфографии.

Тем не менее, иногда RWE составляют около 15% всех ошибок, и в этом случае вам следует как-то с ними бороться. Наиболее успешная модель работы с RWE описана в [4] - там вы можете найти псевдокод, основанный на словарных нограммах в качестве контекста. Другой способ найти RWE - это модель канала с шумом, которая больше не считается классическим подходом, но может быть эффективной при обнаружении ошибок такого рода.

Реализации:

Псевдо-Java Шумно-канальный Python Еще одно решение для Java

Некоторый вывод

Это ни в коем случае не исчерпывающий список структур данных и алгоритмов, которые вы можете использовать - например, мы не особо отметили решения машинного обучения для проверки орфографии или проанализировали существующие источники данных и решения с открытым исходным кодом. Пишите в комментариях, что вам было бы интересно почитать по теме.

Тем не менее, я надеюсь, что этот список дает вводные знания, если вы хотите быстро и дешево создать свою собственную проверку орфографии. Эти алгоритмы могут применяться для улучшения существующего проекта без кардинального изменения архитектуры, как дополнительный инструмент в швейцарском ноже.

Больше сообщений о развитии НЛП смотрите на моей личной странице!