【手続補正書】
【提出日】平成18年8月2日(2006.8.2)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
過去の入力データ群、及び圧縮対象データを保持するバッファと、
過去の入力データにおける代表部分に対応するアドレスに、ポインタを記憶する第１記憶部と、
前記ポインタに対応するアドレスに、前記過去の入力データにおける補助部分を表す情報、及び前記代表部分と補助部分から成る過去の入力データが前記バッファ内に記憶されている位置を示すオフセット情報を記憶する第２記憶部とを備え、
圧縮対象データにおける代表部分に基づいて前記第１記憶部のアドレスを特定し、
該圧縮対象データにおける補助部分と前記第２記憶部に記憶された補助部分を示す情報とが一致する場合に、前記オフセット情報が示すバッファ内の位置に記憶された過去の入力データと前記圧縮対象データとが一致する長さ、及び前記オフセット情報に基づいて、前記圧縮対象データを符号化することを特徴とするデータ圧縮装置。
【請求項２】
過去の入力データ群、及び圧縮対象データを保持するバッファと、
第１及び第２の過去の入力データにおいて共通する代表部分に対応するアドレスに、第１ポインタを記憶する第１記憶部と、
前記第１ポインタに対応するアドレスに、前記第１の過去の入力データにおける補助部分を表す第１情報、及び該第１の過去の入力データが前記バッファ内に記憶されている位置を示す第１オフセット情報、及び第２ポインタを記憶する第２記憶部と、
前記第２ポインタに対応するアドレスに、前記第２の過去の入力データにおける補助部分を表す第２情報、及び該第２の過去の入力データが前記バッファ内に記憶されている位置を示す第２オフセット情報を記憶する第３記憶部とを備え、
圧縮対象データにおける代表部分に基づいて前記第１記憶部のアドレスを特定し、
該圧縮対象データにおける補助部分と前記第２記憶部に記憶された補助部分を表す第１情報とが一致する場合に、前記第１オフセット情報が示すバッファ内の位置に記憶された前記第１の過去の入力データと前記圧縮対象データとが一致する長さ、及び前記第１オフセット情報に基づいて、前記圧縮対象データを符号化し、
該圧縮対象データにおける補助部分と前記第２記憶部に記憶された補助部分を示す情報とが一致せず、該圧縮対象データにおける補助部分と前記第３記憶部に記憶された補助部分を表す第２情報とが一致する場合に、前記第２オフセット情報が示すバッファ内の位置に記憶された前記第２の過去の入力データと前記圧縮対象データとが一致する長さ、及び前記第２オフセット情報に基づいて、前記圧縮対象データを符号化することを特徴とするデータ圧縮装置。
【請求項３】
前記符号化にはハフマン符号化を用いることを特徴とする請求項１または２に記載のデータ圧縮装置。
【請求項４】
前記過去の入力データと前記圧縮対象データとが一致する長さは、最長一致長であることを特徴とする請求項１または２に記載のデータ圧縮装置。
【請求項５】
過去の入力データ群、及び圧縮対象データを保持するバッファと、過去の入力データにおける代表部分に対応するアドレスに、ポインタを記憶する第１記憶部と、前記ポインタに対応するアドレスに、前記過去の入力データにおける補助部分を表す情報、及び前記代表部分と補助部分から成る過去の入力データが前記バッファ内に記憶されている位置を示すオフセット情報を記憶する第２記憶部とを備えるデータ圧縮装置の制御方法であって、
圧縮対象データにおける代表部分に基づいて前記第１記憶部のアドレスを特定し、
該圧縮対象データにおける補助部分と前記第２記憶部に記憶された補助部分を示す情報とが一致する場合に、前記オフセット情報が示すバッファ内の位置に記憶された過去の入力データと前記圧縮対象データとが一致する長さ、及び前記オフセット情報に基づいて、前記圧縮対象データを符号化する
ことを特徴とするデータ圧縮装置の制御方法。
【請求項６】
過去の入力データ群、及び圧縮対象データを保持するバッファと、第１及び第２の過去の入力データにおいて共通する代表部分に対応するアドレスに、第１ポインタを記憶する第１記憶部と、前記第１ポインタに対応するアドレスに、前記第１の過去の入力データにおける補助部分を表す第１情報、及び該第１の過去の入力データが前記バッファ内に記憶されている位置を示す第１オフセット情報、及び第２ポインタを記憶する第２記憶部と、前記第２ポインタに対応するアドレスに、前記第２の過去の入力データにおける補助部分を表す第２情報、及び該第２の過去の入力データが前記バッファ内に記憶されている位置を示す第２オフセット情報を記憶する第３記憶部とを備えるデータ圧縮装置の制御方法であって、
圧縮対象データにおける代表部分に基づいて前記第１記憶部のアドレスを特定し、
該圧縮対象データにおける補助部分と前記第２記憶部に記憶された補助部分を表す第１情報とが一致する場合に、前記第１オフセット情報が示すバッファ内の位置に記憶された前記第１の過去の入力データと前記圧縮対象データとが一致する長さ、及び前記第１オフセット情報に基づいて、前記圧縮対象データを符号化し、
該圧縮対象データにおける補助部分と前記第２記憶部に記憶された補助部分を示す情報とが一致せず、該圧縮対象データにおける補助部分と前記第３記憶部に記憶された補助部分を表す第２情報とが一致する場合に、前記第２オフセット情報が示すバッファ内の位置に記憶された前記第２の過去の入力データと前記圧縮対象データとが一致する長さ、及び前記第２オフセット情報に基づいて、前記圧縮対象データを符号化する
ことを特徴とするデータ圧縮装置の制御方法。
【請求項７】
所定の入力記憶域から入力データを読み込み、該入力データと一致する過去の入力データを検索し、該過去の入力データに対応した符号作成情報をもとに符号化データを構成し、該符号化データを所定の出力記憶域に出力するデータ圧縮方法であって、
前記過去の入力データに関連した入力データ関連情報と、該入力データの符号作成情報を関連付けて記憶するための辞書を確保する確保工程と、
ここで、前記辞書は要素領域を含み、該要素領域は他の要素領域への接続情報を含むように構成される；
確保された前記辞書を検索する検索工程と、
前記過去の入力データに関連した入力データ関連情報と、該入力データの符号作成情報とを前記要素領域に登録する登録工程と、
前記辞書検索工程により、現在の入力データに関連した入力データ関連情報と対応する前記辞書内の入力関連情報の検索を、要素領域を前記接続情報で辿ることにより行い、該入力データ関連情報と関連する前記符号作成情報を求め、該符号作成情報から符号化データを作成する符号化データ作成工程と
を備えることを特徴とするデータ圧縮方法。
【請求項８】
前記検索工程により、現在の入力データに関連した入力データ関連情報と対応する前記辞書内の入力データ関連情報がみつからなかった場合に、前記入力データ関連情報と前記入力データに対応する符号作成情報とを関連付けて辞書に記憶する辞書登録工程を有することを特徴とする請求項第７項に記載のデータ圧縮方法。
【請求項９】
未使用の要素領域を含む自由要素管理領域を確保する工程と、要素取得工程と、要素返却工程、及び辞書更新工程とを有し、該辞書更新工程により、辞書に入力データから導かれる入力データ関連情報と符号作成情報とを関連付けて登録する場合に、該要素取得工程により前記自由要素管理領域から要素領域を取得し、該要素領域を辞書に追加し、辞書から要素領域を取り外すことを決定した場合に、前記要素返却工程により該要素領域を前記自由要素管理領域へ未使用の要素領域として返却・保管し、次の使用に備えることを特徴とする請求項第７項に記載のデータ圧縮方法。
【請求項１０】
入力データを一時記憶するバッファを確保し、前記符号作成情報は、バッファ内位置情報であり、
前記入力データとバッファ内位置情報が示す位置から開始する過去の入力データとを比較し最長一致長を求める最長一致検索工程と、
該最長一致検索工程にて得られた、前記バッファ内位置情報と最長一致長から符号化データを作成する符号作成工程と
を備えることを特徴とする請求項第７項に記載のデータ圧縮方法。
【請求項１１】
所定の入力記憶域から入力データを読み込み、該入力データと一致する過去のデータを検索し、該過去のデータに対応した符号作成情報をもとに符号化データを構成し、該符号化データを所定の出力記憶域に出力するデータ圧縮方法であって、
前記入力データに関連した代表データと、分類情報を関連付けて記憶する第１の記憶領域と、前記入力データに関連した補助データと符号作成情報を関連付けて前記分類情報ごとに記憶する第２の記憶領域とで構成される辞書を確保する確保工程と、
前記辞書を検索する第１検索工程及び第２検索工程で構成される検索工程とを備え、
前記第１の検索工程は、前記代表データをキーとして第１の記憶領域を検索し、該第２の検索工程は前記補助データをキーとして第２の記憶領域を検索するものであって、
前記入力データから代表データを導き、前記第１の検索工程により前記第１の記憶領域を検索して、該代表データに関連する前記分類情報を求め、
前記第２の検索工程によって該分類情報により限定される第２の記憶領域内を、前記入力データから導いた補助データをキーとして検索し、該補助データと関連する符号作成情報を求め、
該符号作成情報から符号化データを作成し、該符号化データを出力記憶域に出力することを特徴とするデータ圧縮方法。
【請求項１２】
前記第２の検索工程により、前記補助データと対応する符号作成情報が見つからなかった場合に、前記入力データから代表データと補助データ及び符号作成情報を導き、該代表データを第１の記憶領域に分類情報と対応させて記憶し、該分類情報によって限定される第２の記憶領域内に前記補助データと前記符号作成情報を対応させて記憶する辞書登録工程を有することを特徴とする請求項第１１項に記載のデータ圧縮方法。
【請求項１３】
前記第２の記憶領域は、前記分類情報により複数の小領域に分類され、該小領域は空であるか１個以上の要素領域から構成され、該要素領域は同じ小領域内の他の要素領域とポインタで接続されるデータ構造を構成するところの、補助データと符号作成情報と前記ポインタからなる要素領域を含むことを特徴とする請求項第１２項に記載のデータ圧縮方法。
【請求項１４】
未使用の要素領域を含む自由要素管理領域を確保する工程と、要素取得工程と、要素返却工程、及び辞書更新工程を有し、
該辞書更新工程により、辞書に入力データから導かれる代表データと補助データ及び符号作成情報を登録する場合に、該要素取得工程により前記自由要素管理領域から要素領域を取得し、該要素領域を前記第２の記憶領域に追加し、該第２の記憶領域から要素領域を取り外すことを決定した場合に、前記要素返却工程により、該要素領域を前記自由要素管理領域へ未使用の要素領域として保管し、次の使用に備えることを特徴とする請求項第１３項に記載のデータ圧縮方法。
【請求項１５】
入力データを一時記憶するバッファを確保し、前記符号作成情報は、バッファ内位置情報であり、
前記入力データとバッファ内位置情報が示す位置から開始する過去のデータとを比較し最長一致長を求める最長一致検索工程と、
該最長一致検索工程で得られた該バッファ内位置情報と前記最長一致長から符号化データを作成する符号作成工程と
を備えることを特徴とする請求項第１１項に記載のデータ圧縮方法。
【請求項１６】
前記符号作成情報は、最終出力符号そのものであることを特徴とする請求項第１１項に記載のデータ圧縮方法。
【請求項１７】
前記符号作成工程は、前記符号作成情報を可変長符号化して符号化データを作成することを特徴とする請求項第１５項に記載のデータ圧縮方法。
【請求項１８】
前記可変長符号化は、ハフマン符号化であることを特徴とする請求項第１７項に記載のデータ圧縮方法。
【請求項１９】
前記最長一致検索工程は、最長一致した前記入力データを前記辞書に登録することを特徴とする請求項第１５項に記載のデータ圧縮方法。
【請求項２０】
ハッシュ生成工程を具備し、前記代表データは、前記入力データからハッシュ生成工程により求めたハッシュ値とすることを特徴とする請求項第１１項に記載のデータ圧縮方法。
【請求項２１】
コンピュータが読み込み実行することで、所定の入力記憶域から入力データを読み込み、該入力データと一致する過去の入力データを検索し、該過去の入力データに対応した符号作成情報をもとに符号化データを構成し、該符号化データを所定の出力記憶域に出力するデータ圧縮装置として機能するコンピュータプログラムであって、
前記過去の入力データに関連した入力データ関連情報と、該入力データの符号作成情報を関連付けて記憶するための辞書を確保する確保工程と、
ここで、前記辞書は要素領域を含み、該要素領域は他の要素領域への接続情報を含むように構成される；
確保された前記辞書を検索する検索工程と、
前記過去の入力データに関連した入力データ関連情報と、該入力データの符号作成情報とを前記要素領域に登録する登録工程と、
前記辞書検索工程により、現在の入力データに関連した入力データ関連情報と対応する前記辞書内の入力関連情報の検索を、要素領域を前記接続情報で辿ることにより行い、該入力データ関連情報と関連する前記符号作成情報を求め、該符号作成情報から符号化データを作成する符号化データ作成工程と
をコンピュータに実行させることを特徴とするコンピュータプログラム。
【請求項２２】
コンピュータが読み込み実行することで、所定の入力記憶域から入力データを読み込み、該入力データと一致する過去のデータを検索し、該過去のデータに対応した符号作成情報をもとに符号化データを構成し、該符号化データを所定の出力記憶域に出力するデータ圧縮装置として機能するコンピュータプログラムであって、
前記入力データに関連した代表データと、分類情報を関連付けて記憶する第１の記憶領域と、前記入力データに関連した補助データと符号作成情報を関連付けて前記分類情報ごとに記憶する第２の記憶領域とで構成される辞書を確保する確保工程と、
前記辞書を検索する第１検索工程及び第２検索工程で構成される検索工程とを備え、
前記第１の検索工程は、前記代表データをキーとして第１の記憶領域を検索し、該第２の検索工程は前記補助データをキーとして第２の記憶領域を検索するものであって、
前記入力データから代表データを導き、前記第１の検索工程により前記第１の記憶領域を検索して、該代表データに関連する前記分類情報を求め、
前記第２の検索工程によって該分類情報により限定される第２の記憶領域内を、前記入力データから導いた補助データをキーとして検索し、該補助データと関連する符号作成情報を求め、
該符号作成情報から符号化データを作成し、該符号化データを出力記憶域に出力する
ことをコンピュータに実行させることを特徴とするコンピュータプログラム。
【請求項２３】
請求項２１又は２２に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【請求項２４】
所定の入力記憶域から入力データを読み込み、該入力データと一致する過去の入力データを検索し、該過去の入力データに対応した符号作成情報をもとに符号化データを構成し、該符号化データを所定の出力記憶域に出力するデータ圧縮装置であって、
前記過去の入力データに関連した入力データ関連情報と、該入力データの符号作成情報を関連付けて記憶するための辞書を確保する確保手段と、
ここで、前記辞書は要素領域を含み、該要素領域は他の要素領域への接続情報を含むように構成される；
確保された前記辞書を検索する検索手段と、
前記過去の入力データに関連した入力データ関連情報と、該入力データの符号作成情報とを前記要素領域に登録する登録手段と、
前記辞書検索手段により、現在の入力データに関連した入力データ関連情報と対応する前記辞書内の入力関連情報の検索を、要素領域を前記接続情報で辿ることにより行い、該入力データ関連情報と関連する前記符号作成情報を求め、該符号作成情報から符号化データを作成する符号化データ作成手段と
を備えることを特徴とするデータ圧縮装置。
【請求項２５】
所定の入力記憶域から入力データを読み込み、該入力データと一致する過去のデータを検索し、該過去のデータに対応した符号作成情報をもとに符号化データを構成し、該符号化データを所定の出力記憶域に出力するデータ圧縮装置であって、
前記入力データに関連した代表データと、分類情報を関連付けて記憶する第１の記憶領域と、前記入力データに関連した補助データと符号作成情報を関連付けて前記分類情報ごとに記憶する第２の記憶領域とで構成される辞書を確保する確保手段と、
前記辞書を検索する第１検索手段及び第２検索手段で構成される検索手段とを備え、
前記第１の検索手段は、前記代表データをキーとして第１の記憶領域を検索し、該第２の検索手段は前記補助データをキーとして第２の記憶領域を検索するものであって、
前記入力データから代表データを導き、前記第１の検索手段により前記第１の記憶領域を検索して、該代表データに関連する前記分類情報を求め、
前記第２の検索手段によって該分類情報により限定される第２の記憶領域内を、前記入力データから導いた補助データをキーとして検索し、該補助データと関連する符号作成情報を求め、
該符号作成情報から符号化データを作成し、該符号化データを出力記憶域に出力することを特徴とするデータ圧縮装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
【課題を解決するための手段】
かかる課題を解決するため、例えば本発明のデータ圧縮方法は、本願明細書の記載の実施形態と対応させて示すと以下の工程を備える。すなわち、
過去の入力データ群、及び圧縮対象データを保持するバッファ（例えば図７のウインドウバッファに相当）と、
過去の入力データにおける代表部分（図７の“ａｂ”に相当）に対応するアドレスに、ポインタを記憶する第１記憶部（図７の第１の記憶領域４０に相当）と、
前記ポインタに対応するアドレスに、前記過去の入力データにおける補助部分（図７の“ｃ”に相当）を表す情報、及び前記代表部分と補助部分から成る過去の入力データ（図７の“ａｂｃ”に相当）が前記バッファ内に記憶されている位置を示すオフセット情報（図７の“Ｐｃ”に相当）を記憶する第２記憶部（図７の第２の記憶領域４１に相当）とを備え、
圧縮対象データにおける代表部分（図７の“ａｂ”に相当）に基づいて前記第１記憶部のアドレスを特定し、
該圧縮対象データにおける補助部分（図７の“ｃ”に相当）と前記第２記憶部に記憶された補助部分（図７の“ｃ”に相当）を示す情報とが一致する場合に、前記オフセット情報（図７の“Ｐｃ”に相当）が示すバッファ内の位置に記憶された過去の入力データ（図７の“ａｂｃ”に相当）と前記圧縮対象データとが一致する長さ（図７のＬに相当）、及び前記オフセット情報（図７のｍに相当）に基づいて、前記圧縮対象データを符号化することを特徴とする。
また、本発明のデータ圧縮装置は、本願明細書に記載の実施形態と対応させて示すと以下の構成を備える。すなわち、
過去の入力データ群、及び圧縮対象データを保持するバッファ（例えば図７のウインドウバッファに相当）と、
第１及び第２の過去の入力データにおいて共通する代表部分（同“ａｂ”に相当）に対応するアドレスに、第１ポインタを記憶する第１記憶部（同第１の記憶領域４０に相当）と、
前記第１ポインタに対応するアドレスに、前記第１の過去の入力データにおける補助部分（同“ｃ”に相当）を表す第１情報、及び該第１の過去の入力データ（同“ａｂ”に相当）が前記バッファ内に記憶されている位置を示す第１オフセット情報（同“Ｐｃ”に相当）、及び第２ポインタ（同４１３のポインタに相当）を記憶する第２記憶部（同第２の記憶領域４１に相当）と、
前記第２ポインタに対応するアドレスに、前記第２の過去の入力データにおける補助部分（同“ｄ”に相当）を表す第２情報、及び該第２の過去の入力データ（同“ａｂ”に相当）が前記バッファ内に記憶されている位置を示す第２オフセット情報（同“Ｐｄ”に相当）を記憶する第３記憶部（同第２の記憶領域４２に相当）とを備え、
圧縮対象データにおける代表部分（同“ａｂ”に相当）に基づいて前記第１記憶部のアドレスを特定し、
該圧縮対象データにおける補助部分（同“ｃ”に相当）と前記第２記憶部に記憶された補助部分を表す第１情報とが一致する場合に、前記第１オフセット情報（同“Ｐｃ”に相当）が示すバッファ内の位置に記憶された前記第１の過去の入力データ（同“ａｂ”に相当）と前記圧縮対象データとが一致する長さ（同“Ｌ”に相当）、及び前記第１オフセット情報（同“ｍ”に相当）に基づいて、前記圧縮対象データを符号化し、
該圧縮対象データにおける補助部分（同“ｄ”に相当）と前記第２記憶部に記憶された補助部分を示す情報とが一致せず、該圧縮対象データにおける補助部分と前記第３記憶部に記憶された補助部分を表す第２情報とが一致する場合に、前記第２オフセット情報（同“Ｐｄ”に相当）が示すバッファ内の位置に記憶された前記第２の過去の入力データ（同“ａｂｄ”に相当）と前記圧縮対象データとが一致する長さ（同“Ｌ”に相当）、及び前記第２オフセット情報（同“ｍ”に相当）に基づいて、前記圧縮対象データを符号化することを特徴とする。