检查字符串是否是字符串列表中的子字符串的最快方法

Question

我有一个包含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万。

有没有一种算法来优化这种搜索？

Answer 1

你可以看看把你的名字列表变成一个正则表达式。举个例子名称这个小名单：

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))\b

然后，您可以自动化生产这个正则表达式的 - 首先从名称列表创建dict - 树结构可能和然后将该树翻译成正则表达式。对于上面的例子，这中间的树应该是这样的：

{ 
    '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) 

看到它在repl.it

Answer 2

来看，我觉得这可能会更快，如果你AR E可使用输入的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))] 

Answer 3

我已经发现了关于阿霍Corasick算法的多字符串搜索（见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秒VS0.8秒为：

我使用这个库改写了我的代码整个10000批）。

此外，作为文档的状态，自动机对象的初始创建，如果单词是静态的，那么需要用名称列表来提供以创建单词树，如果单词是静态的案件。