Igła w stogu siana: fajny samouczek dotyczący algorytmu wyszukiwania tekstu na dużą skalę

Gdy napotykamy termin „wyszukiwanie tekstowe”, zwykle myśli się o dużej części tekstu, która jest indeksowana w sposób, który umożliwia szybkie wyszukanie jednego lub więcej wyszukiwanych haseł, gdy zostaną one wprowadzone przez użytkownika. To klasyczny problem dla informatyków, na który istnieje wiele rozwiązań.

Ale co powiesz na odwrotny scenariusz? Co zrobić, jeśli to, co jest dostępne do zaindeksowania wcześniej, to grupa wyszukiwanych fraz i tylko w czasie wykonywania jest wyświetlany duży tekst do wyszukiwania? Te pytania są tym, co próbuje rozwiązać ten samouczek dotyczący struktury danych próbnych.

Aplikacje

Prawdziwym zastosowaniem tego scenariusza jest zestawienie szeregu prac medycznych z listą schorzeń i ustalenie, które tezy omawiają które schorzenia. Innym przykładem jest przeglądanie dużej kolekcji precedensów sądowych i wydobywanie praw, do których się odnoszą.

Bezpośrednie podejście

Najbardziej podstawowym podejściem jest zapętlenie wyszukiwanych fraz i przeszukiwanie tekstu każdej frazy, jedna po drugiej. To podejście nie jest dobrze skalowane. Wyszukiwanie ciągu wewnątrz innego ma złożoność O(n) . Powtórzenie tego dla m fraz wyszukiwania prowadzi do okropnego O(m * n) .

(prawdopodobnie jedyna) zaleta bezpośredniego podejścia, którą można łatwo zaimplementować, jak widać w następującym fragmencie 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;

Uruchamiając ten kod na moim komputerze deweloperskim [1] z próbką testową [2], uzyskałem czas działania wynoszący 1 godzinę 14 minut – znacznie więcej niż czas potrzebny na napicie się kawy, wstawanie i rozciąganie się lub jakąkolwiek inną wymówkę programiści używają do pomijania pracy.

Lepsze podejście — Trie

Poprzedni scenariusz można ulepszyć na kilka sposobów. Na przykład proces wyszukiwania może być podzielony na partycje i zrównoleglony na wielu procesorach/rdzeniach. Jednak skrócenie czasu pracy osiągnięte dzięki temu podejściu (całkowity czas pracy wynoszący 20 minut przy założeniu idealnego podziału na 4 procesory/rdzeni) nie uzasadnia dodatkowej złożoności kodowania/debugowania.

Najlepszym możliwym rozwiązaniem byłoby takie, które przemierza treść tekstu tylko raz. Wymaga to indeksowania wyszukiwanych fraz w strukturze, która może być przesuwana liniowo, równolegle z treścią tekstu, w jednym przejściu, osiągając końcową złożoność O(n) .

Strukturą danych, która jest szczególnie odpowiednia tylko w tym scenariuszu, jest trie . Ta wszechstronna struktura danych jest zwykle pomijana i nie jest tak znana, jak inne struktury związane z drzewami, jeśli chodzi o problemy z wyszukiwaniem.

Poprzedni samouczek Toptal na temat prób stanowi doskonałe wprowadzenie do ich struktury i użycia. Krótko mówiąc, trie to specjalne drzewo, zdolne do przechowywania sekwencji wartości w taki sposób, że śledzenie ścieżki od korzenia do dowolnego węzła daje prawidłowy podzbiór tej sekwencji.

Tak więc, jeśli uda nam się połączyć wszystkie wyszukiwane frazy w jedną próbę, w której każdy węzeł zawiera słowo, otrzymamy frazy ułożone w strukturze, w której proste śledzenie od korzenia w dół, dowolną ścieżką, da prawidłową wyszukiwaną frazę.

Zaletą próby jest znaczne skrócenie czasu wyszukiwania. Aby ułatwić zrozumienie na potrzeby tego samouczka, wyobraźmy sobie drzewo binarne. Przechodzenie przez drzewo binarne ma złożoność O(log 2 n) , ponieważ każdy węzeł rozgałęzia się na dwa, przecinając pozostałe przejście na pół. Jako takie, drzewo trójskładnikowe ma złożoność przechodzenia O(log 3 n) . W jednym przypadku liczba węzłów potomnych jest jednak podyktowana sekwencją, którą reprezentuje, a w przypadku tekstu czytelnego/sensownego liczba potomków jest zwykle wysoka.

Algorytm wyszukiwania tekstu

Jako prosty przykład przyjmijmy następujące wyszukiwane frazy:

• „ta sama rodzina”
• „inna rodzina”
• „oddzielna egzystencja”
• „członkowie ligi”

Pamiętaj, że wcześniej znamy nasze wyszukiwane frazy. Tak więc zaczynamy od zbudowania indeksu w postaci tria:

Później użytkownik naszego oprogramowania przedstawia mu plik zawierający następujący tekst:

Języki europejskie należą do tej samej rodziny. Ich oddzielne istnienie to mit.

Reszta jest dość prosta. Nasz algorytm będzie miał dwa wskaźniki (wskaźniki, jeśli chcesz), jeden zaczynający się od korzenia lub węzła „początkowego” w naszej strukturze trie, a drugi od pierwszego słowa w treści tekstu. Oba wskaźniki poruszają się razem, słowo po słowie. Wskaźnik tekstowy po prostu przesuwa się do przodu, podczas gdy wskaźnik trie przesuwa się w głąb tria, podążając śladem pasujących słów.

