ИСПРАВЛЕНИЕ ОПЕЧАТОК И ОШИБОК В СЛОВАХ С ПОМОЩЬЮ НЕЧЕТКОГО ПОИСКА

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

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

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

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

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

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

При словарном методе все входящие в текст словоформы проверяются по компьютерному словарю. Если словарь такую форму допускает, она считается правильной, а иначе либо сразу признаётся ошибочной, либо предъявляется человеку. В настоящее время первые два метода практически не используются, т.к. уже есть хорошие компьютерные словари, достаточно большие по объёму и с эффективным доступом [1].

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

Алгоритмы нечеткого поиска строк в словаре являются основой для построения современных систем проверки орфографии, которые используются в текстовых редакторах, системах оптического распознавания символов и поисковых системах, вроде Google или Yandex. Например, такие алгоритмы используются для функций, которые выдают пользователю сообщение «возможно вы имели в виду…» в поисковых системах, то есть поиск должен учитывать возможные ошибки и опечатки пользователей при вводе запросов.

Задачу нечеткого поиска текстовой информации можно сформулировать так: «Есть текстовая информация определенного размера. Пользователь вводит слово или фразу для поиска. Необходимо найти в тексте все совпадения с заданным словом с учетом возможных допустимых различий». Количество и виды различий могут изменяться и задаются заранее. Это может быть пропущенный символ, добавленный символ, измененный символ. Например, при запросе «Точка» с учетом двух возможных ошибок, найти слова «Тоска», «Дочка», «Кочка», «Точилка» и так далее [2].

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

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

Для начала опишем принцип работы расстояния Левенштейна. Создадим матрицу D, содержащую столько же столбцов, сколько символов в первой строке, и столько же строк, сколько символов во второй строке. Пусть: : science, а : distance.   − редакционное расстояние.

Заполним элементы матрицы D. Самым очевидным фактом, является то, что  = 0, так как пустые строки итак полностью совпадают.  = i и  = j, так как любая строка может получиться из пустой, добавлением нужного количества символов. В общем случае немного сложнее, так как приходится выбирать что выгоднее: добавить символ, удалить или заменить .

На каждом шаге ищем минимальное из трёх значений:

• если минимально , добавляем удаление символа из [i] и идём в ;
• если минимально , добавляем вставку символа в [i] и идём в ;
• если минимально , иначе ,  после чего идём в  и добавляем замену, если .

Обобщим всё вышесказанное в общую формулу (1):

                   (1)

На рисунке 1 изображена конечная матрица D с рассчитанными элементами, согласно формуле (1).

Рисунок 1. Изображение конечного вида матрицы D

Здесь шаг по j символизирует удаление (D) из первой строки, по i — вставку (I) в первую строку, а шаг по обоим индексам символизирует замену символа (R) или отсутствие изменений (M). С помощью данных операций преобразуем первую строку во вторую. Для этого, осуществляется проход по матрице в обратном направлении, начиная с правой нижней клетки до верхней левой, по минимальным элементам. Так, отслеживаются операции для преобразования первой строки во вторую [4].

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

Приведем реализацию вычисления расстояния Левенштейна на языке программирования C#:

public static int LevenshteinDistance(string s1, string s2)

        {

            int D;

            int[,] m = new int[s1.Length + 1, s2.Length + 1];

            for (int i = 0; i <= s1.Length; i++)

            { m[i, 0] = i; }

            for (int j = 0; j <= s2.Length; j++)

            { m[0, j] = j; }

            for (int i = 1; i <= s1.Length; i++)

            {

                for (int j = 1; j <= s2.Length; j++)

                {

                    D = (s1[i - 1] == s2[j - 1]) ? 0 : 1;

                     m[i, j] = Math.Min(Math.Min(m[i - 1, j] + 1,

                                                                      m[i, j - 1] + 1),

                                                                      m[i - 1, j - 1] + D);

                }

            }

            return m[s1.Length, s2.Length];

      }

Однако по результатам тестирования данного алгоритма можно сделать вывод, что может случиться так, что расстояния между совершенно разными короткими словами оказываются небольшими, в то время как расстояния между очень похожими длинными словами оказываются значительными. Например, у слов «поиск» − «холст» и у слов «информативный» − «информационный» расстояние будет равно 3.

Ученый Фредерик Дамерау показал, что 80 % ошибок при наборе текста человеком являются транспозициями. Поэтому существует модификация расстояния Левенштейна, которая называется расстояние Дамерау-Левенштейна. К операциям вставки, удаления и замены символов, определенных в расстоянии Левенштейна, добавлена операция транспозиции (перестановки) символов. Именно эти две метрики наиболее часто применяется на практике [5].

Было разработано приложение на языке C# с использованием Windows Forms [6].

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

Автомат Левенштейна используется для исправления орфографических ошибок, находя слова в словаре, которые близки к слову с ошибкой. После написания данного слова, автомат Левенштейна будет построен, а затем применен ко всем словам в словаре, чтобы определить, какие из них наиболее близки к слову с ошибкой [7].

На рисунке 2 приведены результаты выполнения приложения. Для начала проведено тестирование для слова с одной орфографической ошибкой, затем с двумя и после с тремя ошибками. Как видим из рисунка, все слова были исправлены верно. Но нужно добавить, что если же слово является какой-либо формой искомого слова, но отсутствует в словаре (особенно это касается неологизмов и сленга), то не всегда возможно его корректно распознать [8].

Рисунок 2. Результаты выполнения приложения

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

Список литературы:

1. Исправление ошибок в русскоязычных текстах [Электронный ресурс]. — Режим доступа: http://www.plam.ru/compinet/prikladnoe_programmnoe_obespechenie_sistemy_avtomaticheskoi_obrabotki_tekstov/p3.php (дата обращения: 6.10.19)
2. Мосалев П.М. Обзор методов нечеткого поиска текстовой информации // Вестник Московского государственного университета печати, 2013. — С. 87-91.
3. Конечный автомат [Электронный ресурс]. — Режим доступа: https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82 (дата обращения 6.10. 19)
4. Расстояние Левенштейна [Электронный ресурс]. — Режим доступа: https://ru.wikipedia.org/wiki/Расстояние_Левенштейна (дата обращения 6.10.19)
5. Damerau–Levenshtein distance [Электронный ресурс]. — Режим доступа: https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance (дата обращения: 6.10.19)
6. Windows Forms [Электронный ресурс]. — Режим доступа: https://ru.wikipedia.org/wiki/Windows_Forms (дата обращения 6.10.19)
7. Levenshtein automaton [Электронный ресурс]. — Режим доступа: https://en.m.wikipedia.org/wiki/Levenshtein_automaton (дата обращения: 6.10.19)
8. Алгоритм нечеткого текстового поиска [Электронный ресурс]. — Режим доступа: https://cyberleninka.ru/article/n/algoritm-nechetkogo-tekstovogo-poiska-v-virtualnyh-sotsialnyh-setyah (дата обращения: 6.10.19)