Бојер-Мур алгоритам за претрагу ниски

Из Википедије, слободне енциклопедије

У рачунарству Бојер-Мур алгоритам за претрагу ниски је ефикасан алгоритам за претрагу низова који је стандардни репер за практично претраживање ниски у литератури. .[1] Развили су га Роберт С. Бојер и Ј Стротер Мур. [2] Алгоритам претпроцесује ниску која се тражи (узорак), али не ниску која се тражи (у тексту). Због тога је погодан за примене где се текст не састоји од више третрага али узорак да. Бојер-Мур алгоритам користи информације које су прикупљене током претпроцесирања да би прескочио делове текста, разултирајући мањим сталним фактором од многих других алторитама за ниске. У принципу, алгоритам ради брже док се дужина узорка повећава.

Дефиниције[уреди]

A Н П A Н M A Н -
П A Н - - - - - -
- П A Н - - - - -
- - П A Н - - - -
- - - П A Н - - -
- - - - П A Н - -
- - - - - A Н -
Поравнања узорка ПАН у тексту АНПАНМАН, од k=3 до k=8. Подударају се у k=5.
  • S[i] односи се на карактер у индексу i ниске S, почевши од 1.
  • S[i..j] се односи на подниску ниске S почевши од i и завршавајући се на j, закључно.
  • Префикс из S је подниска S[1..i] за неко i у размаку [1, n], где је n дужина S.
  • Суфикс из S је подниска S[i..n] за неко i у размаку [1, n], где је n дужина S.
  • Ниска која се тражи зове се узорак и зове се симболом P.
  • Ниска кроз коју се претражује зове се текст и зове се симболом T.
  • Дужина P је n.
  • Дужина T је m.
  • Поравнање од P до T је индекс k у T такав да последњи карактер из P је поравнат са индексом k из T.
  • Подударање или појава P се јавља у виду усклађивања ако је P еквивалентно са T[(k-n+1)..k].

Опис[уреди]

Бојер-Мур алгоритам тражи појављивања P у T вршећи експлицитно поређење карактера на различитим поравнањима. Уместо претраге сировом снагом свих поравнања (којих има m-n+1). Бојер-Мур користи информације добијене из претпроцесирања P да прескочи што више поравнања.

Алгоритам почиње код поравнања k = n, тако да је почетак P је поравнат са почетком T. Карактери P и T се онда пореде почевши од индекса n у P и k у Т, идући ка доле: ниске се упарују од краја ка почетку од P. Поређења се настављају све док не дође или до неусклађености или се дође до почетка P (што значи да је дошло до поклапања), после чега је поравнање померено у десно у складу са максималном вредношћу која је дозвољена одређеним правилима. Поређења се поново врше у новом поравнању, и процес се понавља све док поравнање не прође крај T.

Правила за померање се имплементирају као константе табеле за преглед, коришћењем табеле добијене током претпроцесирања P.

Правила за померање[уреди]

Правило лошег карактера[уреди]

Опис[уреди]

- - - - X - - K - - -
A Н П A N M A Н A M -
- Н Н A A M A Н - - -
- - - Н N A A M A Н -
Демонстрација правила лошег карактера са узорком ННААМАН.

Правило лошег карактера разматра карактер у T код ког процес поређења не успе (претпостављајући да ће до таквог неуспеха доћи). Следеће појављивање тог карактера лево у P се проналази, и промена коју доноси тај догађај у складу са непогођеним догађајем у T се предлаже. Ако се непогођени карактер не појави лево у P, предлаже се померање које помера цело P после тачке неслагања.

Претпроцесирање[уреди]

Методе варирају у тачном облику табела које правило лошег карактера треба да узме, али једноставно решење инстант-време претргагом је следеће: направити 2D табелу која се индексира прво по идексу карактера cу алфабету о другог по индексу i у узорку. Ово проналажење враћа појављивање c' y P са следећим највећим индексом j < i или -1 ако нема таквог догађаја. Предложено померање ће онда бити i - j, са O(1) временском сложеношћу и O(kn) просторном, претпостављајући коначну дужину речи дужине k.

Добро правило суфикса[уреди]

Опис[уреди]

- - - - X - - K - - - - -
M A N P A N A M A N A P -
A N A M P N A M - - - - -
- - - - A N A M P N A M -
Demonstration of good suffix rule with pattern ANAMPNAM.

Добро правило суфикса је упадљиво сложеније у оба концепта и имплементације од правила лошег карактера. То је разлог зашто поређења почињу на крају узорка радије него на почетку, и формално се наводи као:[3]

Претпоставимо да за дато поравнање из P и T, подстринг t из T одговара суфиксу из P, али до неслагања долази током следећег поређења улево. Онда пронаћи, уколико постоји, најдеснију копију t' из t у P тако да t' није суфикс из P и карактер лево од t' у P се раликује од карактера лево од t у P. Помера се P удесно тако да подниска t' у P је испод подниске t у T. Ако t' не постоји, онда помери улево од P после левог краја t у T за најмању величину тако да префикс помереног узорка се подудара са суфиксом t у T. Ако такво померање није могуће, онда помери P за n места у десно. Ако се појави P, онда помери P за најмању величину тако да одговарајући префикс помереног P се подудара са суфиксом настанка из P у T. Ако такво померање није могуће, онда помери P за n места, то јест, помери P поред T.

