快速n-gram计算

Question

我正在使用NLTK这个工具来在一堆文本中查找n-grams（就是把词组分成n个词的小块），但有时候速度特别慢。我发现其他一些工具包也能计算n-grams（比如Haystack就有这个功能）。这是不是意味着如果我不再使用NLTK，可能会有更快的方法来找到我文本中的n-grams呢？如果是这样的话，有什么工具可以让我加快速度呢？

Answer 1

如果你想要处理字符级别的n-grams（就是把字符分成小块），你可以使用下面这个函数。

def ngrams(text, n):
    n-=1
    return [text[i-n:i+1] for i,char in enumerate(text)][n:] 

Answer 2

你可以找到一个使用 zip 和星号（*）运算符的优雅、快速的 ngram 生成函数，具体的内容可以在这里查看：

def find_ngrams(input_list, n):
  return zip(*[input_list[i:] for i in range(n)])

Answer 3

因为你没有说明你想要的是按单词还是按字符来提取n-gram，我就假设你想要的是按单词来处理，这样也不会影响结果。

我还假设你手头有一个字符串列表，这些字符串就是你要处理的内容。你可以很简单地自己写一个提取n-gram的程序。

def ngrams(tokens, MIN_N, MAX_N):
    n_tokens = len(tokens)
    for i in xrange(n_tokens):
        for j in xrange(i+MIN_N, min(n_tokens, i+MAX_N)+1):
            yield tokens[i:j]

然后把yield替换成你想对每个n-gram执行的实际操作（比如把它加到一个dict里，或者存到数据库中，随便你），这样就能避免生成器带来的额外开销。

最后，如果速度还是不够快，可以把上面的代码转换成Cython并进行编译。下面是一个使用defaultdict代替yield的例子：

def ngrams(tokens, int MIN_N, int MAX_N):
    cdef Py_ssize_t i, j, n_tokens

    count = defaultdict(int)

    join_spaces = " ".join

    n_tokens = len(tokens)
    for i in xrange(n_tokens):
        for j in xrange(i+MIN_N, min(n_tokens, i+MAX_N)+1):
            count[join_spaces(tokens[i:j])] += 1

    return count