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

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批）。

此外，作爲文檔的狀態，自動機對象的初始創建，如果單詞是靜態的，那麼需要用名稱列表來提供以創建單詞樹，如果單詞是靜態的案件。