高效的叠瓦算法

Question

我已经实现了以下算法来从字符串中提取 n 个词组。

def ngrams(text, size):
    tokens = text.split()
    ngrams = []
    for char in range(len(tokens)):
        if (len(tokens)-char) < size:
            break
        list_shingle = tokens[char:char+size]
        str_shingle = ' '.join(list_shingle)
        ngrams.append(str_shingle)
    return ngrams

字符串有这样的形式：

['Hello my name is Inigo Montoya, you killed my father, prepare to die.']

对于 3 个字的大小，输出应如下所示：

['Hello my name','my name is','name is Inigo',...,'prepare to die.']

我要比较大量的文档，如何让这段代码更有效率？

Answer 1

这不是一个不同的算法，但它使用 list comprehension 而不是循环：

def ngrams2(text, size):
    tokens = text.split()
    return [' '.join(tokens[i:i+size])
                     for i in range(len(tokens) - size + 1)]

至少在我的机器上，改变是有回报的：

$ python3 -m timeit -s 'from shingle import ngrams, ngrams2, text' 'ngrams(text, 3)'
1000 loops, best of 3: 501 usec per loop
$ python3 -m timeit -s 'from shingle import ngrams, ngrams2, text' 'ngrams2(text, 3)'
1000 loops, best of 3: 293 usec per loop

(text是由https://www.lipsum.com/生成的10kb。一行包含1347个"words"。)

高效的叠瓦算法

Efficient shingling algorithm

python

performance

parsing

text

n-gram