Применение и модификация алгоритма Вагнера — Фишера нахождения расстояния Левенштейна в проблеме распознавания фраз | Статья в журнале «Молодой ученый»

Авторы: ,

Рубрика: Информатика

Опубликовано в Молодой учёный №9 (113) май-1 2016 г.

Дата публикации: 27.04.2016

Статья просмотрена: 141 раз

Библиографическое описание:

Антипов М. Ю., Казначеев А. А. Применение и модификация алгоритма Вагнера — Фишера нахождения расстояния Левенштейна в проблеме распознавания фраз // Молодой ученый. — 2016. — №9. — С. 47-50. — URL https://moluch.ru/archive/113/29189/ (дата обращения: 23.09.2018).



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

Для решения поставленной задачи требуется ввести какую-либо меру (метрику), которая будет оценивать ошибку. «В числе наиболее известных метрик — расстояния Хемминга, Левенштейна и Дамерау —Левенштейна» [2]. «Наиболее часто применяемой метрикой является расстояние Левенштейна» [2]. Эта метрика универсальна и не содержит избыточных по отношению к решаемой задаче операций. Обычно эта метрика находится с помощью алгоритма Вагнера — Фишера.

Таким образом, целью данной работы была реализация алгоритма сопоставления на основе алгоритма Вагнера — Фишера нахождения расстояния Левенштейна для улучшения распознавания слов, фраз, предложений английского языка. Задача заключалась в выборке из списка фраз наиболее похожую на произнесенную пользователем. Список фраз заранее содержится в приложении. Процент ошибки должен быть не более 30 % процентов.

В процессе работы решались следующие задачи:

– изучение материалов по данной теме;

– применение алгоритма поиска расстояния Левенштейна;

– модификация алгоритма для решения поставленной задачи;

– сравнение и анализ полученных результатов.

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

В связи с тем, что приложение ориентировано на рынок мобильных устройств и Android OS имеет стандартные средства распознавания голоса, то в качестве языка программирования выступал Java. Входные данные алгоритма — это текстовое сообщение, распознанное стандартными средствами операционной системы. Выходные данные — это список слов наиболее похожих на произнесенное сообщение.

Алгоритм Вагнера — Фишера находит метрику Левенштейна, которая позволяет оценить «минимальное количество правок одной строки (под правками подразумеваются три возможные операции: стирание символа, замена символа и вставка символа), чтобы превратить ее во вторую» [1], при этом, где — вес операции. Используя этот алгоритм, опытным путем было получено значение , вероятность ошибки, то есть получения на выходе неправильного результата. Для достижения поставленных целей, предположим, как можно модифицировать метрику:

I. Замена морфем на фонемы. В английском языке имеется большое количество сочетаний букв, которые схожи по звучанию между собой. Например, th → z, oo → u, kn → n, er → e и т. д. Сделав подобные преобразования, будем работать уже не с самим словом, а с его «транскрипцией». То есть moon уже будет рассматриваться как mun, а mother как moze.

II. Перераспределение веса в зависимости от типа буквы (гласная или согласные), при этом омонимичные согласные имеют меньший вес. «Согласные звуки — это своеобразный каркас слов, определяющий основу слова» [3], а гласные нужны для их соединения, поэтому ошибка в согласной букве будет стоить больше, чем в гласной. Также существуют омонимичные согласные (похожие по звучанию: b → p, d → t и т. д.), в этом случае ошибка должна стоить меньше. Например, между словами bat и bad ошибка будет стоить меньше, чем в словах bat и bar, потому что b и d — омонимичны.

III. Корректировка веса ошибки по длине слова и её позиции. Если в коротком слове (3–4 буквы), будет совершена ошибка хотя бы в одной букве, то слово может трактоваться неправильно. Но если совершить ошибку в достаточно длинном слове (6–8) букв, то вряд ли ошибка будет критичной. Очевидно, что позиция тоже имеет значение: ошибка в начале слова должна иметь вес больше, чем в конце. Например, возьмём слово imporhant. Наверняка, многие увидели ошибку: вместо h должна быть буква t. сравним это со случаем: swim — slim.

IV. Введение штрафа за разное количество слов. Нередко сравниваемые словосочетания отличаются по количеству слов. В данных ситуациях сравнение производится следующим образом: фразы делятся на слова и первое слово сравнивается с первым, получаем , второе со вторым и т. д; Конечный вес получается , где T — штраф за различные длины сравниваемых фраз, а n — количество слов. Отметим, что артикли не рассматриваются.

Для оценки предложенных модификаций была создана выборка из возможных произношений английских фраз. Для модификации II проведем дополнительное исследование, для нахождения веса гласных относительно веса согласных:

Рис. 1. Вероятность ошибки от веса гласной

Как видно из графика, оптимальный вес равен 30 % от стоимости согласной. Проведем сравнительное исследование распознавания слов, «Л» — означает процент ошибки метрики Левенштейна, римские цифры обозначают соответствующие модификации:

Рис. 2. Вероятность ошибки каждой из модификаций

Так как модификация метрики под номером II показала самые лучшие результаты, то попробуем на её основе применить другие модификации:

Рис. 3. Вероятность ошибки каждой из модификаций

