JPH08237138A

JPH08237138A - 圧縮装置および圧縮方法

Info

Publication number: JPH08237138A
Application number: JP7341868A
Authority: JP
Inventors: Terry A Welch; テリィ・アーチャー・ウエルチ
Original assignee: Unisys Corp
Current assignee: Unisys Corp
Priority date: 1983-06-20
Filing date: 1995-12-27
Publication date: 1996-09-13
Also published as: EP0129439A1; DE3476617D1; JPH07249996A; US4558302B1; CA1223965A; US4558302A; JP2610084B2; JPS60116228A; EP0129439B1; JPH0568893B2

Abstract

(57)【要約】【目的】ディジタル入力信号の流れにおいて新しく遭
遇した文字ストリングごとに接頭部ストリングと一つの
拡張文字からなる文字ストリングとして割当てた符号信
号を用いて圧縮するディジタルデータの圧縮方法とその
ための圧縮装置を提供することである。【構成】入力データ・ストリームからパースされたデ
ータ文字信号のストリングを格納し、そのストリームと
の最長一致を決めるために、そのストリームを格納され
たストリングと比較してデータ文字信号のストリームを
探索することによって、データ文字信号のストリームを
符号信号の圧縮されたストリームに圧縮する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はデータ圧縮および圧
縮データの伸長（ｄｅｃｏｍｐｒｅｓｓｉｏｎ）の分野
に関するものである。さらに具体的にいえば、ディジタ
ル入力信号の流れにおいて新しく遭遇した文字ストリン
グごとに接頭部ストリングと一つの拡張文字からなる文
字ストリングとして割当てた符号信号を用いて圧縮する
ディジタルデータの圧縮方法とそのための圧縮装置に関
するものである。

【０００２】

【従来の技術】ディジタル・データ信号のストリームを
圧縮されたディジタル・データ信号に符号化して、圧縮
されたディジタル・データ信号を元のデータ信号に復元
するデータ圧縮装置が従来知られている。データ圧縮と
は、与えられたフォーマットのデータを元のものより少
ないビットをもつもう一つのフォーマットに変換するす
べての処理をいう。データ圧縮装置の目的はディジタル
情報の与えられた主要部を保持するに必要な記憶装置の
量またはその主要部を伝送するのに必要な時間の量を節
約することである。圧縮比は、符号化されたデータの長
さの元の入力データの長さに対する比として定義され
る。圧縮比が小さければ小さいほど、記憶域または時間
の節約が大きくなる。データ記憶に必要な記憶装置また
はデータ伝送に必要な時間を減らすことによって、圧縮
は金銭上の節約をもたらす。磁気ディスクまたは磁気テ
ープのような物理的装置がデータファイルの格納に用い
られれば、圧縮されたデータを格納する装置に必要なス
ペースが小さくなって利用するディスクまたはテープが
少なくなる。電話線またはサテライト・リンクをディジ
タル情報の伝送に用いる場合、伝送の前にデータを圧縮
するとコストが下がる。データ圧縮装置は、元のデータ
が高い頻度で現れる記号または記号のストリングを持つ
ような冗長性を含む場合に特に有効である。データ圧縮
装置がデータの入力ブロックをより簡潔な形に変換し、
そのあとでその簡潔な形を逆にそれの元のフォーマット
の元のデータに翻訳または伸長する。

【０００３】例えば、日刊新聞の内容をサテライト・リ
ンクを経て遠隔の地に伝送して、そこで印刷することが
望まれることがある。適当なセンサが新聞の内容を直列
に発生する文字のデータ・ストリームに変換して、通信
リンクを介して伝送することができる。新聞の内容を含
む何百万の記号が伝送前に圧縮されて受信者のところで
再構成されるとすればかなりの量の伝送時間が節約され
るであろう。

【０００４】別の例として、定期航空路予約データベー
スまたはバンキング・システム・データベースなどの広
範囲なデータベースが記録保管の目的で格納されると
き、データベースを構成する文字の全体が記憶に先立っ
て圧縮されて、あとで使用するには格納された圧縮ファ
イルから再び広げられるとすれば、かなりの量の記憶ス
ペースが節約されるであろう。

【０００５】

【発明が解決しようとする課題】実際にそして一般に役
立つようにするためには、ディジタル・データ圧縮装置
がある基準を満足する必要がある。この装置はデータ圧
縮装置およびデータ伸長装置が仲介している機器によっ
て授受されるデータ速度に関して高い性能を与える必要
がある。データ圧縮できる速度は、圧縮装置に入る入力
データ処理速度によって決まり、普通数百万バイト毎秒
（メガバイト／秒）である。普通１メガバイト／秒を超
える速度を持つ今日のディスク、テープおよび通信装置
において達成されたデータ速度を保つには高性能が必要
である。従って、データ圧縮装置およびデータ伸長装置
は、最近の装置で達成される帯域幅に一致するデータ帯
域幅をもっていなければならない。従来のデータ圧縮装
置およびデータ伸長装置の性能は、普通、統計的データ
を記憶して圧縮処理および伸長処理を管理するのに用い
られるランダムアクセス記憶装置（ＲＡＭ）などの速度
によって制限される。圧縮装置に対する高性能は、圧縮
装置に入る入力文字ごとに必要なｒａｍサイクル（読み
書き動作）の数によって特徴づけられる。記憶サイクル
の数が少なければ少ないほど性能は高い。高性能設計を
電話通信等の低速度の適用業務に対して経済的な低速Ｒ
ＡＭを用いて利用でき、または磁気ディスク転送に対し
て超高速ＲＡＭを用いて利用できる。

【０００６】データ圧縮装置およびデータ伸長装置の設
計におけるもう一つの重要な基準は、圧縮有効度であ
る。圧縮有効度は装置の圧縮比によって特徴づけられ
る。圧縮比は、圧縮された形のデータ記憶の大きさを圧
縮されていない形のデータ記憶の大きさで割った比であ
る。データが圧縮可能であるためには、そのデータは、
冗長度を含んでいなければならない。圧縮有効性は、圧
縮手順が入力データにおける冗長性のいろいろな形態に
いかに有効に調和するかによって決められる。代表的な
コンピュータに記憶されたデータ、例えば整数の配列、
テキストまたはプログラムなどにおいて、冗長性は個々
の記号表記法、例えば数字、バイトの不統一な使用と共
通語などの記号列、空白記録欄などの頻繁な繰返しの両
方において起こる。有効なデータ圧縮装置は、両方の形
式の冗長性に応じる必要がある。

【０００７】データ圧縮装置およびデータ伸長装置の設
計における別の重要な基準は、適応性の基準である。多
くの従来のデータ圧縮手段は、圧縮されようとするデー
タの以前の知識または統計を必要とする。従来の手順の
あるものは、データが受けられるときのデータの統計に
適用する。従来の処理における適応性は、法外な複雑度
を必要とした。普通には、汎用コンピュータ施設におけ
る必要条件である広範囲の情報形式にわたって適応圧縮
および伸長装置を用いることができる。圧縮装置は、デ
ータ統計の以前の知識がなくても良好な圧縮比を達成す
ることが望ましい。現在利用できるデータ圧縮手順およ
びデータ伸長手段は、一般には適応できないので、それ
を汎用用途には利用できない。

【０００８】データ圧縮装置およびデータ伸長装置の設
計におけるもう一つの重要な基準は、可逆性の基準であ
る。データ圧縮装置が可逆性の性質をもつためには、そ
の装置は、圧縮されたデータを情報の変質または損失な
しにその元の形に再拡張または伸長することができなけ
ればならない。伸長されたデータと元のデータとは同一
であって互いに区別できないものでなければならない。

【０００９】適応性のあるようにされているか、または
適応性のあるようにされる可能性のある汎用データ圧縮
手段が従来技術において知られており、二つの該当する
手順は、ハフマン（Ｈｕｆｆｍａｎ）法およびタンスタ
ル（Ｔｕｎｓｔａｌｌ）法である。ハフマン法は広く知
られて用いられており、それに関してはハフマンの「最
小冗長性コードの構成のための方法」という論文［プロ
シーディングスＩＲＥ、第４０巻、第１０号、１０９８
〜１１００頁（１９５２年９月）］に出ている。さらハ
フマンの方法については、Ｒ．ガラハ（Ｇａｌｌａｇｈ
ｅｒ）の「ハフマンによる論文についての変形」という
論文［ＩＥＥＥ情報理論トランザクションズ，ＩＴ−２
４，Ｎｏ．６（１９７８年１１月）］に見ることができ
る。適応ハフマン・コーディングは、固定長の記号列を
可変長さ２進語に写像する。適応ハフマン・コーディン
グは、その方法が解釈できる固定列長より長い入力記号
列内に冗長があるとき、それが有効でないという限界を
もっているという欠点がある。ハフマン法を実際に装置
として具体化するときは、入力列長は、ＲＡＭの価格の
ために１２ビットを超えることは殆どないので、この方
法は、一般は良好な圧縮比を達成しない。なお、適応ハ
フマン法は複雑で、各入力記号に対して法外に多数の記
憶サイクルを必要とすることが多い。従って、適応ハフ
マン法は、望ましくないほどわずらわしく、高価でかつ
遅い傾向があるために、この方法を実際的な現在の設備
のほとんどに適さなくしている。

【００１０】タンスタルの方法については、Ｂ．Ｔ．タ
ンスタルの「雑音のない圧縮コードの合成」という題名
の博士論文、［ジョージア・インスティチュート・オブ
・テクノロジ（１９６７年９月）］に見ることができ
る。タンスタルの方法は、可変長の入力記号列を固定長
の２進出力語に写像する。タンスタル法の適応形は、従
来技術に記載されていないが、一つの適応形を誘導でき
る可能性はあるものの、それは複雑で高性能の装置にす
るには不適切であろう。ハフマン法もタンスタル法も原
始記号の組合せの長さが段々長くなると符号化すること
ができなくなる。

【００１１】従来技術の欠点の多くを克服するさらに別
の適応データ圧縮および伸長装置は、Ｍ．コーイン（Ｃ
ｏｈｅｎ）、Ｗ．イーストマン（Ｅａｓｔｍａｎ）、
Ａ．レンペル（Ｌｅｍｐｅｌ）およびＪ．ジブ（Ｚｉ
ｖ）の米国特許第４，４６４，６５０号（データの圧縮
と圧縮されたデータの伸長の装置と方法」（１９８１年
８月１０日出願）に開示されたものである。前記米国特
許第４，４６４，６５０号の方法は入力データの記号の
ストリームを記号の適応増大する列に分解する。前記特
許第４，４６４，６５０号の方法は、入力文字ごとに多
数のＲＡＭサイクルを必要として、圧縮および伸長を行
うために乗算および除算のような時間のかかる複雑な数
学的手順を用いるという欠点をもっている。これらの欠
点は、前記特許第４，４６４，６５０号の方法を多くの
経済的で高性能の装置として実現するのに不適当にする
傾向がある。前述のことから従来技術も前記米国特許第
４，４６４，６５０号の方法も高性能のアプリケーショ
ンに適する適応性があり、かつ効率的な圧縮装置を提供
しないことがわかる。既知の従来の設計アプローチは、
そのような装置には直接には適当ではない。

【００１２】したがって、本発明の目的は、上述した装
置の欠点を除去したデータの圧縮装置及び方法を提供す
ることにある。

【００１３】

【課題を解決するための手段】本発明は上述の装置の欠
点を除去し、良好な圧縮比を達成することのできる経済
的で高性能で適応性があり、可逆的なデータ圧縮の装置
及び方法を提供することによって克服する。

【００１４】本発明の第１の形態は、データ文字信号の
ストリームを圧縮された符号信号ストリームに圧縮する
圧縮装置であって、前記データ文字信号のストリーム中
において遭遇するデータ文字信号のストリングをストア
し、前記ストアされたストリングは、当該ストアされた
ストリングにそれぞれ関連する符号信号を有し、および
該符号信号に対応するメモリアドレスにストアされるよ
うになしたアドレス可能なメモリと、前記ストリームを
前記メモリ内にストアされたストリングと比較して、前
記データ文字信号ストリームをサーチして前記ストリー
ムとの最長一致を決定し、前記最長一致中のデータ文字
信号の個数に応じて１または２以上のメモリアドレスに
アクセスして最長一致を決定する手段と、前記最長一致
に続く次のデータ文字信号で拡張された前記データ文字
信号ストリームとの最長一致を含む拡張されたストリン
グを形成する手段と、前記拡張されたストリングに符号
信号を割り当てる手段と、前記拡張されたストリングを
前記メモリ内の、割り当てられた符号信号に対応するメ
モリアドレスにストアする手段と、前記最長一致に関連
する符号信号を供給して前記圧縮された符号信号ストリ
ームを供給する手段とを具えたことを特徴とする。

【００１５】また、本発明は、最長一致を決定する際に
前記サーチする手段によりアクセスされる各メモリアド
レスは、より長い一致があるか否かを決定するために前
記サーチする手段によって用いられるデータを含むこと
を特徴とする。

【００１６】また、本発明は、前記サーチする手段によ
って、アクセスされたメモリアドレス内にストアされた
データを前記ストリームからのデータ文字信号と共に用
いて、より長い一致が存在するときにはそのより長い一
致に対応するメモリアドレスを決定することを特徴とす
る。

【００１７】また、本発明は、ストリングを前記メモリ
に間接的にストアすることを特徴とする。

【００１８】また、本発明は、拡張されたストリング
は、前記最長一致の少なくとも表示をストアすることに
よってメモリアドレスにストアされることを特徴とす
る。

【００１９】また、本発明は、前記サーチする手段は、
先に定めた最長一致に続く次のデータ文字信号で始まる
次に生じる最長一致に対するサーチを実行することを特
徴とする。

【００２０】本発明の第２の形態は、データ文字信号の
ストリームを圧縮された符号信号ストリームに圧縮する
圧縮装置であって、前記データ文字信号のストリーム中
において遭遇するデータ文字信号のストリングをストア
し、前記ストアされたストリングは、当該ストアされた
ストリングにそれぞれ関連する符号信号を有するストア
手段と、複数の予め定めたストリングを前記ストア手段
内に最初にストアし、前記データ文字信号のストリーム
の圧縮の開始前に、ストアされたストリングに対応する
符号信号を前記ストリングに割り当てる手段と、前記ス
トリームを該ストア手段内にストアされたストリングと
比較することによって、前記データ文字信号のストリー
ムをサーチして前記ストリームとの最長一致を決定する
手段と、前記ストア手段にストアするために、前記最長
一致に続く次のデータ文字信号によって拡張された前記
データ文字信号のストリームとの前記最長一致を含む拡
張されたストリングを前記ストア手段に挿入する手段
と、前記ストアされた拡張されたストリングに対応する
符号信号を割り当てる手段と、前記最長一致に関連する
符号信号を供給して前記圧縮された符号信号のストリー
ムを供給する手段とを具えたことを特徴とする。

【００２１】また、本発明は、前記メモリ内に最初にス
トアされた予め定めたストリングは単一データ文字信号
を含むことを特徴とする。

【００２２】また、本発明は、前記単一データ文字信号
はデータ文字のアルファベットの文字に対応することを
特徴とする。

【００２３】また、本発明は、前記アルファベットの文
字値に基づいて、符号信号を前記データ文字のアルファ
ベットに割り当てられることを特徴とする。

【００２４】また、本発明は、前記データ文字はASCII
文字であり、および符号信号をASCII 値に基づいて前記
ASCII 文字に割り当てることを特徴とする。

【００２５】本発明の第３の形態は、データ文字信号の
ストリームを圧縮された符号信号ストリームに圧縮する
圧縮装置であって、前記データ文字信号のストリーム中
において遭遇するデータ文字信号のストリングをストア
し、前記ストアされたストリングは、当該ストアされた
ストリングにそれぞれ関連する符号信号を有するストア
手段と、前記ストリームを前記ストア手段内にストアさ
れたストリングと比較することによって、前記データ文
字信号のストリームをサーチして前記ストリームとの最
長一致を決定する手段と、前記ストア手段にストアする
ために、前記最長一致に続く次のデータ文字信号によっ
て拡張された前記データ文字信号のストリームとの前記
最長一致を含む拡張されたストリングを前記ストア手段
に挿入する手段と、可変長の符号信号を供給する手段を
有し、前記ストアされた拡張されたストリングに対応す
る符号信号を割り当てる手段と、前記最長一致に関連す
る符号信号を供給して前記圧縮された符号信号ストリー
ムを供給する手段とを具えたことを特徴とする。

【００２６】本発明の第４の形態は、データ文字信号の
ストリームを圧縮された符号信号ストリームに圧縮する
圧縮装置であって、前記データ文字信号のストリーム中
において遭遇するデータ文字信号のストリングをストア
し、前記ストアされたストリングは、当該ストアされた
ストリングにそれぞれ関連する符号信号を有するストア
手段と、前記ストリームを前記ストア手段内にストアさ
れたストリングと比較することによって、前記データ文
字信号のストリームをサーチして前記ストリームとの最
長一致を決定する手段と、前記ストア手段にストアする
ために、前記最長一致に続く次のデータ文字信号によっ
て拡張された前記データ文字信号のストリームとの前記
最長一致を含む拡張されたストリングを前記ストア手段
に挿入する手段と、固定長の符号信号を供給する手段を
有し、前記ストアされた拡張されたストリングに対応す
る符号信号を割り当てる手段と、前記最長一致に関連す
る符号信号を供給して前記圧縮された符号信号ストリー
ムを供給する手段とを具えたことを特徴とする。

【００２７】本発明の第５の形態は、データ文字信号の
ストリームを圧縮された符号信号ストリームに圧縮する
圧縮装置であって、前記データ文字信号のストリーム中
において遭遇するデータ文字信号のストリングをストア
し、前記ストアされたストリングは、当該ストアされた
ストリングにそれぞれ関連する符号信号を有するストア
手段と、前記ストリームを前記ストア手段内にストアさ
れたストリングと比較することによって、前記データ文
字信号のストリームをサーチして前記ストリームとの最
長一致を決定する手段と、前記ストア手段にストアする
ために、前記最長一致に続く次のデータ文字信号によっ
て拡張された前記データ文字信号のストリームとの前記
最長一致を含む拡張されたストリングを前記ストア手段
に挿入する手段と、符号信号を数値の昇順に割り当てる
手段を有し、前記ストアされた拡張されたストリングに
対応する符号信号を割り当てる手段と、前記最長一致に
関連する符号信号を供給して前記圧縮された符号信号ス
トリームを供給する手段とを具えたことを特徴とする。

【００２８】本発明の第６の形態は、データ文字信号の
ストリームを圧縮された符号信号ストリームに圧縮する
圧縮装置であって、前記データ文字信号のストリーム中
において遭遇するデータ文字信号のストリングをストア
し、前記ストアされたストリングは、当該ストアされた
ストリングにそれぞれ関連する符号信号を有するストア
手段と、前記ストリームを前記ストア手段内にストアさ
れたストリングと比較することによって、前記データ文
字信号のストリームをサーチして前記ストリームとの最
長一致を決定する手段と、前記ストア手段にストアする
ために、前記最長一致に続く次のデータ文字信号によっ
て拡張された前記データ文字信号のストリームとの前記
最長一致を含む拡張されたストリングを前記ストア手段
に挿入する手段と、前記最長一致に関連する符号信号を
供給して前記圧縮された符号信号ストリームを供給する
手段とを具え、前記サーチ手段は、前記データ文字信号
のストリームを繰り返して分析するよう動作して前記ス
トア手段内にストアされたストリングとの最長一致を決
め、次の最長一致のための各サーチは、先行する最長一
致に続く次のデータ文字信号で始まることを特徴とす
る。

【００２９】また、本発明は、前記データ文字信号のス
トリームの圧縮が前記データ文字信号のストリームの単
一のパスにおいて達成されることを特徴とする。

【００３０】また、本発明は、前記圧縮装置により行わ
れる圧縮は無損失であることを特徴とする。

