python - 有效检查单词是否与集合中的模式匹配(Python)

Question

我有一组许多简单的通配模式和整个单词，如下所示:

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

我还有一大堆单词。我想检查此列表中的每个单词是否与 a) 集合中的通配模式或 b) 集合中的单词匹配。

如果没有通配模式，我会做类似的事情:

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

但是由于该集合也包含通配模式，因此如果我想将“BREADY”与“BREAD*”匹配，它将找不到匹配项

我能想到的唯一方法是使用嵌套的 for 循环将每个单词与集合中的每个模式进行比较。有没有一种方法可以检查每个单词在集合中是否有匹配项，而无需将其与集合中的每个元素进行比较？

Answer 1

您应该将要匹配的完整字符串与要匹配的前缀分开存储。对于您的前缀，将它们进一步划分为等长前缀组(即一组长度为 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", ...])

完整字符串匹配很简单 - 只需检查单词是否在完整字符串中。

对于前缀，您将分别检查每个长度，从长度 1 开始到您要匹配的最大前缀长度。对于每个长度n，检查word[:n]是否在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"