ログイン 新規登録
言語:

WEKO3

  • トップ
  • ランキング
To
lat lon distance
To

Field does not validate



インデックスリンク

インデックスツリー

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

  1. 論文誌(トランザクション)
  2. 数理モデル化と応用(TOM)
  3. Vol.13
  4. No.2

Grammar-compressed Self-index with Lyndon Words

https://ipsj.ixsq.nii.ac.jp/records/206700
https://ipsj.ixsq.nii.ac.jp/records/206700
a9422e90-a985-436a-aa96-2bdec3d310cd
名前 / ファイル ライセンス アクション
IPSJ-TOM1302009.pdf IPSJ-TOM1302009.pdf (420.0 kB)
Copyright (c) 2020 by the Information Processing Society of Japan
オープンアクセス
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

× Kazuya, Tsuruta

Kazuya, Tsuruta

Search repository
Dominik, Köppl

× Dominik, Köppl

Dominik, Köppl

Search repository
Yuto, Nakashima

× Yuto, Nakashima

Yuto, Nakashima

Search repository
Shunsuke, Inenaga

× Shunsuke, Inenaga

Shunsuke, Inenaga

Search repository
Hideo, Bannai

× Hideo, Bannai

Hideo, Bannai

Search repository
Masayuki, Takeda

× Masayuki, Takeda

Masayuki, Takeda

Search repository
著者名(英) Kazuya, Tsuruta

× Kazuya, Tsuruta

en Kazuya, Tsuruta

Search repository
Dominik, Köppl

× Dominik, Köppl

en Dominik, Köppl

Search repository
Yuto, Nakashima

× Yuto, Nakashima

en Yuto, Nakashima

Search repository
Shunsuke, Inenaga

× Shunsuke, Inenaga

en Shunsuke, Inenaga

Search repository
Hideo, Bannai

× Hideo, Bannai

en Hideo, Bannai

Search repository
Masayuki, Takeda

× Masayuki, Takeda

en Masayuki, Takeda

Search repository
論文抄録
内容記述タイプ 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
出版者 情報処理学会
戻る
0
views
See details
Views

Versions

Ver.1 2025-01-19 19:21:21.970129
Show All versions

Share

Mendeley Twitter Facebook Print Addthis

Cite as

エクスポート

OAI-PMH
  • OAI-PMH JPCOAR
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by WEKO3


Powered by WEKO3