【００３１】本発明の第７の形態は、データ文字信号の
ストリームを圧縮された符号信号ストリームに圧縮する
圧縮装置であって、前記データ文字信号のストリーム中
において遭遇するデータ文字信号のストリングをストア
し、前記ストアされたストリングは、当該ストアされた
ストリングにそれぞれ関連する符号信号を有するストア
手段と、前記ストリームを前記ストア手段内にストアさ
れたストリングと比較することによって、前記データ文
字信号のストリームをサーチして前記ストリームとの最
長一致を決定する手段と、前記ストア手段にストアする
ために、前記最長一致に続く次のデータ文字信号によっ
て拡張された前記データ文字信号のストリームとの前記
最長一致を含む拡張されたストリングを前記ストア手段
に挿入する手段と、前記ストアされた拡張されたストリ
ングに対応する符号信号を割り当てる手段と、前記最長
一致に関連する符号信号を供給して前記圧縮された符号
信号のストリームを供給する手段と、前記データ文字信
号のストリームのサーチが当該ストリームの終端に達し
たか否かを決定するための手段とを具えたことを特徴と
する。

【００３２】また、本発明は、前記サーチが前記データ
文字信号のストリームの終端に達すると、前記データ文
字信号のストリーム中の最後のデータ文字ストリングに
対応する符号値が前記圧縮されたストリームでの使用の
ため供給されることを特徴とする。

【００３３】また、本発明は、前記サーチが前記データ
文字信号のストリームの終端に達したことに応答して、
ストリームの終端の表示が提供されることを特徴とす
る。

【００３４】本発明の第８の形態は、データ文字信号の
ストリームを圧縮された符号信号ストリームに圧縮する
圧縮装置であって、前記データ文字信号のストリーム中
において遭遇するデータ文字信号のストリングをストア
し、前記ストアされたストリングは、当該ストアされた
ストリングにそれぞれ関連する符号信号を有するストア
手段と、前記ストリームを前記ストア手段内にストアさ
れたストリングと比較することによって、前記データ文
字信号のストリームをサーチして前記ストリームとの最
長一致を決定する手段と、前記ストア手段にストアする
ために、前記最長一致に続く次のデータ文字信号によっ
て拡張された前記データ文字信号のストリームとの前記
最長一致を含む拡張されたストリングを前記ストア手段
に挿入する手段と、前記ストアされた拡張されたストリ
ングに対応する符号信号を割り当てる手段と、前記最長
一致に関連する符号信号を供給して前記圧縮された符号
信号のストリームを供給する手段と、前記圧縮装置によ
り行われた圧縮を変化させる手段とを具えたことを特徴
とする。

【００３５】また、本発明は、前記圧縮を変化させる手
段は圧縮比を変化させることを特徴とする。

【００３６】また、本発明は、前記圧縮を変化させる手
段は圧縮速度を変化させることを特徴とする特許請求の
範囲第２１項に記載の装置。

【００３７】本発明の第９の形態は、データ文字信号の
ストリームを圧縮された符号信号ストリームに圧縮する
圧縮装置であって、前記データ文字信号のストリーム中
において遭遇するデータ文字信号のストリングをストア
し、前記ストアされたストリングは、当該ストアされた
ストリングにそれぞれ関連する符号信号を有するストア
手段と、前記ストリームを前記ストア手段内にストアさ
れたストリングと比較することによって、前記データ文
字信号のストリームをサーチして前記ストリームとの最
長一致を決定する手段と、前記ストア手段にストアする
ために、前記最長一致に続く次のデータ文字信号によっ
て拡張された前記データ文字信号のストリームとの前記
最長一致を含む拡張されたストリングを前記ストア手段
に挿入する手段と、前記ストアされた拡張されたストリ
ングに対応する符号信号を割り当てる手段と、前記最長
一致に関連する符号信号を供給して前記圧縮された符号
信号のストリームを供給する手段と、前記サーチする手
段の動作を中断する手段とを具えたことを特徴とする。

【００３８】本発明の第１０の形態は、データ文字信号
のストリームを圧縮された符号信号ストリームに圧縮す
る圧縮方法であって、前記データ文字信号のストリーム
中において遭遇するデータ文字信号のストリングをアド
レス可能なメモリにストアし、前記ストアされたストリ
ングは、当該ストアされたストリングにそれぞれ関連す
る符号信号を有し、および前記ストリングを該符号信号
に対応するメモリアドレスにストアするステップと、前
記ストリームを前記メモリ内にストアされたストリング
と比較して、前記データ文字信号ストリームをサーチし
て前記ストリームとの最長一致を決定し、前記最長一致
中のデータ文字信号の個数に応じて1 または2 以上のメ
モリアドレスにアクセスして最長一致を決定するステッ
プと、前記最長一致に続く前記次のデータ文字で拡張さ
れた前記データ文字信号のストリームとの最長一致を含
む拡張されたストリングを形成するステップと、前記拡
張されたストリングに符号信号を割り当てるステップ
と、前記拡張されたストリングを前記メモリ内の、割り
当てられた符号信号に対応するメモリアドレスにストア
するステップと、前記最長一致に関連する符号信号を供
給して圧縮された前記符号信号ストリームを供給するス
テップとを具えたことを特徴とする。

【００３９】また、本発明は、最長一致を決定する際に
サーチしている間にアクセスされる各メモリアドレス
は、より長い一致があるか否かを決定するために前記サ
ーチによって用いられるデータを含むことを特徴とす
る。

【００４０】また、本発明は、サーチの間、アクセスさ
れたメモリアドレス内にストアされたデータを前記スト
リームからのデータ文字信号と共に用いて、より長い一
致が存在するときにはその長い一致に対応するメモリア
ドレスを決定することを特徴とする。

【００４１】また、本発明は、ストリングを前記メモリ
に間接的にストアすることを特徴とする。

【００４２】また、本発明は、拡張されたストリング
は、前記最長一致の少なくとも表示をストアすることに
よってメモリアドレスにストアされることを特徴とす
る。

【００４３】また、本発明は、前記サーチするステップ
は、先に定めた最長一致に続く次のデータ文字信号で始
まる次に生じる最長一致に対するサーチを実行すること
を特徴とする。

【００４４】本発明の第１１の形態は、データ文字信号
のストリームを圧縮された符号信号ストリームに圧縮す
る圧縮方法であって、前記データ文字信号のストリーム
中において遭遇するデータ文字信号のストリングをスト
ア手段にストアし、前記ストアされたストリングは、当
該ストアされたストリングにそれぞれ関連する符号信号
を有するステップと、複数の予め定めたストリングを前
記ストア手段に最初にストアし、および前記データ文字
信号のストリームの圧縮を始める前に対応する符号信号
を前記ストリングに割り当てるステップと、前記ストリ
ームを前記ストア手段内にストアされたストリングと比
較して、前記データ文字信号のストリームをサーチして
前記ストリームとの最長一致を決定するステップと、前
記ストア手段にストアするために、前記最長一致に続く
次のデータ文字信号によって拡張された前記データ文字
信号のストリームとの前記最長一致を含む拡張されたス
トリングを前記ストア手段に挿入するステップと、前記
ストアされた拡張されたストリングに対応する符号信号
を割り当てるステップと、前記最長一致に関連する符号
信号を供給して前記圧縮された符号信号ストリームを供
給するステップとを具えたことを特徴とする。

【００４５】また、本発明は、前記メモリ内に最初にス
トアされた予め定めたストリングは単一データ文字信号
を含むことを特徴とする。

【００４６】また、本発明は、前記単一データ文字はデ
ータ文字のアルファベットの文字に対応することを特徴
とする。

【００４７】また、本発明は、前記アルファベットの文
字値に基づいて、符号信号を前記データ文字のアルファ
ベットに割り当てることを特徴とする。

【００４８】また、本発明は、前記データ文字はASCII
文字であり、および符号信号をASCII 値に基づいて前記
ASCII 文字に割り当てることを特徴とする。

【００４９】本発明の第１２の形態は、データ文字信号
ストリームを圧縮された符号信号ストリームに圧縮する
圧縮方法であって、前記データ文字信号のストリーム中
において遭遇するデータ文字信号のストリングをストア
手段にストアし、前記ストアされたストリングは、当該
ストアされたストリングにそれぞれ関連する符号信号を
有するステップと、前記ストリームを前記ストア手段内
にストアされたストリングと比較して、前記データ文字
信号のストリームをサーチして前記ストリームとの最長
一致を決定するステップと、前記ストア手段にストアす
るために、前記最長一致に続く次のデータ文字信号によ
って拡張された前記データ文字信号のストリームとの前
記最長一致を含む拡張されたストリングを前記ストア手
段に挿入するステップと、前記ストアされた拡張された
ストリングに対応する符号信号を割り当て、その割り当
てられた符号信号は可変長であるステップと、前記最長
一致に関連する符号信号を供給して前記圧縮された符号
信号ストリームを供給するステップとを具えたことを特
徴とする。

【００５０】本発明の第１３の形態は、データ文字信号
ストリームを圧縮された符号信号ストリームに圧縮する
圧縮方法であって、前記データ文字信号のストリーム中
において遭遇するデータ文字信号のストリングをストア
手段にストアし、前記ストアされたストリングは、当該
ストアされたストリングにそれぞれ関連する符号信号を
有するステップと、前記ストリームを前記ストア手段内
にストアされたストリングと比較して、前記データ文字
信号のストリームをサーチして前記ストリームとの最長
一致を決定するステップと、前記ストア手段にストアす
るために、前記最長一致に続く次のデータ文字信号によ
って拡張された前記データ文字信号のストリームとの前
記最長一致を含む拡張されたストリングを前記ストア手
段に挿入するステップと、前記ストアされた拡張された
ストリングに対応する符号信号を割り当て、その割り当
てられた符号信号は固定長であるステップと、前記最長
一致に関連する符号信号を供給して前記圧縮された符号
信号ストリームを供給するステップとを具えたことを特
徴とする。

【００５１】本発明の第１４の形態は、データ文字信号
ストリームを圧縮された符号信号ストリームに圧縮する
圧縮方法であって、前記データ文字信号のストリーム中
において遭遇するデータ文字信号のストリングをストア
手段にストアし、前記ストアされたストリングは、当該
ストアされたストリングにそれぞれ関連する符号信号を
有するステップと、前記ストリームを前記ストア手段内
にストアされたストリングと比較して、前記データ文字
信号のストリームをサーチして前記ストリームとの最長
一致を決定するステップと、前記ストア手段にストアす
るために、前記最長一致に続く次のデータ文字信号によ
って拡張された前記データ文字信号のストリームとの前
記最長一致を含む拡張されたストリングを前記ストア手
段に挿入するステップと、前記ストアされた拡張された
ストリングに対応し、数値の昇順で割り当てられる符号
信号を割り当てるステップと、前記最長一致に関連する
符号信号を供給して前記圧縮された符号信号ストリーム
を供給するステップとを具えたことを特徴とする。

【００５２】本発明の第１５の形態は、データ文字信号
ストリームを圧縮された符号信号ストリームに圧縮する
圧縮方法であって、前記データ文字信号のストリーム中
において遭遇するデータ文字信号のストリングをストア
手段にストアし、前記ストアされたストリングは、当該
ストアされたストリングにそれぞれ関連する符号信号を
有するステップと、前記ストリームを前記ストア手段内
にストアされたストリングと比較して、前記データ文字
信号のストリームをサーチして前記ストリームとの最長
一致を決定するステップと、前記ストア手段にストアす
るために、前記最長一致に続く次のデータ文字信号によ
って拡張された前記データ文字信号のストリームとの前
記最長一致を含む拡張されたストリングを前記ストア手
段に挿入するステップと、前記最長一致に関連する符号
信号を供給して前記圧縮された符号信号ストリームを供
給するステップとを具え、前記サーチを行うステップ
は、前記データ文字信号のストリームにおけるデータ文
字を繰り返して分析するよう動作して前記ストア手段内
にストアされたストリングとの最長一致を決め、次の最
長一致のための各サーチは、先行する最長一致に続く次
のデータ文字信号で始まることを特徴とする。

【００５３】また、本発明は、前記データ文字信号のス
トリームの圧縮は前記データ文字信号のストリームの単
一のパスにおいて達成されることを特徴とする。

【００５４】また、本発明は、前記圧縮方法により行わ
れる圧縮は無損失であることを特徴とする。

【００５５】本発明の第１６の形態は、データ文字信号
ストリームを圧縮された符号信号ストリームに圧縮する
圧縮方法であって、前記データ文字信号のストリーム中
において遭遇するデータ文字信号のストリングをストア
手段にストアし、前記ストアされたストリングは、当該
ストアされたストリングにそれぞれ関連する符号信号を
有するステップと、前記ストリームを前記ストア手段内
にストアされたストリングと比較して、前記データ文字
信号のストリームをサーチして前記ストリームとの最長
一致を決定するステップと、前記ストア手段にストアす
るために、前記最長一致に続く次のデータ文字信号によ
って拡張された前記データ文字信号のストリームとの前
記最長一致を含む拡張されたストリングを前記ストア手
段に挿入するステップと、前記ストアされた拡張された
ストリングに対応する符号信号を割り当てるステップ
と、前記最長一致に関連する符号信号を供給して前記圧
縮された符号信号ストリームを供給するステップと、前
記データ文字信号のストリームのサーチが当該ストリー
ムの終端に達したか否かを決定するためのステップとを
具えたことを特徴とする。

【００５６】また、本発明は、前記サーチが前記データ
文字信号のストリームの終端に達すると、前記データ文
字信号のストリームの最後のデータ文字ストリングに対
応する符号値が前記圧縮されたストリームでの使用のた
め供給されることを特徴とする。

【００５７】また、本発明は、前記サーチが前記データ
文字信号のストリームの終端に達したことに応答して、
ストリームの終端の表示が提供されることを特徴とす
る。

【００５８】本発明の第１７の形態は、データ文字信号
ストリームを圧縮された符号信号ストリームに圧縮する
圧縮方法であって、前記データ文字信号のストリーム中
において遭遇するデータ文字信号のストリングをストア
手段にストアし、前記ストアされたストリングは、当該
ストアされたストリングにそれぞれ関連する符号信号を
有するステップと、前記ストリームを前記ストア手段内
にストアされたストリングと比較して、前記データ文字
信号のストリームをサーチして前記ストリームとの最長
一致を決定するステップと、前記ストア手段にストアす
るために、前記最長一致に続く次のデータ文字信号によ
って拡張された前記データ文字信号のストリームとの前
記最長一致を含む拡張されたストリングを前記ストア手
段に挿入するステップと、前記ストアされた拡張された
ストリングに対応する符号信号を割り当てるステップ
と、前記最長一致に関連する符号信号を供給して前記圧
縮された符号信号ストリームを供給するステップと、前
記圧縮方法により行われた圧縮を変化させるステップと
を具えたことを特徴とする。

【００５９】また、本発明は、前記変化させるステップ
は圧縮比を変えることを含むことを特徴とする。

【００６０】また、本発明は、前記変化させるステップ
は圧縮の速度を変えることを含むことを特徴とする。

【００６１】本発明の第１８の形態は、データ文字信号
ストリームを圧縮された符号信号ストリームに圧縮する
圧縮方法であって、前記データ文字信号のストリーム中
において遭遇するデータ文字信号のストリングをストア
手段にストアし、前記ストアされたストリングは、当該
ストアされたストリングにそれぞれ関連する符号信号を
有するステップと、前記ストリームを前記ストア手段内
にストアされたストリングと比較して、前記データ文字
信号のストリームをサーチして前記ストリームとの最長
一致を決定するステップと、前記ストア手段にストアす
るために、前記最長一致に続く次のデータ文字信号によ
って拡張された前記データ文字信号のストリームとの前
記最長一致を含む拡張されたストリングを前記ストア手
段に挿入するステップと、前記ストアされた拡張された
ストリングに対応する符号信号を割り当てるステップ
と、前記最長一致に関連する符号信号を供給して前記圧
縮された符号信号ストリームを供給するステップと、圧
縮の動作を中断することを提供するステップとを具えた
ことを特徴とする。

【００６２】本発明は、入力データ・ストリームからパ
ース（構文解析して分解すること）されたデータ文字信
号のストリングを格納（ストア）し、そのストリームと
の最長一致を決めるために、そのストリームを格納され
たストリングと比較してデータ文字信号のストリームを
探索（サーチ）することによって、データ文字信号のス
トリームを符号信号の圧縮されたストリームに圧縮す
る。この圧縮装置はまた、データ文字信号のストリーム
からの最長一致を含み最長一致に続く次の一つのデータ
文字信号によって拡張された拡張ストリングを格納す
る。最長一致を拡張して格納するとき、格納された拡張
ストリングに対応する符号信号がそれに割当てられる。
符号信号の圧縮されたストリームは、格納された最長一
致に対応する符号信号で作られる。データ文字の格納さ
れたストリングが接頭部ストリングと拡張文字で構成さ
れる。ストリングがその接頭部ストリングに対応する符
号信号によって格納される。

【００６３】符号信号の圧縮されたストリームは、接頭
符号信号および拡張文字信号を含む文字ストリングを構
成して格納することによって伸長される。伸長装置は、
受けられた符号信号によるストリングと次に続くストリ
ングの最初の文字として受けられる拡張文字とを格納す
る。

【００６４】データ文字信号のストリングは、各探索繰
返しに対する限られた数のハッシュアドレスを与える限
定探索ハッシング技術によって記憶装置に入れられる。

【００６５】

【発明の実施の形態】本発明はデジタルデータ文字信号
のストリームまたは列を圧縮して、圧縮されたディジタ
ル符号信号の対応するストリームを与えるデータ圧縮装
置を備えている。例えば、圧縮される予定のデータは、
英語の原文資料、格納されたコンピュータ記録などを含
んでいてもよい。今日のデータ処理装置および通信装置
においては、圧縮を行われるはずのアルファベットの文
字は、処理されてＡＳＣＩＩフォーマットのような都合
のよいコードで２進数字のバイトとして伝達されること
がわかっている。例えば、入力文字を８ビット・バイト
の形式で２５６文字の文字体系全体を受けることができ
る。圧縮装置からの圧縮符号信号は、例えば、記録保管
の目的のために電子記憶ファイルに格納されるか、また
は伸長を行う遠隔の場所に伝送されてもよい。このほか
に、ディスク記憶装置のような電子記憶ファイルが入力
電子回路に圧縮装置を備え、出力電子回路に伸長装置を
備えることができ、それによってファイルに入るすべて
のデータを記憶するために圧縮して、ファイルから検索
されたすべてのデータを利用機器に伝送する前に伸長す
る。前述の従来の圧縮装置および伸長装置は、圧縮およ
び伸長のそのような用途に適合させる性能または適応性
を与えない。本発明に従って実施された高性能適応装置
をそのように用いることができる。

【００６６】多数の設計オプションが被圧縮データおよ
び装置の所望の特性に従う種々の組合せで本発明の実施
例に用いることができる。発明の三つの実施例を以下に
説明する。一つの実施例は、最高性能を与えるオプショ
ンを組合せており、第２の実施例は、最高圧縮を与える
オプションを組合せており、第３の実施例は、最高性能
実施例のプログラムされたコンピュータの例を提供す
る。

【００６７】本発明の圧縮装置は、データ文字の入力ス
トリームをストリングまたはセグメントにパースして、
各ストリングを識別する符号信号を伝送する。圧縮装置
が初めて遭遇したデータ文字以外は、各パースされたス
トリングは、前に認識されたストリングに対する最長一
致を含んでいる。圧縮装置は、認識されたストリングに
対応する符号信号を伝送する。１ストリングの文字が入
力ストリームからパースされると、パースされたストリ
ングは、入力ストリームにおいて次に発生する文字によ
って拡張され、あとで符号化に利用されるために圧縮装
置において符号化され、そこに記憶される拡張ストリン
グを形成する。従って認識されている文字シーケンス
は、１ブロックのデータを圧縮する過程で統計的情報を
集めるとき、平均長さがたえず大きくなっている。拡張
文字は、次のパーシング繰返しにおける最初の文字とし
て用いられる。パーシングは、データを１回通すだけで
達成され、初めの文字から出発して、１回の１文字を分
離する。従って、単一文字のストリング以外は、各スト
リングは、前に記憶されたストリングと一致する接頭部
ストリングと拡張文字として記憶される。そのストリン
グは、そのような各ストリングを接頭部の符号信号表現
と拡張文字の実際の表現または暗示表現を一緒にして記
録するのが都合よい。パーシングは、データ・ストリー
ムの各文字間に仮想コンマを挿入し、それによってパー
スされたストリングまたはセグメントを区切るものとし
て概念化できる。従って、本発明においては、一致を得
るための未処理のデータストリームの探索は、先に観察
されたストリングとの最長一致を見出すために一つのコ
ンマから次に続くコンマを一文字越えたところまでを探
索することを含む。

