[PYTHON] 파이썬에서 여러 부분 문자열 중 하나를 찾는 가장 효율적인 방법은 무엇입니까?

파이썬에서 여러 부분 문자열 중 하나를 찾는 가장 효율적인 방법은 무엇입니까?

가능한 하위 문자열 목록이 있습니다 (예 : [ 'cat', 'fish', 'dog']. 실제로 목록에는 수백 개의 항목이 들어 있습니다.

나는 문자열을 처리하고 있는데, 내가 찾고있는 것은 이들 부분 문자열의 첫 등장 색인을 찾는 것이다.

명확하게하기 위해 '012cat'의 결과는 3이고 '0123dog789cat'의 결과는 4입니다.

또한 하위 문자열 (예 : 하위 문자열 목록 또는 텍스트 자체의 색인) 또는 일치하는 하위 문자열의 길이를 알아야합니다.

이것을 구현하는 명백한 무차별 대항력 방법이 있습니다. 이에 대한 우아한 Python / Regex 솔루션이 있는지 궁금합니다.

감사, Rax

해결법

1. ==============================

   1.정규 표현식이 DFA로 모델링되어 개념적으로 입력이 소비 될 때마다 모든 일치가 동시에 테스트되므로 (결과적으로 입력 문자열을 한 번 스캔하면 정규 표현식이 각 하위 문자열을 개별적으로 검사하는 것보다 낫다고 가정합니다. ).

   정규 표현식이 DFA로 모델링되어 개념적으로 입력이 소비 될 때마다 모든 일치가 동시에 테스트되므로 (결과적으로 입력 문자열을 한 번 스캔하면 정규 표현식이 각 하위 문자열을 개별적으로 검사하는 것보다 낫다고 가정합니다. ).

   여기 예제가 있습니다.

   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)
   

   최종 업데이트

   regex (ie - re.compile ()에 대한 호출)를 가능한 한 적게 작성해야한다는 점에 유의해야합니다. 가장 좋은 경우는 사전에 검색 결과를 알고 (또는 한 번 / 자주 검색하지 않고) re.compile의 결과를 어딘가에 저장하는 것입니다. 내 예제는 단지 간단한 말도 안되는 함수이므로 정규식의 사용법을 볼 수 있습니다. 몇 가지 정규식 문서가 있습니다.

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

   희망이 도움이됩니다.

   업데이트 : 파이썬이 정규식을 구현하는 방법에 대해 확신 할 수는 없지만 re.compile ()의 제한 사항에 대한 Rax의 질문에 대답하기 위해 (예 : 한 번에 "|" , 그리고 컴파일을 실행하는 데 걸리는 시간 : 이들 중 어느 것도 문제가 아닌 것 같습니다. 나는이 코드를 시험해 보았다. 그것은 나를 설득하기에 충분하다. (타이밍과보고 결과를 추가하고 단어 목록을 세트에 포함시켜 중복이 없음을 확인하면 더 좋게 만들 수 있지만 이러한 개선 사항 모두는 잔인한 것으로 보입니다.) 이 코드는 기본적으로 즉시 실행되었으며 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)
   

   업데이트 : 그것은 정규식 문제에서 함께 ORed 것들의 순서를 지적한다. 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의 응용 프로그램에 어떤 의미인지는 모르겠지만 적어도 그 동작은 알려져 있습니다.

   업데이트 : 파이썬에서 정규 표현식 구현에 관한이 질문을 올렸습니다. 그러면이 질문에서 발견 된 문제에 대한 통찰력을 얻을 수 있습니다.

2. ==============================

   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)
   

3. ==============================

   3.DisplacedAussie의 대답과 Tom의 대답 사이의 시간차를 지적하고 싶습니다. 한 번 사용하면 둘 다 빠르므로 한 번 더 기다릴 필요는 없지만 시간을 할애해야합니다.

   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
   

   나는 가독성과 속도 모두를 위해 Tom의 대답과 함께 갈 것입니다.

4. ==============================

   4.이는 코드가 제공되지 않는 모호하고 이론적 인 대답이지만 올바른 방향으로 나에게 알려줄 수 있기를 바랍니다.

   이는 코드가 제공되지 않는 모호하고 이론적 인 대답이지만 올바른 방향으로 나에게 알려줄 수 있기를 바랍니다.

   첫째, 하위 문자열 목록을보다 효율적으로 조회해야합니다. 나는 일종의 나무 구조를 추천 할 것이다. 루트로 시작한 다음 하위 문자열이 'a'로 시작하면 'a'노드를 추가하고 'b'로 시작하는 하위 문자열이 있으면 'b'노드를 추가하십시오. 이 노드들 각각에 대해 하위 노드를 계속 추가하십시오.

   예를 들어 "ant"라는 단어가있는 하위 문자열이있는 경우 루트 노드, 자식 노드 'a', 손자 노드 'n'및 위대한 손자 노드 't'가 있어야합니다.

   노드는 쉽게 만들 수 있어야합니다.

   class Node(object):
       children = []
   
       def __init__(self, name):
           self.name = name
   

   여기서 name은 문자입니다.

   문자로 문자열을 반복합니다. 현재 사용중인 편지를 추적하십시오. 각 글자에서 다음 몇 글자를 사용하여 나무를 가로 질러보십시오. 성공하면 문자 번호가 부분 문자열의 위치가되며 통과 명령은 발견 된 부분 문자열을 나타냅니다.

   명확한 편집 : DFA는이 방법보다 훨씬 빠르며 Tom의 대답을지지해야합니다. 난 당신의 하위 문자열 목록이 자주 변경되는 경우에만이 답변을 유지하고 있는데,이 경우 트리를 사용하는 것이 더 빠를 수도 있습니다.

5. ==============================

   5.우선, 초기 목록을 오름차순으로 정렬하는 것이 좋습니다. 더 짧은 하위 문자열을 검색하면 더 긴 하위 문자열을 검색 할 때보 다 빠릅니다.

   우선, 초기 목록을 오름차순으로 정렬하는 것이 좋습니다. 더 짧은 하위 문자열을 검색하면 더 긴 하위 문자열을 검색 할 때보 다 빠릅니다.

6. ==============================

   6.이건 어때.

   이건 어때.

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

   분명히 튜플이 아닌 다른 것을 반환 할 수 있습니다.

   이것은 다음에 의해 작동합니다 :

from https://stackoverflow.com/questions/842856/whats-the-most-efficient-way-to-find-one-of-several-substrings-in-python by cc-by-sa and MIT license