Rabin-Karp Algorithm(라빈 카프 알고리즘) 분석

Rabin-Karp Algorithm  분석

 

 

1. 논문

- 논문 1 : 이도훈,강상수,조환규 “일반화 된 Rabin - Karp 방식을 이용한 스트링 검색 알고리즘” 한국정보과학회 1991년도 봄 학술발표논문집 제18권 제1호 1991.4 p515-518

- 논문 2 : "String Matching Methodologies: A Comparative Analysis" International Journal of Computer Science and Information Technologies, Vol. 3 (2) , 2012,3394 - 3397

 

2. 연구 동기/목적

- 스트링 매칭 알고리즘 라빈-카프 알고리즘(Rabin-Karp Algorithm)의 기본 동작 원리를 이해하고 장단점 및 한계를 분석한다.

- 다른 스트링 매칭 알고리즘과 라빈-카프 알고리즘(Rabin-Karp Algorithm)을 비교 분석하여 알고리즘 선택 기준을 정리한다.

 

3. 연구 및 분석

3.1 라빈-카프 알고리즘(Rabin-Karp Algorithm)

Rabin-Karp 알고리즘은 해싱을 사용하여 텍스트에서 패턴을 검색하는 알고리즘이다.

1987년 Michael Rabin과 Richard Karp가 개발했다.

1) 작동 원리 분석

문자열의 해시 값을 비교하여 일치 여부를 검사한다.

텍스트 : ababaacabacaabacaaba

패턴 : abacaaba

 

①      해시 값은 비교할 각 문자의 아스키 코드 값에 해시 상수의 제곱 수를 차례대로 곱하여 더해준다.

패턴 해시 값 : 97*2^7 + 98*2^6 + 97*2^5 + 99*2^4 + 97*2^3 + 97*2^2 + 98*2^1 + 97*2^0 = 24833

②      텍스트의 0번째 문자부터 패턴의 길이만큼 동일하게 해시 값을 만들고 패턴의 해시 값과 비교한다.

③      일치하지 않을 경우 오른쪽으로 한 칸 이동하며 비교한다.

④      텍스트의 해시 값과 패턴의 해시 값이 일치하면 문자열이 모두 일치하는지 확인 후 매칭 된 첫 문자의 위치를 반환한다.

 

텍스트 : 97*2^7 + 98*2^6 + 97*2^5 + 98*2^4 + 97*2^3 + 97*2^2 + 99*2^1 + 97*2^0 = 24819

패턴 : 24833

 

텍스트 : 98*2^7 + 97*2^6 + 98*2^5 + 97*2^4 + 97*2^3 + 99*2^2 + 97*2^1 + 98*2^0 = 24904

패턴 : 24833

 

텍스트 : 97*2^7 + 98*2^6 + 97*2^5 + 97*2^4 + 99*2^3 + 97*2^2 + 98*2^1 + 97*2^0 = 24817

패턴 : 24833

 

텍스트 : 98*2^7 + 97*2^6 + 97*2^5 + 99*2^4 + 97*2^3 + 98*2^2 + 97*2^1 + 99*2^0 = 24901

패턴 : 24833

 

텍스트 : 97*2^7 + 98*2^6 + 97*2^5 + 99*2^4 + 97*2^3 + 97*2^2 + 98*2^1 + 97*2^0 = 24833

패턴 : 24833

 

 

2) 장단점

장점		단점
빠른 속도	해시 함수를 통해 문자열을 상수 시간 내에 비교할 수 있다. O(n)	해시 충돌 가능성	다른 문자열이 동일한 해시 값을 갖는 상황 발생할 수 있다
다양한 언어 및 문자 집합 지원	유니코드와 같이 다양한 문자 집합을 다룰 수 있다.	고정된 해시 크기	사용되는 해시 함수의 크기가 고정되어 큰 데이터 집합에서 충돌 가능성 증가
다중 패턴 검색 가능	여러 개의 패턴을 동시에 검색할 수 있다.	최악의 경우 성능	해시 충돌이 일어날 경우 O(nm)

 

 

3) 알고리즘 구현

 

 

 

 

 

 

3.2 스트링 매칭 알고리즘 비교 분석

1) KMP 알고리즘(Knuth-Morris-Pratt Algorithm), 보이어-무어 알고리즘(Boyer-Moore Algorithm)과 비교