【００６８】図１を参照すると、データ文字のストリー
ムの一部分の略図が示されており、そこではＸがアルフ
ァベットの任意の文字を表している。コンマは、パーシ
ングを表すためにのみデータストリーム中に示されてい
る。このデータストリームのストリング１が仮想コンマ
２および３によってパースされている。ストリング１は
前のストリング１´に一致し、ストリング１´はコンマ
２に続く入力データストリームに一致するコンマ２に先
行した最長拡張ストリングである。ストリング１´は、
前に符号化されたものであるから、その符号は、ストリ
ング１に遭遇したとき圧縮装置によって伝送される。次
いで圧縮装置は、接頭部ストリング１と拡張文字５を含
む拡張ストリング４を符号化して記憶する。拡張文字
は、それがどんな文字であるかに関係なく、接頭部１に
続くデータストリームの中の次の文字である。すなわ
ち、拡張文字５は、前に、データストリームの中で現れ
た文字であってもよいし、またはそれは初めて遭遇する
アルファベットの１文字であってもよい。

【００６９】圧縮装置は、もう一度最長一致が達成され
るまで拡張文字５で始まる次のパーシングの繰返しを仮
想コンマ３のところで開始する。このようにして、前に
拡張されたストリング６´にマッチするストリング６が
パースされる。前の繰返しにおけると同じようにまた、
ストリング６´に対する符号信号は、伝送され、ストリ
ング６は後続の文字によって拡張され、拡張されたスト
リングは、符号化されて記憶される。続くパーシング繰
返しにおいては、符号化されて記憶されたストリング４
にマッチするストリング７がパースされる。このパーシ
ング繰返しで伝送された符号信号は、拡張ストリング４
に割当てられたものである。

【００７０】上述のように、圧縮装置によって与えられ
た符号信号は、引続く伸長のために記憶または伝送する
ことができる。

【００７１】本発明において、入力バイトの各シーケン
スが実施例次第で固定長または可変長のものであっても
よい符号信号に圧縮される。上述のように、各入力バイ
ト列は、各符号識別子を割当てられ、一つの列が入力デ
ータ・ストリームの中で再び出てくるときはいつも、同
じ識別子が再び伝送される。各１バイト列が各符号を割
当てられ、一つの列が再び出てくるときはいつも、１バ
イトだけ拡張され、新しい符号が拡張されたシーケンス
に割当てられる。概念的には、圧縮装置は、各データブ
ロックを格納されたセット内のゼロストリングのみから
開始する。圧縮装置は、新しい文字が出てくるたびにそ
のセットに１文字のストリングを入れ、次にこれらの記
憶された１文字ストリングをさらに長いストリングを形
成するのに用いる。各ストリングがそのセットに加えら
れると、それは、一つの符号信号を割当てられる。入力
からの一つの文字ストリングがセット内で見出される度
に、次の入力文字がそのストリングに追加され、拡張さ
れたストリングがそのセットの中にあるかどうかを決め
るためにそのセットが探索される。拡張されたストリン
グが既に存在しなければ、そのストリングがセットに入
れられる。随意選択的に、そのストリングセットをすべ
ての単一文字ストリングを含むように初期設定できる。
これは、より高い性能の装置として実現できるようにに
することもあるが、ある程度の圧縮効率を失うことがあ
る。圧縮装置からの出力符号信号は、同一文字列が以前
に起こったことを示しているものとして考えることがで
きる。

【００７２】前記米国特許第４，４６４，６５０号のデ
ータ圧縮および伸長装置において、拡張文字が各認識さ
れた列に追加されて拡張された列が符号化された。拡張
列の符号化表現は、それの圧縮符号として圧縮装置によ
って伝送された。その代りに、本発明の圧縮装置は、拡
張列を記憶して、認識された列に対する符号を伝送す
る。認識された列は、拡張列の接頭部である。記憶され
た拡張列は、次にあとで符号化するために用いられる。
前記米国特許第４，４６４，６５０号の方法をこのよう
に変更すると、前記米国特許第４，４６４，６５０号に
おいて用いた時間のかかる、やっかいな数学的操作およ
び乗算・除算装置のような付随のハードウェアをなくす
ことによってデータ圧縮および伸長装置を著しく簡単に
することができる。この変更は、装置の性能を著しく高
めると同様にまた、普通に遭遇するデータの場合の圧縮
効率を増加させる。これは、前記米国特許第４，４６
４，６５０号の装置では、圧縮された符号信号の一部分
として伝送される拡張文字が等しく起こりそうな文字体
系のすべての記号に見合った多数のビットを含むからで
ある。本発明では、拡張文字は、次の圧縮ストリング符
号の一部分として伝送されるので、文字の各ストリング
について行われた圧縮に一致して必要とするビットの数
が少なくなる。

【００７３】本発明は、限定探索長の計算されたアドレ
ス・ハッシング装置を用いて各ストリングをストリング
・テーブルに入れ、そのストリング・テーブル内で各ス
トリングを探索する。ハッシング関数は、前の符号信号
と拡張文字とからなるハッシュ・キーを用いてＮ個のハ
ッシュ・テーブル・アドレスの組を与える（ここでＮは
普通１ないし４である）Ｎ個のＲＡＭ記憶場所は、逐次
に探索され、その項目がＮ個の記憶場所になければ、そ
れはそのテーブル内にないと考えられる。圧縮のとき
に、テーブルに挿入されるべき新しいキーをＮ個の割当
て場所に受入れできなければ、それはテーブルから除外
される。この限定探索ハッシング法は、圧縮効率をわず
かに下げるが、装置として実現するのを非常に簡単にす
る。Ｎ個のハッシュ・アドレスが反復したＲＡＭの中で
並列に探索される別の実施例を用いてもよい。

【００７４】本発明は、固定長または可変長の圧縮され
た符号信号を用いて装置として具体化することができ
る。固定長符号信号の実施例は、圧縮効率においてわず
かの損失を伴いながら装置として実現する場合の簡単化
をもたらす。固定長符号実施例は、ＲＡＭのスペース必
要度と可変符号長による装置としての実現に必要な符号
シフティング機構の複雑さを小さくする傾向がある。し
かし固定長符号による装置の実現は非常に高い性能の装
置の実現を行うときに望ましい。

【００７５】一般には、本発明は、入力文字信号の可変
ストリングを出力符号記号信号に写像することによって
圧縮を行う。圧縮装置は、ストリング・テーブル（ＲＡ
Ｍ）の中に圧縮装置が認識するストリングのリストを記
憶し、各ストリングに対しては対応する出力符号信号を
記憶する。そのように記憶されたストリングの組は、ど
んな一連の入力文字も記憶されるストリングにパースで
き、従って、出力符号に写像できるように構成される。
パーシングは、どの繰返しにおいてもストリング・テー
ブルの中に最長ストリングに一致するすべての連続する
入力文字を使いきり、対応する出力符号を伝送すること
によって達成される。最長一致は、次の入力文字によっ
て拡張され、ストリング・テーブルに記憶され、そして
対応する符号を割当てられる。

【００７６】従って、ストリング・テーブル内のストリ
ングの組を合成することは、現在のデータブロックの統
計に適応し、かつその統計の一つの表現法である。明確
にいえば、そのストリングの組に追加される各ストリン
グは、その組に既にある一つのストリングを１文字で拡
張したものである。一つのストリングがそのセットに加
えられるのは、それが実際に入力データにおいて観測さ
れたのちにおいてだけである。従って、一つの長いスト
リングがそのセット内に現れる可能性のあるのは、それ
が何度も出てきたので頻繁に再び現れると期待できる場
合だけである。このストリングセットは、できればラン
ダムアクセス記憶装置（ＲＡＭ）にテーブルとして記憶
されるのがよい。各ストリングは、連結トリー構造と考
えてもよいものに記憶される。各ストリングは、少なく
とも暗黙的にすなわち間接的に、その符号記号、そのス
トリングの最後の文字および最後の文字以外のすべての
ストリング文字を含むストリング接頭部の符号記号で記
憶される。各文字が個別に得られ、かつ各接頭部符号が
逐次に呼び出されるので、伸長装置は、一つのストリン
グを複合するときに多重ＲＡＭアクセスを用いる。

【００７７】各データ信号は、入力文字列に対する最長
一致を探すのを容易にするようなやり方でストリング・
テーブル内に記憶される。各入力文字が読まれると、そ
れが既に認識された一つのストリング（新しい列の始め
にゼロストリングで始まったもの）に付け加えられて、
その新しいストリングは、それがそのテーブルの中にあ
るかどうかを決めるために検査される。新しいストリン
グがそのテーブルの中にあれば、その符号が検索され
て、その処理が新しい文字と新しい符号とで繰返され
る。それらのストリングをそのように呼び出すために、
それらのストリングは、“接頭部符号、拡張文字”の組
（タブル）によって識別されるのが都合よい。限定探索
ハッシング装置がストリング・テーブルをくまなく探索
するのに用いられる。

【００７８】本発明を実施する際に用いることのできる
ハッシング装置は、一つの符号、文字組合わせに対して
一連の記憶アドレスを発生する関数ハッシュ（符号、文字）→アドレス１，アドレス２・・
・を含む。テーブルに一つのストリングを挿入すると、発
生したＲＡＭアドレスが空サイトを発見するまで逐次に
呼出され、項目がその点に挿入される。一つの項目を検
索するとき、同じアドレス列がその項目が発見されるか
または空サイトが発見されるまで呼出され、空サイトが
発見された場合にその項目はテーブルの中に存在しない
と定義される。各占有されたサイトにおいては、そのス
トリングのための識別用符号、文字の組は、そのサイト
を占有するものが所望の項目であるかどうかを決めるた
めに比較されてもよい。あとで説明する理由によって、
識別用符号を比較することは、実際には、この実施例で
必要なだけである。

【００７９】本発明で用いられたハッシュ関数において
は、取り出されて用いられたアドレスの数は、小さな一
定値Ｎ（Ｎは普通１ないし４である）に限定される。一
つの項目をＮ回の呼出しでストリング・テーブルに挿入
できなければ、その項目は用いられない。テーブルから
検索される予定の一つの項目がＮ回の呼出しの中で所在
をつきとめられなければ、それはテーブル内にないと定
義される。この限定探索の特徴は、圧縮効率の小さな損
失をもたらすが、性能を著しく増加させる。本発明はＢ
ビット・バイトの文字体系について圧縮を行うとして説
明する。本発明を実施する際に用いられるハッシュ関数
は、任意の一つの符号に関連したアドレスの組すなわち
２^B 拡張文字すべてに対するＮ個のアドレスすべてがど
のアドレスをも２回は含まない。従って、一つのアドレ
スが特定の符号、文字の組に対してアクセスされると、
その符号の比較はその記憶場所の占有物の識別を行うの
に十分である。その文字の値をＲＡＭに記憶する必要は
ない。従って、ＲＡＭのスペースは、ハッシュ関数のこ
の特徴のために保存される。なお、ハッシュ関数は、符
号または文字の連続する値を異常なほど激しく使っても
どの特定のアドレスの組をも使い過ぎることにはならな
いように設計される。これは同じ最初のアドレス値をも
つ任意の二つの符号、文字の組が同じ第２のアドレス値
をもたないことを確実にすることが可能であれば、それ
によって達成される。ハッシュ関数によって作られた幾
つかのアドレスを、二つの全く同じＲＡＭを同時に探索
して装置の性能をさらに高めることができるように並列
に与えてもよいことが分かるであろう。上記の基準を満
足する多くのハッシュ関数が本発明を実施するのに満足
に機能することになる。特定の適当なハッシュ関数を以
下に説明する。上記の基準を満足する他のハッシュ関数
を通常のやり方で導出できることがわかる。

【００８０】以下に説明する本発明の実施例において、
圧縮装置からの出力符号信号は、Ｃビットの公称語長
（２^C はストリング・テーブルの大きさ以下である）を
もつことになる。しかし、ストリング・テーブルが最初
に構成されようとしているとき、各ストリングを１回の
繰返しの間に利用できるものから選択するためには、Ｃ
より少ないビットを必要とする。最高の圧縮は、漸新的
に大きくなる出力符号をＣビットの限界まで伝送する場
合に達成される。このアプローチは、可変符号を固定バ
イト配向に整列させるのに追加の出力ハードウェアを用
いる。出力語長はまた新しい入力文字の認識に従って変
わることがある。以下に説明する実施例の一つにおい
て、一つの入力文字がまず出てくると常に、その文字そ
のもののビットパターンがあとに続くゼロ・ストリング
符号が与えられる。従って、これらの出力は正規のスト
リング符号よりいくらか長い。あとで説明するようにし
て、出力長のこの変動は、入力データを処理する前にす
べての単一文字ストリングを含むようにストリング・テ
ーブルを初期設定することによって避けられる。このア
プローチは、それがそうでない場合に必要な任意のビッ
ト・シフト・ハードウェアをなくすが、圧縮を小さくす
ることがある点で装置としての具体化の複雑性を簡単に
する。圧縮の低減は、未使用の単一文字に割当てられた
符号が有益に用いられ得ないが、すべての割当てられた
符号を区別するのに必要なビットの数を大きくするので
起こる。この圧縮の低減は、可変長符号を利用する初期
ストリングの圧縮の間に起こるだけである。

【００８１】図２は本発明の最高性能の実施例を実現す
る圧縮装置を示している。この実施例は、経済的で高速
な圧縮処理を与える。Ｂビットの文字の大きさおよびＣ
ビットの圧縮符号の大きさが用いられる。ストリング・
テーブルは、２^C の記憶場所を含む。普通には、Ｂは、
８ビットであり、Ｃは、１２ビットで、他の文字および
符号の大きさをこの発明を実施するのに利用できるよう
にしている。この実施例は、ハッシュされたストリング
・テーブル内のストリング記述項のアドレスとして用い
られるＣビットの固定長符号記号信号を用いる。最初の
２^B の記憶場所は、各単一文字ストリングを含むように
初期設定される。この圧縮装置は、各記述項にＣビット
の接頭部ストリング符号だけを含むストリング・テーブ
ルを用いる。伸長テーブルは、この同じ符号とそのほか
に現在のストリングを合成するのに接頭ストリングに追
加されるＢビットの拡張文字を含む。

【００８２】圧縮装置からの出力符号記号信号として用
いられるストリング・テーブルに入るアドレスは、図２
の実施例の説明の次に詳細に説明するハッシュ関数を用
いて得られる。ハッシュ関数は、Ｎ個のＣビット・アド
レスを順次に発生する。図２の実施例は、図３の実施例
とともに以下に説明する多数の機能を制御する制御装置
を用いる。例えば、ハッシュ関数装置は、Ｎ番目のアド
レスが発生したときに制御装置に知らせる。本発明のハ
ードウェア実施例は、順次状態機械（シーケンシャル・
ステート・マシーン）として実現され説明される。圧縮
装置の制御装置は、それらの種々のブロックから信号を
受けて、機械の現存の状態に従って圧縮装置の構成要素
を制御するためにそれらへ信号を与える。説明した各シ
ーケンスを制御するのにどんな標準制御論理装置をも利
用できる。例えば、１状態ごとに１フリップ・フロップ
を付勢して、各状態の間実行されるべき演算上の接続お
よび機能を区別し、その状態を制御するフリップ・フロ
ップをその状態の間付勢してもよい。

【００８３】次に図２を参照すると本発明の最高性能の
実施例の圧縮装置が示されている。この圧縮装置は、バ
ス１０に入力文字信号を受けてバス１１に圧縮出力符号
信号を与える。入力文字は外部装置からバス１０に与え
られる。外部装置は、また入力文字信号がその外部装置
から利用でき、バス１０に加えられるときにつねに、デ
ータ利用可能信号をライン１２に与える。ライン１２上
のデータ利用可能信号は、圧縮装置制御装置１３に加え
られる。圧縮装置制御装置１３は、図２の圧縮装置のブ
ロックのすべてにリード１４を経て制御信号を与える。
圧縮装置制御装置１３は、図２の圧縮装置を制御状態を
介して以下に詳細に説明するような方法で順序付けす
る。制御装置１３はまた、追加の入力文字を要求するた
めライン１５を通して外部装置に文字ストローブ信号を
与える。出力符号信号がバス１１の上で利用できると
き、制御装置１３は、符号ストローブ信号をリード１６
を通して外部装置に与える。

【００８４】バス１０の上の入力文字は、Ｂビット文字
レジスタ１７に入れられる。単一文字ストリング符号を
作るために、文字レジスタ１７からのＢビット文字バイ
トは、バス１８を経てＣビット符号番号レジスタ１９の
Ｂ個の下位ビットに挿入される。符号番号レジスタ１９
の高位桁のＣ−Ｂビットをリード２０の上の制御信号を
用いてゼロにセットできる。

【００８５】レジスタ１９からの符号記号信号およびレ
ジスタ１７からの文字信号は、それぞれバス２１および
２２を経てハッシュ関数回路２３に加えられる。ハッシ
ュ関数回路２３は、バス２１の上のＣビット符号信号を
バス２２の上のＢビット文字と結合してバス２４の上に
Ｎ個のＣビット・アドレスを逐次に与える。ハッシュ関
数回路２３は、バス２４を通して与えられたハッシュア
ドレスがそのシーケンスのＮ番目のアドレスであるかど
うかをリード２５を経て制御装置１３に知らせる。

【００８６】ハッシュ関数回路２３はまた、制御装置１
３から「新ハッシュ」指令および「次のハッシュ」指令
を受ける。制御装置１３は、ハッシュ関数回路２３に指
令して「新ハッシュ」指令に応答するＮ個のハッシュ・
アドレスの最初のものおよび「次のハッシュ」指令が相
次いで発生するのに応答して相次ぐハッシュ・アドレス
を与える。既に説明したように、ハッシュ関数２３がＮ
番目のハッシュ・アドレスを与えたとき、一つの信号が
リード２５を介して制御装置１３に戻される。

【００８７】バス２４の上のハッシュ・アドレスは、２
^B に等しい一定値信号をも受ける比較器２６に加えられ
る。比較器２６は、バス２４の上のハッシュ・アドレス
を値２^B と比較して、バス２４の上のハッシュ・アドレ
スが２^B より大きいかまたは２^B 以下であるかどうかを
指示する信号をリード２７を介して制御装置１３に与え
る。

【００８８】バス２４の上のハッシュ・アドレスはま
た、ＣビットＲＡＭアドレス・レジスタ２８にも加えら
れる。ＲＡＭアドレス・レジスタ２８にロードされたア
ドレスは、圧縮装置ストリング・テーブルを記憶するの
に用いられるＲＡＭ２９を呼出す。ＲＡＭ２９は、２^C
のＣビット記憶場所を含んでいる。各ストリングは、そ
のストリングに割当てられた符号によってアドレス指定
された記憶場所にあるその接頭符号を記憶することによ
ってＲＡＭ２９の中に記憶される。そのストリングに割
当てられた符号は、後述のようにして、ストリング拡張
文字と接頭部符号をハッシュすることにより得られる。

【００８９】ＲＡＭ２９は、「読出し」指令および「書
込み」指令を制御装置１３から受けてＲＡＭ２９の「読
出し」、「書込み」機能を制御する。ＲＡＭ２９は、２
^B に等しいＣビットの値またはＣビット符号番号信号を
レジスタ１９からバス３０を介して受取るように制御装
置１３によって制御される。

