我有一个包含 4000 个不同名字的静态列表：因此列表的长度很大（4000），但每个字符串大约有 4 到 12 个字符（它们是名字）。
然后，我有一个从数据库检索到的 10000 个字符串的动态列表：这些字符串可能具有任意长度。
我需要输出，对于 10000 个字符串中的每一个，该字符串是否包含 4000 个名称之一，如果包含，是哪一个。如果它包含多个名称，我只需要其中一个（即第一个）。而且，不太可能找到这样的名字，所以可能 10000 个中只有 10 个包含名字。
到目前为止我的代码：
names # list of 4000 short static names
fields # list of 10000 retrieved strings
def findit(element):
for name in names:
if name in element:
return name
return None
output = [findit(element) for element in fields]
这当然有效。但是，它非常慢，因为它不太可能找到名称，并且因为我正在测试是否是子字符串而不是相等（即我不能使用二等分或其他基于排序的索引技术）。它几乎每时每刻都会完整扫描所有名单。所以基本上，它执行大约 10000 x 4000 = 4000 万次“in”比较。
有没有一种算法可以优化这种搜索？
您可以考虑将姓名列表转换为一个正则表达式。以这个小小的名单为例：
names = ['AARON',
'ABDUL',
'ABE',
'ABEL',
'ABRAHAM',
'ABRAM',
'ADALBERTO',
'ADAM',
'ADAN',
'ADOLFO',
'ADOLPH',
'ADRIAN',
]
可以用以下正则表达式来表示：
\b(?:AARON|ABDUL|ABE|ABEL|ABRAHAM|ABRAM|ADALBERTO|ADAM|ADAN|ADOLFO|ADOLPH|ADRIAN)\b
但这不会很有效率。像树一样构建的正则表达式会更好地工作：
\b(?:A(?:B(?:E(?:|L)|RA(?:M|HAM)|DUL)|D(?:A(?:M|N|LBERTO)|OL(?:FO|PH)|RIAN)|ARON))\bdict
树结构，然后将该树转换为正则表达式。对于上面的例子，中间树看起来像这样：
{
'A': {
'A': {
'R': {
'O': {
'N': {
'': {}
}
}
}
},
'B': {
'D': {
'U': {
'L': {
'': {}
}
}
},
'E': {
'': {},
'L': {
'': {}
}
},
... etc
...可以选择简化为：
{
'A': {
'ARON': {
'': {}
}
'B': {
'DUL': {
'': {}
},
'E': {
'': {},
'L': {
'': {}
}
},
'RA': {
'HAM': {
'': {}
},
'M': {
'': {}
}
}
},
... etc
以下是执行此操作的建议代码：
import re
def addToTree(tree, name):
if len(name) == 0:
return
if name[0] in tree.keys():
addToTree(tree[name[0]], name[1:])
else:
for letter in name:
tree[letter] = {}
tree = tree[letter]
tree[''] = {}
# Optional improvement of the tree: it combines several consecutive letters into
# one key if there are no alternatives possible
def simplifyTree(tree):
repeat = True
while repeat:
repeat = False
for key, subtree in list(tree.items()):
if key != '' and len(subtree) == 1 and '' not in subtree.keys():
for letter, subsubtree in subtree.items():
tree[key + letter] = subsubtree
del tree[key]
repeat = True
for key, subtree in tree.items():
if key != '':
simplifyTree(subtree)
def treeToRegExp(tree):
regexp = [re.escape(key) + treeToRegExp(subtree) for key, subtree in tree.items()]
regexp = '|'.join(regexp)
return '' if regexp == '' else '(?:' + regexp + ')'
def listToRegExp(names):
tree = {}
for name in names:
addToTree(tree, name[:])
simplifyTree(tree)
return re.compile(r'\b' + treeToRegExp(tree) + r'\b', re.I)
# Demo
names = ['AARON',
'ABDUL',
'ABE',
'ABEL',
'ABRAHAM',
'ABRAM',
'ADALBERTO',
'ADAM',
'ADAN',
'ADOLFO',
'ADOLPH',
'ADRIAN',
]
fields = [
'This is Aaron speaking',
'Is Abex a name?',
'Where did Abraham get the mustard from?'
]
regexp = listToRegExp(names)
# get the search result for each field, and link it with the index of the field
results = [[i, regexp.search(field)] for i, field in enumerate(fields)]
# remove non-matches from the results
results = [[i, match.group(0)] for [i, match] in results if match]
# print results
print(results)
https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm），及其 python 实现 pyahocorasick（参见 http://pyahocorasick.readthedocs.io/en/latest/）。
我使用这个库重写了我的代码：
import ahocorasick
names # list of 4000 short static names
fields # list of 10000 retrieved strings
automaton = ahocorasick.Automaton()
for name in names:
automaton.add_word(name, name)
automaton.make_automaton()
def findit_with_ahocorasick(element):
try:
return next(A.iter(element))[1]
except StopIteration:
return None
output = [findit_with_ahocorasick(element) for element in fields]
与我之前所做的相比，执行速度要快得多（即，我用我的数据估计了原始统计数据，大约需要 12 秒，而整个 10000 批次的时间为 0.8 秒）。
此外，正如文档所述，如果单词像我的情况一样是静态的，则可以对 Automaton 对象的初始创建进行腌制，该对象需要提供名称列表才能创建单词树。
set()
并仅检查集合之间的交集，这可能会更快：
names = ['AARON',
'ABDUL',
'ABE',
'ABEL',
'ABRAHAM',
'ABRAM',
'ADALBERTO',
'ADAM',
'ADAN',
'ADOLFO',
'ADOLPH',
'ADRIAN',
]
search = {'BE', 'LFO', 'AB'}
def get_all_substrings(input_string):
length = len(input_string)
return {input_string[i:j+1] for i in range(length) for j in xrange(i,length)}
names_subs = {name: get_all_substrings(name) for name in names}
result = [name for name, sub in names_subs.items() if bool(search.intersection(sub))]