JP2025139943A - データ圧縮装置、データ伸張装置、およびメモリシステム - Google Patents

Abstract

【課題】 スループットを向上できるデータ圧縮装置を実現する。
【解決手段】 実施形態によれば、データ圧縮装置は、全リテラル判定部と、終端シンボル追加部とを具備する。全リテラル判定部は、第１データブロックに対する辞書式圧縮により得られた第２データブロックに含まれる１つ以上のシンボルが、全てリテラルシンボルであるか否かを判定する。終端シンボル追加部は、１つ以上のシンボルが全てリテラルシンボルである場合、第２データブロックの終端にブロック終端シンボルを追加しない。終端シンボル追加部は、１つ以上のシンボルの内の少なくとも１つのシンボルがリテラルシンボルでない場合、第２データブロックの終端にブロック終端シンボルを追加する。
【選択図】図９

Description

本発明の実施形態は、データを圧縮または伸張する技術に関する。

データを圧縮して圧縮データ（圧縮ストリーム）を生成する圧縮方式として、例えば、ＲＦＣ１９５１に定められたＤＥＦＬＡＴＥが知られている。ＤＥＦＬＡＴＥでは、辞書式圧縮の結果として得られたシンボル列に対するエントロピー符号化が規定されている。

エントロピー符号化は、符号化対象のシンボル列におけるシンボル毎の出現頻度に基づいて符号化テーブルを生成する可変長符号化方式である。符号化テーブルは、シンボルと、当該シンボルに割り当てられた符号語との対応を示す。エントロピー符号化では、出現頻度が高いシンボルには短い符号語が割り当てられ、出現頻度が低いシンボルには長い符号語が割り当てられる。よって、符号化対象の各シンボルは、符号化テーブルを用いて可変長符号に変換される。

米国特許出願公開第２０２２／０３７６７０１号明細書 米国特許出願公開第２０２２／００８３３８２号明細書 米国特許出願公開第２０２３／０００６６８９号明細書

本発明の一実施形態では、スループットを向上できるデータ圧縮装置、データ伸張装置、およびメモリシステムを提供する。

実施形態によれば、データ圧縮装置は、全リテラル判定部と、終端シンボル追加部とを具備する。全リテラル判定部は、第１データブロックに対する辞書式圧縮により得られた第２データブロックに含まれる１つ以上のシンボルが、全てリテラルシンボルであるか否かを判定する。終端シンボル追加部は、１つ以上のシンボルが全てリテラルシンボルである場合、第２データブロックの終端にブロック終端シンボルを追加しない。終端シンボル追加部は、１つ以上のシンボルの内の少なくとも１つのシンボルがリテラルシンボルでない場合、第２データブロックの終端にブロック終端シンボルを追加する。

実施形態に係るデータ圧縮装置およびデータ伸張装置を含む情報処理システムの構成の例を示すブロック図。 実施形態に係るデータ圧縮装置から出力される、あるいはデータ伸張装置に入力される、圧縮ストリームの例を示す図。 実施形態に係るデータ圧縮装置による辞書式圧縮およびエントロピー符号化において生成されるデータの例を示す図。 実施形態に係るデータ伸張装置によるエントロピー復号および辞書式伸張において生成されるデータの例を示す図。 第１比較例に係るデータ圧縮装置の構成を示すブロック図。 第１比較例に係るデータ伸張装置の構成を示すブロック図。 第２比較例に係るデータ伸張装置の構成を示すブロック図。 第２比較例に係るデータ伸張装置において実行されるブロック境界判定処理の手順を示すフローチャート。 実施形態に係るデータ圧縮装置の構成例を示すブロック図。 実施形態に係るデータ圧縮装置において実行される全リテラル判定処理の手順の例を示すフローチャート。 実施形態に係るデータ伸張装置の構成例を示すブロック図。 実施形態に係るデータ伸張装置において実行されるブロック境界判定処理の手順の例を示すフローチャート。

以下、実施の形態について図面を参照して説明する。

図１は、実施形態に係る辞書式圧縮部を含む情報処理システムの構成の例を示す。情報処理システム１は、ホストデバイス２と、メモリシステム３とを含む。

ホストデバイス２は、データをメモリシステム３に格納する情報処理装置である。ホストデバイス２は、例えば、大量且つ多様なデータをメモリシステム３に格納するストレージサーバ、またはパーソナルコンピュータである。以下では、ホストデバイス２を、ホスト２と称する。

メモリシステム３は、不揮発性メモリにデータを書き込み、不揮発性メモリからデータを読み出すように構成された半導体ストレージデバイスである。不揮発性メモリは、例えば、ＮＡＮＤ型フラッシュメモリ４である。メモリシステム３は、例えば、ソリッドステートドライブ（ＳＳＤ）として実現される。以下では、メモリシステム３がＳＳＤとして実現される場合について例示するが、メモリシステム３はハードディスクドライブ（ＨＤＤ）として実現されてもよい。

メモリシステム３は、ホスト２のストレージとして使用され得る。メモリシステム３はホスト２に内蔵されてもよいし、ホスト２にケーブルまたはネットワークを介して接続されてもよい。

ホスト２とメモリシステム３とを接続するためのインタフェースは、ＳＣＳＩ、Ｓｅｒｉａｌ Ａｔｔａｃｈｅｄ ＳＣＳＩ（ＳＡＳ）、ＡＴＡ（ＡＴ Ａｔｔａｃｈｍｅｎｔ）、Ｓｅｒｉａｌ ＡＴＡ（ＳＡＴＡ）、ＰＣＩ Ｅｘｐｒｅｓｓ^ＴＭ（ＰＣＩｅ^ＴＭ）、Ｅｔｈｅｒｎｅｔ^ＴＭ、Ｆｉｂｒｅ ｃｈａｎｎｅｌ、ＮＶＭ Ｅｘｐｒｅｓｓ^ＴＭ（ＮＶＭｅ^ＴＭ）等の規格に準拠する。

メモリシステム３は、例えば、ＮＡＮＤ型フラッシュメモリ４、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）５、およびコントローラ６を備える。

ＮＡＮＤ型フラッシュメモリ４は、１つ以上のメモリチップを含む。各メモリチップは、複数のブロックを含む。１つのブロックは、データ消去動作の最小単位として機能する。ブロックは、消去ブロック、または物理ブロックと称されることもある。複数のブロックのそれぞれは、複数のページを含む。複数のページのそれぞれは、単一のワード線に接続された複数のメモリセルを含む。１つのページは、データ書き込み動作およびデータ読み出し動作の単位として機能する。なお、ワード線がデータ書き込み動作およびデータ読み出し動作の単位として機能してもよい。

各ブロックに対するプログラム／イレーズサイクル数（Ｐ／Ｅサイクル数）には上限があり、最大Ｐ／Ｅサイクル数と称される。あるブロックの１回のＰ／Ｅサイクルは、このブロック内のすべてのメモリセルを消去状態にするための消去動作と、このブロックのページそれぞれにデータを書き込む書き込み動作とを含む。

ＤＲＡＭ５は、揮発性のメモリである。ＤＲＡＭ５の記憶領域は、例えば、ファームウェア（ＦＷ）の格納領域、論理物理アドレス変換テーブルのキャッシュ領域、およびユーザデータのバッファ領域として割り当てられる。

コントローラ６は、ＮＡＮＤ型フラッシュメモリ４およびＤＲＡＭ５を制御するメモリコントローラである。コントローラ６は、例えば、Ｓｙｓｔｅｍ－ｏｎ－ａ－ｃｈｉｐ（ＳｏＣ）のような回路によって実現される。コントローラ６は、スタティックランダムアクセスメモリ（ＳＲＡＭ）またはＤＲＡＭを内蔵していてもよい。この場合、コントローラ６の外部のＤＲＡＭ５が設けられていなくてもよい。

コントローラ６は、例えば、ＮＡＮＤ型フラッシュメモリ４のデータ管理およびブロック管理を実行するように構成されたフラッシュトランスレーション層（ＦＴＬ）として機能する。このＦＴＬによって実行されるデータ管理には、（１）論理アドレスそれぞれとＮＡＮＤ型フラッシュメモリ４の物理アドレスそれぞれとの間の対応関係を示すマッピング情報の管理、および（２）ページ単位のデータ読み出し動作／データ書き込み動作とブロック単位のデータ消去動作との差異を隠蔽するための処理、が含まれる。ブロック管理には、不良ブロックの管理、ウェアレベリング、およびガベージコレクションが含まれる。

論理アドレスは、メモリシステム３の記憶領域をアドレス指定するために、ホスト２によって使用される。論理アドレスは、例えば、論理ブロックアドレス（ＬＢＡ）である。

論理アドレスそれぞれと物理アドレスそれぞれとの間のマッピングの管理は、例えば、論理物理アドレス変換テーブルを用いて実行される。コントローラ６は、論理物理アドレス変換テーブルを使用して、論理アドレスそれぞれと物理アドレスそれぞれとの間のマッピングを特定の管理サイズ単位で管理する。ある論理アドレスに対応する物理アドレスは、この論理アドレスのユーザデータが書き込まれたＮＡＮＤ型フラッシュメモリ４内の物理記憶位置を示す。論理物理アドレス変換テーブルは、メモリシステム３の起動時にＮＡＮＤ型フラッシュメモリ４からＤＲＡＭ５にロードされてもよい。

１つのページへのデータ書き込みは、１回のＰ／Ｅサイクル当たり１回のみ可能である。このため、コントローラ６は、ある論理アドレスに対応する更新ユーザデータを、この論理アドレスに対応する以前のユーザデータが格納されている物理記憶位置ではなく、別の物理記憶位置に書き込む。そして、コントローラ６は、この論理アドレスをこの別の物理記憶位置に関連付けるように論理物理アドレス変換テーブルを更新することにより、以前のユーザデータを無効化する。

コントローラ６は、例えば、ＣＰＵ１１、ＮＡＮＤインタフェース（ＮＡＮＤ Ｉ／Ｆ）１２、ＤＲＡＭインタフェース（ＤＲＡＭ Ｉ／Ｆ）１３、ホストインタフェース（ホストＩ／Ｆ）１４、データ圧縮装置１５、およびデータ伸張装置１６を含む。これらＣＰＵ１１、ＮＡＮＤ Ｉ／Ｆ１２、ＤＲＡＭ Ｉ／Ｆ１３、ホストＩ／Ｆ１４、データ圧縮装置１５、およびデータ伸張装置１６は、例えば、バス１０を介して接続される。

ＣＰＵ１１は、ＮＡＮＤ Ｉ／Ｆ１２、ＤＲＡＭ Ｉ／Ｆ１３、ホストＩ／Ｆ１４、データ圧縮装置１５、およびデータ伸張装置１６を制御するように構成されたプロセッサである。ＣＰＵ１１は、ＮＡＮＤ型フラッシュメモリ４からＤＲＡＭ５にロードされたＦＷを実行することによって、様々な処理を行う。ＦＷは、ＣＰＵ１１に様々な処理を実行させるための命令群を含む制御プログラムである。ＣＰＵ１１は、前述のＦＴＬの処理に加え、ホスト２からの様々なコマンドを処理するためのコマンド処理を実行する。ＣＰＵ１１の動作は、ＣＰＵ１１によって実行されるＦＷによって制御される。なお、ＦＴＬ処理およびコマンド処理の一部または全部は、コントローラ６内の専用ハードウェアによって実行されてもよい。

ＮＡＮＤ Ｉ／Ｆ１２は、コントローラ６とＮＡＮＤ型フラッシュメモリ４とを電気的に接続する。ＮＡＮＤ Ｉ／Ｆ１２は、Ｔｏｇｇｌｅ ＤＤＲ、Ｏｐｅｎ ＮＡＮＤ Ｆｌａｓｈ Ｉｎｔｅｒｆａｃｅ（ＯＮＦＩ）等のインタフェース規格に対応する。

ＮＡＮＤ Ｉ／Ｆ１２は、ＮＡＮＤ型フラッシュメモリ４を制御するように構成されたＮＡＮＤ制御回路として機能する。ＮＡＮＤ Ｉ／Ｆ１２は、複数のチャネルを介して、ＮＡＮＤ型フラッシュメモリ４内の複数のメモリチップにそれぞれ接続されていてもよい。複数のメモリチップが並列に駆動されることにより、ＮＡＮＤ型フラッシュメモリ４全体に対するアクセスを広帯域化することができる。

ＤＲＡＭ Ｉ／Ｆ１３は、ＤＲＡＭ５へのアクセスを制御するように構成されたＤＲＡＭ制御回路として機能する。

ホストＩ／Ｆ１４は、メモリシステム３とホスト２との間の通信を行うインタフェースとして機能する回路である。ホストＩ／Ｆ１４は、ホスト２から様々なコマンド（例えば、入出力（Ｉ／Ｏ）コマンド、および制御コマンド）を受信する回路を含む。Ｉ／Ｏコマンドは、例えば、ライトコマンド、またはリードコマンドである。制御コマンドは、例えば、アンマップコマンド（トリムコマンド）、またはフォーマットコマンドである。ホストＩ／Ｆ１１は、コマンドに応じた応答やデータをホスト２に送信する回路を含む。