【００９０】「書込み」指令をＲＡＭ２９に加えるのに
従って、一定値２^B またはバス３０の上の符号番号のい
ずれかが制御装置１３からの制御信号に従ってレジスタ
２８の中のＲＡＭアドレスによって呼出された記憶場所
に書込まれる。ＲＡＭ２９はまた、「読出し」指令に応
答して呼出された記憶場所のＣビット内容をバス３１に
与える。バス３１の上のＲＡＭ出力および符号レジスタ
１９の出力は、比較器３２へ入力として加えられる。比
較器３２はまた、２^B に等しい一定値信号を受ける。比
較器３２は、ＲＡＭ２９の出力を符号番号レジスタ１９
の出力および２^B と比較する。比較の結果は、リード３
３を経て制御装置１３に与えられる。リード３３の上の
比較信号は、バス３１の上のＲＡＭ出力レジスタ１９か
らの符号番号に等しいか、または２^B に等しいか、また
はどちらでもないかを制御装置１３に指示する。あとで
説明する理由のために、制御装置１３は、ＲＡＭアドレ
ス・レジスタ２８を制御して、その内容をバス３４を経
て符号番号レジスタ１９に転送する。

【００９１】図２の圧縮装置は、Ｃビット信号をバス３
６を経てＲＡＭアドレス・レジスタ２８に与える初期設
定計数器３５を備えている。計数器３５はそれに加わる
ゼロの値をもつ信号を介してゼロにセットできる。制御
装置１３は、計数器３５を計数指令を介して制御して、
計数指令を加えるごとに計数器の内容に１を加える。計
数器３５は、それが計数値２^C に達したときを制御装置
１３にリード３７の上のキャリアウトまたはオーバフロ
ー信号を経て知らせる。初期設定計数器３５はＲＡＭ２
９を初期設定するのに用いられ、ＲＡＭ２９の記憶場所
のすべてを逐次に呼出して空状態を指示するように選択
された一定値２^B を書込むことによって空にする。

【００９２】図２の圧縮装置の基本動作を要約すると次
の通りである。

【００９３】１．各データブロックごとに、ＲＡＭを空
に初期設定する。

【００９４】２．各バイト・ストリングの最初の文字に
ついて：最初の符号番号として、文字を符号番号レジスタに入れ
る。

【００９５】３．相次ぐ文字について：ハッシュ（符号、文字）→一連のＮ個のＲＡＭアドレ
ス；各記憶場所ごとにつぎつぎに、ＲＡＭ出力＝符号番号であれば：ＲＡＭアドレス→符号
番号レジスタ；もう一つの文字でこのステップに再び入る。

【００９６】ＲＡＭ記憶場所が空であれば：符号番号レ
ジスタからＲＡＭに書込み、符号値を出力として伝送す
る。次にステップ２へ行く。

【００９７】そうでないときは、すべてのハッシュ・ア
ドレスの後、符号値を出力として伝送する；ステップ２
へ行く。

【００９８】図２を続けて参照すると、以下のものが図
２の圧縮装置の状態機械語記述である。

【００９９】状態０：各データブロックの始めにおける
待ち状態初期設定計数器をゼロにセット。

【０１００】データ使用可能信号を待つ：次いで状態１
へ行く。

【０１０１】状態１：ＲＡＭを初期設定する初期設定計数器→ＲＡＭアドレス・レジスタ２^B →ＲＡＭデータ入力ＲＡＭを書込む＋１を初期設定計数器に加える初期設定計数器＜２^C なら、状態１を繰返す、そうでな
ければ状態２へ行く。

【０１０２】状態２：符号を開始するブロックの最初の
文字を読出す。

【０１０３】文字を符号番号レジスタ（下位Ｂ個のビッ
ト）に入力するゼロを符号レジスタ（上位Ｃ−Ｂ個のビット）に入力す
る状態３へ行く。

【０１０４】状態３：このストリングの中の次の文字を
処理する次の文字を読出す、使用できる新しい入力文字がなければ：符号番号レジス
タの内容を出力に伝送する；状態０へ行く。

【０１０５】ハッシュ（符号番号レジスタ、次の文字）
→ＲＡＭアドレス

【０１０６】

【外１】

【０１０７】ＲＡＭを読出す。

【０１０８】（ＲＡＭ出力）＝（符号番号レジスタ）な
らば：ＲＡＭアドレス→符号番号レジスタ；状態３へ行く。

【０１０９】（ＲＡＭ記憶場所）＝２^B ならば：状態５
へ行く。

【０１１０】その他の場合：状態４へ行く。

【０１１１】状態４：探索を継続する次のハッシュ（符号、文字）→ＲＡＭアドレス

【０１１２】

【外２】

【０１１３】その他の場合：状態４を繰返す。

【０１１４】ＲＡＭを読出す（ＲＡＭ出力）＝（符号レジスタ）であれば：であれば、ＲＡＭアドレス→符号番号レジスタ；状態３へ行く。

【０１１５】（ＲＡＭ出力）＝２^B ならば：状態５へ行
く。

【０１１６】その他の場合：最終ハッシュ繰返しであれ
ば：状態６へ行き、そうでなければ状態４を繰返す。

【０１１７】状態５：新ストリングを作る（符号番号レジスタ）をＲＡＭに書込む、状態６へ行
く。

【０１１８】状態６：ストリングの終り（符号番号レジスタ）→出力文字レジスタ→符号番号レジスタ（下位Ｂビット）ゼロ＝符号番号レジスタ（上位Ｃ−Ｂ個のビット）、状態３へ行く。

【０１１９】上に与えられた状態機械語記述に関する図
２の圧縮装置の動作のさらに詳細な説明を次に行う；

〔０〕．待ち状態．１ブロックの入力文字を待ってい
る間、図２の圧縮装置は、この状態にある。待ち状態の
間、制御装置１３は、初期設定計数器３５をゼロにリセ
ットする。入力データを供給する外部信号源からリード
１２を通ってくるデータ使用可能信号は、入力データが
利用できるときを指示するために用いられる。データが
使用可能になったとき、リード１２の上のデータ使用可
能信号は、制御装置１３に初期設定状態に入るように合
図する。

【０１２０】〔１〕．初期設定状態．ランダム・アク
セス記憶装置（ＲＡＭ）２９の内容は、空であるように
初期設定される。空記号は、実現の便宜上２^B として任
意に選ばれる。従って、「初期設定状態」では、値２^B
が記憶装置２９の各記憶場所から書込まれる。空記号
は、ストリング符号には決して割当てられてはならな
い。記憶場所ゼロないし２^B は、それらは決して呼出さ
れないであろうけれども、実現の便宜上空に初期設定さ
れる。概念的には、記憶場所ゼロないし２^B −１は、２
^B 個の単一文字ストリングを含むように初期設定され、
それらのストリングは、それらが表す文字に等しい符号
値を予め割当てられている。従って、２^B 個の単一文字
ストリングは、符号ゼロないし２^B −１を予め割当てら
れている。この初期設定は、Ｃビットの初期設定計数器
３５内の値をバス３６を経てＲＡＭアドレス・レジスタ
２８にゲートすることによってメモリサイクルを繰返し
て達成される。ＲＡＭ２９への入力は、Ｃビットの一定
入力値２^B から選択される。初期設定計数器３５は、現
在の内容に１を加えることによって計数を上げるように
指令される。この一連の事象は、各記憶場所に対して１
回ずつ合計２^C 回繰返される。２^C のそのような計数の
のちに初期設定計数器３５は、２^C の計数値が起ったこ
とを知らせるオーバフローまたはキャリアウト信号を制
御装置１３にリード３７を経て与える。これによって図
２の圧縮装置は「最初の文字の状態」に進む。

【０１２１】〔２〕．最初の文字の状態．初期設定の
のち、図２の圧縮装置はバス１０の上にある第１入力文
字を読取って、それのＢ個のビットをＢビット文字レジ
スタ１７にゲートする。次に制御装置１３によって信号
を文字ストローブ・ライン１５に与えて、次の入力文字
信号を外部装置によって入力バス１０の上に与えさせ
る。次に文字レジスタ１７の中のＢ個の文字ビットをバ
ス１８を経てＣビット符号番号レジスタ１９の下位（右
側）Ｂビットにゲートして、レジスタ１９の上位Ｃ−Ｂ
ビットをゼロにセットする。この手順は、最初の入力文
字をその単一文字ストリングに対してあらかじめ割当て
られた符号値に変換する。図２の実施例において、２^B
個のあらかじめ割当てられた符号値は、それらが表す文
字体系の文字にそれぞれ等しい。最初のストリングを開
始してしまうと、図２の圧縮装置の繰返しの主サイクル
である「次の文字状態」に入る。

【０１２２】〔３〕．次の文字状態．この状態に入る
と、一つの正しい文字ストリングが入力からパースされ
てしまっており、その符号値が符号番号レジスタ１９に
入っている。次の文字は、こんどは、バス１０から文字
レジスタ１７に読出され、ライン１５の上の文字ストロ
ーブ信号は、外部データ源に戻される。ライン１２の上
のデータ使用可能信号が、そのような文字がバス１０の
上で使用できなかったことを示す場合には、圧縮装置は
データブロックの終りに達していたことになる。その状
況では、符号番号レジスタ１９にある最終データ・スト
リングに対する符号値は、出力符号としてバス１１を通
して伝送されて、新しい圧縮された符号信号が与えられ
ていることを指示するライン１６の上の符号ストローブ
信号が外部装置に送られる。次に制御装置１３は、圧縮
装置を「待ち状態」に戻す。

【０１２３】しかし、そのデータブロックの終りに達し
ないで、新しい文字が利用できて、文字レジスタ１７に
入れられたとすれば、このＢビットの文字は、バス２２
を経てハッシュ関数回路２３の中へバス２１を通して与
えられたレジスタ１９の中のＣビットの符号番号と結合
される。制御装置１３からの「新ハッシュ」指令の制御
を受けて、ハッシュ関数回路２３は、この符号と文字の
組合せに対する第１のＲＡＭアドレスを与える。バス２
４の上のこのハッシュ・アドレスは、比較器２６によっ
て値２^B と比較される。バス２４の上のハッシュ・アド
レスが２^B 以下であれば、この記憶場所は、呼出し不能
で、次のハッシュ・アドレスが「次のハッシュ状態」へ
ゆくことによって選択される。２^B 以下のアドレス値
は、２^B より小さな値が単一文字のストリングに対する
符号値であるようにあらかじめ割当てられており、かつ
値２^B は、空記憶場所（未使用の符号値）を識別するた
めにあらかじめ割当てられたので、新しい符号値として
認められない。

【０１２４】ハッシュ・アドレスが２^B より大きければ
（通常の場合）、バス２４の上のハッシュ・アドレスが
ＲＡＭアドレス・レジスタ２８にゲートされ、ＲＡＭ２
９がそのアドレスの内容を読取るように制御される。バ
ス３１の上のＣビットの結果は、比較器３２においてレ
ジスタ１９からの符号値と値２^B との両方に比較され
る。バス３１の上のＲＡＭ２９の出力がレジスタ１９か
らの符号番号に等しければ、拡張ストリングは、前に出
てきて既に一つの符号値を割当てられており、すなわち
丁度読出された記憶場所のＲＡＭアドレス値である。新
符号番号はＲＡＭアドレス・レジスタ２８からバス３４
を経て符号番号レジスタ１９にゲートされ、新しい文字
についての手順を繰返すためにこの「次の文字状態」に
再び入る。

【０１２５】代りにバス３１の上のＲＡＭ出力が２^B に
等しければ、この記憶場所は、空であり、拡張ストリン
グがテーブルにないので、入力データをパースするのに
利用できないことを意味する。これによって、現在のス
トリングの構成作業を終りにしてこんどは「新ストリン
グ状態」に入る。

【０１２６】しかし、バス３１の上のＲＡＭ出力が２^B
にもまたレジスタ１９からの符号番号にも等しくない場
合、ＲＡＭ２９の中の他の記憶場所を探索しなければな
らず、それは「次のハッシュ状態」において実行され
る。

【０１２７】〔４〕．次のハッシュ状態．この状態に
おいては、さらに別のＲＡＭアドレスがハッシュ関数回
路２３によって現在の符号、文字組合せに対して制御装
置１３からの「次の「ハッシュ」指令の制御を受けて発
生される。次に前の状態の各手順がその本質において繰
返される。新アドレスは比較器２６によって２^B に比較
され、そのアドレスが２^B より大きくなければ、それは
用いられない。この場合に、もう一つのアドレスを得る
ために、この「次のハッシュ状態」に再び入る。Ｎ個の
ハッシュ・アドレスすべてを、ハッシュ関数回路２３か
らのリード２５の上の信号によって示されているよう
に、検査し終ると、現在のストリングは、そのストリン
グ・テーブルに存在しないと考えられて、それに入る空
間がない。次に「ストリング終了状態」に入る。

【０１２８】しかし、ハッシュ・アドレスが２^B より大
きければ、バス２４の上のアドレスはＲＡＭアドレス・
レジスタ２８にゲートされて、ＲＡＭ２９がその記憶場
所において内容を読出すように制御される。ＲＡＭ出力
のバス３１の上に与えられた結果は、比較器３２におい
てレジスタ１９の中の符号番号および２^B の両方と比較
される。ＲＡＭ出力が符号番号に等しければ、ＲＡＭア
ドレス・レジスタ２８からの新しい符号番号がバス３４
を経てレジスタ１９にゲートされ、「次の文字状態」に
入る。この代りに、バス３１の上のＲＡＭ出力が値２^B
に等しければ、「新ストリング状態」に入る。バス３１
の上のＲＡＭ出力が２^B および符号値のいずれにも等し
くなければ、この処理は、この新アドレス値に対するこ
の「次のハッシュ状態」に再び入ることによってＮ回ま
で繰返す。ハッシュ関数回路２３からのリード２５の上
の信号によって示されているように、Ｎ個の記憶場所が
試みられたとき、このストリングは終りにされて「スト
リング終了状態」に入る。

【０１２９】〔５〕．新ストリング状態．ストリング
・テーブル内の空記憶場所に遭遇したことは、探索され
た拡張ストリングをテーブルの中に発見しなかったこと
およびそのストリングをテーブルの中に入れる必要のあ
ることを示す。これは、拡張ストリングの接頭部符号番
号をＲＡＭ２９に書込むことにより達成されるので、割
当てられたアドレスを拡張ストリングのための符号値と
してとっておく。従って、ＲＡＭアドレス・レジスタ２
８の中のアドレスは、その前の値に維持され、ＲＡＭ２
９は、符号番号レジスタ１９の内容をバス３０を経てア
ドレス指定された記憶場所に書込むように制御される。
次に「ストリング終了状態」に入る。

【０１３０】〔６〕．ストリング終了状態．この状態
に入るとき、拡張ストリングがストリング・テーブルに
ないので、現在あるストリング符号を出力として伝送
し、新しいストリングを開始すべきであると判定され
た。従って、符号番号レジスタ１９からの出力符号信号
を出力バス１１に伝送して、新圧縮符号信号がバス１１
にあることを外部装置に知らせる「符号ストローブ信
号」をリード１６を経て送る。このインターフェイスの
正確な形は、圧縮データ信号を受ける外部装置の特有の
要求事項に従って変わる。新ストリングは、文字レジス
タ１７の中に既にある文字を用いて開始され、その文字
は、それをバス１８を介して符号番号レジスタ１９の下
位Ｂビットにゲートし、かつレジスタ１９の高位Ｃ−Ｂ
ビット位置にあるビット位置にゼロをおくことによって
あらかじめ割当てられた単一文字のストリングに翻訳さ
れている。その新ストリングを構成するために「次の文
字状態」に再び入る。

【０１３１】図３は、本発明の最高の圧縮を実施するた
めの圧縮装置を示す。図３の実施例は、図２の高性能実
施例よりわずかに値段が高く、かつ動作がわずかに遅
い。この実施例は、高性能実施例とほぼ同じ適応圧縮手
順を用いるが、高性能実施例とは違って、圧縮装置は、
可変長さの圧縮された出力符号信号を発生する。高性能
実施例に関して上述したものと同様にして、図３の高圧
縮実施例は、Ｂビット・バイト入力文字信号および２^C
の記憶場所のストリング・テーブルを用いる。圧縮符号
記号は、ストリング・テーブルがいっぱいになるにつれ
て、大きさを増してＣビットの最大長さに達する。必要
に応じて、この符号信号は、新しい文字に出合ったとき
Ｂビットだけ拡張される。

【０１３２】このテーブル内の各ストリングにＣビット
識別子を割当てて、これらの識別子は１で始まる数の順
序で割当てられる。２^D 以下の数の符号を割当てられた
とき、これらの符号の下位Ｄビットだけを圧縮データ信
号として伝送する。ストリング・テーブル内の各記憶場
所は、Ｃビットの接頭部ストリング識別子およびその記
憶場所にあるストリングに割当てられた新しいＣビット
符号を含んでいる。従ってストリング・テーブルの２^C
の記憶場所の各々は、２Ｃビットの幅である。この高圧
縮実施例の圧縮装置で用いられるハッシュ関数は、先に
説明した高性能実施例で用いられたものと同一である。
しかし、この高圧縮実施例においては、ハッシュ関数回
路は、圧縮装置に用いられるだけである。

【０１３３】次に図３を参照すると、本発明の最高圧縮
実施例の圧縮装置が示されている。この圧縮装置は、入
力文字信号をバス１１０を通して受けて、圧縮出力符号
記号信号をビット直列形式でライン１１１に与える。こ
の入力文字は、外部装置からバス１１０に与えられる。
この外部装置はまた、入力文字信号が外部装置から使用
できて、バス１１０に加えられるときは常に、データ使
用可能信号をライン１１２に与える。ライン１１２上の
データ使用可能信号は、圧縮装置制御装置１１３に加え
られる。圧縮装置制御装置１１３は、図３の圧縮装置の
ブロックのすべてに制御信号をリード１１４を介して与
える。圧縮装置制御装置１１３は、図３の圧縮装置をそ
れの制御状態を介して以下に詳細に説明する方法で順序
づけする。制御装置１１３はまた、追加の入力文字を要
求する文字ストローブ信号をライン１１５を通して外部
装置に与える。

【０１３４】バス１１０の上の入力文字はＢビット文字
レジスタ１１６に入れられる。単一文字を出力線１１１
に転送することになっているとき、文字レジスタ１１６
は、その文字のＢビットをバス１１７を介してシフト回
路網１１８にゲートするように制御装置１１３によって
制御される。シフト回路網１１８は、ビット直列出力を
ライン１１１に与え、バス１１７の上のＢビットを受け
て、これらのビットをライン１１１に直列に与えるよう
に制御装置１１３によって制御される。

【０１３５】図３の圧縮装置は、さらに、圧縮ストリン
グ符号信号を保持して出力ストリング符号をシフト回路
網１１８にバス１２０を介して与えるビット符号番号レ
ジスタ１１９を備えている。符号番号レジスタ１１９を
それに加わるゼロの値にされた信号によってゼロに初期
設定できる。

【０１３６】図３の圧縮装置は、さらに、入力バス１１
０に加えられる入力データ・ストリームのパースされた
ストリングにストリング符号記号信号を数の昇順に割当
てるＣビット符号計数器１２１を備えている。制御装置
１１３の制御のもとに、符号計数器１２１をそれに加わ
るゼロの値にされた信号を介してゼロにリセットしても
よいし、「計数」指令信号を介して現存の計数を１だけ
大きくしてもよい。計数器１２１は、符号計数器１２１
の中の計数値が値２^C −１に達したときに制御装置１１
３にライン１２３を介して信号を出力する検出器１２２
に出力を与える。この値は、計数器がオール１の状態に
達するとき、Ｃビット計数器１２１によって達成され
る。符号計数器１２１の出力はまた、シフト回路網１１
８によってシフトアウトされるべきビットの数を定める
信号をシフト回路網１１８にバス１２４を介して与える
符号大きさ回路１２３に加えられる。上述のように、Ｄ
ビットがシフトアウトされる（ここでＤはＣ以下であ
る）。

