如何在 Python/Django 中根据一长串单词有效过滤字符串？

Question

Stackoverflow 通过获取当前问题的标题并从 Google 中删除 10,000 个最常见的英语单词来实现“相关问题”功能。然后将剩余的单词作为全文搜索提交以查找相关问题。

我想在我的 Django 网站中做类似的事情。在 Python 中针对一长串单词过滤字符串（本例中为问题标题）的最佳方法是什么？有什么库可以让我高效地做到这一点吗？

Answer 1

您可以使用 Python 中的 set 和 string 功能非常简单地完成此操作，并查看其执行情况（过早的优化是万恶之源！）：

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

我认为一个更简单且仍然相当快的解决方案是使用 sqlite 和正则表达式。

将一长串单词放入 SQLite 表中并构建 B 树索引。这为您提供了 log(n) 时间存在的查询。使用正则表达式拆分较小的字符串，并循环遍历每个单词，运行存在查询。

您可以先使用 nltk 的 porter 词干分析器对单词进行词干分析。

Answer 3

虽然我讨厌阻止使用像 trie 这样很酷的东西，但你有没有想过直接用 python 来做呢？我使用 corncob worlist 编写了一个简单的基准测试，性能还不错。

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 编写的。最后，这个测试几乎针对英语中的每个单词。如果你只想要一万，我认为那是小菜一碟。

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 4

我不知道 SO 使用哪种方法，但是：

我想一种快速（而且非常简单）的方法是返回到 C，并逐一检查它们，也许使用 KMP 算法。

另一种（不是那么简单）的方法是用这 10000 个单词保留一个 trie并使用它搜索文本。这将是超级快，但相当难以实现。如果您有兴趣，我有一个 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 5

如果一些误报/漏报没问题，请在维基百科上搜索布隆过滤器。

如果不看CDB，（在Fedora中安装tinycdb——没有python API atm）。

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