高效检查单词是否匹配集合中的模式（Python）

Question

我有一组简单的匹配模式和完整的单词，像这样：

s = set(['ALE', 'BREAD*', 'BREAKFAST*', 'BROTH' ...])

我还有一个很大的单词列表。我想检查这个列表中的每个单词，看看它是否符合以下条件：a) 匹配集合中的某个模式，或者 b) 匹配集合中的某个单词。

如果没有匹配模式，我可以直接这样做：

for word in words:
    if word in s:
        # do something

但是因为这个集合里有匹配模式，所以如果我想把'BREADY'和'BREAD*'进行匹配，它就找不到匹配项。

我能想到的唯一方法就是用嵌套的循环，把每个单词和集合中的每个模式进行比较。有没有什么办法可以检查每个单词是否在集合中有匹配，而不需要和集合里的每个元素都比较呢？

Answer 1

假设我们有一个单词列表 words，还有一个搜索列表 searches。对于你给出的简单例子，下面的内容就足够了。

for word in words:
    for search in searches:
        if search[-1] == "*":
            search = search[:-1]
            if word.lower().startswith(search.lower()):
                yield word
        else:
            if word.lower() == search.lower():
                yield word

Answer 2

可以理解，提问者并不想使用循环。

import re
import fnmatch
s = set(['ALE', 'BREAD*', 'BREAKFAST*', 'BROTH'])
patterns = [re.compile(fnmatch.translate(p)) for p in s]

for word in "BEING PALE I LIKE ALE WITH BREADDY ABROTH FOR BREAKFASTY TREATS AND BROTH".split():
    for pattern in patterns:
        if pattern.match(word):
            print "HIT", word

结果是：

HIT ALE
HIT BREADDY
HIT BREAKFASTY
HIT BROTH

Answer 3

你应该把想要匹配的完整字符串和想要匹配的前缀分开存储。对于前缀，可以进一步把它们分成相同长度的组（也就是说，长度为1的前缀放在一组，长度为2的前缀放在另一组，依此类推）。

也就是说：

fullstrings = set(["BREAKFAST", "LUNCH", "DINNER", ...])
prefixes_by_length = {} # dict of length -> prefix string
...
prefixes_by_length[4] = set(["CORN", "DESK", ...])
prefixes_by_length[5] = set(["BREAD", "TABLE", ...])

完整字符串的匹配很简单——只需要检查一下 word in fullstrings 就可以了。

对于前缀，你需要分别检查每个长度，从长度1开始，一直到你想要匹配的最大前缀长度。对于每个长度 n，检查 word[:n] in prefixes_by_length[n]。

这样做比每次都遍历所有前缀要高效得多，特别是当你有很多前缀的时候。

for word in words:
    if word in fullstrings:
        "Match! do something"
    for n in prefixes_by_length:
        if word[:n] in prefixes_by_length[n]:
            "Match! do something"