Ago in un pagliaio: un elegante tutorial sull'algoritmo di ricerca di testo su larga scala

Quando ci si imbatte nel termine "ricerca testuale", di solito si pensa a un ampio corpo di testo che viene indicizzato in modo da rendere possibile la ricerca rapida di uno o più termini di ricerca quando vengono inseriti da un utente. Questo è un classico problema per gli informatici, a cui esistono molte soluzioni.

Ma che ne dici di uno scenario inverso? Cosa succede se ciò che è disponibile per l'indicizzazione in anticipo è un gruppo di frasi di ricerca e solo in fase di esecuzione viene presentato un ampio corpo di testo per la ricerca? Queste domande sono ciò che questo tutorial sulla struttura dei dati di prova cerca di affrontare.

Applicazioni

Un'applicazione nel mondo reale per questo scenario è confrontare un certo numero di tesi mediche con un elenco di condizioni mediche e scoprire quali tesi discutono di quali condizioni. Un altro esempio è attraversare un'ampia raccolta di precedenti giudiziari ed estrarre le leggi a cui fanno riferimento.

Approccio diretto

L'approccio più semplice è quello di scorrere le frasi di ricerca e cercare nel testo ogni frase, una per una. Questo approccio non si adatta bene. La ricerca di una stringa all'interno di un'altra ha la complessità O(n) . Ripetere che per m frasi di ricerca porta al terribile O(m * n) .

Il (probabilmente unico) vantaggio di un approccio diretto che è semplice da implementare, come risulta dal frammento di codice C# seguente:

 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;

Eseguendo questo codice sulla mia macchina di sviluppo [1] rispetto a un campione di prova [2], ho ottenuto un'autonomia di 1 ora e 14 minuti, ben oltre il tempo necessario per prendere una tazza di caffè, alzarsi e sgranchirsi o qualsiasi altra scusa gli sviluppatori usano per saltare il lavoro.

Un approccio migliore: il tentativo

Lo scenario precedente può essere migliorato in un paio di modi. Ad esempio, il processo di ricerca può essere partizionato e parallelizzato su più processori/core. Ma la riduzione del tempo di esecuzione ottenuto da questo approccio (tempo di esecuzione totale di 20 minuti supponendo una perfetta divisione su 4 processori/core) non giustifica la complessità aggiunta alla codifica/debug.

La migliore soluzione possibile sarebbe quella che attraversa il corpo del testo solo una volta. Ciò richiede che le frasi di ricerca siano indicizzate in una struttura che può essere trascorsa linearmente, parallelamente al corpo del testo, in un passaggio, ottenendo una complessità finale di O(n) .

Una struttura dati particolarmente adatta proprio per questo scenario è il trie . Questa struttura di dati versatile è solitamente trascurata e non famosa come altre strutture legate agli alberi quando si tratta di problemi di ricerca.

Il precedente tutorial di Toptal sui tentativi fornisce un'eccellente introduzione a come sono strutturati e utilizzati. In breve, un trie è un albero speciale, in grado di memorizzare una sequenza di valori in modo tale che tracciare il percorso dalla radice a qualsiasi nodo produca un valido sottoinsieme di quella sequenza.

Quindi, se riusciamo a combinare tutte le frasi di ricerca in un trie, in cui ogni nodo contiene una parola, avremo le frasi disposte in una struttura in cui il semplice tracciamento dalla radice verso il basso, tramite qualsiasi percorso, produce una frase di ricerca valida.

Il vantaggio di un tentativo è che riduce notevolmente i tempi di ricerca. Per semplificare la comprensione ai fini di questo tutorial di prova, immaginiamo un albero binario. L'attraversamento di un albero binario ha la complessità di O(log 2 n) , poiché ogni nodo si dirama in due, tagliando a metà l'attraversamento rimanente. Come tale, un albero ternario ha la complessità trasversale di O(log 3 n) . In un trie, tuttavia, il numero di nodi figli è dettato dalla sequenza che rappresenta e, nel caso di testo leggibile/significativo, il numero di figli è generalmente elevato.

Algoritmo di ricerca del testo

Come semplice esempio, assumiamo le seguenti frasi di ricerca:

• “stessa famiglia”
• “famiglia diversa”
• “esistenza separata”
• “membri della lega”

Ricorda che conosciamo in anticipo le nostre frasi di ricerca. Quindi, iniziamo costruendo un indice, sotto forma di un trie:

Successivamente, l'utente del nostro software lo presenta con un file contenente il seguente testo:

Le lingue europee sono membri della stessa famiglia. La loro esistenza separata è un mito.

Il resto è abbastanza semplice. Il nostro algoritmo avrà due indicatori (puntatori, se lo desideri), uno che inizia alla radice, o nodo "inizio" nella nostra struttura trie, e l'altro alla prima parola nel corpo del testo. I due indicatori si muovono insieme, parola per parola. L'indicatore di testo si sposta semplicemente in avanti, mentre l'indicatore di trie attraversa il trie in profondità, seguendo una scia di parole corrispondenti.

L'indicatore trie torna a iniziare in due casi: quando raggiunge la fine di un ramo, il che significa che è stata trovata una frase di ricerca, o quando incontra una parola non corrispondente, nel qual caso non è stata trovata alcuna corrispondenza.