Претпроцесирање[уреди]

Добро правило префикса захтева две табеле: једну да користи у генералном случају, и још једну да се користи када када или генерални случај не врати неки значајан резултат или дође до подударања. Ове табеле ће бити одређене L и H односно. Њихове дефиниције су као што следи :[3]

За свако i, L[i] је највећа позиција мања од n таква да ниска P[i..n] се подудара са суфиксом од P[1..L[i]] и таква да карактер претходног чији суфикс није једнак P[i-1]. L[i] је постављен на нулу ако нема позиције која задовољава услов.

Нека H[i] означава дужину највећег суфикса из P[i..n] који је такође и префикс из P, ако он постоји. Ако не постоје, онда је H[i] постављен на нулу.

Обе табеле се могу направити тако да буду O(n) временска сложеност и да користе O(n) просторну сложеност. Поравнање померања индекса i у P је добијено из n - L[i] или n - H[i]. H би требало само да се користи ако је L[i] нула или је дошло до подударања.

Галил правило[уреди]

Једноставна али веома важна имплементација Бојер-Мура, поставио је Галил 1979.[4] За разлику од померања, Галил правило бави се убрзавањем поређења током сваког поравнања тако што прескаче делове за које се зна да се подударају. Претпоставимо да код поравнања k1, P се пореди са T до карактера c из T. Онда ако се P помера до k2 тако да је леви крај између c и k1, је следећа фаза префикса из P мора се подударати са подниском T[(k2 - n)..k1]. Тако да ако поређења дођу до позиције k1 of T, појављивање из P може се забележити без експлицитног проверања после k1. Поред тога што побољшава ефикасност Бојер-Мура, Галил правило увек мора даје lлинеарно време егзекуције у најгорем случају.

Перформансе[уреди]

Бојер-Мур алгоритам како је наведно у оригиналном раду има најгори случај временске сложености O(n+m) само ако се узорак не појави у тексту. Ово су први доказали Кнут, Морис, и Прат 1977,[5] затим Гуиба and Одлизко 1980[6] са горњом границом од 5m поређења у најгорем случају. Кол је дао доказ да горња граинца од 3m поређења у најгорем случају 1991.[7]

Када се узорак појави у тексту, временска сложеност оригиналног алгоритма је O(nm) у најгорем случају. Ово је лако видети када се и узорак и текст састоје само од истих понабљајућих карактера. Међутим, укључење Галил правила даје линеарну сложеност у свим случајевима.[4][7]

Имплементације[уреди]

Разне имплементације постоје у ралзичитим програмским језицима. У C++-y, Boost обезбеђује generic Boyer–Moore search имплементације у Алгоритми библиотеци.

Испод је пар једноставних имплементација

Варијанте[уреди]

Бојер-Мур-Хорспул алгоритам је упрошћавање Бојер-Мур алгоритма само користећи правило лошег карактера.

Апостолико-Ђанкарло алторитам убрзава процес проверавања да ли је до подударања дошло код одрешеног поравнања прескачући екплицитне провере карактера. Ово користи информације сакупљене током претпроцесирања узорка у спајању са суфкисом се подудараца са дужином забележеном при сваком покушају подударања. Чување дужина погођених суфикса захтева додатну табелу која је једнака величини текста који се претражује.

Види такође[уреди]

Референце[уреди]

  1. ^ Hume and Sunday (1991) [Fast String Searching] SOFTWARE—PRACTICE AND EXPERIENCE, VOL. 21(11), 1221–1248 (NOVEMBER 1991)
  2. ^ Boyer, Robert S.; Moore, J Strother (October 1977). „A Fast String Searching Algorithm.“. Comm. ACM (New York, NY, USA: Association for Computing Machinery) 20 (10): 762-772. DOI:10.1145/359842.359859. ISSN 0001-0782. 
  3. ^ а б Gusfield, Dan (1999) [1997], „Chapter 2 - Exact Matching: Classical Comparison-Based Methods“, Algorithms on Strings, Trees, and Sequences (1 ed.), Cambridge University Press, pp. 19-21, ISBN 0-521-58519-8 
  4. ^ а б Galil, Z. (September 1979). „On improving the worst case running time of the Boyer-Moore string matching algorithm“. Comm. ACM (New York, NY, USA: Association for Computing Machinery) 22 (9): 505-508. DOI:10.1145/359146.359148. ISSN 0001-0782. 
  5. ^ Knuth, Donald; Morris, James H.; Pratt, Vaughan (1977). „Fast pattern matching in strings“. SIAM Journal on Computing 6 (2): 323-350. DOI:10.1137/0206024. 
  6. ^ Guibas, Odlyzko; Odlyzko, Andrew (1977). „A new proof of the linearity of the Boyer-Moore string searching algorithm“. Proceedings of the 18th Annual Symposium on Foundations of Computer Science (Washington, DC, USA: IEEE Computer Society): 189-195. DOI:10.1109/SFCS.1977.3. 
  7. ^ а б Cole, Richard (September 1991). „Tight bounds on the complexity of the Boyer-Moore string matching algorithm“. Proceedings of the 2nd annual ACM-SIAM symposium on Discrete algorithms (Philadelphia, PA, USA: Society for Industrial and Applied Mathematics): 224-233. ISBN 0-89791-376-0. 

Литература[уреди]

Спољашње везе[уреди]