データ圧縮装置１５は、符号化によってデータを圧縮する符号化器である。圧縮すべきデータは、例えば、ＮＡＮＤ型フラッシュメモリ４に書き込むべきデータである。ＣＰＵ１１は、例えば、ホスト２からライトコマンドを受け付けたことに応じて受信したライトデータを、平文データ（非圧縮データ）としてデータ圧縮装置１５へ入力する。データ圧縮装置１５は、ＣＰＵ１１から入力された平文データを符号化して、圧縮ストリーム（圧縮データ）を生成する。

具体的には、データ圧縮装置１５は、例えば、平文データに含まれる複数のシンボルに対する辞書式圧縮を行うことにより、複数のシンボルを取得する。以下、辞書式圧縮により得られたシンボルを、辞書圧縮シンボルとも称する。データ圧縮装置１５は、複数の辞書圧縮シンボルに対するエントロピー符号化を行うことにより、複数の可変長符号を含む圧縮ストリームを生成する。

辞書式圧縮は、過去に入力されたデータ（すなわち、シンボル列）を保持するヒストリバッファを利用して、圧縮対象のデータをポインタに変換する符号化方式である。辞書式圧縮は、辞書式符号化とも称される。ポインタは、例えば、一致距離（マッチ距離）と、一致長（マッチ長）とを含む。辞書式圧縮では、ヒストリバッファを探索して圧縮対象のデータと少なくとも一部が一致する過去のデータを取得して、一致距離と一致長とを得る。一致距離は、ヒストリバッファにおいて、圧縮対象のデータが記憶される位置から、取得した過去のデータが記憶されている位置までの距離である。一致長は、取得した過去のデータと圧縮対象のデータとで一致した部分の長さである。圧縮対象のデータをポインタ（すなわち、一致距離および一致長）に変換することにより、データを圧縮できる。辞書式圧縮によって得られたポインタは、辞書一致シンボル、あるいはマッチシンボルと称される。

なお、圧縮対象のデータと少なくとも一部が一致する過去のデータがヒストリバッファに見つからない場合、圧縮対象のデータ（シンボル）がそのまま出力される。辞書式圧縮でポインタに変換されず、そのまま出力されたシンボルは、辞書不一致シンボル、あるいはリテラルシンボルと称される。

したがって、平文データに含まれる複数のシンボルに対する辞書式圧縮によって得られる複数の辞書圧縮シンボルは、辞書不一致シンボル（リテラルシンボル）と、辞書一致シンボル（マッチシンボル）の少なくともいずれかを含む。

エントロピー符号化は、符号化対象のシンボル（例えば、辞書圧縮シンボル）のシンボル毎の出現頻度を用いて符号化テーブルを生成する可変長符号化方式である。エントロピー符号化は、例えば、ＤＥＦＬＡＴＥで規定されている。符号化テーブルは、Ｎ種類のシンボルと、Ｎ種類のシンボルにそれぞれ関連付けられたＮ個の符号語とを示す情報を含む。エントロピー符号化では、出現頻度が高いシンボルには短い符号語が割り当てられ、出現頻度が低いシンボルには長い符号語が割り当てられる。エントロピー符号化では、このような割り当てに従い、入力されたシンボルが符号語に変換される。つまり、変換により得られる符号語は、可変長符号である。なお、シンボルは、例えば、固定長のデータである。したがって、エントロピー符号化では、シンボルの出現頻度の偏りを利用して、データ量を削減できる。エントロピー符号化によって生成された圧縮ストリームは、複数の辞書圧縮シンボルのそれぞれを変換した符号語を含む。圧縮ストリームは、エントロピー符号化に用いられた符号化テーブルを示すデータをヘッダとしてさらに含み得る。符号化テーブルを示すデータは、圧縮ストリームを伸張する場合に、符号化テーブルを復元するために用いられる。

データ伸張装置１６は、復号によって圧縮ストリームを伸張する復号器である。圧縮ストリームは、例えば、ＮＡＮＤ型フラッシュメモリ４から読み出されたデータである。ＣＰＵ１１は、例えば、ホスト２からリードコマンドを受け付けたことに応じてＮＡＮＤ型フラッシュメモリ４から読み出した圧縮ストリームをデータ伸張装置１６へ入力する。データ伸張装置１６は、ＣＰＵ１１から入力された圧縮ストリームを復号して、非圧縮データ（平文データ）を生成する。

具体的には、データ伸張装置１６は、例えば、圧縮ストリームに含まれる複数の符号語に対するエントロピー復号を行うことにより、複数の辞書圧縮シンボルを取得する。そして、データ圧縮装置１５は、複数の辞書圧縮シンボルに対する辞書式伸張を行うことにより、複数のシンボル（リテラルシンボル）を含む平文データを生成する。

エントロピー復号は、圧縮ストリームのヘッダに含まれるデータを用いて符号化テーブルを復元し、この符号化テーブルに基づき、圧縮データに含まれる符号語をシンボル（辞書圧縮シンボル）に変換する復号方式である。

辞書式伸張は、過去に生成（復号）された平文データを保持するヒストリバッファを利用して、復号すべき辞書圧縮シンボル列に含まれるマッチシンボルを平文データ（すなわち、リテラルシンボル列）に変換する復号方式である。なお、辞書圧縮シンボル列に含まれるリテラルシンボルは、辞書式圧縮されていないシンボルであるので、そのまま出力される。辞書式伸張は、辞書式復号とも称される。

図２は、データ圧縮装置１５から出力される、あるいはデータ伸張装置１６に入力される、圧縮ストリーム３３の例を示す。圧縮ストリーム３３には、マッチシンボルに対応する符号語Ｍと、リテラルシンボルに対応する符号語Ｌとが含まれ得る。

マッチシンボルは、ヒストリバッファを探索して圧縮対象のシンボル列（バイト列）と少なくとも一部が一致する過去のシンボル列がある場合に、その圧縮対象のシンボル列が置き換えられたポインタである。リテラルシンボルは、ヒストリバッファを探索して圧縮対象のシンボル列のいずれの一部とも一致する過去のシンボル列が見つからない場合に、ポインタ（マッチシンボル）に置き換えられずにそのまま出力されたシンボルである。

圧縮対象のシンボル列の少なくとも一部のシンボルがマッチシンボルに置き換えられた場合、圧縮後のシンボル列は、圧縮対象のシンボル列（すなわち、全てリテラルシンボルのままであるシンボル列）よりもシンボル数が減少する。

データ圧縮装置１５は、例えば、非圧縮データを特定の単位毎に圧縮する。特定の単位の非圧縮データは、ハフマンブロックとも称される。ハフマンブロックは、特定のデータサイズを有する。つまり、ハフマンブロックは、特定の数のシンボルを含む。特定のデータサイズは、例えば、情報処理システム１（より詳しくは、データ圧縮装置１５およびデータ伸張装置１６）において任意に設定可能である。データ圧縮装置１５は、エントロピー符号化に用いられる符号化テーブルを、例えばハフマンブロック毎に切り替える。

データ圧縮装置１５は、ハフマンブロックの境界を検出するために、各ハフマンブロックの終端にブロック終端（Ｅｎｄ ｏｆ Ｂｌｏｃｋ：ＥＯＢ）シンボルを追加することがある。ＥＯＢシンボルは、ハフマンブロックの終端を示すシンボルである。ＥＯＢシンボルとして、例えば、ＤＥＦＬＡＴＥで規定された値（ビット列）が用いられる。データ伸張装置１６は、例えばＥＯＢシンボルを検出したことに応じて、エントロピー復号に用いられる符号化テーブルを切り替え得る。

図３および図４を参照して、ハフマンブロックの終端にＥＯＢシンボルを追加するケースについて具体的に説明する。

図３は、データ圧縮装置１５による辞書式圧縮およびエントロピー符号化において生成されるデータの例を示す。ここでは、非圧縮データ３１が、１個のハフマンブロックに相当する非圧縮データであるものとする。

データ圧縮装置１５に入力された非圧縮データ３１は、辞書式圧縮により辞書圧縮シンボル列３２に変換される。具体的には、非圧縮データ３１のバイト列の内、過去のバイト列（ヒストリバッファ内のバイト列）と一致するバイト列は、一致する過去のバイト列へのポインタ（マッチシンボル）に置換される。一方、非圧縮データ３１のバイト列の内、一致する過去のバイト列が見つからないバイト列は、非圧縮バイト列（リテラルシンボル）のまま出力される。

図３に示す例では、非圧縮データ３１に含まれる８個のシンボルが、辞書式圧縮により、５個の辞書圧縮シンボルを含む辞書圧縮シンボル列３２に変換されている。辞書圧縮シンボル列３２は、２個のマッチシンボルと、３個のリテラルシンボルとを含んでいる。このように、非圧縮データ３１は、辞書式圧縮によりシンボル数が削減された辞書圧縮シンボル列３２に圧縮され得る。

次いで、辞書圧縮シンボル列３２の末尾にはＥＯＢシンボルが追加される。辞書圧縮シンボル列３２と追加されたＥＯＢシンボルとは、エントロピー符号化により圧縮ストリーム３３に変換される。具体的には、辞書圧縮シンボル列３２とＥＯＢシンボルとは、エントロピー符号化によりシンボル毎に可変長符号に変換される。

図３に示す例では、圧縮ストリーム３３には、３個のリテラルシンボル、２個のマッチシンボル、およびＥＯＢシンボルの各シンボルをエントロピー符号化することにより得られた６個の可変長符号が含まれている。このように、辞書圧縮シンボル列３２は、エントロピー符号化によりデータ量が削減された圧縮ストリーム３３に圧縮される。つまり、圧縮ストリーム３３は、非圧縮データ３１（ここでは、１個のハフマンブロック）を辞書式圧縮およびエントロピー符号化により圧縮したデータである。

前述したように、ＥＯＢシンボルは、データ伸張装置１６による復号時にハフマンブロックの境界を検出するために用いられ得る。データ伸張装置１６は、ハフマンブロックの境界を検出したことに応じ、復号に用いる符号化テーブルを切り替える。

図４は、データ伸張装置１６によるエントロピー復号および辞書式伸張において生成されるデータの例を示す。データ伸張装置１６は、圧縮ストリーム３３を特定の単位（ハフマンブロック）毎に伸張する。

データ伸張装置１６に入力された圧縮ストリーム３３は、エントロピー復号により辞書圧縮シンボル列３２に変換される。具体的には、圧縮ストリーム３３に含まれる複数の可変長符号は、エントロピー復号により、辞書圧縮シンボル列３２とＥＯＢシンボルとに変換される。ＥＯＢシンボルが得られたことに応じて、圧縮ストリーム３３におけるハフマンブロックの境界が検出される。ＥＯＢシンボルは、出力される辞書圧縮シンボル列３２からは除外される。

図４に示す例では、圧縮ストリーム３３に含まれる６個の可変長符号をエントロピー復号することにより、３個のリテラルシンボル、２個のマッチシンボル、およびＥＯＢシンボルが取得される。この内、３個のリテラルシンボルと２個のマッチシンボルとが復号順に従って、辞書圧縮シンボル列３２として出力される。

次いで、辞書圧縮シンボル列３２は、辞書式伸張により非圧縮データ３１に変換される。具体的には、辞書圧縮シンボル列３２内のマッチシンボルは、ポインタにより示される過去のバイト列（例えば、ヒストリバッファ内のバイト列）に置換されて、非圧縮データ３１として出力される。一方、辞書圧縮シンボル列３２内のリテラルシンボルは、非圧縮バイト列であるので、そのまま非圧縮データ３１として出力される。つまり、非圧縮データ３１は、圧縮ストリーム３３（ここでは、１個のハフマンブロックに相当する圧縮データ）をエントロピー復号および辞書式伸張により伸張したデータである。

図４に示す例では、辞書圧縮シンボル列３２に含まれる５個の辞書圧縮シンボルが、辞書式伸張により、８個のシンボル（リテラルシンボル）を含む非圧縮データ３１に変換されている。このように、辞書圧縮シンボル列３２は、辞書式伸張により、シンボル数が増加した非圧縮データ３１に伸張され得る。つまり、非圧縮データ３１は、圧縮ストリーム３３をエントロピー復号および辞書式伸張により伸張したデータである。

ハフマンブロック（より詳しくは、ハフマンブロックに対応する辞書圧縮シンボル列）の終端にＥＯＢシンボルが追加される場合、データ圧縮装置１５では、ＥＯＢシンボルをエントロピー符号化するための演算により、スループットが低下する。同様に、データ伸張装置１６では、ＥＯＢシンボルに対応する可変長符号をエントロピー復号するための演算により、スループットが低下する。また、ＥＯＢシンボルに対応する可変長符号を含むことにより、圧縮ストリーム３３のデータ量が増加し、圧縮効率が低下する。

