优化Python中字符串列表前缀匹配的效率

def match(string, prefixes):
    """检查一个字符串是否以任意给定前缀开头"""
    for prefix in prefixes:
        if string.startswith(prefix):
            return 1
    return 0

def count_matches(string_list, prefixes):
    """统计列表中匹配前缀的字符串数量"""
    total_matches = 0
    for elem in string_list:
        total_matches += match(elem, prefixes)
    return total_matches

# 示例用法
list1 = ["abc", "acd", "df", "ade"]
list2 = ["a", "ab", "ad"]
print(f"匹配数量: {count_matches(list1, list2)}") # 输出: 3 (abc, acd, ade)

import re

prefixes = ["a", "ab", "ad"]
words = ["abc", "acd", "df", "ade"]

# 构建正则表达式模式
# 注意：为了确保只匹配开头，通常在模式前加上 '^'
regex_pattern = "^(" + "|".join(re.escape(p) for p in prefixes) + ")"
print(f"生成的正则表达式: {regex_pattern}")

match_count = sum(1 for word in words if re.match(regex_pattern, word))
print(f"匹配数量 (基本Regex): {match_count}") # 输出: 3

import re

prefixes = ["a", "ab", "ad"]
words = ["abc", "acd", "df", "ade"]

regex_pattern = "^(" + "|".join(re.escape(p) for p in prefixes) + ")"
compiled_regex = re.compile(regex_pattern) # 编译正则表达式

match_count = sum(1 for word in words if compiled_regex.match(word))
print(f"匹配数量 (编译Regex): {match_count}") # 输出: 3

import re
from trieregex import TrieRegEx

prefixes = ["a", "ab", "ad"]
words = ["abc", "acd", "df", "ade"]

# 使用 TrieRegEx 构建正则表达式
tregex = TrieRegEx(*prefixes)
# tregex.regex() 会生成类似 '^(?:a(?:b|d)?)' 这样的优化模式
compiled_regex = re.compile(tregex.regex())

match_count = sum(1 for word in words if compiled_regex.match(word))
print(f"匹配数量 (TrieRegEx): {match_count}") # 输出: 3
print(f"TrieRegEx 生成的模式: {tregex.regex()}")

import re
from trieregex import TrieRegEx

prefixes = ["a", "ab", "ad", "ba", "bang", "bet", "b"] # 包含冗余前缀
words = ["abc", "acd", "df", "ade", "bale", "banana", "better"]

tregex = TrieRegEx()
compiled_regex = None
effective_prefixes = []

# 对前缀进行排序，确保短前缀先被处理
for prefix in sorted(prefixes):
    # 如果当前前缀已经被现有的正则表达式覆盖，则跳过
    if compiled_regex and compiled_regex.match(prefix):
        continue

    # 否则，添加该前缀并重新编译正则表达式
    tregex.add(prefix)
    compiled_regex = re.compile(tregex.regex())
    effective_prefixes.append(prefix)

print(f"有效前缀列表 (去冗余): {effective_prefixes}")
print(f"优化后 TrieRegEx 生成的模式: {tregex.regex()}")

match_count = sum(1 for word in words if compiled_regex.match(word))
print(f"匹配数量 (去冗余 TrieRegEx): {match_count}") # 输出: 6
# 匹配到的词: abc, acd, ade (由a覆盖); bale, banana, better (由b覆盖)