Sugerencia del algoritmo de subcadena

Question

Tengo un conjunto grande (100k) de cadenas cortas (no más de 100 caracteres) y necesito encontrar rápidamente a todos aquellos que tienen una cierta subcadena.

Esto se usará como un cuadro de búsqueda donde el usuario comienza a escribir y el sistema inmediatamente da "sugerencias" (las cadenas que tienen como subcadena el texto que el usuario tipeó). Algo similar al cuadro "Etiqueta" en StackOverflow.

Como esto será interactivo, debería ser bastante rápido. ¿Qué algoritmo o estructura de datos recomiendas para esto?

Por cierto, voy a estar utilizando Delphi 2007.

Gracias de antemano.

Answer 1

Escribí una larga reseña, haciendo un montón de cálculos de complejidad y chistes xzibit (árbol en un árbol para que pueda buscar cuando lo busque), pero luego me di cuenta de que esto es más fácil de lo que pensaba. Los navegadores hacen esto todo el tiempo y nunca calculan previamente las tablas grandes cada vez que carga una página.

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

lo que significa es que tome sus cadenas 100k y combinarlos en una cadena larga. luego toma su subcadena de consulta e itera sobre su secuencia grande, buscando sus coincidencias. pero no estás saltando por personaje (lo que significaría que estás viendo 100k * 100 iteraciones). estás saltando a lo largo de la subcadena, por lo que cuanto más larga sea la subcadena, más rápido será.

aquí es un gran ejemplo: http://userweb.cs.utexas.edu/users/moore/best-ideas/string-searching/fstrpos-example.html

que están buscando el ejemplo de cadena.

este es el tipo de cosas que hacen los navegadores y editores de texto, y realmente no construyen tablas de prefijos gigantes cada vez que carga una página.

Answer 2

La estructura de datos que probablemente quiera usar es un Trie, específicamente un sufijo trie. Lea this article para obtener una buena explicación de cómo funcionan y cómo escribir uno para su problema.

Answer 3

Mientras que ciertamente puede acelerar con una mejor estructura de datos, este es un momento en que la fuerza bruta podría ser perfectamente adecuada. Hacer una prueba rápida:

[Editar:. Código para buscar subcadenas, editado de nuevo para acortar la subcadena se busca en comparación con los que se busca en cambiado]

#include <algorithm> 
#include <iostream> 
#include <vector> 
#include <string> 
#include <time.h> 

std::string rand_string(int min=20, int max=100) { 
    size_t length = rand()% (max-min) + min; 
    std::string ret; 

    for (size_t i=0; i<length; i++) 
     ret.push_back(rand() % ('z' - 'a') + 'a'); 
    return ret; 
} 

class substr { 
    std::string seek; 
public: 
    substr(std::string x) : seek(x) {} 

    bool operator()(std::string const &y) { return y.find(seek) != std::string::npos; } 
}; 

int main() { 
    std::vector<std::string> values; 

    for (int i=0; i<100000; i++) 
     values.push_back(rand_string()); 

    std::string seek = rand_string(5, 10); 

    const int reps = 10; 

    clock_t start = clock(); 
    std::vector<std::string>::iterator pos; 
    for (int i=0; i<reps; i++) 
     pos = std::find_if(values.begin(), values.end(), substr(seek)); 
    clock_t stop = clock(); 

    std::cout << "Search took: " << double(stop-start)/CLOCKS_PER_SEC/reps << " seconds\n"; 
    if (pos == values.end()) 
     std::cout << "Value wasn't found\n"; 
    else 
     std::cout << "Value was found\n"; 
    return 0; 
} 

En mi máquina (alrededor de 4 años - difícilmente un demonio de velocidad según los estándares actuales) esto se extiende alrededor de 10 milisegundos por búsqueda. Eso es lo suficientemente rápido como para parecer instantáneo para un usuario interactivo, y con 10 veces más cadenas, aún estaría bien.

Answer 4

Odio estar en desacuerdo con Mike y sus seguidores, pero los árboles de sufijos (estructura de datos descrita en este enlace) son muy difíciles de implementar. Y encontrar una implementación confiable en Pascal/Delphi también podría ser difícil.

Suffix Arrays ofrecen la misma funcionalidad a la vez que son mucho más simples.La compensación es O(m * logn) complejidad, donde m es la longitud del token de búsqueda y n es el tamaño del conjunto de datos (100kb en este caso).

En caso de que alguien no sepa, los árboles de sufijos y matrices de sufijos le permiten encontrar todas las apariciones de la subcadena s en texto largo t.

El problema de Fernando se puede reducir a este, al concatenar el conjunto inicial de cadenas en una cadena utilizando algún símbolo delimitador. Por ejemplo, si el conjunto inicial es ["text1", "text2", "some text"], la cadena resultante t será "text1|text2|some text".
Ahora, en lugar de buscar la cadena "text" en cada palabra por separado, solo tenemos que encontrar todas las apariciones en la cadena grande t.

También recomiendo Oren, donde sugiere otro enfoque realista.

Answer 5

Lo que probablemente esté buscando es un n-gram. Se usa para encontrar las palabras más probables relacionadas con su subcadena. Cosas muy interesantes, y aunque puede ser exagerado para lo que estás buscando, aún es bueno saberlo.

Answer 6

This Delphi implementation of Boyer-Moore-Horspool podría darle lo que necesita.
Descargo de responsabilidad: No probé este código ...