JPH0358207B2 - - Google Patents

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、一般的には計算機のデータ・フアイ
ルの圧縮方法、より具体的にはデータがワード及
び区切りに分割されているような文字データを適
応的に圧縮する方法に関する。本発明によるフア
イル・コンプレツサは、計算機プログラム又は自
然言語のいずれかの、言語を含むフアイルに対し
て使用する事が意図されている。

［従来技術及びその問題点］ コンプレツサを設計する問題は、２つの部分に
分けられる。第１は、原文書のモデルの構築であ
る。そのようなモデル毎に、圧縮された文書に関
する理論的な最小の大きさ、いわゆるエントロピ
ー限界が存在する。次に、実際の圧縮がその理論
値に接近するような実用的な符号化方式を定式化
する必要がある。

非適応型のモデル、即ち伝送される文書に対し
てその特性が独立的であるモデルに関しては、ハ
フマン符号化がしばしば、かなり効率的である。
適応型のモデルに関ししては、符号化処理中に符
号化方式も変化しなければならない。従つて適応
型のハフマン符号化が必要になる。既にそのよう
な方式が構成され且つ使用されているが、より高
速の符号化方式が望まれている。

従つて、本発明の目的は、従来技術で知られて
いるよりも高速で且つ圧縮率の高い新規なフアイ
ル圧縮方法を提供する事である。

［問題点を解決するための手段］ 本発明によれば、書かれた言語は第１の種類の
文字の連続したものより成るワードと第２の種類
の文字の連続したものより成る区切りとが交互に
なつたストリームと考える事ができる事に注目す
ることによつて、適応的なフアイル圧縮方法が実
現される。最初、ワード及び区切り用の空白の辞
書が形成される。本発明による文字データ・スト
リームの圧縮方法は、 (a) データ・ストリーム中の事象毎に当該事象が
ワード又は区切りの何れであるかを判定し、 (b) 上記ステツプ(a)で事象がワードであると判定
されたならば、当該ワードが既にデータ・スト
リーム中に登場したワードであるか否かを判定
し、 (c) 上記ステツプ(b)の判断結果が肯定的であるな
らば、 （c1） 既にデータ・ストリーム中に登場した
各ワードの項目を持ち、そのようなワード毎
に登場回数を計数するためのワード用の辞書
の、該当するワードの計数値と該ワード用辞
書中の全ワードの計数値の和との比を確率評
価値として用いて当該ワード事象を符号化
し、 （c2） 上記ワード用辞書の該当するワードの
計数値を所定数だけ増加させ、 (d) 上記ステツプ(b)の判断結果が否定的であるな
らば、 （d1） 上記事象が新しいワードであること
を表わす符号を発生させて上記ワード事象を
符号化し、 （d2） 上記ワードを構成する文字を符号化
する一方、上記ワード用辞書に当該新しいワ
ードの項目を確保し、かつその計数値を上記
ステツプ（c2）のものと同じ所定数に設定
し、 (e) 上記ステツプ(a)で事象が区切りであると判定
されたならば、当該区切りが既にデータ・スト
リーム中に登場した区切りであるか否かを判定
し、 (f) 上記ステツプ(e)の判断結果が肯定的であるな
らば、 （f1） 既にデータ・ストリーム中に登場した
各区切りの項目を持ち、そのような区切り毎
に登場回数を計数するための区切り用の辞書
の、該当する区切りの計数値と該区切り用辞
書中の全区切りの計数値の和との比を確率評
価値として用いて当該区切り事象を符号化
し、 （f2） 上記区切り用辞書の該当する区切りの
計数値を所定数だけ増加させ、 (g) 上記ステツプ(e)の判断結果が否定的であるな
らば、 （g1） 上記事象が新しい区切りであること
を表わす符号を発生させて上記区切り事象を
符号化し、 （g2） 上記区切りを構成する文字を符号化
する一方、上記区切り用辞書に当該新しい区
切りの項目を確保し、かつその計数値を上記
ステツプ（f2）のものと同じ所定数に設定す
る ステツプを含む。

