Введение
Функция проверки орфографии присутствует во многих компьютерных программах. Подбор орфографических вариантов – это функция, используемая во многих компьютерных программах для предложения вероятных замен слов, которые, возможно, были написаны с ошибкой. Функции подбора орфографических вариантов обычно включаются в интернет-поисковые системы, текстовые редакторы, программы проверки орфографии, системы медицинской транскрипции, автоматическую переформулировку запросов и отчетность по статистике частоты использования слов.
Spelling suggestion is a feature of many computer software applications used to suggest plausible replacements for words that are likely to have been misspelled. Spelling suggestion features are commonly included in Internet search engines, word processors, spell checkers, medical transcription, automatic query reformulation, and frequency log statistics reporting.
Алгоритмы
Любой проверяющий орфографию должен обладать определенным объемом данных о словах целевого языка, как в общем употреблении, так и со специализированными знаниями (например, медицинская терминология). Эти данные могут поступать из: словаря всех известных слов; текстового корпуса, содержащего типичный текст, признанный правильно написанным; списка часто встречающихся опечаток с сопоставлением ошибок и исправлений; журналов ввода текста пользователями, например, из популярной поисковой системы. По сути, это коллективный корпус, однако предполагается наличие в нем орфографических ошибок. Также могут учитываться данные о том, когда пользователи выбирают предложенные исправления или выполняют повторный, очень похожий запрос, что создает коллективную карту опечаток и надежных исправлений. Список часто встречающихся опечаток, возможно, включающий многословные фразы, можно использовать для проверки наличия входных слов или фраз в этом списке. Для использования словаря без предварительного сопоставления опечаток и исправлений обычно рассчитывается расстояние редактирования между входным словом и каждым словом в словаре. Метрика расстояния Левенштейна рассматривает "редактирование" как вставку, удаление или замену одной буквы. Расстояние Дамерау — Левенштейна добавляет транспозиции (перестановку соседних букв). Слова, находящиеся на расстоянии редактирования 1 от входного слова, считаются наиболее вероятными исправлениями, расстояние редактирования 2 — менее вероятными, а расстояние редактирования 3 иногда включается в предложения, а иногда игнорируется. Текстовый корпус можно представить как словарь известных слов с указанием частоты появления каждого слова. Это можно использовать для сортировки предложений по исправлению. Например, если есть несколько предложений с расстоянием редактирования 1, то слова, которые чаще всего встречаются в корпусе, с наибольшей вероятностью являются желаемым исправлением. Поскольку словарь известных слов очень велик, вычисление расстояния редактирования между входным словом и каждым словом в словаре требует значительных вычислительных ресурсов и, следовательно, является относительно медленным. Для ускорения поиска в хранилище можно использовать различные структуры данных, такие как BK-деревья. Более быстрый подход, предложенный Питером Норвигом, заключается в генерации всех возможных перестановок входного слова с учетом всех возможных редактирований. Для слова длиной n и алфавита размером a, при расстоянии редактирования 1 существует не более n удалений, n-1 транспозиций, a*n замен и a*(n+1) вставок. Используя только 26 букв английского алфавита, это приведет к 54*n+25 обращениям к словарю, за вычетом дубликатов (зависящих от конкретных букв в слове). Это относительно небольшое число по сравнению со словарем, содержащим сотни тысяч слов. Однако для расстояния редактирования 2 и более могут потребоваться десятки или сотни тысяч обращений. Еще одним нововведением, предложенным Вольфом Гарбе, является SymSpell.
A dictionary of all known words. A text corpus which includes typical text, known to be correctly spelled. A list of frequently misspelled words, mapping errors to corrections. Logs of human text input, such as from a popular search engine. This is essentially a crowdsourced corpus, but it is assumed there will be some spelling mistakes. Data might be included about when people click on a spelling suggestion or make a second, very similar query; this creates a crowdsourced mapping of misspelled words to reliable corrections. A list of frequently misspelled words, possibly including multi word phrases, can simply be consulted to see if any of the input words or phrases are listed. To make use of a dictionary without a pre existing mapping from misspellings to corrections, the typical technique is to calculate the edit distance between an input word and any given word in the dictionary. The Levenshtein distance metric considers an "edit" to be the insertion, deletion, or substitution (with another letter) of one letter. The Damerau–Levenshtein distance adds transpositions (the swapping of neighboring letters). Dictionary words that are an edit distance of 1 away from the input word are considered highly likely as corrections, edit distance 2 less likely, and edit distance 3 sometimes included in suggestions and sometimes ignored. A text corpus can be summed up as a dictionary of known words, with a frequency of appearance for each word. This can be used to sort the spelling suggestions. For example, if there are multiple suggestions of edit distance 1, the words that appear most frequently in the corpus are most likely to be the desired correction. Because a dictionary of known words is very large, calculating the edit distance between an input word and every word in the dictionary is computationally intensive and thus relatively slow. Various data structures can be utilized to speed up storage lookups, such as BK trees. A faster approach adopted by Peter Norvig generates all the permutations from an input word of all possible edits. For a word of length n and an alphabet of size a, for edit distance 1 there are at most n deletions, n 1 transpositions, a*n alterations, and a*(n+1) insertions. Using only the 26 letters in the English alphabet, this would produce only 54*n+25 dictionary lookups, minus any duplicates (which depends on the specific letters in the word). This is relatively small when compared to a dictionary of hundreds of thousands of words. However, tens or hundreds of thousands of lookups might be required for edit distance 2 and greater. A further innovation adopted by Wolf Garbe, known as SymSpell
Другие исследователи экспериментировали с использованием больших объемов данных и методов глубокого обучения (разновидность машинного обучения) для обучения нейронных сетей выполнению коррекции орфографических ошибок.