Buscando una manera más rápida de realizar búsquedas de cadenas

Question

Tengo que reconocer una gran lista de URL (pocos millones de líneas) como pertenecientes a una categoría en particular o no. Tengo otra lista que tiene sub-cadenas que, si están presentes en la URL, pertenecen a esa categoría. Diga, Categoría A.

La lista de subcadenas a verificar tiene alrededor de 10k tales subcadenas. Lo que hice fue simplemente ir línea por línea en el archivo de subcadena y buscar la coincidencia, y si la URL pertenecía a la Categoría A. Encontré en las pruebas que esto consumía bastante tiempo.

No soy un estudiante de ciencias de la computación, así que no tengo mucho conocimiento sobre la optimización de algoritmos. Pero, ¿hay alguna forma de hacerlo más rápido? Solo ideas simples. El lenguaje de programación no es un gran problema, pero Java o Perl serían preferibles.

La lista de subcadenas que coincidan no cambiará mucho. Sin embargo, recibiré diferentes listas de URL, así que debo ejecutar esto cada vez que lo reciba. El cuello de botella parece ser las URL, ya que pueden ser muy largas.

Answer 1

Sí, he implementado el algoritmo Aho-Corasick algorithm en java para el problema que usted está sugiriendo y mostraron una mejora constante de aproximadamente x180 sobre la aplicación ingenua (lo que está haciendo). Hay varias implementaciones disponibles en línea, aunque las modificaría para un mejor rendimiento. Tenga en cuenta que la complejidad de las soluciones está limitada por la longitud de la palabra (en su caso, la URL) y no por el número de subcadenas. además, solo requiere un pase en promedio para emparejar.

P.S - Solíamos dar esta pregunta a las personas en las entrevistas de trabajo, por lo que hay muchas maneras de resolverlo. El que ofrezco es el que usamos en el código de producción, que (por ahora) supera a todas las demás soluciones.

Editar: escribió el nombre equivocado algoritmo previamente, fijo ...

Answer 2

Puede comprimir las subcadenas en clases que comparten el mismo prefijo. Esto debería reducir el tiempo por un margen significativo.

Si está buscando coincidencias al cambiar la cadena por 1 en cada iteración, puede mejorar bastante la velocidad con un algoritmo mejor (como con expresiones regulares).

Answer 3

Sugiero usar el venerable Grep en lugar de utilizar un lenguaje de programación para esta tarea. Utiliza el rápido Boyer-Moore string searching algorithm, que debería ser suficiente para unos pocos millones de líneas.

Answer 4

Por supuesto, existen diferentes enfoques para optimizar esto. En cuanto a tu formación, te dibujaré una simple. Lo cual supone que la lista de subcadenas no cambia muy a menudo.

1. Genera una enorme expresión regular de todas las subcadenas.
2. Recopila esa expresión regular, ver. la clase Pattern en Java, por ejemplo. Almacene la referencia a esa expresión regular compilada.
3. Usa la misma expresión regular compilada para que coincida con cada url.

Answer 5

Perl es muy bueno en la optimización de largas listas de cadenas alternativas en una expresión regular (hasta una cierta longitud de expresiones regulares en general compilado, donde se vuelve a un mecanismo menos eficiente). Usted debe ser capaz de construir una expresión regular para que coincida con una determinada categoría como:

$catAre = join('|', map quotemeta, @catAstrings); 
$catAre = qr/$catAre/; 

Answer 6

Para las bibliotecas Java que implementan los algoritmos de búsqueda de cuerda común ver las respuestas a https://stackoverflow.com/questions/5564610/fast-alernative-for-stringindexofstring-str. Junto con la paralelización, debería poder analizar millones de URL con bastante rapidez. Es bastante fácil de hacer; Probablemente deberías probarlo y ver si el tiempo es aceptable o no antes de buscar mucho más en la optimización.

Answer 7

lo escribí por primera vez como comentario, pero luego me di cuenta, yo creo que es más apropiada como respuesta
Se puede utilizar algún sistema de recuperación de información (como Apache Lucene en Java) y lo utilizan para indexar las URLs como documentos.
Luego, después de la indexación, puede recorrer las consultas y buscarlas, el resultado serán las URL coincidentes.
PROS:
* la búsqueda no requerirá iterar sobre todas las URL para cada consulta.
* si va a necesitar más adelante intersección o unión de subcadena/consultas - la biblioteca le ofrece esta funcionalidad
CONTRA:
* indexación tomará un tiempo ...
* es posible que necesite un poco de espacio extra en la RAM/disco para el índice.

Creo que es un método que vale la pena explorar, tal vez el tiempo que se consume al indexar vale la ganancia de la búsqueda.

Answer 8

He hecho este tipo de cosas antes en Perl, comparando una lista de ~ 13k palabras clave contra una corriente entrante de datos de Twitter para encontrar todos los tweets que coinciden con cualquiera de esas palabras clave (y qué palabras clave coinciden). En términos aproximados, el código es el siguiente:

use Regexp::Assemble; 
my $ra = Regexp::Assemble->new; 
$ra->add(@keywords); 
my $regex = $ra->re; 

for my $tweet (@tweets) { 
    my @matches = $tweet =~ /$regex/g; 
    # do whatever with @matches... 
} 

Tenga en cuenta que este utiliza Regexp::Assemble para construir la expresión regular, que no forma parte del núcleo de la distribución de Perl, por lo que tendrá que instalar si de CPAN si quieres adaptar este código

Si está utilizando Perl 5.10 o posterior, también existe el operador de "coincidencia inteligente" (~~) que puede hacer algo similar sin requerir ningún módulo adicional.

Answer 9

Actualmente estoy trabajando en este problema. Llegué a esta conclusión:

Aho-corasick consumirá más memoria al hacer árboles. Si no hay problema de memoria, es bueno. Pero mira en el HAT Trie una vez. Es la combinación de hash y trie (árbol). Hará un árbol en algún nivel y los caracteres restantes formarán un valor hash que debería marcarse en la tabla Hash.

Disculpe el lenguaje más técnico. Pero creo que es mejor opción HAT si estás buscando una URL específica de la lista de URL. (He formado un trie de HAT que consumirá 12MB para almacenar 6lacks de URL.)