１サイクル当たり１シンボルをエントロピー復号可能なデータ伸張装置１６を例に、ＥＯＢシンボルの追加によるスループットの低下について説明する。ここでは、ハフマンブロックのサイズが８１９２バイトであるものとする。

ハフマンブロックに対応する辞書圧縮シンボル列にマッチシンボルが１つでも含まれていれば、エントロピー復号すべきシンボル（可変長符号）の数は８１９２以下となる。この場合、ハフマンブロックのエントロピー復号にかかるサイクル数は、８１９２サイクル以下に抑えられる。

これに対して、ハフマンブロックに対応する辞書圧縮シンボル列が全てリテラルシンボルである場合、辞書圧縮シンボル列は８１９２個のリテラルシンボルを含む。そして、辞書圧縮シンボル列の末尾にＥＯＢシンボルが追加される場合、エントロピー復号すべきシンボル（可変長符号）の数は８１９３となる。この場合、ハフマンブロックのエントロピー復号にかかるサイクル数は８１９３サイクルになり、エントロピー復号におけるスループットが低下する。

（第１比較例）
第１比較例に係るデータ圧縮装置およびデータ伸張装置により、エントロピー符号化およびエントロピー復号でスループットが低下する例について説明する。

図５は、第１比較例に係るデータ圧縮装置の構成を示すブロック図である。データ圧縮装置１５Ｃは、辞書式圧縮およびエントロピー符号化により、非圧縮データ３１Ｃを圧縮ストリーム３３Ｃ－１に圧縮する圧縮器（符号化器）である。非圧縮データ３１Ｃは、例えば、１つ以上のハフマンブロックを含む圧縮対象のデータである。データ圧縮装置１５Ｃは、辞書式圧縮部２１Ｃと、エントロピー符号化部２２Ｃとを備える。

辞書式圧縮部２１Ｃは、非圧縮データ３１Ｃに対する辞書式圧縮により辞書圧縮シンボル３２Ｃを生成する。辞書圧縮シンボル３２Ｃは、リテラルシンボルとマッチシンボルのいずれかである。辞書式圧縮部２１Ｃは、生成した辞書圧縮シンボル３２Ｃをエントロピー符号化部２２Ｃに送出する。

エントロピー符号化部２２Ｃは、エントロピー符号化により辞書圧縮シンボル３２Ｃを可変長符号に変換して、圧縮ストリーム３３Ｃ－１を生成する。エントロピー符号化部２２Ｃは、ＥＯＢ追加部２２１Ｃ、符号化テーブル生成部２２２Ｃ、および可変長符号化部２２３Ｃを含む。

ＥＯＢ追加部２２１Ｃは、１つのハフマンブロックに対応する１つ以上の辞書圧縮シンボル３２Ｃの末尾にＥＯＢシンボルを追加する。具体的には、ＥＯＢ追加部２２１Ｃは、例えば、辞書式圧縮部２１Ｃから辞書圧縮シンボル３２Ｃを受け取る毎に、その辞書圧縮シンボル３２Ｃが辞書式圧縮される前のデータサイズを取得し、取得したデータサイズの累積値（以下、非圧縮データサイズと称する）を算出する。辞書圧縮シンボル３２Ｃがリテラルシンボルである場合、辞書式圧縮される前のデータサイズは、例えば１バイトである。辞書圧縮シンボル３２Ｃがマッチシンボルである場合、辞書式圧縮される前のデータサイズは、例えば、そのマッチシンボルが示すバイト単位の一致長である。

ＥＯＢ追加部２２１Ｃは、データサイズを取得した辞書圧縮シンボル３２Ｃを、符号化テーブル生成部２２２Ｃと可変長符号化部２２３Ｃとに送出する。そして、ＥＯＢ追加部２２１Ｃは、算出した非圧縮データサイズ特定のサイズに達した場合、ＥＯＢシンボルを追加する。つまり、ＥＯＢ追加部２２１Ｃは、直前にデータサイズを取得した辞書圧縮シンボル３２Ｃの後に、ＥＯＢシンボルを符号化テーブル生成部２２２Ｃと可変長符号化部２２３Ｃとに送出する。特定のサイズは、例えば、ブロックサイズ情報４１Ｃで示される１つのハフマンブロックのサイズ（以下、ブロックサイズとも称する）である。これにより、ＥＯＢ追加部２２１Ｃは、ハフマンブロックに対応する１つ以上の辞書圧縮シンボル３２Ｃの終端に、ＥＯＢシンボルを追加できる。

符号化テーブル生成部２２２Ｃは、ＥＯＢ追加部２２１Ｃから受け取った１つのハフマンブロックに対応する複数のシンボル（より詳しくは、１つ以上の辞書圧縮シンボル３２Ｃと、末尾のＥＯＢブロック）のシンボル毎の出現頻度に基づいて、符号化テーブル４２Ｃを生成する。具体的には、符号化テーブル生成部２２２Ｃは、出現頻度が高いシンボルに短い符号語を割り当て、出現頻度が低いシンボルに長い符号語を割り当てる。符号化テーブル生成部２２２Ｃは、生成した符号化テーブル４２Ｃを可変長符号化部２２３Ｃに送出する。また、符号化テーブル生成部２２２Ｃは、符号化テーブル４２Ｃを示すデータを、圧縮ストリーム３３Ｃ－１のヘッダ部３３１Ｃ－１として出力する。

なお、１つのハフマンブロックに対応する複数のシンボルにおいて、ＥＯＢシンボルの出現頻度は１である。そのため、符号化テーブル生成部２２２Ｃは、ＥＯＢシンボルに対して、符号化テーブル４２Ｃにおいて最長の符号長を有する可変長符号を割り当て得る。

可変長符号化部２２３Ｃは、可変長符号化により、１つのハフマンブロックに対応する複数のシンボルにそれぞれ対応する複数の可変長符号を生成する。具体的には、可変長符号化部２２３Ｃは、符号化テーブル４２Ｃに基づいて、１つのハフマンブロックに対応する複数のシンボルのそれぞれを可変長符号に変換する。可変長符号化部２２３Ｃは、各シンボルから変換された可変長符号を、圧縮ストリーム３３Ｃ－１のペイロード部３３２Ｃ－１として順に出力する。ペイロード部３３２Ｃ－１の末尾には、ＥＯＢシンボルから変換された可変長符号３３３Ｃが格納される。前述したように、ＥＯＢシンボルには最長の可変長符号が割り当てられ得る。したがって、ペイロード部３３２Ｃ－１のデータサイズに占める、ＥＯＢシンボルから変換された可変長符号３３３Ｃのサイズ（符号量）の割合は大きくなる。

なお、符号化テーブル生成部２２２Ｃは、ＥＯＢ追加部２２１Ｃから次のハフマンブロックに対応する複数のシンボルを受け取った場合、新たな符号化テーブル４２Ｃを生成して、可変長符号化部２２３Ｃに送出する。つまり、符号化テーブル生成部２２２Ｃは、ＥＯＢ追加部２２１ＣからＥＯＢシンボルを受け取ったことに応じて、符号化テーブル４２Ｃを切り替える。可変長符号化部２２３Ｃは、新たな符号化テーブル４２Ｃを用いて、その次のハフマンブロックに対応する複数のシンボルのそれぞれを可変長符号に変換する。

したがって、圧縮ストリーム３３Ｃ－１は、ハフマンブロック毎に、符号化テーブル４２Ｃを含むヘッダ部３３１Ｃ－１と、辞書圧縮シンボル列３２ＣおよびＥＯＢシンボルを可変長符号化したペイロード部３３２Ｃ－１とで構成される。

データ圧縮装置１５Ｃでは、ハフマンブロックに対応する辞書圧縮シンボル列３２Ｃが全てリテラルシンボルである場合、可変長符号化部２２３ＣがＥＯＢシンボルをエントロピー符号化するための、例えば１サイクルの演算により、スループットが低下する。なお、データ圧縮装置１５Ｃは、１つのシンボル（ここでは、ＥＯＢシンボル）のエントロピー符号化に複数サイクルを要する構成であってもよい。また、ＥＯＢシンボルに対応する可変長符号を含むことにより、圧縮ストリーム３３Ｃ－１のデータ量が増加する。

図６は、第１比較例に係るデータ伸張装置の構成を示すブロック図である。データ伸張装置１６Ｃ－１は、エントロピー復号および辞書式伸張により、圧縮ストリーム３３Ｃ－１を非圧縮データ３１Ｃに伸張する伸張器（復号器）である。圧縮ストリーム３３Ｃ－１は、１つ以上のハフマンブロックに対応する伸張対象のデータである。データ伸張装置１６Ｃ－１は、エントロピー復号部５１Ｃと、辞書式伸張部５２Ｃとを備える。

エントロピー復号部５１Ｃは、エントロピー復号により圧縮ストリーム３３Ｃ－１から辞書圧縮シンボル３２Ｃを生成する。エントロピー復号部５１Ｃは、ヘッダ／ペイロード分離部５１１Ｃ、符号化テーブル復元部５１２Ｃ、可変長復号部５１３Ｃ、およびＥＯＢ検出部５１４Ｃを含む。

ヘッダ／ペイロード分離部５１１Ｃは、圧縮ストリーム３３Ｃ－１に含まれるヘッダ部３３１Ｃ－１とペイロード部３３２Ｃ－１とを分離する。ヘッダ／ペイロード分離部５１１Ｃは、ヘッダ部３３１Ｃ－１を符号化テーブル復元部５１２Ｃに送出する。ヘッダ／ペイロード分離部５１１Ｃは、ヘッダ部３３１Ｃ－１に後続するペイロード部３３２Ｃ－１を可変長復号部５１３Ｃに送出する。

符号化テーブル復元部５１２Ｃは、ヘッダ部３３１Ｃ－１に含まれるデータを用いて、符号化テーブル４２Ｃを復元（生成）する。符号化テーブル復元部５１２Ｃは、復元した符号化テーブル４２Ｃを可変長復号部５１３Ｃに送出する。

可変長復号部５１３Ｃは、可変長復号により、ペイロード部３３２Ｃ－１に含まれる複数の可変長符号にそれぞれ対応する複数のシンボルを生成する。具体的には、可変長復号部５１３Ｃは、符号化テーブル４２Ｃに基づいて、ペイロード部３３２Ｃ－１に含まれる複数の可変長符号のそれぞれをシンボルに変換する。変換により得られるシンボルは、辞書圧縮シンボル、またはＥＯＢシンボルである。可変長復号部５１３Ｃは、生成されたシンボルを順にＥＯＢ検出部５１４Ｃと辞書式伸張部５２Ｃとに送出する。

ＥＯＢ検出部５１４Ｃは、可変長復号部５１３Ｃから受け取ったシンボルからＥＯＢシンボルを検出する。具体的には、ＥＯＢ検出部５１４Ｃは、可変長復号部５１３Ｃから受け取ったシンボルが、ＥＯＢシンボルの値と一致する場合、そのシンボルをＥＯＢシンボルとして検出する。ＥＯＢ検出部５１４Ｃは、ＥＯＢシンボルを検出したことに応じ、符号化テーブル復元部５１２Ｃに符号化テーブル４２Ｃの切り替えを通知する。

符号化テーブル復元部５１２Ｃは、ＥＯＢ検出部５１４Ｃからの通知に応じて、ヘッダ／ペイロード分離部５１１Ｃから受け取った次のヘッダ部に含まれるデータを用いて、新たな符号化テーブル４２Ｃを復元する。可変長復号部５１３Ｃは、新たな符号化テーブル４２Ｃを用いて、後続するペイロード部に含まれる複数の可変長符号のそれぞれをシンボルに変換する。

辞書式伸張部５２Ｃは、辞書式伸張により、可変長復号部５１３Ｃから受け取った辞書圧縮シンボルから非圧縮データ３１Ｃを生成する。具体的には、辞書式伸張部５２Ｃは、辞書圧縮シンボルがマッチシンボルである場合、ポインタにより示される過去のバイト列を非圧縮データ３１Ｃとして出力する。辞書式伸張部５２Ｃは、辞書圧縮シンボルがリテラルシンボルである場合、リテラルシンボルをそのまま非圧縮データ３１Ｃとして出力する。なお、辞書式伸張部５２Ｃは、可変長復号部５１３Ｃから受け取ったＥＯＢシンボルを非圧縮データ３１Ｃとして出力しない。図６に示す非圧縮データ３１Ｃでは、ＥＯＢシンボルが非圧縮データ３１Ｃとして出力されないことを、“×”で表している。

データ伸張装置１６Ｃ－１では、ハフマンブロックに対応する辞書圧縮シンボル列が全てリテラルシンボルである場合、可変長復号部５１３ＣがＥＯＢシンボルに対応する可変長符号をエントロピー復号するための、例えば１サイクルの演算により、スループットが低下する。

