Pythonでいくつかの部分文字列のどれかを見つける最も効率的な方法は何ですか？

Question

可能な部分文字列のリストがあります。 ['cat'、 'fish'、 'dog']。実際には、リストには数百のエントリが含まれています。

私は文字列を処理しています。私が探しているのは、これらの部分文字列の最初の出現のインデックスを見つけることです。

は、結果は3である「012cat」のため、明確にするため、および「0123dog789cat」の結果は、私がまた見つかった部分文字列を知る必要があり4.

である（例えば、サブストリングのリストまたはテキスト内のインデックスそれ自体、または少なくとも一致した部分文字列の長さ）。

これを達成するための明白な強引な方法があります。私はそこにエレガントなPython/Regexソリューションがあるのか​​疑問に思いました。

おかげで、 ラックス

Answer 1

私は正規表現を引き受ける概念的正規表現はDFAとしてモデル化され、入力はすべての一致を消費しているようので、個別にサブストリングごとの検査よりも優れています同時にテストされています（入力文字列を1回スキャンします）。

だから、ここの例である：

import re 

def work(): 
    to_find = re.compile("cat|fish|dog") 
    search_str = "blah fish cat dog haha" 
    match_obj = to_find.search(search_str) 
    the_index = match_obj.start() # produces 5, the index of fish 
    which_word_matched = match_obj.group() # "fish" 
    # Note, if no match, match_obj is None 

UPDATE：代替語の単一パターン内の単語を組み合わせる場合 いくつかの注意が必要です。次のコードは正規表現を構築しますが、escapes any regex special charactersと長い単語が同じ単語のいずれかの短いプレフィックス前に照合するチャンスを得るように言葉を並べ替え：

def wordlist_to_regex(words): 
    escaped = map(re.escape, words) 
    combined = '|'.join(sorted(escaped, key=len, reverse=True)) 
    return re.compile(combined) 

>>> r.search('smash atomic particles').span() 
(6, 10) 
>>> r.search('visit usenet:comp.lang.python today').span() 
(13, 29) 
>>> r.search('a north\south division').span() 
(2, 13) 
>>> r.search('012cat').span() 
(3, 6) 
>>> r.search('0123dog789cat').span() 
(4, 7) 

ENDのUPDATE

それはずできるだけregex（つまり、re.compile（）への呼び出し）を形成したいと思うでしょう。最良のケースは、検索結果が何であるかを事前に知っているか（または一度しか/頻繁に計算しないで）、re.compileの結果をどこかに保存することです。私の例は単純なナンセンス関数なので、正規表現の使い方を見ることができます。

http://docs.python.org/library/re.html

・ホープ、このことができます：ここにいくつかのより多くの正規表現のドキュメントがあります。

UPDATE：私は（）（たとえば、あなたが "にどのように多くの単語を試すことができますPythonは正規表現を実装する方法について不明な点ですが、re.compileの制限があるかどうかについてのラックスの質問に答えるために| "を一度に一致させるために）、そしてコンパイルを実行する時間の長さ：どちらも問題ではないようです。私はこのコードを試しましたが、それは私を説得するのに十分です。 （タイミングや報告結果を追加するだけでなく、単語のリストをセットに入れて重複がないようにすることで、これをよりうまくできたかもしれません...しかし、これらの改善はどちらも過剰なものです）。このコードは基本的には瞬時に実行され、2000ワード（サイズ10）を検索できることを私に確信させました。そして、それらのワードは適切に一致します。

import random 
import re 
import string 
import sys 

def main(args): 
    words = [] 
    letters_and_digits = "%s%s" % (string.letters, string.digits) 
    for i in range(2000): 
     chars = [] 
     for j in range(10): 
      chars.append(random.choice(letters_and_digits)) 
     words.append(("%s"*10) % tuple(chars)) 
    search_for = re.compile("|".join(words)) 
    first, middle, last = words[0], words[len(words)/2], words[-1] 
    search_string = "%s, %s, %s" % (last, middle, first) 
    match_obj = search_for.search(search_string) 
    if match_obj is None: 
     print "Ahhhg" 
     return 
    index = match_obj.start() 
    which = match_obj.group() 
    if index != 0: 
     print "ahhhg" 
     return 
    if words[-1] != which: 
     print "ahhg" 
     return 

    print "success!!! Generated 2000 random words, compiled re, and was able to perform matches." 

if __name__ == "__main__": 
    main(sys.argv) 

UPDATE：物事の順序がを重要正規表現で一緒に論理和（OR）ことに留意すべきであるここでは、コードです。/- ：

>>> search_str = "01catdog" 
>>> test1 = re.compile("cat|catdog") 
>>> match1 = test1.search(search_str) 
>>> match1.group() 
'cat' 
>>> match1.start() 
2 
>>> test2 = re.compile("catdog|cat") # reverse order 
>>> match2 = test2.search(search_str) 
>>> match2.group() 
'catdog' 
>>> match2.start() 
2 

