Duomenų Mokslas Ir Duomenų Bazės
Užkariaukite stygų paiešką naudodami „Aho-Corasick“ algoritmą
Stygų manipuliavimas ir šablonų paieška jose yra pagrindinės duomenų mokslo užduotys ir tipiškos bet kurio programuotojo užduotys.
Efektyvūs eilučių algoritmai vaidina svarbų vaidmenį daugelyje duomenų mokslo procesų. Dažnai būtent tokie procesai yra pakankamai įmanomi praktiškam naudojimui.
Šiame straipsnyje sužinosite apie vieną iš galingiausių algoritmų, ieškančių šablonų dideliame kiekyje teksto: „Aho-Corasick“ algoritmą. Šis algoritmas naudoja a trie duomenų struktūra (tariama „pabandyti“) sekti paieškos modelius ir naudoja paprastą metodą, kad efektyviai rastų visus tam tikro modelio rinkinio atvejus bet kuriame teksto taške.
Ankstesniame „ApeeScape Engineering“ tinklaraščio straipsnyje buvo parodytas eilutės paieškos algoritmas šiai pačiai problemai. Šiame straipsnyje pasirinktas požiūris suteikia didesnį skaičiavimo sudėtingumą.
Knuth-Morris-Pratt (KMP) algoritmas
Norėdami suprasti, kaip galime efektyviai ieškoti kelių teksto modelių, pirmiausia turime išspręsti lengvesnę problemą: ieškokite vieno modelio tam tikrame tekste.
Tarkime, kad turime didelį ilgio teksto dėmę N ir rašto (kurio norime ieškoti tekste) ilgio M . Nesvarbu, ar norime ieškoti vieno šio modelio, ar visų atvejų, galime pasiekti skaičiavimo sudėtingumą O (N + M) naudojant KMP algoritmą.
Priešdėlio funkcija
KMP algoritmas veikia apskaičiuodamas ieškomo modelio priešdėlio funkciją. Prefiksų funkcija iš anksto apskaičiuoja kiekvieno šablono priešdėlio atsarginę padėtį.
Apibrėžkime savo paieškos modelį kaip eilutę, pažymėtą S Kiekvienai pakraščiai S[0..i], kur i >= 1, rasime maksimalų šios eilutės priešdėlį, kuris taip pat yra šios eilutės galūnė. Pažymėsime šio priešdėlio ilgį P[i]
Modeliui „abracadabra“ priešdėlio funkcija sukurs šias atsargines pozicijas:
Rodyklė (i) | 0 | vienas | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Charakteris | į | b | r | į | c | į | d | į | b | r | į |
Priešdėlio ilgis (P[i]) | 0 | 0 | 0 | vienas | 0 | vienas | 0 | vienas | 2 | 3 | 4 |
Priešdėlio funkcija nurodo įdomią modelio savybę.
Paimkime pavyzdį tam tikrą modelio priešdėlį: „abrakadabas“. Šio priešdėlio priešdėlio funkcijos reikšmė yra dvi. Tai rodo, kad šiam prefiksui „abracadab“ egzistuoja antrojo ilgio priesaga, kuri tiksliai atitinka antrojo ilgio priešdėlį (ty raštas prasideda „ab“, o priešdėlis baigiasi „ab“). Be to, tai yra ilgiausias toks atitikmuo šiam priešdėliui.
Įgyvendinimas
Čia yra funkcija C #, kurią galima naudoti norint apskaičiuoti bet kurios eilutės priešdėlio funkciją:
public int[] CalcPrefixFunction(String s) { int[] result = new int[s.Length]; // array with prefix function values result[0] = 0; // the prefix function is always zero for the first symbol (its degenerate case) int k = 0; // current prefix function value for (int i = 1; i 0 && s[i] != s[k]) k = result[k - 1]; if (s[k] == s[i]) k++; // we've found the longest prefix - case 1 result[i] = k; // store this result in the array } return result; } Paleidus šią funkciją šiek tiek ilgesniu modeliu „abcdabcabcdabcdab“, gaunama:
Rodyklė (i) | 0 | vienas | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | vienuolika | 12 | 13 | 14 | penkiolika | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Charakteris | į | b | c | d | į | b | c | į | b | c | d | į | b | c | d | į | b |
Priešdėlio funkcija (P[i]) | 0 | 0 | 0 | 0 | vienas | 2 | 3 | vienas | 2 | 3 | 4 | 5 | 6 | 7 | 4 | 5 | 6 |
Skaičiavimo sudėtingumas
Nepaisant to, kad yra dvi įdėtos kilpos, priešdėlio funkcijos sudėtingumas yra teisingas O (M) , kur M yra rašto ilgis S .
Tai galima lengvai paaiškinti stebint, kaip veikia kilpos.
Visos išorinės kilpos iteracijos per i galima suskirstyti į tris atvejus:
-
Padidėja
kpo vieną. Kilpa užbaigia vieną kartojimą. -
Nekeičia nulinės vertės
k. Kilpa užbaigia vieną kartojimą. -
Nekeičia ar sumažina teigiamos vertės
k
Pirmieji du atvejai gali būti daugiausia M laikai.
Trečiuoju atveju apibrėžkime P(s, i) = k1 ir P(s, i + 1) = k2, k2 <= k1. Prieš kiekvieną iš šių atvejų turėtų būti k1 - k2 pirmo atvejo. Sumažėjimų skaičius neviršija k1 - k2 + 1. Ir iš viso mes turime ne daugiau kaip 2 * M. kartojimai.
Antrojo pavyzdžio paaiškinimas
Pažvelkime į antrąjį pavyzdžio modelį „abcdabcabcdabcdab“. Štai kaip žingsnis po žingsnio jį apdoroja priešdėlio funkcija:
-
Tuščiam poskirsniui ir „a“, kurio ilgis yra vienas, priešdėlio funkcijos vertė nustatoma į nulį. (
k = 0) -
Pažvelkite į abstraktą „ab“. Dabartinė vertė
kyra nulis, o simbolis „b“ nėra lygus simboliui „a“. Čia mes turime antrą atvejį iš ankstesnio skyriaus.kVertė lieka ties nuliu, o priešdėlio funkcijos reikšmė substringui „ab“ taip pat lygi nuliui. -
Tai tas pats atvejis, kai pateikiamos pakraštys „abc“ ir „abcd“. Nėra priešdėlių, kurie taip pat yra šių pakraščių galūnės. Jų vertė lieka nulyje.
-
Dabar pažvelkime į įdomų atvejį, poskyrį „abcda“. Dabartinė vertė
kvis dar yra nulis, bet paskutinis mūsų poskyrio simbolis sutampa su pirmuoju simboliu. Tai sukelias[k] == s[i]sąlygą, kurk == 0iri == 4. Masyvas yra nulinis indeksas irkyra kito maksimalaus ilgio priešdėlio simbolio rodyklė. Tai reiškia, kad mes radome maksimalaus ilgio priešdėlį savo substringui, kuris taip pat yra priesaga. Turime pirmąjį atvejį, kai naujakreikšmė yra viena, taigi ir priešdėlio funkcijos reikšmė P („abcda“) yra vienas. -
Tas pats atvejis pasitaiko ir kitose dviejose pogrupiuose, P („abcdab“) = 2 ir P („abcdabc“) = 3 . Čia mes ieškome savo modelio tekste, lygindami eilutes pagal simbolius. Tarkime, pirmieji septyni šablono simboliai sutapo su maždaug septyniais iš eilės apdoroto teksto simboliais, tačiau aštuntame simbolyje jis nesutampa. Kas turėtų atsitikti toliau? Naivaus eilučių derinimo atveju turėtume grąžinti septynis simbolius atgal ir vėl pradėti palyginimo procesą nuo pirmojo mūsų modelio simbolio. Su priešdėlio funkcijos reikšme (čia P („abcdabc“) = 3 ) žinome, kad mūsų trijų ženklų priesaga jau atitinka tris teksto simbolius. Ir jei kitas simbolis tekste yra „d“, suderinto mūsų rašto ir eilutės ilgis tekste padidinamas iki keturių („abcd“). Priešingu atveju P („abc“) = 0 ir palyginimo procesą pradėsime nuo pirmo modelio simbolio. Tačiau svarbu tai, kad mes negrįšime apdorodami tekstą.
-
Kitas poskyris yra „abcdabca“. Ankstesniame poskyryje priešdėlio funkcija buvo lygi trims. Tai reiškia, kad
k = 3yra didesnis nei nulis, ir tuo pačiu metu mes nesutapame kito simbolio priešdėlyje (s[k] = s[3] = 'd') ir kito simbolio galūnėje (s[i] = s[7] = 'a'). Tai reiškia, kad suaktyvinomes[k] != s[i]sąlygą ir kad priešdėlis „abcd“ negali būti mūsų eilutės galūnė. Turėtume sumažintikvertę ir palyginimui imkite ankstesnį priešdėlį, jei įmanoma. Kaip aprašėme aukščiau, masyvas yra nulinis indeksas irkyra kito simbolio, kurį tikriname iš priešdėlio, rodyklė. Paskutinis šiuo metu suderinto priešdėlio indeksas yrak - 1Imame prefiksų funkcijos reikšmę šiuo metu suderinamam prefiksuik = result[k - 1]. Mūsų atveju (trečiasis atvejis) maksimalaus priešdėlio ilgis bus sumažintas iki nulio, o paskui kitoje eilutėje jis bus padidintas iki vienos, nes „a“ yra didžiausias priešdėlis, kuris yra ir mūsų pakraščio galūnė. -
(Čia mes tęsiame skaičiavimo procesą, kol pasieksime įdomesnį atvejį.)
-
Mes pradedame apdoroti šią eilutę: „abcdabcabcdabcd“. Dabartinė vertė
kyra septyneri. Kaip ir „abcdabca“ aukščiau, mes pataikėme į neatitikimą: Kadangi simbolis „a“ (septintasis simbolis) nėra lygus simboliui „d“, substringas „abcdabca“ negali būti mūsų eilutės galūnė. Dabar gauname jau apskaičiuotą „abcdabc“ (trijų) priešdėlio funkcijos vertę ir dabar turime atitikmenį: Priešdėlis „abcd“ taip pat yra mūsų eilutės galūnė. Didžiausias jos priešdėlis ir prefikso funkcijos vertė mūsų pakraščiuose yra keturi, nes tai yra dabartinėktapo. -
Mes tęsiame šį procesą iki modelio pabaigos.
Trumpai: abu ciklai trunka ne daugiau kaip 3 M iteracijas, o tai įrodo, kad sudėtingumas yra O (M). Atminties naudojimas taip pat yra O (M).
KMP algoritmo įgyvendinimas
public int KMP(String text, String s) { int[] p = CalcPrefixFunction(s); // Calculate prefix function for a pattern string // The idea is the same as in the prefix function described above, but now // we're comparing prefixes of text and pattern. // The value of maximum-length prefix of the pattern string that was found // in the text: int maxPrefixLength = 0; for (int i = 0; i 0 && text[i] != s[maxPrefixLength]) maxPrefixLength = p[maxPrefixLength - 1]; // If a match happened, increase the length of the maximum-length // prefix. if (s[maxPrefixLength] == text[i]) maxPrefixLength++; // If the prefix length is the same length as the pattern string, it // means that we have found a matching substring in the text. if (maxPrefixLength == s.Length) { // We can return this value or perform this operation. int idx = i - s.Length + 1; // Get the previous maximum-length prefix and continue search. maxPrefixLength = p[maxPrefixLength - 1]; } } return -1; } Aukščiau pateiktas algoritmas kartojasi po tekstą, po simbolį ir bando padidinti maksimalų priešdėlį tiek mūsų šablonui, tiek kai kurioms teksto konsekventų simbolių sekoms. Nesėkmės atveju mes negrąžinsime savo pozicijos ankstesniame tekste. Mes žinome maksimalų rastos modelio pakraščio priešdėlį; šis priešdėlis taip pat yra šio surasto poskyrio galūnė ir mes galime tiesiog tęsti paiešką.
Šios funkcijos sudėtingumas yra toks pat kaip ir priešdėlio funkcijos, todėl bendras skaičiavimo sudėtingumas O (N + M) su O (M) atmintis.
Smulkmenos: metodai
String.IndexOf()irString.Contains().NET sistemoje po gaubtu turi tokio pat sudėtingumo algoritmą.
„Aho-Corasick“ algoritmas
Dabar mes norime padaryti tą patį keliems modeliams.
Tarkime, kad yra M ilgių raštai L1 , L2 , ..., Lm . Turime surasti visas ilgio tekste pateiktų žodžių modelių atitikmenis N .
Menkas sprendimas būtų bet kurio algoritmo paėmimas iš pirmosios dalies ir jo vykdymas M laikai. Mes turime sudėtingumą O (N + L1 + N + L2 +… + N + Lm) , t.y. O (M * N + L) .
Bet koks pakankamai rimtas testas užmuša šį algoritmą.
Paėmus žodyną su 1000 labiausiai paplitusių angliškų žodžių kaip modelius ir jį naudojant ieškoti Tolstojaus „Karas ir taika“ angliškoje versijoje, prireiktų nemažai laiko. Knyga yra daugiau nei trijų milijonų simbolių.
Jei paimsime 10 000 labiausiai paplitusių angliškų žodžių, algoritmas veiks maždaug 10 kartų lėčiau. Akivaizdu, kad dėl didesnių nei šis įvesties, vykdymo laikas taip pat pailgės.
Čia magija yra „Aho-Corasick“ algoritmas.
„Aho-Corasick“ algoritmo sudėtingumas yra O (N + L + Z) , kur SU yra rungtynių skaičius. Šį algoritmą išrado Alfredas V. Aho ir Margaret J. Corasick 1975 m.
Įgyvendinimas
Čia mums reikia „trie“ ir į savo algoritmą įtraukiame panašią idėją į prieš tai aprašytas priešdėlių funkcijas. Apskaičiuosime viso žodyno priešdėlių funkcijos reikšmes.
Kiekvienoje viršūnėje yra tokia informacija:
public class Vertex { public Vertex() { Children = new Hashtable(); Leaf = false; Parent = -1; SuffixLink = -1; WordID = -1; EndWordLink= -1; } // Links to the child vertexes in the trie: // Key: A single character // Value: The ID of vertex public Hashtable Children; // Flag that some word from the dictionary ends in this vertex public bool Leaf; // Link to the parent vertex public int Parent; // Char which moves us from the parent vertex to the current vertex public char ParentChar; // Suffix link from current vertex (the equivalent of P[i] from the KMP algorithm) public int SuffixLink; // Link to the leaf vertex of the maximum-length word we can make from the current prefix public int EndWordLink; // If the vertex is the leaf, we store the ID of the word public int WordID; } Yra keli būdai, kaip įgyvendinti vaikų nuorodas. Algoritmo sudėtingumas bus O (N + L + Z) masyvo atveju, tačiau tam reikės papildomo atminties O (L * q) , kur q yra abėcėlės ilgis, nes tai yra maksimalus vaikų skaičius, kurį gali turėti mazgas.
Jei naudosime kažkokią struktūrą su O (log (q)) prieigą prie jo elementų, turime papildomą atminties poreikį O (L) , bet viso algoritmo sudėtingumas bus O ((N + L) * log (q) + Z) .
Maišos stalo atveju mes turime O (L) papildomos atminties ir viso algoritmo sudėtingumas bus O (N + L + Z) .
Šioje pamokoje naudojama maišos lentelė, nes ji taip pat veiks su skirtingais simbolių rinkiniais, pvz., Kinų simboliais.
Mes jau turime viršūnės struktūrą. Tada mes apibrėžsime viršūnių sąrašą ir inicializuosime šaknies mazgą.
public class Aho { List Trie; List WordsLength; int size = 0; int root = 0; public Aho() { Trie = new List(); WordsLength = new List(); Init(); } private void Init() { Trie.Add(new Vertex()) size++; } } Tada mes įtraukiame visus modelius į trejetą. Tam mums reikia metodo, kaip pridėti žodžius prie „trie“:
public void AddString(String s, int wordID) { int curVertex = root; for (int i = 0; i Šiuo metu visi šabloniniai žodžiai yra duomenų struktūroje. Tam reikia papildomos atminties O (L) .
Toliau turime apskaičiuoti visas priesagines nuorodas ir žodyno įvesties nuorodas.
Kad būtų aišku ir lengvai suprantama, aš eisiu per trejetą nuo šaknies iki lapų ir atliksiu panašius skaičiavimus, kaip mes padarėme KMP algoritmui, tačiau, priešingai nei KMP algoritme, kur randame maksimalų ilgį priešdėlis, kuris taip pat buvo to paties poskyrio galūnė, dabar rasime maksimalaus ilgio dabartinės pakraščio galūnę, kuri taip pat yra kai kurių modelių priešdėlis. Šios funkcijos reikšmė nebus rasto priesagos ilgis; tai bus nuoroda į paskutinį maksimalios dabartinės pakraščio galūnės simbolį. Tai turiu omenyje viršūnės galūnės nuorodą.
Aš apdorosiu viršūnes pagal lygius. Tam naudosiu a pirmojo pločio paieška (BFS) algoritmas:
Toliau pateikiamas šio perėjimo įgyvendinimas:
public void PrepareAho() { Queue vertexQueue = new Queue(); vertexQueue.Enqueue(root); while (vertexQueue.Count > 0) { int curVertex = vertexQueue.Dequeue(); CalcSuffLink(curVertex); foreach (char key in Trie[curVertex].Children.Keys) { vertexQueue.Enqueue((int)Trie[curVertex].Children[key]); } } } Žemiau yra CalcSuffLink kiekvienos viršūnės galūnės nuorodos apskaičiavimo metodas (t. y. prefikso funkcijos vertė kiekvienai trie substringei):
public void CalcSuffLink(int vertex) { // Processing root (empty string) if (vertex == root) { Trie[vertex].SuffixLink = root; Trie[vertex].EndWordLink = root; return; } // Processing children of the root (one character substrings) if (Trie[vertex].Parent == root) { Trie[vertex].SuffixLink = root; if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; return; } // Cases above are degenerate cases as for prefix function calculation; the // value is always 0 and links to the root vertex. // To calculate the suffix link for the current vertex, we need the suffix // link for the parent of the vertex and the character that moved us to the // current vertex. int curBetterVertex = Trie[Trie[vertex].Parent].SuffixLink; char chVertex = Trie[vertex].ParentChar; // From this vertex and its substring we will start to look for the maximum // prefix for the current vertex and its substring. while (true) { // If there is an edge with the needed char, we update our suffix link // and leave the cycle if (Trie[curBetterVertex].Children.ContainsKey(chVertex)) { Trie[vertex].SuffixLink = (int)Trie[curBetterVertex].Children[chVertex]; break; } // Otherwise, we are jumping by suffix links until we reach the root // (equivalent of k == 0 in prefix function calculation) or we find a // better prefix for the current substring. if (curBetterVertex == root) { Trie[vertex].SuffixLink = root; break; } curBetterVertex = Trie[curBetterVertex].SuffixLink; // Go back by sufflink } // When we complete the calculation of the suffix link for the current // vertex, we should update the link to the end of the maximum length word // that can be produced from the current substring. if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; } Šio metodo sudėtingumas yra O (L) ; atsižvelgiant į vaiko kolekcijos įgyvendinimą, gali būti sudėtinga O (L * log (q)) .
Sudėtingumo įrodymas yra panašus į sudėtingumo priešdėlio funkcijos įrodymą KMP algoritme.
Pažvelkime į šį vaizdą. Tai yra žodžio treja vizualizacija { abba, cab, baba, caab, ac, abac, bac } su visa apskaičiuota informacija:
„Trie“ kraštai yra giliai mėlyni, priesagos nuorodos yra šviesiai mėlynos, o žodynų galūnių nuorodos - žalios spalvos. Žodyno įrašus atitinkantys mazgai paryškinami mėlyna spalva.
Dabar mums reikia tik dar vieno metodo - apdoroti teksto bloką, kurio ketiname ieškoti:
public int ProcessString(String text) { // Current state value int currentState = root; // Targeted result value int result = 0; for (int j = 0; j Dabar tai paruošta naudoti:
Įvesties metu turime šablonų sąrašą:
List patterns; Ir ieškokite teksto:
string text; Štai kaip jį suklijuoti:
// Init the trie structure. As an optional parameter we can put the approximate // size of the trie to allocate memory just once for all nodes. Aho ahoAlg = new Aho(); for (int i = 0; i Štai ir viskas! Dabar jūs žinote, kaip veikia šis paprastas, tačiau galingas algoritmas!
„Aho-Corasick“ yra tikrai lanksti. Paieškos šablonai nebūtinai turi būti tik žodžiai, tačiau galime naudoti ištisus sakinius arba atsitiktines simbolių grandines.
Spektaklis
Algoritmas buvo išbandytas naudojant „Intel Core i7-4702MQ“.
Testams atlikti paėmiau du žodynus: 1 000 labiausiai paplitusių angliškų žodžių ir 10 000 labiausiai paplitusių angliškų žodžių.
Norėdami pridėti visus šiuos žodžius į žodyną ir paruošti duomenų struktūrą darbui su kiekvienu žodynu, algoritmui reikėjo atitinkamai 55 ms ir 135 ms.
Algoritmas per 1,0–1,3 sekundės apdorojo tikras 3–4 milijonų simbolių knygas, o maždaug 30 milijonų simbolių knygai prireikė 9,6 sekundės.
„Aho-Corasick“ algoritmo lygiagretumas
Eiti lygiagrečiai su „Aho-Corasick“ algoritmu visai nėra problema:
Didelį tekstą galima suskirstyti į kelis gabalus, o kiekvienam gabalui apdoroti galima naudoti kelias gijas. Kiekviena gija turi prieigą prie sugeneruoto terio pagal žodyną.
O žodžiai, išskaidyti ties riba tarp gabalų? Šią problemą galima lengvai išspręsti.
Leisti N būti mūsų didelio teksto ilgiu, S būti gabalėlio dydžio ir L būti didžiausio žodyno modelio ilgiu.
Dabar mes galime naudoti paprastą triuką. Mes padalijame gabalėlius, kurių galas šiek tiek sutampa, pavyzdžiui, paimkite [S * (i - 1), S * i + L - 1], kur i yra gabalo indeksas. Gavę modelio atitiktį, mes galime lengvai gauti dabartinės atitikties pradinį indeksą ir tiesiog patikrinti, ar šis indeksas yra gabalų diapazone, be sutapimų, [S * (i - 1), S * i - 1]
Universalus eilučių paieškos algoritmas
„Aho-Corasick“ algoritmas yra galingas eilučių derinimo algoritmas, siūlantis geriausią bet kokio įvesties sudėtingumą ir nereikalaujantis daug papildomos atminties.
Algoritmas dažnai naudojamas įvairiose sistemose, pvz., Rašybos tikrintuvuose, šlamšto filtruose, paieškos sistemose, bioinformatikos / DNR sekos paieškose ir kt. Tiesą sakant, kai kurie populiarūs įrankiai, kuriuos galite naudoti kiekvieną dieną, naudoja šį algoritmą už kadro.
KMP algoritmo priešdėlio funkcija pati savaime yra įdomus įrankis, kuris paverčia vieno modelio derinimo sudėtingumą iki linijinio laiko. „Aho-Corasick“ algoritmas laikosi panašaus požiūrio ir naudoja „trie“ duomenų struktūrą, kad tą patį padarytų keliems modeliams.
Tikiuosi, kad ši „Aho-Corasick“ algoritmo pamoka jums buvo naudinga.