例えば、可変長復号部５１３Ｃが１サイクル当たり１シンボルをエントロピー復号可能とする。この場合、仮にＥＯＢシンボルに対応する可変長符号の復号を考慮しなければ、非圧縮データ３１Ｃを出力する際の伸張スループットは、辞書圧縮シンボル列が全てリテラルシンボルであることで復号すべきシンボル数が最多となる最悪のケースでも、１サイクル当たり１バイトを保証できる。しかしながら、ＥＯＢシンボルに対応する可変長符号をさらに復号するならば、この復号のための追加の１サイクルが必要であるので、同じ非圧縮データ３１Ｃを出力する際の伸張スループットは、１サイクル当たり１バイト未満になり、低下する。

したがって、第１比較例のデータ伸張装置１６Ｃ－１では、ハフマンブロックに対応する辞書圧縮シンボル列が全てリテラルシンボルである場合、スループットが低下する。

（第２比較例）
なお、データの圧縮および伸張を行うシステムでは、圧縮対象のデータ単位が、すなわちハフマンブロックのサイズが、例えば、４ＫｉＢ、８ＫｉＢ、等として指定される場合がある。その場合、圧縮ストリームにＥＯＢシンボルを含めなくとも、圧縮ストリームを復号して得られる非圧縮データのサイズ（例えば、バイト数）に基づいて、ハフマンブロック間の境界（すなわち、各ハフマンブロックの終端）を検出可能である。

そこで、第２比較例に係るデータ伸張装置として、圧縮ストリームを復号して得られる非圧縮データのサイズに基づいて、ハフマンブロック間の境界を検出するデータ伸張装置を説明する。

図７は、第２比較例に係るデータ伸張装置の構成を示すブロック図である。第２比較例のデータ伸張装置１６Ｃ－２は、第１比較例のデータ伸張装置１６Ｃ－１と同様に、エントロピー復号および辞書式伸張により、圧縮ストリーム３３Ｃ－２を非圧縮データ３１Ｃに伸張する伸張器である。第２比較例のデータ伸張装置１６Ｃ－２は、ＥＯＢ検出部５１４Ｃの代わりにブロック境界判定部５１５Ｃを備える点で、第１比較例のデータ伸張装置１６Ｃ－１と異なる。以下では、第１比較例のデータ伸張装置１６Ｃ－１と異なる点について主に説明する。

圧縮ストリーム３３Ｃ－２は、１つ以上のハフマンブロックに対応する圧縮ストリームである。圧縮ストリーム３３Ｃ－２には、ＥＯＢシンボルに対応する可変長符号は含まれていない。具体的には、圧縮ストリーム３３Ｃ－２は、ハフマンブロック毎に、符号化テーブル４２Ｃを含むヘッダ部３３１Ｃ－２と、辞書圧縮シンボルに対応する可変長符号を含むペイロード部３３２Ｃ－２とで構成される。

符号化テーブル復元部５１２Ｃは、ヘッダ部３３１Ｃ－２に含まれるデータを用いて、符号化テーブル４２Ｃを復元する。符号化テーブル復元部５１２Ｃは、復元した符号化テーブル４２Ｃを可変長復号部５１３Ｃに送出する。

可変長復号部５１３Ｃは、符号化テーブル４２Ｃに基づいて、ペイロード部３３２Ｃ－２に含まれる各可変長符号を辞書圧縮シンボルに変換する。可変長復号部５１３Ｃは、辞書圧縮シンボルを辞書式伸長部５２Ｃとブロック境界判定部５１５Ｃとに送出する。

ブロック境界判定部５１５Ｃは、可変長復号部５１３Ｃから辞書圧縮シンボルを受け取る毎に、その辞書圧縮シンボルが辞書式伸張された場合のデータサイズを取得し、取得したデータサイズの累積値（非圧縮データサイズ）を算出する。辞書圧縮シンボルがリテラルシンボルである場合、辞書式伸張された場合のデータサイズは、例えば１バイトである。辞書圧縮シンボルがマッチシンボルである場合、辞書式伸張された場合のデータサイズは、例えば、そのマッチシンボルが示すバイト単位の一致長である。ブロック境界判定部５１５Ｃは、算出した非圧縮データサイズの累積値が特定のサイズに達した場合、直前にデータサイズを取得した辞書圧縮シンボルが１つのハフマンブロックの終端であると判断する。特定のサイズは、例えば、ブロックサイズ情報４１Ｃで示される１つのハフマンブロックのサイズ（ブロックサイズ）である。これにより、ブロック境界判定部５１５Ｃは、ハフマンブロック間の境界を検出できる。ブロック境界判定部５１５Ｃは、ハフマンブロック間の境界を検出したことに応じ、符号化テーブル４２Ｃの切り替えを符号化テーブル復元部５１２Ｃに通知する。

図８のフローチャートを参照して、ブロック境界判定部５１５Ｃによる処理を具体的に説明する。図８は、第２比較例に係るデータ伸張装置１６Ｃ－２において実行されるブロック境界判定処理の手順を示すフローチャートである。ブロック境界判定部５１５Ｃは、例えば、データ伸張装置１６Ｃ－２に圧縮ストリーム３３Ｃ－２が入力されたことに応じ、ブロック境界判定処理を実行する。

まず、ブロック境界判定部５１５Ｃは、非圧縮データサイズＤＳを初期化する（ステップＳ１０１）。つまり、ブロック境界判定部５１５Ｃは、非圧縮データサイズＤＳを０に設定する。

次に、ブロック境界判定部５１５Ｃは、可変長復号部５１３Ｃから辞書圧縮シンボルを受信する（ステップＳ１０２）。そして、ブロック境界判定部５１５Ｃは、受信した辞書圧縮シンボルの種類がリテラルシンボルとマッチシンボルのいずれであるかを判定する（ステップＳ１０３）。

受信した辞書圧縮シンボルがマッチシンボルである場合（ステップＳ１０３の“マッチ”）、ブロック境界判定部５１５Ｃは、非圧縮データサイズＤＳにそのマッチシンボルが示す一致長を加算し（ステップＳ１０４）、ステップＳ１０６に進む。

受信した辞書圧縮シンボルがリテラルシンボルである場合（ステップＳ１０３の“リテラル”）、ブロック境界判定部５１５Ｃは、非圧縮データサイズＤＳに１を加算し（ステップＳ１０５）、ステップＳ１０６に進む。

次いで、ブロック境界判定部５１５Ｃは、非圧縮データサイズＤＳがブロックサイズ以上であるか否かを判定する（ステップＳ１０６）。ブロック境界判定部５１５Ｃは、例えば、データ伸張装置１６Ｃ－２に予め格納されているブロックサイズ情報４１Ｃから、ブロックサイズを取得する。

非圧縮データサイズＤＳがブロックサイズ未満である場合（ステップＳ１０６のＮｏ）、ブロック境界判定部５１５Ｃによる処理はステップＳ１０２に戻る。つまり、ブロック境界判定部５１５Ｃは、可変長復号部５１３Ｃから辞書圧縮シンボルを受信して、非圧縮データサイズＤＳがブロックサイズに達したかどうかに基づきハフマンブロック間の境界を検出する処理をさらに行う。

非圧縮データサイズＤＳがブロックサイズ以上である場合（ステップＳ１０６のＹｅｓ）、ブロック境界判定部５１５Ｃは、現在のハフマンブロックと次のハフマンブロックとの境界を検出したと判断して、ブロック境界フラグを符号化テーブル復元部５１２Ｃに出力し（ステップＳ１０７）、ステップＳ１０１に戻る。

ブロック境界フラグは、可変長復号部５１３Ｃから直前に受け取った辞書圧縮シンボルがハフマンブロックの終端であることを示す情報である。ブロック境界フラグは、符号化テーブル４２Ｃの切り替えを符号化テーブル復元部５１２Ｃに指示するために用いられる。符号化テーブル復元部５１２Ｃは、ブロック境界フラグを受け取ったことに応じて、圧縮ストリーム３３Ｃ－２内の後続するヘッダ部を取得する。符号化テーブル復元部５１２Ｃは、取得したヘッダ部を用いて新たな符号化テーブル４２Ｃを生成して、前の符号化テーブル４２Ｃから切り替える。これにより、可変長復号部５１３Ｃは、新たな符号化テーブル４２Ｃを用いて、圧縮ストリーム３３Ｃ－２内の後続する可変長符号（ペイロード部）を辞書圧縮シンボルに復号する。

第２比較例のデータ伸張装置１６Ｃ－２において、可変長復号のスループット（例えば１サイクルあたり１シンボルを復号）を低下させないためには、可変長復号、ブロック境界判定、および符号化テーブル４２Ｃの切り替えを、１サイクルで実行する必要がある。しかし、ブロック境界判定部５１５Ｃにおいて非圧縮データサイズＤＳを計算する演算が追加されるため、この計算に要する遅延時間の分だけエントロピー復号部５１Ｃの最大動作周波数を落とす必要がある。したがって、可変長復号のスループットが低下する可能性がある。つまり、図７に示すように、可変長復号、ブロック境界判定、および符号化テーブル４２Ｃの切り替えの一連の動作は、可変長復号のスループットに関するクリティカルパスとなる。

図８のフローチャートを参照して前述した通り、ブロック境界判定部５１５Ｃは、可変長復号して得られた辞書圧縮シンボルを入力として受け取ると、その辞書圧縮シンボルの種類を判定する。ブロック境界判定部５１５Ｃは、１つのハフマンブロックに対応する各辞書圧縮シンボルが辞書式伸長された場合のデータサイズの累積値を示す非圧縮データサイズＤＳに、受け取った辞書圧縮シンボルの種類に応じた値を加算する。つまり、受け取った辞書圧縮シンボルがマッチシンボルである場合、ブロック境界判定部５１５Ｃは、非圧縮データサイズＤＳに一致長（例えば、バイト単位の一致長）を加算する。一方、受け取った辞書圧縮シンボルがリテラルシンボルである場合、ブロック境界判定部５１５Ｃは、非圧縮データサイズＤＳに１バイトを加算する。そして、ブロック境界判定部５１５Ｃは、更新された非圧縮データサイズＤＳに基づいて、ハフマンブロック間の境界であるかどうかを判定する。

このようなブロック境界判定部５１５Ｃによるハフマンブロック間の境界の判定では、必要な演算の論理段数が増加する。この場合、ブロック境界判定部５１５Ｃを回路実装した場合の遅延時間が長くなる。そのため、第２比較例のデータ伸張装置１６Ｃ－２では、動作周波数が低くなり、スループットが低下する可能性がある。

これに対して、実施形態に係るデータ圧縮装置１５およびデータ伸張装置１６は、処理のスループットと、圧縮効率とを向上できる。

具体的には、データ圧縮装置１５は、ハフマンブロックに対する辞書式圧縮で得られた１つ以上のシンボルが全てリテラルシンボルである場合、１つ以上のシンボルの終端にＥＯＢシンボルを追加しない。これにより、データ圧縮装置１５では、エントロピー符号化の対象となるシンボル数が減少するので、符号化のスループットと、圧縮効率とを向上できる。

また、データ圧縮装置１５においてハフマンブロックに対する辞書式圧縮で得られた１つ以上のシンボルが全てリテラルシンボルである場合、データ伸張装置１６は、圧縮ストリームを可変長復号して得られたリテラルシンボルの数に基づいて、ハフマンブロックの終端を検出できる。これにより、データ伸張装置１６では、第１比較例のデータ伸張装置１６Ｃ－１におけるＥＯＢシンボルを復号する処理サイクルが不要であり、また第２比較例のデータ伸張装置１６Ｃ－２における可変長復号で得られた辞書圧縮シンボルの種類に応じた非圧縮データサイズＤＳの計算も不要である。したがって、データ伸張装置１６では復号のスループットを向上できる。

図９から図１２を参照して、データ圧縮装置１５とデータ伸張装置１６のそれぞれの構成および動作について説明する。

（データ圧縮装置１５）
図９は、実施形態に係るデータ圧縮装置１５の構成例を示すブロック図である。データ圧縮装置１５は、辞書式圧縮およびエントロピー符号化により、非圧縮データ３１を圧縮ストリーム３３に圧縮する圧縮器である。非圧縮データ３１は、例えば、１つ以上のハフマンブロックを含む圧縮対象のデータである。データ圧縮装置１５は、辞書式圧縮部２１と、エントロピー符号化部２２とを備える。

辞書式圧縮部２１は、辞書式圧縮により非圧縮データ３１を辞書圧縮シンボル３２に変換する。辞書圧縮シンボル３２は、リテラルシンボルとマッチシンボルのいずれかである。辞書式圧縮部２１は、辞書圧縮シンボル３２をエントロピー符号化部２２に送出する。