【０１３７】符号大きさ回路１２３をＳＮ７４１４８優
先順位回路網のような標準Ｃビット優先順位符号器回路
によって実現できる。符号計数器１２１は優先順位符号
器に結合され、そして計数器１２１の昇順重みのビット
を優先順位符号器の昇順優先順位に並んだ優先順位入力
にそれぞれ結合される。次に優先順位符号器は、Ｄに対
する値である２進数信号を与える。

【０１３８】数Ｄをシフト回路網１１８の中で用いて、
Ｄシフト・クロック・パルスのパケットをゲートして、
シフト回路網１１８がバス１２０に与えられた出力符号
信号のＤビットをライン１１１に直列に与えるようにし
てもよい。優先順位符号器を符号大きさ回路１２３に用
いることに対する多くの代替のものがふつう熟練した論
理設計者には容易に明らかであろう。

【０１３９】例えば、シフト回路網１１８は、出力符号
をバス１２０に受けて符号大きさ回路１２３によって制
御されたシフトクロックパルスに応答して出力符号のＤ
ビットをシフトアウトするシフト・レジスタを用いて実
現できる。符号大きさ回路１２３によって制御されるＤ
クロックパルスのパケットに応答して、シフト回路網１
１８の中に入っているシフト・レジスタにはクロック信
号がＤ回与えられる。シフト・レジスタの構成は、この
技術分野では周知であり、その正確な詳細は、データを
受ける外部装置のインタフェースによって変る。上述の
ように、シフト回路網１１８はまた、Ｂ文字ビットをバ
ス１１７からライン１１１のシフト回路網１１８によっ
て伝送するのを制御する普通のクロック制御回路を備え
ている。

【０１４０】レジスタ１１９からの符号記号信号および
レジスタ１１６からの文字信号は、それぞれバス１２５
および１２６を経てハッシュ関数回路１２７へ加えられ
る。ハッシュ関数回路１２７は、上述の本発明の高性能
実施例に関して用いられたハッシュ関数回路と同一であ
る。ハッシュ関数回路１２７は、バス１２５の上のＣビ
ット符号信号をバス１２６の上のＢビット文字信号と組
合わせて、バス１２８の上に順次にＮ個のＣビットアド
レスを与える。ハッシュ関数回路１２７は、リード１２
９を介して制御装置１１３にバス１２８の上に与えられ
たハッシュアドレスがその列の中のＮ番目のアドレスで
あるかどうかを知らせる。

【０１４１】ハッシュ関数回路１２７はまた、制御装置
１１３から「新ハッシュ」指令および「次のハッシュ」
指令を受ける。制御装置１１３は「新ハッシュ」指令に
応じてＮ個のハッシュアドレスの最初のものを与え、ま
た「次のハッシュ」指令の相次ぐ発生に応じて相次ぐハ
ッシュドレスを与えるようにハッシュ関数回路１２７に
指令する。上述のように、ハッシュ関数回路１２７がＮ
番目のハッシュアドレスを与えたとき、一つの信号をリ
ード１２９を経て制御装置１１３に戻す。

【０１４２】バス１２８の上のハッシュ・アドレスは、
ＣビットＲＡＭアドレス・レジスタ１３０に加えられ
る。ＲＡＭアドレス・レジスタ１３０にロードされたア
ドレスが圧縮装置ストリング・テーブルを記憶するのに
用いられるＲＡＭ１３１を呼出す。ＲＡＭ１３１は各々
２Ｃビット幅の２^C の記憶場所に編成される。一つの文
字ストリングが一つの記憶場所に符号計数器１２１によ
って割当てられたそのストリングに対する符号番号およ
びその接頭部符号、すなわち、そのストリングの最終文
字を除くすべての文字を含むストリングの符号番号を入
れることによって記憶される。ＲＡＭ１３１は、すべて
の記憶場所が最初に空であることを示すオール・ゼロを
ストリング符号欄に含むように初期設定される。文字を
もたないストリンである符号ゼロのストリングは、ＲＡ
Ｍ１３１の中に記述項をもたない。

【０１４３】ＲＡＭ１３１は、ＲＡＭ１３１の「読出
し」および「書込み」機能を制御するために制御装置１
１３から「読出し」指令および「書き込み」指令を受け
る。制御装置１１３がＲＡＮ１３１に「書込み」機能を
実行するように指令すると、ＲＡＭアドレス・レジスタ
１３０によって呼出された記憶場所のストリング符号欄
がバス１３２を経て符号計数器１２１のＣビット出力を
受け、また呼出された記憶場所の接頭部符号欄が符号番
号レジスタ１１９からの入力をバス１３３を経て受け
る。制御装置１１３がＲＡＭ１３１にＲＡＭアドレス・
レジスタ１３０によって呼出された記憶場所の内容を読
出すように指令すると、呼出された記憶場所の接頭部符
号がバス１３５を経て比較器１３４に加えられ、また呼
出された記憶場所のストリング符号がバス１３６を経て
符号番号レジスタ１１９へ加えられると共に、ゼロ検出
器１３７にも加えられる。比較器１３４はまた、バス１
３８にゼロの値をもつ信号を受ける。図３の圧縮装置の
現存の状態次第で、制御装置１１３は、バス１３５の上
の接頭部符号とレジスタの中に記憶された符号とが等し
いか等しくないかを試験するか、またはレジスタ１１９
の中の符号信号がゼロに等しいか等しくないかを試験す
るように比較器１３４を制御する。これらの試験の結果
は、リード１３９を経て制御装置１１３に与えられる。
図３の圧縮装置の現存の状態に従えば、制御装置１１３
は、バス１３６の上のストリング符号がゼロに等しいか
等しくないかを決めるためのゼロ検出器１３７を始動さ
せる。決定の結果は、リード１４０を経て制御装置１１
３に与えられる。

【０１４４】図３の圧縮装置はまた、Ｃビット信号をバ
ス１４２を経てＲＡＭアドレスレジスタ１３０に与える
初期設定計数器１４１を備えている。制御装置１１３
は、計数指令を介して計数器１４１を制御してその計数
器の内容を計数指令を加えるごとに１だけ増やす。計数
器１４１は、それが計数値２^C に達したときを制御装置
１１３にリード１４３の上のキャリアウトまたはオーバ
ーフロー信号を介して知らせる。初期設定計数器１４１
は、ＲＡＭ１３１の記憶場所のすべてを順次に呼出して
ストリング符号欄にバス１３２から得た値ゼロを書込む
ことによってＲＡＭ１３１を空に初期設定するのに用い
られる。必ずしも必要ではないけれども、接頭部符号欄
を、実現の便宜上、バス１３３から得た値ゼロを書込む
ことによって、初期設定してもよい。

【０１４５】一般的にいえば、図３の圧縮装置に関して
は、ライン１１１に与えられる各出力符号記号信号は、
符号計数器１２１の中に現存する値によって定められた
Ｄビットの長さをもっている。符号計数器内のゼロでな
い最高のビットがＤ番目のビットであって、その結果、
圧縮装置の出力符号の大きさが符号計数器内の値の大き
さに等しい。圧縮装置によって伝送されるべき最初の符
号記号信号は、ゼロビットの幅であるが、それに付加さ
れたＢビットの文字記号信号をもっている。二番目の符
号記号信号は、１ビットの長さで、次の二つの符号記号
信号は、二つのビットを各々含んでいる。次の四つの符
号記号信号は、３ビットを各々含んでいる、などであ
る。これらの符号記号の幾つかはまたそれらに追加され
たＢビットの文字値をもっている。値Ｄは、Ｃビットで
最大に達する。

【０１４６】図３の圧縮装置の基本動作は次のように要
約される。

【０１４７】１．各データ・ブロックごとに、ＲＡＭを
空に初期設定する。

【０１４８】２．符号レジスタをゼロ符号でスタート、最初の入力文字を読出す３．ハッシュ（符号レジスタ、文字）→Ｎ個のＲＡＭアドレスの列ＲＡＭ記憶場所が空ならば：符号レジスタ、符号計数器をＲＡＭに書込む、符号レジスタのＤビットを出力として伝送する；符号計数器を増分する；ゼロ→符号レジスタ；接頭部符号（ＲＡＭ）＝符号レジスタならば：新符号（ＲＡＭ）→符号レジスタ、新入力文字を読出す、符号値が見出されなければ：符号レジスタのＤビットを出力として伝送する；符号計数器を増分する；ゼロ→符号レジスタ；入力が尽きるまでステップ３を繰返す。

【０１４９】図３を続けて参照すると、以下のものが図
３の圧縮装置の状態機械記述語である。

【０１５０】状態０：各データ・ブロックの始めにおける「待ち状態」ゼロ→初期設定計数器ゼロ→符号レジスタゼロ→符号計数器データ使用可能信号を待つ；状態１へ行く状態１：「ＲＡＭを初期設定する」初期設定計数器→ＲＡＭアドレスゼロをＲＡＭに書込む初期設定計数器に＋１を加える初期設定計数が＜２^C ならば：状態１を繰返す、そうでなければ状態２へ行く。

【０１５１】状態２：「入力文字を読出す」どのデータも使用できなければ：符号レジスタ＝ゼロの場合；符号レジスタのＤビットを出力として伝送する。

【０１５２】状態０へ出るデータが使用可能ならば：次の文字を読出す→文字レジスタが状態３へ行く。

【０１５３】状態３：「最初のテーブル検索」最初のハッシュ（符号レジスタ、文字）→ＲＡＭアドレスＲＡＭを読出すストリング符号（ＲＡＭ）＝ゼロならば：（空サイト）状態５へ行く接頭部符号（ＲＡＭ）＝符号レジスタならば（ストリングが見出される）：ストリング符号（ＲＡＭ）→符号レジスタ状態２へ行くそうでなければ状態４へ行く。

【０１５４】状態４：「テーブル探索を繰返す」次のハッシュ（符号レジスタ、文字）→ＲＡＭアドレスＲＡＭを読出すストリング符号（ＲＡＭ）＝ゼロならば：状態５へ行く。

【０１５５】接頭部符号（ＲＡＭ）＝符号レジスタならば：ストリング符号（ＲＡＭ）→符号レジスタ、状態２へ行く最終ハッシュならば、状態６へ行くそうでなければ、状態４を繰返す状態５：「新ストリング・エントリー」符号レジスタのＤビットを出力として伝送する符号計数器＜２^C −１ならば：符号計数器へ＋１を加える書込む（符号レジスタ、符号計数器）→ＲＡＭ符号レジスタ＝ゼロならば：Ｂビット文字を出力として伝送する状態２へ行く符号レジスタ＝非ゼロならば：ゼロ→符号レジスタ状態３へ行く状態６：「ストリング終結」符号レジスタのＤビットを出力として伝送する符号計数器＜２^C −１ならば：符号計数器に＋１を加える符号レジスタ＝ゼロならば：Ｂビット文字を出力として伝送する状態２へ行く符号レジスタ＝非ゼロならば：ゼロ→符号レジスタ状態３へ行く。

【０１５６】上に与えられた状態機械記述語に関する図
３の圧縮装置の動作のさらに詳しい説明を次に行う。

【０１５７】［０］待ち状態．１ブロックの入力文
字を待っている間、図３の圧縮装置は、この状態にあ
る。

【０１５８】待ち状態の間、制御装置１１３は、初期設
定計数器１４１、符号番号レジスタ１１９および符号計
数器１２１をゼロにリセットする。入力データを供給す
る外部信号源からのリード１１２の上のデータ使用可能
信号は、入力データが使用可能であるときを指示するた
めに用いられる。データ使用可能になると、リード１１
２の上のデータ使用可能信号は、制御装置１１３に「初
期設定状態」に入るように合図する。

【０１５９】〔１〕初期設定状態．ランダムアクセ
ス記憶装置ＲＡＭ１３１の内容は、空であるよう初期設
定される。この実施例における空記号は、ゼロとして選
ばれる。従って、ＲＡＭ１３１の初期設定は、すべての
記憶場所にゼロを挿入することによって達成される。ス
トリング符号記述項だけがゼロでなければならないが、
接頭部符号値は、同時に、実現の便宜上、ゼロにセット
されることがわかる。この初期設定は、Ｃビット初期設
定計数器１４１の中の値をバス１４２を経てＲＡＭアド
レス・レジスタ１３０にゲートすることによって記憶サ
イクルを繰返して達成される。ＲＡＭ１３１への入力
は、符号番号レジスタ１１９からバス１３３を経て与え
られるとともに、符号計数器１２１からバス１３２を経
ても与えられる。レジスタ１１９および計数器１２１の
両方が「初期設定状態」の間ゼロになっている。ＲＡＭ
１３１は、ＲＡＭアドレス・レジスタ１３０によって指
定された記憶場所にゼロ入力データを書込むように制御
される。初期設定計数器１４１は、その現在の内容を１
だけ増分することによって数え上げるよう指令される。
この一連の事象は、各記憶場所ごと１回、計２^C 回繰返
される。２^C のそのような計数ののちに、初期設定計数
器１４１は、２^C 計数が起こったことを知らせるオーバ
フローまたはキャリアウト信号を制御装置１１３へリー
ド１４３を経て与える。次に制御装置１１３は、図３に
圧縮装置を「入力文字読出し状態」へ進める。

【０１６０】〔２〕入力文字読出し状態．図３の圧
縮装置が新しい文字に対して用意が整うと常に、この状
態に入る。符号番号レジスタ１１９にある値は、現在の
ストリングの中で既に遭遇した文字を識別する。レジス
タ１１９の中にゼロの値があると新ストリングの始まり
であることを示す。一つの文字信号が入力文字バス１１
０から文字レジスタ１１６に入れられる前に、リード１
１２の上のデータ使用可能信号が検査される。データ使
用可能信号がどのデータも使用できないことを示す場
合、入力データ・ブロックの終りに達したことになる。
その状況において、符号番号レジスタ１１９の中のどの
非ゼロ値をも圧縮データ・ブロックを完成するように圧
縮装置によって伝送しなければならない。従って符号番
号レジスタ１１９の内容は、比較器１３４においてゼロ
と比較される。レジスタ１１９の内容がゼロでなけれ
ば、比較器１３４は、制御装置１１３にリード１３９を
経て信号を与えて、制御装置１１３が符号番号レジスタ
１１９の内容をシフト回路網１１８にバス１２０を経て
ゲートする。符号大きさ回路１２３は、符号計数器１２
１からのＤに対する値を定めて符号値のＤビットをシフ
トアウトするようにシフト回路網１１８を制御する。こ
のデータが出力されてしまったとき、制御装置１１３
は、それ以上の入力データを待つために「待ち状態」に
戻るように図３の圧縮装置を制御する。

【０１６１】リード１１２の上のデータ使用可能信号に
よって、それ以上の入力データが使用可能であれば、バ
ス１１０から一つの文字が文字レジスタ１１６に読み込
まれ、文字を受取ったことの知らせを与える文字ストロ
ーブ信号を外部装置へのリード１１５の上に与える。次
に、制御装置１１３は、「最初のテーブル探索状態」に
入るように図３の圧縮装置を制御する。

【０１６２】〔３〕最初のテーブル探索状態．文字
レジスタ１１６の中の文字によって拡張された符号番号
レジスタ１１９の中の値によって識別されるストリング
から成る潜在的なストリングを、次にそれがストリング
テーブル内に現れるかどうかを決めるために探索する。
レジスタ１１９からの符号信号およびジレスタ１１６か
らの文字信号は、その組合わせに対するハッシュ・アド
レスを発生するハッシュ関数回路１２７へそれぞれバス
１２５および１２６を経てゲートされる。Ｃビットアド
レスは、バス１２８を経てＲＡＭアドレスレジスタ１３
０へゲートされ、ＲＡＭアドレスレジスタ１３０はアド
レス指定された記憶場所でＲＡＭ１３１を呼出す。ＲＡ
Ｍ１３１は、呼出された記憶場所の内容を読み出して、
バス１３５に接頭部符号値を与え、そしてバス１３６に
ストリング符号値を与えるように制御される。バス１３
６に結果として生ずるストリング符号値がゼロ検出器１
３７によってゼロであると決められると、その記憶場所
は空であって、それは拡張ストリングがそのストリング
・テーブルにないことを意味する。その状況において、
現在のストリングの処理が決定されて、圧縮装置は、そ
のテーブルを更新して出力を発生するために「新ストリ
ング・エントリー状態」に入るように制御される。

【０１６３】しかしバス１３６の上のストリング符号値
がゼロでなければ、バス１３５上の接頭部符号値は、比
較器１３４によってレジスタ１１９の中の符号値と比較
される。それらの値が等しければ、拡張ストリングは、
そのテーブル内に存在して拡張ストリングが新ベースス
トリングになる。これは、バス１３６に現れる現在のス
トリングのストリング符号を符号番号レジスタ１１９に
ロードすることによって行われる。次に、次の文字が
「入力文字読出し状態」に入ることによって取出され
る。

【０１６４】バス１３５の上の接頭部符号が符号レジス
タ１１９の中の値に一致しないで、かつバス１３６の上
のストリング符号値がゼロでない場合、テーブル探索を
続ける。継続されたテーブル探索は、「テーブル探索繰
返し状態」に入るように圧縮装置を制御することによっ
て行われる。

【０１６５】〔４〕テーブル探索繰返し状態．「最
初のテーブル探索状態」において、適当な占有データも
空記憶場所もハッシュ関数回路１２７によって与えられ
た最初のハッシュ・アドレスにないとき、相次ぐハッシ
ュドレスがＲＡＭ１３１をアドレス指定するために与え
られる。従って各後続ストリング・テーブル探索は、ハ
ッシュ関数回路１２７からの次のハッシュ値をバス１２
８を経てＲＡＭアドレス・レジスタ１３０に転送して、
代りの探索サイトにおいてＲＡＭ１３１をアドレス指定
することによって実行される。ＲＡＭ１３１はアドレス
指定されたサイトにおける内容を読み出して、その記憶
場所に記憶されたストリング符号および接頭部符号をそ
れぞれバス１３６および１３５の上に与えるように制御
される。本質的には、「最初のテーブル探索状態」にお
けると同じ試験が探索されたストリングが見出されたか
どうか、または空記憶場所に遭遇したかどうかを決める
ために行われる。バス１３６の上のストリング符号が検
出器１３７によってゼロであると検出されれば、その記
憶場所が空であって、「新ストリング・エントリー状
態」に入る。バス１３６の上のストリング符号がゼロで
なく、かつバス１３５の上の接頭部符号がレジスタ１１
９からの現在の符号値に、比較器１３４によって決めら
れるように、一致すれば、そのストリングが見出された
のであり、バス１３６の上の新ストリング符号値が符号
番号レジスタ１１９に入れられる。上記の条件のどちら
も起こらなければ、現在のストリングに対する探索は、
この「テーブル探索繰返し状態」に再び入ることによっ
て続けられる。しかし、ハッシュ関数回路１２７からの
リード１２９の上の信号によって表わされるようにＮ個
のハッシュアドレスすべてを利用した場合、そのストリ
ングは、そのストリング・テーブルにないと定められ
て、そのテーブル内のどのスペースもそれを挿入しない
Ｎ個のハッシュ・アドレスが試みられて成功しなかった
とき、「ストリング終結状態」に入る。

【０１６６】〔５〕新ストリング・エントリー状態．
一つのストリングの処理はそのストリングへの拡張が
ストリング・テーブルに見出されないで、空記憶場所に
遭遇したとき終わりにされる。これが起こると、前に認
識されたストリング符号信号が圧縮符号出力信号として
伝送され、拡張ストリングが潜在的なあとの符号化のた
めに、ストリング・テーブルに入れられる。従って、レ
ジスタ１１９の中の前に認識されたストリング符号信号
は、バス１２０を介して出力シフト回路網１１８へ転送
される。シフト回路網１１８は、出力リード１１１の上
に出力符号のＤビットを与える。ここでＤは符号計数器
１２１の中の値に従って符号大きさ回路１２３によって
決められる。