［実施例］ 本発明を実施する時に使用するモデルは次の特
性を有している。伝送されるデータは、事象の系
列より構成され、事象は最初の事象から始まつ
て、次に２番目のもの、等々と１度に１つづつ符
号化されるものと仮定する。ｎ番目の事象を符号
化する時、モデルは、(1)関連する事象の集合及び
(2)各事象の確率を形成する。それを行なう時、モ
デルは、それ以前の全ての事象についての知識を
利用し得るが、そのｎ番目の事象又はまだ符号化
されていない事象を考慮に入れてはならない。こ
の制限は、デコーダにおけるモデルのコピーが、
エンコーダにおけるそれと同じ情報を有し得る事
を意味している。

モデルは適応的であり、即ち事象の頻度がフア
イルの符号化と共に蓄積されてゆく。確率は有理
数であつて、与えられた事象の確率は、関連する
事象の集合に関する全計数値に対する、その事象
の計数値の比である。従つて、使われる確率は、
符号化処理中に変化する。

このモデルの１つの特徴は、符号化処理中のス
テツプで使われる適切な事象集合の選択である。
このモデルは有限状態機械と考える事もできる。

辞書モデルにおいて、フアイルはレコードの系
列として取り扱われる。各レコードは、「ワード」
及び「区切り」の交互の系列を含んでいる。英数
字によつてワードが構成される自然言語の文字デ
ータ・ストリームでは、ワードとは英数字のスト
リングであり、区切りとは英数字以外の文字のス
トリングである。多くの文書では、１個のスペー
スが主な区切りである。

符号化処理工程が第１図に図示されている。。
レコードは入力フアイルが読取られる。レコード
は区切り又はワードで始まる。従つて最初の事象
は２つの可能性、即ち開始ワード又は開始区切り
より成る。上記自然言語の文字データ・ストリー
ムでは、事象を構成する文字が英数字であれば当
該事象がワードであると判定され、事象を構成す
る文字が英数字以外の文字であれば当該事象が区
切りであると判定される。適当な事象の対が符号
化される。出会つた事象の計数値は１つづつ増加
する。ワードが予期される時、可能な事象は下記
のうち１つである。

新しいワード （（符号「新ワード」） 古いワードＮ（Ｎ＝１，２，…） （符号「ワードＮ」） レコード終了 （符号「レコード終了」） 適当な事象が符号化された後、その事象に関す
る計数値は１つだけ増加する。

古いワードの事象とは、符号化すべきワードに
以前に出会つており、それがワード用辞書中に記
憶されているものである。Ｎは取得番号であり、
当該ワードが文字データ・ストリーム中で第Ｎ番
目にワード用辞書に登録されたワードであること
を示す。事象が古いワードＮである場合には、ワ
ード辞書を参照して後述する算術符号に従つて
「ワードＮ」の符号が生成され、その後、ワード
用辞書中のワードＮの項目の計数値が１だけ増分
される。事象が新しいワードである場合には、所
定の符号「新ワード」を用いて当該事象が符号化
される。続いて、当該ワードを構成する文字が符
号化される。一方、当該ワードはワード用辞書に
登録され、かつ計数値が１に設定される。この新
しいワードを構成する文字の符号化と新しいワー
ドのワード用辞書への登録は、どちらが先であつ
てもよく、あるいは同時に行なわれてもよい。ワ
ードを構成する文字の符号化処理は第２図に示
す。第２図は区切りにも適用される。従つて一般
的な用語「記号」を用いた。記号は１度に１文字
づつ符号化される。事象の集合は次のようなもの
である。

文字Ｎ （以前に出会つた文字） （符号「文字Ｎ」） 新しい文字 （符号「新しい文字」）） 記号終了 （記号中にそれ以上の文字がな
い） （符号「記号終了」） 以上、ワード事象の符号化について説明した
が、区切り事象の符号化も、区切り用辞書を使う
点を除き、ワード事象の場合と同様に行なわれ
る。

