Welk string-zoekalgoritme is eigenlijk het snelste?

Het hangt af van het soort zoekopdracht dat u wilt uitvoeren. Elk van de algoritmen presteert bijzonder goed voor bepaalde typen zoekopdrachten, maar u heeft de context van uw zoekopdrachten niet aangegeven.

Hier zijn enkele typische gedachten over zoektypen:

• Boyer-Moore: werkt door het patroon vooraf te analyseren en van rechts naar links te vergelijken. Als er een mismatch optreedt, wordt de initiële analyse gebruikt om te bepalen hoe ver het patroon kan worden verschoven t.o.v. de tekst die wordt doorzocht. Dit werkt vooral goed bij lange zoekpatronen. In het bijzonder kan het sublineair zijn, aangezien u niet elk afzonderlijk teken van uw tekst hoeft te lezen.

• Knuth-Morris-Pratt: analyseert ook vooraf het patroon , maar probeert te hergebruiken wat al was gematcht in het eerste deel van het patroon om te voorkomen dat dit opnieuw moet worden aangepast. Dit kan best goed werken, als uw alfabet klein is (bv. DNA-basen), aangezien u een grotere kans krijgt dat uw zoekpatronen herbruikbare subpatronen bevatten.

• Aho- Corasick: Heeft veel voorbewerking nodig, maar doet dit voor een aantal patronen. Als je weet dat je steeds weer naar dezelfde zoekpatronen zult zoeken, dan is dit veel beter dan de andere, omdat je patronen maar één keer hoeft te analyseren, niet één keer per zoekopdracht.

Daarom is er, zoals gebruikelijk in CS, geen definitief antwoord op de overall beste . Het is eerder een kwestie van het juiste hulpmiddel voor de taak kiezen.

Nog een opmerking over uw worst-case-redenering: overweeg de soorten zoekopdrachten die nodig zijn om die worst-case te creëren en denk goed na of deze zijn in uw geval echt relevant. De O(mn) worst-case-complexiteit van het Boyer-Moore-algoritme komt bijvoorbeeld voort uit een zoekpatroon en een tekst die elk slechts één teken gebruiken (zoals het vinden van aaa in aaaaaaaaaaaaaaaaaaaaa) – moet je echt snel zijn voor dat soort zoekopdrachten?

Reacties

• Ik heb het hele Engelse alfabet of zo te gebruiken en ik heb de vraag bijgewerkt, sorry dat ik hier niet mee begonnen ben bij het bedelen.
• En ja, ik moet snel zijn, zelfs voor zoekopdrachten zoals dat
• kunt u alstublieft uitweiden over Z ‘ s algoritme en manachar ook?

Hoewel ik een beetje laat ben om deze vraag te beantwoorden, maar ik denk dat Z-Algorithm veel sneller is dan alle tegenhangers.De complexiteit in het slechtste geval is O (m + n) en vereist geen voorbewerking van het patroon / de tekst. Het is ook heel gemakkelijk te coderen in vergelijking met de andere algoritmen.

Het werkt op de volgende manier.

Er is bijvoorbeeld een string S ="abaaba". We moeten z(i) waarden vinden voor i=0 to len(S)-1. Voordat ik op de uitleg inga, wil ik eerst wat definities vastleggen.

z(i) = no. van tekens van het voorvoegsel S dat overeenkomt met het voorvoegsel van s(i).

s(i) = ith achtervoegsel van S.

De volgende zijn de s(i) waarden voor s = "abaaba".

s(0) = "abaaba" = S s(1) = "baaba" s(2) = "aaba" s(3) = "aba" s(4) = "ba" s(5) = "a" 

De z-waarden zijn respectievelijk

z(0) = 6 = length(S) z(1) = 0 z(2) = 1 z(3) = 3 z(4) = 0 z(5) = 1 

Raadpleeg de volgende links voor een gedetailleerd begrip van het algoritme.

http://codeforces.com/blog/entry/3107

https://www.youtube.com/watch?v=MFK0WYeVEag

Nu is O (N) nodig om alle z -waarden te vinden zonder enige overhead voor voorverwerking. Je zou je nu afvragen hoe je deze logica kunt gebruiken om het patroon in een bepaalde string te matchen?

Laten we eens kijken met een voorbeeld. Patroon (P): aba, Tekst (T): aacbabcabaad.

Zet dit in de vorm P $ T. ($ – elk teken dat niet in een patroon of tekst voorkomt. Ik “kom binnen een tijdje tot het belang van $.)

