Acul într-un car de fân: un tutorial îndrăzneț al algoritmului de căutare a textului la scară largă

Când întâlnim termenul „căutare text”, de obicei ne gândim la un corp mare de text care este indexat într-un mod care face posibilă căutarea rapidă a unuia sau mai multor termeni de căutare atunci când sunt introduși de un utilizator. Aceasta este o problemă clasică pentru informaticieni, la care există multe soluții.

Dar ce zici de un scenariu invers? Ce se întâmplă dacă ceea ce este disponibil pentru indexare în prealabil este un grup de expresii de căutare și numai în timpul execuției este prezentat un corp mare de text pentru căutare? Aceste întrebări sunt ceea ce încearcă să abordeze acest tutorial privind structura de date.

Aplicații

O aplicație din lumea reală pentru acest scenariu este potrivirea unui număr de teze medicale cu o listă de afecțiuni medicale și a afla care teze discută care afecțiuni. Un alt exemplu este parcurgerea unei colecții mari de precedente judiciare și extragerea legilor la care se referă.

Abordare directă

Cea mai simplă abordare este să parcurgeți expresiile de căutare și să căutați în text fiecare frază, una câte una. Această abordare nu se scalează bine. Căutarea unui șir în interiorul altuia are complexitatea O(n) . Repetarea acestui lucru pentru m expresii de căutare duce la îngrozitorul O(m * n) .

Avantajul (probabil numai) al unei abordări directe pe care este simplu de implementat, așa cum se vede în următorul fragment C#:

 String[] search_phrases = File.ReadAllLines ("terms.txt"); String text_body = File.ReadAllText("body.txt"); int count = 0; foreach (String phrase in search_phrases) if (text_body.IndexOf (phrase) >= 0) ++count;

Rulând acest cod pe mașina mea de dezvoltare [1] față de un eșantion de testare [2], am avut o durată de rulare de 1 oră și 14 minute - cu mult peste timpul de care aveți nevoie pentru a lua o ceașcă de cafea, a vă ridica și a vă întinde sau orice altă scuză dezvoltatorii folosesc pentru a sări peste lucru.

O abordare mai bună - The Trie

Scenariul anterior poate fi îmbunătățit în câteva moduri. De exemplu, procesul de căutare poate fi partiționat și paralelizat pe mai multe procesoare/nuclee. Însă reducerea timpului de rulare realizată prin această abordare (timpul total de rulare de 20 de minute presupunând o împărțire perfectă pe 4 procesoare/nuclee) nu justifică complexitatea adăugată codării/depanării.

Cea mai bună soluție posibilă ar fi una care traversează corpul textului o singură dată. Aceasta presupune ca frazele de căutare să fie indexate într-o structură care poate fi transversală liniar, în paralel cu corpul textului, într-o singură trecere, realizând o complexitate finală de O(n) .

O structură de date care este deosebit de potrivită doar pentru acest scenariu este trie . Această structură de date versatilă este de obicei trecută cu vederea și nu este la fel de faimoasă ca alte structuri legate de arbore când vine vorba de probleme de căutare.

Tutorialul anterior al Toptal despre încercări oferă o introducere excelentă asupra modului în care sunt structurate și utilizate. Pe scurt, un trie este un arbore special, capabil să stocheze o secvență de valori în așa fel încât trasarea căii de la rădăcină la orice nod să producă un subset valid al acelei secvențe.

Deci, dacă putem combina toate expresiile de căutare într-o singură încercare, în care fiecare nod conține un cuvânt, vom avea frazele așezate într-o structură în care pur și simplu urmărirea de la rădăcină în jos, prin orice cale, dă o expresie de căutare validă.

Avantajul unui trie este că reduce semnificativ timpul de căutare. Pentru a fi mai ușor de înțeles în scopurile acestui tutorial de încercare, să ne imaginăm un arbore binar. Traversarea unui arbore binar are complexitatea lui O(log 2 n) , deoarece fiecare nod se ramifică în două, tăind traversarea rămasă la jumătate. Ca atare, un arbore ternar are complexitatea traversală a lui O(log 3 n) . Într-o încercare, totuși, numărul de noduri copii este dictat de secvența pe care o reprezintă, iar în cazul textului care poate fi citit/cu sens, numărul de copii este de obicei mare.