事象が符号化された後、適当な計数値が１つ増
加される。新しい文字に出会つた時、それも符号
化しなければならない。これは全ての新しい文字
（０〜255））が一様にありそうであると仮定する
事によつて行なわれる。特定の文字に関する計数
値は１にセツトされる。ワード中の文字及び区切
り中の文字については、別個のテーブルが保持さ
れている事に注意すべきである。ワードの後に
は、レコードの終りに出会わなければ、区切りが
予期される。区切りはワードと同様に扱われる
が、それらはそれ自身の辞書と統計を持つてい
る。

プログラムは、入力レコードの終りに至るま
で、ワードと区切りとの間をスイツチする。レコ
ード終了の事象は符号化され、新しいレコードが
読み取られる。そして、レコードがワードで始ま
るか又は区切りで始まるかを示すための符号で始
まり、符号化処理が反復される。フアイル終了の
時、開始ワード及びレコード終了の事象が伝送さ
れる。これは空レコードを示し、フアイルの終了
として用いられる。

本発明を実用的に実施したものは、算術符号を
使用する。最初に、あたかも算術演算が無限の精
度で行ない得るかのように、算術符号化処理を説
明する。実際的なアルゴリズムの詳細は後に与え
る。

事象を符号化するために、必要な入力データ
は、ある任意の順序（これはコンプレツサとデコ
ンプレツサの両者に知られている）に配列された
可能な事象の各々の計数値と、符号化すべき特定
の事象ある。変数ｎは事象の番号を示す。ｎは１
で始まり、各事象が符号化される毎に１つづつ増
加する。

ｃ（ｉ、ｎ）＞０（但しｉ＝１、２、…、Ｉ（ｎ））
を、ｎ番目の事象に関するＩ（ｎ）個の可能な選
択に関する計数値とする。累積計数値を次のよう
に定義する。

(Ci、n)＝ｃ(1、n)＋…＋ｃ(i、n) (1) 但し、ｉ＝１、２、…、Ｉ（ｎ） 及び、Ｃ（０、ｎ）＝０ Ｃは定義により、ｉの単調増加関数である。算
術符号化手段への入力は、数Ｃ及びび特定の事象
ｉの組である。

ｘ（ｎ）及びｒ（ｎ）を、最初のｎ個の事象を符
号化した結果を示す実数の対であるとする。開始
値はｘ（（０）＝０及びｒ（０）＝１である。ｎ番目
の事象（事象ｉはＣによつて記述される集合の中
にある）を符号化するための公式は次の通りであ
る。

ｘ（ｎ）＝ｘ（ｎ−１） ＋ｒ（ｎ−１）Ｃ（ｉ−１、ｎ）／Ｃ（Ｉ（ｎ）、
ｎ）(2) ｒ（ｎ）＝ｒ（ｎ−１） ［Ｃ（（ｉ、ｎ）−Ｃ（ｉ−１、ｎ）］／Ｃ（Ｉ（
ｎ）、ｎ） この公式は、評価確率及び累積分布関数を次の
ように定義すると、一層明瞭になるであろう。

ｐ（ｉ、ｎ）＝ｃ（ｉ、ｎ）／Ｃ（Ｉ（ｎ）、ｎ）(3
) Ｆ（ｉ、ｎ）＝ｐ（１、ｎ） ＋ｐ（２、ｎ）＋…＋ｐ（ｉ、ｎ） Ｆ（０、ｎ）＝０ 上記の定義を用いると、式(2)は次のようにな
る。

ｘ（ｎ）＝ｘ（ｎ−１） ＋ｒ（ｎ−１）Ｆ（（ｉ−１、ｎ） （2a） ｒ（ｎ）＝ｒ（ｎ−１）ｐ（ｉ、ｎ） ＝ｒ（ｎ−１）［Ｆ（ｉ、ｎ） −Ｆ（ｉ−１、ｎ）］ 第３図はこれらの公式の幾何学的関係を示して
いる。但し、第３図ではＩ（ｎ）＝４、ｉ＝３と仮
定されている。

もしフアイル全体がＮの事象を符号化すること
によつて記述されるならば、文書はｘ（Ｎ）の値
によつて表現される。デコーダはｘ（Ｎ）を与え
られ、そしてエンコーダと同じモデルを用いて、
Ｎ個の事象の系列を推論する事ができる。このデ
コーデイングの可能性は次式から導かれる。

