Generalizations of suffix arrays to multi-dimensional matrices

作     者：Kim, DK Kim, YA Park, K 

作者机构：Seoul Natl Univ Sch Engn & Comp Sci Seoul 151742 South Korea Univ Maryland Dept Comp Sci College Pk MD 20742 USA Pusan Natl Univ Sch Elect & Comp Engn Pusan 609735 South Korea 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2003年第302卷第1-3期

页      面：401-416页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Korea Science & Engineering Foundation, (99-11-1-063) Pusan National University, PNU, (R01-2002-000-00589-0) 

主　　题：index data structure suffix array multi-dimensional matrices pattern retrieval 

摘      要：We propose multi-dimensional index data structures that generalize suffix arrays to square matrices and cubic matrices. Giancarlo proposed a two-dimensional index data structure, the Lsuffix tree, that generalizes suffix trees to square matrices. However, the construction algorithm for Lsuffix trees maintains complicated data structures and uses a large amount of space. We present simple construction algorithms for multi-dimensional suffix arrays by applying a new partitioning technique to lexicographic sorting. Our contributions are the first efficient algorithms for constructing two-dimensional and three-dimensional suffix arrays directly. (C) 2002 Published by Elsevier Science B.V.