On-line construction of symmetric compact directed acyclic word graphs

Shunsuke Inenaga; Hiromasa Hoshino; Ayumi Shinohara; Masayuki Takeda; Setsuo Arikawa

doi:10.1109/SPIRE.2001.989743

On-line construction of symmetric compact directed acyclic word graphs

Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa

INF - System Information Sciences

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Citations (Scopus)

Abstract

The Compact Directed Acyclic Word Graph (CDAWG) is a space efficient data structure that supports indices of a string. The Symmetric Directed Acyclic Word Graph (SCDAWG) for a string w is a dual structure that supports indices of both w and the reverse of w simultaneously. Blumer et al. gave the first algorithm to construct an SCDAWG from a given string, that works in an off-line manner. In this paper, we show an on-line algorithm that constructs an SCDAWG from a given string directly.

Original language	English
Title of host publication	Proceedings - 8th Symposium on String Processing and Information Retrieval, SPIRE 2001
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	96-110
Number of pages	15
ISBN (Electronic)	0769511929, 9780769511924
DOIs	https://doi.org/10.1109/SPIRE.2001.989743
Publication status	Published - 2001
Event	8th Symposium on String Processing and Information Retrieval, SPIRE 2001 - Laguna de San Rafael, Chile Duration: 2001 Nov 13 → 2001 Nov 15

Publication series

Name	Proceedings - 8th Symposium on String Processing and Information Retrieval, SPIRE 2001

Conference

Conference	8th Symposium on String Processing and Information Retrieval, SPIRE 2001
Country/Territory	Chile
City	Laguna de San Rafael
Period	01/11/13 → 01/11/15

Access to Document

10.1109/SPIRE.2001.989743

Cite this

Inenaga, S., Hoshino, H., Shinohara, A., Takeda, M., & Arikawa, S. (2001). On-line construction of symmetric compact directed acyclic word graphs. In Proceedings - 8th Symposium on String Processing and Information Retrieval, SPIRE 2001 (pp. 96-110). Article 989743 (Proceedings - 8th Symposium on String Processing and Information Retrieval, SPIRE 2001). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SPIRE.2001.989743

Inenaga, Shunsuke ; Hoshino, Hiromasa ; Shinohara, Ayumi et al. / On-line construction of symmetric compact directed acyclic word graphs. Proceedings - 8th Symposium on String Processing and Information Retrieval, SPIRE 2001. Institute of Electrical and Electronics Engineers Inc., 2001. pp. 96-110 (Proceedings - 8th Symposium on String Processing and Information Retrieval, SPIRE 2001).

@inproceedings{b471e8d28334449eb767bba02e68845f,

title = "On-line construction of symmetric compact directed acyclic word graphs",

abstract = "The Compact Directed Acyclic Word Graph (CDAWG) is a space efficient data structure that supports indices of a string. The Symmetric Directed Acyclic Word Graph (SCDAWG) for a string w is a dual structure that supports indices of both w and the reverse of w simultaneously. Blumer et al. gave the first algorithm to construct an SCDAWG from a given string, that works in an off-line manner. In this paper, we show an on-line algorithm that constructs an SCDAWG from a given string directly.",

author = "Shunsuke Inenaga and Hiromasa Hoshino and Ayumi Shinohara and Masayuki Takeda and Setsuo Arikawa",

note = "Publisher Copyright: {\textcopyright} 2001 IEEE.; 8th Symposium on String Processing and Information Retrieval, SPIRE 2001 ; Conference date: 13-11-2001 Through 15-11-2001",

year = "2001",

doi = "10.1109/SPIRE.2001.989743",

language = "English",

series = "Proceedings - 8th Symposium on String Processing and Information Retrieval, SPIRE 2001",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "96--110",

booktitle = "Proceedings - 8th Symposium on String Processing and Information Retrieval, SPIRE 2001",

address = "United States",

}

Inenaga, S, Hoshino, H, Shinohara, A, Takeda, M & Arikawa, S 2001, On-line construction of symmetric compact directed acyclic word graphs. in Proceedings - 8th Symposium on String Processing and Information Retrieval, SPIRE 2001., 989743, Proceedings - 8th Symposium on String Processing and Information Retrieval, SPIRE 2001, Institute of Electrical and Electronics Engineers Inc., pp. 96-110, 8th Symposium on String Processing and Information Retrieval, SPIRE 2001, Laguna de San Rafael, Chile, 01/11/13. https://doi.org/10.1109/SPIRE.2001.989743

On-line construction of symmetric compact directed acyclic word graphs. / Inenaga, Shunsuke; Hoshino, Hiromasa; Shinohara, Ayumi et al.
Proceedings - 8th Symposium on String Processing and Information Retrieval, SPIRE 2001. Institute of Electrical and Electronics Engineers Inc., 2001. p. 96-110 989743 (Proceedings - 8th Symposium on String Processing and Information Retrieval, SPIRE 2001).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On-line construction of symmetric compact directed acyclic word graphs

AU - Inenaga, Shunsuke

AU - Hoshino, Hiromasa

AU - Shinohara, Ayumi

AU - Takeda, Masayuki

AU - Arikawa, Setsuo

PY - 2001

Y1 - 2001

N2 - The Compact Directed Acyclic Word Graph (CDAWG) is a space efficient data structure that supports indices of a string. The Symmetric Directed Acyclic Word Graph (SCDAWG) for a string w is a dual structure that supports indices of both w and the reverse of w simultaneously. Blumer et al. gave the first algorithm to construct an SCDAWG from a given string, that works in an off-line manner. In this paper, we show an on-line algorithm that constructs an SCDAWG from a given string directly.

AB - The Compact Directed Acyclic Word Graph (CDAWG) is a space efficient data structure that supports indices of a string. The Symmetric Directed Acyclic Word Graph (SCDAWG) for a string w is a dual structure that supports indices of both w and the reverse of w simultaneously. Blumer et al. gave the first algorithm to construct an SCDAWG from a given string, that works in an off-line manner. In this paper, we show an on-line algorithm that constructs an SCDAWG from a given string directly.

UR - http://www.scopus.com/inward/record.url?scp=84963850932&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84963850932&partnerID=8YFLogxK

U2 - 10.1109/SPIRE.2001.989743

DO - 10.1109/SPIRE.2001.989743

M3 - Conference contribution

AN - SCOPUS:84963850932

T3 - Proceedings - 8th Symposium on String Processing and Information Retrieval, SPIRE 2001

SP - 96

EP - 110

BT - Proceedings - 8th Symposium on String Processing and Information Retrieval, SPIRE 2001

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 8th Symposium on String Processing and Information Retrieval, SPIRE 2001

Y2 - 13 November 2001 through 15 November 2001

ER -

Inenaga S, Hoshino H, Shinohara A, Takeda M, Arikawa S. On-line construction of symmetric compact directed acyclic word graphs. In Proceedings - 8th Symposium on String Processing and Information Retrieval, SPIRE 2001. Institute of Electrical and Electronics Engineers Inc. 2001. p. 96-110. 989743. (Proceedings - 8th Symposium on String Processing and Information Retrieval, SPIRE 2001). doi: 10.1109/SPIRE.2001.989743

On-line construction of symmetric compact directed acyclic word graphs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this