라빈-카프 알고리즘

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오.(2018년 9월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

컴퓨터 과학에서 라빈-카프 알고리즘이나 카프-라빈 알고리즘은 텍스트에서 패턴 문자열의 정확한 일치를 찾기 위해 해싱을 사용하는 리처드 M. 카프와 마이클 O. 라빈(1987)이 만든 문자열 검색 알고리즘이다.롤링 해시를 사용해 패턴과 일치하지 않는 텍스트 위치를 빠르게 걸러낸 뒤 나머지 위치에서 일치 여부를 확인한다.동일한 아이디어의 일반화는 단일 패턴의 둘 이상의 일치점을 찾거나 둘 이상의 패턴에 대한 일치점을 찾는데 사용될 수 있다.

단일 패턴의 단일 일치를 찾기 위해 알고리즘의 예상 시간은 패턴과 텍스트의 조합된 길이로 선형이지만 최악의 경우 시간 복잡성은 두 길이의 곱이다.여러 개의 일치 항목을 찾으려면 입력 길이에 모든 일치 항목의 조합 길이가 선형이며, 이는 선형보다 클 수 있다.이와는 대조적으로 아호-코라식 알고리즘은 입력 길이와 일치 횟수(일치 총 길이 대신)에서 최악의 경우 시간 및 공간 선형에서 다중 패턴의 모든 일치를 찾을 수 있다.

그 알고리즘의 실질적인 적용은 표절을 탐지하는 것이다.알고리즘은 주어진 소스 자료를 통해 대소문자, 구두점 등의 세부사항을 무시하고 소스 자료에서 문장 예시를 신속하게 검색할 수 있다.찾는 문자열이 풍부하기 때문에 단일 문자열 검색 알고리즘은 비현실적이다.

개요

순진한 문자열 매칭 알고리즘은 주어진 패턴을 주어진 텍스트의 모든 위치와 비교한다.각각의 비교는 패턴의 길이에 비례하는 시간이 걸리고, 위치의 수는 텍스트의 길이에 비례한다.따라서 그러한 방법에 대한 최악의 시간은 두 길이의 곱에 비례한다.많은 실제 사례에서 불일치가 발견되는 즉시 각 포지션의 비교를 줄임으로써 이 시간을 크게 줄일 수 있지만, 이 아이디어는 속도 향상을 보장할 수 없다.

Knuth-Morris-Pratt 알고리즘과 Boyer-Moore 문자열 검색 알고리즘을 포함한 여러 문자열 매칭 알고리즘은 각 불일치에서 더 많은 정보를 추출하여 문자열 매칭에 대한 최악의 시간을 줄여 패턴과 일치하지 않는다고 보장된 텍스트의 위치를 건너뛸 수 있게 한다.대신 라빈-카프 알고리즘은 해시 함수를 사용하여 각 위치에 대해 대략적인 검사를 신속하게 수행한 다음, 이 대략적인 검사를 통과한 위치에서만 정확한 비교를 수행함으로써 속도 상승을 달성한다.

해시함수는 모든 문자열을 그 해시값이라고 불리는 숫자값으로 변환하는 함수다. 예를 들어, 우리는hash("hello")=5. 두 문자열이 동일하면 해시 값도 동일하다.잘 설계된 해시함수의 경우, 역행은 대략적인 의미에서 참이다. 즉, 동일하지 않은 문자열은 해시 값이 같을 가능성이 매우 낮다.라빈-카프 알고리즘은 텍스트의 각 위치에서 패턴과 같은 길이로 해당 위치에서 시작하는 문자열의 해시 값을 계산하여 진행한다.이 해시 값이 패턴의 해시 값과 같으면, 그 위치에서 완전한 비교를 수행한다.

이것이 잘 작동하기 위해서는 패턴과 해시 값이 같지만 실제로 패턴과 일치하지 않는 텍스트의 위치인 많은 잘못된 긍정을 생성할 가능성이 없는 해시함수 제품군에서 무작위로 해시함수를 선택해야 한다.이러한 위치는 일치를 생성하지 않고 불필요하게 알고리즘의 실행 시간에 기여한다.또한, 사용되는 해시함수는 롤링 해시(Rolling Hash)로, 텍스트의 각 위치에서 다음 위치로 값을 빠르게 업데이트할 수 있는 해시함수여야 한다.각 위치에서 해시함수를 처음부터 다시 계산하는 것은 너무 느릴 것이다.

알고리즘

알고리즘은 다음과 같다.

기능을 하다 라빈카프(끈을 매다 s[1..n], 끈을 매다 무늬를 넣다[1..m])     무늬가 있는 := 해시하다(무늬를 넣다[1..m]);     을 위해 i 로부터 1 로 n-m+1         hs := 해시하다(s[i..i+m-1])         만일 hs = 무늬가 있는             만일 s[i..i+m-1] = 무늬를 넣다[1..m]                 돌아오다 i     돌아오다 아닌 찾았다 

라인 2, 4, 6은 각각 O(m) 시간이 필요하다.단, 2행은 1회만 실행되며, 6행은 해시 값이 일치하는 경우에만 실행되므로 몇 번 이상 실행될 가능성은 낮다.라인 5는 O(n)번 실행되지만, 각각의 비교는 일정한 시간만을 필요로 하기 때문에 그 영향은 O(n)이다.쟁점은 4호선이다.

하위 문자열에 대한 해시 값 순수하게 계산s[i+1..i+m]각 문자를 검사하기 때문에 O(m) 시간이 필요하다.해시 계산은 각 루프에서 이루어지기 때문에, nohav 해시 계산이 있는 알고리즘은 O(mn) 시간이 필요한데, 이는 간단한 문자열 매칭 알고리즘과 동일한 복잡성이다.속도를 위해 해시는 일정한 시간 내에 계산해야 한다.비결은 변수다.hs이전 해시 값을 이미 포함함s[i..i+m-1]만약 그 값이 다음 해시 값을 일정한 시간에 계산하는 데 사용될 수 있다면, 연속 해시 값의 계산은 빠를 것이다.

그 트릭은 롤링 해시를 이용하여 이용할 수 있다.롤링 해시는 이 작업을 가능하게 하기 위해 특별히 고안된 해시함수다.사소한 롤링 해시함수는 하위 문자열에서 각 문자의 값을 추가하기만 하면 된다.이 롤링 해시 수식은 이전 값에서 다음 해시 값을 일정한 시간 내에 계산할 수 있다.

s[i+1..i+m] = s[i+m]i+m-1] - s[i] + s[i+m]

