Agulha no palheiro: um tutorial bacana de algoritmo de pesquisa de texto em grande escala

Ao se deparar com o termo “pesquisa de texto”, geralmente se pensa em um grande corpo de texto indexado de forma a possibilitar a pesquisa rápida de um ou mais termos de pesquisa quando eles são inseridos por um usuário. Este é um problema clássico para cientistas da computação, para o qual existem muitas soluções.

Mas que tal um cenário inverso? E se o que estiver disponível para indexação de antemão for um grupo de frases de pesquisa e somente em tempo de execução for apresentado um grande corpo de texto para pesquisa? Essas questões são o que este tutorial de estrutura de dados tenta abordar.

Formulários

Uma aplicação do mundo real para esse cenário é comparar várias teses médicas com uma lista de condições médicas e descobrir quais teses discutem quais condições. Outro exemplo é percorrer uma grande coleção de precedentes judiciais e extrair as leis a que se referem.

Abordagem direta

A abordagem mais básica é percorrer as frases de pesquisa e pesquisar no texto cada frase, uma por uma. Essa abordagem não escala bem. Procurar uma string dentro de outra tem a complexidade O(n) . Repetir isso para m frases de pesquisa leva ao terrível O(m * n) .

A (provavelmente única) vantagem de uma abordagem direta que é simples de implementar, conforme aparente no seguinte trecho de 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;

Executando este código em minha máquina de desenvolvimento [1] em uma amostra de teste [2], obtive um tempo de execução de 1 hora e 14 minutos – muito além do tempo que você precisa para tomar uma xícara de café, levantar e se alongar ou qualquer outra desculpa desenvolvedores usam para pular o trabalho.

Uma Abordagem Melhor - A Tentativa

O cenário anterior pode ser aprimorado de duas maneiras. Por exemplo, o processo de pesquisa pode ser particionado e paralelizado em vários processadores/núcleos. Mas a redução no tempo de execução alcançada por esta abordagem (tempo de execução total de 20 minutos assumindo uma divisão perfeita em 4 processadores/núcleos) não justifica a complexidade adicional de codificação/depuração.

A melhor solução possível seria aquela que atravessasse o corpo do texto apenas uma vez. Isso exige que as frases de pesquisa sejam indexadas em uma estrutura que possa ser transposta linearmente, em paralelo com o corpo do texto, em uma passagem, atingindo uma complexidade final de O(n) .

Uma estrutura de dados especialmente adequada para esse cenário é o trie . Essa estrutura de dados versátil geralmente é negligenciada e não é tão famosa quanto outras estruturas relacionadas a árvores quando se trata de problemas de pesquisa.

O tutorial anterior de Toptal sobre tentativas fornece uma excelente introdução de como elas são estruturadas e usadas. Em suma, um trie é uma árvore especial, capaz de armazenar uma sequência de valores de tal forma que traçar o caminho da raiz para qualquer nó produz um subconjunto válido dessa sequência.

Portanto, se pudermos combinar todas as frases de pesquisa em uma tentativa, onde cada nó contém uma palavra, teremos as frases dispostas em uma estrutura onde o simples rastreamento da raiz para baixo, por qualquer caminho, produz uma frase de pesquisa válida.

A vantagem de um trie é que ele reduz significativamente o tempo de busca. Para facilitar a compreensão para os propósitos deste tutorial, vamos imaginar uma árvore binária. Atravessar uma árvore binária tem a complexidade de O(log 2 n) , uma vez que cada nó se ramifica em dois, cortando a travessia restante pela metade. Como tal, uma árvore ternária tem a complexidade transversal de O(log 3 n) . Em uma tentativa, no entanto, o número de nós filho é ditado pela sequência que está representando e, no caso de texto legível/significativo, o número de filhos geralmente é alto.

Algoritmo de pesquisa de texto

Como um exemplo simples, vamos supor as seguintes frases de pesquisa:

• “mesma família”
• “família diferente”
• “existência separada”
• “membros da liga”

Lembre-se de que conhecemos nossas frases de pesquisa de antemão. Então, começamos construindo um índice, na forma de um trie:

Posteriormente, o usuário do nosso software apresenta um arquivo contendo o seguinte texto:

As línguas europeias são membros da mesma família. Sua existência separada é um mito.

O resto é bem simples. Nosso algoritmo terá dois indicadores (ponteiros, se preferir), um começando na raiz, ou nó “inicial” em nossa estrutura trie, e outro na primeira palavra do corpo do texto. Os dois indicadores se movem juntos, palavra por palavra. O indicador de texto simplesmente avança, enquanto o indicador de trie percorre o trie em profundidade, seguindo uma trilha de palavras correspondentes.

