문자열 매칭은 긴 문자열 상에서 짧은 패턴 문자열의 출현 위치를 찾는 문제이다. 특히 탐색 대상이 되는 문자열이 고정된 경우에는 이를 색인하여 다수의 패턴 문자열에 대한 질의를 효율적으로 처리할 수 있다. 본 논문에서는 색인된 문자열 매칭 문제에 있어서 탐색 대상 문자열과 패턴 문자열이 모두 런-길이(run-length) 인코딩된 형태로 입력되는 경우를 다루고자 한다. 제안하는 기법은 버로우즈-휠러 변환을 이용하여 문자열을 색인하고, 탐색 대상인 텍스트 문자열의 서로 다른 런의 수가 ${sigma}$, 텍스트 문자열과 패턴 문자열의 런 수가 각각 n과 m, 패턴 문자열의 총 출현 횟수가 ${gamma}$ 일 때, O(nlogn) 비트의 공간을 이용하여 $O(log{sigma}+mloglog{sigma}+{gamma}logn/loglogn)$ 시간에 패턴의 출현 위치를 구할 수 있다.
String matching is the problem to find the occurrences of short pattern strings on a long text string. Specifically, if the text string to be searched is fixed, then we can index it so as to process queries for a number of pattern strings much efficiently. In this paper, we discuss an indexed version of the string matching problem where both the text and the patterns are given as run-length encoded forms. The proposed method uses Burrows-Wheeler Transform to index the text, and provides $O(log{sigma}+mloglog{sigma}+{gamma}logn/loglogn)$ query time using O(nlogn) bit space, where ${sigma}$ is the number of distinct runs in the text, n and m are the number of runs in the text and query pattern, respectively, and ${gamma}$ is the number of occurrences of the pattern on the text.
