Как эффективно отфильтровать строку по длинному списку слов в Python / Django?

Question

Stackoverflow реализовал функцию «Связанные вопросы», взяв название текущего вопроса и удалив из него 10 000 наиболее распространенных английских слов, согласно Google.Остальные слова затем отправляются в виде полнотекстового поиска для поиска связанных вопросов.

Я хочу сделать что-то подобное на моем сайте Django.Каков наилучший способ фильтрации строки (в данном случае названия вопроса) по длинному списку слов в Python?Какие-нибудь библиотеки, которые позволили бы мне сделать это эффективно?

Answer 1

Вы можете сделать это очень просто, используя функцию set и string в Python и посмотреть, как она работает (преждевременная оптимизация - корень всего зла!):

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

Хотя я очень не хочу препятствовать использованию чего-то классного, такого как три, вы думали о том, чтобы сделать это на прямом питоне? Я написал простой тест с использованием кукурузного початка , и производительность не так уж и плоха.

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

обратите внимание, что я тестирую наихудший случай, когда слово отсутствует в файле. Я также включаю время, чтобы загрузить файл и обработать файл. Если бы вы запомнили его, это бы исчезло. Еще одна вещь, на которую стоит обратить внимание, это то, что моя машина в основном чушь. C работает быстро, но большая часть кода, используемого для поиска в списке, в любом случае написана на C. Наконец, этот тест предназначен для каждого слова в английском языке . Если вы просто хотите 10000, я думаю, это торт.

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 3

Я думаю, что гораздо более простое и достаточно быстрое решение - использовать sqlite и регулярные выражения.

Поместить длинный список слов в таблицу sqlite и построить индекс b-дерева.Это дает вам log (n) время существования запросов.Разделите меньшую строку с помощью регулярного выражения и обведите слова, выполняющие существующий запрос, для каждого из них.

Сначала вы можете вставить слова с помощью средства переноса из nltk.

Answer 4

Я не знаю, какой метод используется SO, но:

Полагаю, быстрый (и очень упрощенный) способ сделать это - вернуться к C и проверить их один за другим,может быть, с алгоритмом KMP .

Другой (не такой простой) способ сделать это - сохранить trie с этими 10.000 слов и искать текст с использованием этого,Это было бы очень быстро, но довольно сложно реализовать.Если вам интересно, у меня есть фиктивная реализация на C ++.

EDIT

Оглядываясь назад, я вижу, что я использовал только fstream, так что это может бытьлегко модифицируется для C, так что вы сможете легко интегрироваться с python .Это источник:

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

Он принимает trie.in текст, отформатированный так:

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

И производит текст, подобный этому

0
2
2
3
1
2

0 w- добавить слово w в список (может быть несколько раз)

1 w - удалить одну запись слова w из списка (может быть несколько раз)

2 w - напечатать какв списке много слов w

3 w - выведите длину самого длинного общего префикса w с любым другим словом в списке

О, и извините за плохое форматирование, этобыло сделано для обучения.

Answer 5

Если некоторые ложные срабатывания / отрицания в порядке, ищите фильтр Блума в Википедии.

Если не смотреть на CDB, (yum install tinycdb, в Fedora - без интерфейса Python API).

Answer 6

Как насчет использования очень хорошего * python 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())