如何在Python/Django中高效过滤字符串与长单词列表？

Question

Stackoverflow 实现了“相关问题”这个功能，方法是先拿到当前提问的标题，然后把谷歌统计出来的1万个最常用的英语单词去掉。剩下的单词就用来进行全文搜索，以找到相关的问题。

我想在我的 Django 网站上做类似的事情。有什么好的方法可以在 Python 中过滤一个字符串（在这个例子中是问题标题）与一长串单词进行比较吗？有没有什么库可以高效地实现这个功能？

Answer 1

我不知道StackOverflow用的是什么方法，但：

我想一个快速（而且非常简单）的方法是回到C语言，逐个检查这些单词，可能可以用KMP算法来实现。

另一种（不那么简单）的方法是用一个字典树来存储那1万个单词，然后用这个字典树来搜索文本。这种方法会非常快，但实现起来相对比较困难。如果你感兴趣，我有一个用C++写的简单实现。

编辑

回头看，我发现我只用了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 2

我觉得有一个更简单的解决办法，而且速度也不错，就是用sqlite和正则表达式。

把那长长的单词列表放进一个sqlite表里，然后建立一个b树索引。这样可以让你在查询某个单词是否存在时，速度变得很快，时间复杂度是log(n)。接着，用正则表达式把较短的字符串分开，然后对每个单词进行一次存在性查询。

你可以先用nltk里的porter词干提取器来处理这些单词。

Answer 3

你可以很简单地使用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)