On-Line Construction of Compact Directed Acyclic Word Graphs

@article{citeulike:1155025, abstract = {Directed Acyclic Word Graph (DAWG) is a space efficient data structure that supports indices of a string. Compact Directed Acyclic Word Graph (CDAWG) is a more space efficient variant of DAWG. Crochemore and Verin gave the first direct algorithm to construct CDAWGs from given strings, based on the McCreight's algorithm for suffix trees. In this paper, we give an Ukkonen's counterpart for CDAWGs. That is, we show an on-line algorithm that constructs CDAWGs from given strings directly.}, author = {Inenaga, Shunsuke and Hoshino, Hiromasa and Shinohara, Ayumi and Takeda, Masayuki and Arikawa, Setsuo and Mauri, Giancarlo and Pavesi, Giulio }, citeulike-article-id = {1155025}, journal = {Lecture Notes in Computer Science}, keywords = {compact, dawg, trie}, posted-at = {2007-03-12 07:17:54}, priority = {3}, title = {On-Line Construction of Compact Directed Acyclic Word Graphs}, url = {http://citeseer.ist.psu.edu/494323.html}, volume = {2089}, year = {2001} }

TY - JOUR ID - citeulike:1155025 L3 - citeulike-article-id:1155025 N2 - Directed Acyclic Word Graph (DAWG) is a space efficient data structure that supports indices of a string. Compact Directed Acyclic Word Graph (CDAWG) is a more space efficient variant of DAWG. Crochemore and Verin gave the first direct algorithm to construct CDAWGs from given strings, based on the McCreight's algorithm for suffix trees. In this paper, we give an Ukkonen's counterpart for CDAWGs. That is, we show an on-line algorithm that constructs CDAWGs from given strings directly. JF - Lecture Notes in Computer Science TI - On-Line Construction of Compact Directed Acyclic Word Graphs VL - 2089 KW - compact KW - dawg KW - trie AU - Inenaga, Shunsuke AU - Hoshino, Hiromasa AU - Shinohara, Ayumi AU - Takeda, Masayuki AU - Arikawa, Setsuo AU - Mauri, Giancarlo AU - Pavesi, Giulio PY - 2001/// UR - http://citeseer.ist.psu.edu/494323.html ER -