WEKO3
アイテム
極大反復部分文字列に基づく文法圧縮
https://ipsj.ixsq.nii.ac.jp/records/193953
https://ipsj.ixsq.nii.ac.jp/records/193953c1c2c7da-48f4-4217-9486-d0d6716e8709
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL19171006.pdf (900.3 kB)
|
Copyright (c) 2019 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2019-01-22 | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | 極大反復部分文字列に基づく文法圧縮 | |||||||||||||||||
| 言語 | ||||||||||||||||||
| 言語 | jpn | |||||||||||||||||
| 資源タイプ | ||||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||||||||
| 資源タイプ | technical report | |||||||||||||||||
| 著者所属 | ||||||||||||||||||
| 北海道大学 | ||||||||||||||||||
| 著者所属 | ||||||||||||||||||
| 北海道大学 | ||||||||||||||||||
| 著者所属 | ||||||||||||||||||
| 九州大学 | ||||||||||||||||||
| 著者所属 | ||||||||||||||||||
| 九州大学 | ||||||||||||||||||
| 著者所属 | ||||||||||||||||||
| 九州大学／理化学研究所革新知能統合研究センター | ||||||||||||||||||
| 著者所属 | ||||||||||||||||||
| 北海道大学 | ||||||||||||||||||
| 著者名 |
古谷, 勇
× 古谷, 勇
× 髙木, 拓也
× 中島, 祐人
× 稲永, 俊介
× 坂内, 英夫
× 喜田, 拓也
|
|||||||||||||||||
| 論文抄録 | ||||||||||||||||||
| 内容記述タイプ | Other | |||||||||||||||||
| 内容記述 | 本稿では，文法圧縮アルゴリズムのひとつである RePair を解析し，その生成文法と極大反復部分文字列 （maximal repeat） との関係性を明らかにする．その上で，RePair を拡張した新たな文法圧縮アルゴリズムである MR-RePair を提案する．RePair が最頻出の文字ペアを順次変数に置換していくアルゴリズムであるのに対し，MR-RePair は最頻出の極大反復部分文字列を順次変数に置換していくものである．MR-RePair は RePair と同じデータ構造を用いて，入力文字列長に対して線形時間で実行可能である．最後に，RePair との比較実験の結果から，MR-RePair の圧縮性能の優位性を示す． | |||||||||||||||||
| 書誌レコードID | ||||||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||||||
| 収録物識別子 | AN1009593X | |||||||||||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2019-AL-171, 号 6, p. 1-8, 発行日 2019-01-22 |
|||||||||||||||||
| ISSN | ||||||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||||||
| 収録物識別子 | 2188-8566 | |||||||||||||||||
| Notice | ||||||||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||||||||
| 出版者 | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 出版者 | 情報処理学会 | |||||||||||||||||
