Python의 Rabin-Karp 알고리즘

Python에서 Rabin-Karp 알고리즘을 소개하고 이를 Python 프로그램에서 사용할 수 있는 방법에 대해 논의합니다.

Python의 Rabin-Karp 알고리즘

Rabin-Karp 알고리즘은 주어진 입력 또는 값에서 특정 숫자, 문자 또는 패턴을 찾습니다. 기계 학습 알고리즘은 데이터에서 통찰력을 추출해야 하지만 모든 알고리즘이 동일하게 생성되는 것은 아닌 경우 데이터 과학에서 자주 사용되는 솔루션입니다.

일부는 올바른 통찰력을 찾는 데 다른 것보다 낫고 일부는 오 탐지를 피하는 데 다른 것보다 낫습니다. 올바른 통찰력을 찾기 위한 가장 강력한 기계 학습 알고리즘 중 하나는 Rabin-Karp 알고리즘입니다.

Rabin-Karp 알고리즘은 일련의 텍스트와 가능한 암호 사이에서 가장 일치하는 항목을 찾는 데 사용됩니다. 사용자가 비밀번호를 잊어버렸을 때 찾을 수 있도록 소프트웨어에서 주로 사용됩니다.

처음에는 텍스트에서 이메일 주소를 찾기 위해 개발되었으며 그 이후로 전화번호 찾기, PDF에서 텍스트 추출 등과 같은 다른 많은 응용 프로그램에 사용되었습니다. Richard M. Rabin과 Abraham S. Karp가 설계했습니다.

Python에서 Rabin-Karp 알고리즘의 복잡성

Rabin-Karp 알고리즘은 배열에서 고유한 값의 최소 개수를 효율적으로 찾는 방법입니다. 이진 검색, 2차 탐색 및 순차 검색과 같은 다른 일반적인 최소 찾기 알고리즘보다 점근적으로 더 빠른 것으로 입증되었습니다.

그러나 Rabin-Karp 알고리즘은 이론적 최악의 경우 (O(n))의 복잡성보다 훨씬 더 복잡한 경우가 많습니다. 여기서 n은 검색 배열의 개별 값 수입니다. Rabin-Karp 알고리즘은 필요한 값을 찾을 때까지 검색 배열의 각 값을 반복적으로 방문해야 하기 때문에 이러한 복잡성이 있습니다.

Python에서 Rabin-Karp 알고리즘 구현

이제 Python 예제에서 Rabin-Karp 알고리즘을 구현하는 방법을 이해하겠습니다.

문자 패턴을 부여한 후 기존 요소에 주어진 패턴의 가능성을 확인합니다. 패턴이 발견되면 출력으로 제공하십시오.

먼저 추가된 문자 수 값을 입력으로 할당합니다. 우리의 경우 아래와 같이 15를 할당합니다.

# python
numOfChar = 15

세 개의 인수를 사용하는 searchPattern으로 함수를 정의합니다. 첫 번째 인수는 Rabin-Karp 알고리즘을 사용하여 찾고자 하는 패턴입니다.

두 번째 인수는 패턴을 찾을 텍스트입니다. 그리고 마지막 인수는 소수가 될 것입니다.

나중에 길이를 사용할 수 있도록 패턴과 텍스트의 길이를 변수에 할당합니다. 패턴과 텍스트의 해시 값도 설정합니다.

for 루프에서 a 및 b 변수를 정의합니다.

# python
def searchPattern(pattern, text, primeNum):
    patLen = len(pattern)
    txtLen = len(text)
    a = 0
    b = 0
    p = 0  # hash value for pattern
    t = 0  # hash value for txt
    h = 1

Rabin-Karp 알고리즘에서 먼저 아래와 같이 pow(numOfChar, patLen-1)% primeNum 공식을 사용하여 h 값을 찾습니다.

# python
for a in xrange(patLen - 1):
    h = (h * numOfChar) % primeNum

이제 아래와 같이 패턴의 해시 값과 텍스트의 첫 번째 창을 찾습니다.

# python
for a in xrange(patLen):
    p = (numOfChar * p + ord(pattern[a])) % primeNum
    t = (numOfChar * t + ord(text[a])) % primeNum

또 다른 for 루프를 만들어 패턴을 텍스트 위로 하나씩 슬라이드합니다. 이 for 루프 내에서 현재 텍스트 및 패턴 창의 해시 값을 확인합니다.

해시 값이 일치하면 아래와 같이 문자를 하나씩 확인합니다.

# python
for a in range(txtLen - patLen + 1):

    if p == t:
        for b in range(patLen):
            if text[a + b] != pattern[b]:
                break

        b += 1
        if b == patLen:
            print("Pattern found at index " + str(a))

    if a < txtLen - patLen:
        t = (numOfChar * (t - ord(text[a]) * h) + ord(text[a + patLen])) % primeNum

        if t < 0:
            t = t + primeNum

이제 아래와 같이 매개 변수에 값을 할당하고 함수를 호출하여 어떻게 작동하는지 확인하겠습니다.

# python
text = "ABBAABCDEAABBDCAABB"
pattern = "ABB"
primeNum = 101
searchPattern(pattern, text, primeNum)

출력:

보시다시피 우리의 패턴은 세 곳의 다른 위치에서 발견되었습니다. Rabin-Karp 알고리즘을 사용하여 여러 위치에서 주어진 텍스트의 패턴을 찾을 수 있습니다.