ｘ（ｎ−１）≦ｘ（ｎ）＜ｘ（ｎ−１）＋ｒ（ｎ−
１）） (4) 但しｎ＝１、２、…Ｎ 従つて、 ｘ（ｎ）≦ｘ（Ｎ）＜ｘ（ｎ）＋ｒ（ｎ） (5) この式は次のように書く事ができる。

Ｃ（ｉ−１、ｎ）≦［ｘ（Ｎ）−ｘ（ｎ−１）］
Ｃ（Ｉ（ｎ）、ｎ）／ｒ（ｎ−１） ＜Ｃ（ｉ、ｎ） (6) Ｃはｉの単調増加関数なので、１つだけのｉの
値がこの不等式を満足できる。

符号化されたフアイルはｘ（Ｎ）の値によつて
表現される。充分な精度でｘ（Ｎ）を表現するの
に必要なビツト数は、容易に評価される。次式に
よつて定義される間隔Ｘ中の任意の点が与えられ
れば、フアイルのデコーデイングは充分に可能で
あろう。

ｘ（Ｎ）≦ｘ＜ｘ（Ｎ）＋ｒ（Ｎ） 従つて、ちようどその間隔の中にＸを位置付け
るのに充分なＸのビツトを伝送しさえすれば良
い。log₂（１／ｒ（Ｎ））＋２ビツトを用いれば、そ
れが成しとげられる。

ｒの計算に関する公式を調べてみると、ｒは
個々の事象の確率の積である事がわかる。従つ
て、log₂（１／ｐ（ｉ、ｎ））の全ての事象に関す
る和よりも２つ余分にビツトが必要である。

上記アルゴリズムは、５個の事象の組及び５個
の計数値の組を維持しなければならない。それら
は下記の表に与えられている。

組１ 新しいレコードの開始 項 目 初期値 開始ワード １ 開始区切り １ 組２ ワードの予期 項 目 初期値 レコードの終了 １ 新しいワード １ ワード１ ０ ワード２ ０ ……… 組３ 新しいワード中の文字の予期 項 目 初期値 ワードの終了 １ 新しい文字 １ 文字１ ０ 文字２ ０ ……… 組４ 区切りの予期 項 目 初期値 レコードの終了 １ 新しい区切り １ 区切り１ ０ 区切り２ ０ ……… 組５ 新しい区切り中の文字の予期 項 目 初期値 区切りの終了 １ 新しい文字 １ 文字１ ０ 文字２ ０ ……… 上記のどの組の中の事象に関しても、その事象
は、それについての計数値、符号化される事象に
関する組の中の全ての事象に関する計数値の総
和、及びその組の中の事象の総数を用いて符号化
される。事象が符号化された後、その事象に関す
る計数値は１つだけ増加される。もし事象が新し
いワード、区切り、又は文字であれば、新しい項
目に関する計数値が１にセツトされる。これは以
前はゼロであつた。この場合、その組の中の事象
の総数は２つ増加する事に注意されたい。という
のは各々の新しい項目は組の中の２重の事象だか
らである。

組４の中で、単一のスペース（空白文字）は別
個に取り扱われる。これは実行速度のためであ
る。なぜなら多くの文書において単一のスペース
は主要な区切りだからである。

組３及び５中の文字の計数値は、文字に関する
対応するEBCDIC符号によつてインデツクスされ
る。ワードの文字は０又は１の符号を有するもの
を含まないので、これらは各々ワードの終了及び
新しい文字のために使用される。区切り文字に関
しては、任意の英数字文字を区切りの終了及び新
しい文字を示すために使できる。例えば、文字
「ｘ」及び「ｙ」を選ぶことができる。

これらの計数値の表（組１に関するもの以外）
はかなり大規模である。各組中の項目の最大数は
下記のようになつている。

