다중바이트 문자집합 텍스트에서의 문자열 검색 알고리즘 (String Matching Algorithm on Multi-byte Character Set Texts)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회 컴퓨팅의 실제 논문지 / 16권 / 10호 / 1015 ~ 1019페이지
· 저자명 : 김은상, 김진욱, 박근수

초록

문자열 완전일치 검색 알고리즘은 지금까지 많은 연구가 되어왔지만, EUC-KR 등 다중바이트 문자집합에 대해서는 연구된 것이 부족한 상황이다. 이 논문에서는 기존의 KMP 알고리즘을 사용할 때 EUC-KR과 같은 다중바이트 문자집합 텍스트에서 오검색이 발생할 수 있음을 보이며, 문자 단위의 접두사 함수를 적용하여 오검색이 발생하지 않도록 개선한 KMP 알고리즘을 제안한다. 또한, 널리 사용되고 있는 편집기인 Vim과 Emacs의 검색 알고리즘 및 기존의 오토마타 방식의 연구 결과에 비해 논문에서 제안한 알고리즘이 더 빠른 속도를 보이는 실험 결과를 제시한다.

영어초록

An extensive research on exact string matching has been done, but there have been few researches on the matching in multi-byte character set texts such as EUC-KR. This paper shows that false matches may occur in multi-byte character set texts such as EUC-KR when using KMP algorithm, and presents a refined KMP algorithm without false matches applying a character- based prefix function. And also, Experimental results show that our algorithm is faster than string matching algorithms of widely used editors, Vim and Emacs, and the existing automata-based algorithm.

참고자료

· 없음