JP2000315954A - 入力データストリームの圧縮方法とその装置 - Google Patents
入力データストリームの圧縮方法とその装置Info
- Publication number
- JP2000315954A JP2000315954A JP2000078069A JP2000078069A JP2000315954A JP 2000315954 A JP2000315954 A JP 2000315954A JP 2000078069 A JP2000078069 A JP 2000078069A JP 2000078069 A JP2000078069 A JP 2000078069A JP 2000315954 A JP2000315954 A JP 2000315954A
- Authority
- JP
- Japan
- Prior art keywords
- data stream
- fingerprint
- block
- blocks
- input data
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T9/00—Image coding
- G06T9/005—Statistical coding, e.g. Huffman, run length coding
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Multimedia (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
(57)【要約】
【課題】 記憶装置の条件や伝送時間を減らすために更
に大きく圧縮する方式を提供する。 【解決手段】 圧縮プロセス（例えば、いずれかのLemp
el-Ziv圧縮方式）を適用する前に入力データの初期評価
として入力データストリームのより長い履歴およびより
長いコモンストリングを用いる。すなわち、通常の圧縮
プロセスが所望の圧縮を行うために比較的短い（最も最
近の数キロバイト）入力データの履歴を用いるが、より
長いコモンストリングシーケンスを用いることとより長
い履歴を用いることとが組み合わさって、圧縮効率を増
加できる。これは特に、繰り返す長いストリングを多く
有する長い入力ストリームを圧縮する際に有効である。
本発明に従うと、摘出した長コモンストリングに対して
ストリングマッチングを適用することになり入力データ
をプリプロセス（前処理）する。
に大きく圧縮する方式を提供する。 【解決手段】 圧縮プロセス（例えば、いずれかのLemp
el-Ziv圧縮方式）を適用する前に入力データの初期評価
として入力データストリームのより長い履歴およびより
長いコモンストリングを用いる。すなわち、通常の圧縮
プロセスが所望の圧縮を行うために比較的短い（最も最
近の数キロバイト）入力データの履歴を用いるが、より
長いコモンストリングシーケンスを用いることとより長
い履歴を用いることとが組み合わさって、圧縮効率を増
加できる。これは特に、繰り返す長いストリングを多く
有する長い入力ストリームを圧縮する際に有効である。
本発明に従うと、摘出した長コモンストリングに対して
ストリングマッチングを適用することになり入力データ
をプリプロセス（前処理）する。
Description
【０００１】
【発明の属する技術分野】本発明は、データ記憶および
通信システムに関し、特に、それらシステムの容量およ
び利用を改善することに関する。
通信システムに関し、特に、それらシステムの容量およ
び利用を改善することに関する。
【０００２】
【従来の技術】従来のデータ圧縮技術およびシステムは
デジタルデータストリームを圧縮コードストリームへと
符号化し、圧縮コードストリームを対応する元のデータ
ストリームへとデコードして戻す。ここでコードストリ
ームを「圧縮」としているが、それは、コードストリー
ムが通常、元のデータストリームに含まれる符号の数よ
りも少ない数のコードであるからである。このような小
さいコードは元のデータよりも少ない量のメモリーに記
憶することができる。
デジタルデータストリームを圧縮コードストリームへと
符号化し、圧縮コードストリームを対応する元のデータ
ストリームへとデコードして戻す。ここでコードストリ
ームを「圧縮」としているが、それは、コードストリー
ムが通常、元のデータストリームに含まれる符号の数よ
りも少ない数のコードであるからである。このような小
さいコードは元のデータよりも少ない量のメモリーに記
憶することができる。
【０００３】また、圧縮コードストリームは、圧縮され
ていない元のデータよりも短い時間で通信システム（例
えば、有線、無線、光ファイバ通信システム）にて送信
することができる。今日の通信ネットワークにおいて、
コンテンツ交換の量が相当に増大しており、データ送信
および記憶容量の必要性が今までかつてないほど増えて
いる。このように、データ圧縮は現代の送信プロトコル
および通信ネットワークにおいて重要な役割を担ってい
る。
ていない元のデータよりも短い時間で通信システム（例
えば、有線、無線、光ファイバ通信システム）にて送信
することができる。今日の通信ネットワークにおいて、
コンテンツ交換の量が相当に増大しており、データ送信
および記憶容量の必要性が今までかつてないほど増えて
いる。このように、データ圧縮は現代の送信プロトコル
および通信ネットワークにおいて重要な役割を担ってい
る。
【０００４】データ圧縮に有用な２つのクラスの圧縮技
術は、周知のように、いわゆる特殊用途圧縮と汎用圧縮
である。特殊用途圧縮技術は特殊な種類のデータを圧縮
するために設計され、実装するのに比較的低コストであ
ることが多い。例えば、周知な特殊用途圧縮技術とし
て、ランレングス符号化、ゼロサプレッション符号化、
ヌル圧縮符号化、パターン置き換えの技術がある。
術は、周知のように、いわゆる特殊用途圧縮と汎用圧縮
である。特殊用途圧縮技術は特殊な種類のデータを圧縮
するために設計され、実装するのに比較的低コストであ
ることが多い。例えば、周知な特殊用途圧縮技術とし
て、ランレングス符号化、ゼロサプレッション符号化、
ヌル圧縮符号化、パターン置き換えの技術がある。
【０００５】これら技術により、一般に、比較的小さな
圧縮比となる。なぜなら、一般的な特性および冗長性を
有するデータを通常圧縮するからである。圧縮比とは、
元のデータの長さに対しての圧縮コードの長さの測定値
である。しかし、特殊用途圧縮技術はより一般的性質の
データ（共通な性質を多く有さないようなデータ等）を
圧縮するのにあまり有効でないことが多い。
圧縮比となる。なぜなら、一般的な特性および冗長性を
有するデータを通常圧縮するからである。圧縮比とは、
元のデータの長さに対しての圧縮コードの長さの測定値
である。しかし、特殊用途圧縮技術はより一般的性質の
データ（共通な性質を多く有さないようなデータ等）を
圧縮するのにあまり有効でないことが多い。
【０００６】対照的に、汎用圧縮技術は一種類のデータ
を特別に圧縮するのに設計されてはおらず、実際の圧縮
プロセスの際に異なる種類のデータに適合することが多
い。最も有名で有用な汎用圧縮技術は、Lempel-Zivコー
ディングとして知られる。J.ZivとA.Lempelによって開
発された一連のアルゴリズムから派生している。これに
ついて、文献、Ziv et al.,"A Universal Algorithms f
or Sequential Data Compression", IEEE Transactions
on Information Theory, IT-23(3):337-343,May 1977
（ＬＺ１アルゴリズムを記載している）、Ziv et al.,"
Compression ofIndividual Sequences Via Variable-Ra
te Coding", IEEE Transactions on Information Techn
ology,IT-24(5):530-536, September 1978（ＬＺ２アル
ゴリズムを記載している）に記載されている。これらＬ
Ｚ１、ＬＺ２データ圧縮方式は周知であり詳細には説明
しない。
を特別に圧縮するのに設計されてはおらず、実際の圧縮
プロセスの際に異なる種類のデータに適合することが多
い。最も有名で有用な汎用圧縮技術は、Lempel-Zivコー
ディングとして知られる。J.ZivとA.Lempelによって開
発された一連のアルゴリズムから派生している。これに
ついて、文献、Ziv et al.,"A Universal Algorithms f
or Sequential Data Compression", IEEE Transactions
on Information Theory, IT-23(3):337-343,May 1977
（ＬＺ１アルゴリズムを記載している）、Ziv et al.,"
Compression ofIndividual Sequences Via Variable-Ra
te Coding", IEEE Transactions on Information Techn
ology,IT-24(5):530-536, September 1978（ＬＺ２アル
ゴリズムを記載している）に記載されている。これらＬ
Ｚ１、ＬＺ２データ圧縮方式は周知であり詳細には説明
しない。
【０００７】ＬＺ１（ＬＺ７７とも呼ばれる）データ圧
縮プロセスは繰り返された文字シーケンス（本明細書に
おいて、文字(character)とはビット群をいい言語とし
ての文字を意味するのではない）は、そのシーケンス
（マッチングシーケンス）の前の出現を参照することに
よって置き換えることができるという原理に基づいてい
る。この参照（例えば、ポインタ）は通常、前の出現の
位置（例えば、繰り返しシーケンスの開始からのオフセ
ットバイト)、および繰り返す文字の数（マッチドレン
グス）を示す情報を含む。この参照は通常、伝統的なＬ
Ｚ１コーディングに従うと「<Offset, length>」として
表されている。
縮プロセスは繰り返された文字シーケンス（本明細書に
おいて、文字(character)とはビット群をいい言語とし
ての文字を意味するのではない）は、そのシーケンス
（マッチングシーケンス）の前の出現を参照することに
よって置き換えることができるという原理に基づいてい
る。この参照（例えば、ポインタ）は通常、前の出現の
位置（例えば、繰り返しシーケンスの開始からのオフセ
ットバイト)、および繰り返す文字の数（マッチドレン
グス）を示す情報を含む。この参照は通常、伝統的なＬ
Ｚ１コーディングに従うと「<Offset, length>」として
表されている。
【０００８】対照的に、ＬＺ２（ＬＺ７８としても知ら
れる）圧縮は、圧縮の際に作られるルックアップテーブ
ルないし辞書を適応的に成長させることに基づいて、入
力データ文字のストリームを符号化値へとパースする
（parse)。すなわち、ＬＺ２は、ＬＺ１コーディングの
ようにバイト境界や長さにおいて一致性を見つけたりは
せず、辞書のワードがソースストリング（文字列）と一
致すれば、新しいワードが辞書に加えられる。この辞書
はその一致したワードとその後のソースストリングバイ
トからなる。ＬＺ２コーディングに従うと、一致は辞書
内のワードへのポインタないしインデックスとして符号
化される。
れる）圧縮は、圧縮の際に作られるルックアップテーブ
ルないし辞書を適応的に成長させることに基づいて、入
力データ文字のストリームを符号化値へとパースする
（parse)。すなわち、ＬＺ２は、ＬＺ１コーディングの
ようにバイト境界や長さにおいて一致性を見つけたりは
せず、辞書のワードがソースストリング（文字列）と一
致すれば、新しいワードが辞書に加えられる。この辞書
はその一致したワードとその後のソースストリングバイ
トからなる。ＬＺ２コーディングに従うと、一致は辞書
内のワードへのポインタないしインデックスとして符号
化される。
【０００９】上述のように、ＬＺ１およびＬＺ２アルゴ
リズムが用いる基本的な原理から派生した圧縮方式は多
い。例えば、Terry A.WelchはＬＺ２コーディングを改
善して周知のLempel-Ziv-Welch（ＬＺＷ）圧縮プロセス
を作った。これについて、文献、T.A.Welch,"A Techniq
ue for High performance Data Compression",IEEE Com
puter,pp.8-19,June 1984および米国特許第４５５８３
０２明細書（１９８５年１２月１０日発行）を参照する
とよい。
リズムが用いる基本的な原理から派生した圧縮方式は多
い。例えば、Terry A.WelchはＬＺ２コーディングを改
善して周知のLempel-Ziv-Welch（ＬＺＷ）圧縮プロセス
を作った。これについて、文献、T.A.Welch,"A Techniq
ue for High performance Data Compression",IEEE Com
puter,pp.8-19,June 1984および米国特許第４５５８３
０２明細書（１９８５年１２月１０日発行）を参照する
とよい。
【００１０】これらＬＺ２およびＬＺＷの両方の圧縮技
術は入力文字のストリングを固定長コードへとマッピン
グするいわゆるストリングテーブルを生成し利用する。
具体的には、これら圧縮技術は文字ストリームを順に検
索しテーブル（辞書）に前に記憶した最長のストリング
とマッチ（合致）する遭遇したシンボルのシーケンスに
基づいてコードを生成することにより、データ文字のス
トリームを圧縮されたコードストリームへと圧縮する。
各マッチがなされコードシンボルが生成されるに従い、
このプロセスは辞書に新しいストリングエントリーをも
記憶する。これは、データストリームにおけるマッチし
たシーケンスに加えて、データストリームにおいて遭遇
する次の文字シンボルからなる。
術は入力文字のストリングを固定長コードへとマッピン
グするいわゆるストリングテーブルを生成し利用する。
具体的には、これら圧縮技術は文字ストリームを順に検
索しテーブル（辞書）に前に記憶した最長のストリング
とマッチ（合致）する遭遇したシンボルのシーケンスに
基づいてコードを生成することにより、データ文字のス
トリームを圧縮されたコードストリームへと圧縮する。
各マッチがなされコードシンボルが生成されるに従い、
このプロセスは辞書に新しいストリングエントリーをも
記憶する。これは、データストリームにおけるマッチし
たシーケンスに加えて、データストリームにおいて遭遇
する次の文字シンボルからなる。
【００１１】上述のように、Lempel-Zivコーディングの
要点は、元のデータストリーム（例えば、送信されるド
キュメント）において繰り返されるストリングやサブス
トリングを見つけることである。圧縮されるドキュメン
トにおける繰り返されたフレーズは元のデータストリー
ムにおいて前に出現した場所へのポインタによって置き
換えられる。従って、この方法で圧縮されるデータ（例
えば、テキスト）をデコードすることには、ポインタが
指すすでにデコードしたテキストでポインタを置き換え
ることを必要とする。
要点は、元のデータストリーム（例えば、送信されるド
キュメント）において繰り返されるストリングやサブス
トリングを見つけることである。圧縮されるドキュメン
トにおける繰り返されたフレーズは元のデータストリー
ムにおいて前に出現した場所へのポインタによって置き
換えられる。従って、この方法で圧縮されるデータ（例
えば、テキスト）をデコードすることには、ポインタが
指すすでにデコードしたテキストでポインタを置き換え
ることを必要とする。
【００１２】周知のように、Lempel-Zivコーディングを
用いる際に設計上主に考慮することとして、ポインタが
どれくらい戻るか制限を設定し、その制限をどのように
するか決めることがある。別の設計上に考慮することと
して所望の制限内のどのサブストリングがポインタのタ
ーゲットとするかということがある。すなわち、前のテ
キストへのポインタのリーチの制限がなくなったり、い
わゆるグローイングウィンドウ（growing window)、あ
るいは前の「Ｎ」文字の固定サイズのウィンドウに制限
される。ここで、Ｎは通常、数千文字（例えば、３キロ
バイト）の範囲である。
用いる際に設計上主に考慮することとして、ポインタが
どれくらい戻るか制限を設定し、その制限をどのように
するか決めることがある。別の設計上に考慮することと
して所望の制限内のどのサブストリングがポインタのタ
ーゲットとするかということがある。すなわち、前のテ
キストへのポインタのリーチの制限がなくなったり、い
わゆるグローイングウィンドウ（growing window)、あ
るいは前の「Ｎ」文字の固定サイズのウィンドウに制限
される。ここで、Ｎは通常、数千文字（例えば、３キロ
バイト）の範囲である。
【００１３】このコーディングに従うと、ストリングの
繰り返しは、両方のストリングがウィンドウに出現した
場合にのみ発見され圧縮される。このようなLempel-Ziv
コーディングの設計時には、速さ、メモリー条件、圧縮
比の間で妥協して決められる。ウィンドウをスライドす
ることには少なくとも１つの欠点がある。ウィンドウを
スライドさせる方式は、入力テキストにおいて遠くに出
現するストリング（例えば、１００００文字分）を見つ
けることはできない。
繰り返しは、両方のストリングがウィンドウに出現した
場合にのみ発見され圧縮される。このようなLempel-Ziv
コーディングの設計時には、速さ、メモリー条件、圧縮
比の間で妥協して決められる。ウィンドウをスライドす
ることには少なくとも１つの欠点がある。ウィンドウを
スライドさせる方式は、入力テキストにおいて遠くに出
現するストリング（例えば、１００００文字分）を見つ
けることはできない。
【００１４】
【発明が解決しようとする課題】上述のようなＬＺ１、
ＬＺ２、ＬＺＷ圧縮方式のような従来の圧縮方式は有効
なデータ圧縮を提供しているが、記憶装置の条件や伝送
時間を減らすために更に大きく圧縮する方式が望まれて
いる。
ＬＺ２、ＬＺＷ圧縮方式のような従来の圧縮方式は有効
なデータ圧縮を提供しているが、記憶装置の条件や伝送
時間を減らすために更に大きく圧縮する方式が望まれて
いる。
【００１５】
【課題を解決するための手段】本発明は、比較的低い圧
縮比を実現する方法および装置を提供する。これは、圧
縮プロセス（例えば、いずれかのLempel-Ziv圧縮方式）
を適用する前に入力データの初期評価として入力データ
ストリームのより長い履歴およびより長いコモンストリ
ングを用いることを我々が認識したことに基づいてい
る。すなわち、通常の圧縮プロセスが所望の圧縮を行う
ために比較的短い（最も最近の数キロバイト）入力デー
タの履歴を用いるが、より長いコモンストリングシーケ
ンスを用いることとより長い履歴を用いることとが組み
合わさって、圧縮効率を増加できることを我々は認識し
た。これは特に、繰り返す長いストリングを多く有する
長い入力ストリームを圧縮する際に有効である。
縮比を実現する方法および装置を提供する。これは、圧
縮プロセス（例えば、いずれかのLempel-Ziv圧縮方式）
を適用する前に入力データの初期評価として入力データ
ストリームのより長い履歴およびより長いコモンストリ
ングを用いることを我々が認識したことに基づいてい
る。すなわち、通常の圧縮プロセスが所望の圧縮を行う
ために比較的短い（最も最近の数キロバイト）入力デー
タの履歴を用いるが、より長いコモンストリングシーケ
ンスを用いることとより長い履歴を用いることとが組み
合わさって、圧縮効率を増加できることを我々は認識し
た。これは特に、繰り返す長いストリングを多く有する
長い入力ストリームを圧縮する際に有効である。
【００１６】本発明に従うと、摘出した長コモンストリ
ングに対してストリングマッチングを適用することにな
り入力データをプリプロセス（前処理）する。好ましい
実施例に従うと、入力データは、個々のブロックが均等
なサイズ（線文字長）を有するように一連のブロックへ
と分割される。また、好ましい実施例に従うと、各ブロ
ックに対していわゆるフィンガプリント（指紋）が計算
され記憶される。フィンガプリントは、大きいテキスト
ストリングの比較的小さいシグネチャーである。例え
ば、千文字のストリングが３２ビット長のフィンガプリ
ントへとマッピングされる。従って、同一のストリング
は常に同じフィンガプリントを有する。また、等しくな
いストリングはほとんど常に等しくないフィンガプリン
トを有する（特定の確率ファクタ内で)。
ングに対してストリングマッチングを適用することにな
り入力データをプリプロセス（前処理）する。好ましい
実施例に従うと、入力データは、個々のブロックが均等
なサイズ（線文字長）を有するように一連のブロックへ
と分割される。また、好ましい実施例に従うと、各ブロ
ックに対していわゆるフィンガプリント（指紋）が計算
され記憶される。フィンガプリントは、大きいテキスト
ストリングの比較的小さいシグネチャーである。例え
ば、千文字のストリングが３２ビット長のフィンガプリ
ントへとマッピングされる。従って、同一のストリング
は常に同じフィンガプリントを有する。また、等しくな
いストリングはほとんど常に等しくないフィンガプリン
トを有する（特定の確率ファクタ内で)。
【００１７】本発明に従うと、入力データストリームが
横断され（traverse)、入力ストリームの特定の文字セ
ットから計算した（文字毎ベースで）中間フィンガプリ
ントと、前に計算し記憶したフィンガプリントとの間で
比較がなされる。好ましい実施例に従うと、入力ストリ
ームは、均等なブロックサイズを有するスライドウィン
ドウの関数として横断され、中間フィンガプリントは現
在の文字ウィンドウから計算され、前に記憶したフィン
ガプリントと比較される。
横断され（traverse)、入力ストリームの特定の文字セ
ットから計算した（文字毎ベースで）中間フィンガプリ
ントと、前に計算し記憶したフィンガプリントとの間で
比較がなされる。好ましい実施例に従うと、入力ストリ
ームは、均等なブロックサイズを有するスライドウィン
ドウの関数として横断され、中間フィンガプリントは現
在の文字ウィンドウから計算され、前に記憶したフィン
ガプリントと比較される。
【００１８】好ましい実施例に従い、フィンガプリント
の間にマッチを検出すると、入力ストリームは、検出し
たマッチの関数として決められた識別子とともに符号化
される。符号化された識別子は、元の入力ストリームに
おけるマッチングストリングの開始位置およびストリン
グ長を含む。その後に、好ましい実施例に従うと、前処
理され符号化された入力ストリームに対し更にLempel-Z
iv圧縮を用いて圧縮がなされる。
の間にマッチを検出すると、入力ストリームは、検出し
たマッチの関数として決められた識別子とともに符号化
される。符号化された識別子は、元の入力ストリームに
おけるマッチングストリングの開始位置およびストリン
グ長を含む。その後に、好ましい実施例に従うと、前処
理され符号化された入力ストリームに対し更にLempel-Z
iv圧縮を用いて圧縮がなされる。
【００１９】本発明に従うと、全体の記憶容量の条件を
余り大きくせずに、長いコモンストリングを識別し、入
力データの大きな履歴を調べることができる。本発明に
従って、様々な圧縮方法によって大きな圧縮比を実現す
ることができる。すなわち、本発明の原理はいずれの特
定の圧縮方式には依存せず、広い範囲の圧縮方式におい
て本発明の様々な原理を用いる利点を発揮することがで
きる。
余り大きくせずに、長いコモンストリングを識別し、入
力データの大きな履歴を調べることができる。本発明に
従って、様々な圧縮方法によって大きな圧縮比を実現す
ることができる。すなわち、本発明の原理はいずれの特
定の圧縮方式には依存せず、広い範囲の圧縮方式におい
て本発明の様々な原理を用いる利点を発揮することがで
きる。
【００２０】ストリングマッチングメカニズムとしてフ
ィンガプリントを用いることは新しくはない。テキスト
処理システムにおけるストリングマッチングに対してフ
ィンガプリントは用いられている。具体的には、テキス
トファイルにおいて長いコモンストリングを検索する際
に用いられている。例えば、文献、R.M.Karp and M.O.R
abin,"Efficient Randomized Pattern-Matching Algori
thms",IBMJ.Res.Develop.,Vol.31,No.2,pp.249-260, Ma
rch 1987は、ストリング検索の際にフィンガプリントを
用いることを記載している。しかし、我々はフィンガプ
リントを優雅な圧縮ツールとして導入できることを認識
した。これにより、全体の記憶容量条件を余り大きくせ
ずに、繰り返す長いストリングを多数有する。大きい入
力データストリームに対してデータ圧縮を改善すること
ができる。
ィンガプリントを用いることは新しくはない。テキスト
処理システムにおけるストリングマッチングに対してフ
ィンガプリントは用いられている。具体的には、テキス
トファイルにおいて長いコモンストリングを検索する際
に用いられている。例えば、文献、R.M.Karp and M.O.R
abin,"Efficient Randomized Pattern-Matching Algori
thms",IBMJ.Res.Develop.,Vol.31,No.2,pp.249-260, Ma
rch 1987は、ストリング検索の際にフィンガプリントを
用いることを記載している。しかし、我々はフィンガプ
リントを優雅な圧縮ツールとして導入できることを認識
した。これにより、全体の記憶容量条件を余り大きくせ
ずに、繰り返す長いストリングを多数有する。大きい入
力データストリームに対してデータ圧縮を改善すること
ができる。
【００２１】
【発明の実施の形態】圧縮プロセス（例えば、Lempel-Z
iv圧縮方式のいずれか）を適用する前に入力データの初
期評価として入力データストリームのより長い履歴およ
びより長いコモンストリングを用いることの認識に基づ
いて、本発明は比較的圧縮比を実現する方法および装置
を提供する。通常の圧縮プロセスが所望の圧縮をするた
めに入力データの比較的短い履歴（最も最近のバイト
群）を用いるが我々はより長いコモンストリングシーケ
ンスと共により長い履歴を用いることにより、特に、繰
り返す長いストリングを多数有するより長い入力ストリ
ーム（例えば、大規模データベース）を圧縮する際に、
圧縮効率を増加することができることを認識した。
iv圧縮方式のいずれか）を適用する前に入力データの初
期評価として入力データストリームのより長い履歴およ
びより長いコモンストリングを用いることの認識に基づ
いて、本発明は比較的圧縮比を実現する方法および装置
を提供する。通常の圧縮プロセスが所望の圧縮をするた
めに入力データの比較的短い履歴（最も最近のバイト
群）を用いるが我々はより長いコモンストリングシーケ
ンスと共により長い履歴を用いることにより、特に、繰
り返す長いストリングを多数有するより長い入力ストリ
ーム（例えば、大規模データベース）を圧縮する際に、
圧縮効率を増加することができることを認識した。
【００２２】本発明は、これら方法を実践する方法およ
び装置の形態で実現することができる。また本発明は、
ＦＤ（ｆｌｏｐｐｙ（登録商標） ｄｉｓｋｅｔｔ
ｅ）、ＣＤ−ＲＯＭ、ハードディスクドライブ、機械が
読み取り可能な記憶媒体のような実体的な媒体に実装さ
れるプログラムコードの形態にて実現することもでき
る。この場合、プログラムコードが機械（例えば、コン
ピュータ）へとロードされ機械によって実行されると、
その機械が本発明を実行する装置となる。また、本発明
はプログラムコードの形態にて実装することができ、例
えば、機械へとロードされおよび／または機械によって
実行され、あるいは電線、ケーブリング、光ファイバ、
電磁放射のような何らかの伝送媒体にて送信されるよう
なプログラムコードの形態にて実装される。プログラム
コード汎用プロセッサに実装された場合に、プログラム
コードセグメントがプロセッサと組合わさって、特定の
ロジック回路と類似するように動作するユニークなデバ
イスを与える。
び装置の形態で実現することができる。また本発明は、
ＦＤ（ｆｌｏｐｐｙ（登録商標） ｄｉｓｋｅｔｔ
ｅ）、ＣＤ−ＲＯＭ、ハードディスクドライブ、機械が
読み取り可能な記憶媒体のような実体的な媒体に実装さ
れるプログラムコードの形態にて実現することもでき
る。この場合、プログラムコードが機械（例えば、コン
ピュータ）へとロードされ機械によって実行されると、
その機械が本発明を実行する装置となる。また、本発明
はプログラムコードの形態にて実装することができ、例
えば、機械へとロードされおよび／または機械によって
実行され、あるいは電線、ケーブリング、光ファイバ、
電磁放射のような何らかの伝送媒体にて送信されるよう
なプログラムコードの形態にて実装される。プログラム
コード汎用プロセッサに実装された場合に、プログラム
コードセグメントがプロセッサと組合わさって、特定の
ロジック回路と類似するように動作するユニークなデバ
イスを与える。
【００２３】図１は、本発明に従ってデータを圧縮した
り脱圧縮したりするためのシステム１００のブロック図
である。システム１００は、ほんの少しだけ名前を揚げ
るのに伝送媒体（例えば、有線、無線、光ファイバ等）
上に情報を送信するのに用いられる。また、システム１
００は、例えば、コンピュータのディスクドライブのよ
うな磁気媒体、ＣＤ−ＲＯＭのような光学的に読み取り
可能な媒体、インターネット上の媒体へと情報を記録
し、またはそれらから情報を読み取るのにも有用であ
る。
り脱圧縮したりするためのシステム１００のブロック図
である。システム１００は、ほんの少しだけ名前を揚げ
るのに伝送媒体（例えば、有線、無線、光ファイバ等）
上に情報を送信するのに用いられる。また、システム１
００は、例えば、コンピュータのディスクドライブのよ
うな磁気媒体、ＣＤ−ＲＯＭのような光学的に読み取り
可能な媒体、インターネット上の媒体へと情報を記録
し、またはそれらから情報を読み取るのにも有用であ
る。
【００２４】従って、本発明に従って圧縮されたデータ
を磁気ディスクドライブのような磁気媒体、ＣＤ−ＲＯ
Ｍのような光記録可能な媒体上に記録することができ
る。図１において、入力データストリーム１０５（例え
ば、テスト）が入力データエンコーダ１１０に供給され
る。下で詳細に述べるように、本発明に従う入力データ
エンコーダ１１０は、抽出する長いコモンストリングに
対してストリングマッチング技術を適用することにより
本発明に従って入力データストリームをプリプロセスお
よび符号化する。この符号化プロセスに関連する本発明
の多くの原理は下で図２に示した例を特に参照してより
広く説明する。
を磁気ディスクドライブのような磁気媒体、ＣＤ−ＲＯ
Ｍのような光記録可能な媒体上に記録することができ
る。図１において、入力データストリーム１０５（例え
ば、テスト）が入力データエンコーダ１１０に供給され
る。下で詳細に述べるように、本発明に従う入力データ
エンコーダ１１０は、抽出する長いコモンストリングに
対してストリングマッチング技術を適用することにより
本発明に従って入力データストリームをプリプロセスお
よび符号化する。この符号化プロセスに関連する本発明
の多くの原理は下で図２に示した例を特に参照してより
広く説明する。
【００２５】図１に戻ると、本発明に従って作られた符
号化入力データストリーム１１５はコンプレッサ１２０
に渡される。好ましい実施例に従うコンプレッサ１２０
は、符号化入力データストリーム１１５を圧縮データ１
２５に圧縮するのにLempel-Ziv圧縮を、具体的には、Ｌ
Ｚ７７コーディングを適用する。ここで、上述のように
本発明に従って符号化入力データストリーム１１５を圧
縮するのにいずれのLempel-Zivタイプの圧縮をも有効に
用いて本発明の原理の利点を実現することができること
に留意されたい。
号化入力データストリーム１１５はコンプレッサ１２０
に渡される。好ましい実施例に従うコンプレッサ１２０
は、符号化入力データストリーム１１５を圧縮データ１
２５に圧縮するのにLempel-Ziv圧縮を、具体的には、Ｌ
Ｚ７７コーディングを適用する。ここで、上述のように
本発明に従って符号化入力データストリーム１１５を圧
縮するのにいずれのLempel-Zivタイプの圧縮をも有効に
用いて本発明の原理の利点を実現することができること
に留意されたい。
【００２６】次に圧縮データ１２５はチャネルエンコー
ダ１３０により符号化されチャネル符号化された情報１
３５を作る。チャネル符号化により圧縮された情報に対
し情報を加え、エラー検出やデータ読み取りプロセスに
おける訂正を可能にする。伝統的なチャネル符号化技術
としては、各シンボルが１もしくは複数のデータビット
で表されるシンボルのシーケンスを符号化する周知のRe
ed-Solomon符号化がある。次にこれらシンボルは変調エ
ンコーダ１４０により変調符号化され、変調されたデー
タストリーム１４５を作る。これは、伝送チャネルを通
って送信されるかあるいは媒体１５０上に記録されるチ
ャネルシーケンスを定める。
ダ１３０により符号化されチャネル符号化された情報１
３５を作る。チャネル符号化により圧縮された情報に対
し情報を加え、エラー検出やデータ読み取りプロセスに
おける訂正を可能にする。伝統的なチャネル符号化技術
としては、各シンボルが１もしくは複数のデータビット
で表されるシンボルのシーケンスを符号化する周知のRe
ed-Solomon符号化がある。次にこれらシンボルは変調エ
ンコーダ１４０により変調符号化され、変調されたデー
タストリーム１４５を作る。これは、伝送チャネルを通
って送信されるかあるいは媒体１５０上に記録されるチ
ャネルシーケンスを定める。
【００２７】ノイズや干渉は多くの場合、データストリ
ームの伝送や記録時にチャネル／媒体１５０にて投入さ
れる。従って、変調デコーダ１５５、チャネルデコーダ
１６０はノイズとともに変調データストリーム１４５を
受信し、周知な方法で、チャネルエンコーダ１３０、変
調エンコーダ１４０の符号化プロセスをそれぞれ逆にた
どる。チャネルデコーダ１６０からのデータストリーム
はコンプレッサ１２０が生成する圧縮データ１２５に対
応する。図７、１１に関連して詳細に説明するように本
発明に従って、このデータストリームはデコンプレッサ
１６５により脱圧縮され、データデコーダ１７０により
デコードされ、出力データストリーム１７５を作る。
ームの伝送や記録時にチャネル／媒体１５０にて投入さ
れる。従って、変調デコーダ１５５、チャネルデコーダ
１６０はノイズとともに変調データストリーム１４５を
受信し、周知な方法で、チャネルエンコーダ１３０、変
調エンコーダ１４０の符号化プロセスをそれぞれ逆にた
どる。チャネルデコーダ１６０からのデータストリーム
はコンプレッサ１２０が生成する圧縮データ１２５に対
応する。図７、１１に関連して詳細に説明するように本
発明に従って、このデータストリームはデコンプレッサ
１６５により脱圧縮され、データデコーダ１７０により
デコードされ、出力データストリーム１７５を作る。
【００２８】本発明の多くの原理は、圧縮による相当な
削減や伝送効率を実現することに関連している。図２
は、本発明に従ってデータを圧縮する動作を示す流れ図
であり、図１のシステムにて有用である。入力データス
トリーム（例えば、テキストファイル）が受信される
（２１０）。特定の圧縮ブロックサイズ「ｂ」が選択さ
れる（２２０）。このｂは特定の文字の数である。好ま
しい実施例に従って、ｂは２０〜１０００文字の範囲で
選択される。入力データストリームはサイズｂのブロッ
ク群に分割される（２３０）。その後に、本発明に従っ
て、ブロック群の各ブロックに対しフィンガプリントが
計算され格納される（２４０）。
削減や伝送効率を実現することに関連している。図２
は、本発明に従ってデータを圧縮する動作を示す流れ図
であり、図１のシステムにて有用である。入力データス
トリーム（例えば、テキストファイル）が受信される
（２１０）。特定の圧縮ブロックサイズ「ｂ」が選択さ
れる（２２０）。このｂは特定の文字の数である。好ま
しい実施例に従って、ｂは２０〜１０００文字の範囲で
選択される。入力データストリームはサイズｂのブロッ
ク群に分割される（２３０）。その後に、本発明に従っ
て、ブロック群の各ブロックに対しフィンガプリントが
計算され格納される（２４０）。
【００２９】好ましい実施例に従って、文献、Karp et
al., supra. に記載された技術に従ってフィンガプリン
トが計算される。カープらはストリング検索を支援する
のにフィンガプリントを元々用いた。すなわち、長さｎ
のストリングが長さｍのサーチパターンを含むかどうか
である。カープらはサーチパターンのｍの文字をポリノ
ミアルモジュロ（多項式法処理）した大きな素数として
解釈した。従って、得られるフィンガプリントは、例え
ば、３２ビットワードとして格納することができる。カ
ープの技術は入力ストリングを走査し、長さｍのｎ−ｍ
＋１のサブストリングのそれぞれに対し同じフィンガプ
リントを計算する。もしこれらフィンガプリントがマッ
チしなければ、そのサブストリングはパターンにマッチ
しないという結論を出す。もしそれらフィンガプリント
がマッチすれば、そのサブストリングは実際にはパター
ンにマッチするかどうかの更なるチェックを行う。
al., supra. に記載された技術に従ってフィンガプリン
トが計算される。カープらはストリング検索を支援する
のにフィンガプリントを元々用いた。すなわち、長さｎ
のストリングが長さｍのサーチパターンを含むかどうか
である。カープらはサーチパターンのｍの文字をポリノ
ミアルモジュロ（多項式法処理）した大きな素数として
解釈した。従って、得られるフィンガプリントは、例え
ば、３２ビットワードとして格納することができる。カ
ープの技術は入力ストリングを走査し、長さｍのｎ−ｍ
＋１のサブストリングのそれぞれに対し同じフィンガプ
リントを計算する。もしこれらフィンガプリントがマッ
チしなければ、そのサブストリングはパターンにマッチ
しないという結論を出す。もしそれらフィンガプリント
がマッチすれば、そのサブストリングは実際にはパター
ンにマッチするかどうかの更なるチェックを行う。
【００３０】カープらの技術は以下のようなフィンガプ
リントの幾つかの有用な特性を証明した。すなわち、 （１）フィンガプリントを迅速に計算することができる
こと。すなわち、フィンガプリントをＯ（ｍ）の時間で
初期化することができ、Ｏ（１）の時間である位置をス
ライドすることにより更新することができること。 （２）フィンガプリントは偽のマッチを得ること。すな
わち、等しくないストリングは等しくないフィンガプリ
ントを持つことが非常に確かであること。（２つの等し
くないストリングが同じ３２ビットフィンガプリントを
有する確率は約２-32である。） （３）大きな素数をランダムで選ぶことができ、テキス
トストリング検索においてランダム化したアルゴリスム
を得ることができること。
リントの幾つかの有用な特性を証明した。すなわち、 （１）フィンガプリントを迅速に計算することができる
こと。すなわち、フィンガプリントをＯ（ｍ）の時間で
初期化することができ、Ｏ（１）の時間である位置をス
ライドすることにより更新することができること。 （２）フィンガプリントは偽のマッチを得ること。すな
わち、等しくないストリングは等しくないフィンガプリ
ントを持つことが非常に確かであること。（２つの等し
くないストリングが同じ３２ビットフィンガプリントを
有する確率は約２-32である。） （３）大きな素数をランダムで選ぶことができ、テキス
トストリング検索においてランダム化したアルゴリスム
を得ることができること。
【００３１】我々は、繰り返しストリングを有する非常
に大きな入力データストリームに対し増強したデータ圧
縮を行うようなエレガントな圧縮ツールを導入すること
によってフィンガプリントを用いることを認識した。本
発明に従うと、全体の記憶容量の必要条件の余り増加さ
せないで長いコモンストリングを識別して入力データの
大きな履歴を調べることができる。すなわち、本発明に
従って、異なるストリングの間の相関を認識するデータ
圧縮構成を用いる。具体的には、特定のテキストストリ
ングの第２出現を繰り返しとして認識し、この第２出現
を符号化した第１ストリングへの参照によって置き換え
る。従って、本発明に従うと、多くの圧縮方法に対し大
きな圧縮比を実現することができる。
に大きな入力データストリームに対し増強したデータ圧
縮を行うようなエレガントな圧縮ツールを導入すること
によってフィンガプリントを用いることを認識した。本
発明に従うと、全体の記憶容量の必要条件の余り増加さ
せないで長いコモンストリングを識別して入力データの
大きな履歴を調べることができる。すなわち、本発明に
従って、異なるストリングの間の相関を認識するデータ
圧縮構成を用いる。具体的には、特定のテキストストリ
ングの第２出現を繰り返しとして認識し、この第２出現
を符号化した第１ストリングへの参照によって置き換え
る。従って、本発明に従うと、多くの圧縮方法に対し大
きな圧縮比を実現することができる。
【００３２】特定の圧縮方式におけるストリング繰り返
しの認識は知られている。例えば、文献、J. G. Cleary
et al., "Unbounded length contexts for PPM", Comp
uterJournal 40,2/3, pp. 67-75, 1997、 C. G. Nevill
e-Manning et al., "A space-economical suffix tree
construction algorithm", Journal of ArtificialInte
lligence Research, pp. 67-82, September 1997にはス
トリング繰り返しを認識している特定の圧縮方式を記載
している。しかし、本発明とは対照的にこれらの従来の
方式は大きな量のメモリーを必要とする。すなわち、フ
ィンガプリントを用いない方法において、ｎ文字のファ
イルを処理をするのに約ｎのワードを主メモリーに必要
とする。下で議論するように、記憶条件の必要条件を激
的に増加せずに本発明に従うと大きな圧縮比を実現する
ことができる。
しの認識は知られている。例えば、文献、J. G. Cleary
et al., "Unbounded length contexts for PPM", Comp
uterJournal 40,2/3, pp. 67-75, 1997、 C. G. Nevill
e-Manning et al., "A space-economical suffix tree
construction algorithm", Journal of ArtificialInte
lligence Research, pp. 67-82, September 1997にはス
トリング繰り返しを認識している特定の圧縮方式を記載
している。しかし、本発明とは対照的にこれらの従来の
方式は大きな量のメモリーを必要とする。すなわち、フ
ィンガプリントを用いない方法において、ｎ文字のファ
イルを処理をするのに約ｎのワードを主メモリーに必要
とする。下で議論するように、記憶条件の必要条件を激
的に増加せずに本発明に従うと大きな圧縮比を実現する
ことができる。
【００３３】図２において、好ましい実施例に従うと、
各ブロックに対し計算したフィンガプリントを格納する
（２４０）。入力ストリームの各ブロック境界にてフィ
ンガプリントが記録される。また、プライマリデータ構
造がｂバイトの重なり合わないブロックのそれぞれのフ
ィンガプリントを記憶する。すなわち、好ましい実施例
に従うと、各バイト１...ｂ、ｂ＋１...２ｂ、２ｂ＋
１...３ｂ等々のようにフィンガプリントが記憶され
る。
各ブロックに対し計算したフィンガプリントを格納する
（２４０）。入力ストリームの各ブロック境界にてフィ
ンガプリントが記録される。また、プライマリデータ構
造がｂバイトの重なり合わないブロックのそれぞれのフ
ィンガプリントを記憶する。すなわち、好ましい実施例
に従うと、各バイト１...ｂ、ｂ＋１...２ｂ、２ｂ＋
１...３ｂ等々のようにフィンガプリントが記憶され
る。
【００３４】好ましい実施例に従うと、約ｎ／ｂのフィ
ンガプリントが記憶される。このｎは上述のストリング
の長さである。本発明に従うと、元の入力ストリームの
少ない割合のみが記憶され、従って、記憶装置の必要条
件を低く押さえることができる。また、好ましい実施例
に従うと、入力データストリームにおけるそのシーケン
スの位置を表す正数と共にお互いをハッシュテーブル
（周知なデータ構造）にてフィンガプリントを記憶し表
現する。
ンガプリントが記憶される。このｎは上述のストリング
の長さである。本発明に従うと、元の入力ストリームの
少ない割合のみが記憶され、従って、記憶装置の必要条
件を低く押さえることができる。また、好ましい実施例
に従うと、入力データストリームにおけるそのシーケン
スの位置を表す正数と共にお互いをハッシュテーブル
（周知なデータ構造）にてフィンガプリントを記憶し表
現する。
【００３５】図３は、図２の動作によって計算されたフ
ィンガプリントを記憶するデータ構造３００を示す。デ
ータ構造３００は入力ストリームの各ブロックを記憶す
る。例えば、ブロック１〜ｍはブロック３０５〜３２５
として示した。それに加え、各ブロックに対し、計算し
たフィンガプリントを記憶する。例えば、図３において
ＦＰ１〜ＦＰｍをフィンガプリント３３０〜３５０とし
て示した。更に、下で述べるように、入力データストリ
ーム（データ構成３００）を横断するのにスライディン
グウィンドウ３５５を用い、上述のマッチを検出するの
に現在の文字のウィンドウを記憶されたフィンガプリン
トと比較する。
ィンガプリントを記憶するデータ構造３００を示す。デ
ータ構造３００は入力ストリームの各ブロックを記憶す
る。例えば、ブロック１〜ｍはブロック３０５〜３２５
として示した。それに加え、各ブロックに対し、計算し
たフィンガプリントを記憶する。例えば、図３において
ＦＰ１〜ＦＰｍをフィンガプリント３３０〜３５０とし
て示した。更に、下で述べるように、入力データストリ
ーム（データ構成３００）を横断するのにスライディン
グウィンドウ３５５を用い、上述のマッチを検出するの
に現在の文字のウィンドウを記憶されたフィンガプリン
トと比較する。
【００３６】より詳細には、図２において、入力データ
ストリームを横断し、入力文字と記憶されたフィンガプ
リントの間に比較を行い（２５０）、マッチを検出する
（２６０）。すなわち、入力データストリームを横断す
るのにスライディングウィンドウ（例えば、スライディ
ングウィンドウ３５５）を用い、現在の文字のウィンド
ウに対していわゆる「中間(interim)」フィンガプリン
トを計算する。これは図においては現在の文字のウィン
ドウで文字毎のベースで行われている。
ストリームを横断し、入力文字と記憶されたフィンガプ
リントの間に比較を行い（２５０）、マッチを検出する
（２６０）。すなわち、入力データストリームを横断す
るのにスライディングウィンドウ（例えば、スライディ
ングウィンドウ３５５）を用い、現在の文字のウィンド
ウに対していわゆる「中間(interim)」フィンガプリン
トを計算する。これは図においては現在の文字のウィン
ドウで文字毎のベースで行われている。
【００３７】これら現在の文字のウィンドウにわたって
計算される中間フィンガプリントはマッチを検出するた
めに格納フィンガプリントと比較される。具体的には、
入力テキストを走査するに従って、コモンフィンガプリ
ントを見つけるためにハッシュテーブルが用いられ、コ
モンストリングの位置を判断する。もしマッチが出現す
れば、シーケンス「<start, length>」を用いてそのマ
ッチを符号化する（２７０）。ここで、startは初期位
置であり、lengthはコモンシーケンスのサイズである。
計算される中間フィンガプリントはマッチを検出するた
めに格納フィンガプリントと比較される。具体的には、
入力テキストを走査するに従って、コモンフィンガプリ
ントを見つけるためにハッシュテーブルが用いられ、コ
モンストリングの位置を判断する。もしマッチが出現す
れば、シーケンス「<start, length>」を用いてそのマ
ッチを符号化する（２７０）。ここで、startは初期位
置であり、lengthはコモンシーケンスのサイズである。
【００３８】例えば、以下の入力データストリームを考
えてみる。 The Constitution of the United States, PREAMBLE W
e, the people of theUnited States, in order to for
m a more perfect union... 上述のような本発明の原理を適用すると、以下の符号化
データストリームの結果を得ることができる。 The Constitution of the United States, PREAMBLE W
e, the people <16,21>, in order to form a more per
fect union... この符号化データストリームから、繰り返しストリング
は"the people of theUnited States"は上述のように本
発明の"<start, length>"シーケンスフォーマットを用
いる識別子で符号化されていることがわかる。
えてみる。 The Constitution of the United States, PREAMBLE W
e, the people of theUnited States, in order to for
m a more perfect union... 上述のような本発明の原理を適用すると、以下の符号化
データストリームの結果を得ることができる。 The Constitution of the United States, PREAMBLE W
e, the people <16,21>, in order to form a more per
fect union... この符号化データストリームから、繰り返しストリング
は"the people of theUnited States"は上述のように本
発明の"<start, length>"シーケンスフォーマットを用
いる識別子で符号化されていることがわかる。
【００３９】好ましい実施例に従うと、マッチするフィ
ンガプリントを有するブロックがいわゆる偽マッチでは
ないことを確実にするため、可能な限りであるが長さが
ｂ−１文字よりも長くない範囲で、（入力データストリ
ームにわたって）逆方向および順方向でマッチの拡張を
行う。もし幾つかのブロックが現フィンガプリントとマ
ッチすれば、そのようなブロックの中での最大のマッチ
が本発明に従って符号化される。
ンガプリントを有するブロックがいわゆる偽マッチでは
ないことを確実にするため、可能な限りであるが長さが
ｂ−１文字よりも長くない範囲で、（入力データストリ
ームにわたって）逆方向および順方向でマッチの拡張を
行う。もし幾つかのブロックが現フィンガプリントとマ
ッチすれば、そのようなブロックの中での最大のマッチ
が本発明に従って符号化される。
【００４０】フィンガプリントに対しての入力文字（中
間フィンガプリント）の比較は入力ストリームの終わり
に到達するまで継続する（２８０）。その後に、符号化
データストリーム（本発明に従って符号化された元の入
力データストリーム）が周知の圧縮アルゴリズムのいず
れか（例えば、Lempel-Ziv圧縮）を圧縮される（２９
０）。
間フィンガプリント）の比較は入力ストリームの終わり
に到達するまで継続する（２８０）。その後に、符号化
データストリーム（本発明に従って符号化された元の入
力データストリーム）が周知の圧縮アルゴリズムのいず
れか（例えば、Lempel-Ziv圧縮）を圧縮される（２９
０）。
【００４１】以下の準コードは、上述のような本発明の
原理に従うフィンガプリントの比較および符号化を記し
たものである。変数fpは、フィンガプリントを表し、関
数checkformatchはハッシュテーブルにおけるフィンガ
プリントをルックアップし、マッチを見つければそのマ
ッチを符号化する。 コード１ initialize fp for(i=b; i<n; i++) if(i%b == 0) store(fp, i) a[i]を含みa[i-b]を含まないようにfpを更新 checkformatch(fp, i)
原理に従うフィンガプリントの比較および符号化を記し
たものである。変数fpは、フィンガプリントを表し、関
数checkformatchはハッシュテーブルにおけるフィンガ
プリントをルックアップし、マッチを見つければそのマ
ッチを符号化する。 コード１ initialize fp for(i=b; i<n; i++) if(i%b == 0) store(fp, i) a[i]を含みa[i-b]を含まないようにfpを更新 checkformatch(fp, i)
【００４２】上の準コードは、本発明を実装するプロセ
ッサにおける実行をするために、多くのプログラム（例
えば、Ｃ言語プログラム）にて開発するのに用いること
ができる。例えば、図９〜１０は、本発明に従ってデー
タ圧縮するＣ言語ソースプログラム９００を示す。ソー
スプログラム９００は、このソースコードプログラム９
００全体で用いる特定のデータ型、変数、データ構造を
規定するプログラム命令を含むプログラムソースコード
部分９１０を含む。
ッサにおける実行をするために、多くのプログラム（例
えば、Ｃ言語プログラム）にて開発するのに用いること
ができる。例えば、図９〜１０は、本発明に従ってデー
タ圧縮するＣ言語ソースプログラム９００を示す。ソー
スプログラム９００は、このソースコードプログラム９
００全体で用いる特定のデータ型、変数、データ構造を
規定するプログラム命令を含むプログラムソースコード
部分９１０を含む。
【００４３】プログラムソースコード部分９２０は、上
述のように本発明に従ってストリングマッチング動作を
実装するプログラム命令を含む。プログラムソースコー
ド部分９３０は、上述のように本発明に従って計算され
たフィンガプリントを格納するのに用いるハッシュテー
ブルデータ構造を定め構築するのを支援するプログラム
命令である。プログラムソースコード部分９４０、９５
０（図１０）は、上述のように本発明に従って符号化デ
ータファイルを作るために圧縮を完成させるプログラム
命令を含む。
述のように本発明に従ってストリングマッチング動作を
実装するプログラム命令を含む。プログラムソースコー
ド部分９３０は、上述のように本発明に従って計算され
たフィンガプリントを格納するのに用いるハッシュテー
ブルデータ構造を定め構築するのを支援するプログラム
命令である。プログラムソースコード部分９４０、９５
０（図１０）は、上述のように本発明に従って符号化デ
ータファイルを作るために圧縮を完成させるプログラム
命令を含む。
【００４４】Ｃ言語ソースプログラム９００は、生来的
に例示的であり本発明を理解するのを支援するために表
現してある。本発明を具現化する他のプログラムを本発
明の範囲から外れずに開発することは当業者であればで
きるであろう。
に例示的であり本発明を理解するのを支援するために表
現してある。本発明を具現化する他のプログラムを本発
明の範囲から外れずに開発することは当業者であればで
きるであろう。
【００４５】上述の本発明の多くの原理を更に説明する
ため、図４は、一連の短い非圧縮入力データストリーム
４００を、本発明に従って符号化された対応する一連の
符号化出力データストリーム４１０と共に示してある。
図４を調べることにより、入力データストリーム４２０
〜４５０はそれぞれ、符号化出力４６０〜４９０それぞ
れに示すようにマッチングストリングの符号化された表
現によって処理されている。
ため、図４は、一連の短い非圧縮入力データストリーム
４００を、本発明に従って符号化された対応する一連の
符号化出力データストリーム４１０と共に示してある。
図４を調べることにより、入力データストリーム４２０
〜４５０はそれぞれ、符号化出力４６０〜４９０それぞ
れに示すようにマッチングストリングの符号化された表
現によって処理されている。
【００４６】また、図５、６には本発明を更に説明する
ために、大きな入力データファイル、具体的には、アメ
リカ合衆国の憲法に対する本発明の原理の適用を示して
いる。図５は、憲法の選択部分からなる入力データファ
イル５００を示している。本発明に従う憲法のテキスト
の圧縮は、同じ長いストリングが頻繁に現れることを考
えると特に本発明の利点を発揮できる。例えば、入力デ
ータファイル５００のテキスト部分５１０、５２０、５
３０は幾つかの長い繰り返すストリングを含む。
ために、大きな入力データファイル、具体的には、アメ
リカ合衆国の憲法に対する本発明の原理の適用を示して
いる。図５は、憲法の選択部分からなる入力データファ
イル５００を示している。本発明に従う憲法のテキスト
の圧縮は、同じ長いストリングが頻繁に現れることを考
えると特に本発明の利点を発揮できる。例えば、入力デ
ータファイル５００のテキスト部分５１０、５２０、５
３０は幾つかの長い繰り返すストリングを含む。
【００４７】従って、上述の本発明の多くの原理を適用
すると、図６に示した符号化データファイル６００を得
る。６００は符号化部分６１０、６２０、６３０を有
し、これらそれぞれは入力データファイル５００のテキ
スト部分５１０、５２０、５３０に対応する。符号化部
分６１０、６２０、６３０はそれぞれ、エンコーディン
グ（例えば、エンコーディング６３５−６９０）を含
む。これらは、本発明に従って導かれ、ブロックサイズ
＝２０を用い、更に圧縮比を増しデータ伝送レートをよ
り効率的にするために更に圧縮させることができる。
すると、図６に示した符号化データファイル６００を得
る。６００は符号化部分６１０、６２０、６３０を有
し、これらそれぞれは入力データファイル５００のテキ
スト部分５１０、５２０、５３０に対応する。符号化部
分６１０、６２０、６３０はそれぞれ、エンコーディン
グ（例えば、エンコーディング６３５−６９０）を含
む。これらは、本発明に従って導かれ、ブロックサイズ
＝２０を用い、更に圧縮比を増しデータ伝送レートをよ
り効率的にするために更に圧縮させることができる。
【００４８】例えば、エンコーディング６３５は、文字
位置３９１に始まる４７文字のマッチングシーケンス
（すなわち、マッチングストリング）が検出され符号化
されたことを示す。同様に、例えば、エンコーディング
６７５は、文字位置２４３９に始まる１０３文字のマッ
チングシーケンスが検出され符号化されたことを示す。
位置３９１に始まる４７文字のマッチングシーケンス
（すなわち、マッチングストリング）が検出され符号化
されたことを示す。同様に、例えば、エンコーディング
６７５は、文字位置２４３９に始まる１０３文字のマッ
チングシーケンスが検出され符号化されたことを示す。
【００４９】圧縮プロセスを適用する前に入力データの
初期評価（プリプロセス）においてフィンガプリントを
用いることを認識することにより、入力データストリー
ムの長い履歴および長いコモンストリングを用いること
に基づいて比較的低い圧縮比を実現することができる。
重要なことに、本発明は記憶装置の必要条件を余り増加
させず、いずれの特定の圧縮技術にも依存しない。すな
わち、本発明は、相当な圧縮比を実現する多様な周知の
圧縮アルゴリズムを用い、記憶装置の必要条件や転送時
間を減らすことができる。
初期評価（プリプロセス）においてフィンガプリントを
用いることを認識することにより、入力データストリー
ムの長い履歴および長いコモンストリングを用いること
に基づいて比較的低い圧縮比を実現することができる。
重要なことに、本発明は記憶装置の必要条件を余り増加
させず、いずれの特定の圧縮技術にも依存しない。すな
わち、本発明は、相当な圧縮比を実現する多様な周知の
圧縮アルゴリズムを用い、記憶装置の必要条件や転送時
間を減らすことができる。
【００５０】圧縮テスト結果を記す前に、本発明を用い
て得られる符号化データファイルの脱圧縮を議論する。
図７は、本発明の更なる原理に従ってデータを脱圧縮す
る動作７００の流れ図である。本発明による符号化デー
タファイル（例えば、符号化データファイル６００）か
ら、この態様では文字毎のベースで個々の文字「ｃ」を
取り出す（７１０）。
て得られる符号化データファイルの脱圧縮を議論する。
図７は、本発明の更なる原理に従ってデータを脱圧縮す
る動作７００の流れ図である。本発明による符号化デー
タファイル（例えば、符号化データファイル６００）か
ら、この態様では文字毎のベースで個々の文字「ｃ」を
取り出す（７１０）。
【００５１】特定の文字ｃがシンボル「＜」とマッチす
るかどうかの判断を行う（７２０）。マッチしなけれ
ば、脱圧縮プロセスに従って出力ファイルへと文字ｃが
書き込まれ（７３０）、符号化データファイルから次の
文字が取り出される。マッチすれば、符号化データファ
イルから次の文字が取り出される（７４０）。再び、特
定の文字ｃがシンボル「＜」とマッチするかどうかの判
断をする（７５０）。マッチすれば、出力ファイルにシ
ンボル「＜」が書き込まれ（７６０）、次の文字が取り
出される。マッチしなければ、上で詳細に示した「<sta
rt, length>」エンコーディングが符号化ファイルから
読み取られる（７７０）。
るかどうかの判断を行う（７２０）。マッチしなけれ
ば、脱圧縮プロセスに従って出力ファイルへと文字ｃが
書き込まれ（７３０）、符号化データファイルから次の
文字が取り出される。マッチすれば、符号化データファ
イルから次の文字が取り出される（７４０）。再び、特
定の文字ｃがシンボル「＜」とマッチするかどうかの判
断をする（７５０）。マッチすれば、出力ファイルにシ
ンボル「＜」が書き込まれ（７６０）、次の文字が取り
出される。マッチしなければ、上で詳細に示した「<sta
rt, length>」エンコーディングが符号化ファイルから
読み取られる（７７０）。
【００５２】この態様に従うと、<start, length>情報
を用いて、「start」位置から始まり「length」情報と
等しい長さを有する符号化ファイルから出力ファイルへ
とストリングがコピーされる（７８０）。すなわち、本
発明に従って前に符号化されたマッチングストリングが
それ全体で脱圧縮され出力ファイルへと書き込まれる。
文字が残っていれば（７９０）、脱圧縮プロセスは継続
する。残っていなければ、脱圧縮プロセスは完了し出力
ファイルを完成させる。
を用いて、「start」位置から始まり「length」情報と
等しい長さを有する符号化ファイルから出力ファイルへ
とストリングがコピーされる（７８０）。すなわち、本
発明に従って前に符号化されたマッチングストリングが
それ全体で脱圧縮され出力ファイルへと書き込まれる。
文字が残っていれば（７９０）、脱圧縮プロセスは継続
する。残っていなければ、脱圧縮プロセスは完了し出力
ファイルを完成させる。
【００５３】本発明の脱圧縮プロセスは、コンピュー
タ、プロセッサ、ＤＳＰ等で実行させることができる。
図１１は、図７に示した本発明に従うデータを脱圧縮す
る動作を実装するＣ言語ソースコードプログラム１１０
０を示す。ソースコードプログラム部分１１００は符号
化データファイルおよびそこに含まれる個々の文字を操
作する配列を定める。部分１１２０は文字を処理するプ
ログラムの主要部分を実行し、符号化ファイルを脱圧縮
して出力ファイルを作る。
タ、プロセッサ、ＤＳＰ等で実行させることができる。
図１１は、図７に示した本発明に従うデータを脱圧縮す
る動作を実装するＣ言語ソースコードプログラム１１０
０を示す。ソースコードプログラム部分１１００は符号
化データファイルおよびそこに含まれる個々の文字を操
作する配列を定める。部分１１２０は文字を処理するプ
ログラムの主要部分を実行し、符号化ファイルを脱圧縮
して出力ファイルを作る。
【００５４】Ｃ言語ソースコードプログラム１１００は
生来的に例示的であり、本発明の理解を深めるために記
した。本発明の原理を実装する他のプログラムを本発明
の範囲を外れずに当業者は容易に作ることができるであ
ろう。
生来的に例示的であり、本発明の理解を深めるために記
した。本発明の原理を実装する他のプログラムを本発明
の範囲を外れずに当業者は容易に作ることができるであ
ろう。
【００５５】本発明の多くの原理および利点を説明する
ため、非常に大きなファイルに関連して本発明を適用
し、そのファイルの圧縮の多くの結果を比較した。サン
プルとしては、周知のＣＤ−ＲＯＭで"Project Gutenbe
rg Compact Disc", Walnut Creek CDROM, Walnut Cree
k, CA に含まれる全てのテキストファイルを連結させて
用いた。このＣＤ−ＲＯＭには１９９４の文書が含まれ
ている。この試験のため、我々は周知のＵＮＩＸ（登録
商標）の「cat」コマンドを用いて全てのテキストファ
イルを連結した。具体的なＵＮＩＸコマンド文字列は、
「cat */*.txt > gut94all.txt」であった。このように
連結することにより、６６１２２MBytesの入力ファイル
を得て、これに本発明の原理を適用した。
ため、非常に大きなファイルに関連して本発明を適用
し、そのファイルの圧縮の多くの結果を比較した。サン
プルとしては、周知のＣＤ−ＲＯＭで"Project Gutenbe
rg Compact Disc", Walnut Creek CDROM, Walnut Cree
k, CA に含まれる全てのテキストファイルを連結させて
用いた。このＣＤ−ＲＯＭには１９９４の文書が含まれ
ている。この試験のため、我々は周知のＵＮＩＸ（登録
商標）の「cat」コマンドを用いて全てのテキストファ
イルを連結した。具体的なＵＮＩＸコマンド文字列は、
「cat */*.txt > gut94all.txt」であった。このように
連結することにより、６６１２２MBytesの入力ファイル
を得て、これに本発明の原理を適用した。
【００５６】図８は、連結した当該テキストファイルを
圧縮した結果の比較８００を示す。ファイルサイズはMB
yteで示してあり、圧縮による元ファイルと割合をパー
セントで示した。ブロックサイズｂ（８１０）を変化さ
せた効果を比較した。「comb」の見出しを有する列８２
０は、本発明を適用した効果を示してあり、入力テキス
トファイルのサイズの変化を示してある。「com %」の
見出しを有する列８３０は、ブロックサイズを変化させ
て調べた圧縮パーセンテージを示す。
圧縮した結果の比較８００を示す。ファイルサイズはMB
yteで示してあり、圧縮による元ファイルと割合をパー
セントで示した。ブロックサイズｂ（８１０）を変化さ
せた効果を比較した。「comb」の見出しを有する列８２
０は、本発明を適用した効果を示してあり、入力テキス
トファイルのサイズの変化を示してある。「com %」の
見出しを有する列８３０は、ブロックサイズを変化させ
て調べた圧縮パーセンテージを示す。
【００５７】「com b｜gzip」の見出しを有する列８４
０および「com|gzip %」の見出しを有する列８５０は、
本発明の原理と組み合わせて周知の「gzip」圧縮アルゴ
リズム（周知のＧＮＵによるＬＺ７７の実装であるgzi
p）を適用した結果を示す。「com|gzip %」（８５０）
は、列８２０のサイズに対する列８４０の割合を示す。
例えば、線のブロックサイズを用い本発明と組み合わせ
てgzipを適用すると、元のファイルパーセントを１９．
７％の割合で減らすことができた。図よりブロックサイ
ズｂが減ると、最適でない点（効率的な圧縮にはブロッ
クサイズが小さすぎる）に到達するまで圧縮の度合いは
増えている。また、「total %」の見出しを有する列８
６０は、元のファイルと比較した列８４０の割合を示し
てあり、ｂの最適な選択は、comがgzipのファイルサイ
ズの減少量を超えて２２．５％のファイルサイズの減少
量となっているところの３１MByteである。
０および「com|gzip %」の見出しを有する列８５０は、
本発明の原理と組み合わせて周知の「gzip」圧縮アルゴ
リズム（周知のＧＮＵによるＬＺ７７の実装であるgzi
p）を適用した結果を示す。「com|gzip %」（８５０）
は、列８２０のサイズに対する列８４０の割合を示す。
例えば、線のブロックサイズを用い本発明と組み合わせ
てgzipを適用すると、元のファイルパーセントを１９．
７％の割合で減らすことができた。図よりブロックサイ
ズｂが減ると、最適でない点（効率的な圧縮にはブロッ
クサイズが小さすぎる）に到達するまで圧縮の度合いは
増えている。また、「total %」の見出しを有する列８
６０は、元のファイルと比較した列８４０の割合を示し
てあり、ｂの最適な選択は、comがgzipのファイルサイ
ズの減少量を超えて２２．５％のファイルサイズの減少
量となっているところの３１MByteである。
【００５８】本明細書における説明は単に本発明の原理
の例を示したのみである。当業者は、本発明の範囲を外
れずに多くの構成を変えずに本明細書が開示することに
基づいて多くの構成を考えることができるであろう。特
許請求範囲の記載において特定の機能を実行する手段と
して表現したいずれの要素も、その機能を実行するいず
れの機能をも表すように意図してある。例えば、（ａ）
その機能を実行する回路要素の組み合わせ、あるいは
（ｂ）その機能を実行するためソフトウェアを実行する
適切な回路と組合わさるいずれの形態におけるソフトウ
ェア（従って、ファームウェア、オブジェクトコード、
マイクロコード等をも含む。）を含む。
の例を示したのみである。当業者は、本発明の範囲を外
れずに多くの構成を変えずに本明細書が開示することに
基づいて多くの構成を考えることができるであろう。特
許請求範囲の記載において特定の機能を実行する手段と
して表現したいずれの要素も、その機能を実行するいず
れの機能をも表すように意図してある。例えば、（ａ）
その機能を実行する回路要素の組み合わせ、あるいは
（ｂ）その機能を実行するためソフトウェアを実行する
適切な回路と組合わさるいずれの形態におけるソフトウ
ェア（従って、ファームウェア、オブジェクトコード、
マイクロコード等をも含む。）を含む。
【図１】本発明に従ってデータを圧縮し展開するシステ
ム。
ム。
【図２】本発明に従ってデータを圧縮する動作の流れ
図。これは図１のシステムにて有用である。
図。これは図１のシステムにて有用である。
【図３】図２の動作に従って計算された入力データスト
リームやフィンガプリントを記憶するデータ構造の例。
リームやフィンガプリントを記憶するデータ構造の例。
【図４】本発明に従って符号化された一連の符号化デー
タストリームとともに一連の非圧縮データストリームを
示す。
タストリームとともに一連の非圧縮データストリームを
示す。
【図５】入力データファイルの選択部分。
【図６】本発明の原理に従って図５の入力データファイ
ルから符号化された符号化データファイルの選択部分。
ルから符号化された符号化データファイルの選択部分。
【図７】本発明に従い展開する動作の流れ図。
【図８】本発明に従ってテキストファイルを圧縮した圧
縮結果。
縮結果。
【図９】図２に示すように本発明に従ってデータを圧縮
するＣ言語ソースコードプログラム。
するＣ言語ソースコードプログラム。
【図１０】図９と同様。
【図１１】図７に示すように本発明に従ってデータを展
開するＣ言語プログラム。
開するＣ言語プログラム。
１０５ 入力データストリーム １１０ 入力データエンコーダ １１５ 符号化入力データストリーム １２０ コンプレッサ １２５ 圧縮データ １３０ チャネルエンコーダ １３５ チャネル符号化された情報 １４０ 変調エンコーダ １４５ 変調データストリーム １５０ 媒体 １５５ 変調デコーダ １６０ チャネルデコーダ １６５ デコンプレッサ １７０ データデコーダ １７５ 出力データストリーム ２１０ 入力データストリームを受信 ２２０ 圧縮ブロックサイズ「ｂ」を選択 ２３０ 入力データストリームをサイズ「ｂ」ブロック
群に分割 ２４０ 各ブロックに対しフィンガプリントを計算し格
納する ２５０ 入力データストリームを横断し、キャラクタベ
ースでフィンガプリントを計算し格納されたフィンガプ
リントと比較 ２６０ マッチするか？ ２７０ マッチを符号化 ２８０ 入力データストリームの終わりか？ ２９０ 符号化された入力データストリームに圧縮を適
用 ３９１、２４３９ 文字位置 ４１０ 符号化出力データストリーム ４００、４２０〜４５０ 入力データストリーム ４６０〜４９０ 符号化出力 ５００ 入力データファイル ５１０、５２０、５３０ テキスト部分 ６００ 符号化データファイル ６１０、６２０、６３０ 符号化部分 ６３５ エンコーディング ７１０ 符号化データファイルから文字「ｃ」を取り出
す ７３０ 出力ファイルに文字「ｃ」を書き込む ７４０ 次の文字に進む。 「ｃ＝次の文字」 ７６０ 出力ファイルに「＜」を書き込む ７７０ 符号化データファイルから<start,length>エン
コーディングを読み取る ７８０ start位置からlengthの長さのストリングを出
力ファイルにコピーする ７９０ まだ「ｃ」はあるか？ ９００ ソースプログラム ９１０、９２０、９３０、９４０、９５０ プログラム
ソースコード部分 １１００ ソースコードプログラム部分 １１２０ 部分
群に分割 ２４０ 各ブロックに対しフィンガプリントを計算し格
納する ２５０ 入力データストリームを横断し、キャラクタベ
ースでフィンガプリントを計算し格納されたフィンガプ
リントと比較 ２６０ マッチするか？ ２７０ マッチを符号化 ２８０ 入力データストリームの終わりか？ ２９０ 符号化された入力データストリームに圧縮を適
用 ３９１、２４３９ 文字位置 ４１０ 符号化出力データストリーム ４００、４２０〜４５０ 入力データストリーム ４６０〜４９０ 符号化出力 ５００ 入力データファイル ５１０、５２０、５３０ テキスト部分 ６００ 符号化データファイル ６１０、６２０、６３０ 符号化部分 ６３５ エンコーディング ７１０ 符号化データファイルから文字「ｃ」を取り出
す ７３０ 出力ファイルに文字「ｃ」を書き込む ７４０ 次の文字に進む。 「ｃ＝次の文字」 ７６０ 出力ファイルに「＜」を書き込む ７７０ 符号化データファイルから<start,length>エン
コーディングを読み取る ７８０ start位置からlengthの長さのストリングを出
力ファイルにコピーする ７９０ まだ「ｃ」はあるか？ ９００ ソースプログラム ９１０、９２０、９３０、９４０、９５０ プログラム
ソースコード部分 １１００ ソースコードプログラム部分 １１２０ 部分
───────────────────────────────────────────────────── フロントページの続き (71)出願人 596077259 600 Ｍｏｕｎｔａｉｎ Ａｖｅｎｕｅ, Ｍｕｒｒａｙ Ｈｉｌｌ， Ｎｅｗ Ｊｅ ｒｓｅｙ 07974−0636Ｕ．Ｓ．Ａ. (72)発明者 ジョン ルイス ベントリー アメリカ合衆国、07974 ニュージャージ ー、ニュープロビデンス、セントラル ア ベニュー 449，アパートメント ２ (72)発明者 マルコルム ダグラス マクローイ アメリカ合衆国、03750 ニューハンプシ ャー、エトナ、ヘイフィールド ロード １
Claims (38)
- 【請求項１】 入力データストリームを圧縮する方法で
あって、 （Ａ）入力データストリームを複数のデータブロックへ
と分割するステップと、 （Ｂ）複数のフィンガプリントを計算するステップと、
ここで、各フィンガプリントは、前記複数のデータブロ
ックの異なる１つのデータブロックに対応し、 （Ｃ）前記複数のフィンガプリントの各フィンガプリン
トは、前記複数のデータブロックの異なる１つのデータ
ブロックに対応し、入力データストリームを前記複数の
フィンガプリントと比較するステップと、 （Ｄ）特定のフィンガプリントと入力データストリーム
の間にマッチが出現すれば、そのマッチを入力データス
トリーム内のそのマッチを符号化するステップと、 （Ｅ）符号化したデータストリームを圧縮データストリ
ームへと圧縮するステップとを有することを特徴とする
方法。 - 【請求項２】 前記入力データストリームは一連の文字
からなることを特徴とする請求項１記載の方法。 - 【請求項３】 前記ステップ（Ｃ）は、一連の文字の個
々の文字の関数として入力データストリームを順に横断
し、その個々の文字のそれぞれの関数として中間フィン
ガプリントを計算することを特徴とする請求項２記載の
方法。 - 【請求項４】 （Ｆ）前記複数のフィンガプリントと共
に前記複数のデータブロックをデータ構造に記憶するス
テップを更に有することを特徴とする請求項２記載の方
法。 - 【請求項５】 前記ステップ（Ｃ）は、特定のフィンガ
プリントにマッチする一連の文字から最も長いマッチし
たシーケンスを識別することを特徴とする請求項３記載
の方法。 - 【請求項６】 前記ステップ（Ｃ）は、中間フィンガプ
リントを特定のフィンガプリントと比較することを特徴
とする請求項３記載の方法。 - 【請求項７】 前記ステップ（Ｄ）は、最も長いマッチ
したシーケンスの入力データストリームにおける開始位
置および最も長いマッチしたシーケンスの長さを符号化
することを特徴とする請求項５記載の方法。 - 【請求項８】 複数の文字を含む入力データストリーム
を圧縮コードストリームへと処理する方法であって、 （Ａ）入力データストリームを複数のブロックに分割す
るステップと、ここで、各ブロックは、複数の文字のう
ち特定の数の文字を含み、 （Ｂ）複数のフィンガプリントを計算するステップと、
ここで、各フィンガプリントは、前記複数のデータブロ
ックの異なる１つのデータブロックに対応し、 （Ｃ）各フィンガプリントは複数のブロックの異なる１
つのブロックに対応し、特定のフィンガープリントと特
定のブロックのいずれかの部分との間にマッチが出現す
るかを判断するために、複数のブロックを複数のフィン
ガプリントと比較するステップと、 （Ｄ）出現したマッチそれぞれに対して入力データスト
リームにて識別子を符号化するステップと、ここで、 この識別子は、特定のブロックのマッチ部分の入力デー
タストリームにおける開始位置およびマッチ部分の長さ
を含み、 （Ｅ）符号化された入力データストリームを圧縮コード
ストリームへと圧縮するステップとを有することを特徴
とする方法。 - 【請求項９】 符号化された入力データストリームの圧
縮は、Lempel-Zivコーディング技術に従って行われるこ
とを特徴とする請求項１、８記載の方法。 - 【請求項１０】 前記ステップ（Ｃ）は、 （ａ）ウインドウサイズを選択するステップと、 （ｂ）ウインドウサイズの関数として複数のブロックを
横断するステップとを有することを特徴とする請求項８
記載の方法。 - 【請求項１１】 ウインドウサイズは、特定の数の文字
であることを特徴とする請求項１０記載の方法。 - 【請求項１２】 前記ステップ（Ｃ）は、 （ｃ）ブロックに含まれる特定の数の文字それぞれにお
けるブロックに対する中間フィンガプリントを計算する
ステップと、 （ｄ）中間フィンガプリントを特定のフィンガプリント
と比較するステップとを有することを特徴とする請求項
１１記載の方法。 - 【請求項１３】 前記複数のブロックの各ブロックはブ
ロックサイズが等しいことを特徴とする請求項１１記載
の方法。 - 【請求項１４】 前記ブロックサイズは１０〜１０００
文字の範囲であることを特徴とする請求項１３記載の方
法。 - 【請求項１５】 前記横断（ｂ）は、ブロックに含まれ
る特定の数の文字を順に横断することを特徴とする請求
項１２記載の方法。 - 【請求項１６】 （Ｆ）前記複数のフィンガプリントと
共に前記複数のデータブロックをデータ構造に記憶する
ステップを有し、このデータ構造は、各フィンガプリン
トをその異なる１つの対応するブロックと共に記憶する
ことを特徴とする請求項８記載の方法。 - 【請求項１７】 前記開始位置は、入力データストリー
ムにおける文字の位置であり、マッチした部分の長さは
文字の数であることを特徴とする請求項１６記載の方
法。 - 【請求項１８】 （Ａ）入力データストリームを受信し
複数のブロックへと分割する受信器と、ここで、 各ブロックは、入力データストリームからの複数の文字
の特定の数の文字を含み、 （Ｂ）複数のフィンガプリントを計算するエンコーダ
と、ここで、 各フィンガプリントは、前記複数のブロックの異なる１
つのブロックに対応し、このエンコーダは、複数のブロ
ックを複数のフィンガプリントと比較し、特定のフィン
ガプリントと特定のブロックのいずれかの部分の間でマ
ッチが出現するかを判断し、出現した各マッチに対して
そのマッチの入力データストリームにおける識別子を符
号化し、 （Ｃ）符号化された入力データストリームを圧縮コード
ストリームへと圧縮するコンプレッサとを有することを
特徴とするデータ圧縮を行う装置。 - 【請求項１９】 （Ｄ）複数のブロックを複数のフィン
ガプリントと共にデータ構造に記憶するメモリーを更に
有し、 このデータ構造は、各フィンガプリントをその異なる１
つの対応するブロックと共に記憶することを特徴とする
請求項１８記載のデータ圧縮を行う装置。 - 【請求項２０】 前記複数のブロックの比較は、（ａ）
ブロックに含まれる特定の数の文字の各文字におけるブ
ロックに対して中間フィンガプリントを計算し、 （ｂ）中間フィンガプリントを特定のフィンガプリント
と比較することを特徴とする請求項１８記載のデータ圧
縮を行う装置。 - 【請求項２１】 前記識別子は、特定のブロックのマッ
チした部分の入力データストリームにおける開始位置お
よびマッチした部分の長さを含むことを特徴とする請求
項１９記載のデータ圧縮を行う装置。 - 【請求項２２】 前記複数のブロックの各ブロックは、
ブロックサイズが等しいことを特徴とする請求項２１記
載のデータ圧縮を行う装置。 - 【請求項２３】 前記開始位置は、入力データストリー
ムにおける文字の位置であり、前記マッチした部分の長
さは、文字の数であることを特徴とする請求項２２記載
のデータ圧縮を行う装置。 - 【請求項２４】 前記コンプレッサ（Ｃ）は、圧縮コー
ドストリームへと符号化された入力データストリームを
圧縮するのにLempel-Zivコーディングを用いることを特
徴とする請求項１８記載のデータ圧縮を行う装置。 - 【請求項２５】 デジタルデータストリームを圧縮デー
タ形式で記憶するデータ記憶システムであって、 （Ａ）デジタルデートストリームを複数のデータブロッ
クへと分割する手段と、ここで、各ブロックは複数の文
字を有し、 （Ｂ）複数のフィンガプリントを計算する手段と、ここ
で、各フィンガプリントは、前記複数のデータブロック
の異なる１つのデータブロックに対応し、 （Ｃ）複数のブロックを横断する手段と、 （Ｄ）ブロックの複数の文字の各文字における各ブロッ
クに対する中間フィンガプリントを計算する手段と、 （Ｅ）中間フィンガプリントを複数のフィンガプリント
の特定のフィンガプリントと比較する手段と、 （Ｆ）その特定のフィンガプリントと中間フィンガプリ
ントの間でマッチが出現すれば、そのマッチをデジタル
データストレームにおいて符号化する手段と （Ｇ）符号化されたデータストリームを圧縮データ形式
に圧縮する手段と、を有することを特徴とするデータ記
録システム。 - 【請求項２６】 （Ｈ）複数のデータブロックを複数の
フィンガプリントと共にデータ構造に記憶する手段を更
に有することを特徴とする請求項２５記載のデータ記録
システム。 - 【請求項２７】 前記横断する手段（Ｃ）は、各ブロッ
クの複数の文字の関数としてブロックを順に横断するこ
とを特徴とする請求項２６記載のデータ記録システム。 - 【請求項２８】 前記圧縮する手段（Ｇ）は、符号化さ
れたデジタルデータストリームを圧縮データ形式に圧縮
するためにLempel-Zivコーディングを用いることを特徴
とする請求項２７記載のデータ記録システム。 - 【請求項２９】 前記符号化されたマッチは、特定の部
分のマッチした部分のデジタルデータストリームにおけ
る開始位置およびマッチした部分の長さを含むことを特
徴とする請求項２５記載のデータ記録システム。 - 【請求項３０】 圧縮デジタル信号を処理する装置であ
って、 圧縮デジタル信号は、 （ａ）入力デジタルデータストリームを複数のデータブ
ロックへと分割し、 （ｂ）それぞれが複数のデータブロックの異なる１つの
データブロックに対応する複数のフィンガプリントを計
算し、 （ｃ）入力デジタルデータストリームを複数のフィンガ
プリントと比較し、 （ｄ）特定のフィンガプリントと入力デジタルデータス
トリームの間でマッチが出現すれば、入力デジタルデー
タストリームにおいてそのマッチを符号化し、 （ｅ）符号化された入力デジタルデータストリームを圧
縮デジタル信号に圧縮し、 （ｆ）圧縮デジタル信号を通信チャネルへ、供給するこ
とにより作られ、 （Ａ）通信チャネルから圧縮デジタル信号を受信する受
信器と、 （Ｂ）受信した圧縮デジタル信号を脱圧縮し、その脱圧
縮したデジタル信号から入力デジタルデータストリーム
を回復するデコンプレッサとを有することを特徴とする
圧縮デジタル信号を処理する装置。 - 【請求項３１】 前記複数のブロックの各ブロックは、
複数の文字を含み、前記入力デジタルデータストリーム
の比較（ｃ）は、 （ｇ）ブロックの複数の文字の各文字におけるブロック
に対する中間フィンガプリントを計算し、 （ｈ）中間フィンガプリントを特定のフィンガプリント
と比較することを特徴とする請求項３０記載の装置。 - 【請求項３２】 前記複数のブロックの各ブロックは、
ブロックサイズが等しいことを特徴とする請求項３１記
載の装置。 - 【請求項３３】 前記複数のフィンガプリントの各フィ
ンガプリントは対応するデータブロックの特定の文字群
を表すことを特徴とする請求項３１記載の装置。 - 【請求項３４】 以下の命令を含む複数の命令が記憶さ
れた機械が読み取り可能な媒体。すなわち、 （Ａ）機械により実行されると、入力データストリーム
を圧縮コードストリームへと処理させ、 （Ｂ）入力データストリームを複数のブロックへと分割
させ、ここで、各ブロックは複数の文字の特定の数の文
字を含み、 （Ｃ）複数のフィンガプリントを計算させ、ここで、各
フィンガプリントは、前記複数のブロックの異なる１つ
のブロックに対応し、 （Ｄ）複数のブロックを複数のフィンガプリントと比較
させ、 （Ｅ）特定のフィンガプリントと特定のブロックのいず
れかの部分の間にマッチが出現するかどうかを判断さ
せ、 （Ｆ）出現した各マッチに対して、入力データストリー
ムにおけるそのマッチの識別子を符号化させ、ここで、
この識別子は、特定のブロックのマッチした部分の入力
データストリームにおける開始位置およびマッチした部
分の長さを含み、 （Ｇ）符号化された入力データストリームを圧縮コード
ストリームへと圧縮させる命令。 - 【請求項３５】 前記複数のフィンガプリントの各フィ
ンガプリントはその対応するブロックの特定の文字群を
表すことを特徴とする請求項３４記載の機械が読み取り
可能な媒体。 - 【請求項３６】 前記比較（Ｄ）は、ブロックにおける
文字の関数として行われ、ブロックに対する中間フィン
ガプリントは、前記複数の文字の各文字にて計算され、
前記特定のフィンガプリントと比較されることを特徴と
する請求項３４記載の機械が読み取り可能な媒体。 - 【請求項３７】 前記圧縮は、Lempel-Zivコーディング
技術に従って行われることを特徴とする請求項３６記載
の機械が読み取り可能な媒体。 - 【請求項３８】 （Ａ）それぞれが複数の文字からなる
複数のブロックへと入力データストリームを分割し、 （Ｂ）それぞれが前記複数のブロックの異なる１つのブ
ロックに対応する複数のフィンガプリントを計算し、 （Ｃ）ブロックの複数の文字の各文字の関数として入力
ストリームを横断し、 （Ｄ）ブロックの各文字におけるブロックに対する中間
フィンガプリントを計算し、 （Ｅ）中間フィンガプリントを複数のフィンガプリント
と比較し、 （Ｆ）複数のフィンガプリントの特定のフィンガプリン
トと中間フィンガプリントの間でマッチが出現するかど
うか判断し、 （Ｇ）出現した各マッチに対して、ブロックのマッチし
た部分の入力データストリームの開始位置およびマッチ
した部分の長さを含む、入力データストリーム内の識別
子を符号化し、 （Ｈ）符号化された入力データストリームを圧縮コード
ストリームへと圧縮し、 （Ｉ）圧縮コードストリームを表す記録信号を記憶媒体
に供給し、 （Ｊ）記録信号を記憶媒体上に記録する動作からなるプ
ロセスを用いて作成された記憶媒体。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US09/273840 | 1999-03-22 | ||
| US09/273,840 US6611213B1 (en) | 1999-03-22 | 1999-03-22 | Method and apparatus for data compression using fingerprinting |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2000315954A true JP2000315954A (ja) | 2000-11-14 |
| JP3634711B2 JP3634711B2 (ja) | 2005-03-30 |
Family
ID=23045627
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2000078069A Expired - Lifetime JP3634711B2 (ja) | 1999-03-22 | 2000-03-21 | 入力データストリームの圧縮方法とその装置 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US6611213B1 (ja) |
| EP (1) | EP1039645B1 (ja) |
| JP (1) | JP3634711B2 (ja) |
| CA (1) | CA2299902C (ja) |
| DE (1) | DE60000380T2 (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6927706B2 (en) | 2003-02-24 | 2005-08-09 | Oki Electric Industrial, Co., Ltd | Data compressing apparatus and data decoding apparatus |
| WO2009057459A1 (ja) * | 2007-10-30 | 2009-05-07 | Nec Corporation | データ圧縮方法 |
| JP2014183551A (ja) * | 2013-03-21 | 2014-09-29 | Fujitsu Ltd | データ圧縮装置、データ圧縮方法、およびデータ圧縮プログラム、並びにデータ復元装置、データ復元方法、およびデータ復元プログラム |
Families Citing this family (26)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3434756B2 (ja) * | 1999-12-07 | 2003-08-11 | エヌイーシ−カスタムテクニカ株式会社 | 指紋認証方法及び装置 |
| US7509420B2 (en) * | 2000-02-18 | 2009-03-24 | Emc Corporation | System and method for intelligent, globally distributed network storage |
| US8121843B2 (en) | 2000-05-02 | 2012-02-21 | Digimarc Corporation | Fingerprint methods and systems for media signals |
| US6810398B2 (en) * | 2000-11-06 | 2004-10-26 | Avamar Technologies, Inc. | System and method for unorchestrated determination of data sequences using sticky byte factoring to determine breakpoints in digital sequences |
| US7164369B2 (en) * | 2001-06-19 | 2007-01-16 | Sharp Laboratories Of America, Inc. | System for improving storage efficiency of digital files |
| US7071854B1 (en) * | 2002-05-13 | 2006-07-04 | Unisys Corporation | Hardware-implemented LZW data decompression |
| US7320009B1 (en) | 2003-03-28 | 2008-01-15 | Novell, Inc. | Methods and systems for file replication utilizing differences between versions of files |
| US8135683B2 (en) * | 2003-12-16 | 2012-03-13 | International Business Machines Corporation | Method and apparatus for data redundancy elimination at the block level |
| US7019674B2 (en) * | 2004-02-05 | 2006-03-28 | Nec Laboratories America, Inc. | Content-based information retrieval architecture |
| US7747635B1 (en) | 2004-12-21 | 2010-06-29 | Oracle America, Inc. | Automatically generating efficient string matching code |
| US7592935B2 (en) * | 2005-03-10 | 2009-09-22 | Nec Laboratories America, Inc. | Information retrieval architecture for packet classification |
| US7098815B1 (en) * | 2005-03-25 | 2006-08-29 | Orbital Data Corporation | Method and apparatus for efficient compression |
| US7095342B1 (en) * | 2005-03-31 | 2006-08-22 | Intel Corporation | Compressing microcode |
| US7102552B1 (en) * | 2005-06-07 | 2006-09-05 | Windspring, Inc. | Data compression with edit-in-place capability for compressed data |
| US7882084B1 (en) | 2005-12-30 | 2011-02-01 | F5 Networks, Inc. | Compression of data transmitted over a network |
| US20070220026A1 (en) * | 2006-03-17 | 2007-09-20 | Microsoft Corporation | Efficient caching for large scale distributed computations |
| US9772981B2 (en) * | 2006-03-29 | 2017-09-26 | EMC IP Holding Company LLC | Combined content indexing and data reduction |
| US8175875B1 (en) | 2006-05-19 | 2012-05-08 | Google Inc. | Efficient indexing of documents with similar content |
| US7747078B2 (en) * | 2006-07-06 | 2010-06-29 | Intel Corporation | Substring detection system and method |
| US8032757B1 (en) * | 2008-05-16 | 2011-10-04 | Trend Micro Incorporated | Methods and apparatus for content fingerprinting for information leakage prevention |
| WO2010069364A1 (en) * | 2008-12-16 | 2010-06-24 | Telefonaktiebolaget Lm Ericsson (Publ) | String matching method and apparatus |
| KR101049699B1 (ko) * | 2009-07-17 | 2011-07-15 | (주)이스트소프트 | 데이터의 압축방법 |
| US9648144B2 (en) * | 2014-01-24 | 2017-05-09 | Mediatek Inc. | Data compression method and decompression method |
| CN104216666A (zh) * | 2014-09-03 | 2014-12-17 | 浪潮(北京)电子信息产业有限公司 | 一种管理磁盘数据写入的方法及装置 |
| US10840943B1 (en) * | 2019-10-15 | 2020-11-17 | EMC IP Holding Company LLC | System and method of data compression between backup server and storage |
| US12547450B2 (en) * | 2023-01-20 | 2026-02-10 | Arm Limited | Reading data within a compressed data stream |
Family Cites Families (22)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4464650A (en) | 1981-08-10 | 1984-08-07 | Sperry Corporation | Apparatus and method for compressing data signals and restoring the compressed data signals |
| US4558302A (en) | 1983-06-20 | 1985-12-10 | Sperry Corporation | High speed data compression and decompression apparatus and method |
| US5146221A (en) | 1989-01-13 | 1992-09-08 | Stac, Inc. | Data compression apparatus and method |
| FR2646575A1 (fr) * | 1989-04-26 | 1990-11-02 | Labo Electronique Physique | Procede et structure pour la compression de donnees |
| US5045852A (en) * | 1990-03-30 | 1991-09-03 | International Business Machines Corporation | Dynamic model selection during data compression |
| US5373290A (en) * | 1991-09-25 | 1994-12-13 | Hewlett-Packard Corporation | Apparatus and method for managing multiple dictionaries in content addressable memory based data compression |
| US5371499A (en) * | 1992-02-28 | 1994-12-06 | Intersecting Concepts, Inc. | Data compression using hashing |
| US5442350A (en) | 1992-10-29 | 1995-08-15 | International Business Machines Corporation | Method and means providing static dictionary structures for compressing character data and expanding compressed data |
| US5550540A (en) | 1992-11-12 | 1996-08-27 | Internatioal Business Machines Corporation | Distributed coding and prediction by use of contexts |
| US5408234A (en) * | 1993-04-30 | 1995-04-18 | Apple Computer, Inc. | Multi-codebook coding process |
| US5369605A (en) | 1993-07-07 | 1994-11-29 | Dell Usa, L.P. | Incremental search content addressable memory for increased data compression efficiency |
| JP3397431B2 (ja) | 1994-03-16 | 2003-04-14 | 富士通株式会社 | データ圧縮方法および装置ならびにデータ復元方法および装置 |
| US5701125A (en) | 1994-06-15 | 1997-12-23 | The United States Of America As Represented By The United States Department Of Energy | Method for compression of data using single pass LZSS and run-length encoding |
| US5572206A (en) | 1994-07-06 | 1996-11-05 | Microsoft Corporation | Data compression method and system |
| US5572209A (en) | 1994-08-16 | 1996-11-05 | International Business Machines Corporation | Method and apparatus for compressing and decompressing data |
| EP0718980A1 (en) | 1994-12-20 | 1996-06-26 | International Business Machines Corporation | Data compression method of individual sequences of strings of a data stream based on a dictionary and device for performing the same |
| US5608396A (en) | 1995-02-28 | 1997-03-04 | International Business Machines Corporation | Efficient Ziv-Lempel LZI data compression system using variable code fields |
| US5663721A (en) | 1995-03-20 | 1997-09-02 | Compaq Computer Corporation | Method and apparatus using code values and length fields for compressing computer data |
| US5729223A (en) * | 1996-03-20 | 1998-03-17 | Motorola Inc. | Method and apparatus for data compression and restoration |
| GB9606465D0 (en) | 1996-03-27 | 1996-06-05 | Memory Corp Plc | Data conversion device |
| US5703581A (en) | 1996-06-14 | 1997-12-30 | Lucent Technologies Inc. | Method and apparatus for data compression and decompression |
| US6084229A (en) | 1998-03-16 | 2000-07-04 | Photon Vision Systems, Llc | Complimentary metal oxide semiconductor imaging device |
-
1999
- 1999-03-22 US US09/273,840 patent/US6611213B1/en not_active Expired - Lifetime
-
2000
- 2000-02-29 CA CA002299902A patent/CA2299902C/en not_active Expired - Fee Related
- 2000-03-14 EP EP00302040A patent/EP1039645B1/en not_active Expired - Lifetime
- 2000-03-14 DE DE60000380T patent/DE60000380T2/de not_active Expired - Lifetime
- 2000-03-21 JP JP2000078069A patent/JP3634711B2/ja not_active Expired - Lifetime
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6927706B2 (en) | 2003-02-24 | 2005-08-09 | Oki Electric Industrial, Co., Ltd | Data compressing apparatus and data decoding apparatus |
| WO2009057459A1 (ja) * | 2007-10-30 | 2009-05-07 | Nec Corporation | データ圧縮方法 |
| US8532415B2 (en) | 2007-10-30 | 2013-09-10 | Nec Corporation | Data compression method |
| JP2014183551A (ja) * | 2013-03-21 | 2014-09-29 | Fujitsu Ltd | データ圧縮装置、データ圧縮方法、およびデータ圧縮プログラム、並びにデータ復元装置、データ復元方法、およびデータ復元プログラム |
Also Published As
| Publication number | Publication date |
|---|---|
| CA2299902C (en) | 2004-08-17 |
| EP1039645B1 (en) | 2002-09-04 |
| EP1039645A1 (en) | 2000-09-27 |
| JP3634711B2 (ja) | 2005-03-30 |
| CA2299902A1 (en) | 2000-09-22 |
| US6611213B1 (en) | 2003-08-26 |
| DE60000380T2 (de) | 2003-05-15 |
| DE60000380D1 (de) | 2002-10-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3634711B2 (ja) | 入力データストリームの圧縮方法とその装置 | |
| CN108880556B (zh) | 基于lz77的无损数据压缩方法、误码修复方法及编码器和解码器 | |
| CN108768403B (zh) | 基于lzw的无损数据压缩、解压方法及lzw编码器、解码器 | |
| US7616138B2 (en) | Data compression using a stream selector with edit-in-place capability for compressed data | |
| US7403136B2 (en) | Block data compression system, comprising a compression device and a decompression device and method for rapid block data compression with multi-byte search | |
| US5870036A (en) | Adaptive multiple dictionary data compression | |
| US10476518B1 (en) | Hardware friendly data compression | |
| JP3231663B2 (ja) | データ圧縮方法 | |
| WO2019153700A1 (zh) | 编解码方法、装置及编解码设备 | |
| US5877711A (en) | Method and apparatus for performing adaptive data compression | |
| JPH0869370A (ja) | データ圧縮方法およびシステム | |
| EP0903865A1 (en) | Method and apparatus for compressing data | |
| WO2013095615A1 (en) | Bitstream processing using coalesced buffers and delayed matching and enhanced memory writes | |
| JPH03204233A (ja) | データ圧縮方法 | |
| KR20030040567A (ko) | 허프만 디코딩을 수행하는 방법 | |
| EP0435802B1 (en) | Method of decompressing compressed data | |
| JP2536422B2 (ja) | デ―タ圧縮装置及びデ―タ復元装置 | |
| JPH03204235A (ja) | 圧縮データの復号方法 | |
| EP1941617A1 (en) | Method and system for compressing data | |
| US6819272B2 (en) | System, method and computer readable medium for compressing a data sequence for partial decompressing | |
| CN117200805B (zh) | 一种mcu的低内存占用的压缩和解压方法及装置 | |
| Subathra et al. | Performance analysis of dictionary based data compression algorithms for high speed networks | |
| GB2360916A (en) | Compression encoder which transmits difference between new data word and recent data word where this falls within a threshold | |
| JPH06274311A (ja) | データ圧縮装置及びデータ復元装置 | |
| JP2014229926A (ja) | データ変換方法、データ逆変換方法、装置、及びプログラム |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20040726 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20041015 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20041201 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20041224 |
|
| R150 | Certificate of patent or registration of utility model |
Ref document number: 3634711 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080107 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090107 Year of fee payment: 4 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100107 Year of fee payment: 5 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110107 Year of fee payment: 6 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110107 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120107 Year of fee payment: 7 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130107 Year of fee payment: 8 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| EXPY | Cancellation because of completion of term |