WEKO3
-
RootNode
アイテム
Dense符号化のための文法圧縮分割
https://ipsj.ixsq.nii.ac.jp/records/102911
https://ipsj.ixsq.nii.ac.jp/records/102911cbcf1a11-dd49-4022-97f6-797339b615dc
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL14149005.pdf (191.2 kB)
|
Copyright (c) 2014 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2014-09-05 | |||||||
| タイトル | ||||||||
| タイトル | Dense符号化のための文法圧縮分割 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Grammar Compression Parsing for Dense Coding | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 北海道大学大学院情報科学研究科 | ||||||||
| 著者所属 | ||||||||
| 北海道大学大学院情報科学研究科 | ||||||||
| 著者所属 | ||||||||
| 北海道大学大学院情報科学研究科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Hokkaido University, Graduate School of Information Science and Technology | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Hokkaido University, Graduate School of Information Science and Technology | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Hokkaido University, Graduate School of Information Science and Technology | ||||||||
| 著者名 |
正木拓也
笹川裕人
喜田拓也
× 正木拓也 笹川裕人 喜田拓也
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 入力テキストを単語毎に符号化する End-Tagged Dense 符号 (ETDC) は，バイト単位の可変長符号を用いる，符号語の抽出が容易な検索向きのデータ圧縮法である．本稿では，単語毎に分かち書きされていないテキストに対して ETDC で符号化する手法を提案した．提案手法は，テキストに対して文法圧縮の一つである Re-Pair アルゴリズムを利用した分かち書きを行い，その後に ETDC で符号化を行う．その際，Re-Pair アルゴリズムの再帰処理において，後段の ETDC の符号化の効率を見積もる評価指標を導入し，その指標に基づいて再帰を打ち切る．それにより，日本語テキストやゲノムデータなどに対しても，検索や圧縮率の観点から効率よいデータ圧縮が実現できる．今回，実データに対して提案手法を適用することで，gzip や bzip2 に匹敵する圧縮率を達成できることを実証した． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | End-Tagged Dense Code (ETDC) is a word-based compression method that uses byte-oriented codewords. It is easy to extract codewords from compressed texts, and thus suitable for searching keywords on them. In this paper, we proposed a method for ETDC on texts which are not separated by spaces. In the proposed method, an input text is parsed by utilizing Re-Pair algorithm proposed by Larsson and Moffat, and then encoded by ETDC. We introduced a criterion that estimates the efficiency of ETDC in order to truncate the recursion of Re-Pair according to the criterion. This truncation realizes efficient data compression from the viewpoint of searching and compression ratio even for Japanese texts and gene data. In this time, we showed that our method achieved good compression ratios comparable with gzip and bzip2. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2014-AL-149, 号 5, p. 1-5, 発行日 2014-09-05 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