Algoritmul de căutare text

Ca exemplu simplu, să presupunem următoarele expresii de căutare:

• „aceeași familie”
• „alta familie”
• „existență separată”
• „membri ai ligii”

Amintiți-vă că știm dinainte expresiile noastre de căutare. Deci, începem prin a construi un index, sub forma unui trie:

Ulterior, utilizatorul software-ului nostru îl prezintă cu un fișier care conține următorul text:

Limbile europene sunt membre ale aceleiași familii. Existența lor separată este un mit.

Restul este destul de simplu. Algoritmul nostru va avea doi indicatori (indicatori, dacă doriți), unul care începe de la rădăcină sau nodul „start” din structura noastră trie, iar celălalt de la primul cuvânt din corpul textului. Cei doi indicatori se deplasează împreună, cuvânt cu cuvânt. Indicatorul de text pur și simplu se deplasează înainte, în timp ce indicatorul de încercare parcurge încercarea în profunzime, urmând o urmă de cuvinte care se potrivesc.

Indicatorul de încercare revine să înceapă în două cazuri: când ajunge la sfârșitul unei ramuri, ceea ce înseamnă că a fost găsită o expresie de căutare sau când întâlnește un cuvânt care nu se potrivește, caz în care nu a fost găsită nicio potrivire.

O excepție de la mișcarea indicatorului de text este atunci când se găsește o potrivire parțială, adică după o serie de potriviri se întâlnește o nepotrivire înainte ca ramura să se încheie. În acest caz, indicatorul text nu este mutat înainte, deoarece ultimul cuvânt ar putea fi începutul unei noi ramuri.

Să aplicăm acest algoritm exemplului nostru de structură de date trie și să vedem cum merge:

După cum putem vedea, sistemul găsește cu succes cele două expresii care se potrivesc, „aceeași familie” și „existență separată” .

Exemplu din lumea reală

Pentru un proiect recent, mi s-a pus următoarea problemă: o clientă are un număr mare de articole și teze de doctorat legate de domeniul său de activitate și și-a generat propria listă de fraze reprezentând titluri și reguli specifice referitoare la același domeniu de activitate. muncă.

Dilema ei a fost aceasta: având în vedere lista ei de fraze, cum leagă articolele/tezele de acele fraze? Scopul final este de a putea alege la întâmplare un grup de fraze și de a avea imediat o listă de articole/teze care menționează acele fraze particulare, gata de a fi luate.

După cum sa discutat anterior, există două părți pentru a rezolva această problemă: indexarea frazelor într-un trie și căutarea reală. Următoarele secțiuni oferă o implementare simplă în C#. Vă rugăm să rețineți că gestionarea fișierelor, problemele de codificare, curățarea textului și probleme similare nu sunt tratate în aceste fragmente, deoarece nu intră în domeniul de aplicare al acestui articol.

Indexarea

Operația de indexare parcurge pur și simplu frazele una câte una și le inserează în trie, un cuvânt pe nod/nivel. Nodurile sunt reprezentate cu următoarea clasă:

 class Node { int PhraseId = -1; Dictionary<String, Node> Children = new Dictionary<String, Node>(); public Node() { } public Node(int id) { PhraseId = id; } }

Fiecare frază este reprezentată printr-un ID, care poate fi la fel de simplu ca un număr incremental și transmisă următoarei funcții de indexare (rădăcina variabilă este rădăcina reală a trie):

 void addPhrase(ref Node root, String phrase, int phraseId) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // break phrase into words String[] words = phrase.Split (); // start traversal at root for (int i = 0; i < words.Length; ++i) { // if the current word does not exist as a child // to current node, add it if (node.Children.ContainsKey(words[i]) == false) node.Children.Add(words[i], new Node()); // move traversal pointer to current word node = node.Children[words[i]]; // if current word is the last one, mark it with // phrase Id if (i == words.Length - 1) node.PhraseId = phraseId; } }