O indicador trie volta a iniciar em dois casos: Quando atinge o final de um ramo, o que significa que uma frase de pesquisa foi encontrada, ou quando encontra uma palavra não correspondente, caso em que nenhuma correspondência foi encontrada.

Uma exceção ao movimento do indicador de texto é quando uma correspondência parcial é encontrada, ou seja, após uma série de correspondências, uma não correspondência é encontrada antes que a ramificação termine. Nesse caso, o indicador de texto não é movido para frente, pois a última palavra pode ser o início de uma nova ramificação.

Vamos aplicar este algoritmo ao nosso exemplo de estrutura de dados trie e ver como fica:

Como podemos ver, o sistema encontra com sucesso as duas frases correspondentes, “mesma família” e “existência separada” .

Exemplo do mundo real

Para um projeto recente, foi-me apresentado o seguinte problema: uma cliente possui um grande número de artigos e teses de doutorado relacionadas à sua área de trabalho e gerou sua própria lista de frases representando títulos específicos e regras relativas à mesma área de trabalhar.

Seu dilema era este: dada sua lista de frases, como ela vincula os artigos/teses a essas frases? O objetivo final é poder escolher aleatoriamente um grupo de frases e ter imediatamente uma lista de artigos/teses que mencionam essas frases em particular prontas para serem apreendidas.

Conforme discutido anteriormente, há duas partes para resolver esse problema: indexar as frases em um trie e a pesquisa real. As seções a seguir fornecem uma implementação simples em C#. Observe que o manuseio de arquivos, problemas de codificação, limpeza de texto e problemas semelhantes não são tratados nesses snippets, pois estão fora do escopo deste artigo.

Indexação

A operação de indexação simplesmente percorre as frases uma a uma e as insere no trie, uma palavra por nó/nível. Os nós são representados com a seguinte classe:

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

Cada frase é representada por um ID, que pode ser tão simples quanto um número incremental, e passado para a seguinte função de indexação (raiz da variável é a raiz real da 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; } }

Procurando

O processo de pesquisa é uma implementação direta do algoritmo trie discutido no tutorial acima:

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

atuação

O código aqui apresentado é extraído do projeto real e foi simplificado para os propósitos deste documento. A execução desse código novamente na mesma máquina [1] e na mesma amostra de teste [2] resultou em um tempo de execução de 2,5 segundos para a construção da tentativa e 0,3 segundos para a pesquisa. Tanto para o tempo de pausa, hein?

Variações

É importante reconhecer que o algoritmo descrito neste tutorial pode falhar em certos casos extremos e, portanto, foi projetado com termos de pesquisa predefinidos já em mente.

Por exemplo, se o início de um termo de pesquisa for idêntico a alguma parte de outro termo de pesquisa, como em:

• “ para compartilhar e curtir com os amigos”
• “Tenho dois bilhetes para partilhar com alguém”

e o corpo do texto contém uma frase que faz com que o ponteiro trie comece no caminho errado, como:

Tenho dois ingressos para compartilhar e curtir com os amigos.

então o algoritmo não corresponderá a nenhum termo, porque o indicador trie não retornará ao nó inicial até que o indicador de texto já tenha passado pelo início do termo correspondente no corpo do texto.

É importante considerar se esse tipo de caso extremo é uma possibilidade para seu aplicativo antes de implementar o algoritmo. Nesse caso, o algoritmo pode ser modificado com indicadores de teste adicionais para rastrear todas as correspondências a qualquer momento, em vez de apenas uma correspondência por vez.

Conclusão

A pesquisa de texto é um campo profundo da ciência da computação; um campo rico em problemas e soluções. O tipo de dados com os quais tive que lidar (23 MB de texto é uma tonelada de livros na vida real) pode parecer uma ocorrência rara ou um problema especializado, mas os desenvolvedores que trabalham com pesquisa linguística, arquivamento ou qualquer outro tipo de manipulação de dados , se deparam regularmente com quantidades muito maiores de dados.

Como é evidente no tutorial de estrutura de dados acima, é de grande importância escolher cuidadosamente o algoritmo correto para o problema em questão. Nesse caso em particular, a abordagem trie reduziu o tempo de execução em impressionantes 99,93%, de mais de uma hora para menos de 3 segundos.

De forma alguma essa é a única abordagem eficaz, mas é bastante simples e funciona. Espero que você tenha achado esse algoritmo interessante e desejo boa sorte em seus esforços de codificação.

[1] A máquina utilizada para este teste possui as seguintes especificações:

• Intel i7 4700HQ
• 16 GB de RAM

Os testes foram feitos no Windows 8.1 usando .NET 4.5.1 e também no Kubuntu 14.04 usando a versão mais recente do mono e os resultados foram muito semelhantes.

[2] A amostra de teste consiste em 280 mil frases de pesquisa com um tamanho total de 23,5 MB e um corpo de texto de 1,5 MB.