これは注文事項を示唆：TZOTZIOYに触発され、次のテストを見てみましょう。私はこれがRaxのアプリケーションにとって何を意味するのかよくわかりませんが、少なくともその動作はわかっています。

UPDATE：私はうまくいけば、私たちにこの質問に見つかった問題にいくつかの洞察力を与えるであろうthis questions about the implementation of regular expressions in Pythonを掲載。

Answer 2

subs = ['cat', 'fish', 'dog'] 
sentences = ['0123dog789cat'] 

import re 

subs = re.compile("|".join(subs)) 
def search(): 
    for sentence in sentences: 
     result = subs.search(sentence) 
     if result != None: 
      return (result.group(), result.span()[0]) 

# ('dog', 4) 

Answer 3

これはコードが提供されていない漠然とした理論的な回答ですが、正しい方向に向けることを願っています。

まず、部分文字列リストを効率的に検索する必要があります。私は木構造のいくつかの並べ替えをお勧めします。ルートから始めて、部分文字列が'a'で始まる場合は'a'ノードを追加し、'b'で始まる部分文字列がある場合は'b'ノードを追加します。これらのノードごとに、サブノードの追加を続けます。例えば

あなたが単語「アリ」の部分文字列を持っている場合、あなたは、ルートノード、子ノード'a'、孫ノード'n'、そして偉大な孫ノード't'を持っている必要があります。

ノードは簡単に作成することができます。

class Node(object): 
    children = [] 

    def __init__(self, name): 
     self.name = name 

ここで、nameは文字です。

文字列を文字で繰り返します。自分がどのレターを持っているかを記録しておく。それぞれの手紙で、次の数文字を使って木を横切ってみてください。成功した場合は、文字列が部分文字列の位置になり、トラバーサル順序で見つかった部分文字列が表示されます。

編集を明確にする：DFAはこの方法よりもはるかに速くなければならないので、Tom's answerを保証する必要があります。あなたのサブストリングリストが頻繁に変更された場合に備えて、この答えを保持しているだけです。その場合は、ツリーを使用してが速くなる可能性があります。

Answer 4

最初に、最初のリストを昇順でソートすることをお勧めします。短い部分文字列を検索する方が、長い部分文字列を検索する方が高速です。

Answer 5

これはどうですか。

>>> substrings = ['cat', 'fish', 'dog'] 
>>> _string = '0123dog789cat' 
>>> found = map(lambda x: (_string.index(x), x), filter(lambda x: x in _string, substrings)) 
[(10, 'cat'), (4, 'dog')] 
>>> if found: 
>>>  min(found, key=lambda x: x[0]) 
(4, 'dog') 

明らかに、タプル以外のものを返すことができます。

これはで動作します。ストリングのインデックス、およびサブ

の場合を含むタプルのリストを構築する文字列であるもの

までのサブストリングのリストをフィルタリング

• サブストリングが見つかった場合は、インデックスに基づいて最小値を見つける

Answer 6

DisplacedAussieの回答とTomの回答の時間差を指摘したいだけです。一度使用された場合の両方が速かったので、あなたは、どちらかのために顕著な待機を持つべきではないが、あなたはそれらを時間を計るとき：

import random 
import re 
import string 

words = [] 
letters_and_digits = "%s%s" % (string.letters, string.digits) 
for i in range(2000): 
    chars = [] 
    for j in range(10): 
     chars.append(random.choice(letters_and_digits)) 
    words.append(("%s"*10) % tuple(chars)) 
search_for = re.compile("|".join(words)) 
first, middle, last = words[0], words[len(words)/2], words[-1] 
search_string = "%s, %s, %s" % (last, middle, first) 

def _search(): 
    match_obj = search_for.search(search_string) 
    # Note, if no match, match_obj is None 
    if match_obj is not None: 
     return (match_obj.start(), match_obj.group()) 

def _map(): 
    search_for = search_for.pattern.split("|") 
    found = map(lambda x: (search_string.index(x), x), filter(lambda x: x in search_string, search_for)) 
    if found: 
     return min(found, key=lambda x: x[0]) 


if __name__ == '__main__': 
    from timeit import Timer 


    t = Timer("_search(search_for, search_string)", "from __main__ import _search, search_for, search_string") 
    print _search(search_for, search_string) 
    print t.timeit() 

    t = Timer("_map(search_for, search_string)", "from __main__ import _map, search_for, search_string") 
    print _map(search_for, search_string) 
    print t.timeit() 

出力：

(0, '841EzpjttV') 
14.3660159111 
(0, '841EzpjttV') 
# I couldn't wait this long 

私は両方のために、トムの答えとなるだろう読みやすさ、スピードを向上させます。