エントロピー符号化部２２は、エントロピー符号化により辞書圧縮シンボル３２を可変長符号に変換して、圧縮ストリーム３３を生成する。エントロピー符号化部２２は、例えば、全リテラル判定部２２４、ＥＯＢ追加部２２１、符号化テーブル生成部２２２、および可変長符号化部２２３を含む。

辞書式圧縮部２１、ＥＯＢ追加部２２１、符号化テーブル生成部２２２、可変長符号化部２２３、全リテラル判定部２２４は、レジスタ、加算器、乗算器、セレクタ、および、その他の演算器のうちの少なくとも一つにより実現される。レジスタは、例えば、フリップフロップのような論理回路で実現される。加算器、乗算器、セレクタ、および、その他の演算器は、例えば、論理回路で実現される。

全リテラル判定部２２４は、第１のタイミング以降に連続して辞書式圧縮部２１から受け取った１つ以上の辞書圧縮シンボル３２（以下、辞書圧縮シンボル列３２とも称する）が、全てリテラルシンボルであるか否かを判定する。第１のタイミングは、データ圧縮装置１５におけるデータ圧縮処理が開始されたタイミング、またはＥＯＢ追加部２２１によってハフマンブロックの終端が通知されたタイミング（後述するブロック終端フラグを受け取ったタイミング）である。辞書圧縮シンボル列３２は、例えば、１つのハフマンブロック（第１データブロック）に対する辞書式圧縮により得られたデータブロック（第２データブロック）に含まれる１つ以上の辞書圧縮シンボル３２である。全リテラル判定部２２４は、例えば、辞書圧縮シンボル列３２に含まれる各シンボルのバイト値が、予め規定された（例えば、ＤＥＦＬＡＴＥで規定された）いずれかのリテラルシンボルのバイト値と一致するか否かに基づいて、辞書圧縮シンボル列３２が全てリテラルシンボルであるか否かを判定する。

全リテラル判定部２２４は、辞書圧縮シンボル列３２が全てリテラルシンボルであるか否かを示す情報（以下、全リテラル判定情報とも称する）を、ＥＯＢ追加部２２１に送出する。全リテラル判定情報は、例えば、ｔｒｕｅ（真）とｆａｌｓｅ（偽）のいずれかを示す情報である。ｔｒｕｅを示す値として、例えば、１が用いられる。ｆａｌｓｅを示す値として、例えば、０が用いられる。より具体的には、全リテラル判定部２２４は、例えば、常時、あるいは一定時間毎に、全リテラル判定情報を含む信号をＥＯＢ追加部２２１に送出する。

また、全リテラル判定部２２４には、ＥＯＢ追加部２２１によってブロック終端フラグが送出される。ブロック終端フラグは、ハフマンブロックの終端（すなわち、判定対象の辞書圧縮シンボル列３２の終端が、ハフマンブロックの終端に対応すること）を示す情報である。ＥＯＢ追加部２２１によってブロック終端フラグが送出されたことに応じ、全リテラル判定部２２４は、現在の全リテラル判定情報をヘッダ部３３１として出力してもよい。この全リテラル判定情報は、例えばデータ伸張装置１６において、圧縮ストリーム３３に対するエントロピー復号で得られた辞書圧縮シンボルに対応するハフマンブロックが、全てリテラルシンボルであるハフマンブロックであるかどうかの判定に用いられる。

ＥＯＢ追加部２２１は、全リテラル判定情報がｆａｌｓｅを示す場合に、１つのハフマンブロックに対応する１つ以上の辞書圧縮シンボル３２の終端（末尾）にＥＯＢシンボルを追加する。

具体的には、ＥＯＢ追加部２２１は、例えば、辞書式圧縮部２１から１つの辞書圧縮シンボル３２を受け取る（取り込む）毎に、その辞書圧縮シンボル３２が辞書式圧縮される前のデータサイズを取得し、取得したデータサイズの累積値（非圧縮データサイズ）を算出する。辞書圧縮シンボル３２がリテラルシンボルである場合、辞書式圧縮される前のデータサイズは、例えば１バイトである。辞書圧縮シンボル３２がマッチシンボルである場合、辞書式圧縮される前のデータサイズは、例えば、そのマッチシンボルが示すバイト単位の一致長である。ＥＯＢ追加部２２１は、データサイズを取得した辞書圧縮シンボル３２を、符号化テーブル生成部２２２と可変長符号化部２２３とに送出する。

ＥＯＢ追加部２２１は、算出した非圧縮データサイズと、ブロックサイズ情報４１とに基づいて、非圧縮データサイズの算出に用いた１つ以上の辞書圧縮シンボル３２の終端がハフマンブロックの終端に対応するか否かを判定する。ブロックサイズ情報４１は、１つのハフマンブロックのサイズ（ブロックサイズ）を示す。ブロックサイズ情報４１は、例えば、情報処理システム１において規定されたブロックサイズに基づいて生成される。ブロックサイズ情報４１は、データ圧縮装置１５（またはメモリシステム３）内の任意の記憶領域に予め格納されていてもよいし、外部（例えば、ホスト２）から受信されてもよい。ＥＯＢ追加部２２１は、算出した非圧縮データサイズがブロックサイズに達したか否かに基づいて、１つ以上の辞書圧縮シンボル３２の終端がハフマンブロックの終端に対応するか否かを判定する。１つ以上の辞書圧縮シンボル３２の終端（末尾）のシンボルは、データサイズを直前（最後）に取得したシンボルである。

算出した非圧縮データサイズがブロックサイズに達した場合（すなわち、１つ以上の辞書圧縮シンボル３２の終端がハフマンブロックの終端に対応する場合）、ＥＯＢ追加部２２１は、全リテラル判定部２２４から受け取った全リテラル判定情報がｔｒｕｅとｆａｌｓｅのいずれを示しているかを判定する。

全リテラル判定情報がｆａｌｓｅを示す場合、ＥＯＢ追加部２２１は、現在のハフマンブロックの終端にＥＯＢシンボルを追加する。つまり、ＥＯＢ追加部２２１は、符号化テーブル生成部２２２と可変長符号化部２２３とにＥＯＢシンボルを送出する。送出したＥＯＢシンボルは、直前にデータサイズを取得した辞書圧縮シンボル３２に後に配置される。

一方、全リテラル判定情報がｔｒｕｅを示す場合、ＥＯＢ追加部２２１は、現在のハフマンブロックの終端にＥＯＢシンボルを追加しない。つまり、ＥＯＢ追加部２２１は、符号化テーブル生成部２２２と可変長符号化部２２３とにＥＯＢシンボルを送出しない。したがって、直前にデータサイズを取得した辞書圧縮シンボル３２の後にＥＯＢシンボルは配置されない。

そして、ＥＯＢ追加部２２１は、非圧縮データサイズの算出に用いた１つ以上の辞書圧縮シンボル３２の終端がハフマンブロックの終端に対応することを示す情報（ブロック終端フラグ）を、全リテラル判定部２２４に送出する。ＥＯＢ追加部２２１は、ブロック終端フラグを符号化テーブル生成部２２２に送出してもよい。

符号化テーブル生成部２２２は、１つのハフマンブロックに対応する複数のシンボルのシンボル毎の出現頻度に基づいて、符号化テーブル４２を生成する。１つのハフマンブロックに対応する複数のシンボルは、例えば、第１のタイミングからブロック終端フラグを受け取るまでにＥＯＢ追加部２２１から受け取ったシンボルを含む。具体的には、符号化テーブル生成部２２２は、出現頻度が高いシンボルに短い符号語を割り当て、出現頻度が低いシンボルに長い符号語を割り当てる。符号化テーブル生成部２２２は、生成した符号化テーブル４２を可変長符号化部２２３に送出する。また、符号化テーブル生成部２２２は、符号化テーブル４２を示すデータを、圧縮ストリーム３３のヘッダ部３３１として出力する。

可変長符号化部２２３は、可変長符号化により、１つのハフマンブロックに対応する複数のシンボルにそれぞれ対応する複数の可変長符号を生成する。具体的には、可変長符号化部２２３は、符号化テーブル４２に基づいて、１つのハフマンブロックに対応する複数のシンボルのそれぞれを可変長符号に変換する。可変長符号化部２２３は、各シンボルから変換された可変長符号を、圧縮ストリーム３３のペイロード部３３２として順に出力する。ＥＯＢ追加部２２１によってＥＯＢシンボルが追加された場合、ペイロード部３３２は、１つ以上の辞書圧縮シンボル３２のそれぞれに対応する可変長符号と、ＥＯＢブロックに対応する末尾の可変長符号とを含む。ＥＯＢ追加部２２１によってＥＯＢシンボルが追加されなかった場合、ペイロード部３３２は、全てリテラルシンボルである複数の辞書圧縮シンボル３２のそれぞれに対応する可変長符号を含む。

なお、符号化テーブル生成部２２２は、ＥＯＢ追加部２２１から次のハフマンブロックに対応する複数のシンボルを受け取った場合、新たな符号化テーブル４２を生成して、可変長符号化部２２３に送出する。可変長符号化部２２３は、新たな符号化テーブル４２を用いて、そのハフマンブロックに対応する複数のシンボルのそれぞれを可変長符号に変換する。

したがって、圧縮ストリーム３３は、ハフマンブロック毎の、符号化テーブル４２を含むヘッダ部３３１と、ペイロード部３３２とで構成される。ペイロード部３３２は、（Ａ）辞書圧縮シンボル列３２およびＥＯＢシンボルを可変長符号化した可変長符号列と、（Ｂ）全てリテラルシンボルである辞書圧縮シンボル列３２を可変長符号化した可変長符号列のいずれかを含む。

なお、ペイロード部３３２が、（Ｂ）全てリテラルシンボルである辞書圧縮シンボル列３２を可変長符号化した可変長符号列を含む場合、ヘッダ部３３１は、その可変長符号列のサイズを示す情報（以下、圧縮サイズ情報と称する）をさらに含んでいてもよい。ペイロード部３３２に含まれる可変長符号列のサイズは、対応するハフマンブロックに対する辞書式圧縮およびエントロピー符号化により得られる可変長符号列（すなわち、圧縮されたハフマンブロック）のサイズである。圧縮サイズ情報は、例えばデータ伸張装置１６において、圧縮ストリーム３３内の１つ以上の可変長符号（可変長符号列）に対するエントロピー復号で１つ以上のシンボルが得られた場合に、それら１つ以上の可変長符号の終端がハフマンブロックの終端に対応するかどうかの判定に用いられる。つまり、圧縮サイズ情報は、ハフマンブロック間の境界の判定に用いられる。

ここで、全リテラル判定部２２４による具体的な処理の例を示すと共に、ＥＯＢ追加部２２１が全リテラル判定情報に応じてＥＯＢシンボルを追加するか否かを変更することによる効果について説明する。

図１０は、実施形態に係るデータ圧縮装置１５において実行される全リテラル判定処理の手順の例を示すフローチャートである。全リテラル判定処理は、ハフマンブロックに対応する１つ以上の辞書圧縮シンボル３２が全てリテラルシンボルであるか否かを判定する処理である。全リテラル判定部２２４は、例えば、データ圧縮装置１５に非圧縮データ３１が入力されたことに応じ、全リテラル判定処理を実行する。ここでは、全リテラル判定処理に、変数Ｌが用いられる例を示す。変数Ｌは、変数Ｌが初期化された後に全リテラル判定部２２４が辞書式圧縮部２１から受け取った１つ以上の辞書圧縮シンボル３２が、全てリテラルシンボルであったか否かを示す変数である。

まず、全リテラル判定部２２４は、変数Ｌを初期化する（ステップＳ２０１）。具体的には、全リテラル判定部２２４は、変数Ｌをｔｒｕｅに設定する。変数Ｌは、例えば、ｔｒｕｅとｆａｌｓｅのいずれかに設定される。ｔｒｕｅは、例えば、変数Ｌが初期化された後に辞書式圧縮部２１から受け取った１つ以上の辞書圧縮シンボル３２が全てリテラルシンボルであったことを示す。ｆａｌｓｅは、例えば、変数Ｌが初期化された後に辞書式圧縮部２１から受け取った１つ以上の辞書圧縮シンボル３２の少なくとも１つがリテラルシンボルでなかったこと（すなわち、マッチシンボルであったこと）を示す。変数Ｌを含む信号は、全リテラル判定部２２４からＥＯＢ追加部２２１へ全リテラル判定情報として出力される。

全リテラル判定部２２４は、辞書式圧縮部２１から辞書圧縮シンボル３２を受信する（ステップＳ２０２）。そして、全リテラル判定部２２４は、変数Ｌがｔｒｕｅであるか否かを判定する（ステップＳ２０３）。

変数Ｌがｆａｌｓｅである場合（ステップＳ２０３のＮｏ）、全リテラル判定部２２４はステップＳ２０６に進む。

変数Ｌがｔｒｕｅである場合（ステップＳ２０３のＹｅｓ）、全リテラル判定部２２４は、受信した辞書圧縮シンボルがリテラルシンボルであるか否かを判定する（ステップＳ２０４）。

