Aguja en un pajar: un ingenioso algoritmo de búsqueda de texto a gran escala Tutorial

Cuando se encuentra con el término "búsqueda de texto", generalmente se piensa en una gran cantidad de texto que está indexado de una manera que permite buscar rápidamente uno o más términos de búsqueda cuando los ingresa un usuario. Este es un problema clásico para los informáticos, para el que existen muchas soluciones.

Pero, ¿qué tal un escenario inverso? ¿Qué pasa si lo que está disponible para la indexación de antemano es un grupo de frases de búsqueda, y solo en el tiempo de ejecución se presenta una gran cantidad de texto para la búsqueda? Estas preguntas son las que este tutorial de estructura de datos trie busca abordar.

Aplicaciones

Una aplicación del mundo real para este escenario es hacer coincidir una serie de tesis médicas con una lista de condiciones médicas y descubrir qué tesis discuten qué condiciones. Otro ejemplo es recorrer una gran colección de precedentes judiciales y extraer las leyes a las que hacen referencia.

Acercamiento directo

El enfoque más básico es recorrer las frases de búsqueda y buscar en el texto cada frase, una por una. Este enfoque no escala bien. Buscar una cadena dentro de otra tiene la complejidad O(n) . Repetir eso para m frases de búsqueda conduce a la terrible O(m * n) .

La (probablemente única) ventaja de un enfoque directo que es simple de implementar, como se ve en el siguiente fragmento 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;

Ejecutando este código en mi máquina de desarrollo [1] contra una muestra de prueba [2], obtuve un tiempo de ejecución de 1 hora y 14 minutos, mucho más allá del tiempo que necesita para tomar una taza de café, levantarse y estirarse, o cualquier otra excusa. los desarrolladores usan para saltarse el trabajo.

Un mejor enfoque - El Trie

El escenario anterior se puede mejorar de un par de maneras. Por ejemplo, el proceso de búsqueda se puede particionar y paralelizar en múltiples procesadores/núcleos. Pero la reducción en el tiempo de ejecución logrado por este enfoque (tiempo de ejecución total de 20 minutos suponiendo una división perfecta entre 4 procesadores/núcleos) no justifica la complejidad añadida a la codificación/depuración.

La mejor solución posible sería una que atraviese el cuerpo del texto solo una vez. Esto requiere que las frases de búsqueda se indexen en una estructura que se pueda atravesar linealmente, en paralelo con el cuerpo del texto, en una sola pasada, logrando una complejidad final de O(n) .

Una estructura de datos especialmente adecuada para este escenario es la trie . Esta estructura de datos versátil generalmente se pasa por alto y no es tan famosa como otras estructuras relacionadas con árboles cuando se trata de problemas de búsqueda.

El tutorial anterior de Toptal sobre intentos proporciona una excelente introducción a cómo se estructuran y utilizan. En resumen, un trie es un árbol especial, capaz de almacenar una secuencia de valores de tal manera que rastrear la ruta desde la raíz hasta cualquier nodo produce un subconjunto válido de esa secuencia.

Entonces, si podemos combinar todas las frases de búsqueda en un solo intento, donde cada nodo contiene una palabra, tendremos las frases dispuestas en una estructura en la que simplemente rastrear desde la raíz hacia abajo, a través de cualquier ruta, produce una frase de búsqueda válida.

La ventaja de un trie es que reduce significativamente el tiempo de búsqueda. Para que sea más fácil de comprender a los efectos de este tutorial de prueba, imaginemos un árbol binario. Atravesar un árbol binario tiene la complejidad de O(log 2 n) , ya que cada nodo se ramifica en dos, cortando el recorrido restante a la mitad. Como tal, un árbol ternario tiene la complejidad transversal de O(log 3 n) . En un trie, sin embargo, el número de nodos secundarios viene dictado por la secuencia que representa y, en el caso de texto legible/significativo, el número de elementos secundarios suele ser alto.

Algoritmo de búsqueda de texto

Como ejemplo simple, supongamos las siguientes frases de búsqueda:

• "la misma familia"
• “familia diferente”
• “existencia separada”
• "miembros de la liga"

Recuerda que conocemos nuestras frases de búsqueda de antemano. Entonces, comenzamos construyendo un índice, en forma de trie:

Posteriormente, el usuario de nuestro software le presenta un archivo que contiene el siguiente texto:

Las lenguas europeas son miembros de la misma familia. Su existencia separada es un mito.

El resto es bastante simple. Nuestro algoritmo tendrá dos indicadores (punteros, si lo desea), uno que comienza en la raíz o el nodo de "inicio" en nuestra estructura trie, y el otro en la primera palabra del cuerpo del texto. Los dos indicadores se mueven juntos, palabra por palabra. El indicador de texto simplemente se mueve hacia adelante, mientras que el indicador trie atraviesa el trie en profundidad, siguiendo un rastro de palabras coincidentes.

