Є хороша стаття Пітера Норвіга, в якій він розповідає як написати спелчекер в 20 рядків коду. У цій статті він показує, як пошукові системи можуть виправляти помилки у запитах. І робить це досить елегантно. Однак, у його підходу є два серйозних недоліки. По-перше, виправлення більше трьох помилок вимагає великих ресурсів. А гугл, до речі, непогано справляється і з чотирма помилками. По-друге, немає можливості перевірки зв'язкового тексту.
Отже, хочеться виправити ці проблеми. А саме, написати коректор коротких фраз або запитів, який:
- вмів би виявляти три (і більше) помилки в запиті;
- вмів би перевіряти «розірвані» або «злиплися» фрази, наприклад expertsexchange - experts_exchange, ma na ger - manager
- не вимагав багато коду для реалізації
- міг би добудовуватися до виправлення помилок іншими мовами та іншими типами «» помилок
Решта - під катом.
Як визначити помилку
Для початку вирішимо проблему пошуку помилки в одному слові. Припустимо, у нас є словник і є слово для перевірки. Ми можемо піти шляхом, про який писав Норвіг:
- повірити слово у словнику
- якщо ні, створити однобуквені помилки і перевірити у словнику
- якщо знову невдача, згенерувати двобуквені помилки, і знову за словником
Під генерацією помилок тут розуміється досить проста річ. Для перевірки слова створюється набір слів, які отримуються застосуванням 4-х операцій: видалення, вставлення, заміна і перестановка. Наприклад, помилки заміни'a'на'о'в слові'ашибка'дадуть такі слова: помилка, ааїбка, ашабка, ашиаку, ашибаа, ашибка. Ясно, що таке проробляється для всіх букв алфавіту. Подібним чином створюються варіанти слів для вставки, видалення і перестановки.
У цьому підході є один мінус. Якщо порахувати, то для англійської абетки і слова довжиною 5 символів ми отримаємо близько 400 варіантів однієї помилки. Для двох помилок - 160 000. Для трьох помилок - більше шести мільйонів. І навіть якщо перевірка за словником відбувається за костянтний час, таку кількість варіантів занадто довго генерувати. Та й пам'яті це від'їсть пристойно.
Ми можемо піти іншим шляхом: порівняти слово з кожним словом зі словника, використовуючи якусь міру подібності. Тут нам допоможе відстань Левенштейна. Якщо коротко, відстань Лівенштейна - це мінімальна кількість операцій редагування, які потрібно застосувати до першого рядка щоб отримати другий. У класичному варіанті розглядаються три операції: вставлення, вилучення і заміна. Наприклад, щоб з слова «cat» отримати «cafe» нам необхідні дві операції: заміна (t- > f) і одна вставка (- > e).
cat
cafe
Але і тут є підступ. Відстань Левенштейна вважається за час O (n * m), де n, m - довжини відповідних рядків. Таким чином, порахувати відстань Левенштейна влоб не представляється можливим. Однак, з цим можна працювати, перетворивши словник на кінцевий автомат.
Кінцеві автомати
Так, так, ті самі. А потрібні вони для того, щоб представити словник у вигляді єдиної структури. Ця структура дуже схожа на trie, лише з невеликими відмінностями. Отже, кінцевий автомат - якийсь логічний пристрій, який отримує на вхід рядок і допускає або відкидає його. Можна записати все це формально, але я спробую обійтися без цього, щоб вид формул нікого не приспав.
На зображенні показано автомат, який приймає на вхід будь-яку кінцеву послідовність символів, але допускає тільки два слова: 'cat' и 'horse'. Такий автомат називається акцептором. Нескладно доповнити цю конструкцію ще кількома тисячами слів, і в результаті вийде повноцінний словник. Варто зазначити, що цю конструкцію можна мінімізувати, в результаті чого вона може зберігати сотні тисяч слів. Якщо зберігати умову детермінованості (з будь-якого стану виходять дуги, що не мають однакових міток), то пошук буде проводиться за лінійний час. І це добре.
Але простого акцептора тут недостатньо. Потрібно ввести трохи більше хитромудру конструкцію, звану кінцевим перетворювачем (finite state transducer), або трансдьюсером. Від акцептора він відрізняється тим, що кожна дуга має два символи: вхідний і вихідний. Це дозволяє не тільки «допускати» або «відкидати» рядки, але також перетворювати вхідний рядок.
Ось приклад перетворення рядка «cat» на рядок «fox».
Композиція автоматів
Перетворювач - це математичний об'єкт. Як безліч, або краще сказати, як формальний вираз. Як і формальний вираз, трансдьюсер задає певну мову, тобто набір рядків. Також, трансдьюсери можна перетинати, об'єднувати, інвертувати і т. п. Але на відміну від регулярного виразу у нього є дуже корисна операція, звана композицією.
Якщо описати неформально, суть операції полягає в наступному. Ми проходимо одночасно по першому і другому трансдьюсеру, при цьому символи на виході першого «згодовуємо» на вхід другого. Якщо знайшовся успішний шлях як у першому, так і в другому трансдьюсері, ми фіксуємо його в новому результуючому трансдьюсері.
Треба сказати, це дуже неформальне пояснення. Однак формалізація призведе до необхідності викочувати цілий пласт теорії, а це не входило в мої плани. За формальними викладками можна звернутися на вікіпедію. Сувору формалізацію дає Меріар Морі (Mehryar Mohri). Він пише дуже цікаві статті на цю тему, хоча і непрості для читання.
Відстань Левенштейна через композицію
Час перейти до пояснення, як все ж це допоможе при обчисленні відстані Левенштейна. Тут слід зазначити, що у трансдьюсері можуть брати участь спеціальні символи, які позначають порожній рядок (порожній символ, позначимо його'eps'). Це і дозволить нам використовувати їх як операції редагування. Все що нам потрібно - провести композицію трьох трансдьюсерів:
- трансдьюсер, який представляє перше слово
- трансдьюсер, що представляє модель помилок
- трансдьюсер, який представляє друге слово
Перші два трансдьюсери представляють вхідні рядки (см малюнки). Вони допускають слова cat і bath.
Модель помилок являє собою стан з рефлексивними (замкнутими на себе) переходами. Всі вони, за винятком переходу a:a, які представляють дії редагування:
- a:a - залишаємо символ без зміни
- a:b - заміна символу; тут'a'на'b '
- eps:a - вставлення символу
- a:eps - вилучення символу
Щоб не замикати картинку, на ній показано корекції тільки для двох літер. Тут потрібно зазначити, що кожен перехід маркований числом. Це позначення ваги корекції. Тобто. для операцій вставки, заміни, видалення вага дорівнює 1. Тоді як для переходу типу a:a, який просто транслює початковий символ без корекції, вага дорівнює 0. В результаті, підсумкова композиція прийме наступний вигляд.
І ось результат: сума терезів уздовж найкоротшого шляху і буде відстанню Левенштейна. У даному прикладі таким шляхом є: 0 — 1 — 4 — 10 — 17. Сума терезів уздовж цього шляху дорівнює 2. А тепер простежимо за мітками вздовж цього шляху: c:b a:a t:t eps:h. Це є ні що інше, як операції редагування. Тобто. щоб отримати слово bath з слова cat нам необхідно замінити першу букву і додати'h'останньої.
Отже, ми можемо обчислити відстань Левенштейна між двома трансдьюсерами. Але це означає, що ми можемо обчислити цю відстань між рядком і словником. Це і дозволить обчислити найбільш близьке слово в словнику і дасть правильний варіант виправлення.
Мовна модель
Як виправляти помилки в окремих словах вже зрозуміло. Але як виправити помилку, коли два слова злиплися. Наприклад, якщо замість Pen Island хтось написав penisland. Більш того, потрібно розділити ці слова правильно, щоб не травмувати ніжну психіку користувача. До речі, і яндекс і рамблер справляються із завданням добре, тоді як mail.ru рубає сплеча.
Щоб правильно змінювати або об'єднувати рядки, необхідно знати, яке словосполучення найбільш імовірне. У статистичній лінгвістиці для цього використовуються так звані моделі мови, які будуються зазвичай на основі ngram'ної моделі (або байєсовської мережі). Тут я не буду докладно пояснювати що це таке. Читач може глянути в мій попередній пост, де така модель створюється для простого генератора тексту.
Хороша новина полягає в тому, що ця модель може бути представлена у вигляді трансдьсера. Більш того, є готові бібліотеки, які дозволяють розрахувати модель по заданому корпусу. Основна ідея полягає в підрахунку пар, трійок, або n-послідовностей слів, переходу від частот до ймовірностей, і побудові автомата. Цей автомат робить просту річ - він оцінює ймовірність послідовності слів на вході. Де ймовірність більша, ту послідовність і використовуємо.
На малюнку - модель мови для декількох слів. Картинка здається дещо заплутаною, але алгоритм її побудови нескладний. Тим не менш, мовна модель - це тема, що вимагає окремої статті. У найближчому майбутньому сподіваюся її написати.
Вага переходів у моделі мови - не що інше як ймовірність зустріти наступне слово. Однак, для числової стабільності вона представлена негативним логарифмом. Таким чином ваги перетворюються на деякий штраф, і чим штраф менший, тим найбільш імовірний даний рядок.
Збираємо всі разом
У нас є все що потрібно для побудови спелчекера. Все що потрібно зробити - провести композицію чотирьох трансдьюсерів:
R = S o E o L o M
- S - початковий рядок
- E - модель помилок
- L - лексикон
- M - модель мови
і знайти найкоротший шлях у результуючому трансдьюсері R. Шлях, що представляє набір слів і буде шуканим варіантом виправлення.
Тут є пара моментів, які потребують пояснення. По-перше - перетворювач L. Це досить тривіальний трансдьюсер, який «склеює» слово з букв для передачі в модель вже цілого слова. Таким чином він допомагає перейти від літер і символів моделі помилок до слів у моделі мови. Другий момент полягає у вагах перетворювачів. Щоб зробити коректну композицію, необхідно, щоб ваги всіх перетворювачів мали один сенс. Вихідний рядок і лексикон не мають вагів, модель мови представляє ймовірності, але ось модель помилок дає Левенштейна. Нам необхідно перейти від цієї оцінки до ймовірностей. Цей процес близький до шаманізму, але тим не менш можливо підібрати такі ваги, які найбільш підходять до реальних помилок.
Це, мабуть і все. Ви можете справедливо запитати, а де ж код? А його немає. Все робиться за допомогою операцій над перетворювачами. А ці операції вже реалізовані в бібліотеках. Наприклад, у цій: openfst.org. Все що потрібно - побудувати вихідні об'єкти.
Висновки, pro et contra
Я вважаю даний підхід дуже цікавим. Він володіє низкою сильних сторін. Першою сильною стороною є те, що ми не пишемо код, а просто оперуємо математичними об'єктами. Це спрощує розробку інструментів роботи з текстом і дуже сильно економить час.
Іншою сильною стороною є його універсальність. Не потрібно писати різні алгоритми для операцій з рядками. Наприклад, якщо потрібно визначити помилки неправильної розкладки вигляду «fkujhbnv» - > «алгоритм», то для цього не потрібно писати нову програму. Досить трохи модифікувати модель помилок: додати переходи, марковані літерами двох мов і пару станів.
Однак, є і негативні сторони. Досить не тривіально домогтися стабільної і швидкої швидкості. У мене не вийшло. Швидкість роботи сильно залежить від структури перетворювачів, кількості переходів, заходи недетермінованості. Крім того, деякі операції над перетворювачами вимагають великих обсягів пам'яті. Але всі ці питання так чи інакше вирішувані.
Сподіваюся, стаття була корисною. Ставте питання, якщо щось незрозуміло. Охоче відповім.