受信した辞書圧縮シンボルがリテラルシンボルである場合（ステップＳ２０４のＹｅｓ）、全リテラル判定部２２４はステップＳ２０６に進む。

受信した辞書圧縮シンボルがリテラルシンボルでない場合（ステップＳ２０４のＮｏ）全リテラル判定部２２４は、変数Ｌをｆａｌｓｅに設定し（ステップＳ２０５）、ステップＳ２０６に進む。

次いで、全リテラル判定部２２４は、現在のハフマンブロックの終端を示す信号（ブロック終端フラグ）を、ＥＯＢ追加部２２１から受信したか否かを判定する（ステップＳ２０６）。

現在のハフマンブロックの終端を示す信号をＥＯＢ追加部２２１から受信していない場合（ステップＳ２０６のＮｏ）、全リテラル判定部２２４はステップＳ２０２に戻る。つまり、全リテラル判定部２２４は、辞書式圧縮部２１から辞書圧縮シンボルを受信し、変数Ｌがｔｒｕｅである間、受信した辞書圧縮シンボルがリテラルシンボルであるか否かを判定する処理をさらに行う。

現在のハフマンブロックの終端を示す信号をＥＯＢ追加部２２１から受信している場合（ステップＳ２０６のＹｅｓ）、全リテラル判定部２２４はステップＳ２０１に戻る。つまり、全リテラル判定部２２４は、変数Ｌを初期化して、次のハフマンブロックに対する辞書式圧縮によって得られるシンボルが全てリテラルシンボルであるかどうかを判定する処理をさらに行う。

以上の全リテラル判定処理により、全リテラル判定部２２４は、変数Ｌを用いて、ハフマンブロックに対する辞書式圧縮によって得られたシンボルが全てリテラルシンボルであるか否かを示す信号（全リテラル判定情報）を、ＥＯＢ追加部２２１に出力できる。

具体的には、ハフマンブロックに対する辞書式圧縮によって得られた１つ以上の辞書圧縮シンボル３２が全てリテラルシンボルである場合（すなわち、変数Ｌがｔｒｕｅである場合）、ＥＯＢ追加部２２１は、それら複数の辞書圧縮シンボル３２の末尾にＥＯＢシンボルを追加しない。これにより、データ圧縮装置１５では、エントロピー符号化の対象となるシンボル数が減少するので、圧縮効率と、符号化のスループットとを向上できる。

一方、ハフマンブロックに対する辞書式圧縮によって得られた１つ以上の辞書圧縮シンボル３２の少なくとも１つがリテラルシンボルでない場合（すなわち、変数Ｌがｆａｌｓｅである場合）、ＥＯＢ追加部２２１は、それら複数の辞書圧縮シンボル３２の末尾にＥＯＢシンボルを追加する。この場合、ＥＯＢシンボルを用いてハフマンブロック間の境界を検出できるので、例えば、第２比較例のデータ伸張装置１６Ｃ－２のように可変長復号で得られた辞書圧縮シンボルの種類に応じた非圧縮データサイズＤＳを計算する必要がない。したがって、データ伸張装置１６における復号のスループットの低下を回避できる。

以上の構成により、データ圧縮装置１５は、辞書式圧縮およびエントロピー符号化により、非圧縮データ３１を圧縮ストリーム３３に圧縮できる。データ圧縮装置１５は、ハフマンブロックに対する辞書式圧縮によって得られた１つ以上の辞書圧縮シンボル３２が全てリテラルシンボルである場合、ＥＯＢシンボルを追加しないことにより、圧縮効率と、符号化のスループットとを向上できる。また、データ圧縮装置１５は、ハフマンブロックに対する辞書式圧縮によって得られた１つ以上の辞書圧縮シンボル３２の少なくとも１つがリテラルシンボルでない場合、ＥＯＢシンボルを追加することにより、復号時のスループットの低下を回避できる。

（データ伸張装置１６）
図１１は、実施形態に係るデータ伸張装置の構成例を示すブロック図である。データ伸張装置１６は、エントロピー復号および辞書式伸張により、圧縮ストリーム３３を非圧縮データ３１に伸張する伸張器である。圧縮ストリーム３３は、１つ以上のハフマンブロックに対応する伸張対象のデータである。データ伸張装置１６は、エントロピー復号部５１と、辞書式伸張部５２とを備える。

エントロピー復号部５１は、エントロピー復号により圧縮ストリーム３３から辞書圧縮シンボル３２を生成する。エントロピー復号部５１は、例えば、ヘッダ／ペイロード分離部５１１、符号化テーブル復元部５１２、可変長復号部５１３、ＥＯＢ検出部５１４、ブロック境界判定部５１５、全リテラル判定部５１６、およびマルチプレクサ（ＭＵＸ）５１７を含む。

辞書式伸張部５２、ヘッダ／ペイロード分離部５１１、符号化テーブル復元部５１２、可変長復号部５１３、ＥＯＢ検出部５１４、ブロック境界判定部５１５、全リテラル判定部５１６、ＭＵＸ５１７は、レジスタ、加算器、乗算器、セレクタ、および、その他の演算器のうちの少なくとも一つにより実現される。レジスタは、例えば、フリップフロップのような論理回路で実現される。加算器、乗算器、セレクタ、および、その他の演算器は、例えば、論理回路で実現される。

ヘッダ／ペイロード分離部５１１は、圧縮ストリーム３３に含まれるヘッダ部３３１とペイロード部３３２とを分離する。ヘッダ／ペイロード分離部５１１は、ヘッダ部３３１を符号化テーブル復元部５１２に送出する。ヘッダ／ペイロード分離部５１１は、ヘッダ部３３１に後続するペイロード部３３２を可変長復号部５１３に送出する。なお、ヘッダ部３３１に全リテラル判定情報が含まれる場合、ヘッダ／ペイロード分離部５１１は、全リテラル判定情報を全リテラル判定部５１６に送出してもよい。

符号化テーブル復元部５１２は、ヘッダ部３３１に含まれるデータを用いて、符号化テーブル４２を復元する。符号化テーブル復元部５１２は、復元した符号化テーブル４２を可変長復号部５１３に送出する。

可変長復号部５１３は、可変長復号により、ペイロード部３３２に含まれる複数の可変長符号にそれぞれ対応する複数のシンボルを生成する。具体的には、可変長復号部５１３は、符号化テーブル４２に基づいて、ペイロード部３３２に含まれる複数の可変長符号のそれぞれをシンボルに変換する。変換により得られるシンボルは、辞書圧縮シンボル、またはＥＯＢシンボルである。可変長復号部５１３は、生成したシンボルを順に、ＥＯＢ検出部５１４、ブロック境界判定部５１５、全リテラル判定部５１６、および辞書式伸張部５２のそれぞれに送出する。

ＥＯＢ検出部５１４は、可変長復号部５１３から受け取ったシンボルからＥＯＢシンボルを検出し、ＥＯＢシンボルを検出したことを示す情報をＭＵＸ５１７とブロック境界判定部５１５とに送出する。ＥＯＢシンボルを検出したことを示す情報を、ＥＯＢ検出フラグとも称する。

具体的には、ＥＯＢ検出部５１４は、可変長復号部５１３からシンボルを受け取る毎に、そのシンボルがＥＯＢシンボルと一致するか否かを判定する。例えば、可変長復号部５１３から１つ以上のシンボルを受け取る場合、ＥＯＢ検出部５１４は、それら１つ以上のシンボルの先頭から順にＥＯＢシンボル（より詳しくは、ＥＯＢシンボルに割り当てられた値）と一致するか否かを判定する。先頭のシンボルから末尾のシンボルの一つ前のシンボルまでＥＯＢシンボルが検出されなかった場合、末尾のシンボルがＥＯＢシンボルと一致するか否かを判定する。ＥＯＢ検出部５１４は、その末尾のシンボルがＥＯＢシンボルと一致する場合、その末尾のシンボルをＥＯＢシンボルとして検出する。これにより、ＥＯＢ検出部５１４は、それら１つ以上のシンボルの終端が、ハフマンブロックの終端に対応することを検出する。そして、ＥＯＢ検出部５１４は、ＥＯＢ検出フラグ（すなわち、１つ以上のシンボルの終端がハフマンブロックの終端に対応することを示す情報）を、ＭＵＸ５１７とブロック境界判定部５１５とに送出する。

ブロック境界判定部５１５は、第２のタイミング以降に連続して可変長復号部５１３から受け取った１つ以上のシンボルの終端が、ハフマンブロックの終端に対応することを示す情報（ブロック境界フラグ）をＭＵＸ５１７に送出する。第２のタイミングは、データ伸張装置１６におけるデータ伸張処理が開始されたタイミング、またはＥＯＢ検出部５１４からＥＯＢ検出フラグを受け取ったタイミングである。

具体的には、ブロック境界判定部５１５は、可変長復号部５１３からシンボルを受け取る毎に、そのシンボルが辞書式伸張された場合のデータサイズを取得し、取得したデータサイズの累積値（非圧縮データサイズ）を算出する。ブロック境界判定部５１５は、受け取ったシンボルがリテラルシンボルであると仮定して、そのシンボルが辞書式伸張された場合のデータサイズを取得する。リテラルシンボルは辞書式圧縮されていないシンボルであるので、リテラルシンボルが辞書式伸張された場合のデータサイズは、例えば１バイトである。したがって、ブロック境界判定部５１５は、可変長復号部５１３から受け取ったシンボルがリテラルシンボルであると仮定することにより、受け取ったシンボルの数をカウントすることで、非圧縮データサイズを容易に算出できる。

ブロック境界判定部５１５は、算出した非圧縮データサイズと、ブロックサイズ情報４１とに基づいて、非圧縮データサイズの算出に用いた１つ以上のシンボルの終端がハフマンブロックの終端に対応するか否かを判定する。ブロックサイズ情報４１は、データ伸張装置１６（またはメモリシステム３）内の任意の記憶領域に予め格納されていてもよいし、外部（例えば、ホスト２）から受信されてもよい。具体的には、ブロック境界判定部５１５は、算出した非圧縮データサイズがブロックサイズに達したことに応じ、それら１つ以上のシンボルの終端がハフマンブロックの終端に対応すると判断する。直前にデータサイズを算出したシンボルは、１つのハフマンブロックの終端に対応する。これにより、ブロック境界判定部５１５は、ハフマンブロック間の境界を検出できる。ブロック境界判定部５１５は、ハフマンブロック間の境界を検出したことに応じ、ブロック境界フラグをＭＵＸ５１７に送出する。ブロック境界フラグは、例えば、ハフマンブロック間の境界を検出したこと（すなわち、１つ以上のシンボルの終端がハフマンブロックの終端に対応すること）を示す信号である。なお、ブロック境界判定部５１５による具体的な処理の例は、図１２のフローチャートを参照して後述する。

全リテラル判定部５１６は、第３のタイミング以降に連続して可変長復号部５１３から受け取った１つ以上のシンボル（以下、対象シンボル列とも称する）が、全てリテラルシンボルであるか否かを示す情報（全リテラル判定情報）を、ＭＵＸ５１７とブロック境界判定部５１５とに送出する。第３のタイミングは、データ伸張装置１６におけるデータ伸張処理が開始されたタイミング、またはＭＵＸ５１７によってハフマンブロックの終端が通知されたタイミングである。全リテラル判定部５１６は、例えば、対象シンボル列に含まれる各シンボルのバイト値が、予め規定された（例えば、ＤＥＦＬＡＴＥで規定された）いずれかのリテラルシンボルのバイト値と一致するか否かに基づいて、対象シンボル列が全てリテラルシンボルであるか否かを判定する。

なお、全リテラル判定部５１６は、ヘッダ／ペイロード分離部５１１から受け取った全リテラル判定情報（すなわち、ヘッダ部３３１内の全リテラル判定情報）を用いて、対象シンボル列が全てリテラルシンボルであるか否かを判定してもよい。この場合、全リテラル判定部５１６の回路規模（演算量）を削減できる。

全リテラル判定部５１６は、例えば、常時、あるいは一定時間毎に、全リテラル判定情報をＭＵＸ５１７とブロック境界判定部５１５とに送出する。全リテラル判定部５１６による全リテラル判定処理は、データ圧縮装置１５の全リテラル判定部２２４による全リテラル判定処理とほぼ同様である。より詳しくは、全リテラル判定部５１６による全リテラル判定処理は、図１０のフローチャートを参照して前述した全リテラル判定処理における辞書式圧縮部２１およびＥＯＢ追加部２２１を、全リテラル判定部５１６にシンボルを送出する可変長復号部５１３、およびハフマンブロックの終端を通知するＭＵＸ５１７にそれぞれ置き換えた処理に相当する。