이 간단한 함수는 작동하지만 다음 절에서 논의된 것과 같은 다른 보다 정교한 롤링 해시함수보다 문 5가 더 자주 실행될 것이다.

좋은 성능은 마주친 데이터에 대해 좋은 해싱 기능을 필요로 한다.해싱이 불량할 경우(예: 모든 입력에 대해 동일한 해시 값을 생성하는 경우), 라인 6은 O(n)번 실행된다(즉, 루프의 모든 반복에서).길이 m인 문자열의 문자별 비교는 O(m) 시간이 걸리기 때문에 전체 알고리즘은 최악의 경우 O(mn) 시간이 걸린다.

사용된 해시함수

라빈-카프 알고리즘의 성능의 핵심은 텍스트의 연속적인 서브스트링의 해시값의 효율적인 계산이다.라빈 지문은 대중적이고 효과적인 롤링 해시함수다.여기서 설명하는 해시함수는 라빈 지문이 아니라 똑같이 잘 작동한다.그것은 모든 하위 문자열을 어떤 기본에서 숫자로 취급하며, 기본은 보통 문자 집합의 크기가 된다.

예를 들어, 하위 문자열이 "hi"이고, 베이스가 256이고, 프라임 계수가 101이라면, 해시 값은 다음과 같다.

[(104 × 256 ) % 101 + 105] % 101 = 65 ('h'의 ASCII는 104이고, 'i'는 105)

_{'%'는 'mod' 또는 modulo이며, 정수 분할 후 나머지 연산자}

기술적으로 이 알고리즘은 십진수 이외의 시스템 표현에서 실제 숫자와 유사할 뿐인데, 예를 들어 "밑수"가 "밑수" 중 하나보다 작을 수 있기 때문이다.자세한 내용은 해시 함수를 참조하십시오.라빈 지문과 같은 롤링 해시를 사용함으로써 얻어지는 본질적인 이점은 서브스트링의 길이에 관계 없이 일정한 수의 연산만을 수행함으로써 이전 서브스트링의 해시값을 계산할 수 있다는 것이다.

예를 들어 "abracadabra"라는 텍스트가 있고 길이 3의 패턴을 검색하고 있다면, 256을 베이스로 하는 첫 번째 하위 문자열 "abr"의 해시, 그리고 프라임 계수의 101은 다음과 같다.

// ASCII a = 97, b = 98, r = 114.해시사브르" = [ ([ (97 × 256) % 101 + 98 ] % 101 ) × 256 ] + 114 ] % 101 = 4

그런 다음 "abr"의 첫 번째 'a'에 추가된 숫자, 즉 97 × 256을² 베이스에 곱하고 "bra"의 마지막 a에 더하여 "bra" 즉 97 × 256을⁰ "abr"의 해시에서 다음 하위 문자열인 "bra"의 해시를 계산할 수 있다.이와 같이:

// 이전 해시(-ve feeter)* 이전 'a' 좌측 베이스 오프셋 새로운 'a' prime modulus hashbra') = [ (4 + 101 - 97 * [(256%101)*256] 101] * 256 + 97 ] 101 = 30

