Функция подсказки орфографии используется во многих компьютерных программах для предложения правдоподобных вариантов замены слов, которые, вероятно, были написаны с ошибками.
Функции подсказки орфографии обычно включены в поисковые системы Интернета , текстовые процессоры , программы проверки орфографии , медицинские транскрипции , автоматическое переформулирование запросов и отчеты по частотной статистике.
Любой проверяющий орфографию должен иметь некоторые данные о словах в целевом языке, либо в общем употреблении, либо со специальными знаниями (например, медицинский словарь). Это может быть получено из:
Можно просто просмотреть список слов, в написании которых часто допускаются ошибки, включая, возможно, многословные фразы, чтобы узнать, есть ли в списке какие-либо из введенных слов или фраз.
Чтобы использовать словарь без заранее существующего сопоставления ошибок с исправлениями, типичный метод заключается в вычислении расстояния редактирования между входным словом и любым заданным словом в словаре. Метрика расстояния Левенштейна рассматривает «редактирование» как вставку, удаление или замену (другой буквой) одной буквы. Расстояние Дамерау–Левенштейна добавляет транспозиции (перестановку соседних букв). Слова словаря, которые находятся на расстоянии редактирования 1 от входного слова, считаются с высокой вероятностью исправлениями, расстояние редактирования 2 менее вероятным, а расстояние редактирования 3 иногда включается в предложения, а иногда игнорируется.
Корпус текста можно суммировать как словарь известных слов с частотой появления каждого слова. Это можно использовать для сортировки предложений по написанию. Например, если есть несколько предложений с расстоянием редактирования 1, слова, которые встречаются в корпусе чаще всего, скорее всего, будут желаемым исправлением.
Поскольку словарь известных слов очень большой, вычисление расстояния редактирования между входным словом и каждым словом в словаре требует больших вычислительных затрат и, следовательно, является относительно медленным. [2] Различные структуры данных могут быть использованы для ускорения поиска в хранилище, такие как BK-деревья . [3] Более быстрый подход, принятый Питером Норвигом [4], генерирует все перестановки из входного слова всех возможных правок. Для слова длиной n и алфавита размером a для расстояния редактирования 1 существует не более n удалений, n-1 транспозиций, a*n изменений и a*(n+1) вставок. [5] Используя только 26 букв английского алфавита , это даст только 54*n+25 поисков в словаре, за вычетом любых дубликатов (что зависит от конкретных букв в слове). Это относительно мало по сравнению со словарем из сотен тысяч слов. Однако для расстояния редактирования 2 и больше могут потребоваться десятки или сотни тысяч поисков. Еще одно нововведение, принятое Вольфом Гарбе, известное как SymSpell [5] («sym» от «symmetry»), ускоряет вычисления времени ввода, используя тот факт, что для входных слов необходимо генерировать только перестановки, включающие удаления, если те же перестановки с удалениями предварительно рассчитаны в словаре.
Описанные до сих пор алгоритмы не справляются с правильными словами, которых нет в словаре. Обычными источниками неизвестных слов в английском языке являются сложные слова и флексии , такие как -s и -ing . [4] Их можно учесть алгоритмически, особенно если словарь содержит часть речи .
Эти алгоритмы также предполагают, что все ошибки заданного расстояния равновероятны, что неверно. Ошибки, связанные с написанием фонетически, когда английская орфография не фонетическая, распространены, как и ошибки, которые повторяют одну и ту же букву или путают соседние буквы на клавиатуре QWERTY . Если доступен большой набор известных орфографических ошибок и исправлений, эти данные можно использовать для создания таблиц частотности для пар букв и типов редактирования; их можно использовать для более точного ранжирования предложений. [4] Также более распространено, чем вероятность, что слово будет написано на неправильном диалекте по сравнению с остальной частью текста, например, из-за различий в написании американского и британского английского . [4]
Предложения по правописанию также можно сделать более точными, принимая во внимание более одного слова за раз. [4] Многословные последовательности известны как n-граммы (где n — количество слов в последовательности). Очень большая база данных n-грамм длиной до 5 слов доступна в Google для этих и других целей. [6]
Другие экспериментировали с использованием больших объемов данных и методов глубокого обучения (форма машинного обучения ) для обучения нейронных сетей выполнять исправление орфографии. [7] [8]