【０１６７】出力がリード１１１に配送されたのち、検
出器１２２は計数器１２１のオール１の状態によって示
される値２^C −１に対して符号計数器１２１を試験す
る。計数器１２１がオール１を含まない場合、計数器１
２１の中の値は、制御装置１１３からの「計数」指令信
号の制御のもとに１だけ増分される。なお、検出器１２
２が符号計数器１２１のオール１の状態を検出しない場
合、新ストリングが前の状態で空であると決定されたば
かりのアドレスにおいてストリング・テーブルの中に入
れられる。これはＲＡＭアドレスレジスタ１３０の中の
アドレスをその前の値で不変に維持し、符号レジスタ１
１９からのバス１３３の上の接頭部符号および符号計数
器１２１によって割当てられたばかりのバス１３２の上
のストリング符号をＲＡＭ１３１の中のアドレス指定さ
れた記憶場所の接頭部符号欄およびストリング符号欄に
それぞれ書込むようにＲＡＭ１３１を制御することによ
って達成される。

【０１６８】そのあとで、比較器１３４は、最後に伝送
された符号がゼロであったかどうかを決めるために符号
番号レジスタ１１９を試験する。最後に伝送された信号
がゼロであった場合、これはストリング・テーブル内に
対応する文字値のなかった１文字のストリングを意味し
た。従ってその文字値は圧縮装置出力として伝送されな
ければならない。従って、文字レジスタ１１６からのＢ
ビット値は、こんどは、すべてのＢビットを出力として
直列に伝送するように制御されているシフト回路網１１
８にバス１１７を介して転送される。次に、新ストリン
グを開始するために「入力文字読出し状態」に入る。

【０１６９】しかし、符号番号レジスタ１１９が非ゼロ
値を含んでいれば、文字レジスタ１１６の中の現在の文
字は伝送されないで、次のストリングの最初の文字とし
て用いられる。従って、符号レジスタ１１９は、新スト
リングを指示するためにゼロに払われ、「最初のテーブ
ル探索状態」に入る。

【０１７０】〔６〕ストリング終結状態．この状態
は、空記憶場所に遭遇しなかったのでストリング・テー
ブル内でエントリーが全く行われないのを除いて「新ス
トリング・エントリー」状態と同一である。しかし「新
ストリング・エントリー」状態の前述のアクションのす
べては、ＲＡＭ１３１の中への「書込み」動作以外は行
われる。符号計数器１２１を増分すると、一つのストリ
ング番号が新しい拡張ストリングに割当てられるが、こ
の拡張ストリングはテーブルに入れられない。そのスト
リングのためのスペースが見出されなかったので、エン
トリーが起こらず、従って符号化されたストリングをあ
との符号化に使用できない。テーブルからのこの削除
は、システムの圧縮有効性を小さくする可能性がある
が、正しくない動作を生じない。

【０１７１】図２および図３に示した本発明の上述の実
施例は、例えば、ディスクリートなディジタル論理部品
を用いてハードウェアで実現される。第１〜４表は、本
発明によるデータ信号の圧縮および伸長を行うプログラ
ム記憶式ディジタル計算機にロードするソフトウェアで
実現された本発明の１実施例を示している。明確に言え
ば、本発明のプログラム格納計算機の実施例は、図２に
関して先に述べた本発明の最高性能実施例をソフトウェ
アで実現する。第１〜４表のプログラム格納計算機の実
施例はＦＯＲＴＲＡＮで実現されるので、互換性のある
ＦＯＲＴＲＡＮコンパイラを備えた計算機ならどれでも
実行できる。圧縮装置は、それぞれ入力および出力デー
タを管理する主プログラムの中で呼出されるべきサブル
ーチンとして実現される。圧縮装置のサブルーチンは、
基礎になっている計算機のワードの大きさに関係のない
任意の長さで密に積められた記号の配列（アレイ）につ
いて取る動作と置く動作をそれぞれ行うＩＢＩＴＳＧお
よびＩＢＩＴＳＰという名の文字操作サブプログラムを
用いる。ＩＢＩＴＳＧおよびＩＢＩＴＳＰサブプログラ
ムは、それぞれ等しい大きさの記号の直線配列の指定さ
れた位置にある選択されたビット長の一つの記号をそれ
ぞれ取ったり、置いたりする。ＩＢＩＴＳＧは、圧縮装
置および伸長装置サブルーチンにおいて用いるための機
能サブルプログラムとして実現され、ＩＢＩＴＳＰは、
圧縮装置および伸長装置サブルーチンの実行において呼
び出されるべきサブルーチン・サブプログラムとして実
現される。表３および表４は、それぞれＩＢＩＴＳＧお
よびＩＢＩＴＳＰを示す。これらのサブプログラムは、
一例として与えられたものであって、等価なサブプログ
ラムが通常の熟練した計算機プログラマによって容易に
作られる。

【０１７２】

【表１】

【０１７３】

【表２】

【０１７４】

【表３】

【０１７５】

【表４】

【０１７６】表１および表２にそれぞれ示した圧縮装置
および伸長装置のサブルーチンは、それぞれＣＯＭＰお
よびＤＥＣＯＭＰという名称である。ＣＯＭＰサブルー
チンは、９ビット文字信号のストリングを１２ビット符
号記号信号に圧縮し、ＤＥＣＯＭＰサブルーチンは、１
２ビット符号記号信号を９ビット文字信号のストリング
に伸長する。例示したサブルーチンは、３６ビットワー
ド長を有する計算機を用いる。これらのサブルーチン
は、３２ビット計算機を用いて８ビット文字で動作する
ように容易に変換される。ＣＯＭＰおよびＤＥＣＯＭＰ
は、サブルーチンとして構成されるけれども、それらは
当然別々のプログラムとして等価に構成できる可能性の
あることがわかる。ＦＯＲＴＲＡＮがこれらのルーチン
を実施するために用いられるが、他の等価なプログラム
言語を同じ効果に用いることができるであろう。

【０１７７】さて、表１を参照すると、ＣＯＭＰ（ＩＢ
ＵＦＡ，ＮＡ，ＩＢＵＦＢ，ＮＢ）サブルーチンが示さ
れている。ＣＯＭＰサブルーチンは、配列ＩＢＵＦＡに
含まれたＮＡ個の９ビット文字のブロックについてデー
タ圧縮を行う。ＣＯＭＰは、配列ＩＢＵＦＢの中のＮＢ
個の１２ビット記号で構成された圧縮符号を作る。

【０１７８】ＣＯＭＰは、圧縮装置ストリング・テーブ
ルを記憶するための４０９６整数配列ＩＴＡＢＬＥを内
部的に用いる。従って、表１の文１４は、ＩＴＡＢＬＥ
配列の寸法を決める。ＩＴＡＢＬＥの中の各記憶場所
は、そのテーブル内のアドレスに等しい圧縮符号をもつ
遭遇した文字ストリングに対応する。このインプリメン
テーションにおいては、ＦＯＲＴＲＡＮがゼロを基準と
した配列を支持しないので、アドレスを作るのに１をそ
の符号に加える。一つのストリングを記憶する各テーブ
ル記憶場所は、そのストリングの接続部の符号を含む。
ストリング・テーブルは、空であるように初期設定され
る。ＩＴＡＢＬＥの空状態は、値５１２をもつＩＦＩＬ
Ｌという空白記号でテーブルを埋めることよって行わ
れ、値５１２は、どのストリングに対しても用いられる
ものではない任意の選択された符号値である。表１の文
１５は、ＩＦＩＬＬの量を限定する。従って、ＩＦＩＬ
Ｌは、値２^B をもっている（この実施例において、Ｂ
は、９である）ことがわかる。表１の実施例は、文１６
によって１を含むように確立されて、初期設定された内
部文字計数器ＮＣＨＡを用いる。ＮＣＨＡ計数器は、読
出されるべき次の入力文字のインデックスを与える。表
１の圧縮装置はまた、ＦＯＲＴＲＡＮ文１７によって定
義されて、１に初期設定される内部出力記号計数器ＮＢ
を用いる。記号計数器ＮＢは、発生されるべき次の出力
記号のインデックスを与える。ＦＯＲＴＲＡＮ文１８お
よび１９は、４０９６の記憶場所すべてにＩＦＩＬＬを
挿入することによってすべての空白値を含むようにスト
リング・テーブルを初期設定する。ＩＴＡＢＬＥの最初
の５１３記憶場所は、決して呼出されないので、これら
の記憶場所は、初期設定を必要としない。これらの記憶
場所の初期設定は、初期設定を行う時間を節約したい場
合に省略できる。

【０１７９】最初の文字は、最初の文字１からの９ビッ
トをＩＢＵＦＡから検索するＩＢＩＴＳＧ機能を用いて
ＦＯＲＴＲＡＮ文２０によって読出される。この入力文
字は、文２０において、変数ＮＯＤＥＮＯにその値を記
憶することによってその文字の値に等しいあらかじめ割
当てられた単一文字ストリング符号値に変換される。変
数ＮＯＤＥＮＯは、既に読出された文字のどの部分的入
力ストリングに対してもその符号値を含むように用いら
れる。表１の文１６〜２０によって、１ブロックのデー
タを処理するための初期設定およびその過程の開始を完
了する。

【０１８０】表１の文２１は、各新しい入力文字が読出
される主処理ループへの入り口を与える。文２１は、そ
れへの飛び越し（ジャンプ）を行うためのラベル１００
を備えている。文字インデックス計数器ＮＣＨＡは、文
２１で増分される。文２２は、ＮＣＨＡが入力パラメー
タＮＡより大きいかどうかを決定し、ＮＣＨＡがＮＡを
超えていれば、すべての入力文字は、使い果たされたの
であって、データブロック終了処理のための文４０へジ
ャンプが行われる。文４０は、そのジャンプを行うため
のラベル４００を備えている。

【０１８１】正常の状況においては、新しい文字が使用
できるとき、文２３は、ＮＣＨＡ番目の９ビット文字を
入力バッファＩＢＵＦＡからＮＯＷＣＨＲという名の変
数に読み込むためのＩＢＩＴＳＧ機能サブプログラムを
用いる。文２４は、ＮＯＷＣＨＲの中の値およびＮＯＤ
ＥＮＯの中の値、すなわちＮＯＷＣＨＲ内の文字によっ
て拡張されたＮＯＤＥＮＯの中の符号によって定められ
るストリングのハッシュアドレスＬＯＣを計算するため
の前のストリング符号を用いる。文２４の中で述べられ
たハッシュ関数は、文字の値は、ビットが逆でないこと
以外、図２に関して上に述べたものと同じである。前述
のハードウェア実施例においては文字の値を１ビットず
つ逆にすることが便利であるけれども、ソフトウェアで
文字の値を１ビットずつ逆にするのは不便である。な
お、文２４のハッシュ関数は、ＦＯＲＴＲＡＮがゼロベ
ースの配列（アレイ）を支持しないので、ＬＯＣの値が
アドレスを作るのにそれに１を加えられている点でハー
ドウェア実施例において用いられたハッシュ関数と異な
る。この最初のハッシュアドレスを発生したのち、計数
器の変数Ｎが、ＬＯＣの中の値がテーブルの中のＮ個の
可能な探索サイトの最初のものであるということを示す
文２５によって限定されて、１に初期設定される。本実
施例においては、Ｎは７として選択される。

【０１８２】表１の文２６は、計数変数としてＮを用い
るテーブル探索ループへの入口を与える。文２６は、そ
れへ飛び越し（ジャンプ）を行うことのできるようにラ
ベル１２０を備えている。文２６は、ＬＯＣが適法な値
を含むかどうかを決定する。従って、文２６は、ＬＯＣ
が５１３より大きいかどうかを決める。記号符号ゼロな
いし５１１は、単一文字のストリングにあらかじめ割当
てられ、５１２は、空白記号のためにとっておき、かつ
すべての符号は、上述のＦＯＲＴＲＡＮ規則のために１
だけ増やされる。ＬＯＣが適法な新しいアドレスを含ま
なければ、飛び越しが文３１へ行われて、もう一つの試
みを発生する。文３１は、飛び越しを行うためのラベル
１８０を備えている。正常には、ＬＯＣ内の値は適法な
アドレスであって、その記憶場所におけるストリング・
テーブルの内容は、文２７における既存の文字ストリン
グ符号に対して検査される。アドレス指定されたストリ
ング記憶場所の内容が既存のストリング信号に等しくな
ければ、求めるべきストリングは、前にこの符号値が割
当てられなかったので文３０への飛び越しがその探索を
続けるために行われる。文３０は、転送を行うためのラ
ベル１３０を備えている。しかし、文２７で試験された
符号値が等しければ、現在の文字によって拡張された前
のストリングは、ストリング・テーブルにＬＯＣ−１に
等しい符号値と一緒に既に記憶された受入れられたスト
リングである。文２８は、符号ＬＯＣ−１を変数ＮＯＤ
ＥＮＯにおいて記憶することによってこの新しいストリ
ングを前のストリングに変換する。次に、文２９は、も
う一つの入力文字を読出して、ストリング拡張処理を繰
返すために文２１に戻る転送を行う。

【０１８３】文２７において、前のＩＴＡＢＬＥ呼出し
が失敗に終わると、文３０に割当てられたラベル１３０
を介して文３０に飛び越しが行われる。文３０は、記憶
場所ＬＯＣが空であるかどうかをその内容の初期値ＩＦ
ＬＩＬに対して等しいことを試験することによって決め
る。その記憶場所が空であれば、求めるべきストリング
は、そのテーブルの中に存在しないと定められて、その
テーブルを更新し、現在のストリングを終了にするため
に飛び越しが文３５へ行われる。文３５への飛び越し
は、その文に割当てられたラベル２００によって行われ
る。しかし、文２７および３０によって行われた試験が
共に失敗したときには、調べられた最後の記憶場所が一
つのストリングまたは空記憶場所を発見するための７番
目の試みを構成するのでなければ、もう一つの記憶場所
が検査されなければならない。従って、文３１は、探索
計数値Ｎを１だけ増分し、文３２は、この次の探索計数
値をそれが７を越しているかどうかを決めるために試験
する。Ｎがこんどは７を超えていれば、それ以上の探索
が試みられず、そのストリングは、そのテーブルの中に
存在しないと定められて文３６への転送が行われる。ラ
ベル３００は、飛び越しを行うために文３６に割当てら
れている。しかし、Ｎがまだ７に等しくなければ、求め
るべきストリングに対する探索は、新しいハッシュ・ア
ドレスにおいて続けられる。文３３は、試験されたばか
りのノード番号へ加えられる接頭部ストリング・ノード
番号から新しいハッシュ・アドレスを計算する。テーブ
ル長を保つために加算が４０９６を法として（モジュロ
４０９６）行われる。この新しいノード番号は、またＦ
ＯＲＴＲＡＮ適法記憶場所ＬＯＣを与えるために１だけ
増やされる。新しいハッシュ・アドレスが計算される
と、文３４は、新しいアドレスに関する探索手順を行う
ために文２６への転送をラベル１２０を介して行う。

【０１８４】文３５は、空記憶場所に遭遇したときに文
３０が転送を行った転送先のプログラム内の状態を切分
ける。ストリング・テーブルは、こんどは、空記憶場所
において、観察されたばかりであるがまだテーブルの中
に入っていない拡張ストリングを入れることによって更
新される。文３５は、ＮＯＤＥＮＯの中に記憶された接
頭部ノード番号を空記憶場所に書込むことによって更新
を行い、それによりその記憶場所のアドレスを新しいス
トリングの圧縮符号記号として割当てる。そのあとで、
ストリングの処理の終りが文３６〜３８によって行われ
る。文３６は、ＩＢＩＴＳＰを呼出してＮＯＤＥＮＯの
中の現在のノード番号を出力バッファＩＢＵＦＢにその
バッファ内のＮＢ番目の１２ビット記憶場所にある１２
ビット符号として置く。次に、文３７は、伝送されたば
かりのストリングの中に含まれていなかった最後に受け
た入力文字を符号番号に変換して、次のストリング探索
の始めを与える。その文字信号は、ＮＯＷＣＨＲの中の
値をＮＯＤＥＮＯに転送することによって符号信号にな
る。次に、文３８は、出力記号計数ＮＢを１だけ増分し
て開始したばかりのストリングに出力１を与え、文３９
は、ラベル１００を介して文２１に戻り転送し、もう一
つ入力文字信号を取出して、主反復ループを行う。

【０１８５】文４０は、現在のデータ・ブロック内のす
べての入力文字を処理したプログラムの中の状態を切り
分ける。従って、文４０は、ＩＢＩＴＳＰを呼出し最後
の部分ストリングを示すＮＯＤＥＮＯ内の最後の１２ビ
ット符号値を出力バッファＩＢＵＦＢのＮＢ番目の位置
に置く。次に、文４１は、入力バッファＩＢＵＦＡ内に
含まれたＮＡ文字信号のデータ・ブロックを圧縮するた
めに表１のサブルーチンＣＯＭＰを呼出した主プログラ
ムに制御を戻す。

【０１８６】表２を参照すると、バッファＩＢＵＦＢの
中に受け入れられたＮＢ個の１２ビット圧縮符号記号信
号のブロックについて伸長を行い、結果として生じた回
復された９ビットの文字信号を出力バッファＩＢＵＦＡ
に詰めて、結果として生じた文字の数の計数ＮＡを戻す
伸長サブルーチンＤＥＣＯＭＰ（ＩＢＵＦＢ、ＮＢ．Ｉ
ＢＵＦＡ、ＮＡ）が示されている。

【０１８７】表１ないし表４に関して説明した本発明の
実施例は、ＦＯＲＴＲＡＮプログラミング言語で与えら
れた圧縮および伸長サブルーチンとして例示されたが、
その圧縮および伸長サブルーチンは、当然に主プログラ
ムとしてフォーマットを作ることができた。これらのプ
ログラムは、例えばコンピュータまたはマイクロプロセ
ッサにおいて、ソフトウェアとして用いることができる
し、または、例えば、磁気ディスクまたはテープの制御
装置の入出力電子回路において用いるためのＲＯＭチッ
プの形でファームウェアとして構成してもよい。なお、
ＦＯＲＴＲＡＮ以外のプログラミング言語を用いること
もできるし、または同じ言語または他の言語における他
のプログラムコーディングを、ここで説明した機能を行
うのに用いて、本発明のデータ信号圧縮および伸長の諸
手順を実施することもできる。

【０１８８】マイクロプロセッサまたは他の形式のコン
ピュータのプログラム格納式のものが、ここで説明した
能力と技術の１実施例を、すなわち、基本的データ操作
の選択および状態順序づけ制御インプリメンテーション
の選択における以外は、ここで述べたデジタル論理式の
ものと区別できない実施例を与えることが分る。汎用コ
ンピュータにおける標準化されたデータ操作の動作を、
ワイヤおよび論理ゲートの形でなく再書込みできる記憶
装置に記憶されたものとしての容易に変更された形式の
制御ロジックと共に作ることの経済性によって、実行速
度のある程度の相対的低下で特定の適用業務に対して経
済的に作ることができ、さ細な方法で経済的に製造で
き、かつ迅速に変更できる実施例を提案できる。

【０１８９】本発明のハードウェア実施例に関する上述
のハッシュ関数は、２０ビットの項目（１２の符号ビッ
トと８の文字ビット）を含む符号、文字タプルを１２ビ
ット・アドレス・スペースにマップする。ソフトウェア
実施例に関して用いられたハッシュ関数は、２１ビット
項目（１２符号ビットと９文字ビット）を２１ビット・
アドレス・スペースにマップする。２０ビットの値およ
び２１ビットの値のすべてが起こるわけではないので、
そのようなハッシュ関数を用いることができる。上述の
ハッシュ関数を前に述べた基準を満たすように設計し
た。なお、このハッシュ関数は、その諸仮定から生ずる
撞着を最小にするように設計され、第１には、幾つかの
個々の入力文字がほかのものよりより頻繁に用いられ、
低い番号の文字が頻繁に使われ易く、そして、第２に
は、幾つかの符号が他のものよりより頻繁に用いられ、
早期に生ずる符号が最も頻繁に用いられるであろう。上
述のものに代るハッシュ関数は、符号の左５ビットを回
転することによって最初のハッシュアドレスを発生し、
その文字ビットに排他的論理和演算を施して回転された
符号の高位ビットにすることにより実施できる。三つの
順次のアドレスが前の１２ビット・ハッシュ・アドレス
にモジュロ４０９６を加えることによって発生され、新
しい１２ビット番号が終端間で反転され、かつ結果とし
て生じた番号の最下位ビットを１に強制して左３ビット
を回転した符号番号を含んでいる。