라빈-카프 알고리즘	KMP 알고리즘	보이어-무어 알고리즘
해싱 사용 방식	접두사 접미사 일치 방식	불일치 접미부, 일치 접미부 방식
시간복잡도 O(n)	시간복잡도 O(n+m)	시간복잡도 O(n)
최악의 경우 비효율적	최악의 경우에도 일정한 성능 보장	평균 및 최악의 경우에도 효율적
해시 충돌 가능성 있음	해시 충돌 고려 필요없음	해시 충돌 고려 필요없음
구현이 간단함	구현이 다소 복잡함	구현이 다소 복잡함

 

2) 스트링 매칭 알고리즘 선택 기준

	라빈-카프 알고리즘	KMP 알고리즘	보이어-무어 알고리즘
짧고 변동성이 낮은 패턴	O	O
길거나 변동성이 큰 패턴			O
다중 패턴 검색	O
구현의 간결성	O
최악의 경우 안정적 성능		O	O
평균적인 경우 더 빠른 성능	O	O
텍스트의 크기가 매우 크고 패턴 변경이 잦은 경우		O
텍스트 구조에 따라 불일치가 발생하는 경우			O

 

 

3.3 한계 및 해결 방안

1) 라빈-카프 알고리즘의 한계

①      해시 충돌

해시 충돌이 발생할 수 있으며, 두 다른 문자열이 동일한 해시 값을 가질 경우 성능이 저하된다.

②      패턴 길이 영향

패턴의 길이가 너무 길면 해시 충돌이 더 자주 발생할 수 있고 이로 인해 성능이 저하될 수 있다.

③      문자 집합 한계

문자 집합이 크거나 다양한 경우 해시 충돌의 가능성이 높아진다

④      매칭 위치만 알려줌

패턴이 텍스트에서 일치하는 위치만 알려주기 때문에 패턴을 찾은 후 진행될 비즈니스 로직에서 사용할 추가 정보 부족할 수 있다.

 

2) 해결 방안

라빈-카프 알고리즘은 해시 충돌이 가장 큰 단점이다. 이를 해결하기 위해 기본 해시 함수 외에 다양한 해시 함수를 시도하여 최적의 해시 함수를 사용해 볼 수 있다. 해시 충돌을 줄이기 위해 고정된 해시 함수 크기를 조절하여 더 큰 해시 값을 사용하거나 동적으로 크기를 조정하는 방법이 있다.

문자 집합과 패턴 길이의 한계에서 윈도우의 크기를 동적으로 조절하는 방식을 사용한다면 성능을 최적화할 수 있다.

또한 다른 스트링 매칭 알고리즘과 결합하여 사용하는 방식을 고려해 볼 수 있다.

 

4. 연구 및 분석 프로젝트를 진행하며

-  스트링 매칭 알고리즘 중 라빈-카프 알고리즘의 작동 방식 및 장단점과 구현 방법을 알아보고 많이 사용되는 스트링 매칭 알고리즘인 KMP 알고리즘과 보이어-무어 알고리즘을 함께 비교해보았다.

 라빈-카프 알고리즘은 해시 충돌 가능성이라는 큰 단점이 있지만 구현 난이도가 낮고 텍스트와 패턴의 크기가 크지 않을 경우 좋은 성능을 보이는 장점이 있어 물류/주문/배송 등의 API 연동 시 잘못된 포맷으로 들어오는 주소를 검사하여 정상 주소와의 일치여부를 판별할 때 간단하게 구현하여 사용하는 용도로 적합할 것이라 판단된다.

개발 실무에서는 스트링을 다루는 다양한 경우가 존재하는데 어떠한 경우에 어떠한 알고리즘을 선택/조합하여 사용할지 스트링 매칭 알고리즘 선택 기준을 참고한다면 적절한 알고리즘 선택에 도움이 될 것이라 기대한다.

 

5. 참고 문헌

-논문 1 : 이도훈,강상수,조환규 “일반화 된 Rabin - Karp 방식을 이용한 스트링 검색 알고리즘” 한국정보과학회 1991년도 봄 학술발표논문집 제18권 제1호 1991.4 p515-518

- 논문 2 : "String Matching Methodologies: A Comparative Analysis" International Journal of Computer Science and Information Technologies, Vol. 3 (2) , 2012,3394 - 3397

- Wikipedia “Rabin–Karp algorithm” https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm