| Item type |
Trans(1) |
| 公開日 |
2020-08-28 |
| タイトル |
|
|
タイトル |
Grammar-compressed Self-index with Lyndon Words |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Grammar-compressed Self-index with Lyndon Words |
| 言語 |
|
|
言語 |
eng |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
[オリジナル論文] grammar compression, Lyndon words, self-index |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 著者所属 |
|
|
|
Department of Informatics, Kyushu University |
| 著者所属 |
|
|
|
Department of Informatics, Kyushu University／Japan Society for Promotion of Science |
| 著者所属 |
|
|
|
Department of Informatics, Kyushu University |
| 著者所属 |
|
|
|
Department of Informatics, Kyushu University／PRESTO, Japan Science and Technology Agency |
| 著者所属 |
|
|
|
M&D Data Science Center, Tokyo Medical and Dental University |
| 著者所属 |
|
|
|
Department of Informatics, Kyushu University |
| 著者所属(英) |
|
|
|
en |
|
|
Department of Informatics, Kyushu University |
| 著者所属(英) |
|
|
|
en |
|
|
Department of Informatics, Kyushu University / Japan Society for Promotion of Science |
| 著者所属(英) |
|
|
|
en |
|
|
Department of Informatics, Kyushu University |
| 著者所属(英) |
|
|
|
en |
|
|
Department of Informatics, Kyushu University / PRESTO, Japan Science and Technology Agency |
| 著者所属(英) |
|
|
|
en |
|
|
M&D Data Science Center, Tokyo Medical and Dental University |
| 著者所属(英) |
|
|
|
en |
|
|
Department of Informatics, Kyushu University |
| 著者名 |
Kazuya, Tsuruta
Dominik, Köppl
Yuto, Nakashima
Shunsuke, Inenaga
Hideo, Bannai
Masayuki, Takeda
|
| 著者名(英) |
Kazuya, Tsuruta
Dominik, Köppl
Yuto, Nakashima
Shunsuke, Inenaga
Hideo, Bannai
Masayuki, Takeda
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
We introduce a new class of straight-line programs (SLPs), named the Lyndon SLP, inspired by the Lyndon trees (Barcelo, 1990). Based on this SLP, we propose a self-index data structure of O(g) words of spacethat can be built from a string T in O(n lg n) expected time, retrieving the starting positions of all occurrences of a pattern P of length m in O(m + lg m lg n + occ lg g) time, where n is the length of T, g is the size of the Lyndon SLP for T, and occ is the number of occurrences of P in T. |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
We introduce a new class of straight-line programs (SLPs), named the Lyndon SLP, inspired by the Lyndon trees (Barcelo, 1990). Based on this SLP, we propose a self-index data structure of O(g) words of spacethat can be built from a string T in O(n lg n) expected time, retrieving the starting positions of all occurrences of a pattern P of length m in O(m + lg m lg n + occ lg g) time, where n is the length of T, g is the size of the Lyndon SLP for T, and occ is the number of occurrences of P in T. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA11464803 |
| 書誌情報 |
情報処理学会論文誌数理モデル化と応用（TOM）
巻 13,
号 2,
p. 84-92,
発行日 2020-08-28
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
1882-7780 |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-TOM1302009.pdf (420.0 kB)