【０１９０】図２および図３に関して説明した本発明の
実施例は、本発明の代りの実施例を与えるために上述の
ものと異なる組合わせで結合できる種々の随意選択的技
術を用いる。図２の圧縮装置は、単一文字ストリングの
すべてでストリング・テーブルを初期設定するが、一方
図３の圧縮装置は、ゼロストリングだけでストリング・
テーブルを初期設定する。図２については、単一文字ス
トリングの初期設定を単一文字そのものをこれらのスト
リングの符号番号として用い、２^B より大きいアドレス
に対してのみストリング・テーブルにアクセスすること
を可能にすることによって行われる。圧縮されるべき文
字のすべては、Ｂビット・バイトであるから、全ての文
字は、２^B より小さな値をもっている。従って、２^B よ
り小さい符号値をもつ単一文字ストリングが図２の圧縮
装置によってストリング・テーブルのアクセスなしで伝
送される。図３の圧縮装置は、ゼロストリングだけでテ
ーブル初期設定を行うのであって、それのストリング・
テーブルをゼロないし２^C−１のすべてのアドレスで呼
出す。従って、図３の圧縮装置の実施例においては、単
一文字ストリングが、受けた文字を符号番号ゼロでハッ
シュして、結果として生じたハッシュ・アドレスにある
ゼロのストリング接頭部符号を入れることによってスト
リング・テーブルに入れられる。

【０１９１】このほかの変形例としては、図２の圧縮装
置は、ストリングのハッシュ・テーブル・アドレスをそ
れのストリング符号記号信号として割当てるが、一方、
図３の圧縮装置は、新ストリング・エントリーが作られ
るストリング符号記号信号を各ストリングに逐次に割当
てる。

【０１９２】なお別の変形例としては、図２の圧縮装置
は、固定長符号値を各ストリングに割当てるが、一方、
図３の圧縮装置は、可変する長さの符号記号を各ストリ
ングに割当てる。図２の実施例において、固定長はＣビ
ットの全アドレス長であるが、一方図３の実施例におい
ては圧縮符号記号の長さはＣビットの長さが得られるま
でデータブロックの処理の間増える。

【０１９３】前述のように、各変形例は、図２および図
３に開示された実施例において実施される。当業者がこ
れらの変形例を別途組合せて本発明の範囲内で追加の実
施例を作ることができる。上述の四つの変形例の各々
は、二つの可能性をもっているので、１６の別々の実施
例を構成できる。例えば図３の圧縮装置に関して、逐次
割当てストリング符号をＣビットの固定長出力として伝
送できる。その場合、符号大きさ回路１２３を除去でき
る。そのような圧縮装置においてストリング・テーブル
をゼロストリングだけで初期設定する変形例が組入れら
れると（図３で説明したように）、図３の圧縮装置のシ
フト回路網１１８を用いてオールゼロの空白符号の伝送
に続くＢビット・バイトと同様に固定長Ｃビット圧縮符
号信号を伝送するのに用いることができる。しかし、図
３の圧縮装置を上述のように固定長符号の変形例を含む
ように変更し、さらにすべての単一符号のストリングを
使うストリング・テーブル初期設定を用いるように変更
するとすれば、図３の圧縮装置のシフト回路網１１８を
符号番号レジスタ１１９からバス１２０を通して与えら
れる出力と共に除去することになろう。さらに、図３の
符号計数器１２１をストリング・テーブル初期設定が行
われたのちに、２^B にセットすることになる。なお、符
号レジスタ１１６からの図３のバス１１７は、Ｂビット
文字をレジスタ１１９の最下位位置に挿入するために符
号番号レジスタ１１９に加えることになろう。レジスタ
１１９のＣ−Ｂの最上上位位置をゼロにセットすること
になろう。図３の圧縮装置に対する上述の変更は、圧縮
効率を犠牲にして性能を向上させることになろう。

【０１９４】上述のことから、変更された図３のレジス
タ１１６および１１９とそれらの動作との間の関係は、
図２のレジスタ１７および１９とその動作との間の関係
と同一であることが分る。なお、すべての単一文字スト
リングを使ったテーブル初期設定を用いる変更された実
施例においては、図３の比較器１３４へのゼロの値をも
った入力は、用いられない。初めて遭遇する文字の単一
符号ストリングを含む単一文字のストリングは、新しく
遭遇した文字に対して、新しい文字に先立つオールゼロ
の空白符号信号を伝送するのではなく、図２に関して述
べたものと同一の方法で伝送される。

【０１９５】単一文字のストリングのすべてでストリン
グ・テーブルを初期設定し、新しいストリング・エント
リーが作られるとき、ストリング符号記号を逐次に割当
て、そして変化する長さの圧縮符号信号を伝送する圧縮
装置の実施例を作りたい場合は、図３の装置をそれ相応
に変更できる。図３の圧縮装置は、ストリング・テーブ
ルの初期設定が行われたのちに、符号計数器１２１を２
^B にセットすることによって変更できる。なお、文字レ
ジスタ１１６からの図３のバス１１７は、上述のように
符号番号レジスタ１１９へ加えられる。

【０１９６】空白ストリングだけでストリング・テーブ
ルを初期設定するように図２の圧縮装置の実施例を変更
したい場合、比較器２６は空白符号および空符号に等し
いハッシュ関数アドレスを放棄するように変更される。
なお、比較器３２は、文字レジスタ１７の中のＢビット
文字を空白符号の伝送のあとに伝送すべきかどうかを決
定するために符号番号レジスタ１９の中の値をゼロと比
較するように変更される。Ｂビット文字をゼロを満たさ
れたＣビット文字として伝送できるし、またはその代り
にシフト回路網機構を前述のものと同様に用いることも
できる。

【０１９７】上述のことから図２の実施例は、圧縮効率
を犠牲にして最高性能を与えることがわかるであろう。
なお、図３の実施例は、性能を犠牲にして最高圧縮を与
える。各変形例、すなわち、全ての単一文字ストリング
を用いてのテーブル初期設定；新しいストリングを作る
とき逐次に割当てられるストリング符号記号；固定長符
号値を伝送すること；および後入れ先出しスタックを用
いるストリング反転、を組合わせる上述の変更は応用業
務に従って好ましい実施例を与えることのできる最高性
能と最高圧縮との間の中間のものである。

【０１９８】上述のように、表１〜表４は図２の最高性
能ハードウェア実施例の各変形例を用いる本発明のプロ
グラム格納式コンピュータの実施例を示す。本発明の種
々のソフトウェア実施例は、上述の各変形例の種々の組
合せを通常の熟練したコンピュータ・プログラマによっ
て普通に与えられるそのためのプログラムコーディング
と共に用いることによって提供することができる。

【０１９９】まとめると、本発明は入力データの中で観
察された文字のストリングを、多分、圧縮されるべきデ
ータブロックの始めにおいてテーブルを初期設定できる
単一文字ストリングなどのストリングを除いて記憶する
ストリング・テーブルを用いる。それらのストリング
は、各ストリングの記憶されたセットが処理されている
データの統計に適応するようにストリングが入力データ
の文字ストリームの中で観測されるとき、テーブルに動
的に入れられる。Ｘ文字の各ストリングは、Ｘ−１文字
の接頭部ストリングと一つの拡張文字とを含み、その場
合に接頭部ストリングもまたテーブルの１構成要素であ
る。各ストリングは、一つの符号記号を割当てられ、記
憶されたストリングが入力データ文字ストリームの中で
遭遇されると、遭遇したストリングは、圧縮データの中
のその符号信号によって表される。各ストリングは、ス
トリングの符号記号、接頭部ストリングの符号記号、お
よびストリング拡張文字とによって判然とまたは暗黙裏
に（すなわち、直接にまたは間接的に）、のいずれかで
記憶される。データ文字信号のストリームは、各文字の
ストリングにそのストリームをパースすることによって
処理され、各ストリングは、ストリング・テーブルの中
に既に置かれている。このパーシングは、始めの文字か
ら出発して１度に１文字ずつ分離するデータ文字ストリ
ームの中への唯１回のパスにおいて達成される。各文字
は、拡張されたストリングがストリング・テーブル内に
あるものに一致する場合、前のストリングを拡張するの
に用いられる。そうでなければ、その文字は、新しいス
トリングを開始するのに用いられる。基本的には、圧縮
処理は、入力データストリームの中で各文字が出てきた
とき、以下のように各文字に次々に加えられる循環ステ
ップとして考えてもよい。

【０２００】入力データストリームからのストリングＳ
がストリング・テーブル内に置かれていたとする。その
入力データ・ストリームの中で次に続く文字ｃに対し
て、そのテーブルは、拡張ストリングＳｃがその中に存
在するかどうかを決定するために探索される。ストリン
グＳｃがそのテーブルの中に存在すれば、次に続く文字
が試験されてその手続きが再び適用される。拡張ストリ
ングがそのテーブルに存在しなければ、ストリングＳに
対する符号記号が圧縮出力として伝送され、ストリング
Ｓｃがそのテーブルに入れられる。次に文字ｃは、次の
ストリングの最初の文字として用いられて、その手続き
は、次に続く入力文字を用いて再び適用される。

【０２０１】ストリングＳｃに対する探索は、一つのス
トリング・テーブルアドレスを与えるために文字ｃをス
トリングＳに対する符号と組合せることによって行われ
る。拡張ストリングＳｃは、既にそのアドレスの記憶場
所に記憶されていれば、そのストリングＳｃは、そのテ
ーブルの中に存在していることになる。その記憶場所が
空であれば、そのストリングは、そのテーブルの中に存
在しない。その場合には、ストリングＳに対する符号記
号が伝送され、ストリングＳｃが空記憶場所に入れられ
る。できれば、文字ｃとストリングＳに対する符号との
組合せが上述の限定探索ハッシュ手順によって行われる
のが好ましい。圧縮の間、圧縮手順の中の１点において
定められた可能なストリングの数がストリングの実際の
数およびある本質的なファクタによる経済的記憶装置の
大きさを超えることになるので、ハッシュ・テーブル機
械化は、あらかじめ割当てられていないストリングを記
憶するのに用いられる。一般的には、ハッシュ・テーブ
ルの各記憶場所が選択された数学的関数によって割当て
られた可能な項目の割当てられたセットを含むことので
きるものがハッシュ・テーブルである。前述の限定探索
ハッシュ・テーブル・プロセスにおいて、各可能なアド
レスが限られた数の記憶アドレスの小さなグループ内で
のみ現れる。この基準は、可能なエントリを探すためま
たはそれがテーブルの中にないことを定めるために必要
な探索の量を限定する。

【０２０２】圧縮の間ストリングが少なくともそれを識
別するためのその接頭部符号を用いて検索される。伸長
の間、ストリングがその符号記号によって直接に識別さ
れる。伸長装置のストリング・テーブルは、各ストリン
グ記憶場所に接頭部ストリング符号および拡張文字を記
憶し、そのストリング記憶場所は、そのストリングに対
する符号によってアドレス指定可能である。従って、入
力符号記号は、接頭部ストリングおよび拡張文字を与え
るテーブル内で探索される。次に接頭部ストリングは新
接頭部ストリングおよび新拡張文字を与えるテーブル内
で探索される。この過程は始めの単一文字ストリングに
出合うまで繰返される。

【０２０３】本発明の上述の各実施例において、ハッシ
ュアドレスまたは数が大きくなってゆく次々の値がスト
リングのための圧縮符号記号信号として用いられる。こ
れらの値の矛盾のない変更またはアイソモルフィズムも
またそれらのストリングに対する圧縮符号記号信号とし
て用いることができるとわかる。

【０２０４】本発明の上述の実施例の若干の変形を以下
のように容易にわかる設計変更を用いて行うことができ
る。

【０２０５】本発明の圧縮装置がディスク装置またはテ
ープ装置のような同期チャネルに圧縮データを与えてい
る場合、その出力速度がバッファリングを最小にするた
めにチャネルの入力速度に一致するように圧縮装置の速
度を増減するのが望ましいことがある。圧縮装置の出力
速度を達成された圧縮比によって制御し、その圧縮比は
遭遇したデータの形式に従って変わる。圧縮装置が高す
ぎる速度で出力記号を作るように、その圧縮装置が圧縮
しにくいデータに遭遇した場合、圧縮装置を入力文字の
間で待機させることによって減速できる。圧縮装置が非
常に圧縮しやすいデータに遭遇するので、それが出力記
号をあまりゆっくり作る場合、その圧縮装置を圧縮装置
の効率を減らすことによってスピードアップできる。こ
れは、出力符号記号を必要とするときは常に、文字スト
リング拡張を中止することによって行われてもよい。従
って、圧縮装置が必要な出力速度を遅くするときは常に
最長マッチより少ないストリングを選ぶことができる。
なお、圧縮有効度は、データブロックの初期部分を処理
するとき低くなり、そのブロックの処理が続くとき増加
する傾向があるので、圧縮符号ストリームの転送を開始
する前に圧縮を始めて圧縮速度の変化を相殺することが
望ましいことがある。この待ち時間損失は、圧縮データ
を圧縮装置から外部装置に書込むときにのみ起こること
がわかる。圧縮データを外部装置から読出すときには、
圧縮データが外部信号源から使用できるようになったら
直ちに伸長を開始できる。

【０２０６】さらに別の変更が選択された値より小さく
なるようにパースされたストリング長さを制御するため
に圧縮装置の一部分として計数器を用いることを含むこ
とがある。この特徴は、圧縮データの出力速度がさらに
予測しやすくなるように瞬時圧縮比の変動を小さくする
であろう。なお、そのような計数器は、最大ストリング
長さに敏感な伸長装置内の装置の価格を引下げるであろ
う。

【０２０７】本発明のさらに別の変更は、同時にではな
いけれども圧縮および伸長の両方に対して同じハードウ
ェア装置のセットを用いてもよいことである。圧縮およ
び伸長の必要条件の間には、特にＲＡＭについて、同時
性を失ってもよいとき、かなりの価格の節約をこの変更
によって得ることができるという十分な類似性がある。
なお、圧縮を実行する際に連想記憶装置をＲＡＭの代り
に用いることもできよう。そのような変更は、ハッシン
グの必要をなくして制御の複雑さを減らす。

【０２０８】

【発明の効果】本発明は、非常に様々なデータの種類に
ついて適応性のある可逆データ圧縮をデータ統計または
データ冗長度の形式について前もって何ら知ることなし
に達成する。良好な圧縮比を、最も速い今日の磁気テー
プおよび磁気ディスクデータ記憶装置ならびに最も速い
今日の商用通信リンクと共に用いるのに適する高性能動
作で達成することができる。

【図面の簡単な説明】

【図１】データ文字信号のストリームのパースされた部
分の略図である。

【図２】最高性能を与えるように実施された本発明によ
るデータ圧縮装置の略ブロック図である。

【図３】最高圧縮を与えるように実施された本発明によ
るデータ圧縮装置の略ブロック図である。

【符号の説明】

１３制御装置１７文字レジスタ１９符号番号レジスタ２３ハッシュ関数回路２６，３２比較器２８ＲＡＭアドレス・レジスタ２９ＲＡＭ３５初期設定計数器１１３制御装置１１６文字レジスタ１１８シフト回路網１１９符号番号レジスタ１２１符号計数器１２３符号大きさ回路１２７ハッシュ関数回路１３０ＲＡＭアドレス・レジスタ１３１ＲＡＭ１４１初期設定計数器

Claims

【特許請求の範囲】

