길이가 n인 알파벳 $Sigma$상의 텍스트 T에서 패턴 P를 효율적으로 검색하기 위해 접미사 트리와 접미사 배열이 널리 쓰이고 있다. 접미사 배열이 접미사 트리보다 더 적은 공간을 사용하기 때문에 텍스트의 길이가 긴 경우에는 접미사 배열이 더 선호되고 있다. 최근에는 접미사 배열을 이용한 O(${mid}P{mid}{codt}{mid}{Sigma}{mid}) 시간과 O(${mid}P{mid}{codt}log{mid}{Sigma}{mid}$) 시간 검색 알고리즘들이 개발되었다. 본 논문에서는 접미사 배열을 이용한 시간과 공간 효율적인 알고리즘들을 제시한다. 하나의 알고리즘은 O(${mid}P{mid}{codt}{mid}{Sigma}{mid}$) 비트 공간을 사용하여 O(${mid}P{mid}$) 시간에 수행되고, 다른 하나는 O($n{cdot}log{mid}{Sigma}{mid}+{mid}{Sigma}{mid}{cdot}$nlog log n/logn)비트 공간을 사용하여 O(${mid}P{mid}{codt}log{mid}{Sigma}{mid}$) 시간에 수행되는데, 두 번째 알고리즘은 보다 효율적인 공간을 사용하면서 여전히 빠른 알고리즘이다. 본 논문이 제시하는 알고리즘들이 시간과 공간에 있어 기존의 알고리즘들보다 더 효율적인 알고리즘들임을 실험을 통해 보여주고 있다.
To search efficiently a text T of length n for a pattern P over an alphabet 5, suffix trees and suffix arrays are widely used. In case of a large text, suffix arrays are preferred to suffix trees because suffix ways take less space than suffix trees. Recently, O(${mid}P{mid}{codt}{mid}{Sigma}{mid}$-time and O(${mid}P{mid}P{cdot}log{mid}{Sigma}{mid}$)-time search algorithms in suffix ways were developed. In this paper we present time and space efficient search algorithms in suffix arrays. One algorithm runs in O(${mid}P{mid}$) time using O($n{cdot}{mid}{Sigma}{mid}$)-bits space, and the other runs in O($n{cdot}{mid}{Sigma}{mid}$ time using O($nlog{mid}{Sigma}{mid}+{mid}{Sigma}{mid}{cdot}$nlog log n/logn)-bits space, which is more space efficient and still fast. Experiments show that our algorithms are efficient in both time and space when compared to previous algorithms.
