Two-Way String-Matching에 대하여

오늘은 KMP 방식과 Boyer-Moore의 방식을 조합하여 양방향으로 탐색하는 Two-Way String Matching Algorithm에 대하여 알아보도록 하겠습니다.

 

python 3.10에서 적용한 이후 약 25배가량의 엄청난 효과를 보았다고 알려진 알고리즘 입니다.

C의 strstr의 하위 문자열 함수를 구현하는데에도 사용되어져 있습니다.

 

찾고자 하는 문자열이 앞에 있는 경우

개수 / 문자열 길이 / 패턴 길이	kmp(s)	boyer-moore (s)	rabin-karp (s)	two-way String Macthing (s)
100,000 / 2,000 / 10	7.926	154.063	16.305	24.876
10,000 / 5,000 / 10	0.966	16.524	1.798	2.69

 

찾고자 하는 문자열이 뒤에 있는 경우

개수 / 문자열 길이 / 패턴 길이	kmp (s)	boyer-moore (s)	rabin-karp (s)	two-way String Matching (s)
100,000 / 10,000 / 10	285.174	192.133	135.888	215.638
10,000 / 5,000 / 10	10.966	17.619	6.304	7.619

 

python의 find함수와 c의 strstr 함수는 문자열 길이가 어느 정도이고, 찾고자 하는 문자열의 길이가 어느 정도인지 알 수 없는 환경에서 속도를 챙겨야 하므로, 평균적인 시간을 소요하는 two-way String Matching algorithm을 사용하지 않았나 싶습니다.

 

https://www-igm.univ-mlv.fr/~lecroq/string/node26.html

Two Way algorithm

 

https://github.com/lms0806/Java-Algorithm-Source/blob/main/Two-way%20String%20matching.java

Java-Algorithm-Source/Two-way String matching.java at main · lms0806/Java-Algorithm-Source