組番号 項目数 １ ２ ２ 4096 ３ 64 ４ 4096 ５ 196 ワード用辞書（組２）及び組区切り辞書(4)の大
きさは任意である。上記の選択は実際のフアイル
を圧縮する時には妥当なようである。組３及び５
に関しては、各々の表の中に256個の項目を記入
できるようにすると便利である。もつともその多
くは使われないであろう。これは計算のスピード
のためである。

事象に関する計数値を更新するのは単純な計算
である。問題は累積計数値が必要な時に生じる。
累積計数値は式(1)で定義されている。辞書が一杯
になれば、累積計数値を得るために4096回に至る
加算が必要であろう。また各々の新しい事象のた
めにＣ（ｉ、ｎ））を維持することも時間のかかる
事である。しかしこの問題を解決する技術が利用
可能である。その方法は第４図に示されている。
これは８つの事象の事象集合に関して構成されて
いる。第４図のＣ(i)は式(1)のＣ（ｉ、ｎ）に相当
するものである。各ノードには適当なＣ(i)の差が
記憶されている。事象の計数値は根から葉へ木を
トラバースする事によつて更新される。この時に
同時に累積計数値も計算される。各ノードの数値
は、経路がそのノードから左側へ行くならば１だ
け増加される。また葉の計数値は１だけ増加され
る。事象ｉに関するＣ（ｉ−１）の値は、経路が
そのノードを通り右側へ行つたノードの数値の和
によつて与えられる。ｉ＝５の場合、Ｃ(5)−Ｃ
（０）＝［Ｃ(4)−Ｃ（０）］＋［Ｃ(5)−Ｃ(4)］であ
る。
Ｃ(6)−Ｃ(4)及びＣ(6)−Ｃ(5)は１だけ増やされる。

木の深さは木の葉の数よりもずつと小さい事に
注意されたい。従つて更新動作にはずつと少ない
ステツプ数しか必要でない。実際、木は上部から
所望の葉又は事象まで１度トラバースされるだけ
である。最初に、累積計数値はゼロにセツトされ
る。トラバースの間、もし左側に行けば、そのノ
ードの計数値は１つだけ増やされる。一方、もし
右側に行けば、そのノードの値が累積計数値に加
算される。木の底部に達した時、葉は所望のｃ
（ｉ、ｎ）の値を有し、累積計数値はＣ（ｉ−１、
ｎ）に関する値を有している。

大規模なフアイルの場合、計数値が大きくなり
すぎるのを防ぐため又は辞書を限界内に保つため
に、計数値の再生規化が必要になる事がある。ま
た再正規化は古い統計の強調緩和も生じさせる。
再生規化の手続きは次の通りである。もし、事象
が処理される前にその事象の組に関する計数値合
計が16000よりも大きいか、又はその事象がワー
ド又は区切りであつてその事象の組に関する辞書
が殆んど一杯であれば、再正規化が起こる。各計
数値は２で割り算される。ワード及び区切りの場
合、剰余は捨てられる。他の計数値については、
丸めが行なわれる。ワード及び区切りの場合、あ
る記入項目は計数値が１から０になる。それらの
項目は辞書から切り捨てられる。もしそのような
項目に再び出会つたならば、それは新しいワード
又は新しい区切りになる。

上述した符号化方式は、32ビツト・ワードの機
械に関してインプリメントされた。重み及び切り
捨ての詳細は、デコーデイング処理を誤りなしに
行なう事ができ、元のフアイルを復元できるよう
に注意すべきである。

全ての計算は整数で行なわれる。数ｘ及びｒは
両方共整数である。初期値は次の通りである。

ｘ（０））＝０ ｒ（０）＝2³¹−１ ｒのこの値は32ビツト・ワード及び２の補数の
演算を用いた機械における最大の正の値である。
ｘは任意の長さのアキユムレータとして取り扱わ
れるが、ｘへの加算は常に、ｒの初期値に等しい
か又はそれよりも小さな数のものである。

式(2)によれば、ｒは次第に小さくなる。精度を
維持するために、ｒが小さくなりすぎるたびに、
ｒは256を乗算される。ｘの値も256を乗算しなけ
ればならない。従つて下記のスケーリング動作が
導かれる。これは符号化処理中の最初のステツプ
である。

