(57)【要約】【課題】データを高圧縮率かつ高スループットでロスレス圧縮する。【解決手段】実施形態によれば、圧縮装置は、第１の圧縮部と、第２の圧縮部と、選択部とを含む。第１の圧縮部は、入力データ列を所定サイズで分割した部分データ列のうち少なくとも１つが辞書登録データのいずれかに一致するならば当該辞書登録データの少なくとも１つに関連付けられる辞書アドレスを含む第１の圧縮データを生成する。第２の圧縮部は、第１の圧縮データと過去の第１の圧縮データとの比較、ならびに、過去の入力データ列のうち少なくとも一方に基づいて、入力データ列を圧縮することによって辞書アドレスを含まない第２の圧縮データを生成する。選択部は、第１の圧縮データおよび第２の圧縮データのうちデータサイズの小さい一方を選択することによって、入力データ列の圧縮データを得る。【選択図】図１
2016052046.tif 000002
【特許請求の範囲】
【請求項１】
辞書アドレスを所定サイズの辞書登録データと関連付ける辞書テーブルを保存する辞書メモリと、
入力データ列を前記所定サイズで分割した部分データ列の各々と前記辞書登録データとの比較結果に基づいて当該入力データ列を圧縮することによって、前記部分データ列のうち少なくとも１つが前記辞書登録データのいずれかに一致するならば当該辞書登録データの少なくとも１つに関連付けられる辞書アドレスを含む第１の圧縮データを生成する第１の圧縮部と、
前記第１の圧縮データと過去の第１の圧縮データとの比較、ならびに、過去の入力データ列のうち少なくとも一方に基づいて、前記入力データ列を圧縮することによって前記辞書アドレスを含まない第２の圧縮データを生成する第２の圧縮部と、
前記第１の圧縮データおよび前記第２の圧縮データのうちデータサイズの小さい一方を選択することによって、前記入力データ列の圧縮データを得る選択部と
を具備する圧縮装置。
【請求項２】
オリジナルデータ列を固定サイズで分割することによって前記入力データ列を得る分割部をさらに具備する、請求項１記載の圧縮装置。
【請求項３】
前記第２の圧縮部は、
前回の入力データ列を保存する記憶部と、
前記前回の入力データ列を特定サイズで分割した部分データ列に基づいて当該特定サイズの各データパターンの出現頻度をカウントすることによって最頻値を算出する算出部と、
前記入力データ列を前記特定サイズで分割した部分データ列の各々を前記最頻値と比較する比較部と、
前記入力データ列と前記最頻値との比較結果に基づいて当該入力データ列を符号化することによって、前記入力データ列を前記特定サイズで分割した各部分データ列と前記最頻値との一致／不一致を示す最頻値一致情報と、当該部分データ列のうち最頻値と一致しなかった最頻値不一致データの符号語とを含む前記第２の圧縮データを生成する符号化部と
を備える、
請求項１記載の圧縮装置。
【請求項４】
前記第２の圧縮部は、
前回の第１の圧縮データに含まれる一部または全部の情報要素を記憶する記憶部と、
前記第１の圧縮データを前記記憶部に記憶された情報要素と比較する比較部と、
前記第１の圧縮データと前記記憶部に記憶された情報要素との比較結果に基づいて、当該第１の圧縮データに含まれる情報要素のうち当該記憶部に記憶された情報要素と一致する情報要素をスキップフラグによって置き換えることで、前記第２の圧縮データを生成する符号化部と
を備える、
請求項１記載の圧縮装置。
【請求項５】
前記第１の圧縮データは、前記入力データ列に適用される分割パターン、ならびに、当該分割パターンに対応する各部分データ列と辞書登録データとの一致／不一致を示す辞書一致情報と、当該部分データ列の各々の符号語とを含み、
前記部分データ列の符号語は、当該部分データ列が前記辞書登録データのいずれかに一致する辞書一致データに相当するならば当該辞書登録データに関連付けられる辞書アドレスであり、当該部分データ列が前記辞書登録データのいずれにも一致しない辞書不一致データに相当するならば当該辞書不一致データである、
請求項４記載の圧縮装置。
【請求項６】
前記符号化部は、前記第１の圧縮データおよび前記前回の第１の圧縮データが前記辞書一致情報および前記辞書アドレスにおいて一致するならば、当該第１の圧縮データに含まれる前記辞書一致情報および前記辞書アドレスを前記スキップフラグによって置き換えることで、前記第２の圧縮データを生成する、請求項５記載の圧縮装置。
【請求項７】
前記符号化部は、前記第１の圧縮データおよび前記前回の第１の圧縮データが前記辞書一致情報、前記辞書アドレスおよび前記辞書不一致データにおいて一致するならば、当該第１の圧縮データに含まれる前記辞書一致情報、前記辞書アドレスおよび前記辞書不一致データを前記スキップフラグによって置き換えることで、前記第２の圧縮データを生成する、請求項５記載の圧縮装置。
【請求項８】
前記第１の圧縮データおよび前記第２の圧縮データは、コーデックが第１の方式および第２の方式のいずれであるかを示す情報要素をそれぞれ含む、請求項１記載の圧縮装置。
【請求項９】
前記第１の圧縮データおよび前記第２の圧縮データは、コーデックが第１の方式および第２の方式のいずれであるかを示し、当該コーデックが当該第１の方式である場合には前記入力データ列に適用される分割パターン、ならびに、当該分割パターンに対応する各部分データ列と辞書登録データとの一致／不一致をさらに示す情報要素をそれぞれ含む、請求項１記載の圧縮装置。
【請求項１０】
辞書アドレスを所定サイズの辞書登録データと関連付ける辞書テーブルを保存する辞書メモリと、
圧縮データに対応する圧縮前データを所定の分割パターンに従って分割した各部分データ列の符号語を当該圧縮データから抽出し、当該部分データ列が前記辞書アドレスのいずれかに相当するならば当該辞書アドレスに関連付けられる辞書登録データを当該部分データ列として取り扱うことによって、第１の伸長データを生成する第１の伸長部と、
過去の圧縮データおよび過去の伸長データのうち少なくとも一方に基づいて、前記圧縮データを伸長することによって第２の伸長データを生成する第２の伸長部と、
前記圧縮データのコーデックが第１の方式であるならば前記第１の伸長データを選択し、前記圧縮データのコーデックが第２の方式であるならば前記第２の伸長データを選択することによって、前記圧縮データの伸長データを得る選択部と
を具備する伸長装置。
【請求項１１】
ストレージと、圧縮装置と、伸長装置とを具備し、
前記圧縮装置は、
辞書アドレスを所定サイズの辞書登録データと関連付ける辞書テーブルを保存する辞書メモリと、
入力データ列を前記所定サイズで分割した部分データ列の各々と前記辞書登録データとの比較結果に基づいて当該入力データ列を圧縮することによって、前記部分データ列のうち少なくとも１つが前記辞書登録データのいずれかに一致するならば当該辞書登録データの少なくとも１つに関連付けられる辞書アドレスを含む第１の圧縮データを生成する第１の圧縮部と、
前記第１の圧縮データと過去の第１の圧縮データとの比較、ならびに、過去の入力データ列のうち少なくとも一方に基づいて、前記入力データ列を圧縮することによって前記辞書アドレスを含まない第２の圧縮データを生成する第２の圧縮部と、
前記第１の圧縮データおよび前記第２の圧縮データのうちデータサイズの小さい一方を選択することによって、前記入力データ列の圧縮データを得る選択部と
を備え、
前記入力データ列の圧縮データは、前記ストレージにおいて読み書きされ、
前記伸長装置は、
辞書アドレスを所定サイズの辞書登録データと関連付ける辞書テーブルを保存する辞書メモリと、
前記ストレージから読み出された圧縮データに対応する圧縮前データを所定の分割パターンに従って分割した各部分データ列の符号語を当該圧縮データから抽出し、当該部分データ列が前記辞書アドレスのいずれかに相当するならば当該辞書アドレスに関連付けられる辞書登録データを当該部分データ列として取り扱うことによって、第１の伸長データを生成する第１の伸長部と、
過去に前記ストレージから読み出された圧縮データおよび過去の伸長データのうち少なくとも一方に基づいて、前記ストレージから読み出された圧縮データを伸長することによって第２の伸長データを生成する第２の伸長部と、
前記ストレージから読み出された圧縮データのコーデックが第１の方式であるならば前記第１の伸長データを選択し、前記ストレージから読み出された圧縮データのコーデックが第２の方式であるならば前記第２の伸長データを選択することによって、前記ストレージから読み出された圧縮データの伸長データを得る選択部と
を備える、
ストレージ装置。
【請求項１２】
前記ストレージは、ＮＡＮＤフラッシュメモリであり、
前記圧縮装置および前記伸長装置は、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）コントローラに組み込まれる、
請求項１１記載のストレージ装置。
【請求項１３】
前記ストレージは、磁気ディスクであり、
前記圧縮装置および前記伸長装置は、ハードディスクコントローラに組み込まれる、
請求項１１記載のストレージ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
実施形態は、データの圧縮および伸長に関する。
【背景技術】
【０００２】
近年、タブレット端末、ｕｌｔｒａｂｏｏｋなどのモバイル端末の普及が進んでいる。このようなモバイル端末のストレージとして、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）に比べて消費電力、耐衝撃性などの点で優れたＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）を採用することがある。さらに、ＳＳＤの大容量化、ＳＡＴＡ（Ｓｅｒｉａｌ  ＡＴＡ）からＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ）  Ｅｘｐｒｅｓｓへのホストインターフェースのシフトなども進みつつある。この結果、ＳＳＤの取り扱うデータ量およびアクセス速度は増加しつつある。
【０００３】
ＳＳＤの応答性および信頼性を向上させるために、データの読み書きに付随して可逆（ロスレス）圧縮を利用することができる。具体的には、ＳＳＤコントローラは、オリジナルのデータを圧縮し、ＳＳＤ内のＮＡＮＤフラッシュメモリに圧縮データを書き込む。そして、ＳＳＤコントローラは、ＮＡＮＤフラッシュメモリから圧縮データを読み出し、圧縮データを伸長することによってオリジナルのデータを復元する。係るロスレス圧縮を利用することにより、特にホストがサスペンド／レジュームする際のＳＳＤの応答性は向上する。さらに、ＮＡＮＤフラッシュメモリのオーバープロビジョニングが等価的に大きくなるのでＳＳＤの寿命および信頼性も向上する。故に、ＳＳＤコントローラは、好ましくは、ストレージ（ＮＡＮＤフラッシュメモリ）に保存されるデータ全般を高圧縮率かつ高スループットでロスレス圧縮する。ストレージに保存されるデータ全般とは、例えば、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）若しくはプログラムなどのシステムファイル、ハイバネーションファイル若しくはページファイルなどのメモリイメージ、または、ユーザデータなどである。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｂ．  Ｓｕｋｈｗａｎｉ，  Ｂ．  Ａｂａｌｉ，  Ｂ．  Ｂｒｅｚｚｏ，  ａｎｄ  Ｓ．  Ａｓａａｄ，  “Ｈｉｇｈ−Ｔｈｒｏｕｇｈｐｕｔ，  Ｌｏｓｓｌｅｓｓ  Ｄａｔａ  Ｃｏｍｐｒｅｓｓｉｏｎ  ｏｎ  ＦＰＧＡｓ，”  ｉｎ  Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｃｕｓｔｏｍ  Ｃｏｍｐｕｔｉｎｇ  Ｍａｃｈｉｎｅｓ  （ＦＣＣＭ），  ２０１１  ＩＥＥＥ  １９ｔｈ  Ａｎｎｕａｌ  Ｉｎｔ．  Ｓｙｍｐ．  ｏｎ．  ＩＥＥＥ，  ２０１１，  ｐｐ．  １１３−１１６．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
実施形態は、データを高圧縮率かつ高スループットでロスレス圧縮することを目的とする。
【課題を解決するための手段】
【０００６】
実施形態によれば、圧縮装置は、辞書メモリと、第１の圧縮部と、第２の圧縮部と、選択部とを含む。辞書メモリは、辞書アドレスを所定サイズの辞書登録データと関連付ける辞書テーブルを保存する。第１の圧縮部は、入力データ列を所定サイズで分割した部分データ列の各々と辞書登録データとの比較結果に基づいて当該入力データ列を圧縮することによって、部分データ列のうち少なくとも１つが辞書登録データのいずれかに一致するならば当該辞書登録データの少なくとも１つに関連付けられる辞書アドレスを含む第１の圧縮データを生成する。第２の圧縮部は、第１の圧縮データと過去の第１の圧縮データとの比較、ならびに、過去の入力データ列のうち少なくとも一方に基づいて、入力データ列を圧縮することによって辞書アドレスを含まない第２の圧縮データを生成する。選択部は、第１の圧縮データおよび第２の圧縮データのうちデータサイズの小さい一方を選択することによって、入力データ列の圧縮データを得る。
【０００７】
実施形態によれば、伸長装置は、辞書メモリと、第１の伸長部と、第２の伸長部と選択部とを含む。辞書メモリは、辞書アドレスを所定サイズの辞書登録データと関連付ける辞書テーブルを保存する。第１の伸長部は、圧縮データに対応する圧縮前データを所定の分割パターンに従って分割した各部分データ列の符号語を当該圧縮データから抽出し、当該部分データ列が辞書アドレスのいずれかに相当するならば当該辞書アドレスに関連付けられる辞書登録データを当該部分データ列として取り扱うことによって、第１の伸長データを生成する。第２の伸長部は、過去の圧縮データおよび過去の伸長データのうち少なくとも一方に基づいて、圧縮データを伸長することによって第２の伸長データを生成する。選択部は、圧縮データのコーデックが第１の方式であるならば第１の伸長データを選択し、圧縮データのコーデックが第２の方式であるならば第２の伸長データを選択することによって、圧縮データの伸長データを得る。
【０００８】
実施形態によれば、ストレージ装置は、ストレージと、圧縮装置と、伸長装置とを含む。圧縮装置は、辞書メモリと、第１の圧縮部と、第２の圧縮部と、選択部とを含む。辞書メモリは、辞書アドレスを所定サイズの辞書登録データと関連付ける辞書テーブルを保存する。第１の圧縮部は、入力データ列を所定サイズで分割した部分データ列の各々と辞書登録データとの比較結果に基づいて当該入力データ列を圧縮することによって、部分データ列のうち少なくとも１つが辞書登録データのいずれかに一致するならば当該辞書登録データの少なくとも１つに関連付けられる辞書アドレスを含む第１の圧縮データを生成する。第２の圧縮部は、第１の圧縮データと過去の第１の圧縮データとの比較、ならびに、過去の入力データ列のうち少なくとも一方に基づいて、入力データ列を圧縮することによって辞書アドレスを含まない第２の圧縮データを生成する。選択部は、第１の圧縮データおよび第２の圧縮データのうちデータサイズの小さい一方を選択することによって、入力データ列の圧縮データを得る。入力データ列の圧縮データは、ストレージにおいて読み書きされる。伸長装置は、辞書メモリと、第１の伸長部と、第２の伸長部と、選択部とを含む。辞書メモリは、辞書アドレスを所定サイズの辞書登録データと関連付ける辞書テーブルを保存する。第１の伸長部は、ストレージから読み出された圧縮データに対応する圧縮前データを所定の分割パターンに従って分割した各部分データ列の符号語を当該圧縮データから抽出し、当該部分データ列が辞書アドレスのいずれかに相当するならば当該辞書アドレスに関連付けられる辞書登録データを当該部分データ列として取り扱うことによって、第１の伸長データを生成する。第２の伸長部は、過去にストレージから読み出された圧縮データおよび過去の伸長データのうち少なくとも一方に基づいて、ストレージから読み出された圧縮データを伸長することによって第２の伸長データを生成する。選択部は、ストレージから読み出された圧縮データのコーデックが第１の方式であるならば第１の伸長データを選択し、ストレージから読み出された圧縮データのコーデックが第２の方式であるならば第２の伸長データを選択することによって、ストレージから読み出された圧縮データの伸長データを得る。
【図面の簡単な説明】
【０００９】
【図１】第１の実施形態に係る圧縮装置を例示するブロック図。
【図２】第１の圧縮部によって行われるデータ圧縮処理の説明図。
【図３】入力データ列の分割パターンを例示する図。
【図４】第１の圧縮部によって行われるデータ圧縮処理の説明図。
【図５】図１の圧縮装置によって行われるデータ圧縮処理を例示するフローチャート。
【図６】第１の実施形態に係る伸長装置を例示するブロック図。
【図７】図６の伸長装置によって行われるデータ伸長処理を例示するフローチャート。
【図８】第１の実施形態に係るストレージ装置を例示するブロック図。
【図９】図１の変形例を例示するブロック図。
【図１０】第１の圧縮データの構造の説明図。
【図１１】第３の実施形態に係る圧縮装置に含まれる第２の圧縮部を例示するブロック図。
【図１２】図１１の第２の圧縮部によって生成される第２の圧縮データを例示する図。
【図１３】図１１の第２の圧縮部によって生成される第２の圧縮データを例示する図。
【図１４】第４の実施形態に係る圧縮装置に含まれる第２の圧縮部を例示するブロック図。
【図１５】第４の実施形態に係る圧縮装置が行うデータ圧縮処理の説明図。
【図１６】第４の実施形態に係る圧縮装置が行うデータ圧縮処理の説明図。
【図１７】第４の実施形態に係る圧縮装置によって生成される第１の圧縮データおよび第２の圧縮データの構造の説明図。
【図１８】図８のストレージ装置のハードウェア構成を例示するブロック図。
【発明を実施するための形態】
【００１０】
以下、図面を参照しながら実施形態の説明が述べられる。尚、以降、説明済みの要素と同一または類似の要素には同一または類似の符号が付され、重複する説明は基本的に省略される。
【００１１】
（第１の実施形態）  
図１に例示されるように、第１の実施形態に係る圧縮装置は、辞書メモリ１１０と、第１の圧縮部１２０と、第２の圧縮部１３０と、選択部１４０とを含む。この圧縮装置は、固定サイズ（例えば、８Ｂｙｔｅｓ）の入力データ列１０をロスレス圧縮することによって圧縮データ１１を生成する。なお、以降の説明において、固定サイズの入力データ列１０をブロックと呼ぶこともある。
【００１２】
辞書メモリ１１０には、ハッシュ関数、ハッシュテーブルおよび辞書テーブルが保存される。ハッシュテーブルは、入力データ列１０を所定のサイズで分割した部分データ列に対してハッシュ関数を適用することによって得られるハッシュ値を、辞書アドレスと呼ばれるパラメータと関連付ける。
【００１３】
辞書テーブルは、上記辞書アドレスを辞書登録データと関連付ける。辞書登録データとは、圧縮済みのデータに相当する過去の入力データ列を上記所定のサイズで分割した部分データ列である。
【００１４】
なお、複数のサイズに対して個別のハッシュ関数、ハッシュテーブルおよび辞書テーブルが用意されてもよい。図３および図４に例示されるように、入力データ列１０のサイズが８Ｂｙｔｅｓであるならば、当該入力データ列１０を２Ｂｙｔｅｓ単位、４Ｂｙｔｅｓ単位および８Ｂｙｔｅｓ単位でそれぞれ分割した部分データ列を登録するために、２Ｂｙｔｅｓ向け、４Ｂｙｔｅｓ向けおよび８Ｂｙｔｅｓ向けのハッシュ関数、ハッシュテーブルおよび辞書テーブルがそれぞれ用意されてもよい。
【００１５】
辞書メモリ１１０に保存されるハッシュテーブルおよび辞書テーブルは、後述されるように、将来の入力データ列を効率的に圧縮するために、入力データ列１０を用いて更新される。
【００１６】
第１の圧縮部１２０は、入力データ列１０を図示されない外部装置（例えばホスト）から受け取る。第１の圧縮部１２０は、辞書メモリ１１０に保存されるハッシュ関数、ハッシュテーブルおよび辞書テーブルを用いて、入力データ列１０を圧縮することによって第１の圧縮データを得る。第１の圧縮データは、入力データ列１０に適用される分割パターン、ならびに、当該分割パターンに対応する各部分データ列と辞書登録データとの一致／不一致を示す辞書一致情報と、当該部分データ列の各々の符号語とを含む。第１の圧縮部１２０は、第１の圧縮データを選択部１４０へと出力する。
【００１７】
具体的には、第１の圧縮部１２０は図２に例示されるようにデータ圧縮処理を行う。第１の圧縮部１２０は、入力データ列１０を１種類以上のサイズ単位でそれぞれ分割し、各部分データ列に一致する辞書登録データを辞書メモリ１１０に保存された辞書テーブルから検索する。
【００１８】
例えば図３に示されるように、第１の圧縮部１２０は入力データ列１０を２Ｂｙｔｅｓ単位、４Ｂｙｔｅｓ単位および８Ｂｙｔｅｓ単位でそれぞれ分割する。それから、例えば図４に示されるように、第１の圧縮部１２０は、８Ｂｙｔｅｓの部分データ列に対して８Ｂｙｔｅｓ向けのハッシュ関数を適用することによってハッシュ値を得る。第１の圧縮部１２０は、このハッシュ値に関連付けられる辞書アドレスを８Ｂｙｔｅｓ向けのハッシュテーブルから読み出す。第１の圧縮部１２０は、さらに、この辞書アドレスに関連付けられる辞書登録データを８Ｂｙｔｅｓ向けの辞書テーブルから読み出し、上記８Ｂｙｔｅｓの部分データ列と比較する。第１の圧縮部１２０は、４Ｂｙｔｅｓの部分データ列および２Ｂｙｔｅｓの部分データ列についても同様に辞書検索処理を行う。なお、異なるサイズ向けの辞書検索処理の間には依存関係がないので、第１の圧縮部１２０は複数のサイズ向けの辞書検索処理を並列的なパイプライン処理として実現することで高スループットを達成できる。
【００１９】
第１の圧縮部１２０は、各部分データ列が辞書登録データのいずれかに一致するならば当該辞書登録データに関連付けられる辞書アドレスを当該部分データ列の符号語として出力する。なお、第１のサイズ（例えば、２Ｂｙｔｅｓ）の第１の部分データ列と当該第１の部分データ列を包含する第２のサイズ（例えば、４Ｂｙｔｅｓ）の第２の部分データ列との両方が辞書登録データのいずれかに一致するならば、第１の圧縮部１２０は第１の部分データ列ではなく第２の部分データ列を辞書アドレスへと符号化することで第１の圧縮データのサイズを小さくすることができる。
【００２０】
他方、第１の圧縮部１２０は、部分データ列が辞書登録データのいずれにも一致しないならば当該部分データ列（辞書不一致データと呼ばれる）をそのまま当該部分データ列の符号語として出力する（すなわち、当該部分データ列をパススルーする）。
【００２１】
すなわち、第１の圧縮データは、入力データ列１０に適用される分割パターン、ならびに、当該分割パターンに対応する各部分データ列と辞書登録データとの一致／不一致を示す辞書一致情報と、当該部分データ列の各々の符号語（すなわち、辞書アドレスまたは辞書不一致データ）とを含む。
【００２２】
さらに、第１の圧縮部１２０は、将来の入力データ列を効率的に圧縮するために、入力データ列１０を用いて辞書メモリ１１０に保存されたハッシュテーブルおよび辞書テーブルを更新する。すなわち、第１の圧縮部１２０は、入力データ列１０を分割した部分データ列の各々を辞書アドレスと関連付けて辞書テーブルに登録する。そして、第１の圧縮部１２０は、この部分データ列に対応するハッシュ値とこの辞書アドレスとを関連付けてハッシュテーブルに登録する。
【００２３】
第２の圧縮部１３０は、入力データ列１０を図示されない外部装置（例えばホスト）から受け取る。第２の圧縮部１３０は、現行の第１の圧縮データおよび過去の第１の圧縮データの比較、ならびに、圧縮済みのデータに相当する過去の入力データ列のうち少なくとも一方に基づいて、入力データ列１０を圧縮することによって第２の圧縮データを得る。第２の圧縮データは、少なくとも前述の辞書アドレスを含まない点で第１の圧縮データとは異なる。第２の圧縮部１３０は、第２の圧縮データを選択部１４０へと出力する。
【００２４】
選択部１４０は、第１の圧縮データを第１の圧縮部１２０から受け取り、第２の圧縮データを第２の圧縮部１３０から受け取る。選択部１４０は、第１の圧縮データおよび第２の圧縮データのうちデータサイズの小さい一方を選択することによって、圧縮データ１１を得る。選択部１４０は、圧縮データ１１を図示されない外部装置（例えば、ＮＡＮＤフラッシュメモリ）へと出力する。
【００２５】
図１の圧縮装置は、図５に例示されるデータ圧縮処理を行う。  
第１の圧縮部１２０は、辞書メモリ１１０に保存されるハッシュ関数、ハッシュテーブルおよび辞書テーブルを用いて、入力データ列１０を圧縮することによって第１の圧縮データを生成する（ステップＳ２０１）。第１の圧縮部１２０は、入力データ列１０を用いて辞書メモリ１１０に保存されるハッシュテーブルおよび辞書テーブルを更新する（ステップＳ２０２）。
【００２６】
第２の圧縮部１３０は、現行の第１の圧縮データおよび過去の第１の圧縮データの比較、ならびに、圧縮済みのデータに相当する過去の入力データ列のうち少なくとも一方に基づいて、入力データ列１０を圧縮することによって第２の圧縮データを生成する（ステップＳ２０３）。なお、ステップＳ２０１、ステップＳ２０２およびステップＳ２０３は、図５は異なる順序で実行されてもよい。
【００２７】
選択部１４０は、ステップＳ２０１において生成された第１の圧縮データおよびステップＳ２０２において生成された第２の圧縮データのうちデータサイズの小さい一方を選択することによって、圧縮データ１１を得る（ステップＳ２０４）。ステップＳ２０４の後に図５のデータ圧縮処理は終了する。
【００２８】
なお、図１の圧縮装置は、図９に例示される圧縮装置に変形することもできる。図９の圧縮装置は、分割部６５０を備えている点で図１の圧縮装置とは異なる。
【００２９】
分割部６５０は、オリジナルデータ列１２を図示されない外部装置（例えばホスト）から受け取る。分割部６５０は、オリジナルデータ列１２を予め定められた固定サイズに分割することによって、入力データ列１０を得る。
【００３０】
図９の第１の圧縮部１２０および第２の圧縮部１３０は、分割部６５０から固定サイズの入力データ列１０をそれぞれ受け取って圧縮する。
【００３１】
図６に例示されるように、第１の実施形態に係る伸長装置は、判定部３１０と、辞書メモリ３２０と、第１の伸長部３３０と、第２の伸長部３４０と、選択部３５０とを含む。この伸長装置は、本実施形態に係る圧縮装置によって生成された圧縮データ２１を伸長することによって固定サイズ（例えば、８Ｂｙｔｅｓ）の伸長データ２２を生成する。
【００３２】
判定部３１０は、圧縮データ２１を図示されない外部装置（例えば、ＮＡＮＤフラッシュメモリ）から受け取る。判定部３１０は、圧縮データ２１が第１の方式および第２の方式のいずれによって圧縮されているかを判定する。判定部３１０は、判定した方式を選択部３５０に通知し、圧縮データ２１を第１の伸長部３３０および第２の伸長部３４０へと出力する。
【００３３】
辞書メモリ３２０には、辞書テーブルが保存され。辞書テーブルは、図１の圧縮装置の辞書メモリ１１０に保存される辞書テーブルと対応する。すなわち、辞書メモリ３２０に保存される辞書テーブルは、辞書アドレスを、過去の伸長データを所定のサイズで分割した部分データ列（辞書登録データとも呼ばれる）と関連付ける。すなわち、辞書テーブルでは、辞書登録データが辞書アドレスと関連付けられている。なお、複数のサイズに対して個別の辞書テーブルが用意されてもよい。辞書メモリ３２０に保存される辞書テーブルは、後述されるように伸長データ２２を用いて更新される。
【００３４】
第１の伸長部３３０は、圧縮データ２１を判定部３１０から受け取る。第１の伸長部３３０は、辞書メモリ３２０に保存される辞書テーブルを用いて、圧縮データ２１を伸長することによって第１の伸長データを得る。なお、圧縮データ２１が第２の方式によって圧縮されている場合には、第１の伸長部３３０は圧縮データ２１を正しく伸長できない。第１の伸長部３３０は、第１の伸長データを選択部３５０へと出力する。
【００３５】
圧縮データ２１が第１の方式によって圧縮されている場合に、当該圧縮データ２１は当該圧縮データ２１に対応する圧縮前データに適用された分割パターン、ならびに、当該分割パターンに対応する各部分データ列と辞書登録データとの一致／不一致を示す辞書一致情報と、当該部分データ列の各々の符号語（すなわち、辞書アドレスまたは辞書不一致データ）とを含む。
【００３６】
第１の伸長部３３０は、圧縮データ２１から辞書一致情報を抽出し、当該辞書一致情報に基づいて各部分データ列の符号語を当該圧縮データ２１からさらに抽出する。そして、第１の伸長部３３０は、辞書一致情報に基づいて各部分データ列の符号語が辞書アドレスに相当するか辞書不一致データに相当するかを判定する。部分データ列の符号語が辞書アドレスに相当するならば、第１の伸長部３３０は辞書テーブルにおいて当該辞書アドレスに関連付けられる辞書登録データを当該部分データ列として取り扱う。他方、部分データ列の符号語が辞書不一致データに相当するならば、第１の伸長部３３０は当該辞書不一致データを当該部分データ列として取り扱う。
【００３７】
第２の伸長部３４０は、圧縮データ２１を判定部３１０から受け取る。第２の伸長部３４０は、過去の圧縮データおよび過去の伸長データのうち少なくとも一方に基づいて、圧縮データ２１を伸長することによって第２の伸長データを得る。なお、圧縮データ２１が第１の方式によって圧縮されている場合には、第２の伸長部３４０は圧縮データ２１を正しく伸長できない。圧縮データ２１が第２の方式によって圧縮されている場合に、当該圧縮データ２１は少なくとも前述の辞書アドレスを含まない。第２の伸長部３４０は、第２の伸長データを選択部３５０へと出力する。
【００３８】
選択部３５０は、判定部３１０によって判定された方式を通知され、第１の伸長データを第１の伸長部３３０から受け取り、第２の伸長データを第２の伸長部３４０から受け取る。選択部３５０は、第１の伸長データおよび第２の伸長データのうち判定部３１０によって判定された方式に対応する一方を選択することによって、伸長データ２２を得る。選択部３５０は、伸長データ２２を図示されない外部装置（例えばホスト）へと出力する。
【００３９】
さらに、選択部３５０は、伸長データ２２を用いて辞書メモリ３２０に保存された辞書テーブルを更新する。すなわち、選択部３５０は、伸長データ２２を分割した部分データ列の各々を辞書アドレスと関連付けて辞書テーブルに登録する。
【００４０】
なお、選択部３５０は、判定部３１０と同一または類似の機能を備えていてもよい。すなわち、選択部３５０が、圧縮データ２１が第１の方式および第２の方式のいずれによって圧縮されているかを判定し、第１の伸長データおよび第２の伸長データのうち判定した方式に対応する一方を選択してもよい。この場合には、判定部３１０は省略可能である。
【００４１】
図６の圧縮装置は、図７に例示されるデータ伸長処理を行う。  
判定部３１０は、圧縮データ２１が第１の方式および第２の方式のいずれによって圧縮されているかを判定する（ステップＳ４０１）。第１の伸長部３３０は、辞書メモリ３２０に保存される辞書テーブルを用いて、圧縮データ２１を伸長することによって第１の伸長データを得る（ステップＳ４０２）。
【００４２】
第２の伸長部３４０は、過去の圧縮データおよび過去の伸長データのうち少なくとも一方に基づいて、圧縮データ２１を伸長することによって第２の伸長データを得る（ステップＳ４０３）。なお、ステップＳ４０２およびステップＳ４０３は、図７は異なる順序で実行されてもよい。
【００４３】
選択部３５０は、ステップＳ４０２において生成された第１の伸長データおよびステップＳ４０３において生成された第２の伸長データのうちステップＳ４０１において判定された方式に対応する一方を選択することによって、伸長データ２２を得る（ステップＳ４０４）。
【００４４】
選択部３５０は、ステップＳ４０４において得られた伸長データ２２を用いて辞書メモリ３２０に保存された辞書テーブルを更新する（ステップＳ４０５）。ステップＳ４０５の後に図７のデータ伸長処理は終了する。
【００４５】
図８に例示されるように、図１の圧縮装置および図６の伸長装置をストレージ５００に接続することによって、入力データ列をロスレス圧縮して保存するストレージ装置が形成される。図８のストレージ装置によれば、図１の圧縮装置によって生成された圧縮データ１１がストレージ５００に書き込まれ、当該ストレージ５００から読み出された圧縮データ２１が図６の伸長装置によって伸長される。図８のストレージ装置は例えばＳＳＤに相当し、ストレージ５００は例えばＮＡＮＤフラッシュメモリに相当する。なお、本実施形態はＳＳＤに限らずＨＤＤにも適用可能である。例えば、ストレージ５００は磁気ディスクであってもよく、図１の圧縮装置および図６の伸長装置がハードディスクコントローラに組み込まれてもよい。
【００４６】
図８のストレージ装置のハードウェア構成が図１８に例示される。図１８のストレージ装置は、ＳＳＤコントローラ９０１と、入出力Ｉ／Ｆ（インターフェース）９０４と、ＮＡＮＤフラッシュメモリ９０５とを含む。ＳＳＤコントローラ９０１、入出力Ｉ／Ｆ９０４およびＮＡＮＤフラッシュメモリ９０５は、互いにバス接続されている。
【００４７】
ＳＳＤコントローラ９０１は、ＮＡＮＤフラッシュメモリ９０５の読み書きなどの種々の制御を行う。ＳＳＤコントローラ９０１は、圧縮装置９０２および伸長装置９０３を含む。圧縮装置９０２は例えば図１の圧縮装置に相当し、伸長装置９０３は例えば図６の伸長装置に相当する。
【００４８】
入出力Ｉ／Ｆ９０４は、図１８のストレージ装置と図示されない外部装置（例えばホスト）との間でデータをやり取りする。入出力Ｉ／Ｆ９０４は、例えばＵＳＢを用いて実装可能である。ＮＡＮＤフラッシュメモリ９０５は、図８のストレージ５００に相当する。
【００４９】
以上説明したように、第１の実施形態に係る圧縮装置は、圧縮済みのデータに相当する過去の入力データ列を所定のサイズで分割した部分データ列が登録された辞書を用いて入力データ列を圧縮することで第１の圧縮データを生成する。さらに、この圧縮装置は、現行の第１の圧縮データおよび過去の第１の圧縮データの比較、ならびに、過去の入力データ列のうち少なくとも一方に基づいて入力データ列を圧縮することで第２の圧縮データを生成する。そして、この圧縮装置は、第１の圧縮データおよび第２の圧縮データのうちデータサイズの小さい一方を選択してする。すなわち、この圧縮装置は、第１の圧縮データの圧縮率が低い場合（例えば、入力データ列を分割した部分データ列の大部分が辞書登録データと一致しない場合）には第２の圧縮データを選択できる。
【００５０】
故に、この圧縮装置によれば、安定的に高い圧縮率で入力データ列をロスレス圧縮することができる。また、この圧縮装置は、第１の圧縮データを生成するものの第２の圧縮データを生成しない従来の圧縮装置と比べて、スループットの低下およびハードウェアの増加をほとんど招くことなく実装可能である。
【００５１】
本実施形態に係る伸長装置は、本実施形態に係る圧縮装置によって生成された圧縮データを伸長できる。本実施形態に係るストレージ装置は、この圧縮データを保存することで高い応答性および信頼性を達成できる。
【００５２】
（第２の実施形態）  
第２の実施形態に係る圧縮装置において、第１の圧縮部１２０は図１０に例示される構造を持つ第１の圧縮データを生成する。図１０の例では、８Ｂｙｔｅｓデータ“ＡＢＣＤＥＦ１２”が入力データ列１０として取り扱われる。
【００５３】
第１の圧縮部１２０は、入力データ列１０の部分データ列“ＡＢＣＤＥＦ１２”、“ＡＢＣＤ”、“ＥＦ１２”、“ＡＢ”、“ＣＤ”、“ＥＦ”および“１２”についてそれぞれ辞書検索処理を行う。そして、部分データ列“ＡＢＣＤ”および“１２”が辞書登録データのいずれかに一致し、残りの部分データ列“ＥＦ”が辞書登録データのいずれにも一致しなかったとする。
【００５４】
第１の圧縮部１２０は、入力データ列１０に適用される分割パターン（例えば、４Ｂｙｔｅｓ｜２Ｂｙｔｅｓ｜２Ｂｙｔｅｓ）、ならびに、当該分割パターンに対応する各部分データ列と辞書登録データとの一致／不一致（例えば、一致｜不一致｜一致）を示す辞書一致情報を出力する。具体的には、８Ｂｙｔｅｓの入力データ列１０を２Ｂｙｔｅｓ単位、４Ｂｙｔｅｓ単位および８Ｂｙｔｅｓ単位でそれぞれ分割する場合に、部分データ列の出現パターンおよび当該分割パターンに対応する各部分データ列と辞書登録データとの一致パターンの組み合わせの総数は２６個である。故に、辞書一致情報は５ｂｉｔｓで表現することができる。
【００５５】
また、第１の圧縮部１２０は、辞書一致データに相当する部分データ列“ＡＢＣＤ”および“１２”に一致した辞書登録データに関連付けられる辞書アドレスを当該部分データ列“ＡＢＣＤ”および“１２”の符号語として出力する。辞書アドレスのデータサイズは、辞書テーブルのエントリ数に依存する。具体的には、２５６個の辞書登録データが辞書テーブルによって管理されているならば、辞書アドレスは８ｂｉｔｓで表現することができる。
【００５６】
さらに、第１の圧縮部１２０は、辞書不一致データに相当する部分データ列“ＥＦ”をそのまま当該部分データ列の符号語として出力する。具体的には、部分データ列“ＥＦ”のデータサイズは２Ｂｙｔｅｓであるから、符号語のデータサイズも同じ２Ｂｙｔｅｓ（１６ｂｉｔｓ）となる。
【００５７】
従って、図１０の例によれば、入力データ列１０のデータサイズが８Ｂｙｔｅｓ（６４ｂｉｔｓ）であるのに対して、第１の圧縮データのデータサイズは約３．６Ｂｙｔｅｓ（３７ｂｉｔｓ）である。故に、第１の圧縮データの領域節約率（１−圧縮後のデータサイズ／圧縮前のデータサイズ）は約４２％（＝１−３７／６４）と見積もることができる。
【００５８】
以上説明したように、第２の実施形態に係る圧縮装置は、圧縮済みのデータに相当する過去の入力データ列を所定のサイズで分割した部分データ列が登録された辞書を用いて入力データ列を圧縮することで第１の圧縮データを生成する。この第１の圧縮データは、辞書一致情報を含める必要はあるものの、入力データ列を分割した部分データ列の大部分が辞書登録データと一致する場合には高い圧縮率を達成できる。
【００５９】
なお、辞書一致情報および辞書不一致データの発生頻度には偏りがあると考えられる。従って、第１の圧縮部は、係るデータに対してＨｕｆｆｍａｎ符号化などの可変長符号化をさらに適用することによって、第１の圧縮データの期待圧縮率を向上させることができる。
【００６０】
（第３の実施形態）  
第３の実施形態に係る圧縮装置は、図１１に例示される第２の圧縮部７３０を備える点で図１または図６の圧縮装置と異なる。第２の圧縮部７３０は、第１の圧縮データを第１の圧縮部１２０から受け取る。第２の圧縮部７３０は、現行の第１の圧縮データおよび前回の第１の圧縮データの比較に基づいて、入力データ列１０を圧縮することによって第２の圧縮データを得る。第２の圧縮部７３０は、第２の圧縮データを選択部１４０へと出力する。第２の圧縮部７３０は、記憶部７３１と、比較部７３２と、符号化部７３３とを含む。
【００６１】
記憶部７３１には、前回の第１の圧縮データが保存されている。記憶部７３１に保存された前回の第１の圧縮データは、比較部７３２によって読み出される。なお、記憶部７３１に保存される前回の第１の圧縮データは、全部でなく一部であってもよい。例えば、前回の第１の圧縮データのうち辞書一致情報および辞書アドレスは記憶部７３１に保存され、当該前回の第１の圧縮データのうち辞書不一致データは記憶部７３１に保存されなくてもよい。
【００６２】
比較部７３２は、第１の圧縮部１２０から現行の第１の圧縮データを受け取り、記憶部７３１から前回の第１の圧縮データを受け取る。比較部７３２は、現行の第１の圧縮データを前回の第１の圧縮データと比較する。具体的には、比較部７３２は、現行の第１の圧縮データに含まれる各情報要素（例えば、辞書一致情報、辞書アドレスおよび辞書不一致データ）が、過去の第１の圧縮データに含まれる対応する情報要素と一致するか否かを判定する。比較部７３２は、比較結果を符号化部７３３に通知する。
【００６３】
符号化部７３３は、比較部７３２によって通知された比較結果に従い、現行の第１の圧縮データに含まれる情報要素のうち過去の第１の圧縮データに含まれる対応する情報要素と一致する情報要素をフラグ（以降の説明においてスキップフラグと呼ぶ）によって置き換えることで、第２の圧縮データを生成する。スキップフラグによって置き換えられた情報要素は、伸長装置への伝送がスキップされる。
【００６４】
具体的には、図１２に例示されるように、現行の第１の圧縮データに含まれる情報要素のうち辞書一致情報（Ｆｌａｇ＃１）、辞書アドレス（Ａｄｒｓ＃１）および辞書不一致データ（Ｄａｔａ＃１）が過去の第１の圧縮データに含まれる対応する情報要素（すなわち、辞書一致情報（Ｆｌａｇ＃０）、辞書アドレス（Ａｄｒｓ＃０）および辞書不一致データ（Ｄａｔａ＃０））と一致するとする。この場合に、符号化部７３３は現行の第１の圧縮データ全体をスキップフラグによって置き換えることで第２の圧縮データを生成する。例えば、特定の値（０など）を用いた初期化が行われる場合には、入力データ列１０には同一の値が連続して出現するかもしれない。係る場合には、第１の圧縮データにおいても同一の辞書一致情報、辞書アドレスおよび辞書不一致データが連続して出現することになる。従って、選択部１４０は、第２の圧縮データを選択して出力することで高い圧縮率を達成できる。
【００６５】
或いは、図１３に例示されるように、現行の第１の圧縮データに含まれる情報要素のうち辞書一致情報（Ｆｌａｇ＃１）および辞書アドレス（Ａｄｒｓ＃１）が過去の第１の圧縮データに含まれる対応する情報要素（すなわち、辞書一致情報（Ｆｌａｇ＃０）および辞書アドレス（Ａｄｒｓ＃０））と一致するとする。この場合に、符号化部７３３は現行の第１の圧縮データのうち辞書一致情報および辞書アドレスをスキップフラグによって置き換えることで第２の圧縮データを生成する。例えば、本実施形態に係る圧縮装置に接続される外部装置（ホストなど）に含まれるプロセッサは、２Ｂｙｔｅｓ、４Ｂｙｔｅｓ、８Ｂｙｔｅｓなどの２のべき乗Ｂｙｔｅｓのサイズ単位でデータを取り扱うことがあり、入力データ列１０が当該サイズに応じた周期性を持つかもしれない。係る場合には、第１の圧縮データにおいて同一の辞書一致情報および辞書アドレスが連続して出現する可能性がある。従って、選択部１４０は、第２の圧縮データを選択して出力することで高い圧縮率を達成できる。
【００６６】
以上説明したように、第３の実施形態に係る圧縮装置は、現行の第１の圧縮データのうち前回の第１の圧縮データと一致する情報要素をスキップフラグに置き換えることで第２の圧縮データを生成する。従って、この圧縮装置によれば、第１の圧縮データにおいて同一の情報要素が連続して出現する場合に、第２の圧縮データを選択して出力することで高い圧縮率を達成できる。
【００６７】
なお、本実施形態に係る圧縮装置に含まれる第２の圧縮部を実装するためには、符号化（すなわち圧縮）を行う符号化部に加えて、記憶部（すなわち、前回の第１の圧縮データの一部または全部を保存するためのハードウェア）および比較部（すなわち、現行の第１の圧縮データに含まれる各情報要素を前回の第１の圧縮データに含まれる対応する情報要素と比較するためのハードウェア）が必要となる。しかしながら、これら記憶部および比較部を増設することによる影響（コスト、消費電力、回路面積など）は限定的である。
【００６８】
（第４の実施形態）  
第４の実施形態に係る圧縮装置は、図１４に例示される第２の圧縮部８３０を備える点で図１または図６の圧縮装置と異なる。第２の圧縮部８３０は、入力データ列１０を図示されない外部装置（例えばホスト）から受け取る。第２の圧縮部８３０は、圧縮済みのデータに相当する前回の入力データ列における特定サイズの最頻値に基づいて入力データ列１０を圧縮することによって第２の圧縮データを得る。第２の圧縮部８３０は、第２の圧縮データを選択部１４０へと出力する。第２の圧縮部８３０は、記憶部８３１と、比較部８３２と、最頻値算出部８３３と、符号化部８３４とを含む。
【００６９】
記憶部８３１には、前回の入力データ列が保存されている。記憶部８３１に保存された前回の入力データ列は、最頻値算出部８３３によって読み出される。最頻値算出部８３３は、記憶部８３１から前回の入力データ列を読み出す。最頻値算出部８３３は、前回の入力データ列を上記特定サイズで分割した部分データ列に基づいて、特定サイズの各データパターンの出現頻度をカウントすることによって最頻値を算出する。最頻値算出部８３３は、最頻値を比較部８３２に通知する。
【００７０】
比較部８３２は、入力データ列１０を受け取り、最頻値算出部８３３によって最頻値を通知される。比較部８３２は、入力データ列１０を上記特定サイズで分割した部分データ列の各々を最頻値と比較する。具体的には、比較部８３２は、入力データ列１０を特定サイズで分割した部分データ列の各々が、最頻値と一致するか否かを判定する。比較部８３２は、比較結果を符号化部８３４に通知する。
【００７１】
符号化部８３４は、比較部８３２によって通知された比較結果に従い、入力データ列１０を圧縮することで第２の圧縮データを生成する。第２の圧縮データは、入力データ列１０を上記特定サイズで分割した各部分データ列と最頻値との一致／不一致を示す最頻値一致情報と、上記部分データ列のうち最頻値と一致しなかった部分データ列（以降、最頻値不一致データと呼ぶ）の符号語とを含む。すなわち、第２の圧縮データは、上記部分データ列のうち最頻値と一致した部分データ列の符号語を含まない。
【００７２】
本実施形態に係る圧縮装置は、図１５に例示されるデータ圧縮処理を行う。図１５の例では、入力データ列１０のデータサイズは１６Ｂｙｔｅｓであり、上記特定サイズは１Ｂｙｔｅである。この圧縮装置は、辞書マッチングに基づく第１の方式および最頻値マッチングに基づく第２の方式の両方を試行しデータサイズの小さい一方の圧縮データを選択することで、安定的に高い圧縮率を達成できる。ある種のデータでは所与のブロックにおける最頻値が次のブロックの最頻値と一致する可能性が高いので、係るデータを取り扱う場合には最頻値マッチングに基づく第２の方式によって高い圧縮率を達成できる。
【００７３】
図１５の例では、第１の圧縮データおよび第２の圧縮データのいずれにも、コーデック（圧縮方式）を示す情報要素（Ｃｏｄｅｃ）が含められる。コーデックが第１の方式および第２の方式のいずれかである場合には、係る情報要素は１ｂｉｔで表現できる。伸長装置は、係る情報要素に基づいて圧縮データが第１の方式および第２の方式のいずれによって圧縮されているかを判定できる。加えて、第１の圧縮データは、前述の辞書一致情報（Ｆｌａｇ）、辞書アドレス（Ａｄｒｓ）および辞書不一致データ（Ｄａｔａ）を含む。他方、第２の圧縮データは、最頻値一致情報（Ｍａｔｃｈ）および最頻値不一致データ（Ｄａｔａ）を含む。
【００７４】
最頻値一致情報は、１６Ｂｙｔｅｓの入力データ列１０を１Ｂｙｔｅで分割した１６個の部分データ列の各々が１Ｂｙｔｅの最頻値と一致するか否かを１ｂｉｔ（１／０）で表現する。故に、最頻値一致情報のデータサイズは２Ｂｙｔｅｓ（１６ｂｉｔｓ）となる。最頻値不一致データは、上記１６個の部分データ列のうち最頻値と一致しなかった部分データ列を伝送するために用意され、データサイズはそれぞれ１Ｂｙｔｅとなる。図１５の例では、２つの部分データ列が最頻値と一致しなかったので、最頻値不一致データのデータサイズは合計２Ｂｙｔｅｓである。故に、図１５の例によれば、第２の圧縮データのデータサイズは合計約４Ｂｙｔｅｓである。
【００７５】
なお、上記特定サイズは１Ｂｙｔｅに限定されない。また、第２の圧縮部８３０は、複数種類の特定サイズについて最頻値を算出し、第２の圧縮データのデータサイズを最小化させる最頻値を選択してもよい。
【００７６】
例えば、本実施形態に係る圧縮装置は図１６に示されるようにデータ圧縮処理を行ってもよい。図１６の例では、入力データ列１０のデータサイズは８Ｂｙｔｅｓであり、特定サイズは２Ｂｙｔｅｓである。入力データ列１０は、“００１２００００”、“００１４００００”、“００１６００００”の順で圧縮装置に与えられている。圧縮装置は、これら“００１２００００”、“００１４００００”および“００１６００００”に対し、辞書マッチングに基づく第１の方式および最頻値マッチングに基づく第２の方式の両方を試行しデータサイズの小さい一方の圧縮データを選択することで、安定的に高い圧縮率を達成できる。
【００７７】
なお、図１６の例によれば、“００１４００００”および“００１６００００”の圧縮データに関して、辞書不一致データおよび最頻値不一致データは同一である。故に、圧縮装置は、辞書一致情報および辞書アドレスのデータサイズと最頻値一致情報のデータサイズとを比較することで、データサイズの小さい圧縮データを選択することができる。
【００７８】
なお、図１５の例では、第１の圧縮データおよび第２の圧縮データのいずれにも、コーデック（圧縮方式）を示す情報要素（Ｃｏｄｅｃ）が用いられているが、例えば図１７に示されるように、辞書一致情報（Ｆｌａｇ）が係る情報要素を表現できるように拡張されてもよい。
【００７９】
図１７の例では、第１の圧縮データおよび第２の圧縮データのいずれにも、コーデックを示す情報要素（Ｆｌａｇ）が含められる。この情報要素（Ｆｌａｇ）は、辞書一致情報の拡張版に相当するから、コーデックが第１の方式である場合には、入力データ列１０に適用される分割パターン、ならびに、当該分割パターンに対応する各部分データ列と辞書登録データとの一致／不一致をさらに示す。換言すれば、この情報要素（Ｆｌａｇ）は、辞書一致情報に相当するＮ（例えば２６）種類の値およびコーデックが第２の方式であることを示す値との合計Ｎ＋１種類の値を取り得る。この情報要素（Ｆｌａｇ）は、ｃｅｉｌ（ｌｏｇ２（Ｎ＋１））  ｂｉｔｓで表現可能である。なお、ｃｅｉｌ（ｘ）は、ｘ以上の最小の整数を返す天井関数である。
【００８０】
伸長装置は、上記情報要素（Ｆｌａｇ）に基づいて圧縮データが第１の方式および第２の方式のいずれによって圧縮されているかを判定できる。加えて、第１の圧縮データは、前述の辞書アドレス（Ａｄｒｓ）および辞書不一致データ（Ｄａｔａ）を含む。他方、第２の圧縮データは、最頻値一致情報（Ｍａｔｃｈ）および最頻値不一致データ（Ｄａｔａ）を含む。
【００８１】
以上説明したように、第４の実施形態に係る圧縮装置は、前回の入力データ列における特定サイズの最頻値と現行の入力データ列との比較結果に基づいて第２の圧縮データを生成する。第２の圧縮データは、入力データ列を特定サイズで分割した部分データ列のうち最頻値と一致した部分データ列の符号語を含まない。従って、この圧縮装置によれば、入力データ列における最頻値が連続して一致する場合に、第２の圧縮データを選択して出力することで高い圧縮率を達成できる。
【００８２】
なお、本実施形態に係る圧縮装置に含まれる第２の圧縮部を実装するためには、符号化（すなわち圧縮）を行う符号化部に加えて、記憶部（すなわち、前回の入力データ列を保存するためのハードウェア）、最頻値算出部（すなわち、最頻値を算出するためのハードウェア）および比較部（すなわち、最頻値を現行の第１の入力データ列と比較するためのハードウェア）が必要となる。しかしながら、これら記憶部、最頻値算出部および比較部を増設することによる影響（コスト、消費電力、回路面積など）は限定的である。
【００８３】
前述の各実施形態において説明されたコーデックは、必要に応じて組み合わせて利用してもよい。例えば、第１の実施形態から第４の実施形態を組み合わせ、辞書マッチングに基づく方式、辞書マッチングに基づく圧縮データの一部をスキップフラグに置き換える方式、ならびに、最頻値マッチングに基づく方式のうちデータサイズを最小化させる方式を選択可能としてもよい。
【００８４】
上記各実施形態の処理の少なくとも一部は、汎用のコンピュータを基本ハードウェアとして用いることでも実現可能である。上記処理を実現するプログラムは、コンピュータで読み取り可能な記録媒体に格納して提供されてもよい。プログラムは、インストール可能な形式のファイルまたは実行可能な形式のファイルとして記録媒体に記憶される。記録媒体としては、磁気ディスク、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＤＶＤ等）、光磁気ディスク（ＭＯ等）、半導体メモリなどである。記録媒体は、プログラムを記憶でき、かつ、コンピュータが読み取り可能であれば、何れであってもよい。また、上記処理を実現するプログラムを、インターネットなどのネットワークに接続されたコンピュータ（サーバ）上に格納し、ネットワーク経由でコンピュータ（クライアント）にダウンロードさせてもよい。
【００８５】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００８６】
１０・・・入力データ列
１１，２１・・・圧縮データ
１２・・・オリジナルデータ列
２２・・・伸長データ
１１０，３２０・・・辞書メモリ
１２０・・・第１の圧縮部
１３０，７３０，８３０・・・第２の圧縮部
１４０，３５０・・・選択部
３１０・・・判定部
３３０・・・第１の伸長部
３４０・・・第２の伸長部
５００・・・ストレージ
６５０・・・分割部
７３１，８３１・・・記憶部
７３２，８３２・・・比較部
７３３，８３４・・・符号化部
８３３・・・最頻値算出部
９０１・・・ＳＳＤコントローラ
９０２・・・圧縮装置
９０３・・・伸長装置
９０４・・・入出力Ｉ／Ｆ
９０５・・・ＮＡＮＤフラッシュメモリ
【図１】
2016052046.tif 000003
【図２】
2016052046.tif 000004
【図３】
2016052046.tif 000005
【図４】
2016052046.tif 000006
【図５】
2016052046.tif 000007
【図６】
2016052046.tif 000008
【図７】
2016052046.tif 000009
【図８】
2016052046.tif 000010
【図９】
2016052046.tif 000011
【図１０】
2016052046.tif 000012
【図１１】
2016052046.tif 000013
【図１２】
2016052046.tif 000014
【図１３】
2016052046.tif 000015
【図１４】
2016052046.tif 000016
【図１５】
2016052046.tif 000017
【図１６】
2016052046.tif 000018
【図１７】
2016052046.tif 000019
【図１８】
2016052046.tif 000020