В итоге, был реализован алгоритм сопоставления на основе алгоритма Вагнера — Фишера нахождения расстояния Левенштейна для улучшения распознавания слов, фраз, предложений английского языка. Решение основано на модификации под номером II (перераспределение весов в зависимости от типа буквы), так как является самым эффективным.

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

Литература:

  1. Алгоритмы, Паттерны, Bestpractices, Justforfun [Электронный ресурс]. — Расстояние Левенштейна — определяем «похожесть» строк — URL: http://muzhig.ru/levenstein-distance-python/ (дата обращения 13.01.2016);
  2. Интересные публикации / Хабрахабр [Электронный ресурс]. — Нечеткий поиск в тексте и словаре — URL: http://habrahabr.ru/post/114997/ (дата обращения 14.01.2016);
  3. Самоучитель английского языка [Электронный ресурс]. — Согласные звуки английского языка — URL: http://samouchitel-angliyskogo.blogspot.ru/2014/01/soglasnyye-zvuki-angliyskogo-yazyka.html (дата обращения 21.01.2016);
Основные термины (генерируются автоматически): английский язык, вероятность ошибки, ошибка, слово, алгоритм сопоставления, нахождение расстояния, III, список фраз, тип буквы, основа алгоритма.


Похожие статьи

Программная реализация алгоритма Левенштейна для...

Ключевые слова. Сравнение строк; база данных; редакционное расстояние; расстояние Левенштейна; дистанция редактирования; алгоритм

4. Для исправления ошибок в результате автоматического распознавания отсканированного текста или записей речи.

Анализ методов тематического моделирования текстов на...

Основной алгоритм данного метода можно разделить на четыре шага: предобработку, нахождение

Анализ фразеологизмов английского языка с компонентами – зоонимами (кот, кошка)

Эталонные списки и метод сопоставления с образцом для организации диалога на...

Обзор некоторых алгоритмов нестрогого сопоставления записей...

В работе рассматриваются некоторые алгоритмы нестрого сопоставления строк как ключевой части алгоритмов нестрогого сопоставления записей баз данных, содержащих

Порядок букв в слове абсолютно никакого значения не имеет. Хеш. Список слов.

Использование алгоритмов нечеткого поиска при решении задачи...

Предложен алгоритм вычисления функции релевантности на основании метода N-gram. Ключевые слова.

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

Эталонные списки и метод сопоставления с образцом для...

Список — один из наиболее важных и часто используемых типов данных, которые поддерживает Пролог.

Анализ методов тематического моделирования текстов на естественном языке. Обзор некоторых алгоритмов нестрогого сопоставления записей...

Реализация алгоритма Metaphone для кириллических фамилий...

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

Сам алгоритм описан ниже. 1. Все буквы в слове сделать заглавными.

Анализ поисковых алгоритмов при решении задач идентификации...

Ключевые слова. База данных; расстояние Хемминга; сравнение строк; расстояние

· Орфографические ошибки (опечатки) – ошибки, возникающие при вводе информации.

Алгоритм нечеткого поиска позволяет быстро отобрать все слова, фрагменты которых...

Алгоритмы распознавания объектов | Статья в сборнике...

Основное свойство, которым должен обладать простой классификатор — вероятность ошибки должна быть меньше .

В основе алгоритма Хафа лежит метод обнаружения линий на изображении.

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Программная реализация алгоритма Левенштейна для...

Ключевые слова. Сравнение строк; база данных; редакционное расстояние; расстояние Левенштейна; дистанция редактирования; алгоритм

4. Для исправления ошибок в результате автоматического распознавания отсканированного текста или записей речи.

Анализ методов тематического моделирования текстов на...

Основной алгоритм данного метода можно разделить на четыре шага: предобработку, нахождение

Анализ фразеологизмов английского языка с компонентами – зоонимами (кот, кошка)

Эталонные списки и метод сопоставления с образцом для организации диалога на...

Обзор некоторых алгоритмов нестрогого сопоставления записей...

В работе рассматриваются некоторые алгоритмы нестрого сопоставления строк как ключевой части алгоритмов нестрогого сопоставления записей баз данных, содержащих

Порядок букв в слове абсолютно никакого значения не имеет. Хеш. Список слов.

Использование алгоритмов нечеткого поиска при решении задачи...

Предложен алгоритм вычисления функции релевантности на основании метода N-gram. Ключевые слова.

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

Эталонные списки и метод сопоставления с образцом для...

Список — один из наиболее важных и часто используемых типов данных, которые поддерживает Пролог.

Анализ методов тематического моделирования текстов на естественном языке. Обзор некоторых алгоритмов нестрогого сопоставления записей...

Реализация алгоритма Metaphone для кириллических фамилий...

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

Сам алгоритм описан ниже. 1. Все буквы в слове сделать заглавными.

Анализ поисковых алгоритмов при решении задач идентификации...

Ключевые слова. База данных; расстояние Хемминга; сравнение строк; расстояние

· Орфографические ошибки (опечатки) – ошибки, возникающие при вводе информации.

Алгоритм нечеткого поиска позволяет быстро отобрать все слова, фрагменты которых...

Алгоритмы распознавания объектов | Статья в сборнике...

Основное свойство, которым должен обладать простой классификатор — вероятность ошибки должна быть меньше .

В основе алгоритма Хафа лежит метод обнаружения линий на изображении.

Задать вопрос