_{*(-ve feeter) = "언더플로 피서"계산에 부호 없는 정수를 사용하는 경우 필요.prime modulus $p$에$$ 대한 모든 해시 h$$ ${\displaystyle p}$ {\$displaystyle$ h$\leq$p}를 알고 있기 때문에, 구 'a'(mod p)에 해당하는 값을 빼기 전에 구 해시에 p를 더하면 언더플로우가 발생하지 않도록 보장할 수 있다.}

_{마지막 '* 256'은 감산된 해시를 왼쪽으로 이동시키는 것이다.}

_{(256%101)*256 %101은 256² % 101과 동일하지만, 패턴 문자열이 길 때 정수 최대값이 넘쳐나지 않도록(예: 'Rabin-Karp'은 10자, 256은⁹ 변조 없는 오프셋임) 패턴 길이 베이스 오프셋을 루프로 미리 계산하여 각 반복 결과를 변조한다.}

유사한 해시("abr") 계산을 사용하여 검색 문자열 "bra"를 일치시키는 경우,

해시'("bra") = [ ([ ( 98 × 256) %101 + 114] %101 % 101 ) × 256 % ] + 97 ] % 101 = 30

만약 문제의 하위 문자열들이 길다면, 이 알고리즘은 많은 다른 해싱 계획들에 비해 큰 절약을 달성한다.

이론적으로, 편리한 재조합을 제공할 수 있는 다른 알고리즘이 존재한다. 예를 들어, 이동 중인 하위 문자열은 이전 해시를 첫 번째 문자 값으로 나눈 다음 새로운 마지막 문자 값으로 곱하는 것을 수반한다.그러나 제한은 정수 데이터 유형의 제한된 크기와 해시 결과를 축소하기 위해 모듈식 산술을 사용해야 하는 필요성이다(해시 함수 기사 참조).한편 순진한 해시함수는 많은 숫자를 빨리 만들어내지 못하지만 ASCII 값을 추가하는 것과 마찬가지로 해시 충돌이 많이 일어나 알고리즘이 느려질 가능성이 높다.따라서 기술된 해시함수는 일반적으로 라빈-카프 알고리즘에서 선호되는 함수가 된다.

다중 패턴 검색

Rabin-Karp 알고리즘은 가장 느린 최악의 경우 동작 때문에 Knuth-Morris-Pratt 알고리즘, Boyer-Moore 문자열 검색 알고리즘 및 기타 더 빠른 단일 패턴 문자열 검색 알고리즘에 대해 열등하다.그러나 다중 패턴 검색에 유용한 알고리즘이다.

텍스트에서 큰 숫자(예: k, 고정 길이 패턴)를 찾으려면, Rabin-Karp 알고리즘의 단순한 변종은 블룸 필터 또는 설정된 데이터 구조를 사용하여 특정 문자열의 해시가 우리가 찾고 있는 패턴의 해시 값 집합에 속하는지 여부를 확인한다.

기능을 하다 라빈카프셋(끈을 매다 s[1..n], 세트 의 끈을 매다 자급자족하다, m):     세트 깡충깡충깡패들 := emptySet     앞을 내다 후보선수 에 자급자족하다         삽입하다 해시하다(후보선수[1..m]) 로 깡충깡충깡패들     hs := 해시하다(s[1..m])     을 위해 i 로부터 1 로 n-m+1         만일 hs ∈ 깡충깡충깡패들 그리고 s[i..i+m-1] ∈ 자급자족하다             돌아오다 i         hs := 해시하다(s[i+1..i+m])     돌아오다 아닌 찾았다 

우리는 모든 기둥이 고정된 길이 m을 가지고 있다고 가정한다.

k 패턴을 검색하는 순진한 방법은 O(n+m) 시간이 걸리는 단일 패턴 검색을 O(n+m) 시간으로 합쳐서 반복하는 것이다.대조적으로, 위의 알고리즘은 해시 테이블 체크가 O(1) 예상 시간에서 작동한다고 가정할 때, 예상 시간에서 모든 k 패턴을 찾을 수 있다.

참조

• Karp, Richard M.; Rabin, Michael O. (March 1987). "Efficient randomized pattern-matching algorithms". IBM Journal of Research and Development. 31 (2): 249–260. CiteSeerX 10.1.1.86.9502. doi:10.1147/rd.312.0249.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001-09-01) [1990]. "The Rabin–Karp algorithm". Introduction to Algorithms (2nd ed.). Cambridge, Massachusetts: MIT Press. pp. 911–916. ISBN 978-0-262-03293-3.
• Candan, K. Selçuk; Sapino, Maria Luisa (2010). Data Management for Multimedia Retrieval. Cambridge University Press. pp. 205–206. ISBN 978-0-521-88739-7. (Bloom 필터 확장자의 경우)
• 하지만 또 다른 설명은

외부 링크

• "Rabin–Karp Algorithm/Rolling Hash" (PDF). MIT 6.006: Introduction to Algorithms 2011- Lecture Notes. MIT.