Застосування та модифікація алгоритму Вагнера
Бібліографічний опис:
У світі взаємодія між людиною і машиною є буденністю. Завдяки технічному прогресу воно не обмежується простим натисканням клавіш та виведенням інформації на екран. Користувач взаємодіє з пристроями різними способами: за допомогою сенсорів, жестів та голосових команд. Сьогодні всі ці можливості активно використовуються у повсякденному житті, наприклад існують додатки вивчення іноземних мов. Під час розробки подібного додатка для мобільних пристроїв з'явилася ідея перевіряти вимову користувача. Розпізнавання голосу здійснює стандартна служба, що входить до пакету операційної системи Android, після її роботи на виході отримуємо голосове повідомлення у вигляді текстової інформації. Не завжди отримане текстове повідомлення відповідає сказаному, що заважає порівняти його з наявним заздалегідь списком. Отже, необхідно реалізувати алгоритм зіставлення сказаного повідомлення з наперед відомим списком фраз.
Для вирішення поставленого завдання потрібно ввести будь-яку міру (метрику), яка оцінюватиме помилку. «У числі найбільш відомих метрик - відстані Хеммінга, Левенштейна та Дамерау-Левенштейна» [2]. «Найчастіше застосовуваною метрикою є відстань Левенштейна» [2]. Ця метрика універсальна і не містить надлишкових по відношенню до розв'язуваної задачі операцій. Зазвичай ця метрика перебуває з допомогою алгоритму Вагнера - Фішера.
Таким чином, метою даної роботи була реалізація алгоритму зіставлення на основі алгоритму Вагнера - Фішера знаходження відстані Левенштейна для покращення розпізнавання слів,фраз, речень англійської мови. Завдання полягало у вибірці зі списку фраз найбільш схожу на сказану користувачем. Список фраз заздалегідь міститься у додатку. Відсоток помилки має бути не більше 30%.
У процесі роботи вирішувалися такі:
– вивчення матеріалів з цієї теми;
- Застосування алгоритму пошуку відстані Левенштейна;
– модифікація алгоритму на вирішення поставленої задачи;
– порівняння та аналіз отриманих результатів.
Практична значущість роботи полягає в тому, що модифікований алгоритм може вбудовуватись у безліч програм, де потрібно збільшити ефективність розпізнавання, а також, за прямим призначенням — завдання розпізнавання слів, фраз у додатку з вивчення англійської мови.
У зв'язку з тим, що додаток орієнтований на ринок мобільних пристроїв і Android OS має стандартні засоби розпізнавання голосу, то мовою програмування виступав Java. Вхідні дані алгоритму - це текстове повідомлення, розпізнане стандартними засобами операційної системи. Вихідні дані — це список найбільш схожих на сказане повідомлення.
Алгоритм Вагнера — Фішера знаходить метрику Левенштейна, яка дозволяє оцінити «мінімальну кількість правок одного рядка (під правками маються на увазі три можливі операції: стирання символу, заміна символу та вставка символу), щоб перетворити її на другий» [1], при цьому, де — вага операції. Використовуючи цей алгоритм, дослідним шляхом було отримано значення , ймовірність помилки, тобто отримання неправильного результату. Для досягнення поставленої мети, припустимо, як можна модифікувати метрику:
I. Заміна морфем на фонеми. В англійській мові є велика кількість поєднаньлітер, які схожі на звучання між собою. Наприклад, th → z, oo → u, kn → n, er → e і т. д. Зробивши подібні перетворення, працюватимемо вже не з самим словом, а з його транскрипцією. Тобто moon вже розглядатиметься як mun, а mother як moze.
ІІ. Перерозподіл ваги в залежності від типу літери (гласна або приголосні), при цьому омонімічні приголосні мають меншу вагу. "Згідні звуки - це своєрідний каркас слів, що визначає основу слова" [3], а голосні потрібні для їх з'єднання, тому помилка в літері буде коштувати більше, ніж у голосній. Також існують омонімічні приголосні (подібні до звучання: b → p, d → t і т. д.), у цьому випадку помилка повинна коштувати менше. Наприклад, між словами bat та bad помилка буде коштувати менше, ніж у словах bat і bar, тому що b і d – омонімічні.
ІІІ. Коригування ваги помилки по довжині слова та її позиції. Якщо в короткому слові (3-4 літери), буде зроблено помилку хоча б в одній літері, то слово може трактуватися неправильно. Але якщо припуститися помилки в досить довгому слові (6–8) літер, то навряд чи помилка буде критичною. Очевидно, що позиція теж має значення: помилка на початку слова повинна мати вагу більше, ніж наприкінці. Наприклад, візьмемо слово imporhant. Напевно, багато хто побачив помилку: замість h має бути буква t. порівняємо це з нагодою: swim - slim.
IV. Введення штрафу за різну кількість слів. Словосполучення, що нерідко порівнюються, відрізняються за кількістю слів. У даних ситуаціях порівняння проводиться так: фрази діляться на слова і перше слово порівнюється з першим, отримуємо , друге з другим і т. д; Кінцева вага виходить , де T - штраф за різні довжини фраз, що порівнюються, а n - кількість слів. Зазначимо, що артиклі не розглядаються.
Для оцінкизапропонованих модифікацій було створено вибірку з можливих вимов англійських фраз. Для модифікації II проведемо додаткове дослідження, для знаходження ваги голосних щодо ваги приголосних:
Мал. 1. Імовірність помилки від ваги голосної
Як видно з графіка, оптимальна вага дорівнює 30% від вартості згоди. Проведемо порівняльне дослідження розпізнавання слів, «Л» означає відсоток помилки метрики Левенштейна, римські цифри позначають відповідні модифікації:
Мал. 2. Імовірність помилки кожної з модифікацій
Оскільки модифікація метрики під номером II показала найкращі результати, спробуємо її основі застосувати інші модифікації:
Мал. 3. Імовірність помилки кожної з модифікацій
У результаті було реалізовано алгоритм зіставлення з урахуванням алгоритму Вагнера — Фішера знаходження відстані Левенштейна поліпшення розпізнавання слів, фраз, речень англійської. Рішення ґрунтується на модифікації під номером II (перерозподіл ваг залежно від типу літери), оскільки є найефективнішим.