Un'eccezione al movimento dell'indicatore di testo è quando viene trovata una corrispondenza parziale, cioè dopo una serie di corrispondenze si verifica una mancata corrispondenza prima che il ramo termini. In questo caso l'indicatore di testo non viene spostato in avanti, poiché l'ultima parola potrebbe essere l'inizio di un nuovo ramo.

Applichiamo questo algoritmo al nostro esempio di struttura dati di prova e vediamo come va:

Come possiamo vedere, il sistema trova con successo le due frasi corrispondenti, “stessa famiglia” ed “esistenza separata” .

Esempio del mondo reale

Per un progetto recente, mi è stato presentato il seguente problema: una cliente ha un gran numero di articoli e tesi di dottorato relativi al suo campo di lavoro, e ha generato un proprio elenco di frasi che rappresentano titoli e regole specifici relativi allo stesso campo di lavoro lavoro.

Il suo dilemma era questo: data la sua lista di frasi, come collega gli articoli/tesi a quelle frasi? L'obiettivo finale è essere in grado di scegliere casualmente un gruppo di frasi e avere immediatamente un elenco di articoli/tesi che menzionano quelle frasi particolari pronte per essere afferrate.

Come discusso in precedenza, ci sono due parti per risolvere questo problema: l'indicizzazione delle frasi in un trie e la ricerca vera e propria. Le sezioni seguenti forniscono una semplice implementazione in C#. Tieni presente che la gestione dei file, i problemi di codifica, la pulizia del testo e problemi simili non vengono gestiti in questi frammenti, poiché non rientrano nell'ambito di questo articolo.

Indicizzazione

L'operazione di indicizzazione attraversa semplicemente le frasi una per una e le inserisce nel trie, una parola per nodo/livello. I nodi sono rappresentati con la seguente classe:

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

Ogni frase è rappresentata da un ID, che può essere semplice come un numero incrementale, e passato alla seguente funzione di indicizzazione (la radice della variabile è la radice effettiva del 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; } }

Ricerca

Il processo di ricerca è un'implementazione diretta dell'algoritmo trie discusso nel tutorial sopra:

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

Prestazione

Il codice qui presentato è estratto dal progetto vero e proprio ed è stato semplificato ai fini del presente documento. L'esecuzione di questo codice nuovamente sulla stessa macchina [1] e sullo stesso campione di prova [2] ha comportato un tempo di esecuzione di 2,5 secondi per la creazione del trie e di 0,3 secondi per la ricerca. Tanto per la pausa, eh?

Variazioni

È importante riconoscere che l'algoritmo descritto in questo tutorial di prova può non riuscire in alcuni casi limite e pertanto è progettato tenendo già presenti i termini di ricerca predefiniti.

Ad esempio, se l'inizio di un termine di ricerca è identico a una parte di un altro termine di ricerca, come in:

• “ da condividere e divertirsi con gli amici”
• “Ho due biglietti da condividere con qualcuno”

e il corpo del testo contiene una frase che fa sì che il puntatore trie inizi lungo il percorso sbagliato, ad esempio:

Ho due biglietti da condividere e divertirmi con gli amici.

quindi l'algoritmo non riuscirà a trovare la corrispondenza con nessun termine, perché l'indicatore trie non tornerà al nodo iniziale finché l'indicatore di testo non avrà già superato l'inizio del termine corrispondente nel corpo del testo.

È importante considerare se questo tipo di caso limite è una possibilità per la tua applicazione prima di implementare l'algoritmo. In tal caso, l'algoritmo può essere modificato con indicatori trie aggiuntivi per tenere traccia di tutte le corrispondenze in un dato momento, invece di una sola corrispondenza alla volta.

Conclusione

La ricerca di testo è un campo profondo nell'informatica; un campo ricco di problemi e soluzioni allo stesso modo. Il tipo di dati con cui ho avuto a che fare (23 MB di testo sono un sacco di libri nella vita reale) potrebbe sembrare un evento raro o un problema specializzato, ma gli sviluppatori che lavorano con la ricerca linguistica, l'archiviazione o qualsiasi altro tipo di manipolazione dei dati , imbattersi regolarmente in quantità molto maggiori di dati.

Come è evidente nel tutorial sulla struttura dei dati trie sopra, è di grande importanza scegliere con cura l'algoritmo corretto per il problema in questione. In questo caso particolare, l'approccio trie ha ridotto il tempo di esecuzione di uno sbalorditivo 99,93%, da oltre un'ora a meno di 3 secondi.

Non è affatto questo l'unico approccio efficace là fuori, ma è abbastanza semplice e funziona. Spero che tu abbia trovato questo algoritmo interessante e ti auguro buona fortuna per i tuoi sforzi di programmazione.

[1] La macchina utilizzata per questo test ha le seguenti specifiche:

• Intel i7 4700HQ
• 16 GB di RAM

Il test è stato eseguito su Windows 8.1 utilizzando .NET 4.5.1 e anche Kubuntu 14.04 utilizzando l'ultima versione di mono ei risultati sono stati molto simili.

[2] Il campione di prova è costituito da 280.000 frasi di ricerca con una dimensione totale di 23,5 MB e un corpo di testo di 1,5 MB.