Grammar-compressed Self-index with Lyndon Words

• 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
• 書誌レコードID / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 13, 号 2, p. 84-92, 発行日 2020-08-28
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会