(57)【特許請求の範囲】
【請求項１】
過去の入力データ群、及び圧縮対象データを保持するバッファと、
過去の入力データにおける代表部分に対応するアドレスに、ポインタを記憶する第１記憶部と、
前記ポインタに対応するアドレスに、前記過去の入力データにおける補助部分を表す情報、及び前記代表部分と補助部分から成る過去の入力データが前記バッファ内に記憶されている位置を示すオフセット情報を記憶する第２記憶部とを備え、
圧縮対象データにおける代表部分に基づいて前記第１記憶部のアドレスを特定し、
該圧縮対象データにおける補助部分と前記第２記憶部に記憶された補助部分を示す情報とが一致する場合に、前記オフセット情報が示すバッファ内の位置に記憶された過去の入力データと前記圧縮対象データとが一致する長さ、及び前記オフセット情報に基づいて、前記圧縮対象データを符号化することを特徴とするデータ圧縮装置。
【請求項２】
過去の入力データ群、及び圧縮対象データを保持するバッファと、
第１及び第２の過去の入力データにおいて共通する代表部分に対応するアドレスに、第１ポインタを記憶する第１記憶部と、
前記第１ポインタに対応するアドレスに、前記第１の過去の入力データにおける補助部分を表す第１情報、及び該第１の過去の入力データが前記バッファ内に記憶されている位置を示す第１オフセット情報、及び第２ポインタを記憶する第２記憶部と、
前記第２ポインタに対応するアドレスに、前記第２の過去の入力データにおける補助部分を表す第２情報、及び該第２の過去の入力データが前記バッファ内に記憶されている位置を示す第２オフセット情報を記憶する第３記憶部とを備え、
圧縮対象データにおける代表部分に基づいて前記第１記憶部のアドレスを特定し、
該圧縮対象データにおける補助部分と前記第２記憶部に記憶された補助部分を表す第１情報とが一致する場合に、前記第１オフセット情報が示すバッファ内の位置に記憶された前記第１の過去の入力データと前記圧縮対象データとが一致する長さ、及び前記第１オフセット情報に基づいて、前記圧縮対象データを符号化し、
該圧縮対象データにおける補助部分と前記第２記憶部に記憶された補助部分を示す情報とが一致せず、該圧縮対象データにおける補助部分と前記第３記憶部に記憶された補助部分を表す第２情報とが一致する場合に、前記第２オフセット情報が示すバッファ内の位置に記憶された前記第２の過去の入力データと前記圧縮対象データとが一致する長さ、及び前記第２オフセット情報に基づいて、前記圧縮対象データを符号化することを特徴とするデータ圧縮装置。
【請求項３】
前記符号化にはハフマン符号化を用いることを特徴とする請求項１または２に記載のデータ圧縮装置。
【請求項４】
前記過去の入力データと前記圧縮対象データとが一致する長さは、最長一致長であることを特徴とする請求項１または２に記載のデータ圧縮装置。
【請求項５】
過去の入力データ群、及び圧縮対象データを保持するバッファと、過去の入力データにおける代表部分に対応するアドレスに、ポインタを記憶する第１記憶部と、前記ポインタに対応するアドレスに、前記過去の入力データにおける補助部分を表す情報、及び前記代表部分と補助部分から成る過去の入力データが前記バッファ内に記憶されている位置を示すオフセット情報を記憶する第２記憶部とを備えるデータ圧縮装置の制御方法であって、
圧縮対象データにおける代表部分に基づいて前記第１記憶部のアドレスを特定し、
該圧縮対象データにおける補助部分と前記第２記憶部に記憶された補助部分を示す情報とが一致する場合に、前記オフセット情報が示すバッファ内の位置に記憶された過去の入力データと前記圧縮対象データとが一致する長さ、及び前記オフセット情報に基づいて、前記圧縮対象データを符号化する
ことを特徴とするデータ圧縮装置の制御方法。
【請求項６】
過去の入力データ群、及び圧縮対象データを保持するバッファと、第１及び第２の過去の入力データにおいて共通する代表部分に対応するアドレスに、第１ポインタを記憶する第１記憶部と、前記第１ポインタに対応するアドレスに、前記第１の過去の入力データにおける補助部分を表す第１情報、及び該第１の過去の入力データが前記バッファ内に記憶されている位置を示す第１オフセット情報、及び第２ポインタを記憶する第２記憶部と、前記第２ポインタに対応するアドレスに、前記第２の過去の入力データにおける補助部分を表す第２情報、及び該第２の過去の入力データが前記バッファ内に記憶されている位置を示す第２オフセット情報を記憶する第３記憶部とを備えるデータ圧縮装置の制御方法であって、
圧縮対象データにおける代表部分に基づいて前記第１記憶部のアドレスを特定し、
該圧縮対象データにおける補助部分と前記第２記憶部に記憶された補助部分を表す第１情報とが一致する場合に、前記第１オフセット情報が示すバッファ内の位置に記憶された前記第１の過去の入力データと前記圧縮対象データとが一致する長さ、及び前記第１オフセット情報に基づいて、前記圧縮対象データを符号化し、
該圧縮対象データにおける補助部分と前記第２記憶部に記憶された補助部分を示す情報とが一致せず、該圧縮対象データにおける補助部分と前記第３記憶部に記憶された補助部分を表す第２情報とが一致する場合に、前記第２オフセット情報が示すバッファ内の位置に記憶された前記第２の過去の入力データと前記圧縮対象データとが一致する長さ、及び前記第２オフセット情報に基づいて、前記圧縮対象データを符号化する
ことを特徴とするデータ圧縮装置の制御方法。
【請求項７】
所定の入力記憶域から入力データを読み込み、該入力データと一致する過去の入力データを検索し、該過去の入力データに対応した符号作成情報をもとに符号化データを構成し、該符号化データを所定の出力記憶域に出力するデータ圧縮方法であって、
前記過去の入力データに関連した入力データ関連情報と、該入力データの符号作成情報を関連付けて記憶するための辞書を確保する確保工程と、
ここで、前記辞書は要素領域を含み、該要素領域は他の要素領域への接続情報を含むように構成される；
確保された前記辞書を検索する検索工程と、
前記過去の入力データに関連した入力データ関連情報と、該入力データの符号作成情報とを前記要素領域に登録する登録工程と、
前記辞書検索工程により、現在の入力データに関連した入力データ関連情報と対応する前記辞書内の入力関連情報の検索を、要素領域を前記接続情報で辿ることにより行い、該入力データ関連情報と関連する前記符号作成情報を求め、該符号作成情報から符号化データを作成する符号化データ作成工程と
を備えることを特徴とするデータ圧縮方法。
【請求項８】
前記検索工程により、現在の入力データに関連した入力データ関連情報と対応する前記辞書内の入力データ関連情報がみつからなかった場合に、前記入力データ関連情報と前記入力データに対応する符号作成情報とを関連付けて辞書に記憶する辞書登録工程を有することを特徴とする請求項第７項に記載のデータ圧縮方法。
【請求項９】
未使用の要素領域を含む自由要素管理領域を確保する工程と、要素取得工程と、要素返却工程、及び辞書更新工程とを有し、該辞書更新工程により、辞書に入力データから導かれる入力データ関連情報と符号作成情報とを関連付けて登録する場合に、該要素取得工程により前記自由要素管理領域から要素領域を取得し、該要素領域を辞書に追加し、辞書から要素領域を取り外すことを決定した場合に、前記要素返却工程により該要素領域を前記自由要素管理領域へ未使用の要素領域として返却・保管し、次の使用に備えることを特徴とする請求項第７項に記載のデータ圧縮方法。
【請求項１０】
入力データを一時記憶するバッファを確保し、前記符号作成情報は、バッファ内位置情報であり、
前記入力データとバッファ内位置情報が示す位置から開始する過去の入力データとを比較し最長一致長を求める最長一致検索工程と、
該最長一致検索工程にて得られた、前記バッファ内位置情報と最長一致長から符号化データを作成する符号作成工程と
を備えることを特徴とする請求項第７項に記載のデータ圧縮方法。
【請求項１１】
所定の入力記憶域から入力データを読み込み、該入力データと一致する過去のデータを検索し、該過去のデータに対応した符号作成情報をもとに符号化データを構成し、該符号化データを所定の出力記憶域に出力するデータ圧縮方法であって、
前記入力データに関連した代表データと、分類情報を関連付けて記憶する第１の記憶領域と、前記入力データに関連した補助データと符号作成情報を関連付けて前記分類情報ごとに記憶する第２の記憶領域とで構成される辞書を確保する確保工程と、
前記辞書を検索する第１検索工程及び第２検索工程で構成される検索工程とを備え、
前記第１の検索工程は、前記代表データをキーとして第１の記憶領域を検索し、該第２の検索工程は前記補助データをキーとして第２の記憶領域を検索するものであって、
前記入力データから代表データを導き、前記第１の検索工程により前記第１の記憶領域を検索して、該代表データに関連する前記分類情報を求め、
前記第２の検索工程によって該分類情報により限定される第２の記憶領域内を、前記入力データから導いた補助データをキーとして検索し、該補助データと関連する符号作成情報を求め、
該符号作成情報から符号化データを作成し、該符号化データを出力記憶域に出力することを特徴とするデータ圧縮方法。
【請求項１２】
前記第２の検索工程により、前記補助データと対応する符号作成情報が見つからなかった場合に、前記入力データから代表データと補助データ及び符号作成情報を導き、該代表データを第１の記憶領域に分類情報と対応させて記憶し、該分類情報によって限定される第２の記憶領域内に前記補助データと前記符号作成情報を対応させて記憶する辞書登録工程を有することを特徴とする請求項第１１項に記載のデータ圧縮方法。
【請求項１３】
前記第２の記憶領域は、前記分類情報により複数の小領域に分類され、該小領域は空であるか１個以上の要素領域から構成され、該要素領域は同じ小領域内の他の要素領域とポインタで接続されるデータ構造を構成するところの、補助データと符号作成情報と前記ポインタからなる要素領域を含むことを特徴とする請求項第１２項に記載のデータ圧縮方法。
【請求項１４】
未使用の要素領域を含む自由要素管理領域を確保する工程と、要素取得工程と、要素返却工程、及び辞書更新工程を有し、
該辞書更新工程により、辞書に入力データから導かれる代表データと補助データ及び符号作成情報を登録する場合に、該要素取得工程により前記自由要素管理領域から要素領域を取得し、該要素領域を前記第２の記憶領域に追加し、該第２の記憶領域から要素領域を取り外すことを決定した場合に、前記要素返却工程により、該要素領域を前記自由要素管理領域へ未使用の要素領域として保管し、次の使用に備えることを特徴とする請求項第１３項に記載のデータ圧縮方法。
【請求項１５】
入力データを一時記憶するバッファを確保し、前記符号作成情報は、バッファ内位置情報であり、
前記入力データとバッファ内位置情報が示す位置から開始する過去のデータとを比較し最長一致長を求める最長一致検索工程と、
該最長一致検索工程で得られた該バッファ内位置情報と前記最長一致長から符号化データを作成する符号作成工程と
を備えることを特徴とする請求項第１１項に記載のデータ圧縮方法。
【請求項１６】
前記符号作成情報は、最終出力符号そのものであることを特徴とする請求項第１１項に記載のデータ圧縮方法。
【請求項１７】
前記符号作成工程は、前記符号作成情報を可変長符号化して符号化データを作成することを特徴とする請求項第１５項に記載のデータ圧縮方法。
【請求項１８】
前記可変長符号化は、ハフマン符号化であることを特徴とする請求項第１７項に記載のデータ圧縮方法。
【請求項１９】
前記最長一致検索工程は、最長一致した前記入力データを前記辞書に登録することを特徴とする請求項第１５項に記載のデータ圧縮方法。
【請求項２０】
ハッシュ生成工程を具備し、前記代表データは、前記入力データからハッシュ生成工程により求めたハッシュ値とすることを特徴とする請求項第１１項に記載のデータ圧縮方法。
【請求項２１】
コンピュータが読み込み実行することで、所定の入力記憶域から入力データを読み込み、該入力データと一致する過去の入力データを検索し、該過去の入力データに対応した符号作成情報をもとに符号化データを構成し、該符号化データを所定の出力記憶域に出力するデータ圧縮装置として機能するコンピュータプログラムであって、
前記過去の入力データに関連した入力データ関連情報と、該入力データの符号作成情報を関連付けて記憶するための辞書を確保する確保工程と、
ここで、前記辞書は要素領域を含み、該要素領域は他の要素領域への接続情報を含むように構成される；
確保された前記辞書を検索する検索工程と、
前記過去の入力データに関連した入力データ関連情報と、該入力データの符号作成情報とを前記要素領域に登録する登録工程と、
前記辞書検索工程により、現在の入力データに関連した入力データ関連情報と対応する前記辞書内の入力関連情報の検索を、要素領域を前記接続情報で辿ることにより行い、該入力データ関連情報と関連する前記符号作成情報を求め、該符号作成情報から符号化データを作成する符号化データ作成工程と
をコンピュータに実行させることを特徴とするコンピュータプログラム。
【請求項２２】
コンピュータが読み込み実行することで、所定の入力記憶域から入力データを読み込み、該入力データと一致する過去のデータを検索し、該過去のデータに対応した符号作成情報をもとに符号化データを構成し、該符号化データを所定の出力記憶域に出力するデータ圧縮装置として機能するコンピュータプログラムであって、
前記入力データに関連した代表データと、分類情報を関連付けて記憶する第１の記憶領域と、前記入力データに関連した補助データと符号作成情報を関連付けて前記分類情報ごとに記憶する第２の記憶領域とで構成される辞書を確保する確保工程と、
前記辞書を検索する第１検索工程及び第２検索工程で構成される検索工程とを備え、
前記第１の検索工程は、前記代表データをキーとして第１の記憶領域を検索し、該第２の検索工程は前記補助データをキーとして第２の記憶領域を検索するものであって、
前記入力データから代表データを導き、前記第１の検索工程により前記第１の記憶領域を検索して、該代表データに関連する前記分類情報を求め、
前記第２の検索工程によって該分類情報により限定される第２の記憶領域内を、前記入力データから導いた補助データをキーとして検索し、該補助データと関連する符号作成情報を求め、
該符号作成情報から符号化データを作成し、該符号化データを出力記憶域に出力する
ことをコンピュータに実行させることを特徴とするコンピュータプログラム。
【請求項２３】
請求項２１又は２２に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【請求項２４】
所定の入力記憶域から入力データを読み込み、該入力データと一致する過去の入力データを検索し、該過去の入力データに対応した符号作成情報をもとに符号化データを構成し、該符号化データを所定の出力記憶域に出力するデータ圧縮装置であって、
前記過去の入力データに関連した入力データ関連情報と、該入力データの符号作成情報を関連付けて記憶するための辞書を確保する確保手段と、
ここで、前記辞書は要素領域を含み、該要素領域は他の要素領域への接続情報を含むように構成される；
確保された前記辞書を検索する検索手段と、
前記過去の入力データに関連した入力データ関連情報と、該入力データの符号作成情報とを前記要素領域に登録する登録手段と、
前記辞書検索手段により、現在の入力データに関連した入力データ関連情報と対応する前記辞書内の入力関連情報の検索を、要素領域を前記接続情報で辿ることにより行い、該入力データ関連情報と関連する前記符号作成情報を求め、該符号作成情報から符号化データを作成する符号化データ作成手段と
を備えることを特徴とするデータ圧縮装置。
【請求項２５】
所定の入力記憶域から入力データを読み込み、該入力データと一致する過去のデータを検索し、該過去のデータに対応した符号作成情報をもとに符号化データを構成し、該符号化データを所定の出力記憶域に出力するデータ圧縮装置であって、
前記入力データに関連した代表データと、分類情報を関連付けて記憶する第１の記憶領域と、前記入力データに関連した補助データと符号作成情報を関連付けて前記分類情報ごとに記憶する第２の記憶領域とで構成される辞書を確保する確保手段と、
前記辞書を検索する第１検索手段及び第２検索手段で構成される検索手段とを備え、
前記第１の検索手段は、前記代表データをキーとして第１の記憶領域を検索し、該第２の検索手段は前記補助データをキーとして第２の記憶領域を検索するものであって、
前記入力データから代表データを導き、前記第１の検索手段により前記第１の記憶領域を検索して、該代表データに関連する前記分類情報を求め、
前記第２の検索手段によって該分類情報により限定される第２の記憶領域内を、前記入力データから導いた補助データをキーとして検索し、該補助データと関連する符号作成情報を求め、
該符号作成情報から符号化データを作成し、該符号化データを出力記憶域に出力することを特徴とするデータ圧縮装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はデジタルデータの可逆的圧縮方法及び装置に関するものである。
【０００２】
【従来の技術】
ロスレス（可逆的）のデータ圧縮方法としては、ZivとLempelにより発明されたLZ77／LZ78を基本とした方法がある。
【０００３】
LZ77は、過去の入力データをウィンドウバッファに記憶し、現在の入力データと最長一致する過去の入力データをウィンドウバッファ内で検索し、みつかった最長一致ストリングの位置と長さを符号化して出力することによりデータ圧縮を行っている。この方法は、USP-4,054,951(Jackson,et al)、Ziv,J. and Lempel,A.,“A universal algorithm for sequential data compression”, IEEE Transaction on Information Theory,Vol.23,No.3,pp.337-343,May 1977 などに記載されている。
【０００４】
また、LZ78は、USP-4,464,650, USP-4,558,302, Ziv,J. and Lempel,A.,“Compression of individual sequences via variable-rate coding”, IEEE Transaction on Information Theory,Vol.24,No.5,pp.530-536,May 1978などに開示されているように過去の入力データから辞書を作成していき、現在の入力データと最長一致する辞書内のストリングを検索し、該ストリングに対応付けてあった符号を出力し、また最長一致した現在の入力データに次の1文字を連結したストリングを辞書に追加登録し、次の検索でより最長の一致が可能となるよう工夫したものである。
【０００５】
LZ77におけるウィンドウバッファは２〜３２ＫＢのサイズが適当であり、LZ77が、入力データとウィンドウバッファ内のデータとを比較するので、最長一致を探す範囲は、高々過去３２ＫＢのデータに限定される。一方、LZ78はウィンドウバッファの大きさには関係なく、辞書のサイズが許す限り遠い過去の入力データまで最長一致検索の範囲とすることでき、検索範囲はLZ77のように直近のものだけに限られない。したがって、LZ77が近い相関を活用するのに対し、LZ78は遠い相関も活用するという汎用性をもっているという利点がある。
【０００６】
また、LZ78は圧縮時に現在の入力データと辞書との比較をすればよく、辞書が検索に適した構成にできるので最長一致検索が高速に行える。
【０００７】
しかしながら、LZ78はデータ伸長時に辞書を作成・更新しながら、伸長処理をしなくてはならないが、LZ77はウィンドウバッファ内のストリングの位置とオフセットが符号となっているために、辞書を作成せずすぐに伸長が行え、LZ78よりも伸長処理が高速に行われる。
【０００８】
つまり、LZ78はデータに対して汎用性がありかつデータの圧縮が高速であるのに対し、LZ77はデータに対する汎用性には劣るものの、伸長処理を高速に行えるという特徴を有する。
【０００９】
LZ77の圧縮では、入力データと最長一致する過去のストリングを探すため、ウィンドウバッファを検索する必要がある。これを高速化するためには、USP-4,701,745 (J.R.Waterworth)、USP-5,049,881 (D.K.Gibson), USP-5.051,745 (P.W.Katz)、及びRFC-1951(“ DEFLATE Compressed Data Format Specification version 1.3”, P. Deutsch)などに開示されているようなハッシュ検索方法がある。これらの公知資料でのハッシュ検索方法は次のようなものである。
【００１０】
図１はこれらの説明図であり、１０はウィンドウバッファであり、Ｐ点より左側が既に圧縮の終わった入力データの圧縮前のデータが格納される領域であり、Ｐ点より右側はこれから圧縮しようとする入力データが格納される領域である。Ｐ点より左側の領域のサイズは、例えば３２ＫＢとする。Ｐ点から左側の領域の位置を示すオフセットは、Ｐ点を基点として左にいくにしたがい増えていくものとする。
【００１１】
また、１１はウィンドウバッファのオフセットを格納するハッシュ配列H[i]であって、要素数は215=32768エントリである。オフセットの長さは２バイトとしてよい。
【００１２】
次に図３は圧縮処理の処理手順であり、これに従い説明する。
【００１３】
ステップ３０１では、現在入力データのストリングを示すポインタＣに初期値（入力データの先頭アドレス）を与える。ステップ３０２では、初期化状態としてH[i]をゼロに初期化する。ここで、オフセットが０であることはありえないので、０であることはオフセットがいまだ格納されていないことを意味する。ステップ３０３では圧縮すべき入力データがまだあるかどうかチェックし、もしなければ処理を終了する。まだあればステップ３０４に処理が進む。
【００１４】
図１の１２は現在入力データの文字列である。この先頭３文字を配列C[0]〜C[2]で表すと、ハッシュ値ｈを図２のようにして計算する（ステップ３０４）。
【００１５】
なお、図２において、「＾」 は排他的ORを意味する。その他はＣ言語に準拠するが、「ｘ＜＜ｙ」はｘを上位ビット方向へのｙビット分だけシフトすることを示し、「ｘ＆ｙ」は値ｘ、ｙをビット単位に論理積することを示している。ハッシュ値ｈが求まったら、ステップ３０５において、H[h]と０を比較し、０ならばこのハッシュ値ｈをもつ３文字列がまだ現れなかったことを意味するのでステップ３０６にいき、H[h]に現在入力データのカレントオフセット（先頭文字のオフセット）を格納する。次にステップ３０７へいき、１バイトのデータC[0]をそのまま出力する。そしてステップ３０８へいき、ポインタＣを１増やし、次の入力データを処理可能にして、ステップ３０３へ戻る。
【００１６】
ステップ３０５において、H[h]が０でなければ、算出したハッシュ値ｈと同じハッシュ値を出す３文字列が現れていたので、その文字列があるH[h]の位置ｍを取り出す（ステップ３０９）。そして、ステップ３１０で、位置ｍからの過去のデータと、現在入力データとを比較し最長一致する長さＬを求める。次に、ステップ３１１では、ｍとＬをハフマン符号化したものを符号化データとして出力する。最長一致長Ｌが決まると、ステップＳ３１２でポインタＣをＬだけ増分し、ステップ３０３へ戻る。
【００１７】
【発明が解決しようとする課題】
LZ77の圧縮方式では、前述のようなハッシュ検索方法で圧縮時の処理を高速化することができるが、LZ78のようなウィンドウバッファを越えたずっと過去のデータをも現在入力データと比較するようなことはしないので、例えば、ウィンドウバッファの大きさ、３２ＫＢを周期として繰り返しが現れるようなデータについてはその圧縮効果を期待できない。一方、LZ78の圧縮方式は、伸長時にも辞書を作成更新しながら処理をするので、オーバーヘッドがあり伸長処理のスピードはLZ77よりも劣る。
【００１８】
伸長処理を高速化するためには、オフセットと長さもしくはそれらを符号化したものを符号化データとし、伸長時にはウィンドウバッファから対応するストリングを取り出すことが好ましい。しかし、オフセットと長さを符号化データにするということは圧縮時にウィンドウバッファ内だけの過去のデータを最長一致の検索対象に限定することになるので、伸長時の高速化と、圧縮時の比較対象の過去データの広がりをもたすこととは両立が困難ではある。
【００１９】
本発明は、かかる問題点に鑑みなされたものであり、伸長の高速化を生かしながら、高速にデータをロスレスに圧縮するデータ圧縮方法及び装置及びコンピュータプログラム及び記憶媒体を提供することにある。
【００２０】
【課題を解決するための手段】
かかる課題を解決するため、例えば本発明のデータ圧縮装置は、本願明細書の記載の実施形態と対応させて示すと以下の構成を備える。すなわち、
過去の入力データ群、及び圧縮対象データを保持するバッファ（例えば図７のウインドウバッファに相当）と、
過去の入力データにおける代表部分（図４の“ａｂ”に相当）に対応するアドレスに、ポインタを記憶する第１記憶部（図４の第１の記憶領域４０に相当）と、
前記ポインタに対応するアドレスに、前記過去の入力データにおける補助部分（図４の“ｃ”に相当）を表す情報、及び前記代表部分と補助部分から成る過去の入力データ（図４の４０が表わすエントリ“ａｂ”と４１が表わす“ｃ”の組み合わせに想到）が前記バッファ内に記憶されている位置を示すオフセット情報（図４の“Ｐｃ”に相当）を記憶する第２記憶部（図４の第２の記憶領域４１に相当）とを備え、
圧縮対象データにおける代表部分（図４の“ａｂ”に相当）に基づいて前記第１記憶部のアドレスを特定し、
該圧縮対象データにおける補助部分（“ｃ”）と前記第２記憶部に記憶された補助部分（図４の“ｃ”に相当）を示す情報とが一致する場合に、前記オフセット情報（図４の“Ｐｃ”に相当）が示すバッファ内の位置に記憶された過去の入力データ（図４の“ａｂｃ”に相当）と前記圧縮対象データとが一致する長さ（図６のＬに相当）、及び前記オフセット情報（図６のｍに相当）に基づいて、前記圧縮対象データを符号化することを特徴とする。
また、本発明のデータ圧縮装置は、本願明細書に記載の実施形態と対応させて示すと以下の構成を備える。すなわち、
過去の入力データ群、及び圧縮対象データを保持するバッファ（例えば図７のウインドウバッファに相当）と、
第１及び第２の過去の入力データにおいて共通する代表部分（図４の“ａｂ”に相当）に対応するアドレスに、第１ポインタを記憶する第１記憶部（同第１の記憶領域４０に相当）と、
前記第１ポインタに対応するアドレスに、前記第１の過去の入力データにおける補助部分（同“ｃ”に相当）を表す第１情報、及び該第１の過去の入力データ（３文字ストリングの“ａｂｃ”に相当）が前記バッファ内に記憶されている位置を示す第１オフセット情報（同“Ｐｃ”に相当）、及び第２ポインタ（同４１３のポインタに相当）を記憶する第２記憶部（同第２の記憶領域４１に相当）と、
前記第２ポインタに対応するアドレスに、前記第２の過去の入力データにおける補助部分（同“ｄ”に相当）を表す第２情報、及び該第２の過去の入力データ（３文字ストリング“ａｂｄ”に相当）が前記バッファ内に記憶されている位置を示す第２オフセット情報（同“Ｐｄ”に相当）を記憶する第３記憶部（同第２の記憶領域４２に相当）とを備え、
圧縮対象データにおける代表部分（同“ａｂ”に相当）に基づいて前記第１記憶部のアドレスを特定し、
該圧縮対象データにおける補助部分（同“ｃ”に相当）と前記第２記憶部に記憶された補助部分を表す第１情報とが一致する場合に、前記第１オフセット情報（同“Ｐｃ”に相当）が示すバッファ内の位置に記憶された前記第１の過去の入力データ（同“ａｂｃ”を先頭とする過去の入力データ）と前記圧縮対象データとが一致する長さ、及び前記第１オフセット情報に基づいて、前記圧縮対象データを符号化し、
該圧縮対象データにおける補助部分（同“ｄ”に相当）と前記第２記憶部に記憶された補助部分を示す情報とが一致せず、該圧縮対象データにおける補助部分と前記第３記憶部に記憶された補助部分を表す第２情報とが一致する場合に、前記第２オフセット情報（同“Ｐｄ”に相当）が示すバッファ内の位置に記憶された前記第２の過去の入力データ（同“ａｂｄ”を先頭とする過去の入力データ）と前記圧縮対象データとが一致する長さ、及び前記第２オフセット情報に基づいて、前記圧縮対象データを符号化することを特徴とする。
【００２１】
【発明の実施の形態】
以下、添付図面に従って本発明に係る実施形態を詳細に説明する。
【００２２】
図１７は、実施形態における装置のブロック構成図である。図示において、２０１は装置全体の制御を司るＣＰＵであり、２０２はブートプログラム、ＢＩＯＳ等を記憶しているＲＯＭである。２０３はＣＰＵ２０１のワークエリアとして使用するＲＡＭであり、ここにＯＳ及び実施形態における圧縮プログラムがロードされ実行されることになる。２０４はＯＳ、圧縮プログラムを始め、圧縮対象のファイル等各種ファイルを記憶するＨＤＤである。２０５は通信インタフェースであって、例えばモデムや、ネットワークカード等が接続され、ＬＡＮやインターネット等へ接続する。２０６はキーボード及びマウス、２０７は表示コントローラであって、表示用のメモリ及び描画を司るコントローラを内臓している。２０８はＣＲＴ等の表示装置である。
【００２３】
図示の構成において、本装置に電源が投入されると、ＲＯＭ２０２内のプログラムが起動し、ＨＤＤからＯＳをＲＡＭ２０３にロードし、そのＯＳ上で実施形態の圧縮プログラムを起動することになる。なお、ＯＳとしては様々なものがあり、いずれを採用しても構わない。
【００２４】
以下では、本装置のＯＳが動作を行い、ＨＤＤ２０４内に格納されている圧縮対象のファイル（ＨＤＤ２０４に格納されている）を指定し、圧縮プログラムを起動した場合に説明する。なお、圧縮対象のファイルはＨＤＤ２０４に限らず、如何なる記憶媒体に記憶されていても良い。また、圧縮後のデータの出力先として、ＨＤＤとして説明するが、この出力先も如何なるものでも良い。また、以下の説明における配列変数を始めとする各領域はＲＡＭ２０３に確保されるものとする。
【００２５】
図４〜図８は、本発明の第１の実施形態の説明図である。図４は、辞書に相当するもので、４０は第１の記憶領域に相当するところのヘッダ配列Ｘ［ｉ］、４１〜４４は第２の記憶領域であって、４１〜４４の各データは要素領域である。ヘッダ配列Ｘ［ｉ］における配列要素の個数が216＝65536個であって、各配列要素（４バイト）には、要素領域のアドレスが格納できるようになっている。したがって、ヘッダ配列の大きさは、２５６ＫＢ（＝4×65536)となる。
【００２６】
要素領域４１〜４４は、図５のＣ言語で示すデータ構造体であって、変数Ｃ（411に相当）はデータの１バイトを格納でき、offset（412に相当）は符号作成情報であるところのデータのバッファ内オフセットを格納でき、next（413に相当）は要素領域をチェイン接続するために要素領域のアドレスが格納でき、dummyはこのデータ構造体のメモリバウンダリを４バイトの倍数にするための調整用変数である。
【００２７】
本実施形態では長さが３バイトのストリングを図４の辞書に登録できる。図４では、'abc','abd','abs','cup' の４つの３文字ストリングが登録されている状態を示している。それぞれの３文字ストリングには、４１、４２、４３，４４の各要素領域が対応している。例えば、'ストリングabc'は、先頭の2バイト'ab'をバイナリで表すと0x6162 であるので、ヘッダ配列［0x6162］のところに４１のアドレスが格納されている。そして、要素領域４１には、先頭２バイトの情報は明らかであるから省略され、3バイト目の'c'だけが記録される。また、４１２のoffsetにはこの３文字ストリングが出現した過去データの位置が格納されている。そして、４１３のnextには、先頭２バイトが４１と同じ'ab'である３文字ストリングで、昇順にならべた場合に次にくるものの要素領域へのポインタが格納されている。４２も同様であり、４３もnext以外は同様であるが、４３の場合はチェインの末端であることを示すためにnextには存在しえない値、ここではNULL（ゼロ）が入っている。４４の場合も末端であるため、nextにNULLが入っている。
【００２８】
図７は、ウィンドウバッファを説明する図である。本実施形態では、現在入力データと最長一致する過去のデータを検索するのであるが、その検索範囲は現在から過去へ３２ＫＢさかのぼったところまでである。バッファは６４ＫＢの領域である。図７の（１）〜（５）は、順に最初から圧縮処理を進行させた場合のバッファの状態を表している。同図（１）はいまだ圧縮したデータがない、すなわち過去データがない場合であり、現在入力データの位置を示す変数strは０である。同図（２）は少したって圧縮が進み、過去入力データがいくらか生じた場合で、変数strにはある値（０＜str＜３２ＫＢ）が入っている。同図（３）は過去データがちょうど３２ＫＢたまった場合であり、str＝３２ＫＢである。同図（４）はさらに進行し、３２KB＜str＜６４ＫＢとなった状態である。このとき、過去データは３２ＫＢよりも多くバッファに残っているが、実際に検索対象となる過去データはstrの位置より過去へ３２ＫＢさかのぼったところが限界である。同図（５）はついにstr が64KBの最後に到達した状態であり、このままでは処理を進行できないので、同図（５）の状態にいたった場合は、バッファ内のデータをすべて32KBだけ左にシフトして、同図（３）の状態にする。それ以降は、同図（３）〜（５）の状態を繰り返すことになる。
【００２９】
さて、図６のフローチャートにそって、本実施形態の説明を詳細に述べる。ステップ６０１で、まず圧縮処理開始にさきだち初期化を行う。すなわち、
・ヘッダ配列Ｘ［ｉ］のすべての配列要素にNULLを格納する。
・自由要素管理領域を初期化する。
・現在入力データ位置変数strに０をセットする。
【００３０】
図８は、自由要素管理領域を説明する図である。図示において、８０１は要素管理領域、８０２は自由領域先頭ポインタである。要素管理領域は、配列Ｗ［ｉ］であって、その配列要素は、図５のデータ構造体であり、配列要素数は適当な値FREEMAX（例えば60000）とする。初期化は、自由領域先頭ポインタheadにＷ［０］のアドレスを設定し、Ｗ［i］のメンバー変数nextにＷ［i+1］のアドレスを設定する。これをすべてのiについて行い、最後の変数Ｗ［FREEMAX-1］の変数nextにはNULLを設定する。図８は、これを図示したものである。
【００３１】
次にステップ６０２へ行き、圧縮処理をする入力データがあるかどうか判定し、なければ終了し、あればステップ６０３へいく。
【００３２】
以下、図７のウィンドウバッファをWindow[i]で表すことにする。Window[i]の配列要素は１バイトである。変数indexは２バイトの変数であり、このindexに、Window[str]とWindow[str+1]をつなげた2バイトを設定する。このindexが、入力データの代表データに相当する。また、変数ｍにゼロをセットする。
【００３３】
次にステップ６０４にいき、Window[str], Window[str+1],Window[str+2]の３バイトで構成される３字ストリング（入力データ関連情報）と同じものが辞書内にあるかどうか検索し、もし辞書内になければこの３文字ストリングを辞書（４０、４１）に登録する。つまり、３文字ストリングのうち、前半の２文字（代表データ）が既にヘッダ配列４０に存在すれば、残りの１文字（補助データ）を要素領域４１として登録し、前半の２文字も一致しない場合には、要素領域４１は勿論、その要素領域４１のアドレスを、前半の２文字で示されるヘッダ配列４０の該当する位置に登録する。図９Ａ、９Ｂはステップ６０４の処理をＣ言語でプログラミングした一例である。Window[str+2]が入力データの補助データに相当する。
【００３４】
例えば、３文字ストリングが、'abd'であって、辞書のそのときの状態が図４のようであれば、indexは0x6162(“ab”に相当するバイナリ数)となり、Ｘ[index]を参照すると、ゼロでない値があり、その値をポインタとして辿ると４１にいく。４１で、４１１の'c'と'abd'の補助データである３バイト目を比較すると等しくないので、４１３のポインタを辿り、４２にいく。４２１の'd'と'abd'の３バイト目が一致するので、３文字ストリングと同じ過去の３文字ストリングがみつかったことになる。そして、４２２の値Ｐｄはこの過去の３文字ストリングのバッファ内位置を表すので、ｍにＰｄをセットし、かつ、Ｐｄの欄に現ポインタｓｔｒのアドレスを格納する。
【００３５】
また、もし３文字ストリングが'abe'であった場合には、４３まで辿っても一致する過去の３文字ストリングがみつからず、４３１の's' が'e'(“abe”の３バイト目)よりバイナリ数値として大きいという結果になる。４１〜４３は第１文字のバイナリ数値順にチェイン接続されているので、たとえ４３以降にも要素領域が接続されていても、もやは検索をしても一致する３文字ストリングはないことは明白であるから検索を打ち切る。そして、４２と４３の間に変数ｃが'e'である新しい要素領域を追加挿入する。このため、自由要素管理領域から未使用の要素領域を獲得して、上記追加挿入を行う。それ以外にも、新しい要素領域をチェインの先頭に追加したり、チェインの末端に追加したりする場合もあるが、これらの正しい処理方法は、図９Ａ、Ｂに示すが如くである。つまり、チェインの順序を出現する文字コード順に並べるために、ポインタのアドレスを更新する。
【００３６】
なお、バッファの位置は１を基点として１以上の値が割り当てられるようにすれば、ｍ＝０ならば、過去に同じ３文字ストリングがなかったことを意味することになる。
【００３７】
次にステップ６０５にいき、辞書とのマッチングが成功（過去の３文字ストリングがあった、すなわちｍ≠０）かどうかチェックする。
【００３８】
もしｍ≠０ならば、ステップ６０６にいき、バッファ内のｍ＋３の位置からのデータと入力データの４バイト目からを比較し最長一致の長さＬを線形探索法で求める。
【００３９】
ここで、USP-4,701,745などのようなハッシュ検索法よりも勝っている点を述べる。
【００４０】
これらのハッシュ検索法ではハッシュ値と３文字ストリングのバッファ内位置を対応させてハッシュ配列に記憶する。入力データの３文字からハッシュ関数によりハッシュ値を求め、同じハッシュ値にあるハッシュ配列に記憶してあるバッファ内位置ｍを求める。この場合は、異なる３文字列から求めたハッシュ値が等しくなることがあり得るので、最長一致を求めるためには、ｍ＋３から探索するのは危険であり、ｍから、つまり１文字目からｍ位置にあるバッファ内データと入力データとを比較しなければならない。したがって、本発明のほうが比較数が少ないので有利である。
【００４１】
さて、処理はステップ６０７にいき、符号化データを作成し出力する。符号化データの作成は、簡単にはｍを先頭が常に１の１６ビットのバイナリ数値表現とし、Ｌ−１を８ビットのバイナリ数値表現にしてｍ、（Ｌ−１）の順に出力すればよい。ただし、この場合にはＬは最大２５６バイトしか表せないので、ステップ６０６では最長一致の検索を２５６で打ち切ることが必要となる。また、１バイトを非圧縮のまま出力するときは、先頭が１の後に非圧縮の１バイトを追加した形式で出力する。
【００４２】
或いは、別の符号化としては、Deutsch, L.P.,“DEFLATE Compressed Data Format Specification”, RFC-1951に示されてあるように、Ｌとｍをハフマン符号化して出力してもよい。ハフマン符号化は可変長符号化の一形式であるが、もっとほかの可変長符号化であってもよい。
【００４３】
次にステップ６１１にいき、現在入力データの位置を表す変数strにstr+Lを設定し更新する。
【００４４】
ステップ６０５においてマッチングが不成功であった場合は、ステップ６０９へいき、Window[str]の１バイトを、前述のように先頭が１の９ビットで出力するか、前記RFC-1951に開示されてあるようにハフマン符号化して出力する。
【００４５】
そして、ステップ６１０へいき、str にstr+1を設定し更新し、ステップ６１１へ進む。
【００４６】
str変数の更新により、バッファの状態が図７（５）のような状態にいたることが起こりえる。つまりバッファのあふれである。バッファがあふれなければ、再びステップ６０２へいき６０２〜６０８の処理を繰り返す。もし、バッファのあふれがあった場合は、前述したように、バッファを左に３２ＫＢだけシフトして、図７（５）の状態から図７（３）の状態に変更する。このとき、辞書内の要素領域に記憶される４１２、４２２、４３２、・・・のすべてのオフセットは32KB（32,768）だけ減じて変更する必要がある。そして、減じた結果、ゼロ以下になった場合には、該当する要素領域を辞書から取り外し、その要素領域を自由要素管理領域に返却する。この操作は、図９ＡのソースコードのRETURN_LISTマクロ関数で示してあるようにnext変数の値の変更と、図８の変数headを書き換えることで行えることは、通常のリスト構造の手法である。
【００４７】
なお、自由要素管理領域から、未使用の要素領域を獲得したり、不要になった要素領域を自由要素管理領域へ返却したりすると、自由要素管理領域の状態は、図８の上図の初期状態にとどまることはなく、たとえば図８の下図のような接続関係が交錯した状態になっていく。また、使用している要素領域は、最初に用意された自由要素管理領域の連続した部分にはならないことは容易に理解できる。
【００４８】
このことにより、本発明の辞書の記憶領域がハッシュ配列のような連続した記憶領域とは異なっていることがわかる。バッファのシフトが終わったら再びステップ６０２へいき処理を繰り返す。
【００４９】
＜第２の実施の形態＞
次に、第２の実施形態における動作を図１０、１１に従って説明する。図１０は、要素領域を説明する図であって、１０１は要素領域、１０１１は補助データ、１０１２は符号作成情報であるところのオフセット、１０１３は子の要素領域へのポインタ、１０１４は次の要素領域へのポインタである。
【００５０】
図１１は辞書の構造を説明する図であって、１１０１は先に説明した実施形態（第１の実施形態）の記憶領域に相当する、２５６個の配列要素からなる配列であって、配列要素には要素領域のポインタが記憶される。つまり、このポインタが分類情報に相当する。ヘッダ配列の各要素から辿れる要素領域全体は第２の記憶領域である。図１１の１１０２〜１１０４の要素領域群は、３文字ストリングの２文字目に対応する要素領域であり、１１０５〜１１０７は３文字ストリングの３文字目に対応する要素領域である。
【００５１】
本第２の実施形態では、ヘッダ配列のインデックスが３文字ストリング（入力データ関連情報）の第１文字に相当し、これが入力データの代表データである。そして、３文字ストリングの２〜３文字目が補助データに相当する。なお、ヘッダ配列のインデックスとして１文字（１バイト）を用いるので、そのエントリーは２５６個となる。
【００５２】
第２の実施形態では、第１の実施形態と処理のフローはほとんど図６と同じであるが、ステップ６０３とステップ６０４が辞書の構造にあわせて変更となる。
【００５３】
例えば、図１１の辞書の状態において、３文字ストリング'acz'を検索する場合を考える。indexには代表データであるところの、'a'のバイナリ値をセットして、ヘッダ配列Ｘ［index］をアドレスとして辿ると１１０２にいく。そして、変数ｃの内容と補助データの'c'を比較すると一致するので、１１０２のdesc変数を取り出し、それをアドレスとして辿ると１１０５にいく、変数ｃの内容と補助データ'z'のを比較し要素領域のチェインをポインタnextでたどれば、１１０７で一致をみる。したがって、１１０７のoffsetをとりだし、それをｍにセットする。このような検索をしても一致する要素領域がなかった場合は、ｍは０のままである。なお、図１１において、１１０２〜１１０４が変数ｃの昇順に接続され、１１０５〜１１０７も変数ｃの昇順に接続される（もしくは、接続されるように更新処理を行う）。それ以外の処理は第１の実施形態と同じである。
【００５４】
また、本第２の実施形態ではヘッダ配列Ｘ［i］は、３文字ストリングの先頭バイトがインデックスとなるように構成されたが、３文字ストリングｘからハッシュ値を計算する適当なハッシュ関数h（ｘ）をつかって、Ｘ［ｈ（ｘ）］を上記のヘッダ配列の変わりに使用するような構成もとれる。この場合の配列Ｘ［ｈ（ｘ）］は、インデックスが２バイトとする。こうすれば、３文字ストリングがヘッダ配列によりばらつかせて登録できるので、要素領域を辿って検索する速度が向上する。ハッシュ関数は、例えば、
h(x) = (S[0] ＜＜ 8) | (S[1] ＾ S[2]);    （＜＜はビットシフト、＾は排他的ORを意味する）
とすればよい。S[i]は、３文字ストリングの第i+1バイトのデータである。
【００５５】
この場合は、前記ハッシュ値が代表データとなる。
【００５６】
h(x)は、第１バイト目のデータが異なれば違った値になるので、図１１と類似のヘッダ配列要素が第1バイトを、そこからリンクされる2個の要素領域が第２−３バイトを表すような態様になる。
【００５７】
＜第３の実施形態＞
また、上記の第２の実施形態で次のことが可能になる。つまり、図１１の辞書には３文字ストリングだけでなく、任意の長さのストリングを登録できる。例えば、４文字ストリングを登録したければ、１１０５〜１１０７の各desc変数に4文字目に対応する要素領域のアドレスをセットして、４文字目の要素領域を接続すればよい。
【００５８】
この場合、入力データ関連情報とは、入力データの先頭の不定長のバイト列である。また、入力データの先頭1バイトが代表データであり、2バイト以降の不定長のバイト列が補助データである。
【００５９】
また、実は第１の実施形態においても、図５の要素領域の構造体を図１０のそれに置き換えることによって、任意の長さのストリングを辞書に登録できることは容易にわかる。
【００６０】
図６のステップ６０６において、バッファ内と入力データの比較によって、最長一致が見つかったら、入力データの最長一致長の長さのストリングを辞書に登録することができる。
【００６１】
ステップ６０６にこのような最長一致のストリングを辞書に登録する処理を追加したならば、次回にバッファを線形探索行わずとも、入力データと辞書との比較だけによって最長一致がみつかるので、処理の高速化を期待できる。
【００６２】
また、ステップ６１２でバッファシフトのときに、要素領域の取り外しをおこわないことにすれば、バッファ内から消え去った遠い過去のストリングを辞書に残せ、上記の辞書とのマッチングで最長一致がみつかるので、データ圧縮を効率よく行える。
【００６３】
＜第４の実施形態＞
第１の実施形態で、最長一致の長さＬと過去のデータの位置ｍを合計２３ビットの符号で表すことを示したが、図１０の要素領域のかわりに図１２の要素領域を使うことを考える。図１２は、変数offsetのかわりに変数codeを格納する。
【００６４】
変数codeは、ヘッダ配列からその要素領域までたどって、各変数ｃをつなげてできるストリングの符号化データを意味する。その値は、オフセットを先頭が常に１の１６ビットで表し、ストリングの長さを８ビットで表し、合計２４ビットを変数codeにセットしたものである。
【００６５】
＜第５の実施形態＞
次に図１３〜１６にしたがって、第５の実施形態を説明する。図１３は、本第５の実施形態の辞書のデータ構造を説明する図であって、１３０１〜１３１２は要素領域である。要素領域は、図１４で示されるデータ形式であって、１４０１は１バイトのデータを格納する変数ｃ、１４０３はストリングの先頭バイトの位置を格納する変数offset、１４０４は子の要素領域へのポインタを格納する変数down、１４０５は次の要素領域へのポインタを格納する変数nextである。
【００６６】
図１３のおいて、１３０１はルートの要素領域であって、辞書を検索する出発点である。変数rootに１３０１のアドレスが格納されている。１３０２〜１３０４は、辞書に登録してあるストリングの先頭バイトを格納する要素領域であって、１３０２は先頭バイトが'a'、１３０３は先頭バイトが'c'、１３０４は先頭バイトが'g'のストリングの要素領域である。そして、１３０２は子の要素領域へのポインタが変数downに格納されていて、１３０５、１３０６へと接続されている。１３０５〜１３０８はストリングの第2バイトを格納する要素領域であって、例えば１３０５は第2バイトが'b'、１３０６は第２バイトが'k'のストリングの要素領域である。そして、１３０５はやはり子の要素領域へのポインタが変数downに格納されているいて、１３０９、１３１０へと接続されている。１３０９〜１３１１はストリングの第３バイトを格納する要素領域である。さらに、１３１０は子の要素領域へのポインタがdownに格納されていて、１３１２へと接続されている。１３１２のdown、nextはNULLなので、もはやどこにも接続されていない。
【００６７】
図１３の状態で辞書に登録されているストリングは図１６に示すように１１個あり、対応する要素領域は図１６に示されている。例えば、ストリング'abdp'は、1301,1302,1305,1310,1312のルートを含めて５個の要素領域からなっている。
【００６８】
さて、このような辞書を使用した本第５の実施形態のデータ圧縮の処理手順は、図６と同様であるが、ステップ６０４のマッチング・挿入の処理内容は、図１５のフローチャートに置き換えたものである。以下、図１５にそって説明する。
【００６９】
なお、以下において、変数offsetは、入力データと辞書内で最長一致するストリングのバッファ内における位置を格納する変数であり、Lは、そのストリングの長さであり、npは辞書のツリーを探索するための要素領域のポインタを格納する変数である。また、変数posにはあらかじめ入力データの位置が入っている。また、S[i]は入力データのストリングを表す配列である。
【００７０】
ステップ１５０１では、変数offset、Lを０で初期化する。変数npにはルート要素領域のdownをセットする。次に１５０２へいき、変数npが０かどうかチェックする。０ならば、辞書にはなにもストリングが登録されていないので、１５０８へいき、入力データの位置posから３バイトのストリングを図１３の態様に従い辞書に登録する。変数npが０でなければ、ステップ１５０３へいき、長さLを１だけカウントアップする。次に１５０４へいき、npが指す要素領域の変数np->cと入力データストリングの第Lバイト目S[L]を比較する。変数np->cが小さければ１５０５へいき、npに次の要素領域のポインタをセットする。そして、１５０６へいき、npがNULLかどうかチェックする。もしNULLであれば、それ以上一致するストリングが辞書内にはないので、ステップ１５０７へいき、入力データストリングをnpが指す要素領域に追加して辞書に登録する。１５０６でNULLでなければ比較すべき要素領域があるのでステップ１５０４へ戻る。１５０４での比較で、もし、変数np->cのほうがS[L]よりも大きければ、図１３のツリーは辞書順に登録されてあるので、これ以上の横のチェインを辿る必要がないので、npが指す要素領域の前に入力データを挿入して辞書に登録する。
【００７１】
ステップ１５０４の比較において両者が等しければ、ステップ１５０９にいき、offset変数がまだ０ならばoffsetにnpのoffsetをセットし、０でなければセットしない。ステップ１５１１にいき、npのoffsetには、入力データのposをセットし更新する。次に、１５１２へいきnp変数に子の要素領域へのポインタdownをセットする。そして、１５１３にいき、npがNULLかどうかチェックする。０ならば、１５０７へいきnpが指す位置に入力データストリングを挿入し辞書に登録する。ステップ1513で０でなければ、ステップ１５０３へ戻る。
【００７２】
上記処理で、入力データストリングの辞書への登録１５０８、１５０７は、Lが２以下であれば、（３−L）バイトのストリングS[L]〜S[2]を登録し、Lが３以上ならば１バイトのストリングS[L]を登録するものとする。また、辞書への登録では、要素領域の変数ｃには入力データストリングのバイトをセットし、変数offsetには入力データストリングの先頭位置、すなわちposをセットする。変数down、offsetは図１３の辞書態様となるべくポインタをセットする。
【００７３】
このような辞書へのストリングの登録によって、図１３に辞書態様は要素領域が変数ｃが昇順になるように構成される点に注意すべきである。
【００７４】
なお、offsetは図６のｍに相当する。ステップ６０６では、ウィンドウバッファ内で、さらに最長一致を検索する。ステップ６０６では、ウィンドウバッファのｍ＋１以降と入力データのpos＋ｍ＋１以降を比較することになる。ここで、さらにL2（L2＞L）の長さの最長一致が見つかった場合には、S[0]〜S[L2-1]のストリングを辞書に登録しておき、後のマッチングに役立てる。ここで、S[0]〜S[L-1]のストリングは登録済みなので、実際は残りのS[L]〜S[L2]を追加で登録することになる。
【００７５】
上記説明において、図１４の１４０２の変数ｃが入力データ関連情報に相当する。なお、本実施形態においては代表データと補助データに相当するものはない。  さらに、上記実施形態に以下のような改良を追加することを説明する。
【００７６】
まず、第１の実施形態と同じく、自由要素管理領域と、要素取得手段、要素返却手段、及び辞書更新手段を有し、辞書の更新と、要素領域の獲得と返却を行い、要素領域のメモリ管理をすることができる。
【００７７】
そして、第１の実施形態と同じく、辞書には入力データの所定長データである３バイトストリングだけを登録するようにしてもよい。また、第４の実施形態と同じように、offsetのかわりに、符号化データそのものを格納してもよい。
【００７８】
なお、上述した各実施形態は、ＲＡＭ２０３等のハードウェアを必要とするものの、その実体はＲＡＭ２０３にロードされ、ＣＰＵ２０１によって実行されるプログラムによって実現できる。すなわち、本発明は、コンピュータが実行するプログラムによって実行することができるので、当然、そのプログラムは本発明に含まれる。また、通常、プログラムは、記憶媒体に記憶されたそのプログラムを、その記憶媒体から直接実行する、或いは、記憶媒体に記憶されたプログラムをコンピュータが有する記憶装置（ＨＤＤ２０４等）にインストール若しくはコピーすることで実施できる。従って、かかる記憶媒体も本発明の範疇に含まれるものである。記憶媒体としては、紙テープ等の紙記憶媒体、フロッピーディスク等の磁気記憶媒体、ＣＤＲＯＭ等の光記憶媒体、或いは、ＭＯ等の光磁気記憶媒体等を上げることができるが、その媒体の記録方式は如何なるものであっても構わない。
【００７９】
【発明の効果】
以上説明したように本発明によれば、伸長の高速化を生かしながら、高速にデータをロスレスに圧縮することが可能になる。また、ＬＺ７７の伸長の高速性を生かしながら、ＬＺ７８の広範な範囲の検索を行える辞書構成法をとることにより、同じアルゴリズムでＬＺ７７のデータ圧縮装置と、あるいはまたＬＺ７８の圧縮装置への実装も可能になる。
【図面の簡単な説明】
【図１】従来のLZ77の方法を説明するための図である。
【図２】ハッシュ関数の演算手順を示すフローチャートである。
【図３】従来の方法の処理手順を示すフローチャートである。
【図４】第１の実施形態の辞書構成を示す図である。
【図５】第１の実施形態における要素領域の構造体を示す図である。
【図６】第１の実施形態の処理手順を示すフローチャートである。
【図７】ウィンドウバッファの推移を示す図である。
【図８】自由要素管理領域の構造を示す図である。
【図９Ａ】、
【図９Ｂ】マッチング・挿入処理のソースコードを示す図である。
【図１０】第２の実施形態の要素領域及びその構造体を示す図である。
【図１１】第２の実施形態の辞書構成を示す図である。
【図１２】第４の実施形態の要素領域及びその構造体を示す図である。
【図１３】第５の実施形態の辞書構成を示す図である。
【図１４】第５の実施形態の要素領域及びその構造体を示す図である。
【図１５】第５の実施形態の処理手順を示すフローチャートである。
【図１６】第５の実施形態の辞書の内容を示す図である。
【図１７】実施形態における装置のブロック構成図である。
【図１】
0003913004.tif 000002
【図２】
0003913004.tif 000003
【図３】
0003913004.tif 000004
【図４】
0003913004.tif 000005
【図５】
0003913004.tif 000006
【図６】
0003913004.tif 000007
【図７】
0003913004.tif 000008
【図８】
0003913004.tif 000009
【図９Ａ】
0003913004.tif 000010
【図９Ｂ】
0003913004.tif 000011
【図１０】
0003913004.tif 000012
【図１１】
0003913004.tif 000013
【図１２】
0003913004.tif 000014
【図１３】
0003913004.tif 000015
【図１４】
0003913004.tif 000016
【図１５】
0003913004.tif 000017
【図１６】
0003913004.tif 000018
【図１７】
0003913004.tif 000019