ｒ（ｎ−１）＜2²³ならば (7) ｒ（ｎ−１）＝256r（ｎ−１） ｘ（ｎ−１）＝256x（ｎ−１） 繰り返し、 ここで事象ｉを符号化する用意が整つた。式(2)
の代わりに、次式を用いる。但し［…］は…の整
数部を表わす。

ｚ＝［ｒ（ｎ−１）Ｃ（ｉ−１、ｎ）／Ｃ（Ｉ（ｎ）
、ｎ）］(8) ｕ＝［ｒ（ｎ−１）Ｃ（ｉ、ｎ）／Ｃ（Ｉ（ｎ）、ｎ
）］ ｘ（ｎ）＝ｘ（ｎ−１）＋ｚ ｒ（ｎ）＝ｒ（ｎ−１）（ｕ−ｚ） ｒ及びｘに256を乗算する時、ｘの下位桁の４
バイトから左側にシフト・アウトされたｘのバイ
トを伝送するという誘惑にかられるかもしれな
い。この処理は多くの時には正しい。しかし不幸
なことに、ｘ（ｎ−１）からｘ（ｎ）を計算する
と、ｘの４つの下位桁バイトから左へキヤリーが
生じる事がある。このキヤリーは、ｘ及びｒの各
スケーリング毎に高々１回生じる。このキヤリー
を処理するために、ｘは８バイトの数値として維
持され、これら８バイトの最上位バイトが256を
掛ける前に伝送される。ここで問題は、ｘの４つ
の上位桁バイトの各々が255の値を持つという特
殊な場合に還元される。このまれな場合が生じる
たびに、ｘの上位４バイトはｘの最上位バイトを
伝送した後に256を乗算される。ｘが変化した時
はいつでもこのテストが行なわれる。

このアルゴリズムは、もしｒがゼロになると、
失敗する。式(8)から、もしｕ＝ｚであればその時
に限つてこれが起きる事が明らかである。

ｕ−ｚ＝［ｒ（ｎ−１）Ｃ（ｉ、ｎ）／Ｃ（Ｉ（ｎ）
、ｎ）］−［ｒ （ｎ−１）Ｃ（ｉ−１、ｎ）／Ｃ（Ｉ（ｎ）、ｎ）］ ≧［ｒ（ｎ−１）Ｃ（ｉ、ｎ）／Ｃ（Ｉ（ｎ）、ｎ
）−ｒ（ｎ− １）Ｃ（ｉ−１、ｎ）／Ｃ（Ｉ（ｎ）、ｎ）］ ≧［ｒ（ｎ−１）／Ｃ（Ｉ（ｎ）、ｎ）］ もしもＣ（Ｉ（ｎ）、ｎ）＜ｒ（ｎ−１）であれば
安全である。

ｒは符号化の前にスケーリングされるので、ｒ
の取り得る最小値は2²³である。従つてＣ（Ｉ
（ｎ）、ｎ）＜2²³でありさえすればよい。デコーデ
イングのために使われる下記の不等式(12)の証明中
で、条件2C（Ｉ（ｎ）、ｎ）＜ｒ（ｎ−１）が使われ
る。従つてＣ（Ｉ（ｎ）、ｎ）＜2²²を要求する必要
がある。既に述べたように、Ｃ（Ｉ（ｎ）、ｎ）に
関して許された最大の値は16000であり、これは
明らかに条件を満足する。

復号の処理は符号化処理と並行している。ｘの
値は圧縮されたデータから得られる。圧縮された
データの最初の４バイトはｘの初期値を与える。
ｒの初期値は、符号化で使われたものである。
種々の事象の組に関する統計は、エンコーダと同
様にデコーダにおいても維持されている。従つ
て、事象が復号される毎に、適当な事象の組がＣ
の正しい値と共に知られる。ｘ及びｒの再正規化
及びスケーリングは符号化の時と同様に行なわれ
る。

復号の時、ｘの値は可能な限り減少されるが、
ゼロよりも小さくなる事は許されない。従つて、
基本的な復号公式は、次式のようにｉを決定する
事に基づいている。

