Наближена відповідність рядків

У комп'ютерних науках, наближена відповідність рядків (часто вживається як нечіткий пошук рядків) — це техніка знаходження стрічок що відповідає патерну наближено (аніж точно). Проблема приблизної відповідності стрічок типово поділяється на дві під-проблеми: знаходження наближеної під-стрічки всередині певної стрічки та знаходження тих, що наближено відповідають патерну.

Загальний огляд

Наближеність збігу вимірюється кількістю примітивних операцій, необхідних для того щоб перетворити стрічку на точний збіг. Ця кількість називається редакційною відстанню між стрічкою і патерном. Зазвичай як операції розцінюються:

вставка: кіт → кріт
видалення: кріт → кіт
заміна: кит → кіт

Всі ці три операції можуть бути узагальнені як форми заміщення з додаваннями символу NULL (тут зазначеним як *), під час видалення або вставки:

вставка: к*іт → кріт
видалення: кріт → к*іт
заміна: кит → кіт

Також інколи розглядається операція транспозиція, в якій дві літери у стрічці міняються місцями, щоб бути примітивною операцією. Зміна abc → acb це транспозиція.

Різні наближені обчислювачі накладають різні обмеження. Деякі обчислювачі використовують єдину глобальну незважену вартість, тобто загальне число примітивних операцій, необхідних для перетворення збігу патерном. Наприклад, якщо патерном є coil, foil відрізняється одною заміною, oil одним видаленням та foal двома замінами. Якщо рахувати що окрема операція вартує однієї затрати, та встановити ліміт на одну затрату, то coil, foil та oil будуть валідними збігами, а foal - ні.

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

Постановка завдання та алгоритми

Одне з можливих визначень задач наближеного збігу рядків є: Маємо стрічку паттерн P = p₁p₂...p_m та текстову стрічку T = t₁t₂...t_n, необхідно знайти стрічку T_j`,j = t_j`...t_j в Т, яка з усіх підстрічок Т, має найменшу редакційну відстань до паттерна P.

