집 > 기사 > 백엔드 개발 > 문자열 일치 알고리즘 예제 코드의 Python 구현

문자열 일치 알고리즘 예제 코드의 Python 구현

小云云원래의: 2017-12-06 09:55:102397검색

이 문서에서는 문자열 일치, 무차별 문자열 일치 및 Horspool 알고리즘의 문제를 포함하여 Python으로 구현된 문자열 일치 알고리즘의 코드 예제를 소개합니다. 필요한 친구는 이에 대해 배울 수 있습니다.

문자열 일치 문제

Python에는 긴 문자열에 하위 문자열이 있는지 확인하는 두 가지 방법이 있습니다. 하나는 str의 find() 함수이고 find() 함수는 하위 문자열만 반환합니다. 일치하는 항목의 시작 위치는 그렇지 않은 경우 -1을 반환합니다. 두 번째는 일치하는 모든 하위 문자열을 반환할 수 있는 re 모듈의 findall 함수입니다.

하지만 findall 함수를 사용하는 경우 문자열에 있는 특수 문자에 주의해야 합니다.

무차별 문자열 일치:

패턴을 텍스트의 첫 번째 m(패턴 길이) 문자로 정렬한 다음 모두 일치하거나 하나가 일치하지 않을 때까지 왼쪽에서 오른쪽으로 해당 문자 쌍을 일치시킵니다. 문자. 후자의 경우 패턴이 오른쪽으로 한 위치 이동됩니다.

코드는 다음과 같습니다.

def string_match(string, sub_str): 
 # 蛮力法字符串匹配 
 for i in range(len(string)-len(sub_str)+1): 
  index = i  # index指向下一个待比较的字符 
  for j in range(len(sub_str)): 
   if string[index] == sub_str[j]: 
    index += 1 
   else: 
    break 
   if index-i == len(sub_str): 
    return i 
 return -1 

if __name__ == "__main__": 
 print(string_match("adbcbdc", "dc"))

최악의 경우 이 알고리즘은 Θ(nm)에 속하며 실제로 이 알고리즘의 평균 효율은 최악의 효율보다 훨씬 좋습니다. 실제로 임의의 텍스트를 검색할 때 효율성은 선형 Θ(n)입니다.

Horspool 알고리즘:

Horspool 알고리즘은 Boyer-Moore 알고리즘의 단순화된 버전으로, 시간과 공간을 교환하는 전형적인 예이기도 합니다. 알고리즘은 패턴 P와 텍스트 T의 시작 문자를 정렬하고, 패턴의 마지막 문자부터 비교를 시작합니다. 비교 시도가 실패하면 패턴이 뒤로 이동합니다. 비교는 각 시도 동안 오른쪽에서 왼쪽으로 이루어집니다.

브루트 포스 알고리즘에서는 패턴의 각 움직임이 문자입니다. Horspool 알고리즘의 핵심 아이디어는 시간 대신 공간을 사용하여 패턴 일치 창의 이동 범위를 늘리는 것입니다. 무차별 대입 알고리즘과 달리 패턴 매칭은 오른쪽에서 왼쪽으로 이루어지며, 각 움직임의 거리는 미리 계산되어 테이블에 저장됩니다.

코드는 다음과 같습니다.

__author__ = &#39;Wang&#39; 
from collections import defaultdict 
def shift_table(pattern): 
 # 生成 Horspool 算法的移动表 
 # 当前检测字符为c，模式长度为m 
 # 如果当前c不包含在模式的前m-1个字符中，移动模式的长度m 
 # 其他情况下移动最右边的的c到模式最后一个字符的距离 
 table = defaultdict(lambda: len(pattern)) 
 for index in range(0, len(pattern)-1): 
  table[pattern[index]] = len(pattern) - 1 - index 
 return table 
def horspool_match(pattern, text): 
 # 实现 horspool 字符串匹配算法 
 # 匹配成功，返回模式在text中的开始部分；否则返回 -1 
 table = shift_table(pattern) 
 index = len(pattern) - 1 
 while index <= len(text) - 1: 
  print("start matching at", index) 
  match_count = 0 
  while match_count < len(pattern) and pattern[len(pattern)-1-match_count] == text[index-match_count]: 
   match_count += 1 
  if match_count == len(pattern): 
   return index-match_count+1 
  else: 
   index += table[text[index]] 
 return -1 

if __name__ == "__main__": 
 print(horspool_match("barber", "jim_saw_me_in_a_barbershopp"))

분명히 Horspool 알고리즘의 효율성이 가장 낮은 것은 Θ(nm)입니다. 임의의 텍스트를 검색할 때 효율성은 선형 Θ(n)입니다. 효율성 유형은 동일하지만 평균적으로 Horspool 알고리즘은 Brute Force 알고리즘보다 훨씬 빠릅니다.

위 내용은 Python에서 문자열 일치 알고리즘을 구현하기 위한 예제 코드입니다. 모두에게 도움이 되기를 바랍니다.

문자열 일치 알고리즘 예제 코드의 Python 구현

관련 기사