［ｒ（ｎ−１）Ｃ（ｉ−１、ｎ）／Ｃ（Ｉ（ｎ）、ｎ
）］≦ｘ＜ ［ｒ（ｎ−１）Ｃ（ｉ、ｎ）／Ｃ（Ｉ（ｎ）、ｎ）］
(9) このｉは事象集合から選択すべき事象を特定す
る。ｒ及びｘの新しい値は次式から計算される。

ｚ＝［ｒ（ｎ−１）Ｃ（ｉ−１、ｎ）／Ｃ（Ｉ（ｎ）
、ｎ）］(10) ｕ＝［ｒ（ｎ−１）Ｃ（ｉ、ｎ）／Ｃ（Ｉ（ｎ）、ｎ
）］ ｘ（ｎ）＝ｘ（ｎ−１）−ｚ ｒ（ｎ）＝ｒ（ｎ−１）（ｕ−ｚ） 式(7)に従つてｘ及びｒがスケーリングされる
時、符号化されたフアイルから新しいバイトがｘ
に付加され、右揃えされる。もし符号化されたメ
ツセージ中の４つの最近に使用された連続したバ
イトが各々255の値を持てば、次のバイトもｘに
付加され、右揃えされる。これは、キヤリーを管
理するために使われた機構を反転する。

不等式(9)からのｉの決定は、計算上望ましくな
い。というのは累積計数値及び多数回のテストが
必要だからである。そこで統計値を管理するため
に使用した木構造がデコードでも使用される。計
数値ｃを次式のように見つける事を試みる。

Ｃ（ｉ−１、ｎ）≦ｃ＜Ｃ（ｉ、ｎ） (11) そのようなｃは事象を見つけるために第４図の
木を検索するために容易に使用できる。ｃの決定
は次のように行なわれる。

ｃ＝［２（１＋ｘ／２）Ｃ（Ｉ（ｎ）、ｎ）／ｒ（ｎ
−１）］ 最初に、ｃ≧Ｃ（ｉ−１、ｎ）である事を示す。
下記において、ｄ及びｆは１よりも小さく且つゼ
ロに等しいか又はそれよりも大きな変数である。
変数ｅは０及び0.5の正の値を持つ。

ｃ＝［２（１＋ｘ／２−ｅ）Ｃ（Ｉ（ｎ）、ｎ）／ｒ
（ｎ−１）］ ｃ＋ｄ＝（２＋ｘ−2e）Ｃ（Ｉ（ｎ）、ｎ）／ｒ（ｎ
−１） ＝２（１−ｅ）Ｃ（Ｉ（ｎ）、ｎ）／ｒ（ｎ−１）
＋ｘ Ｃ（Ｉ（ｎ）、ｎ）／ｒ（ｎ−１） 不等式(9)から、次式が得られる。

ｘ≧ｒ（ｎ−１）Ｃ（ｉ−１、ｎ）／Ｃ（Ｉ（ｎ）、
ｎ）−ｆ 従つて ｃ＋ｄ≧（２−2e−ｆ）Ｃ（Ｉ（ｎ）、ｎ）／ｒ（ｎ
−１）＋Ｃ （ｉ−１、ｎ） ＞Ｃ（ｉ−１、ｎ） ｃ及びＣは整数であり、ｄは１よりも小さいの
で、ｃ≧Ｃ（ｉ−１、ｎ）が得られる。次に、ｃ
≦Ｃ（ｉ、ｎ）である事を示す。以前に次式が得
られている。

ｃ＋ｄ＝２（１−ｅ）Ｃ（Ｉ（ｎ）、ｎ）／ｒ（ｎ−
１）＋ｘ Ｃ（Ｉ（ｎ）、ｎ）／ｒ（ｎ−１） 不等式(9)から、 ｘ＜ｒ（ｎ−１）Ｃ（ｉ、ｎ）／Ｃ（（Ｉ（ｎ）、ｎ
） 従つて、 ｃ＋ｄ＜２（１−ｅ）Ｃ（Ｉ（ｎ）、ｎ）／ｒ（ｎ−
１）＋Ｃ（ｉ、 ｎ） ｃ及びＣ（（ｉ、ｎ）は整数であり、右辺の第１
項は１よりも小さいので、次の結論が得られる。

