Comment filtrer efficacement une chaîne contre une longue liste de mots dans Python/Django?

Question

Stackoverflow a implémenté sa fonction "Questions Connexes" en prenant le titre de la question en cours posée et en supprimant les 10 000 mots anglais les plus courants selon Google. Les mots restants sont ensuite soumis en tant que recherche de texte intégral pour trouver des questions connexes. Je veux faire quelque chose de similaire sur mon site Django. Quel est le meilleur moyen de filtrer une chaîne (le titre de la question dans ce cas) contre une longue liste de mots en Python? Des bibliothèques qui me permettraient de le faire efficacement?

Answer 1

Vous pouvez le faire très simplement en utilisant les fonctionnalités set et string en Python et voir comment cela fonctionne (l'optimisation prématurée étant la racine de tous les maux!):

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

Je ne sais pas quelle méthode est utilisée par SO, mais:

Je suppose un rapide (et très simpliste) façon de le faire est en remontant à C, et les vérifier un par un, peut-être avec un algorithme KMP.

Une autre façon (pas si simple) de le faire, est de garder un trie avec ces 10.000 mots et de chercher dans le texte en utilisant cela. Ce serait super-rapide, mais assez difficile à mettre en œuvre. Si vous êtes intéressé, j'ai une implémentation fictive en C++.

EDIT

Rétrospectivement à elle, je vois que je ne l'ai utilisé fstream, donc cela pourrait être modifié facilement pour C, vous aurez donc be able to integrate with python easily. Ceci est la source:

#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; 
} 

Cela prend en trie.in texte formaté comme ceci:

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 

Et produit un texte comme celui-ci

0 
2 
2 
3 
1 
2 

0 w - ajouter le mot w dans la liste (pourrait être plusieurs fois)

1 w - supprimer un enregistrement du mot w de la liste (pourrait être plusieurs fois)

2 w - impression combien w mots sont là dans la liste

3 w - imprimer la longueur du plus long préfixe commun de w avec tout autre mot dans la liste

Oh , et désolé pour le mauvais formatage, cela a été fait pour la formation.

Answer 3

Je pense qu'une solution beaucoup plus simple et toujours assez rapide consiste à utiliser des expressions sqlite et régulières.

Placez la longue liste de mots dans une table sqlite et créez un index b-tree. Cela vous donne des requêtes de temps de log (n). Fractionnez la chaîne la plus petite avec une expression régulière et faites une boucle sur les mots exécutant une requête exists pour chacun d'entre eux.

Vous pouvez arrêter les mots d'abord avec le stemmer porteur de nltk.

Answer 4

Bien que je déteste décourager l'utilisation de quelque chose de cool comme un Trie, avez-vous pensé à le faire en python droit? J'ai écrit un benchmark simple en utilisant le corncob worlist et la performance n'était pas si mauvaise.

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)) 

Notez que je teste le pire cas où le mot ne figure pas dans le fichier. J'inclus également le temps de charger le fichier et de traiter le fichier. Si vous deviez le mémoriser, cela disparaîtrait. Une autre chose à noter est que ma machine est essentiellement de la merde. C est rapide mais la plupart du code impliqué dans la recherche d'une liste est écrit en C de toute façon. Enfin, ce test est à peu près chaque mot dans la langue anglaise. Si vous voulez seulement 10 000, je pense que c'est un gâteau.

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 certains faux positifs/négatifs sont corrects, recherchez le filtre bloom sur wikipedia.

Si ne regarde pas CDB, (yum install tinycdb, dans Fedora - pas d'API API python).

Answer 6

Que diriez-vous en utilisant la méthode de python très agréable filter:

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())