búsqueda de cadenas cortas masivas de alto rendimiento en Python

Question

El problema: una gran lista estática de cadenas se proporciona como A, una cadena larga se proporciona como B, las cadenas en A son todas muy cortas (una lista de palabras clave), quiero comprobar si cada cadena en A es una subcadena de B y obténgalos.

Ahora uso un bucle simple como:

result = [] 
for word in A: 
    if word in B: 
     result.append(word) 

Pero es una locura lenta cuando A contiene ~ 500.000 o más elementos.

¿Hay alguna biblioteca o algoritmo que se ajuste a este problema? Hice mi mejor esfuerzo para buscar pero no tuve suerte.

¡Gracias!

Answer 1

Su problema es suficientemente grande como para que probablemente tenga que golpearlo con el algoritmo bat.

Eche un vistazo al algoritmo Aho-Corasick. La declaración del problema es una paráfrasis del problema que aborda este algoritmo.

Además, vea el trabajo de Nicholas Lehuen con su paquete PyTST.

También hay referencias en un mensaje de desbordamiento de pila relacionados que mencionan otros algoritmos tales como Rabin-Karp: Algorithm for linear pattern matching?

Answer 2

No sé si esto sería con mayor rapidez, pero es mucho más Pythonic:

result = [x for x in A if x in B] 

Answer 3

empacar todas las palabras individuales de B en una nueva lista, que consiste en la cadena original dividido por ' '. Luego, para cada elemento en B, pruebe la pertenencia a cada elemento de A. Si encuentra uno (o más), elimínelos del A y salga cuando A esté vacío.

Parece que su enfoque se extenderá a través de 500,000 candidatos sin que se establezca un opt-out.

Answer 4

Dependiendo de la duración de su cadena larga es, puede valer la pena hacer algo como esto:

ls = 'my long string of stuff' 
#Generate all possible substrings of ls, keeping only uniques 
x = set([ls[p:y] for p in range(0, len(ls)+1) for y in range(p+1, len(ls)+1)]) 

result = [] 
for word in A: 
    if word in x: 
     result.append(word) 

Obviamente, si su cadena larga es muy, muy larga, esto también se vuelve demasiado lenta, pero debería ser más rápida para cualquier cadena de unos pocos cientos de caracteres.

Answer 5

Suponga que tiene todas las palabras clave de la misma longitud (más adelante se podría extender esta algo para diferentes longitudes)

que podría sugerir siguiente:

1. precalcular algunos hash para cada palabra clave (por ejemplo, XOR hash):

   hash256 = reduce(int.__xor__, map(ord, keyword)) 
   

2. crear un diccionario donde la clave es un hash, y la lista de valores de palabras clave correspondientes

3. Guardar longitud de palabra clave

   curr_keyword = [] 
   for x in B: 
       if len(curr_keyword) == keyword_length: 
       hash256 = reduce(int.__xor__, map(ord, curr_keyword)) 
       if hash256 in dictionary_of_hashed: 
        #search in list 
   
       curr_keyword.append(x) 
       curr_keyword = curr_keyword[1:] 
   

Algo como esto