Wu-Manber 알고리즘 소개 및 Python 구현 지침

Wu-Manber 알고리즘은 문자열을 효율적으로 검색하는 데 사용되는 문자열 일치 알고리즘입니다. Boyer-Moore 알고리즘과 Knuth-Morris-Pratt 알고리즘의 장점을 결합한 하이브리드 알고리즘으로 빠르고 정확한 패턴 매칭을 제공합니다.

Wu-Manber 알고리즘 단계

1. 패턴의 가능한 각 하위 문자열을 해당 하위 문자열이 발생하는 패턴 위치에 매핑하는 해시 테이블을 만듭니다.

2. 이 해시 테이블은 텍스트에서 패턴의 잠재적 시작 위치를 빠르게 식별하는 데 사용됩니다.

3. 텍스트를 반복하면서 각 문자를 패턴의 해당 문자와 ​​비교합니다.

4. 문자가 일치하면 다음 문자로 이동하여 계속 비교할 수 있습니다.

5. 문자가 일치하지 않으면 해시 테이블을 사용하여 패턴의 다음 잠재적 시작 위치 전에 건너뛸 수 있는 최대 문자 수를 결정할 수 있습니다.

6. 이를 통해 알고리즘은 잠재적인 일치 항목을 놓치지 않고 텍스트의 많은 부분을 빠르게 건너뛸 수 있습니다.

Python은 Wu-Manber 알고리즘을 구현합니다

# Define the hash_pattern() function to generate
# a hash for each subpattern


def hashPattern(pattern, i, j):
h = 0
for k in range(i, j):
h = h * 256 + ord(pattern[k])
return h

# Define the Wu Manber algorithm


def wuManber(text, pattern):

# Define the length of the pattern and
# text
m = len(pattern)
n = len(text)

# Define the number of subpatterns to use
s = 2

# Define the length of each subpattern
t = m // s

# Initialize the hash values for each
# subpattern
h = [0] * s
for i in range(s):
h[i] = hashPattern(pattern, i * t, (i + 1) * t)

# Initialize the shift value for each
# subpattern
shift = [0] * s
for i in range(s):
shift[i] = t * (s - i - 1)

# Initialize the match value
match = False

# Iterate through the text
for i in range(n - m + 1):
# Check if the subpatterns match
for j in range(s):
if hashPattern(text, i + j * t, i + (j + 1) * t) != h[j]:
break
else:
# If the subpatterns match, check if
# the full pattern matches
if text[i:i + m] == pattern:
print("Match found at index", i)
match = True

# Shift the pattern by the appropriate
# amount
for j in range(s):
if i + shift[j] < n - m + 1:
break
else:
i += shift[j]

# If no match was found, print a message
if not match:
print("No match found")


# Driver Code
text = "the cat sat on the mat"
pattern = "the"

# Function call
wuManber(text, pattern)

KMP와 Wu-Manber 알고리즘의 차이점

KMP 알고리즘과 Wu Manber 알고리즘은 모두 문자열 일치 알고리즘이므로 둘 다 사용됩니다. 더 큰 문자열. 두 알고리즘 모두 시간 복잡도가 동일합니다. 즉, 알고리즘을 실행하는 데 걸리는 시간 측면에서 성능 특성이 동일하다는 의미입니다.

그러나 이들 사이에는 몇 가지 차이점이 있습니다.

1 KMP 알고리즘은 문자열 일치 프로세스 속도를 높이는 데 사용되는 부분 일치 테이블을 생성하는 전처리 단계를 사용합니다. 이는 검색되는 패턴이 상대적으로 길 때 Wu Manber 알고리즘보다 KMP 알고리즘을 더 효율적으로 만듭니다.

2. Wu Manber 알고리즘은 문자열 일치를 위해 다른 방법을 사용합니다. 패턴을 여러 하위 패턴으로 나누고 이러한 하위 패턴을 사용하여 텍스트에서 일치하는 항목을 검색합니다. 이는 검색되는 패턴이 상대적으로 짧을 때 KMP 알고리즘보다 Wu Manber 알고리즘을 더 효율적으로 만듭니다.

위 내용은 Wu-Manber 알고리즘 소개 및 Python 구현 지침의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!