ＭＵＸ５１７は、全リテラル判定情報がｔｒｕｅとｆａｌｓｅのいずれであるかに応じて、ＥＯＢ検出部５１４によって出力されたＥＯＢ検出フラグと、ブロック境界判定部５１５によって出力されたブロック境界フラグのいずれかを出力するセレクタである。なお、図１１に示す例では、ＭＵＸ５１７内において、ｔｒｕｅである全リテラル判定情報を“１”として、ｆａｌｓｅである全リテラル判定情報を“０”として、表している。具体的には、全リテラル判定部５１６からｆａｌｓｅ（図１１では、０）を示す全リテラル判定情報を受け取っている間に、ＥＯＢ検出部５１４からＥＯＢ検出フラグを受け取った場合、ＭＵＸ５１７は、ＥＯＢ検出フラグに基づいて、符号化テーブル４２の切り替えを符号化テーブル復元部５１２に通知し、現在のハフマンブロックの終端を全リテラル判定部５１６に通知する。これに対して、全リテラル判定部５１６からｔｒｕｅ（図１１では、１）を示す全リテラル判定情報を受け取っている間に、ブロック境界判定部５１５からブロック境界フラグを受け取った場合、ＭＵＸ５１７は、ブロック境界フラグに基づいて、符号化テーブル４２の切り替えを符号化テーブル復元部５１２に通知し、現在のハフマンブロックの終端を全リテラル判定部５１６に通知する。具体的には、ＭＵＸ５１７は、符号化テーブル４２の切り替えを通知するために、例えば、符号化テーブル４２の切り替えを示す信号を符号化テーブル復元部５１２に送出する。ＭＵＸ５１７は、現在のハフマンブロックの終端を通知するために、例えば、現在のハフマンブロックの終端を示す信号を全リテラル判定部５１６に送出する。

符号化テーブル復元部５１２は、ＭＵＸ５１７からの符号化テーブル４２の切り替えの通知に応じて、ヘッダ／ペイロード分離部５１１から受け取った次のヘッダ部に含まれるデータを用いて、新たな符号化テーブル４２を復元する。可変長復号部５１３は、新たな符号化テーブル４２を用いて、後続するペイロード部に含まれる複数の可変長符号のそれぞれをシンボルに変換する。

辞書式伸張部５２は、辞書式伸張により、可変長復号部５１３から受け取った辞書圧縮シンボルから非圧縮データ３１を生成する。具体的には、辞書式伸張部５２は、辞書圧縮シンボルがマッチシンボルである場合、ポインタにより示されるヒストリバッファ内の過去のバイト列を、非圧縮データ３１として出力する。辞書式伸張部５２は、辞書圧縮シンボルがリテラルシンボルである場合、リテラルシンボルをそのまま非圧縮データ３１として出力する。なお、辞書式伸張部５２は、可変長復号部５１３から受け取ったＥＯＢシンボルを非圧縮データ３１として出力しない。

ここで、ブロック境界判定部５１５による具体的な処理の例を示すと共に、ＭＵＸ５１７が全リテラル判定情報に応じてＥＯＢ検出フラグとブロック境界フラグのいずれかを選択して、符号化テーブル４２の切り替えを符号化テーブル復元部５１２に通知することによる効果について説明する。

図１２は、実施形態に係るデータ伸張装置１６において実行されるブロック境界判定処理の手順の例を示すフローチャートである。ブロック境界判定処理は、現在のハフマンブロックに対応するシンボル（より詳しくは、可変長復号されたシンボル）が全てリテラルシンボルである場合に、ハフマンブロック間の境界を判定する処理である。ブロック境界判定部５１５は、例えば、データ伸張装置１６に圧縮ストリーム３３が入力されたことに応じ、ブロック境界判定処理を実行する。

まず、ブロック境界判定部５１５はカウンタＣを初期化する（ステップＳ３０１）。具体的には、ブロック境界判定部５１５は、カウンタＣを０に設定する。カウンタＣは、カウンタＣが初期化された後にブロック境界判定部５１５が可変長復号部５１３から受け取ったシンボルの数を示す変数である。つまり、カウンタＣは、可変長復号部５１３から受け取ったシンボルがリテラルシンボル（すなわち、１バイトのシンボル）であると仮定した場合の非圧縮データサイズを示す。

ブロック境界判定部５１５は、可変長復号部５１３からシンボルを受信する（ステップＳ３０２）。そして、ブロック境界判定部５１５は、カウンタＣを初期化した後にＥＯＢ検出部５１４によってＥＯＢシンボルが検出されたか否かを判定する（ステップＳ３０３）。具体的には、ブロック境界判定部５１５は、例えば、カウンタＣを初期化した後にＥＯＢ検出部５１４からＥＯＢ検出フラグを受け取ったか否かを判定する。

ＥＯＢ検出部５１４によってＥＯＢシンボルが検出された場合（ステップＳ３０３のＹｅｓ）、ブロック境界判定部５１５はステップＳ３０１に戻る。つまり、ブロック境界判定部５１５は、ＥＯＢシンボルの検出によって現在のハフマンブロックの終端が既に検出されているので、次のハフマンブロックの終端を判定するための処理をさらに行う。

ＥＯＢ検出部５１４によってＥＯＢシンボルが検出されていない場合（ステップＳ３０３のＮｏ）、ブロック境界判定部５１５はカウンタＣに１を加算する（ステップＳ３０４）。ブロック境界判定部５１５は、カウンタＣを初期化した後に受信したシンボル（すなわち、現在のハフマンブロックに対応する辞書圧縮シンボル）が全てリテラルシンボルであるか否かを判定する（ステップＳ３０５）。具体的には、ブロック境界判定部５１５は、例えば、全リテラル判定部５１６から受け取った全リテラル判定情報に基づいて、カウンタＣを初期化した後に受信したシンボルが全てリテラルシンボルであるか否かを判定する。

カウンタＣを初期化した後に受信したシンボルの少なくとも１つがリテラルシンボルでない場合（ステップＳ３０５のＮｏ）、ブロック境界判定部５１５はステップＳ３０２に戻る。この場合、ブロック境界判定部５１５は、カウンタＣを用いたハフマンブロックの境界の検出を行うことができない。つまり、ブロック境界判定部５１５は、受信したシンボルが全てリテラルシンボルであると仮定した場合の非圧縮データサイズに基づくハフマンブロックの境界の検出を行うことができない。そのため、ブロック境界判定部５１５は、ステップＳ３０３でＥＯＢ検出部５１４によってＥＯＢシンボルが検出されたことに応じ、次のハフマンブロックの境界を検出するためにステップＳ３０１に戻る。

カウンタＣを初期化した後に受信したシンボルが全てリテラルシンボルである場合（ステップＳ３０５のＹｅｓ）、ブロック境界判定部５１５は、カウンタＣがブロックサイズと等しいか否かを判定する（ステップＳ３０６）。

カウンタＣがブロックサイズと等しい場合（ステップＳ３０６のＹｅｓ）、ブロック境界判定部５１５は、現在のハフマンブロックの境界を検出したと判断して、ブロック境界フラグを出力し（ステップＳ３０７）、ステップＳ３０１に戻る。つまり、ブロック境界判定部５１５は、次のハフマンブロックのブロック境界を検出するための処理をさらに行う。ブロック境界フラグは、ＭＵＸ５１７を介して符号化テーブル復元部５１２に出力される。これにより、符号化テーブル４２の切り替えが符号化テーブル復元部５１２に指示される。

符号化テーブル復元部５１２は、ブロック境界フラグを受け取ったことに応じて、圧縮ストリーム３３内の次のヘッダ部を取得する。符号化テーブル復元部５１２は、取得したヘッダ部を用いて新たな符号化テーブル４２を復元して、前の符号化テーブル４２から切り替える。これにより、可変長復号部５１３は、新たな符号化テーブル４２を用いて、圧縮ストリーム３３内の後続するシンボル（ペイロード部）を復号する。

以上のブロック境界判定処理により、データ伸張装置１６は、ハフマンブロックに対応する可変長復号されたシンボル（辞書圧縮シンボル）が全てリテラルシンボルである場合、可変長復号部５１３から得られたシンボルの数に基づいて、ハフマンブロックの終端を検出できる。この場合、データ伸張装置１６では、第１比較例のデータ伸張装置１６Ｃ－１におけるＥＯＢシンボルを復号する処理サイクルが不要であり、また第２比較例のデータ伸張装置１６Ｃ－２における可変長復号で得られたシンボルの種類に応じた非圧縮データサイズＤＳの計算も不要である。したがって、データ伸張装置１６では復号のスループットを向上できる。また、対応する辞書圧縮シンボルが全てリテラルシンボルであるハフマンブロックにはＥＯＢシンボルが追加されていないので、入力される圧縮ストリーム３３は圧縮効率が高いデータである。

なお、ブロック境界判定部５１５は、圧縮サイズ情報を用いて、第２のタイミング以降に連続して可変長復号部５１３から受け取った１つ以上のシンボルの終端が、ハフマンブロックの終端に対応するか否かを判定してもよい。圧縮サイズ情報は、対応するハフマンブロックに対する辞書式圧縮およびエントロピー符号化により得られるデータブロック（より詳しくは、可変長符号列）のサイズを示す情報である。圧縮サイズ情報は、例えば、ヘッダ部３３１から取得される。なお、特定のサイズを示す圧縮サイズ情報が、データ伸張装置１６に予め格納されていてもよい。

具体的には、ブロック境界判定部５１５は、可変長復号部５１３から受け取った１つ以上のシンボルに対応する１つ以上の可変長符号のデータサイズ（以下、圧縮データサイズと称する）を算出する。ブロック境界判定部５１５は、例えば、符号化テーブル４２を用いて、可変長復号部５１３からシンボルを受け取る毎に、そのシンボルが可変長復号される前のデータサイズ（例えば、対応する可変長符号の符号長）を取得し、取得したデータサイズの累積値を圧縮データサイズとして算出する。そして、ブロック境界判定部５１５は、例えば受け取った１つ以上のシンボルが全てリテラルシンボルである場合、算出した圧縮データサイズと、圧縮サイズ情報とに基づいて、圧縮データサイズの算出に用いた１つ以上のシンボルの終端がハフマンブロックの終端に対応することを示す情報（ブロック境界フラグ）を、ＭＵＸ５１７に送出する。より詳しくは、ブロック境界判定部５１５は、全リテラル判定部５１６から受け取った全リテラル判定情報がｔｒｕｅを示し、且つ算出した圧縮データサイズが圧縮サイズ情報に示されるサイズと等しい場合、ブロック境界フラグをＭＵＸ５１７に送出する。圧縮サイズ情報を用いてハフマンブロック間の境界を判定する場合にも、図１２を参照して前述したブロック境界判定処理と同様の効果を得ることができる。

以上の構成により、データ伸張装置１６は、エントロピー復号および辞書式伸張により、圧縮ストリーム３３を非圧縮データ３１に伸張できる。データ伸張装置１６は、圧縮ストリーム３３に対するエントロピー復号によって得られた１つ以上のシンボルが全てリテラルシンボルである場合、それらシンボルの数をカウントすることでハフマンブロック間の境界を判断でき、復号のスループットを向上できる。また、データ伸張装置１６は、圧縮ストリーム３３に対するエントロピー復号によって得られた１つ以上のシンボルの少なくとも１つがリテラルシンボルでない場合、ＥＯＢシンボルを検出することでハフマンブロック間の境界を判断でき、復号のスループットの低下を回避できる。

なお、前述したように、データ圧縮装置１５は、非圧縮データ３１が圧縮された圧縮ストリーム３３を生成する。例えば、非圧縮データ３１がホスト２によってＮＡＮＤ型フラッシュメモリ４に書き込むことを要求されたデータである場合、ＣＰＵ１１は、ＮＡＮＤ Ｉ／Ｆ１２を介して圧縮ストリーム３３をＮＡＮＤ型フラッシュメモリ４に書き込む。

また、コントローラ６は、さらに、ＥＣＣエンコーダとＥＣＣデコーダを備えてもよい。この場合、ＥＣＣエンコーダが、データ圧縮装置１５から出力される圧縮データ（圧縮ストリーム）３３に対して誤り訂正用のパリティ（ＥＣＣパリティ）を生成し、生成したＥＣＣパリティと圧縮データ３３とを有する符号語を生成する。そして、ＣＰＵ１１が、符号語をＮＡＮＤ Ｉ／Ｆ１２経由でＮＡＮＤ型フラッシュメモリ４へ書き込むように構成される。つまり、ＣＰＵ１１は、データ圧縮装置１５から出力される圧縮データ３３に基づくデータを、ＮＡＮＤ Ｉ／Ｆ１２を介してＮＡＮＤ型フラッシュメモリ４に書き込むように構成される。また、ＣＰＵ１１は、例えばホスト２からホストＩ／Ｆ１４を介してリードコマンドを受信する場合、当該リードコマンドに基づくデータをＮＡＮＤ Ｉ／Ｆ１２を介してＮＡＮＤ型フラッシュメモリ４から読み出す。ＥＣＣデコーダは、読み出されたデータに対する誤り訂正処理を実行する。誤り訂正処理が実行された読み出しデータは圧縮データ３３としてＣＰＵ１１によりデータ伸張装置１６へ入力され、データ伸張装置１６は、入力された圧縮データ３３を伸張する。ＣＰＵ１１は、ホスト２からのリードコマンドに対して、伸張された非圧縮データ３１をホスト２へ送信する。つまり、ホスト２からのリードコマンドに対して、ＣＰＵ１１は、ＮＡＮＤ型フラッシュメモリ４から読み出したデータに基づく圧縮データ３３を伸張し、伸張した非圧縮データ３１をホスト２へ送信するように構成される。