El indicador trie vuelve a empezar en dos casos: cuando llega al final de una rama, lo que significa que se ha encontrado una frase de búsqueda, o cuando encuentra una palabra que no coincide, en cuyo caso no se ha encontrado ninguna coincidencia.

Una excepción al movimiento del indicador de texto es cuando se encuentra una coincidencia parcial, es decir, después de una serie de coincidencias, se encuentra una no coincidencia antes de que finalice la bifurcación. En este caso, el indicador de texto no avanza, ya que la última palabra podría ser el comienzo de una nueva rama.

Apliquemos este algoritmo a nuestro ejemplo de estructura de datos trie y veamos cómo funciona:

Como podemos ver, el sistema encuentra con éxito las dos frases coincidentes, "misma familia" y "existencia separada" .

Ejemplo del mundo real

Para un proyecto reciente, se me presentó el siguiente problema: un cliente tiene una gran cantidad de artículos y tesis doctorales relacionadas con su campo de trabajo y ha generado su propia lista de frases que representan títulos y reglas específicas relacionadas con el mismo campo de trabajo. trabajo.

Su dilema era este: dada su lista de frases, ¿cómo vincula los artículos/tesis a esas frases? El objetivo final es poder elegir aleatoriamente un grupo de frases e inmediatamente tener una lista de artículos/tesis que mencionen esas frases en particular listas para agarrar.

Como se discutió anteriormente, hay dos partes para resolver este problema: indexar las frases en un trie y la búsqueda real. Las siguientes secciones proporcionan una implementación simple en C#. Tenga en cuenta que el manejo de archivos, los problemas de codificación, la limpieza de texto y problemas similares no se tratan en estos fragmentos, ya que están fuera del alcance de este artículo.

Indexación

La operación de indexación simplemente atraviesa frases una por una y las inserta en el trie, una palabra por nodo/nivel. Los nodos se representan con la siguiente clase:

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

Cada frase está representada por un ID, que puede ser tan simple como un número incremental, y se pasa a la siguiente función de indexación (la raíz variable es la raíz real 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; } }

buscando

El proceso de búsqueda es una implementación directa del algoritmo trie discutido en el tutorial anterior:

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

Rendimiento

El código que se presenta aquí se extrajo del proyecto real y se ha simplificado para los fines de este documento. Ejecutar este código nuevamente en la misma máquina [1] y contra la misma muestra de prueba [2] resultó en un tiempo de ejecución de 2,5 segundos para construir el trie y 0,3 segundos para la búsqueda. Tanto para el tiempo de descanso, ¿eh?

variaciones

Es importante reconocer que el algoritmo que se describe en este tutorial de prueba puede fallar en ciertos casos extremos y, por lo tanto, está diseñado con términos de búsqueda predefinidos ya en mente.

Por ejemplo, si el comienzo de un término de búsqueda es idéntico a alguna parte de otro término de búsqueda, como en:

• “ para compartir y disfrutar con amigos”
• “Tengo dos entradas para compartir con alguien”

y el cuerpo del texto contiene una frase que hace que el puntero trie comience por el camino equivocado, como:

Tengo dos entradas para compartir y disfrutar con amigos.

entonces el algoritmo no podrá hacer coincidir ningún término, porque el indicador trie no volverá al nodo de inicio hasta que el indicador de texto ya haya pasado el comienzo del término coincidente en el cuerpo del texto.

Es importante considerar si este tipo de caso límite es una posibilidad para su aplicación antes de implementar el algoritmo. Si es así, el algoritmo se puede modificar con indicadores de prueba adicionales para rastrear todas las coincidencias en un momento dado, en lugar de solo una coincidencia a la vez.

Conclusión

La búsqueda de texto es un campo profundo de la informática; un campo rico en problemas y soluciones por igual. El tipo de datos con los que tuve que lidiar (23 MB de texto son una tonelada de libros en la vida real) puede parecer un hecho raro o un problema especializado, pero los desarrolladores que trabajan con investigación lingüística, archivado o cualquier otro tipo de manipulación de datos , se encuentran con cantidades mucho mayores de datos de forma regular.

Como es evidente en el tutorial de estructura de datos trie anterior, es de gran importancia elegir cuidadosamente el algoritmo correcto para el problema en cuestión. En este caso particular, el enfoque trie redujo el tiempo de ejecución en un asombroso 99,93 %, de más de una hora a menos de 3 segundos.

De ninguna manera es este el único enfoque efectivo que existe, pero es bastante simple y funciona. Espero que haya encontrado este algoritmo interesante y le deseo la mejor de las suertes en sus esfuerzos de codificación.

[1] La máquina utilizada para esta prueba tiene las siguientes especificaciones:

• Intel i7 4700HQ
• RAM de 16GB

Las pruebas se realizaron en Windows 8.1 usando .NET 4.5.1 y también en Kubuntu 14.04 usando la última versión de mono y los resultados fueron muy similares.

[2] La muestra de prueba consta de 280 000 frases de búsqueda con un tamaño total de 23,5 MB y un cuerpo de texto de 1,5 MB.