P$T = aba$aacbabcabaad

We weten len(P) = 3.

Alle z-waarden van P$T zijn

z(0) = 16 = len(P$T) z(1) = 0 z(2) = 1 z(3) = 0 z(4) = 1 z(5) = 1 z(6) = 0 z(7) = 0 z(8) = 2 z(9) = 0 z(10) = 0 z(11) = 3 z(12) = 0 z(13) = 1 Z(14) = 1 Z(15) = 0 

Nu welke z(i) = len(P). Ans = 11. Ons patroon is dus aanwezig op Ans-len(P)-1 = 7. -1 is voor $ teken.

Waarom nu $ of zon speciaal karakter is belangrijk. Overweeg P = "aaa" en T = "aaaaaaa". Zonder het speciale teken hebben alle z(i) incrementele waarden. Men kan nog steeds de positie van het patroon in de tekst vinden met de onderstaande formules:

Conditie: z(i)> = len(P) en positie: Ans-len(P). Maar de toestand wordt in dit geval een beetje lastig en verwarrend. Persoonlijk geef ik er de voorkeur aan om de speciale karaktertechniek te gebruiken.

Opmerkingen

• Kunt u het hier zelf uitleggen? Het hebben van links naar externe sites kan worden gebruikt om uit te werken, maar de kern van een antwoord zou in het antwoord zelf moeten liggen in plaats van een link naar een andere site te moeten volgen.
• Het z-algoritme is in principe hetzelfde als kmp. Ik betwijfel of het veel sneller is.
• Ik ben het eens met @ThomasAhle. Berekenen z is aan het voorbewerken. Het ‘ is echter een goede uitleg. Ik heb een O(n) manier opgezet om van KMP-voorverwerking naar Z-voorverwerking om te zetten, vanwege dit antwoord. Hier

Gebruik inhoud adresseerbaar geheugen , geïmplementeerd in software in de vorm van virtuele adressering (letters naar letters wijzen).

Het is een beetje overbodig voor een gemiddeld string-matching-algoritme.

CAM kan een groot aantal patronen tegelijkertijd matchen, tot ongeveer 128-letterpatronen (als ze ASCII zijn; als ze Unicode slechts 64 zijn). En het is één aanroep per lengte van de letter in de string waarmee u wilt matchen en één willekeurige uitlezing uit het geheugen per lengte van de maximale patroonlengte. Dus als je een reeks van 100.000 letters analyseert, met maximaal 90.000.000 patronen tegelijkertijd (wat ongeveer 128 GiB zou kosten om een zo groot aantal patronen op te slaan), zou het 12.800.000 willekeurige leesbewerkingen van RAM vereisen, dus het zou gebeuren in 1 ms. / p>

Hier is hoe de virtuele adressering werkt.

Als ik begin met 256 startadressen, die de eerste letter vertegenwoordigen, verwijzen deze letters naar 256 van de volgende letters. Als een patroon bestaat niet, je slaat het niet op.

Dus als ik letters aan letters blijf koppelen, is het alsof ik 128 schijfjes virtuele adressering heb die naar virtuele adressering verwijzen.

Dat zal werk — maar om 900.000.000 patronen tegelijkertijd overeen te laten komen, is er nog een laatste truc om eraan toe te voegen — en daar wordt geprofiteerd van van het feit dat je begint met veel hergebruik van deze briefbuffers, maar later uit de hand loopt.Als je de inhoud opsomt, in plaats van alle 256 tekens toe te wijzen, wordt het heel weinig vertraagd en krijg je een capaciteitsverhoging van 100 keer, omdat je uiteindelijk maar 1 letter gebruikt in elke letterpointerbuffer (die ik heb nagesynchroniseerd ” escape “).

Als je een string-match met de dichtstbijzijnde buur wilt krijgen, dan heb je veel van deze parallel lopen en verzamel je ze in een hiërarchie, dus je spreidt je fout onbevooroordeeld uit. als je probeert om naaste-buur met slechts één, dan ben je “bevooroordeeld naar het begin van de boom.

Reacties

• @MagnusRobertCarlWoot aangezien je dezelfde gavatar als roucer81, is het ofwel een astronomisch toeval van een hashcode-botsing of je hebt hetzelfde e-mailadres. Als u dezelfde persoon achter beide accounts heeft, moet u het ” contact ” -formulier gebruiken om ze samen te voegen, zodat u de juiste erkenning krijgt voor de reputatie die is verkregen door upvotes over dit antwoord.