рських помилок.
Алгоритми, використовувані опечаточнікамі
У багатьох опечаточніках модель помилок найчастіше, грунтується на понятті відстані, введеним Левенштейн, і використовує функцію обчислення відстані між рядками на основі алгоритму Вагнера і Фішера.
Алгоритм нечіткого пошуку
Алгоритми нечіткого пошуку є основою систем перевірки орфографії і повноцінних пошукових систем ніби Google або Yandex. Наприклад, такі алгоритми використовуються для функцій на кшталт В«Можливо ви мали на увазі ...В» у тих же пошукових системах. p align="justify"> Задачу нечіткого пошуку можна сформулювати так:
В«По заданому слову знайти в тексті або словнику розміру n всі слова, що збігаються з цим словом (або починаються з цього слова) з урахуванням k можливих відмінностейВ».
Наприклад, при запиті В«МашинаВ» з урахуванням двох можливих помилок, знайти слова В«МашинкаВ», В«МахінаВ», В«МалинаВ», В«КалинаВ» і так далі.
Алгоритми нечіткого пошуку характеризуються метрикою - функцією відстані між двома словами, що дозволяє оцінити ступінь їх подібності в даному контексті. Суворе математичне визначення метрики включає в себе необхідність відповідності умові нерівності трикутника (X - безліч слів, p - метрика)
В
У числі найбільш відомих метрик - Левенштейна і Дамерау-Левенштейна.
Відстань Левенштейна
Відстань Левенштейна (також редакційне відстань або дистанція редагування) між двома рядками в теорії інформації та комп'ютерної лінгвістики - це мінімальна кількість операцій вставки одного символа , видалення одного символу і заміни одного символу на інший, необхідних для перетворення одного рядка в іншу.
Застосування
Відстань Левенштейна і його узагальнення активно застосовується:
В· для виправлення помилок у слові (в пошукових системах, базах даних, при введенні тексту, при автоматичному розпізнаванні відскановану тексту або мови).
В· для порівняння текстових файлів утилітою diff і їй подібними. Тут роль В«символівВ» грають рядки, а роль В«рядківВ» - файли.
В· в біоінформатики для порівняння генів, хромосом і білків.
Редакційним приписом називається послідовність дій, необхідних для отримання з першого рядка другий найкоротшим чином. Зазвичай дії позначаються так: D (англ. delete) - видалити, I (англ. insert) - вставити, R (replace) - замінити, M (match) - збіг.
Наприклад, для 2-х...