【請求項１】データ文字信号のストリームを圧縮され
た符号信号ストリームに圧縮する圧縮装置であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをストアし、前記ストアされ
たストリングは、当該ストアされたストリングにそれぞ
れ関連する符号信号を有し、および該符号信号に対応す
るメモリアドレスにストアされるようになしたアドレス
可能なメモリと、前記ストリームを前記メモリ内にストアされたストリン
グと比較して、前記データ文字信号ストリームをサーチ
して前記ストリームとの最長一致を決定し、前記最長一
致中のデータ文字信号の個数に応じて１または２以上の
メモリアドレスにアクセスして最長一致を決定する手段
と、前記最長一致に続く次のデータ文字信号で拡張された前
記データ文字信号ストリームとの最長一致を含む拡張さ
れたストリングを形成する手段と、前記拡張されたストリングに符号信号を割り当てる手段
と、前記拡張されたストリングを前記メモリ内の、割り当て
られた符号信号に対応するメモリアドレスにストアする
手段と、前記最長一致に関連する符号信号を供給して前記圧縮さ
れた符号信号ストリームを供給する手段とを具えたこと
を特徴とする圧縮装置。
【請求項２】最長一致を決定する際に前記サーチする
手段によりアクセスされる各メモリアドレスは、より長
い一致があるか否かを決定するために前記サーチする手
段によって用いられるデータを含むことを特徴とする特
許請求の範囲第１項に記載の装置。
【請求項３】前記サーチする手段によって、アクセス
されたメモリアドレス内にストアされたデータを前記ス
トリームからのデータ文字信号と共に用いて、より長い
一致が存在するときにはそのより長い一致に対応するメ
モリアドレスを決定することを特徴とする特許請求の範
囲第２項に記載の装置。
【請求項４】ストリングを前記メモリに間接的にスト
アすることを特徴とする特許請求の範囲第１項に記載の
装置。
【請求項５】拡張されたストリングは、前記最長一致
の少なくとも表示をストアすることによってメモリアド
レスにストアされることを特徴とする特許請求の範囲第
１項に記載の装置。
【請求項６】前記サーチする手段は、先に定めた最長
一致に続く次のデータ文字信号で始まる次に生じる最長
一致に対するサーチを実行することを特徴とする特許請
求の範囲第１項に記載の装置。
【請求項７】データ文字信号のストリームを圧縮され
た符号信号ストリームに圧縮する圧縮装置であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをストアし、前記ストアされ
たストリングは、当該ストアされたストリングにそれぞ
れ関連する符号信号を有するストア手段と、複数の予め定めたストリングを前記ストア手段内に最初
にストアし、前記データ文字信号のストリームの圧縮の
開始前に、ストアされたストリングに対応する符号信号
を前記ストリングに割り当てる手段と、前記ストリームを該ストア手段内にストアされたストリ
ングと比較することによって、前記データ文字信号のス
トリームをサーチして前記ストリームとの最長一致を決
定する手段と、前記ストア手段にストアするために、前記最長一致に続
く次のデータ文字信号によって拡張された前記データ文
字信号のストリームとの前記最長一致を含む拡張された
ストリングを前記ストア手段に挿入する手段と、前記ストアされた拡張されたストリングに対応する符号
信号を割り当てる手段と、前記最長一致に関連する符号信号を供給して前記圧縮さ
れた符号信号のストリームを供給する手段とを具えたこ
とを特徴とする圧縮装置。
【請求項８】前記メモリ内に最初にストアされた予め
定めたストリングは単一データ文字信号を含むことを特
徴とする特許請求の範囲第７項に記載の装置。
【請求項９】前記単一データ文字信号はデータ文字の
アルファベットの文字に対応することを特徴とする特許
請求の範囲第８項に記載の装置。
【請求項１０】前記アルファベットの文字値に基づい
て、符号信号を前記データ文字のアルファベットに割り
当てられることを特徴とする特許請求の範囲第９項に記
載の装置。
【請求項１１】前記データ文字はASCII 文字であり、
および符号信号をASCII 値に基づいて前記ASCII 文字に
割り当てることを特徴とする特許請求の範囲第１０項に
記載の装置。
【請求項１２】データ文字信号のストリームを圧縮さ
れた符号信号ストリームに圧縮する圧縮装置であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをストアし、前記ストアされ
たストリングは、当該ストアされたストリングにそれぞ
れ関連する符号信号を有するストア手段と、前記ストリームを前記ストア手段内にストアされたスト
リングと比較することによって、前記データ文字信号の
ストリームをサーチして前記ストリームとの最長一致を
決定する手段と、前記ストア手段にストアするために、前記最長一致に続
く次のデータ文字信号によって拡張された前記データ文
字信号のストリームとの前記最長一致を含む拡張された
ストリングを前記ストア手段に挿入する手段と、可変長の符号信号を供給する手段を有し、前記ストアさ
れた拡張されたストリングに対応する符号信号を割り当
てる手段と、前記最長一致に関連する符号信号を供給して前記圧縮さ
れた符号信号ストリームを供給する手段とを具えたこと
を特徴とする圧縮装置。
【請求項１３】データ文字信号のストリームを圧縮さ
れた符号信号ストリームに圧縮する圧縮装置であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをストアし、前記ストアされ
たストリングは、当該ストアされたストリングにそれぞ
れ関連する符号信号を有するストア手段と、前記ストリームを前記ストア手段内にストアされたスト
リングと比較することによって、前記データ文字信号の
ストリームをサーチして前記ストリームとの最長一致を
決定する手段と、前記ストア手段にストアするために、前記最長一致に続
く次のデータ文字信号によって拡張された前記データ文
字信号のストリームとの前記最長一致を含む拡張された
ストリングを前記ストア手段に挿入する手段と、固定長の符号信号を供給する手段を有し、前記ストアさ
れた拡張されたストリングに対応する符号信号を割り当
てる手段と、前記最長一致に関連する符号信号を供給して前記圧縮さ
れた符号信号ストリームを供給する手段とを具えたこと
を特徴とする圧縮装置。
【請求項１４】データ文字信号のストリームを圧縮さ
れた符号信号ストリームに圧縮する圧縮装置であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをストアし、前記ストアされ
たストリングは、当該ストアされたストリングにそれぞ
れ関連する符号信号を有するストア手段と、前記ストリームを前記ストア手段内にストアされたスト
リングと比較することによって、前記データ文字信号の
ストリームをサーチして前記ストリームとの最長一致を
決定する手段と、前記ストア手段にストアするために、前記最長一致に続
く次のデータ文字信号によって拡張された前記データ文
字信号のストリームとの前記最長一致を含む拡張された
ストリングを前記ストア手段に挿入する手段と、符号信号を数値の昇順に割り当てる手段を有し、前記ス
トアされた拡張されたストリングに対応する符号信号を
割り当てる手段と、前記最長一致に関連する符号信号を供給して前記圧縮さ
れた符号信号ストリームを供給する手段とを具えたこと
を特徴とする圧縮装置。
【請求項１５】データ文字信号のストリームを圧縮さ
れた符号信号ストリームに圧縮する圧縮装置であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをストアし、前記ストアされ
たストリングは、当該ストアされたストリングにそれぞ
れ関連する符号信号を有するストア手段と、前記ストリームを前記ストア手段内にストアされたスト
リングと比較することによって、前記データ文字信号の
ストリームをサーチして前記ストリームとの最長一致を
決定する手段と、前記ストア手段にストアするために、前記最長一致に続
く次のデータ文字信号によって拡張された前記データ文
字信号のストリームとの前記最長一致を含む拡張された
ストリングを前記ストア手段に挿入する手段と、前記最長一致に関連する符号信号を供給して前記圧縮さ
れた符号信号ストリームを供給する手段とを具え、前記サーチ手段は、前記データ文字信号のストリームを
繰り返して分析するよう動作して前記ストア手段内にス
トアされたストリングとの最長一致を決め、次の最長一
致のための各サーチは、先行する最長一致に続く次のデ
ータ文字信号で始まることを特徴とする圧縮装置。
【請求項１６】前記データ文字信号のストリームの圧
縮が前記データ文字信号のストリームの単一のパスにお
いて達成されることを特徴とする特許請求の範囲第１５
項に記載の装置。
【請求項１７】前記圧縮装置により行われる圧縮は無
損失であることを特徴とする特許請求の範囲第１６項に
記載の装置。
【請求項１８】データ文字信号のストリームを圧縮さ
れた符号信号ストリームに圧縮する圧縮装置であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをストアし、前記ストアされ
たストリングは、当該ストアされたストリングにそれぞ
れ関連する符号信号を有するストア手段と、前記ストリームを前記ストア手段内にストアされたスト
リングと比較することによって、前記データ文字信号の
ストリームをサーチして前記ストリームとの最長一致を
決定する手段と、前記ストア手段にストアするために、前記最長一致に続
く次のデータ文字信号によって拡張された前記データ文
字信号のストリームとの前記最長一致を含む拡張された
ストリングを前記ストア手段に挿入する手段と、前記ストアされた拡張されたストリングに対応する符号
信号を割り当てる手段と、前記最長一致に関連する符号信号を供給して前記圧縮さ
れた符号信号のストリームを供給する手段と、前記データ文字信号のストリームのサーチが当該ストリ
ームの終端に達したか否かを決定するための手段とを具
えたことを特徴とする圧縮装置。
【請求項１９】前記サーチが前記データ文字信号のス
トリームの終端に達すると、前記データ文字信号のスト
リーム中の最後のデータ文字ストリングに対応する符号
値が前記圧縮されたストリームでの使用のため供給され
ることを特徴とする特許請求の範囲第１８項に記載の装
置。
【請求項２０】前記サーチが前記データ文字信号のス
トリームの終端に達したことに応答して、ストリームの
終端の表示が提供されることを特徴とする特許請求の範
囲第１８項に記載の装置。
【請求項２１】データ文字信号のストリームを圧縮さ
れた符号信号ストリームに圧縮する圧縮装置であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをストアし、前記ストアされ
たストリングは、当該ストアされたストリングにそれぞ
れ関連する符号信号を有するストア手段と、前記ストリームを前記ストア手段内にストアされたスト
リングと比較することによって、前記データ文字信号の
ストリームをサーチして前記ストリームとの最長一致を
決定する手段と、前記ストア手段にストアするために、前記最長一致に続
く次のデータ文字信号によって拡張された前記データ文
字信号のストリームとの前記最長一致を含む拡張された
ストリングを前記ストア手段に挿入する手段と、前記ストアされた拡張されたストリングに対応する符号
信号を割り当てる手段と、前記最長一致に関連する符号信号を供給して前記圧縮さ
れた符号信号のストリームを供給する手段と、前記圧縮装置により行われた圧縮を変化させる手段とを
具えたことを特徴とする圧縮装置。
【請求項２２】前記圧縮を変化させる手段は圧縮比を
変化させることを特徴とする特許請求の範囲第２１項に
記載の装置。
【請求項２３】前記圧縮を変化させる手段は圧縮速度
を変化させることを特徴とする特許請求の範囲第２１項
に記載の装置。
【請求項２４】データ文字信号のストリームを圧縮さ
れた符号信号ストリームに圧縮する圧縮装置であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをストアし、前記ストアされ
たストリングは、当該ストアされたストリングにそれぞ
れ関連する符号信号を有するストア手段と、前記ストリームを前記ストア手段内にストアされたスト
リングと比較することによって、前記データ文字信号の
ストリームをサーチして前記ストリームとの最長一致を
決定する手段と、前記ストア手段にストアするために、前記最長一致に続
く次のデータ文字信号によって拡張された前記データ文
字信号のストリームとの前記最長一致を含む拡張された
ストリングを前記ストア手段に挿入する手段と、前記ストアされた拡張されたストリングに対応する符号
信号を割り当てる手段と、前記最長一致に関連する符号信号を供給して前記圧縮さ
れた符号信号のストリームを供給する手段と、前記サーチする手段の動作を中断する手段とを具えたこ
とを特徴とする圧縮装置。
【請求項２５】データ文字信号のストリームを圧縮さ
れた符号信号ストリームに圧縮する圧縮方法であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをアドレス可能なメモリにス
トアし、前記ストアされたストリングは、当該ストアさ
れたストリングにそれぞれ関連する符号信号を有し、お
よび前記ストリングを該符号信号に対応するメモリアド
レスにストアするステップと、前記ストリームを前記メモリ内にストアされたストリン
グと比較して、前記データ文字信号ストリームをサーチ
して前記ストリームとの最長一致を決定し、前記最長一
致中のデータ文字信号の個数に応じて1 または2 以上の
メモリアドレスにアクセスして最長一致を決定するステ
ップと、前記最長一致に続く前記次のデータ文字で拡張された前
記データ文字信号のストリームとの最長一致を含む拡張
されたストリングを形成するステップと、前記拡張されたストリングに符号信号を割り当てるステ
ップと、前記拡張されたストリングを前記メモリ内の、割り当て
られた符号信号に対応するメモリアドレスにストアする
ステップと、前記最長一致に関連する符号信号を供給して圧縮された
前記符号信号ストリームを供給するステップとを具えた
ことを特徴とする圧縮方法。
【請求項２６】最長一致を決定する際にサーチしてい
る間にアクセスされる各メモリアドレスは、より長い一
致があるか否かを決定するために前記サーチによって用
いられるデータを含むことを特徴とする特許請求の範囲
第２５項に記載の方法。
【請求項２７】サーチの間、アクセスされたメモリア
ドレス内にストアされたデータを前記ストリームからの
データ文字信号と共に用いて、より長い一致が存在する
ときにはその長い一致に対応するメモリアドレスを決定
することを特徴とする特許請求の範囲第２６項に記載の
方法。
【請求項２８】ストリングを前記メモリに間接的にス
トアすることを特徴とする特許請求の範囲第２５項に記
載の方法。
【請求項２９】拡張されたストリングは、前記最長一
致の少なくとも表示をストアすることによってメモリア
ドレスにストアされることを特徴とする特許請求の範囲
第２５項に記載の方法。
【請求項３０】前記サーチするステップは、先に定め
た最長一致に続く次のデータ文字信号で始まる次に生じ
る最長一致に対するサーチを実行することを特徴とする
特許請求の範囲第２５項に記載の方法。
【請求項３１】データ文字信号のストリームを圧縮さ
れた符号信号ストリームに圧縮する圧縮方法であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをストア手段にストアし、前
記ストアされたストリングは、当該ストアされたストリ
ングにそれぞれ関連する符号信号を有するステップと、複数の予め定めたストリングを前記ストア手段に最初に
ストアし、および前記データ文字信号のストリームの圧
縮を始める前に対応する符号信号を前記ストリングに割
り当てるステップと、前記ストリームを前記ストア手段内にストアされたスト
リングと比較して、前記データ文字信号のストリームを
サーチして前記ストリームとの最長一致を決定するステ
ップと、前記ストア手段にストアするために、前記最長一致に続
く次のデータ文字信号によって拡張された前記データ文
字信号のストリームとの前記最長一致を含む拡張された
ストリングを前記ストア手段に挿入するステップと、前記ストアされた拡張されたストリングに対応する符号
信号を割り当てるステップと、前記最長一致に関連する符号信号を供給して前記圧縮さ
れた符号信号ストリームを供給するステップとを具えた
ことを特徴とする圧縮方法。
【請求項３２】前記メモリ内に最初にストアされた予
め定めたストリングは単一データ文字信号を含むことを
特徴とする特許請求の範囲第３１項に記載の方法。
【請求項３３】前記単一データ文字はデータ文字のア
ルファベットの文字に対応することを特徴とする特許請
求の範囲第３２項に記載の方法。
【請求項３４】前記アルファベットの文字値に基づい
て、符号信号を前記データ文字のアルファベットに割り
当てることを特徴とする特許請求の範囲第３３項に記載
の方法。
【請求項３５】前記データ文字はASCII 文字であり、
および符号信号をASCII 値に基づいて前記ASCII 文字に
割り当てることを特徴とする特許請求の範囲第３４項に
記載の方法。
【請求項３６】データ文字信号ストリームを圧縮され
た符号信号ストリームに圧縮する圧縮方法であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをストア手段にストアし、前
記ストアされたストリングは、当該ストアされたストリ
ングにそれぞれ関連する符号信号を有するステップと、前記ストリームを前記ストア手段内にストアされたスト
リングと比較して、前記データ文字信号のストリームを
サーチして前記ストリームとの最長一致を決定するステ
ップと、前記ストア手段にストアするために、前記最長一致に続
く次のデータ文字信号によって拡張された前記データ文
字信号のストリームとの前記最長一致を含む拡張された
ストリングを前記ストア手段に挿入するステップと、前記ストアされた拡張されたストリングに対応する符号
信号を割り当て、その割り当てられた符号信号は可変長
であるステップと、前記最長一致に関連する符号信号を供給して前記圧縮さ
れた符号信号ストリームを供給するステップとを具えた
ことを特徴とする圧縮方法。
【請求項３７】データ文字信号ストリームを圧縮され
た符号信号ストリームに圧縮する圧縮方法であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをストア手段にストアし、前
記ストアされたストリングは、当該ストアされたストリ
ングにそれぞれ関連する符号信号を有するステップと、前記ストリームを前記ストア手段内にストアされたスト
リングと比較して、前記データ文字信号のストリームを
サーチして前記ストリームとの最長一致を決定するステ
ップと、前記ストア手段にストアするために、前記最長一致に続
く次のデータ文字信号によって拡張された前記データ文
字信号のストリームとの前記最長一致を含む拡張された
ストリングを前記ストア手段に挿入するステップと、前記ストアされた拡張されたストリングに対応する符号
信号を割り当て、その割り当てられた符号信号は固定長
であるステップと、前記最長一致に関連する符号信号を供給して前記圧縮さ
れた符号信号ストリームを供給するステップとを具えた
ことを特徴とする圧縮方法。
【請求項３８】データ文字信号ストリームを圧縮され
た符号信号ストリームに圧縮する圧縮方法であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをストア手段にストアし、前
記ストアされたストリングは、当該ストアされたストリ
ングにそれぞれ関連する符号信号を有するステップと、前記ストリームを前記ストア手段内にストアされたスト
リングと比較して、前記データ文字信号のストリームを
サーチして前記ストリームとの最長一致を決定するステ
ップと、前記ストア手段にストアするために、前記最長一致に続
く次のデータ文字信号によって拡張された前記データ文
字信号のストリームとの前記最長一致を含む拡張された
ストリングを前記ストア手段に挿入するステップと、前記ストアされた拡張されたストリングに対応し、数値
の昇順で割り当てられる符号信号を割り当てるステップ
と、前記最長一致に関連する符号信号を供給して前記圧縮さ
れた符号信号ストリームを供給するステップとを具えた
ことを特徴とする圧縮方法。
【請求項３９】データ文字信号ストリームを圧縮され
た符号信号ストリームに圧縮する圧縮方法であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをストア手段にストアし、前
記ストアされたストリングは、当該ストアされたストリ
ングにそれぞれ関連する符号信号を有するステップと、前記ストリームを前記ストア手段内にストアされたスト
リングと比較して、前記データ文字信号のストリームを
サーチして前記ストリームとの最長一致を決定するステ
ップと、前記ストア手段にストアするために、前記最長一致に続
く次のデータ文字信号によって拡張された前記データ文
字信号のストリームとの前記最長一致を含む拡張された
ストリングを前記ストア手段に挿入するステップと、前記最長一致に関連する符号信号を供給して前記圧縮さ
れた符号信号ストリームを供給するステップとを具え、前記サーチを行うステップは、前記データ文字信号のス
トリームにおけるデータ文字を繰り返して分析するよう
動作して前記ストア手段内にストアされたストリングと
の最長一致を決め、次の最長一致のための各サーチは、
先行する最長一致に続く次のデータ文字信号で始まるこ
とを特徴とする圧縮方法。
【請求項４０】前記データ文字信号のストリームの圧
縮は前記データ文字信号のストリームの単一のパスにお
いて達成されることを特徴とする請求項39に記載の方
法。
【請求項４１】前記圧縮方法により行われる圧縮は無
損失であることを特徴とする特許請求の範囲第４０項に
記載の方法。
【請求項４２】データ文字信号ストリームを圧縮され
た符号信号ストリームに圧縮する圧縮方法であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをストア手段にストアし、前
記ストアされたストリングは、当該ストアされたストリ
ングにそれぞれ関連する符号信号を有するステップと、前記ストリームを前記ストア手段内にストアされたスト
リングと比較して、前記データ文字信号のストリームを
サーチして前記ストリームとの最長一致を決定するステ
ップと、前記ストア手段にストアするために、前記最長一致に続
く次のデータ文字信号によって拡張された前記データ文
字信号のストリームとの前記最長一致を含む拡張された
ストリングを前記ストア手段に挿入するステップと、前記ストアされた拡張されたストリングに対応する符号
信号を割り当てるステップと、前記最長一致に関連する符号信号を供給して前記圧縮さ
れた符号信号ストリームを供給するステップと、前記データ文字信号のストリームのサーチが当該ストリ
ームの終端に達したか否かを決定するためのステップと
を具えたことを特徴とする圧縮方法。
【請求項４３】前記サーチが前記データ文字信号のス
トリームの終端に達すると、前記データ文字信号のスト
リームの最後のデータ文字ストリングに対応する符号値
が前記圧縮されたストリームでの使用のため供給される
ことを特徴とする特許請求の範囲第４２項に記載の方
法。
【請求項４４】前記サーチが前記データ文字信号のス
トリームの終端に達したことに応答して、ストリームの
終端の表示が提供されることを特徴とする特許請求の範
囲第４２項に記載の方法。
【請求項４５】データ文字信号ストリームを圧縮され
た符号信号ストリームに圧縮する圧縮方法であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをストア手段にストアし、前
記ストアされたストリングは、当該ストアされたストリ
ングにそれぞれ関連する符号信号を有するステップと、前記ストリームを前記ストア手段内にストアされたスト
リングと比較して、前記データ文字信号のストリームを
サーチして前記ストリームとの最長一致を決定するステ
ップと、前記ストア手段にストアするために、前記最長一致に続
く次のデータ文字信号によって拡張された前記データ文
字信号のストリームとの前記最長一致を含む拡張された
ストリングを前記ストア手段に挿入するステップと、前記ストアされた拡張されたストリングに対応する符号
信号を割り当てるステップと、前記最長一致に関連する符号信号を供給して前記圧縮さ
れた符号信号ストリームを供給するステップと、前記圧縮方法により行われた圧縮を変化させるステップ
とを具えたことを特徴とする圧縮方法。
【請求項４６】前記変化させるステップは圧縮比を変
えることを含むことを特徴とする特許請求の範囲第４５
項に記載の方法。
【請求項４７】前記変化させるステップは圧縮の速度
を変えることを含むことを特徴とする特許請求の範囲第
４５項に記載の方法。
【請求項４８】データ文字信号ストリームを圧縮され
た符号信号ストリームに圧縮する圧縮方法であって、前記データ文字信号のストリーム中において遭遇するデ
ータ文字信号のストリングをストア手段にストアし、前
記ストアされたストリングは、当該ストアされたストリ
ングにそれぞれ関連する符号信号を有するステップと、前記ストリームを前記ストア手段内にストアされたスト
リングと比較して、前記データ文字信号のストリームを
サーチして前記ストリームとの最長一致を決定するステ
ップと、前記ストア手段にストアするために、前記最長一致に続
く次のデータ文字信号によって拡張された前記データ文
字信号のストリームとの前記最長一致を含む拡張された
ストリングを前記ストア手段に挿入するステップと、前記ストアされた拡張されたストリングに対応する符号
信号を割り当てるステップと、前記最長一致に関連する符号信号を供給して前記圧縮さ
れた符号信号ストリームを供給するステップと、圧縮の動作を中断することを提供するステップとを具え
たことを特徴とする圧縮方法。