본 논문에서는 A와 B의 써픽스 배열이 주어졌을 때 두 배열을 합병하여 이들의 일반화된 써픽스 배열을 구축하는 방법을 연구하였다. 흘수 써픽스와 짝수 써픽스같이 특별한 경우의 두 써픽스를 합병하는 알고리즘은 이미 발표되었지만, A와 』가 임의의 문자열인 일반적인 경우 두 써픽스 배열을 합병하는 효율적인 알고리즘은 아직 개발되지 않았다. 따라서 현재까지는 A와 B의 써픽스 배열을 합병하기 위해서 A와 B의 써픽스 배열이 이미 주어져 있음에도 불구하고 A$\#$B$\$$라는 문자열에 대한 써픽스 배열을 다시 구축해야했다. 본 논문에서는 상수 문자집합이나 정수 문자집합에서 정의된 임의의 두 문자열 A와 B에 대한 써픽스 배열을 합병하는 효율적인 알고리즘을 제시한다. 실험결과 상수문자집합의 경우 A$\#$B$\$$에대한 써픽스 배열을 다시 구축하는 것보다 합병하는 것이 5배 정도 빨랐다. 여기서 제시한 알고리즘은 써픽스 배열 A에서 스트링 B의 모든 써픽스를 검색하여야 한다. 이를 위해 써픽스 배열에서 정의한 써픽스 링크를 사용하였고, 또 써픽스 링크를 계산하는 효율적인 알고리즘도 개발하였다. 써픽스 링크는 생물정보학에서 사용되는 매칭 통계나 최장 공통 부분 문자열 검색처럼 다른 스트링의 써픽스 배열에서 주어진 스트링의 모든 써픽스를 찾는 데 이용할 수 있으므로, 이를 계산하는 효율적인 방법을 제시한 것 역시 많은 의미를 가진다. 실험을 통해 여기서 제시한 방법이 기존 알고리즘 중 가장 빠른 방법보다 3$\~$4배 정도 빠르다는 것을 보였다.
본 논문에서는 A와 B의 써픽스 배열이 주어졌을 때 두 배열을 합병하여 이들의 일반화된 써픽스 배열을 구축하는 방법을 연구하였다. 흘수 써픽스와 짝수 써픽스같이 특별한 경우의 두 써픽스를 합병하는 알고리즘은 이미 발표되었지만, A와 』가 임의의 문자열인 일반적인 경우 두 써픽스 배열을 합병하는 효율적인 알고리즘은 아직 개발되지 않았다. 따라서 현재까지는 A와 B의 써픽스 배열을 합병하기 위해서 A와 B의 써픽스 배열이 이미 주어져 있음에도 불구하고 A$\#$B$\$$라는 문자열에 대한 써픽스 배열을 다시 구축해야했다. 본 논문에서는 상수 문자집합이나 정수 문자집합에서 정의된 임의의 두 문자열 A와 B에 대한 써픽스 배열을 합병하는 효율적인 알고리즘을 제시한다. 실험결과 상수문자집합의 경우 A$\#$B$\$$에대한 써픽스 배열을 다시 구축하는 것보다 합병하는 것이 5배 정도 빨랐다. 여기서 제시한 알고리즘은 써픽스 배열 A에서 스트링 B의 모든 써픽스를 검색하여야 한다. 이를 위해 써픽스 배열에서 정의한 써픽스 링크를 사용하였고, 또 써픽스 링크를 계산하는 효율적인 알고리즘도 개발하였다. 써픽스 링크는 생물정보학에서 사용되는 매칭 통계나 최장 공통 부분 문자열 검색처럼 다른 스트링의 써픽스 배열에서 주어진 스트링의 모든 써픽스를 찾는 데 이용할 수 있으므로, 이를 계산하는 효율적인 방법을 제시한 것 역시 많은 의미를 가진다. 실험을 통해 여기서 제시한 방법이 기존 알고리즘 중 가장 빠른 방법보다 3$\~$4배 정도 빠르다는 것을 보였다.
We consider constructing the generalized suffix way of strings A and B when the suffix arrays of A and B are given, j.e., merging two suffix arrays of A and B. There are efficient algorithms to merge some special suffix arrays such as the odd array and the even array. However, for the general case t...
We consider constructing the generalized suffix way of strings A and B when the suffix arrays of A and B are given, j.e., merging two suffix arrays of A and B. There are efficient algorithms to merge some special suffix arrays such as the odd array and the even array. However, for the general case that A and B are arbitrary strings, no efficient merging algorithms have been developed. Thus, one had to construct the generalized suffix arrays of A and B by constructing the suffix array of A$\#$B$\$$ from scratch, even though the suffix ways of A and B are given. In this paper, we Present efficient merging algorithms for the suffix arrays of two arbitrary strings A and B drawn from constant and integer alphabets. The experimental results show that merging two suffix ways of A and B are about 5 times faster than constructing the suffix way of A$\#$B$\$$ from scratch for constant alphabets. Our algorithms include searching all suffixes of string B in the suffix array of A. To do this, we use suffix links in suffix ways and we developed efficient algorithms for computing the suffix links. Efficient computation of suffix links is another contribution of this paper because it can be used to solve other problems occurred in bioinformatics that should search all suffixes of a given string in the suffix array of another string such as computing matching statistics, finding longest common substrings, and so on. The experimental results show that our methods for computing suffix links is about 3-4 times faster than the previous fastest methods.
We consider constructing the generalized suffix way of strings A and B when the suffix arrays of A and B are given, j.e., merging two suffix arrays of A and B. There are efficient algorithms to merge some special suffix arrays such as the odd array and the even array. However, for the general case that A and B are arbitrary strings, no efficient merging algorithms have been developed. Thus, one had to construct the generalized suffix arrays of A and B by constructing the suffix array of A$\#$B$\$$ from scratch, even though the suffix ways of A and B are given. In this paper, we Present efficient merging algorithms for the suffix arrays of two arbitrary strings A and B drawn from constant and integer alphabets. The experimental results show that merging two suffix ways of A and B are about 5 times faster than constructing the suffix way of A$\#$B$\$$ from scratch for constant alphabets. Our algorithms include searching all suffixes of string B in the suffix array of A. To do this, we use suffix links in suffix ways and we developed efficient algorithms for computing the suffix links. Efficient computation of suffix links is another contribution of this paper because it can be used to solve other problems occurred in bioinformatics that should search all suffixes of a given string in the suffix array of another string such as computing matching statistics, finding longest common substrings, and so on. The experimental results show that our methods for computing suffix links is about 3-4 times faster than the previous fastest methods.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
가설 설정
2. Construct the child table cldtabe in 0( n) time.
The suffix tree is time-efficient in that the suffix tree for a string of length n can be constructed in 0( n) time[2, 4-6] and a pattern of length m can be searched in 0(. m) time in the suffix tree if the size of alphabet is constant. However, it is not space-efficient because it consumes quite large space.
제안 방법
We measure the running time of constructing the generalized suffix array for two strings of the same length using our merging algorithms and compare it with constructing the generalized suffix array from scratch. We generated different kinds of random strings which are differ in lengths (IM, 5M, 10M, and 30M) and in the sizes of alphabets (2, 4, 64, and 128) from which they are drawn.
이론/모형
The suffix tree due to McCreight[2] is a compacted trie of all suffixes of the string. It was designed as a simplified version of Weiner's position tree[3]. The suffix tree is time-efficient in that the suffix tree for a string of length n can be constructed in 0( n) time[2, 4-6] and a pattern of length m can be searched in 0(.
참고문헌 (26)
D. Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge Univ. Press, 1997
E. M. McCreight, 'A space-economical suffix tree construction algorithms,' J. ACM 23, pp. 262-272, 1976
P. Weiner, Linear pattern matching algorithms, Proc. 14th IEEE Symp. Switching and Automata Theory, pp. 1-11, 1973
M. Farach, Optimal suffix tree construction with large alphabets, IEEE Symp. Found. Computer Science (1991), 137-143
M. Farach-Colton, P. Ferragina and S. Muthukri-shnan, On the sorting-complexity of suffix tree construction, J. Assoc. Comput. Mach, vol 47, pp. 987-1011, 2000
G. Gonnet, R. Baeza-Yates, and T. Snider, New indices for text: Pat trees and pat arrays. In W. B. Frakes and R. A. Baeza-Yates, editors, Information Retrieval: Data Structures & Algorithms, Prentice Hall, pp. 66-82, 1992
J. Karkkainen and P. Sanders, Simpler linear work suffix array construction, Int. Colloq. Automata Languages and Programming, pp. 943-955, 2003
D. K. Kim, J. S. Sim, H. Park and K. Park, Linear-time construction of suffix arrays, Symp. Combinatorial Pattern Matching, pp. 186-199, 2003.
P. Ko and S. Aluru, Space-efficient linear time construction of suffix arrays, Symp. Combinatorial Pattern Matching, pp. 200-210, 2003
M. Abouelhoda, E. Ohlebusch, and S. Kurtz, Optimal exact string matching based on suffix arrays, Symp. on String Processing and Information Retrieval, pp. 31-43, 2002
J. S. Sim, D. K. Kim, H. Park and K. Park, Linear-time search in suffix arrays, Australasian Workshop on Combinatorial Algorithms, pp. 139-146, 2003
M. T. Chen and J. Seiferas, Efficient and elegant subword tree construction, In A. Apostolico and Z. Galil, editors, Combinatorial Algorithms on Words, NATO ASI Series F: Computer and System Sciences, 1985
W.K. Hon, K. Sadakane and W.K. Sung, Breaking a time-and-space barrier in constructing full-text indices, IEEE Symp. Found. Computer Science, pp. 251-260, 2003
M.I. Abouelhoda, S. Kurtz, and E. Ohlebusch, Replacing suffix trees with enhanced suffix arrays, J. of Discrete Algorithms, pp. 53-86, 2004
A. Aho, J. Hopcroft, J. Ullman, Data Structures and Algorithms, Addison-Wesley, 1983
D. K. Kim and K. Park, Linear-time construction of two-dimensional suffix trees, Int. Colloq. on Automata, Languages and Programming, pp. 463-472, 1999
M. Burrows and D. Wheeler, A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation, 1994
R. Grossi, A. Gupta and J.S. Vitter, When indexing equals compression: Experiments with compressing suffix arrays and applications, ACM-SIAM Symp. on Discrete Algorithms, 2004
K. Sadakane, Compressed text databases with efficient query algorithms based on the compressed suffix array, Int. Symp. Algorithms and Computation, pp. 410-421, 2000
K. Sadakane, Succinct representations of lcp Information and improvements in the compressed suffix arrays, CM-SIAM Symp. on Discrete Algorithms, pp. 225-232, 2002
R. Grossi and J.S. Vitter, Compressed suffix arrays and suffix trees with applications to text indexing and string matching, ACM Symp. Theory of Computing, pp, 397-406, 2000
※ AI-Helper는 부적절한 답변을 할 수 있습니다.