문자열 매칭이란 주어진 패턴 문자열이 상대적으로 긴 다른 문자열의 부분 문자열로서 존재하는 모든 위치를 찾는 문제이다. 특히 탐색 대상이 되는 긴 문자열이 고정되어 있는 경우 이를 색인하여 매칭 시간을 단축시킬 수 있다. 본 논문에서는 한글 문자열에 대한 시공간적으로 효율적인 문자열 매칭 색인 기법을 제안한다. 제안 기법은 한글 문자열에 대한 버로우즈-휠러 변환의 특성을 이용하여 음소별로 웨이블릿 트리를 별도로 구성함으로서 공간효율성을 높이고 문자열 매칭 속도도 향상시킨다. 실험을 통해 제안 기법이 기존의 기법에 비하여 공간을 18.5% 더 적게 사용하면서 탐색 속도는 21.02% 향상됨을 확인할 수 있었다.
String matching is the problem that asks to find all occurrences of a given pattern string on another relatively long string. In particular, when the long string is fixed, we can index it so as to reduce the matching time. In this paper, we propose a time-space efficient indexing method for Korean string matching. The proposed method uses the characteristics of the Burrows-Wheeler transform of Korean strings, and constructs separate wavelet trees for each phoneme set. Experimental results show that the proposed method outperforms the existing method by 18.5% and 21.02% in terms of space efficiency and query processing time, respectively.
