2014年3月1日
Faster compact on-line Lempel-ziv factorization
Leibniz International Proceedings in Informatics, LIPIcs
- ,
- ,
- ,
- ,
- 巻
- 25
- 号
- 開始ページ
- 675
- 終了ページ
- 686
- 記述言語
- 英語
- 掲載種別
- 研究論文(国際会議プロシーディングス)
- DOI
- 10.4230/LIPIcs.STACS.2014.675
- 出版者・発行元
- Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
We present a new on-line algorithm for computing the Lempel-Ziv factorization of a string that runs in O(N logN) time and uses only O(N log σ) bits of working space, where N is the length of the string and σ is the size of the alphabet. This is a notable improvement compared to the performance of previous on-line algorithms using the same order of working space but running in either O(N log3N) time (Okanohara &
Sadakane 2009) or O(N log2N) time (Starikovskaya 2012). The key to our new algorithm is in the utilization of an elegant but less popular index structure called Directed Acyclic Word Graphs, or DAWGs (Blumer et al. 1985). We also present an opportunistic variant of our algorithm, which, given the run length encoding of size m of a string of length N, computes the Lempel-Ziv factorization of the string on-line, in O (m · min{n (log logm)(log logN)/log log logN , √ logm/log logm o})time and O(mlogN) bits of space.
Sadakane 2009) or O(N log2N) time (Starikovskaya 2012). The key to our new algorithm is in the utilization of an elegant but less popular index structure called Directed Acyclic Word Graphs, or DAWGs (Blumer et al. 1985). We also present an opportunistic variant of our algorithm, which, given the run length encoding of size m of a string of length N, computes the Lempel-Ziv factorization of the string on-line, in O (m · min{n (log logm)(log logN)/log log logN , √ logm/log logm o})time and O(mlogN) bits of space.
- リンク情報
- ID情報
-
- DOI : 10.4230/LIPIcs.STACS.2014.675
- ISSN : 1868-8969
- DBLP ID : conf/stacs/YamamotoIBIT14
- SCOPUS ID : 84907858098