なお、データ圧縮装置１５およびデータ伸張装置１６の一部または全ては、回路のようなハードウェアとして実現されてもよいし、少なくとも１つのプロセッサによって実行されるプログラム（すなわちソフトウェア）として実現されてもよい。

以上説明したように、本実施形態に係るデータ圧縮装置１５およびデータ伸張装置１６によれば、スループットを向上できる。

データ圧縮装置１５において、全リテラル判定部２２４は、第１データブロック（ハフマンブロック）に対する辞書式圧縮により得られた第２データブロックに含まれる１つ以上のシンボルが、全てリテラルシンボルであるか否かを判定する。ＥＯＢ追加部２２１は、１つ以上のシンボルが全てリテラルシンボルである場合、第２データブロックの終端にブロック終端シンボルを追加しない。ＥＯＢ追加部２２１は、１つ以上のシンボルの内の少なくとも１つのシンボルがリテラルシンボルでない場合、第２データブロックの終端にブロック終端シンボルを追加する。

このように、ＥＯＢ追加部２２１は、ハフマンブロックに対する辞書式圧縮で得られた１つ以上のシンボルが全てリテラルシンボルである場合、１つ以上のシンボルの終端にＥＯＢシンボルを追加しない。これにより、データ圧縮装置１５では、エントロピー符号化の対象となるシンボル数が減少するので、符号化のスループットと、圧縮効率とを向上できる。

また、データ伸張装置１６において、全リテラル判定部５１６は、圧縮データ３３をエントロピー復号することによって得られた１つ以上のシンボルが、全てリテラルシンボルであるか否かを判定する。ブロック境界判定部５１５は、１つ以上のシンボルが辞書式伸張された場合の第１データサイズを算出し、１つ以上のシンボルが全てリテラルシンボルである場合、第１データサイズと、非圧縮のデータブロック（ハフマンブロック）のサイズを示すブロックサイズ情報４１とに基づいて、１つ以上のシンボルの終端がデータブロックの終端に対応することを示す情報を出力する。ＥＯＢ検出部５１４は、１つ以上のシンボルの内の少なくとも１つのシンボルがリテラルシンボルでない場合、１つ以上のシンボルの末尾のシンボルに基づいて、１つ以上のシンボルの終端がデータブロックの終端に対応することを示す情報を出力する。

このように、ブロック境界判定部５１５は、１つ以上のシンボルが全てリテラルシンボルである場合、ＥＯＢシンボルの検出を行うことなく、ハフマンブロックの終端を検出できる。また、ＥＯＢ検出部５１４は、１つ以上のシンボルの内の少なくとも１つのシンボルがリテラルシンボルでない場合には、ＥＯＢシンボルを検出して、ハフマンブロックの終端を判別できる。これにより、データ伸張装置１６では復号のスループットを向上できる。

本実施形態に記載された様々な機能の各々は、回路（処理回路）によって実現されてもよい。処理回路の例には、中央処理装置（ＣＰＵ）のような、プログラムされたプロセッサが含まれる。このプロセッサは、メモリに格納されたコンピュータプログラム（命令群）を実行することによって、記載された機能それぞれを実行する。このプロセッサは、電気回路を含むマイクロプロセッサであってもよい。処理回路の例には、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、マイクロコントローラ、コントローラ、他の電気回路部品も含まれる。本実施形態に記載されたＣＰＵ以外の他のコンポーネントの各々もまた処理回路によって実現されてもよい。

本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。

１…情報処理システム、２…ホスト、３…メモリシステム、４…ＮＡＮＤ型フラッシュメモリ、５…ＤＲＡＭ、６…コントローラ、１１…ＣＰＵ、１２…ＮＡＮＤ Ｉ／Ｆ、１３…ＤＲＡＭ Ｉ／Ｆ、１４…ホストＩ／Ｆ、１５…データ圧縮装置、１６…データ伸張装置、２１…辞書式圧縮部、２２…エントロピー符号化部、２２１…ＥＯＢ追加部、２２２…符号化テーブル生成部、２２３…可変長符号化部、２２４…全リテラル判定部、３１…非圧縮データ、３３…圧縮ストリーム、３３１…ヘッダ部、３３２…ペイロード部、３３３…ブロック終端シンボル（ＥＯＢシンボル）、５１…エントロピー復号部、５２…辞書式伸張部、５１１…ヘッダ／ペイロード分離部、５１２…符号化テーブル復元部、５１３…可変長復号部、５１４…ＥＯＢ検出部、５１５…ブロック境界判定部、５１６…全リテラル判定部、５１７…ＭＵＸ。

Claims (23)

1. 第１データブロックに対する辞書式圧縮により得られた第２データブロックに含まれる１つ以上のシンボルが、全てリテラルシンボルであるか否かを判定する全リテラル判定部と、
   前記１つ以上のシンボルが全てリテラルシンボルである場合、前記第２データブロックの終端にブロック終端シンボルを追加せず、
   前記１つ以上のシンボルの内の少なくとも１つのシンボルがリテラルシンボルでない場合、前記第２データブロックの終端に前記ブロック終端シンボルを追加する終端シンボル追加部と、
   を具備するデータ圧縮装置。
2. 前記第１データブロックを辞書式圧縮して前記第２データブロックを生成する辞書式圧縮回路をさらに備え、
   前記終端シンボル追加部は、
   前記１つ以上のシンボルを、前記辞書式圧縮回路から１シンボルずつ取り込み、前記取り込んだシンボルが辞書式圧縮される前のデータサイズを取得し、前記取得したデータサイズの累積値を算出し、
   前記算出した累積値が、前記第１データブロックのサイズ情報が示すサイズに達する場合に、前記取り込んだシンボルが前記第１データブロックの終端に対応すると判定し、前記１つ以上のシンボルの内の少なくとも１つのシンボルがリテラルシンボルでない場合、前記第２データブロックの終端に前記ブロック終端シンボルを追加する、
   請求項１に記載のデータ圧縮装置。
3. 前記全リテラル判定部は、
   前記取り込んだシンボルがリテラルシンボルであるか否かを判定し、リテラルシンボルでない場合はフラグをＦａｌｓｅに設定する、
   請求項２に記載のデータ圧縮装置。
4. 前記終端シンボル追加部は、
   前記取り込んだシンボルが前記第１データブロックの終端に対応すると判定する場合に、前記フラグがＦａｌｓｅであるならば、前記１つ以上のシンボルの内の少なくとも１つのシンボルがリテラルシンボルでないと判定する、
   請求項３に記載のデータ圧縮装置。
5. 前記第２データブロックをエントロピー符号化することによって圧縮データを生成する符号化部をさらに具備する、
   請求項１に記載のデータ圧縮装置。
6. 前記圧縮データは、前記１つ以上のシンボルが全てリテラルシンボルであるか否かを示す情報を含む、
   請求項５に記載のデータ圧縮装置。
7. 前記圧縮データは、前記第２データブロックのサイズを示す情報を含む、
   請求項５に記載のデータ圧縮装置。
8. 前記第２データブロックのシンボル毎の出現頻度に基づいて、符号化テーブルを生成する符号化テーブル生成部をさらに具備し、
   前記符号化部は、前記符号化テーブルを用いて前記第２データブロックをエントロピー符号化する、
   請求項５に記載のデータ圧縮装置。
9. 前記終端シンボル追加部は、
   前記１つ以上のシンボルが辞書式圧縮される前のデータサイズを算出し、
   前記データサイズと、前記第１データブロックのサイズを示す情報とに基づいて、前記１つ以上のシンボルの終端が前記第１データブロックの終端に対応するか否かを判定し、
   前記１つ以上のシンボルの終端が前記第１データブロックの終端に対応し、且つ前記１つ以上のシンボルの内の少なくとも１つのシンボルがリテラルシンボルでない場合、前記第２データブロックの終端に前記ブロック終端シンボルを追加する、
   請求項１に記載のデータ圧縮装置。
10. 前記全リテラル判定部は、前記１つ以上のシンボルが全てリテラルシンボルであるか否かを示す情報を、前記終端シンボル追加部に出力する、
    請求項９に記載のデータ圧縮装置。
11. 前記終端シンボル追加部は、前記１つ以上のシンボルの終端が前記第１データブロックの終端に対応することを示す情報を、前記全リテラル判定部に出力する、
    請求項１に記載のデータ圧縮装置。
12. 不揮発性メモリと、
    請求項５に記載のデータ圧縮装置を含み、前記圧縮データを前記不揮発性メモリに書き込むように構成されるコントローラと、
    を具備するメモリシステム。
13. 圧縮データをエントロピー復号することによって得られた１つ以上のシンボルが全てリテラルシンボルであるか否かを判定する全リテラル判定部と、
    前記１つ以上のシンボルが辞書式伸張された場合の第１データサイズを算出し、前記１つ以上のシンボルが全てリテラルシンボルである場合、前記第１データサイズと、非圧縮のデータブロックのサイズを示す情報とに基づいて、前記１つ以上のシンボルの終端が前記データブロックの終端に対応することを示す第１情報を出力するブロック境界判定部と、
    前記１つ以上のシンボルの内の少なくとも１つのシンボルがリテラルシンボルでない場合、前記１つ以上のシンボルの末尾のシンボルに基づいて、前記１つ以上のシンボルの終端が前記データブロックの終端に対応することを示す第２情報を出力する終端シンボル検出部と、
    を具備するデータ伸張装置。
14. 前記圧縮データは、前記１つ以上のシンボルが全てリテラルシンボルであるか否かを示す第３情報を含み、
    前記全リテラル判定部は、前記第３情報に基づいて、前記１つ以上のシンボルが全てリテラルシンボルであるか否かを判定する、
    請求項１３に記載のデータ伸張装置。
15. 前記ブロック境界判定部は、前記１つ以上のシンボルの数に基づいて前記第１データサイズを算出する、
    請求項１３または請求項１４に記載のデータ伸張装置。
16. 前記ブロック境界判定部は、前記第１データサイズと、前記非圧縮のデータブロックのサイズとが等しい場合、前記第１情報を出力する、
    請求項１５に記載のデータ伸張装置。
17. 前記終端シンボル検出部は、
    前記末尾のシンボルがブロック終端シンボルであるか否かを判定し、
    前記末尾のシンボルが前記ブロック終端シンボルである場合、前記第２情報を出力する、
    請求項１３または請求項１４に記載のデータ伸張装置。
18. 前記終端シンボル検出部は、前記末尾のシンボルが前記ブロック終端シンボルである場合、前記第２情報を前記ブロック境界判定部に出力する、
    請求項１７に記載のデータ伸張装置。
19. 前記圧縮データから得られる第１符号化テーブルを用いて前記圧縮データをエントロピー復号することによって、前記１つ以上のシンボルを生成し、
    前記第１情報が出力された場合、または前記第２情報が出力された場合、前記圧縮データから得られる前記第１符号化テーブルとは異なる第２符号化テーブルを用いて前記圧縮データをエントロピー復号することによって、前記１つ以上のシンボルに後続する１つ以上のシンボルを生成する復号部をさらに具備する、
    請求項１３に記載のデータ伸張装置。
20. 前記圧縮データに含まれる１つ以上の可変長符号をエントロピー復号することによって、前記１つ以上のシンボルを生成する復号部をさらに具備し、
    前記ブロック境界判定部は、
    前記１つ以上の可変長符号の第２データサイズを算出し、
    前記１つ以上のシンボルが全てリテラルシンボルである場合、前記第２データサイズと、第１データブロックに対する辞書式圧縮およびエントロピー符号化により得られる第２データブロックのサイズを示す第３情報とに基づいて、前記第１情報を出力する、
    請求項１３に記載のデータ伸張装置。
21. 前記ブロック境界判定部は、前記第２データサイズと、前記第２データブロックのサイズとが等しい場合、前記第１情報を出力する、
    請求項２０に記載のデータ伸張装置。
22. 前記圧縮データは、前記第３情報を含む、
    請求項２０に記載のデータ伸張装置。
23. 不揮発性メモリと、
    請求項１３に記載のデータ伸張装置を含み、前記圧縮データを前記不揮発性メモリから読み出すように構成されるコントローラと、
    を具備するメモリシステム。