講演名 | 1997/7/25 文脈つきRecency Rank符号によるデータ圧縮について 定兼 邦彦, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 文脈ソートによる圧縮方法は、block sortingによる圧縮をオンラインにしたものと考えることができ、漸近最良であるが、実際の性能はあまり良くない。また、圧縮速度も遅い。本研究ではこの圧縮方法の変種である、文脈つきのrecency rank (RRC)符号を提案する。この方法では文脈をsuffix treeを使って記憶することで高速化でき。treeの枝のmove-to-front変換を行なうことでrecency rank符号を実現する。この方法は元の方法と同様に漸近最良であり、さらに、符号を改良し圧縮率をあげることできた。ただし、block sortingよりは圧縮率、速度ともに劣っている。その原因を調べ、これらの方法の関係を明らかにした。 |
抄録(英) | The context sorting compression scheme is regarded as an on-line version of the block sorting compression and it is asymptotically optimal. However, the compression speed is slow and the real performance is not so good. In this paper, recency rank code with context (RRC), which is a variation of the scheme, is proposed. The proposed method can be implemented using suffix tree and recency rank code is realized by move-to-front transformation of edges in the tree. The method is faster than the original one and is also asymptotically optimal. Moreover, compression performance becomes better by improving codes However, the proposed method is still inferior to the block sorting in both performance and speed. The reason of bad performance was investigated and the relation among these methods became clear. |
キーワード(和) | 文脈ソート / block sorting / recency rank |
キーワード(英) | context sorting / block sorting / recency rank |
資料番号 | IT97-38 |
発行日 |
研究会情報 | |
研究会 | IT |
---|---|
開催期間 | 1997/7/25(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Information Theory (IT) |
---|---|
本文の言語 | JPN |
タイトル(和) | 文脈つきRecency Rank符号によるデータ圧縮について |
サブタイトル(和) | |
タイトル(英) | On a Compression Scheme using Recency Rank with Context |
サブタイトル(和) | |
キーワード(1)(和/英) | 文脈ソート / context sorting |
キーワード(2)(和/英) | block sorting / block sorting |
キーワード(3)(和/英) | recency rank / recency rank |
第 1 著者 氏名(和/英) | 定兼 邦彦 / Kunihiko Sadakane |
第 1 著者 所属(和/英) | 東京大学大学院理学系研究科情報科学 Department of Information Science, University of Tokyo |
発表年月日 | 1997/7/25 |
資料番号 | IT97-38 |
巻番号(vol) | vol.97 |
号番号(no) | 208 |
ページ範囲 | pp.- |
ページ数 | 6 |
発行日 |