部分列数え上げデータ圧縮法とその周辺:―オフライン無ひずみユニバーサル符号の架け橋として―  [in Japanese] Compression by Substring Enumeration and Its Related Topics: As a Bridge Between Offline Universal Codes  [in Japanese]

Access this Article

Author(s)

Abstract

<p>2010年に提案された部分列数え上げデータ圧縮法は,無ひずみデータ圧縮法の代表例であるジブ・レンペル符号と同様,情報源の確率構造についての事前知識を前提としないユニバーサル符号の一種である.ただし,後者が逐次的な処理を基本とするのに対し,部分列数え上げデータ圧縮法は対象データ全体を読み込んで一括して処理するオフラインの圧縮法である.オフラインのユニバーサルデータ圧縮法としては,BW変換に基づくブロックソート法が有名である.部分列数え上げデータ圧縮法は,ブロックソート法をはじめ,数え上げ符号,反辞書法との関係が深く,これらを体系として理解する上で欠かせない学習材料である.しかも,情報理論的な解析から実装のためのデータ構造に至るまで,分野横断的な諸側面において興味深い性質を有している.本稿では,そのような諸側面を簡潔に紹介する.</p>

<p>This article surveys a recently introduced data compression method known as compression by substring enumeration (CSE) and its related topics. CSE is an offline, lossless universal code, which encodes an entire data sequence as a single block without using prior knowledge of the information source. It is strongly related to existing offline compression methods such as enumerative codes, the block-sorting method, and the antidictionary method. Various interesting characteristics are seen in several fields from information theory to algorithms and data structures in the development of CSE. CSE leads to a better understanding of a class of offline lossless compression algorithms.</p>

Journal

  • IEICE ESS Fundamentals Review

    IEICE ESS Fundamentals Review 12(1), 21-29, 2018

    The Institute of Electronics, Information and Communication Engineers

Codes

Page Top