버로우즈-휠러 변환을 이용한 런-길이 문자열의 효율적인 색인 기법 (An Efficient Indexing Method for Run-Length Strings Using Burrows-Wheeler Transform)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회 컴퓨팅의 실제 논문지 / 20권 / 1호 / 26 ~ 30페이지
· 저자명 : 김성환, 조환규

초록

문자열 매칭은 긴 문자열 상에서 짧은 패턴 문자열의 출현 위치를 찾는 문제이다. 특히 탐색 대상이 되는 문자열이 고정된 경우에는 이를 색인하여 다수의 패턴 문자열에 대한 질의를 효율적으로 처리할 수 있다. 본 논문에서는 색인된 문자열 매칭 문제에 있어서 탐색 대상 문자열과 패턴 문자열이 모두 런-길이(run-length) 인코딩된 형태로 입력되는 경우를 다루고자 한다. 제안하는 기법은 버로우즈-휠러 변환을 이용하여 문자열을 색인하고, 탐색 대상인 텍스트 문자열의 서로 다른 런의 수가 α, 텍스트 문자열과 패턴 문자열의 런 수가 각각 ｎ과ｍ , 패턴 문자열의 총 출현 횟수가 γ일 때, Ο(ｎlogｎ) 비트의 공간을 이용하여 Ο(logα＋ｍloglogσ＋γlogｎ/loglogｎ) 시간에 패턴의 출현 위치를 구할 수 있다.

영어초록

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 Ο(logα＋ｍloglogσ＋γlogｎ/loglogｎ) query time using Ο(ｎlogｎ) bit space, where is the number of distinct runs in the text, and are the number of runs in the text and query pattern, respectively, and is the number of occurrences of the pattern on the text.

참고자료

· 없음