可能な部分文字列のリストがあります['cat', 'fish', 'dog']。実際には、リストには何百ものエントリが含まれています。
私は文字列を処理しています。私が探しているのは、これらの部分文字列のいずれかの最初の出現のインデックスを見つけることです。
明確にするために'012cat'、結果は3であり'0123dog789cat'、結果は4です。
また、どの部分文字列が見つかったか（たとえば、部分文字列リスト内のインデックスまたはテキスト自体）、または少なくとも一致した部分文字列の長さを知る必要があります。
これを達成するための明白なブルートフォースの方法があります、私はこれのためのエレガントなPython/正規表現ソリューションがあるかどうか疑問に思いました。
概念的には正規表現は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
更新: 単語を組み合わせて代替単語の単一パターンにする場合は、注意が必要です。次のコードは正規表現を作成しますが、正規表現の特殊文字をすべてエスケープし、単語を並べ替えて、長い単語が同じ単語の短い接頭辞より前に一致する機会を得るようにします。
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)
更新を終了
正規表現 (つまり、re.compile() の呼び出し) をできるだけ少なくしたいことに注意してください。最良のケースは、検索が何であるかを事前に知っており (または、検索を 1 回またはまれに計算し)、re.compile の結果をどこかに保存することです。私の例は単なる意味のない関数なので、正規表現の使用法を確認できます。ここにいくつかの正規表現ドキュメントがあります：
http://docs.python.org/library/re.html
お役に立てれば。
更新: Python が正規表現をどのように実装しているかはわかりませんが、re.compile() の制限があるかどうかについての Rax の質問に答えるために (たとえば、一度に一致させるために "|" を一緒に試行できる単語の数) 、およびコンパイルの実行時間: どちらも問題ではないようです。私はこのコードを試してみましたが、これは私を納得させるのに十分です. (タイミングを追加して結果を報告し、単語のリストをセットに入れて重複がないようにすることで、これを改善できたかもしれませんが、これらの改善はどちらもやり過ぎのようです)。このコードは基本的に瞬時に実行され、(サイズが 10 の) 2000 語を検索できること、およびそれらが適切に一致することを確信しました。コードは次のとおりです。
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)
更新:正規表現で論理和をとったものの順序が重要であることに注意してください。TZOTZIOYに触発された次のテストを見て。
>>> 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
これは、順序が重要であることを示唆しています:-/。これが Rax のアプリケーションにとって何を意味するのかはわかりませんが、少なくとも動作はわかっています。
更新: Python での正規表現の実装に関するこの質問を投稿しました。これにより、この質問で見つかった問題についての洞察が得られることを願っています。
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)
DisplacedAussie の回答と Tom の回答の時間差を指摘したいだけです。どちらも 1 回使用すると高速だったので、どちらも目立った待ち時間はありませんが、時間を計ると次のようになります。
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
読みやすさと速度の両方について、トムの答えに行きます。
これは、コードが提供されていない漠然とした理論的な答えですが、正しい方向に向けられることを願っています.
まず、部分文字列リストのより効率的なルックアップが必要になります。ある種のツリー構造をお勧めします。ルートから'a'開始し、部分文字列が で始まる場合はノード'a'を追加し、部分文字列が で始まる場合はノードを追加します。これらのノードごとに、サブノードを追加し続けます。'b''b'
たとえば、「ant」という単語を含む部分文字列がある場合、ルート ノード、子ノード'a'、孫ノード'n'、ひ孫ノードが必要't'です。
ノードは簡単に作成できるはずです。
class Node(object):
children = []
def __init__(self, name):
self.name = name
キャラクターはどこnameですか。
文字列を文字ごとに繰り返し処理します。自分がどの文字にいるかを追跡します。各文字で、次の数文字を使用してツリーをトラバースしてみてください。成功すると、文字番号が部分文字列の位置になり、走査順序は見つかった部分文字列を示します。
編集の明確化: DFA はこの方法よりもはるかに高速である必要があるため、Tom の回答を支持する必要があります。部分文字列リストが頻繁に変更される場合にのみ、この回答を維持しています。その場合、ツリーを使用する方が速い場合があります。
まず、最初のリストを昇順にソートすることをお勧めします。短い部分文字列のスキャンは、長い部分文字列のスキャンよりも高速であるためです。
これはどう。
>>> 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')
明らかに、タプル以外のものを返すことができます。
これは次のように機能します。