Cómo filtrar de manera eficiente una cadena contra una larga lista de palabras en Python/Django?

Question

Stackoverflow implementó su función de "Preguntas relacionadas" tomando el título de la pregunta actual que se le formula y eliminando las 10,000 palabras más comunes en inglés según Google. Las palabras restantes se envían luego como búsqueda de texto completo para encontrar preguntas relacionadas.

Quiero hacer algo similar en mi sitio de Django. ¿Cuál es la mejor manera de filtrar una cadena (el título de la pregunta en este caso) frente a una larga lista de palabras en Python? ¿Alguna biblioteca que me permita hacer eso de manera eficiente?

Answer 1

Puede hacer esto de forma muy simple utilizando la funcionalidad de conjunto y cadena en Python y ver cómo funciona (¡la optimización prematura es la raíz de todos los males!):

common_words = frozenset(("if", "but", "and", "the", "when", "use", "to", "for")) 
title = "When to use Python for web applications" 
title_words = set(title.lower().split()) 
keywords = title_words.difference(common_words) 
print(keywords) 

Answer 2

No sé qué método es utilizado por SO, pero:

supongo una manera rápida (y muy simplista) de hacer esto es volviendo a C, y los cheques, uno por uno, tal vez con un algoritmo KMP.

Otra forma (no tan simple) de hacer esto, es mantener un trie con esas 10.000 palabras y buscar el texto con eso. Esto sería súper rápido, pero bastante difícil de implementar. Si está interesado, tengo una implementación ficticia en C++.

EDITAR

Mirando hacia atrás a ella, veo sólo lo he utilizado fstream, por lo que este podría ser modificado fácilmente para C, por lo que be able to integrate with python easily. Esta es la fuente:

#include <fstream> 
using namespace std; 

ifstream in("trie.in"); 
ofstream out("trie.out"); 

struct Trie 
{ 
    short nr, pref; 
    Trie *children[26], *father; 
    Trie() 
    { 
     int i; 
     nr = pref = 0; 
     for(i=0; i<26; i++) 
      children[i] = NULL; 
     father = NULL; 
    } 
}; 

Trie t, *it, *it2; 
int n, op, val, i, l, len; 
char s[22],*p; 

int main() 
{ 
    while(in>>op>>s) 
    { 
     p = s; 
     it = &t; 
     l = 0;len=0; 
     while(p[0] != '\0') 
     { 
      if(it->children[p[0] - 'a'] == NULL && op == 2) 
       {op=9; out<<"0\n"; break;} 
      if(it->children[p[0] - 'a'] == NULL && op == 3) 
       break; 
      if(it->children[p[0] - 'a'] == NULL) 
       it->children[p[0] - 'a'] = new Trie(), it->children[p[0] - 'a']->father = it, 
         it = it->children[p[0] - 'a']; 
      else 
       it = it->children[p[0] - 'a']; 
      if(op == 0) 
       ++ it->pref; 
      else if(op == 1 && it->pref > 0) 
       -- it->pref; 
      else if(op == 3 && it->pref > 0) 
       l = p-s+1; 

      p++; 
     } 
     if(op == 0) 
      it->nr ++; 
     else if(op == 1 && it->nr > 0) 
     { 
      it->nr --; 
      l = strlen(s)-1; 
      while(it->pref == 0 && it != &t && l>=0) 
      { 
       it2 = it->father; 
       it2->children[s[l--] - 'a'] = NULL; 

       delete it; 
       it = it2; 
      } 

     } 
     else if(op == 2) 
      out<<it->nr<<'\n'; 
     else if(op == 3) 
      out<<l<<'\n'; 

    } 
    return 0; 
} 

Esto toma en trie.in texto con formato como esto:

0 lat 
0 mare 
0 lac 
2 la 
0 mare 
1 lat 
0 ma 
0 lung 
3 latitudine 
0 mari 
2 mare 
0 lat 
0 mic 
3 latime 
2 lac 
3 mire 

y produce texto como este

0 
2 
2 
3 
1 
2 

0 w - añadir la palabra w en la lista (podría ser varias veces)

1 w - eliminar un registro de la palabra w de la lista (podría ser varias veces)

2 W - impresión cuántos w palabras hay en la lista

3 w - imprimir la longitud del prefijo más largo común de w con cualquier otra palabra en la lista

Oh , y perdón por el pobre formato, esto fue hecho para entrenar.

Answer 3

Creo que una solución mucho más simple y aún razonablemente rápida es usar sqlite y expresiones regulares.

Ponga la larga lista de palabras en una tabla sqlite y cree un índice b-tree. Esto le da log (n) tiempo de consultas existentes. Divida la cadena más pequeña con una expresión regular y repita las palabras que ejecutan una consulta existente para cada una de ellas.

Puedes resumir las palabras primero con el portador stemmer de nltk.

Answer 4

Mientras que odio a desalentar el uso de algo fresco como un trie, ¿ha pensado en hacerlo en Python recta? Escribí un punto de referencia simple usando el corncob worlist y el rendimiento no fue tan malo.

import time 

with open('corncob_lowercase.txt') as f: 
    filetime = 0 
    starttime = time.time() 
    words = f.read().split('\n') 
    endtime = time.time() 
    filetime = endtime - starttime 
    print "file opened in {0} seconds".format(filetime)  
    nonwords = ['234' + word for word in words] 
    totaltime = 0 
    for word in nonwords: 
     starttime = time.time() 
     word in words 
     endtime = time.time() 
     totaltime += endtime - starttime 
    wordcount = len(words) 
    avgtime = totaltime/wordcount 
    print "average time for word: {0}".format(avgtime) 
    print "with {0} words".format(wordcount) 
    runningtimes = (filetime + i * avgtime for i in xrange(10)) 
    print "running times: {0}".format(list(runningtimes)) 

tenga en cuenta que estoy probando el peor caso donde la palabra no está en el archivo. También incluyo el tiempo para cargar el archivo y procesar el archivo. Si fueras a Memcache, eso desaparecería. Una cosa más a tener en cuenta es que mi máquina es básicamente basura. C es rápido, pero la mayoría del código involucrado en la búsqueda de una lista está escrito en C de todos modos. Finalmente, esta prueba es para casi cada palabra en el idioma inglés. Si solo quieres 10,000, creo que es un pastel.

file opened in 0.0135519504547 seconds 
average time for word: 0.00249605141253 
with 58113 words 
running times: [0.013551950454711914, 0.016048001867237236, 0.018544053279762558, 
0.021040104692287877, 0.023536156104813199, 0.026032207517338521, 0.028528258929863839, 
0.031024310342389162, 0.033520361754914484, 0.036016413167439809] 

Answer 5

Si algunos positivos/negativos falsos son correctos, busque el filtro bloom en wikipedia.

Si no mira a CDB, (yum install tinycdb, en Fedora - sin la atm de python API).

Answer 6

¿Y si uso muy agradable filter método de pitón:

common_words = set(("if", "but", "and", "the", "when", "use", "to", "for")) 
title = "When to use Python for web applications" 
print filter(lambda word: word not in common_words, title.lower().split())