Buscar una lista de cadenas para cualquier subcadena de otra lista

Question

Teniendo en cuenta estas 3 listas de datos y una lista de palabras clave:

good_data1 = ['hello, world', 'hey, world'] 
good_data2 = ['hey, man', 'whats up'] 
bad_data = ['hi, earth', 'sup, planet'] 
keywords = ['world', 'he'] 

Estoy intentando escribir una función sencilla de comprobar si alguna de las las palabras clave existen como una subcadena de cualquier palabra en las listas de datos. Debería devolver True para las listas good_data y False para bad_data.

sé cómo hacer esto en lo que parece ser una forma ineficiente:

def checkData(data): 
    for s in data: 
    for k in keywords: 
     if k in s: 
     return True 
    return False 

Answer 1

En su ejemplo, con tan pocos elementos, realmente no importa. Pero si tiene una lista de varios miles de artículos, esto podría ayudar.

Como no le importa qué elemento de la lista contiene la palabra clave, puede escanear toda la lista una vez (como una cadena) en lugar de un elemento a la vez. Para eso necesita un carácter de unión que sepa que no ocurrirá en la palabra clave, para evitar falsos positivos. Yo uso la nueva línea en este ejemplo.

def check_data(data): 
    s = "\n".join(data); 
    for k in keywords: 
     if k in s: 
      return True 

    return False 

En mi prueba completamente acientífico, mi versión analiza una lista de los artículos 5000 100000 veces en unos 30 segundos. Detuve su versión después de 3 minutos - me cansé de esperar para publicar =)

Answer 2

¿Está buscando

any(k in s for k in keywords) 

Es más compacto, pero podría ser menos eficiente.

Answer 3

Creo que esto es bastante eficiente y claro, aunque podrías usar map() para evitar los muchos nidos. Estoy de acuerdo con Ross en la idea del diccionario para listas más grandes.

Answer 4

Puede mejorar las cosas al crear su lista de palabras clave como una expresión regular.

Esto puede permitir que se prueben en paralelo, pero dependerá en gran medida de las palabras clave (por ejemplo, algunos trabajos pueden reutilizarse probando "hola" e "infierno", en lugar de buscar todas las frases desde el principio . para cada palabra

Usted puede hacer esto mediante la ejecución:

import re 
keyword_re = re.compile("|".join(map(re.escape, keywords))) 

continuación:

>>> bool(keyword_re.search('hello, world')) 
True 
>>> bool(keyword_re.search('hi, earth')) 
False 

(en realidad va a devolver un objeto partido en descubierto, y Ninguno si no se encuentra, esto podría ser útil si necesita saber qué palabra clave concuerda)

Sin embargo, la cantidad (si la suma) que obtenga dependerá de las palabras clave. Si solo tiene uno o dos, mantenga su enfoque actual. Si tiene una lista grande, puede valer la pena probar y perfilar para ver cuál funciona mejor.

[Editar] Como referencia, así es como lo hacen los enfoques para su ejemplo:

   good1 good2 good3 bad1 bad2 
original  : 0.206 0.233 0.229 0.390 63.879 
gnud (join) : 0.257 0.347 4.600 0.281 6.706 
regex  : 0.766 1.018 0.397 0.764 124.351 
regex (join) : 0.345 0.337 3.305 0.481 48.666 

Obviamente, para este caso, su enfoque lleva a cabo mucho mejor que el de expresiones regulares. Si esto siempre será así depende mucho del número y la complejidad de las palabras clave, y de los datos de entrada que se verificarán. Para números grandes de palabras clave, listas largas o frases que raramente coinciden, las expresiones regulares pueden funcionar mejor, pero haga obtenga información de tiempo, y quizás intente incluso optimizaciones más simples (como mover las palabras más comunes al principio de su lista de palabras clave) primero. A veces, el enfoque más simple es el mejor.

[Edit2] Se actualizó la tabla con gnud's solution, y un enfoque similar antes de aplicar los regexes. También agregué 2 nuevas pruebas:

good_data3 = good_data2 * 500 # 1000 items, the first of which matches. 
bad_data2 = bad_data * 500  # 1000 items, none of which matches. 

que muestran las diversas fortalezas y debilidades.Unirse es peor cuando se encuentra una coincidencia (ya que siempre hay un costo inicial pagado para unirse a la lista; este es el mejor caso posible para el método de búsqueda lineal); sin embargo, para las listas que no coinciden, se realiza mejor. Mucho mejor cuando hay una gran cantidad de artículos en el list.case).

Answer 5

Si tiene muchas palabras clave, es posible que desee probar un árbol de sufijos [1]. Inserta todas las palabras de las tres listas de datos, almacenando de qué lista proviene cada palabra en su nodo de terminación. A continuación, puede realizar consultas en el árbol para cada palabra clave realmente, muy rápido.

Advertencia: ¡los árboles de sufijo son muy complicados de implementar!

[1] http://en.wikipedia.org/wiki/Suffix_tree