Wskaźnik trie powraca do początku w dwóch przypadkach: Gdy dojdzie do końca gałęzi, co oznacza, że ​​wyszukiwana fraza została znaleziona, lub gdy napotka niepasujące słowo, w którym to przypadku nie znaleziono dopasowania.

Jedynym wyjątkiem od ruchu wskaźnika tekstowego jest znalezienie częściowego dopasowania, tj. po serii dopasowań, przed zakończeniem gałęzi, napotkano niedopasowanie. W tym przypadku wskaźnik tekstowy nie jest przesuwany do przodu, ponieważ ostatnie słowo może być początkiem nowej gałęzi.

Zastosujmy ten algorytm do naszego przykładowego przykładu struktury danych i zobaczmy, jak to działa:

Jak widać, system z powodzeniem odnajduje dwie pasujące frazy, „ta sama rodzina” i „oddzielna egzystencja” .

Przykład ze świata rzeczywistego

W przypadku niedawnego projektu postawiono mi następujący problem: klientka ma dużą liczbę artykułów i prac doktorskich związanych z jej dziedziną pracy i wygenerowała własną listę fraz reprezentujących określone tytuły i zasady odnoszące się do tej samej dziedziny Praca.

Jej dylemat był następujący: biorąc pod uwagę jej listę fraz, w jaki sposób łączy artykuły/tezy z tymi frazami? Ostatecznym celem jest możliwość losowego wybrania grupy fraz i natychmiastowego przygotowania listy artykułów/tez, które wspominają o tych konkretnych frazach.

Jak omówiono wcześniej, rozwiązanie tego problemu składa się z dwóch części: indeksowania fraz do trii i rzeczywistego wyszukiwania. Poniższe sekcje zawierają prostą implementację w języku C#. Pamiętaj, że te fragmenty nie obejmują obsługi plików, problemów z kodowaniem, czyszczeniem tekstu i podobnymi problemami, ponieważ nie są one objęte zakresem tego artykułu.

Indeksowanie

Operacja indeksowania po prostu przemierza frazy jedna po drugiej i wstawia je do trójki, po jednym słowie na węzeł/poziom. Węzły są reprezentowane przez następującą klasę:

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

Każda fraza jest reprezentowana przez identyfikator, który może być tak prosty, jak liczba inkrementalna, i jest przekazywany do następującej funkcji indeksującej (pierwiastek zmiennej jest rzeczywistym pierwiastkiem tria):

 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; } }

Badawczy

Proces wyszukiwania jest bezpośrednią implementacją algorytmu trie omówionego w powyższym samouczku:

 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); }

Występ

Przedstawiony tutaj kod został wyodrębniony z rzeczywistego projektu i został uproszczony na potrzeby tego dokumentu. Ponowne uruchomienie tego kodu na tym samym komputerze [1] i na tej samej próbce testowej [2] skutkowało czasem wykonywania 2,5 sekundy na zbudowanie trii i 0,3 sekundy na wyszukiwanie. Tyle czasu na przerwę, co?

Wariacje

Należy pamiętać, że algorytm opisany w tym samouczku próbnym może zawieść w niektórych skrajnych przypadkach i dlatego został zaprojektowany z myślą o predefiniowanych terminach wyszukiwania.

Na przykład, jeśli początek jednego wyszukiwanego hasła jest identyczny z częścią innego wyszukiwanego hasła, jak w:

• “ dzielić się i cieszyć z przyjaciółmi”
• „Mam dwa bilety do podzielenia się z kimś”

a treść tekstu zawiera frazę, która powoduje, że wskaźnik tria zaczyna podążać niewłaściwą ścieżką, na przykład:

Mam dwa bilety, którymi mogę się podzielić z przyjaciółmi.

wtedy algorytm nie dopasuje żadnego terminu, ponieważ wskaźnik trie nie powróci do węzła początkowego, dopóki wskaźnik tekstowy nie minie już początku pasującego terminu w treści tekstu.

Ważne jest, aby zastanowić się, czy tego rodzaju przypadek brzegowy jest możliwy dla Twojej aplikacji przed wdrożeniem algorytmu. Jeśli tak, algorytm można zmodyfikować za pomocą dodatkowych wskaźników prób, aby śledzić wszystkie mecze w danym momencie, zamiast tylko jednego meczu na raz.

Wniosek

Wyszukiwanie tekstu to głęboka dziedzina informatyki; polem bogatym w problemy i rozwiązania. Rodzaj danych, z którymi miałem do czynienia (23 MB tekstu to mnóstwo książek w prawdziwym życiu) może wydawać się rzadkim zjawiskiem lub wyspecjalizowanym problemem, ale programiści zajmujący się badaniami językowymi, archiwizacją lub innymi rodzajami manipulacji danymi regularnie trafiają na znacznie większe ilości danych.

Jak widać w powyższym samouczku dotyczącym struktury danych, bardzo ważne jest, aby starannie wybrać odpowiedni algorytm dla danego problemu. W tym konkretnym przypadku podejście triowe skróciło czas pracy o oszałamiające 99,93%, z ponad godziny do mniej niż 3 sekund.

W żadnym wypadku nie jest to jedyne skuteczne podejście, ale jest dość proste i działa. Mam nadzieję, że ten algorytm okazał się interesujący i życzę powodzenia w programowaniu.

[1] Maszyna użyta do tego testu ma następujące specyfikacje:

• Intel i7 4700HQ
• 16 GB pamięci RAM

Testy przeprowadzono na Windows 8.1 przy użyciu .NET 4.5.1, a także Kubuntu 14.04 przy użyciu najnowszej wersji mono, a wyniki były bardzo podobne.

[2] Próbka testowa składa się z 280 tys. wyszukiwanych fraz o łącznej wielkości 23,5 MB i treści tekstowej 1,5 MB.