In cautarea

Procesul de căutare este o implementare directă a algoritmului trie discutat în tutorialul de mai sus:

 void findPhrases(ref Node root, String textBody) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // a list of found ids List<int> foundPhrases = new List<int>(); // break text body into words String[] words = textBody.Split (); // starting traversal at trie root and first // word in text body for (int i = 0; i < words.Length;) { // if current node has current word as a child // move both node and words pointer forward if (node.Children.ContainsKey(words[i])) { // move trie pointer forward node = node.Children[words[i]]; // move words pointer forward ++i; } else { // current node does not have current // word in its children // if there is a phrase Id, then the previous // sequence of words matched a phrase, add Id to // found list if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); if (node == root) { // if trie pointer is already at root, increment // words pointer ++i; } else { // if not, leave words pointer at current word // and return trie pointer to root node = root; } } } // one case remains, word pointer as reached the end // and the loop is over but the trie pointer is pointing to // a phrase Id if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); }

Performanţă

Codul prezentat aici este extras din proiectul propriu-zis și a fost simplificat în scopul acestui document. Rularea acestui cod din nou pe aceeași mașină [1] și pe același eșantion de testare [2] a dus la un timp de rulare de 2,5 secunde pentru construirea testului și 0,3 secunde pentru căutare. Atât pentru pauză, nu?

Variante

Este important să recunoaștem că algoritmul descris în acest tutorial de încercare poate eșua în anumite cazuri marginale și, prin urmare, este conceput cu termeni de căutare predefiniti deja în minte.

De exemplu, dacă începutul unui termen de căutare este identic cu o parte a altui termen de căutare, ca în:

• „ de împărtășit și să te bucuri cu prietenii”
• „Am două bilete de împărțit cu cineva”

iar corpul textului conține o frază care face ca indicatorul trie să pornească pe calea greșită, cum ar fi:

Am două bilete de împărțit și de bucurat cu prietenii.

atunci algoritmul nu va reuși să se potrivească cu niciun termen, deoarece indicatorul trie nu se va întoarce la nodul de început până când indicatorul de text nu a trecut deja de începutul termenului de potrivire în corpul textului.

Este important să luați în considerare dacă acest tip de caz marginal este o posibilitate pentru aplicația dvs. înainte de a implementa algoritmul. Dacă da, algoritmul poate fi modificat cu indicatori de încercare suplimentari pentru a urmări toate potrivirile la un moment dat, în loc de doar o potrivire la un moment dat.

Concluzie

Căutarea text este un domeniu profund în informatică; un domeniu bogat în probleme și soluții deopotrivă. Tipul de date cu care a trebuit să mă ocup (23 MB de text reprezintă o mulțime de cărți în viața reală) ar putea părea o întâmplare rară sau o problemă de specialitate, dar dezvoltatorii care lucrează cu cercetarea lingvistică, arhivarea sau orice alt tip de manipulare a datelor , întâlniți în mod regulat cantități mult mai mari de date.

După cum este evident în tutorialul trie structura de date de mai sus, este de mare importanță să alegeți cu atenție algoritmul corect pentru problema în cauză. În acest caz particular, abordarea trie a redus timpul de rulare cu 99,93%, de la peste o oră la mai puțin de 3 secunde.

În niciun caz, aceasta nu este singura abordare eficientă, dar este destul de simplă și funcționează. Sper că ați găsit acest algoritm interesant și vă doresc mult succes în eforturile de codare.

[1] Aparatul folosit pentru acest test are următoarele specificații:

• Intel i7 4700HQ
• 16 GB RAM

Testarea a fost făcută pe Windows 8.1 folosind .NET 4.5.1 și, de asemenea, Kubuntu 14.04 folosind cea mai recentă versiune de mono și rezultatele au fost foarte asemănătoare.

[2] Eșantionul de testare constă din 280.000 de expresii de căutare cu o dimensiune totală de 23,5 MB și un corp de text de 1,5 MB.