ｃ≦Ｃ（ｉ、ｎ） 従つて、Ｃ（ｉ−１、ｎ）≦ｃ≦Ｃ（ｉ、ｎ）で
ある事が示された。もしｃ＝Ｃ（ｉ、ｎ）であれ
ば、不等式(9)から、 ｒ（ｎ−１）ｃ／Ｃ（Ｉ（ｎ）、ｎ）＞ｘ この場合、我々はｃの試行値を１だけ減少させ
ている。その結果、我々は不等式(11)を満足するｃ
の値を得る。このｃの値は、符号化された事象を
見い出し且つ式(10)の計算のために必要な関連した
計数値を見い出すために計数値木をトラバースす
る時に使われる。

［発明の効果］ 本発明により、従来技術よりも高速且つ圧縮率
の高い新規なフアイル圧縮技術が提供された。

【図面の簡単な説明】

第１図は本発明によるフアイル・コンプレツサ
の流れ図、第２図は新しいワード及び区切りを符
号化する過程を示す流れ図、第３図はｎ番目の事
象の符号化を説明するための図、第４図は事象の
計数値に関する木構造を説明する図である。

Claims (1)

1. 【特許請求の範囲】 １ 第１の種類の文字の連続したものより成るワ
   ードと第２の種類の文字の連続したものより成る
   区切りとより成る文字データのストリームを圧縮
   する方法であつて、 (a) データ・ストリーム中の事象毎に当該事象が
   ワード又は区切りの何れであるかを判定し、 (b) 上記ステツプ(a)で事象がワードであると判定
   されたならば、当該ワードが既にデータ・スト
   リーム中に登場したワードであるか否かを判定
   し、 (c) 上記ステツプ(b)の判断結果が肯定的であるな
   らば、 （c1） 既にデータ・ストリーム中に登場した
   各ワードの項目を持ち、そのようなワード毎
   に登場回数を計数するためのワード用の辞書
   の、該当するワードの計数値と該ワード用辞
   書中の全ワードの計数値の和との比を確率評
   価値として用いて当該ワード事象を符号化
   し、 （c2） 上記ワード用辞書の該当するワードの
   計数値を所定数だけ増加させ、 (d) 上記ステツプ(b)の判断結果が否定的であるな
   らば、 （d1） 上記事象が新しいワードであること
   を表わす符号を発生させて上記ワード事象を
   符号化し、 （d2） 続いて上記ワードを構成する文字を
   符号化する一方、上記ワード用辞書に当該新
   しいワードの項目を確保し、かつその計数値
   を上記ステツプ（c2）のものと同じ所定数に
   設定し、 (e) 上記ステツプ(a)で事象が区切りでであると判
   定されたならば、当該区切りが既にデータ・ス
   トリーム中に登場した区切りであるか否かを判
   定し、 (f) 上記ステツプ(e)の判断結果が肯定的であるな
   らば、 （f1） 既にデータ・ストリーム中に登場した
   各区切りの項目を持ち、そのような区切り毎
   に登場回数を計数するための区切り用の辞書
   の、該当する区切りの計数値と該区切り用辞
   書中の全区切りの計数値の和との比を確率評
   価値として用いて当該区切り事象を符号化
   し、 （f2） 上記区切り用辞書の該当する区切りの
   計数値を所定数だけ増加させ、 (g) 上記ステツプ(e)の判断結果が否定的であるな
   らば、 （g1） 上記事象が新しい区切りであること
   を表わす符号を発生させて上記区切り事象を
   符号化し、 （g2） 続いて上記区切りを構成する文字を
   符号化する一方、上記区切り用辞書に当該新
   しい区切りの項目を確保し、かつその計数値
   を上記ステツプ（f2）のものと同じ所定数に
   設定する ステツプを含む文字データ・ストリームの適応
   的圧縮方法。