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