python - 通过与英语单词白名单进行比较来快速(呃)检查一个单词是否是英语的方法？

Question

我试图从许多(100k)预处理文本文件中消除所有非英语单词(porter 词干和小写，删除所有非 a-z 字符)。我已经并行化了该过程以加快速度，但它仍然慢得令人痛苦。在 python 中是否有更有效的方法来做到这一点？

englishwords = list(set(nltk.corpus.words.words()))
englishwords = [x.lower() for x in list(englishwords)]
englishwords = [ps.stem(w) for w in englishwords]
# this step takes too long:
shareholderletter= ' '.join(w for w in nltk.wordpunct_tokenize(shareholderletter) if w in englishwords)

Answer 1

您正在检查somthing in otherthing - 和你的otherthing是一个列表。

列表适合存储内容，但查找“x 是否在列表中”需要 O(n) 。

使用 set相反，这会导致查找 O(1) 并且它消除了任何重复，因此如果您有重复项，您要查找的内容的基本大小也会下降。

如果您的设置之后没有改变，请使用 frozenset - 这是不可变的。

阅读:Documentation of sets

如果您遵循 @DeepSpace 的建议，并利用集合运算，您将获得更好的性能:

s = set( t.lower().strip() for t in ["Some","text","in","set"])

t = set("Some text in a string that holds other words as well".lower().split())

print ( s&t )  # show me all things that are in both sets (aka intersection)

输出:

set(['text', 'some', 'in'])

<小时/>

参见set operations

<小时/>

O(n):最坏情况:您的单词是列表中 20 万个单词中的最后一个，并且您检查整个列表 - 这需要 20 万次检查。

O(1):查找时间是恒定的，无论数据结构中有多少项，检查其是否存在都需要相同的时间。为了获得此好处，set有一个更复杂的存储解决方案，需要稍微多一点的内存(然后是列表)才能在查找方面表现出色。

<小时/>

编辑:在集合/列表中找不到单词的最坏情况::

import timeit

setupcode = """# list with some dupes
l = [str(i) for i in range(10000)] + [str(i) for i in range(10000)] + [str(i) for i in range(10000)]
# set of this list
s = set( l )
"""

print(timeit.timeit("""k = "10000" in l """,setup = setupcode, number=100))
print(timeit.timeit("""k = "10000" in s """,setup = setupcode, number=100))

0.03919574100000034    # checking 100 times if "10000" is in the list
0.00000512200000457    # checking 100 times if "10000" us in the set