www.wikidata.uk-ua.nina.az

Наближена відповідність рядків Цю статтю треба вікіфікувати для відповідності стандартам якості Вікіпедії Будь ласка доп

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

Цю статтю треба вікіфікувати для відповідності стандартам якості Вікіпедії. Будь ласка, допоможіть додаванням доречних внутрішніх посилань або вдосконаленням розмітки статті. (лютий 2020)
Ця стаття є сирим перекладом з іншої мови. Можливо, вона створена за допомогою машинного перекладу або перекладачем, який недостатньо володіє обома мовами. Будь ласка, допоможіть поліпшити переклад. (червень 2023)

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

Загальний огляд Редагувати

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

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

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

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

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

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

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

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

Одне з можливих визначень задач наближеного збігу рядків є: Маємо стрічку паттерн P = p1p2...pm та текстову стрічку T = t1t2...tn, необхідно знайти стрічку Tj`,j = tj`...tj в Т, яка з усіх підстрічок Т, має найменшу редакційну відстань до паттерна P.

Підхід грубої сили мав би очислити редакційну відстань до P для всіх підстрічок T, а далі обрати підстрічку з мінімальною відстанню. Але цей алгоритм мав би складність O(n3 m).
Кращий підхід базується на динамічному програмуванні. Він використовує альтернативну постановку задачі: для кожної позиції j в тексті T, а також кожної позиції i в патерні Р обчислити мінімальну редакційну відстань між i першими літерами патерну, Pi, та будь-якої підстрічки Tj`,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(x2, y2), і продовжуємо обчислення в інший бік, до номера рядку 0. Якщо поле до якого ми дійшли E(0, y1), далі T[y1 + 1] ... T[y2] є підстрічкою Т з мінімальною редакційною відстанню до патерна Р.

Обчислюючи 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. . Proc. SPIRE'98. IEEE CS Press. с. 14–22. Архів оригіналу за 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. doi:10.1145/375360.375365.  Проігноровано невідомий параметр |citeseerx= (довідка)
  • ↑  Navarro, Gonzalo, Ricardo Baeza-Yates, E. Sutinen and J. Tarhio (2001). . IEEE Data Engineering Bulletin 24 (4): 19–27. Архів оригіналу за 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.

Посилання Редагувати

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Cyu stattyu treba vikifikuvati dlya vidpovidnosti standartam yakosti Vikipediyi Bud laska dopomozhit dodavannyam dorechnih vnutrishnih posilan abo vdoskonalennyam rozmitki statti lyutij 2020 Cya stattya ye sirim perekladom z inshoyi movi Mozhlivo vona stvorena za dopomogoyu mashinnogo perekladu abo perekladachem yakij nedostatno volodiye oboma movami Bud laska dopomozhit polipshiti pereklad cherven 2023 U komp yuternih naukah nablizhena vidpovidnist ryadkiv chasto vzhivayetsya yak nechitkij poshuk ryadkiv ce tehnika znahodzhennya strichok sho vidpovidaye paternu nablizheno anizh tochno Problema pribliznoyi vidpovidnosti strichok tipovo podilyayetsya na dvi pid problemi znahodzhennya nablizhenoyi pid strichki vseredini pevnoyi strichki ta znahodzhennya tih sho nablizheno vidpovidayut paternu Zmist 1 Zagalnij oglyad 2 Postanovka zavdannya ta algoritmi 3 On line proti off line 4 Zastosuvannya 5 Varto rozglyanuti 6 Dzherela 7 PosilannyaZagalnij oglyad RedaguvatiNablizhenist zbigu vimiryuyetsya kilkistyu primitivnih operacij neobhidnih dlya togo shob peretvoriti strichku na tochnij zbig Cya kilkist nazivayetsya redakcijnoyu vidstannyu mizh strichkoyu i paternom Zazvichaj yak operaciyi rozcinyuyutsya vstavka kit krit vidalennya krit kit zamina kit kitVsi ci tri operaciyi mozhut buti uzagalneni yak formi zamishennya z dodavannyami simvolu NULL tut zaznachenim yak pid chas vidalennya abo vstavki vstavka k it krit vidalennya krit k it zamina kit kitTakozh inkoli rozglyadayetsya operaciya transpoziciya v yakij dvi literi u strichci minyayutsya miscyami shob buti primitivnoyu operaciyeyu Zmina abc acb ce transpoziciya Rizni nablizheni obchislyuvachi nakladayut rizni obmezhennya Deyaki obchislyuvachi vikoristovuyut yedinu globalnu nezvazhenu vartist tobto zagalne chislo primitivnih operacij neobhidnih dlya peretvorennya zbigu paternom Napriklad yaksho paternom ye coil foil vidriznyayetsya odnoyu zaminoyu oil odnim vidalennyam ta foal dvoma zaminami Yaksho rahuvati sho okrema operaciya vartuye odniyeyi zatrati ta vstanoviti limit na odnu zatratu to coil foil ta oil budut validnimi zbigami a foal ni Inshi obchislyuvachi vkazuyut kilkist operacij kozhnogo tipu okremo u toj chas yak vsi inshi vstanovili zagalnu vartist ale dozvolyayut vidnositi rizni vagi do riznih operacij Deyaki obchislyuvachi dopuskayut okreme zadannya mezh i vag dlya okremih grup u strukturi Postanovka zavdannya ta algoritmi RedaguvatiOdne z mozhlivih viznachen zadach nablizhenogo zbigu ryadkiv ye Mayemo strichku pattern P p1p2 pm ta tekstovu strichku T t1t2 tn neobhidno znajti strichku Tj j tj tj v T yaka z usih pidstrichok T maye najmenshu redakcijnu vidstan do patterna P Pidhid gruboyi sili mav bi ochisliti redakcijnu vidstan do P dlya vsih pidstrichok T a dali obrati pidstrichku z minimalnoyu vidstannyu Ale cej algoritm mav bi skladnist O n3 m Krashij pidhid bazuyetsya na dinamichnomu programuvanni Vin vikoristovuye alternativnu postanovku zadachi dlya kozhnoyi poziciyi j v teksti T a takozh kozhnoyi poziciyi i v paterni R obchisliti minimalnu redakcijnu vidstan mizh i pershimi literami paternu Pi ta bud yakoyi pidstrichki Tj j T sho zakinchuyetsya na poziciyi j Dlya kozhnoyi poziciyi j v teksti T i kozhnoyi poziciyi i v paterni P projti po vsim pidstrichkam T zavershuyuchi na poziciyi j ta viznachiti yaka z nih maye minimalnu redakcijnu vidstan do i pershih liter paternu P Obchislennya E m j duzhe shozhe do obchislennya redakcijnoyi vidstani mizh dvoma strichkami Naspravdi mi mozhemo vikoristati algoritm Levenshtejna dlya E m j edina vidminnist polyagaye v tomu sho mi povinni inicializuvati pershij ryadok nulyami ta zberegti poslidovnist obchislennya yak v E i 1 j E i j 1 abo E i 1 j 1 v obchislenni E i j V masivi sho zberigaye E x y znachennya mi potim vibirayemo najmenshe znachennya v ostannomu ryadku napriklad E x2 y2 i prodovzhuyemo obchislennya v inshij bik do nomera ryadku 0 Yaksho pole do yakogo mi dijshli E 0 y1 dali T y1 1 T y2 ye pidstrichkoyu T z minimalnoyu redakcijnoyu vidstannyu do paterna R Obchislyuyuchi E x y masiv zatrachuye O mn chasu z algoritmom dinamichnogo programuvannya tim chasom yak obchislennya navpaki zatrachuye O n m chasu On line proti off line RedaguvatiTradicijno algoritmi nablizhenogo zbigu ryadkiv klasifikuyutsya dvoma kategoriyami on line ta off line Z on line algoritmami patern mozhe buti opracovanij pered poshukom ale tekst ni Inshimi slovami on line tehniki roblyat poshuk bez indeksuvannya Ranni algoritmi nablizhenogo poshuku buli zaproponovani Vagnerom ta Fisherom Obidva algoritmi bazuyutsya na dinamichnomu programuvanni ale virishuyut rizni problemi Algoritm Sellersa shukaye nablizheno pidstrichki v teksti tim chasom yak algoritmi Vagnera ta Fishera obchislyuyut vidstan Levenshtejna buduchi pidhodyashimi lishe dlya nechitkogo poshuku v slovnikah tilki Poshuki za tehnikoyu on line buli znachno pokrasheni Mozhlivo odne z najrkashih pokrashen bulo zadiyano v bitap dvijkovij poshuk algoritmi takozh vidomim yak zsuv abo ta zsuv i algoritmi yakij duzhe efektivnij dlya korotkih strichok Bitap algoritm ce yakdro poshukovih sistem Unix zokrema agrep utiliti Oglyad on line algoritmiv buv zroblenij G Navarro Nezvazhayuchi na isnuvannya duzhe shvidkoyi on line tehniki yihnya produktivnist na velikih danih neprijnyatna Preprocesing tekstu abo indeksuvannya robit dinamichnij poshuk shvidshim Sogodni isnuye masa indeksuyuchih algoritmiv Sered nih ye sufiksni dereva metrichni dereva a takozh metodi n gram Detalnishij opis indeksuyuchih tehnik sho dozvolyayut znahoditi dovilni pidstrichki nadanij u robotah Navarro Obchislyuvalni opituvalniki slovnikovih metodiv napriklad metodi sho dozvolyayut znahoditi vsi slovnikovi slova sho nablizheno zbigayutsya z shukanim paternom nadani v robotah Bojtsova Zastosuvannya RedaguvatiDo nedavnih pir najbilsh chasto nablizhenij poshuk zastosovuvavsya v sistemah perevirki pravopisu Takozh za nayavnistyu velikih obsyagiv DNK danih spivstavlennya nukleotidnih poslidovnostej stalo vazhlivoyu zadacheyu Nablizheni porivnyannya vikoristovuyutsya v spam filtrah Ale nablizhene porivnyannya ne mozhe buti vikoristane dlya binarnih danih takih yak zobrazhen abo muziki Voni potrebuyut inshih algoritmiv takih yak akustichnih vidbitkiv Varto rozglyanuti RedaguvatiConcept search en Podibnist Dzharo Vinklera Vidstan Levenshtejna Locality sensitive hashing en Metafon Algoritm Nidlmana Vunsha Viyavlennya plagiatu Regulyarnij viraz Smith Waterman algorithm en Soundex String metric en Dzherela Redaguvati Baeza Yates R Navarro G June 1996 A faster algorithm for approximate string matching U Dan Hirchsberg Gene Myers Combinatorial Pattern Matching CPM 96 LNCS 1075 Irvine CA s 1 23 Baeza Yates R Navarro G Fast Approximate String Matching in a Dictionary Proc SPIRE 98 IEEE CS Press s 14 22 Arhiv originalu za 1 serpnya 2016 Procitovano 20 grudnya 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 vid 2nd MIT Press s 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 doi 10 1145 375360 375365 Proignorovano nevidomij parametr citeseerx dovidka Navarro Gonzalo Ricardo Baeza Yates E Sutinen and J Tarhio 2001 Indexing Methods for Approximate String Matching IEEE Data Engineering Bulletin 24 4 19 27 Arhiv originalu za 31 lipnya 2016 Procitovano 20 grudnya 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 vid 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 amp Experience 25 3 pp 331 345 1995 Posilannya RedaguvatiFlamingo Project Arhivovano 1 bereznya 2021 u Wayback Machine Efficient Similarity Query Processing Project ostanni doslidzhennya nechitkogo poshuku StringMetric project Arhivovano 17 sichnya 2016 u Wayback Machine a Scala biblioteka strichkovih metrik Otrimano z https uk wikipedia org w index php title Nablizhena vidpovidnist ryadkiv amp oldid 39787764