Предложение правописания - это функция многих компьютерных программных приложений, используемых для предложения подходящих замен для слов, которые, вероятно, были написаны с ошибками.
Функции предложения правописания обычно включены в поисковые системы Интернета , текстовые процессоры , средства проверки орфографии , медицинскую транскрипцию , автоматическое переформулирование запросов и статистические отчеты журнала частоты.
Алгоритмы
Любая программа проверки орфографии должна иметь некоторые данные о словах на целевом языке, как в общем употреблении, так и со специальными знаниями (например, с медицинской лексикой). Это может произойти из-за:
- Словарь всех известных слов.
- Текст корпус , который включает в себя типичный текст, как известно, написаны правильно.
- Список часто используемых слов с ошибками и исправлениями.
- Журналы ввода человеческого текста, например, из популярной поисковой системы . По сути, это краудсорсинговый корпус, но предполагается, что будут некоторые орфографические ошибки. Могут быть включены данные о том, когда люди нажимают на вариант написания или делают второй, очень похожий запрос; это создает краудсорсинговое сопоставление слов с ошибками и надежных исправлений. [1]
Список часто используемых слов с ошибками, возможно, включая фразы из нескольких слов, можно просто проконсультироваться, чтобы увидеть, есть ли в списке какие-либо входные слова или фразы.
Чтобы использовать словарь без ранее существовавшего сопоставления орфографических ошибок с исправлениями, типичным методом является вычисление расстояния редактирования между входным словом и любым заданным словом в словаре. Расстояние Левенштейна метрика рассматривает «редактировать» , чтобы быть вставка, удаление или замена (с другой буквой) из одной буквы. Расстояние Дамерау – Левенштейна добавляет транспозиции (перестановку соседних букв). Словарные слова, которые находятся на расстоянии редактирования 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» от слова «симметрия»), ускоряет вычисление времени ввода за счет использования того факта, что для входных слов необходимо генерировать только перестановки, включающие удаления, если такое же удаление перестановки рассчитываются по словарю.
Описанные до сих пор алгоритмы плохо справляются с правильными словами, которых нет в словаре. Обычными источниками неизвестных слов в английском языке являются составные слова и флексии , такие как -s и -ing . [4] Их можно учесть алгоритмически, особенно если словарь содержит часть речи .
Эти алгоритмы также предполагали, что все ошибки на данном расстоянии равновероятны, что неверно. Ошибки, связанные с фонетическим правописанием, когда английская орфография не фонетическая, являются обычными, как и ошибки, которые повторяют одну и ту же букву или путают соседние буквы на клавиатуре QWERTY . Если доступен большой набор известных орфографических ошибок и исправлений, эти данные можно использовать для создания частотных таблиц для пар букв и типов редактирования; их можно использовать для более точного ранжирования предложений. [4] Также чаще, чем шанс, что слово написано на неправильном диалекте по сравнению с остальным текстом, например, из-за различий в написании американского и британского английского языков . [4]
Предложения по правописанию также можно сделать более точными, если одновременно учитывать более одного слова. [4] Последовательности из нескольких слов известны как n-граммы (где n - количество слов в последовательности). Для этой и других целей у Google доступна очень большая база данных n-граммов длиной до 5 слов. [6]
Другие экспериментировали с использованием больших объемов данных и методов глубокого обучения (форма машинного обучения для обучения нейронных сетей исправлению орфографии. [7] [8]
Рекомендации
- ↑ Search 101 - вице-президент Google по инженерным вопросам и ИТ-директор Дуглас Меррилл
- ^ Изменить расстояние
- ^ Чертовски крутые алгоритмы, часть 1: BK-деревья
- ^ a b c d e Как написать корректор орфографии
- ^ a b Алгоритм исправления орфографии в 1000 раз быстрее (2012)
- ^ Алекс Франц; Торстен Бранц (3 августа 2006 г.). «Все наши N-граммы принадлежат Тебе» .
- ^ Глубокое правописание
- ^ Алгоритмы и методы проверки орфографии