Підхід грубої сили мав би очислити редакційну відстань до P для всіх підстрічок T, а далі обрати підстрічку з мінімальною відстанню. Але цей алгоритм мав би складність O(n³ m).
Кращий підхід базується на динамічному програмуванні. Він використовує альтернативну постановку задачі: для кожної позиції j в тексті T, а також кожної позиції i в патерні Р обчислити мінімальну редакційну відстань між i першими літерами патерну, P_i, та будь-якої підстрічки T_j`,j T, що закінчується на позиції j.

Для кожної позиції j в тексті T, і кожної позиції i в патерні P, пройти по всім підстрічкам T завершуючи на позиції j та визначити яка з них має мінімальну редакційну відстань до i перших літер патерну P.

Обчислення E(m, j) дуже схоже до обчислення редакційної відстані між двома стрічками. Насправді, ми можемо використати алгоритм Левенштейна для E(m, j), эдина відмінність полягає в тому що ми повинні ініціалізувати перший рядок нулями, та зберегти послідовність обчислення, як в E(i - 1,j), E(i,j - 1) або E(i - 1, j - 1) в обчисленні E(i,j).

В масиві що зберігає E(x,y) значення, ми потім вибираємо найменше значення в останньому рядку, наприклад E(x₂, y₂), і продовжуємо обчислення в інший бік, до номера рядку 0. Якщо поле до якого ми дійшли E(0, y₁), далі T[y₁ + 1] ... T[y₂] є підстрічкою Т з мінімальною редакційною відстанню до патерна Р.

Обчислюючи E(x,y) масив затрачує O(mn) часу з алгоритмом динамічного програмування, тим часом як обчислення-навпаки затрачує О(n + m) часу.

On-line проти off-line

Традиційно, алгоритми наближеного збігу рядків класифікуються двома категоріями: on-line та off-line. З on-line алгоритмами патерн може бути опрацьований перед пошуком, але текст - ні. Іншими словами, on-line техніки роблять пошук без індексування. Ранні алгоритми наближеного пошуку були запропоновані Вагнером та Фішером. Обидва алгоритми базуються на динамічному програмуванні але вирішують різні проблеми. Алгоритм Селлерса шукає наближено підстрічки в тексті, тим часом як алгоритми Вагнера та Фішера обчислюють відстань Левенштейна, будучи підходящими лише для нечіткого пошуку в словниках тільки.

Пошуки за технікою on-line були значно покращені. Можливо одне з найркащих покращень було задіяно в bitap (двійковий пошук) алгоритмі (також відомим як зсув-або та зсув-і алгоритмі), який дуже ефективний для коротких стрічок. Bitap алгоритм це якдро пошукових систем Unix, зокрема agrep утиліти. Огляд on-line алгоритмів був зроблений G. Navarro.

Незважаючи на існування дуже швидкої on-line техніки, їхня продуктивність на великих даних неприйнятна. Препроцесинг тексту або індексування робить динамічний пошук швидшим. Сьогодні, існує маса індексуючих алгоритмів. Серед них є суфіксні дерева, метричні дерева а також методи н-грам. Детальніший опис індексуючих технік, що дозволяють знаходити довільні підстрічки наданий у роботах Navarro. Обчислювальні опитувальники словникових методів (наприклад, методи, що дозволяють знаходити всі словникові слова, що наближено збігаються з шуканим патерном) надані в роботах Бойтсова.

Застосування

До недавніх пір найбільш часто наближений пошук застосовувався в системах перевірки правопису. Також, за наявністю великих обсягів ДНК даних, співставлення нуклеотидних послідовностей стало важливою задачею. Наближені порівняння використовуються в спам-фільтрах. Але наближене порівняння не може бути використане для бінарних даних, таких як зображень або музики. Вони потребують інших алгоритмів, таких як "акустичних відбитків"

Варто розглянути

Джерела

↑ Baeza-Yates R, Navarro G (June 1996). A faster algorithm for approximate string matching. У Dan Hirchsberg; Gene Myers (ред.). Combinatorial Pattern Matching (CPM'96), LNCS 1075. Irvine, CA. с. 1—23.
↑ Baeza-Yates R, Navarro G. Fast Approximate String Matching in a Dictionary (PDF). Proc. SPIRE'98. IEEE CS Press. с. 14—22. Архів оригіналу (PDF) за 1 серпня 2016. Процитовано 20 грудня 2016.
↑ Boytsov, Leonid (2011). Indexing methods for approximate dictionary searching: Comparative analysis. Jea Acm. 16 (1): 1—91. doi:10.1145/1963190.1963191.
↑ Cormen, Thomas; Leiserson, Rivest (2001). Introduction to Algorithms (вид. 2nd). MIT Press. с. 364–7. ISBN 0-262-03293-7.
↑ Galil, Zvi; Apostolico, Alberto (1997). Pattern matching algorithms. Oxford [Oxfordshire]: Oxford University Press. ISBN 0-19-511367-5.
↑ Gusfield, Dan (1997). Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge, UK: Cambridge University Press. ISBN 0-521-58519-8.
↑ Myers G (May 1999). A fast bit-vector algorithm for approximate string matching based on dynamic programming. Journal of the ACM. 46 (3): 395—415. doi:10.1145/316542.316550.
↑ Navarro, Gonzalo (2001). A guided tour to approximate string matching. ACM Computing Surveys. 33 (1): 31—88. CiteSeerX 10.1.1.96.7225. doi:10.1145/375360.375365.
↑ Navarro, Gonzalo, Ricardo Baeza-Yates, E. Sutinen and J. Tarhio (2001). Indexing Methods for Approximate String Matching (PDF). IEEE Data Engineering Bulletin. 24 (4): 19—27. Архів оригіналу (PDF) за 31 липня 2016. Процитовано 20 грудня 2016.
↑ Sellers, Peter H. (1980). The Theory and Computation of Evolutionary Distances: Pattern Recognition. Journal of Algorithms. 1 (4): 359—73. doi:10.1016/0196-6774(80)90016-4.
↑ Skiena, Steve (1998). Algorithm Design Manual (вид. 1st). Springer. ISBN 978-0-387-94860-7.
↑ Ukkonen E (1985). Algorithms for approximate string matching. Information and Control. 64: 100—18. doi:10.1016/S0019-9958(85)80046-2.
↑ Wagner R, Fischer M (1974). The string-to-string correction problem. Journal of the ACM. 21: 168—73. doi:10.1145/321796.321811.
↑ J. Zobel, P. Dart. Finding approximate matches in large lexicons. Software-Practice & Experience 25(3), pp 331–345, 1995.

Посилання

Flamingo Project [Архівовано 1 березня 2021 у Wayback Machine.]
Efficient Similarity Query Processing Project останні дослідження нечіткого пошуку.
StringMetric project [Архівовано 17 січня 2016 у Wayback Machine.] a Scala бібліотека стрічкових метрик