JP2610084B2 - データ伸長方法および装置ならびにデータ圧縮伸長方法および装置 - Google Patents

データ伸長方法および装置ならびにデータ圧縮伸長方法および装置

Info

Publication number
JP2610084B2
JP2610084B2 JP4334804A JP33480492A JP2610084B2 JP 2610084 B2 JP2610084 B2 JP 2610084B2 JP 4334804 A JP4334804 A JP 4334804A JP 33480492 A JP33480492 A JP 33480492A JP 2610084 B2 JP2610084 B2 JP 2610084B2
Authority
JP
Japan
Prior art keywords
string
data
character
code
data character
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.)
Expired - Lifetime
Application number
JP4334804A
Other languages
English (en)
Other versions
JPH07249996A (ja
Inventor
テリィ・アーチャー・ウエルチ
Original Assignee
ユニシス コーポレーション
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Family has litigation
First worldwide family litigation filed litigation Critical https://patents.darts-ip.com/?family=24011192&utm_source=google_patent&utm_medium=platform_link&utm_campaign=public_patent_search&patent=JP2610084(B2) "Global patent litigation dataset” by Darts-ip is licensed under a Creative Commons Attribution 4.0 International License.
Application filed by ユニシス コーポレーション filed Critical ユニシス コーポレーション
Publication of JPH07249996A publication Critical patent/JPH07249996A/ja
Application granted granted Critical
Publication of JP2610084B2 publication Critical patent/JP2610084B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

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
    • H03M7/3088—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method employing the use of a dictionary, e.g. LZ78

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)
  • Signal Processing For Digital Recording And Reproducing (AREA)
  • Transmission Systems Not Characterized By The Medium Used For Transmission (AREA)

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は一般的にいえば、データ
圧縮および圧縮データの伸長（ｄｅｃｏｍｐｒｅｓｓｉ
ｏｎ）の分野に関するものである。さらに具体的にいえ
ば、ディジタル入力信号の流れにおいて新しく遭遇した
文字ストリングごとに接頭部ストリングと一つの拡張文
字からなる文字ストリングとして割り当てた符号信号を
用いて圧縮した符号信号の流れからディジタル入力信号
の流れを回復するデータ伸長方法とその方法を実現する
ためのデータ伸長装置ならびにデータ圧縮伸長方法およ
び装置に関する。
【０００２】
【従来の技術】ディジタル・データ信号のストリームを
圧縮されたディジタル・データ信号に符号化して、圧縮
されたディジタル・データ信号を元のデータ信号に復元
するデータ圧縮装置が従来知られている。データ圧縮と
は、与えられたフォーマットのデータを元のものより少
ないビットをもつもう一つのフォーマットに変換するす
べての処理をいう。データ圧縮装置の目的はディジタル
情報の与えられた主要部を保持するに必要な記憶装置の
量またはその主要部を伝送するに必要な時間の量を節約
することである。圧縮比は、符号化されたデータの長さ
の元の入力データの長さに対する比として定義される。
圧縮比が小さければ小さいほど、記憶域または時間の節
約が大きくなる。データ記憶に必要な記憶装置またはデ
ータ伝送に必要な時間を減らすことによって、圧縮は金
銭上の節約をもたらす。磁気ディスクまたは磁気テープ
のような物理的装置がデータファイルの格納に用いられ
れば、圧縮されたデータを格納する装置に必要なスペー
スが小さくなって利用するディスクまたはテープが少な
くなる。電話線またはサテライト・リンクをディジタル
情報の伝送に用いる場合、伝送の前にデータを圧縮する
とコストが下がる。データ圧縮装置は、元のデータが高
い頻度で現れる記号または記号のストリングを持つよう
な冗長性を含む場合に特に有効である。データ圧縮装置
がデータの入力ブロックをより簡潔な形に変換し、その
あとでその簡潔な形を逆にそれの元のフォーマットの元
のデータに翻訳または伸長する。
【０００３】例えば、日刊新聞の内容をサテライト・リ
ンクを経て遠隔の地に伝送して、そこで印刷することが
望まれることがある。適当なセンサが新聞の内容を直列
に発生する文字のデータ・ストリームに変換して、通信
リンクを介して伝送することができる。新聞の内容を含
む何百万の記号が伝送前に圧縮されて受信者のところで
再構成されるとすればかなりの量の伝送時間が節約され
るであろう。
【０００４】別の例として、定期航空路予約データベー
スまたはバンキング・システム・データベースなどの広
範囲なデータベースが記録保管の目的で格納されると
き、データベースを構成する文字の全体が記憶に先立っ
て圧縮されて、あとで使用するには格納された圧縮ファ
イルから再び広げられるとすれば、かなりの量の記憶ス
ペースが節約されるであろう。
【０００５】
【発明が解決しようとする課題】実際にそして一般に役
立つようにするためには、ディジタル・データ圧縮装置
がある基準を満足する必要がある。この装置はデータ圧
縮装置およびデータ伸長装置が仲介している機器によっ
て授受されるデータ速度に関して高い性能を与える必要
がある。データ圧縮できる速度は、圧縮装置に入る入力
データ処理速度によって決まり、普通数百万バイト毎秒
（メガバイト／秒）である。普通１メガバイト／秒を超
える速度を持つ今日のディスク、テープおよび通信装置
において達成されたデータ速度を保つには高性能が必要
である。従って、データ圧縮装置およびデータ伸長装置
は、最近の装置で達成される帯域幅に一致するデータ帯
域幅をもっていなければならない。従来のデータ圧縮装
置およびデータ伸長装置の性能は、普通、統計的データ
を記憶して圧縮処理および伸長処理を管理するのに用い
られるランダムアクセス記憶装置（ＲＡＭ）などの速度
によって制限される。圧縮装置に対する高性能は、圧縮
装置に入る入力文字ごとに必要なｒａｍサイクル（読み
書き動作）の数によって特徴づけられる。記憶サイクル
の数が少なければ少ないほど性能は高い。高性能設計を
電話通信等の低速度の適用業務に対して経済的な低速Ｒ
ＡＭを用いて利用でき、または磁気ディスク転送に対し
て超高速ＲＡＭを用いて利用できる。
【０００６】データ圧縮装置およびデータ伸長装置の設
計におけるもう一つの重要な基準は、圧縮有効度であ
る。圧縮有効度は装置の圧縮比によって特徴づけられ
る。圧縮比は、圧縮された形のデータ記憶の大きさを圧
縮されていない形のデータ記憶の大きさで割った比であ
る。データが圧縮可能であるためには、そのデータは、
冗長度を含んでいなければならない。圧縮有効性は、圧
縮手順が入力データにおける冗長性のいろいろな形態に
いかに有効に調和するかによって決められる。代表的な
コンピュータに記憶されたデータ、例えば整数の配列、
テキストまたはプログラムなどにおいて、冗長は個々の
記号表記法、例えば数字、バイトの不統一な使用と共通
語などの記号列、空白記録欄などの頻繁な繰返しの両方
において起こる。有効なデータ圧縮装置は、両方の形式
の冗長性に応じる必要がある。
【０００７】データ圧縮装置およびデータ伸長装置の設
計における別の重要な基準は、適応性の基準である。多
くの従来のデータ圧縮手段は、圧縮されようとするデー
タの以前の知識または統計を必要とする。従来の手順の
あるものは、データが受けられるときのデータの統計に
適用する。従来の処理における適応性は、法外な複雑度
を必要とした。普通には、汎用コンピュータ施設におけ
る必要条件である広範囲の情報形式にわたって適応圧縮
および伸長装置を用いることができる。圧縮装置は、デ
ータ統計の以前の知識がなくても良好な圧縮比を達成す
ることが望ましい。現在利用できるデータ圧縮手順およ
びデータ伸長手段は、一般には適応できないので、それ
を汎用用途には利用できない。
【０００８】データ圧縮装置およびデータ伸長装置の設
計におけるもう一つの重要な基準は、可逆性の基準であ
る。データ圧縮装置が可逆性の性質をもつためには、そ
の装置は、圧縮されたデータを情報の変質または損失な
しにその元の形に再拡張または伸長することができなけ
ればならない。伸長されたデータと元のデータとは同一
であって互いに区別できないものでなければならない。
【０００９】適応性のあるようにされているか、または
適応性のあるようにされる可能性のある汎用データ圧縮
手段が従来技術において知られており、二つの該当する
手順は、ハフマン（Ｈｕｆｆｍａｎ）法およびタンスタ
ル（Ｔｕｎｓｔａｌｌ）法である。ハフマン法は広く知
られて用いられており、それに関してはハフマンの「最
小冗長性コードの構成のための方法」という論文［プロ
シーディングスＩＲＥ、第４０巻、第１０号、１０９８
〜１１００頁（１９５２年９月）］に出ている。さらハ
フマンの方法については、Ｒ．ガラハ（Ｇａｌｌａｇｈ
ｅｒ）の「ハフマンによる論文についての変形」という
論文［ＩＥＥＥ情報理論トランザクションズ，ＩＴ−２
４，Ｎｏ．６（１９７８年１１月）］に見ることができ
る。適応ハフマン・コーディングは、固定長の記号列を
可変長さ２進語に写像する。適応ハフマン・コーディン
グは、その方法が解釈できる固定列長より長い入力記号
列内に冗長があるとき、それが有効でないという限界を
もっているという欠点がある。ハフマン法を実際に装置
として具体化するときは、入力列長は、ＲＡＭの価格の
ために１２ビットを超えることは殆どないので、この方
法は、一般は良好な圧縮比を達成しない。なお、適応ハ
フマン法は複雑で、各入力記号に対して法外に多数の記
憶サイクルを必要とすることが多い。従って、適応ハフ
マン法は、望ましくないほどわずらわしく、高価でかつ
遅い傾向があるために、この方法を実際的な現在の設備
のほとんどに適さなくしている。
【００１０】タンスタルの方法については、Ｂ．Ｔ．タ
ンスタルの「雑音のない圧縮コードの合成」という題名
の博士論文、［ジョージア・インスティチュート・オブ
・テクノロジ（１９６７年９月）］に見ることができ
る。タンスタルの方法は、可変長の入力記号列を固定長
の２進出力語に写像する。タンスタル法の適応形は、従
来技術に記載されていないが、一つの適応形を誘導でき
る可能性はあるものの、それは複雑で高性能の装置にす
るには不適切であろう。ハフマン法もタンスタル法も原
始記号の組合せの長さが段々長くなると符号化すること
ができなくなる。
【００１１】従来技術の欠点の多くを克服するさらに別
の適応データ圧縮および伸長装置は、Ｍ．コーイン（Ｃ
ｏｈｅｎ）、Ｗ．イーストマン（Ｅａｓｔｍａｎ）、
Ａ．レンペル（Ｌｅｍｐｅｌ）およびＪ．ジブ（Ｚｉ
ｖ）の米国特許第４，４６４，６５０号（データの圧縮
と圧縮されたデータの伸長の装置と方法」（１９８１年
８月１０日出願）に開示されたものである。前記米国特
許第４，４６４，６５０号の方法は入力データの記号の
ストリームを記号の適応増大する列に分解する。前記特
許第４，４６４，６５０号の方法は、入力文字ごとに多
数のＲＡＭサイクルを必要として、圧縮および伸長を行
うために乗算および除算のような時間のかかる複雑な数
学的手順を用いるという欠点をもっている。これらの欠
点は、前記特許第４，４６４，６５０号の方法を多くの
経済的で高性能の装置として実現するのに不適当にする
傾向がある。前述のことから従来技術も前記米国特許第
４，４６４，６５０号の方法も高性能のアプリケーショ
ンに適する適応性があり、かつ効率的な圧縮装置および
伸長装置を提供しないことがわかる。既知の従来の設計
アプローチは、そのような装置には直接には適当ではな
い。
【００１２】したがって、本発明の目的は、前述の新規
なデータ圧縮方式によって圧縮された圧縮符号を確実に
かつ経済的に元のデータに伸長する方法および装置を提
供することにある。
【００１３】本発明の他の目的は、前述の新規なデータ
圧縮方式によってデータを圧縮し、かつその圧縮された
圧縮符号を確実にかつ経済的に元のデータに伸長するデ
ータ圧縮伸長方法および装置を提供することにある。
【００１４】本発明は、上述の装置の欠点を、良好な圧
縮比を達成する経済的で高性能で適応性があり、可逆的
なデータ圧縮装置によって圧縮されたデータを伸長する
装置と方法を提供することによって克服する。本発明の
伸長装置に入力される圧縮データは圧縮装置によって入
力データ・ストリームからパース（構文解析して分解す
ること）されたデータ文字信号のストリングを格納（ス
トア）し、そのストリームとの最長一致を決めるため
に、そのストリームを格納されたストリングと比較して
データ文字信号のストリームを探索（サーチ）すること
によって、データ文字信号のストリームを符号信号の圧
縮されたストリームに圧縮する。この圧縮装置はまた、
データ文字信号のストリームからの最長一致を含み最長
一致に続く次の一つのデータ文字信号によって拡張され
た拡張ストリングを格納する。最長一致を拡張して格納
するとき、格納された拡張ストリングに対応する符号信
号がそれに割当てられる。符号信号の圧縮されたストリ
ームは、格納された最長一致に対応する符号信号で作ら
れる。データ文字の格納されたストリングが接頭部スト
リングと拡張文字で構成される。ストリングがその接頭
部ストリングに対応する符号信号によって格納される。
【００１５】本発明によれば、符号信号の圧縮されたス
トリームは、接頭符号信号および拡張文字信号を含む文
字ストリングを構成して格納することによって伸張され
る。さらに詳しくいえば、本発明においては、符号信号
を逐次に受け、受けた符号信号が単一文字に対応するか
どうかを決定し、受けた符号信号が単一文字に対応する
場合は、該単一文字を出力し、受けた符号信号が単一文
字に対応しない場合は、ストリングテーブルの中に該符
号信号を少なくともデータ文字信号の接頭部ストリング
と一つの拡張文字信号として記憶し、次に、前記ストリ
ングテーブルを探索して、受けた符号信号の最終文字信
号を抽出し、前記受けた符号信号の接頭部ストリングに
ついて前記ストリングテーブルを探索して該接頭部スト
リングに対応するデータ文字ストリングの最終文字信号
を抽出し、この操作を次々の接頭部ストリングが単一文
字を表す符号信号になるまで繰返し、前記受けた符号信
号について抽出された文字ストリングの順序を逆にし、
抽出された順序を逆にされた文字ストリングを出力する
ことによって圧縮されたディジタルデータ信号を伸張す
る。
【００１６】データ文字信号のストリングは、各探索繰
返しに対する限られた数のハッシュアドレスを与える限
定探索ハッシング技術によって記憶装置に入れられる。
【００１７】本発明の第１の形態は、データ文字ストリ
ームにおける、データ文字ストリングに対応する圧縮さ
れた符号信号ストリームから、当該データ文字ストリー
ムを復元するデータ伸長方法において、前記圧縮された
符号信号ストリームを受信するステップと、その受信し
た符号信号から対応するデータ文字ストリングを取り出
すステップであって、受信した符号信号を用いて、前記
符号信号に対応するデータ文字ストリングをストアする
メモリから、対応するデータ文字ストリングを検索する
ステップを含むステップと、取り出されたデータ文字ス
トリングを用いて前記データ文字ストリームを復元する
ステップと、前記取り出すステップに応答して、拡張さ
れたストリングを前記メモリにストアすることによっ
て、前記符号信号に応答してデータ文字ストリングを前
記メモリに供給するステップとを具え、取り出されたデ
ータ文字ストリングを、次に取り出されたデータ文字ス
トリングの第１文字と連結させて、拡張されたストリン
グを形成し、および拡張されたストリングの各々を、対
応する符号信号を用いて、前記メモリから検索可能な形
態で、前記メモリにストアすることを特徴とする。
【００１８】ここで、前記圧縮された符号信号ストリー
ムは、前記データ文字ストリーム中のデータ文字を探索
して、割り当てられた符号信号を持つデータ文字ストリ
ングとの最長一致を決定して生成されたものに対応し、
決定された最長一致に対応する符号信号を用いて前記圧
縮されたストリームを生成し、および各決定された最長
一致を、データ文字ストリームにおいて次に続く文字と
連結させて、最長一致を決定するために用いるデータ文
字ストリングを供給することを特徴とする。
【００１９】ここで、前記対応するデータ文字ストリン
グを取り出すステップは、受信した符号信号が最初にス
トアされた文字に対応するか否かを決定し、対応する場
合は、当該文字を、取り出したデータ文字ストリングと
して用いるステップを含むことを特徴とする。
【００２０】ここで、複数の予め定めたストリングを最
初にストアし、および前記圧縮されたストリームを伸長
する前に、対応する符号信号を前記複数の予め定めたス
トリングに割り当てるステップを含むことを特徴とす
る。
【００２１】ここで、最初にストアされた予め定めたス
トリングは、前記データ文字ストリーム中の個別の文字
に対応するストリングを含むことを特徴とする。
【００２２】ここで、受信した符号信号を用いて前記メ
モリをアドレス指定して対応するデータ文字ストリング
を検索することを特徴とする。
【００２３】ここで、符号信号に応答して前記メモリか
ら逆の順序でデータ文字ストリングを検索し、および検
索されたデータ文字を反転させて、検索に用いた符号信
号に対応するデータ文字ストリングを生成するステップ
を含むことを特徴とする。
【００２４】また本発明の第２の形態は、データ文字ス
トリームにおける、データ文字ストリングに対応する圧
縮された符号信号ストリームから、当該データ文字スト
リームを復元するデータ伸長装置において、前記圧縮さ
れた符号信号ストリームを受信する手段と、その受信し
た符号信号に応答して、対応するデータ文字ストリング
を取り出す手段であって、受信した符号信号に応答し
て、前記符号信号に対応するデータ文字ストリングをス
トアするメモリから、対応するデータ文字ストリングを
検索する手段を含む手段と、取り出されたデータ文字ス
トリングを用いて前記データ文字ストリームを復元する
手段と、取り出されたデータ文字ストリングに応答し
て、拡張されたストリングを、前記メモリにストアする
ことによって、前記符号信号に応答してデータ文字スト
リングを前記メモリに供給する手段とを具え、取り出さ
れたデータ文字ストリングを、次に取り出されたデータ
文字ストリングの第１文字と連結させて、拡張されたス
トリングを形成し、拡張されたストリングを、それぞ
れ、対応する符号信号を用いて、前記メモリから検索可
能な形態で前記メモリにストアすることを特徴とする。
【００２５】ここで、前記圧縮された符号信号ストリー
ムは、前記データ文字ストリーム中の連続データ文字を
探索して、割り当てられた符号信号を持つデータ文字ス
トリングとの最長一致を決定して生成されたものに対応
し、決定された最長一致に対応する符号信号を用いて前
記圧縮されたストリームを生成し、および各決定された
最長一致を、データ文字ストリームにおいて次に続く文
字と連結させて、最長一致を決定するために用いるデー
タ文字ストリングを供給することを特徴とする。
【００２６】ここで、前記対応するデータ文字ストリン
グを取り出す手段は、受信した符号信号が最初にストア
された文字に対応するかを決定し、対応する場合は、当
該文字を、取り出したデータ文字ストリングとして用い
ることを特徴とする。
【００２７】ここで、複数の予め定めたストリングを最
初にストアし、および前記圧縮されたストリームを伸長
する前に、対応する符号信号を前記複数の予め定めたス
トリングに割り当てる手段を含むことを特徴とする。
【００２８】ここで、最初にストアされた予め定めたス
トリングは、前記データ文字ストリームの個別の文字に
対応するストリングを含むことを特徴とする。
【００２９】ここで、前記メモリは、受信した符号信号
に応答して対応するデータ文字を検索することを特徴と
する。
【００３０】ここで、符号信号に応答して前記メモリか
ら逆の順序でデータ文字ストリングを検索し、および検
索されたデータ文字を反転させて、検索に用いた符号信
号に対応するデータ文字ストリングを生成する手段を含
むことを特徴とする。
【００３１】また本発明の第３の形態は、入力されたデ
ータ文字ストリームを圧縮して圧縮された符号信号スト
リームにし、および前記符号信号を用いて、前記圧縮さ
れたストリームを伸長して前記データ文字ストリームを
復元する方法において、前記データ文字ストリームにお
けるデータ文字を探索し、データ文字ストリングに関連
する符号信号を有する第１メモリにストアされたデータ
文字ストリングとの最長一致を決定するステップと、最
長一致が決定されたデータ文字ストリングに対応する符
号信号を用いて、前記圧縮されたストリームを生成する
ステップと、拡張されたストリングを前記第１メモリに
ストアし、およびそれに関連した符号信号を割り当て
て、最長一致を決定するために用いるデータ文字ストリ
ングを供給するステップであって、最長一致を構成する
データ文字を、前記データ文字ストリーム中の次の文字
と連結して、拡張されたストリングを形成するステップ
とにより前記入力されたデータ文字ストリームを圧縮
し、および前記圧縮されたストリーム中の符号信号から
対応するデータ文字ストリングを取り出すステップであ
って、前記符号信号に対応するデータ文字ストリングを
ストアする第２メモリから、符号信号を用いて、データ
文字ストリングを検索するステップを含むステップと、
取り出されたデータ文字ストリングを用いて前記データ
文字ストリームを復元するステップと、前記取り出すス
テップに応答して、拡張されたストリングを第２メモリ
にストアすることによって、前記符号信号に対応して、
データ文字ストリングを前記第２メモリに供給するステ
ップとを具え、取り出されたデータ文字ストリングを、
次に取り出されたデータ文字ストリングの第１文字と連
結させて、拡張されたストリングを形成し、および拡張
されたストリングを当該拡張されたストリングに対応す
る受信された符号信号を用いて、前記第２メモリから検
索可能な形態で、前記第２メモリにストアすることを特
徴とする。
【００３２】ここで、最初に、複数の同様の予め定めた
ストリングを前記第１および第２メモリの各々にストア
し、符号信号を割り当てるステップを含むことを特徴と
する。
【００３３】ここで、最初にストアされた予め定めたス
トリングは、前記データ文字ストリーム中の個別の文字
に対応するストリングを含むことを特徴とする。
【００３４】また本発明の第４の形態は、データ文字ス
トリームを圧縮して圧縮された符号信号ストリームに
し、および前記符号信号を用いて、前記圧縮されたスト
リームを伸長して前記データ文字ストリームを復元する
装置において、前記入力されたデータ文字ストリームを
圧縮する装置と、前記圧縮されたストリームを伸長する
装置とを具備し、前記圧縮する装置は、前記データ文字
ストリームにおけるデータ文字を探索し、データ文字ス
トリングに関連する符号信号を有するデータ文字ストリ
ングとの最長一致を決定する手段と、前記データ文字ス
トリングをストアする第１メモリと、最長一致が決定さ
れたデータ文字ストリングに対応する符号信号を用い
て、前記圧縮されたストリームを生成する手段と、拡張
されたストリングを前記第１メモリにストアし、および
それに関連した符号信号を割り当てて、最長一致を決定
するために用いるデータ文字ストリングを供給する手段
であって、最長一致を構成するデータ文字を、前記デー
タ文字ストリーム中の次の文字と連結して、拡張された
ストリングを形成する手段とを具え、前記伸長する装置
は、前記符号信号に対応するデータ文字ストリングをス
トアする第２メモリと、前記圧縮されたストリーム中の
符号信号から対応するデータ文字ストリングを取り出す
手段であって、前記第２メモリから、符号信号を用い
て、データ文字ストリングを検索する手段と、取り出さ
れたデータ文字ストリングを用いて前記データ文字スト
リームを復元する手段と、取り出されたストリングに応
答して、拡張されたストリングを前記第２メモリにスト
アすることによって、前記符号信号に対応して、デタ文
字ストリングを前記第２メモリに供給する手段とを具
え、取り出されたデータ文字ストリングを、次に取り出
されたデータ文字ストリングの第１文字と連結させて、
拡張されたストリングを形成し、および拡張されたスト
リングを、当該拡張されたストリングに対応する受信さ
れた符号信号を用いて、前記第２メモリから検索可能な
形態で、前記第２メモリにストアすることを特徴とす
る。
【００３５】ここで、最初に、複数の同様の予め定めた
ストリングを前記第１および第２メモリの各々にストア
し、符号信号を割り当てる手段を含むことを特徴とす
る。
【００３６】ここで、最初にストアされた予め定めたス
トリングは、前記データ文字ストリーム中の個別の文字
に対応するストリングを含むことを特徴とする。
【００３７】
【実施例】本発明はデジタルデータ文字信号のストリー
ムまたは列を圧縮して、圧縮されたディジタル符号信号
の対応するストリームを与えるデータ圧縮装置を備えて
いる。例えば、圧縮される予定のデータは、英語の原文
資料、格納されたコンピュータ記録などを含んでいても
よい。今日のデータ処理装置および通信装置において
は、圧縮を行われるはずのアフファベットの文字は、処
理されてＡＳＣＩＩフォーマットのような都合のよいコ
ードで２進数字のバイトとして伝達されることがわかっ
ている。例えば、入力文字を８ビット・バイトの形式で
２５６文字の文字体系全体を受けることができる。圧縮
装置からの圧縮符号信号は、例えば、記録保管の目的の
ために電子記憶ファイルに格納されるか、または伸長を
行う遠隔の場所に伝送されてもよい。このほかに、ディ
スク記憶装置のような電子記憶ファイルが入力電子回路
に圧縮装置を備え、出力電子回路に伸長器を備えること
ができ、それによってファイルに入るすべてのデータを
記憶するために圧縮して、ファイルから検索されたすべ
てのデータを利用機器に伝送する前に伸長する。前述の
従来の圧縮装置および伸長装置は、圧縮および伸長のそ
のような用途に適合させる性能または適応性を与えな
い。本発明に従って実施された高性能適応装置をそのよ
うに用いることができる。
【００３８】多数の設計オプションが被圧縮データおよ
び装置の所望の特性に従う種々の組合せで本発明の実施
例に用いることができる。発明の三つの実施例を以下に
説明する。一つの実施例は、最高性能を与えるオプショ
ンを組合せており、第２の実施例は、最高圧縮を与える
オプションを組合せており、第３の実施例は、最高性能
実施例のプログラムされたコンピュータの例を提供す
る。
【００３９】本発明の伸長装置に入力される圧縮データ
信号を生成する圧縮装置は、データ文字の入力ストリー
ムをストリングまたはセグメントにパースして、各スト
リングを識別する符号信号を伝送する。圧縮装置が初め
て遭遇したデータ文字以外は、各パースされたストリン
グは、前に認識されたストリングに対する最長一致を含
んでいる。圧縮装置は、認識されたストリングに対応す
る符号信号を伝送する。１ストリングの文字が入力スト
リームからパースされると、パースされたストリング
は、入力ストリームにおいて次に発生する文字によって
拡張され、あとで符号化に利用されるために圧縮装置に
おいて符号化され、そこに記憶される拡張ストリングを
形成する。従って認識されている文字シーケンスは、１
ブロックのデータを圧縮する過程で統計的情報を集める
とき、平均長さがたえず大きくなっている。拡張文字
は、次のパーシング繰返しにおける最初の文字として用
いられる。パーシングは、データを１回通すだけで達成
され、初めの文字から出発して、１回の１文字を分離す
る。従って、単一文字のストリング以外は、各ストリン
グは、前に記憶されたストリングと一致する接頭部スト
リングと拡張文字として記憶される。そのストリング
は、そのような各ストリングを接頭部の符号信号表現と
拡張文字の実際の表現または暗示表現を一緒にして記録
するのが都合よい。パーシングは、データ・ストリーム
の各文字間に仮想コンマを挿入し、それによってパース
されたストリングまたはセグメントを区切るものとして
概念化できる。従って、本発明においては、一致を得る
ための未処理のデータストリームの探索は、先に観察さ
れたストリングとの最長一致を見出すために一つのコン
マから次に続くコンマを一文字越えたところまでを探索
することを含む。
【００４０】図１を参照すると、データ文字のストリー
ムの一部分の略図が示されており、そこではＸがアルフ
ァベットの任意の文字を表している。コンマは、パーシ
ングを表すためにのみデータストリーム中に示されてい
る。このデータストリームのストリング１が仮想コンマ
２および３によってパースされている。ストリング１は
前のストリング１´に一致し、ストリング１´はコンマ
２に続く入力データストリームに一致するコンマ２に先
行した最長拡張ストリングである。ストリング１´は、
前に符号化されたものであるから、その符号は、ストリ
ング１に遭遇したとき圧縮装置によって伝送される。次
いで圧縮装置は、接頭部ストリング１と拡張文字５を含
む拡張ストリング４を符号化して記憶する。拡張文字
は、それがどんな文字であるかに関係なく、接頭部１に
続くデータストリームの中の次の文字である。すなわ
ち、拡張文字５は、前に、データストリームの中で現れ
た文字であってもよいし、またはそれは初めて遭遇する
アルファベットの１文字であってもよい。
【００４１】圧縮装置は、もう一度最長一致が達成され
るまで拡張文字５で始まる次のパーシングの繰返しを仮
想コンマ３のところで開始する。このようにして、前に
拡張されたストリング６´にマッチするストリング６が
パースされる。前の繰返しにおけると同じようにまた、
ストリング６´に対する符号信号は、伝送され、ストリ
ング６は後続の文字によって拡張され、拡張されたスト
リングは、符号化されて記憶される。続くパーシング繰
返しにおいては、符号化されて記憶されたストリング４
にマッチするストリング７がパースされる。このパーシ
ング繰返しで伝送された符号信号は、拡張ストリング４
に割当てられたものである。
【００４２】上述のように、圧縮装置によって与えられ
た符号信号を受けた伸長装置は、符号化接頭部ストリン
グと拡張文字の形でデータを記憶する。従って、伸長装
置は、一つの受信符号信号と一つの拡張文字を含むエン
トリーを記憶装置内に構成する。例えば、続けて図１を
参照すると、伸長装置がストリング１に関連した符号信
号を受けると、その伸長装置が前にストリング１′を構
成して記憶しているので、そのストリングを構成する文
字が、以下に詳細に説明する方法で、再構成される。次
に続く繰返しにおいて、伸長装置がストリング６に関連
した符号信号を受けると、そのストリングを構成する文
字が検索される。この時点で、伸長装置は、ストリング
１からの符号信号を受け取って拡張文字５を検索してい
るので、以下に詳細に説明する方法でストリング４を構
成して記憶できる。
【００４３】本発明において、入力バイトの各シーケン
スが実施例次第で固定長または可変長のものであっても
よい符号信号に圧縮される。上述のように、各入力バイ
ト列は、各符号識別子を割当てられ、一つの列が入力デ
ータ・ストリームの中で再び出てくるときはいつも、同
じ識別子が再び伝送される。各１バイト列が各符号を割
当てられ、一つの列が再び出てくるときはいつも、１バ
イトだけ拡張され、新しい符号が拡張されたシーケンス
に割当てられる。概念的には、圧縮装置は、各データブ
ロックを格納されたセット内のゼロストリングのみから
開始する。圧縮装置は、新しい文字が出てくるたびにそ
のセットに１文字のストリングを入れ、次にこれらの記
憶された１文字ストリングをさらに長いストリングを形
成するのに用いる。各ストリングがそのセットに加えら
れると、それは、一つの符号信号を割当てられる。入力
からの一つの文字ストリングがセット内で見出される度
に、次の入力文字がそのストリングに追加され、拡張さ
れたストリングがそのセットの中にあるかどうかを決め
るためにそのセットが探索される。拡張されたストリン
グが既に存在しなければ、そのストリングがセットに入
れられる。随意選択的に、そのストリングセットをすべ
ての単一文字ストリングを含むように初期設定できる。
これは、より高い性能の装置として実現できるようにに
することもあるが、ある程度の圧縮効率を失うことがあ
る。圧縮装置からの出力符号信号は、同一文字列が以前
に起こったことを示しているものとして考えることがで
きる。
【００４４】前記米国特許第４，４６４，６５０号のデ
ータ圧縮および伸長装置において、拡張文字が各認識さ
れた列に追加されて拡張された列が符号化された。拡張
列の符号化表現は、それの圧縮符号として圧縮装置によ
って伝送された。その代りに、本発明の圧縮装置は、拡
張列を記憶して、認識された列に対する符号を伝送す
る。認識された列は、拡張列の接頭部である。記憶され
た拡張列は、次にあとで符号化するために用いられる。
前記米国特許第４，４６４，６５０号の方法をこのよう
に変更すると、前記米国特許第４，４６４，６５０号に
おいて用いた時間のかかる、やっかいな数学的操作およ
び乗算・除算装置のような付随のハードウェアをなくす
ことによってデータ圧縮および伸長装置を著しく簡単に
することができる。この変更は、装置の性能を著しく高
めると同様にまた、普通に遭遇するデータの場合の圧縮
効率を増加させる。これは、前記米国特許第４，４６
４，６５０号の装置では、圧縮された符号信号の一部分
として伝送される拡張文字が等しく起こりそうな文字体
系のすべての記号に見合った多数のビットを含むからで
ある。本発明では、拡張文字は、次の圧縮ストリング符
号の一部分として伝送されるので、文字の各ストリング
について行われた圧縮に一致して必要とするビットの数
が少なくなる。
【００４５】本発明は、限定探索長の計算されたアドレ
ス・ハッシング装置を用いて各ストリングをストリング
・テーブルに入れ、そのストリング・テーブル内で各ス
トリングを探索する。ハッシング関数は、前の符号信号
と拡張文字とからなるハッシュ・キーを用いてＮ個のハ
ッシュ・テーブル・アドレスの組を与える（ここでＮは
普通１ないし４である）Ｎ個のＲＡＭ記憶場所は、逐次
に探索され、その項目がＮ個の記憶場所になければ、そ
れはそのテーブル内にないと考えられる。圧縮のとき
に、テーブルに挿入されるべき新しいキーをＮ個の割当
て場所に受入れできなければ、それはテーブルから除外
される。この限定探索ハッシング法は、圧縮効率をわず
かに下げるが、装置として実現するのを非常に簡単にす
る。Ｎ個のハッシュ・アドレスが反復したＲＡＭの中で
並列に探索される別の実施例を用いてもよい。
【００４６】本発明は、固定長または可変長の圧縮され
た符号信号を用いて装置として具体化することができ
る。固定長符号信号の実施例は、圧縮効率においてわず
かの損失を伴いながら装置として実現する場合の簡単化
をもたらす。固定長符号実施例は、ＲＡＭのスペース必
要度と可変符号長による装置としての実現に必要な符号
シフティング機構の複雑さを小さくする傾向がある。し
かし固定長符号による装置の実現は非常に高い性能の装
置の実現を行うときに望ましい。
【００４７】一般には、本発明は、入力文字信号の可変
ストリングを出力符号記号信号に写像することによって
圧縮を行う。圧縮装置は、ストリング・テーブル（ＲＡ
Ｍ）の中に圧縮装置が認識するストリングのリストを記
憶し、各ストリングに対しては対応する出力符号信号を
記憶する。そのように記憶されたストリングの組は、ど
んな一連の入力文字も記憶されるストリングにパースで
き、従って、出力符号に写像できるように構成される。
パーシングは、どの繰返しにおいてもストリング・テー
ブルの中に最長ストリングに一致するすべての連続する
入力文字を使いきり、対応する出力符号を伝送すること
によって達成される。最長一致は、次の入力文字によっ
て拡張され、ストリング・テーブルに記憶され、そして
対応する符号を割当てられる。
【００４８】従って、ストリング・テーブル内のストリ
ングの組を合成することは、現在のデータブロックの統
計に適応し、かつその統計の一つの表現法である。明確
にいえば、そのストリングの組に追加される各ストリン
グは、その組に既にある一つのストリングを１文字で拡
張したものである。一つのストリングがそのセットに加
えられるのは、それが実際に入力データにおいて観測さ
れたのちにおいてである。従って、一つの長いストリン
グがそのセット内に現れる可能性のあるのは、それが何
度も出てきたので頻繁に再び現れると期待できる場合だ
けである。このストリングセットは、できればランダム
アクセス記憶装置（ＲＡＭ）にテーブルとして記憶され
るのがよい。各ストリングは、連結トリー構造と考えて
もよいものに記憶される。各ストリングは、少なくとも
暗黙的にすなわち間接的に、その符号記号、そのストリ
ングの最後の文字および最後の文字以外のすべてのスト
リング文字を含むストリング接頭部の符号記号で記憶さ
れる。各文字が個別に得られ、かつ各接頭部符号が逐次
に呼び出されるので、伸長装置は、一つのストリングを
複合するときに多重ＲＡＭアクセスを用いる。
【００４９】各データ信号は、入力文字列に対する最長
一致を探すのを容易にするようなやり方でストリング・
テーブル内に記憶される。各入力文字が読まれると、そ
れが既に認識された一つのストリング（新しい列の始め
にゼロストリングで始まったもの）に付け加えられて、
その新しいストリングは、それがそのテーブルの中にあ
るかどうかを決めるために検査される。新しいストリン
グがそのテーブルの中にあれば、その符号が検索され
て、その処理が新しい文字と新しい符号とで繰返され
る。それらのストリングをそのように呼び出すために、
それらのストリングは、“接頭部符号、拡張文字”の組
（タブル）によって識別されるのが都合よい。限定探索
ハッシング装置がストリング・テーブルをくまなく探索
するのに用いられる。
【００５０】本発明を実施する際に用いることのできる
ハッシング装置は、一つの符号、文字組合わせに対して
一連の記憶アドレスを発生する関数 ハッシュ（符号、文字）→アドレス１，アドレス２・・・ を含む。テーブルに一つのストリングを挿入すると、発
生したＲＡＭアドレスが空サイトを発見するまで逐次に
呼出され、項目がその点に挿入される。一つの項目を検
索するとき、同じアドレス列がその項目が発見されるか
または空サイトが発見されるまで呼出され、空サイトが
発見された場合にその項目はテーブルの中に存在しない
と定義される。各占有されたサイトにおいては、そのス
トリングのための識別用符号、文字の組は、そのサイト
を占有するものが所望の項目であるかどうかを決めるた
めに比較されてもよい。あとで説明する理由によって、
識別用符号を比較することは、実際には、この実施例で
必要なだけである。
【００５１】本発明で用いられたハッシュ関数において
は、取り出されて用いられたアドレスの数は、小さな一
定値Ｎ（Ｎは普通１ないし４である）に限定される。一
つの項目をＮ回の呼出しでストリング・テーブルに挿入
できなければ、その項目は用いられない。テーブルから
検索される予定の一つの項目がＮ回の呼出しの中で所在
をつきとめられなければ、それはテーブル内にないと定
義される。この限定探索の特徴は、圧縮効率の小さな損
失をもたらすが、性能を著しく増加させる。本発明はＢ
ビット・バイトの文字体系について圧縮を行うとして説
明する。本発明を実施する際に用いられるハッシュ関数
は、任意の一つの符号に関連したアドレスの組すなわち
２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 および符号値のいずれにも等し
くなければ、この処理は、この新アドレス値に対するこ
の「次のハッシュ状態」に再び入ることによってＮ回ま
で繰返す。ハッシュ関数回路２３からのリード２５の上
の信号によって示されているように、Ｎ個の記憶場所が
試みられたとき、このストリングは終りにされて「スト
リング終了状態」に入る。
【０１０２】〔５〕．新ストリング状態． ストリング
・テーブル内の空記憶場所に遭遇したことは、探索され
た拡張ストリングをテーブルの中に発見しなかったこと
およびそのストリングをテーブルの中に入れる必要のあ
ることを示す。これは、拡張ストリングの接頭部符号番
号をＲＡＭ２９に書込むことにより達成されるので、割
当てられたアドレスを拡張ストリングのための符号値と
してとっておく。従って、ＲＡＭアドレス・レジスタ２
８の中のアドレスは、その前の値に維持され、ＲＡＭ２
９は、符号番号レジスタ１９の内容をバス３０を経てア
ドレス指定された記憶場所に書込むように制御される。
次に「ストリング終了状態」に入る。
【０１０３】〔６〕．ストリング終了状態． この状態
に入るとき、拡張ストリングがストリング・テーブルに
ないので、現在あるストリング符号を出力として伝送
し、新しいストリングを開始すべきであると判定され
た。従って、符号番号レジスタ１９からの出力符号信号
を出力バス１１に伝送して、新圧縮符号信号がバス１１
にあることを外部装置に知らせる「符号ストローブ信
号」をリード１６を経て送る。このインターフェイスの
正確な形は、圧縮データ信号を受ける外部装置の特有の
要求事項に従って変わる。新ストリングは、文字レジス
タ１７の中に既にある文字を用いて開始され、その文字
は、それをバス１８を介して符号番号レジスタ１９の下
位Ｂビットにゲートし、かつレジスタ１９の高位Ｃ−Ｂ
ビット位置にあるビット位置にゼロをおくことによって
あらかじめ割当てられた単一文字のストリングに翻訳さ
れている。その新ストリングを構成するために「次の文
字状態」に再び入る。
【０１０４】次に図３を参照すると、図２の圧縮装置か
らの圧縮符号信号に対応するデータ文字列を回復する本
発明の伸長装置の実施例が示されている。図３の伸長装
置は、その出力を外部ランダム・アクセス・バッファに
直接におくことのできるように回路を構成され、その構
成は、出力文字ストリングの急速な反転をできるように
する。この伸長装置の実施例は、出力記憶場所のアドレ
スの明示管理を用いている。ストリング・テーブル内の
記述項には接頭部ストリング内の文字の数を示す「レベ
ル」値がある。このレベル値を用いて出力バッファ内の
各文字の適当な位置決めを達成する。伸長装置からの伸
長文字ストリングを受ける外部装置は、そのデータを格
納するのにランダム・アクセス記憶装置を用いると仮定
されている。外部ランダム・アクセス・バッファを用い
るとき伸長装置は、各出力データ文字にアドレスを与
え、そのアドレスが出力ストリング内のその文字の記憶
場所を限定する。最初の記憶場所は、ゼロのアドレスに
対応する。外部装置はその特定の記憶アドレス指定の要
求事項にマッチするように記憶場所のアドレスを操作で
きる。
【０１０５】図３の伸長装置は、出力文字をそれらが図
２の圧縮装置によって受けられるのと違う順序で与える
が、各文字に付随して記憶場所の値を与えることによっ
て、最後のアセンブルされたデータストリームは、正し
い順序になる。ランダム・アクセス記憶装置を外部装置
に用いない場合、図５に関して以下に説明するようなス
トリング反転へのスタック機構アプローチを用いること
ができる。
【０１０６】図３の伸長装置は、バス５０の上の圧縮符
号信号を受けて、バス５１の上に回復したデータ文字信
号の対応するストリングを与える。圧縮符号信号は、外
部装置からバス５０の上に与えられる。この外部装置は
また、圧縮信号がその外部装置から入手できて、バス５
０に加えられるときは常に、ライン５２にデータ使用可
能信号を与える。ライン５２の上のデータ使用可能信号
は、伸長装置の制御装置５３に加えられる。制御装置５
３は図３の伸長装置のすべてのブロックにリード５４を
経て制御信号を与える。伸長装置の制御装置５３は、図
３の伸長装置をその制御状態を介して、以下に詳細に説
明する方法で順序づける。制御装置５３はまた、追加の
入力符号信号を要求する入力データ・ストローブ信号を
ライン５５を通して外部装置に与える。一つの出力文字
がバス５１の上で使用可能なとき、制御装置５３はリー
ド５６の上の外部装置に出力データ・ストローブ信号を
与える。
【０１０７】バス５０の上の圧縮符号信号は、Ｃビット
符号レジスタ５７に入れられる。単一文字のストリング
を表す符号と複数文字のストリングを表す符号との区別
をするために、符号レジスタ５７の出力を比較器５８で
２B の一定値信号と比較する。従って、比較器５８は、
レジスタ５７の中の符号信号が２B より大きいか小さい
かを示す信号を制御装置５３にリード５９を経て送る。
レジスタ５７の中の符号値が２B より小さく、従って単
一文字のストリングを表すとき、レジスタ５７の低位ビ
ットがバス６０を経てＢビットの最終文字レジスタ６１
に転送される。上述のように、単一文字のストリングに
対する符号値は、その文字と同じであるから、最終文字
レジスタ６１へバス６０を経て転送された単一文字のス
トリングは直接バス５１に出力される。
【０１０８】レジスタ５７の中の圧縮符号信号が比較器
５８によって決められるように２Bより大きいとき、レ
ジスタ５７の中の符号値は、ＲＡＭアドレス・レジスタ
６２へバス６３を介して転送される。圧縮符号信号の伸
長の間のある幾つかの時点で、レジスタ５７の中の圧縮
符号は、その値を後の処理のために保存するためＣビッ
ト符号レジスタ６４へバス６５を介して転送される。後
で説明するある幾つかの条件ではレジスタ６４の中の符
号値をＲＡＭアドレス・レジスタ６２へバス６６を介し
て転送できる。
【０１０９】適当なアドレスを伸長装置の中の文字スト
リングの記憶域に与えるために、最終文字レジスタ６１
に格納された文字信号および符号レジスタ６４に格納さ
れた符号信号がバス６７および６８をそれぞれ介してハ
ッシュ関数回路６９へ加えられる。ハッシュ関数回路６
９は、図２に関して前に述べたハッシュ関数回路２３と
同一である。ハッシュ関数回路６９は、バス６８の上の
Ｃビット符号信号をバス６７の上のＢビット文字信号と
結合してＮ個のＣビットアドレスをバス７０を経てＲＡ
Ｍアドレス・レジスタ６２へ順次に与える。ハッシュ関
数回路６９は、制御装置５３へリード７１を介してバス
７０の上に与えられたハッシュ・アドレスがその列の中
のＮ番目のアドレスであるかどうかを知らせる。
【０１１０】ハッシュ関数回路６９はまた「新ハッシ
ュ」指令および「次のハッシュ」指令を制御装置５３か
ら受ける。制御装置５３は「新ハッシュ」指令に応じて
Ｎ個のハッシュ・アドレスの中の第１のものを与え、次
に「次のハッシュ」指令の相次いで起るのに応じて、相
次ぐハッシュ・アドレスを与えるようにハッシュ関数回
路６９に指令する。前に述べたように、ハッシュ関数回
路６９がＮ番目のハッシュ・アドレスを与えたとき、一
つの信号が制御回路５３へリード７１を介して戻され
る。
【０１１１】ＲＡＭアドレス・レジスタ６２からのＲＡ
Ｍアドレスは、バス７３を介して比較器７２および最終
文字レジスタ６１の両方に加えられる。比較器７２はま
た２B に等しい一定値信号を受ける。比較器７２は、バ
ス７３の上のＲＡＭアドレスを値２B と比較して、バス
７３の上のアドレスが２B より大きいか小さいかを示す
信号を制御装置５３へリード７４を介して与える。それ
が２B より小さいとき、ＲＡＭアドレス・レジスタ６２
の中の値は、文字ストリングの中の最初の文字を後述の
ようにして回復するために最終文字レジスタ６１に加え
られる。
【０１１２】ＲＡＭアドレス・レジスタ６２の中にロー
ドされたアドレスが伸長装置ストリング・テーブルを記
憶するのに用いられるＲＡＭ７５を呼出す。ＲＡＭ７５
には、各々がＣ＋Ｂ＋Ｌビットの幅である２C の記憶場
所がある。各ストリングは、それのＣビット接頭部符
号、それのＢビット拡張文字およびＬビットレベル値を
記憶することによってＲＡＭに記憶される。レベル欄の
値は、そのストリングの接頭部内のビットの数に等し
い。各ストリングは、そのストリングに割当てられた符
号によってアドレス指定された記憶場所においてＲＡＭ
７５に記憶される。そのストリングに割当てられた符号
は、接頭部符号を後述のようにしてストリング拡張文字
でハッシュすることによって引出される。
【０１１３】ＲＡＭ７５は、ＲＡＭ７５の「読出し」、
「書込み」機能を制御するために「読出し」指令と「書
込み」指令を制御装置５３から受ける。後で説明するよ
うにして初期設定するために、ＲＡＭ７５は、一定値信
号２B 、ゼロおよびゼロをそれぞれＲＡＭアドレス・レ
ジスタ６２によってアドレス指定されたＲＡＭ記憶場所
の接頭部符号、文字およびレベルの各欄に書込むために
受ける。これらの値は制御装置５３の制御のもとで加え
られて、「書込み」指令の加わったときに入れられる。
ＲＡＭ７５はまた制御装置５３によって制御されて、バ
ス７６を経て符号レジスタ６４からくる符号値、バス７
７を経て最終文字レジスタ６１からくる文字値およびバ
ス７９を経てレベル・レジスタ７８からくるレベル値を
ＲＡＭアドレス・レジスタ６２によってアドレス指定さ
れたＲＡＭ記憶場所の接頭部、文字およびレベルの各欄
にそれぞれ入れるために選択的に受ける。これらの値
は、制御装置５３からの「書込み」指令に応じてそれぞ
れの欄に書き込まれる。
【０１１４】制御装置５３はまた、「読出し」指令に応
じてＲＡＭ７５を制御して、ＲＡＭアドレス・レジスタ
６２によってアドレス指定されたＲＡＭ記憶場所の接頭
部符号欄に格納された接頭部符号値をバス８０に与え
る。このバス８０の上の符号値は、検出器８１のほかに
ＲＡＭアドレス・レジスタ６２にも加えられる。検出器
８１は、ＲＡＭ出力のバス８０上の接頭部符号が２B に
等しいかどうかを決定して、それ相応に信号をリード８
２を介して制御装置５３に与える。
【０１１５】制御装置５３はまた、文字値を文字欄から
バス８３を経て最終文字レジスタ６１へ選択的に与える
ようにＲＡＭ７５を制御する。文字値は、「読出し」指
令に応じてＲＡＭアドレス・レジスタ６２によってアド
レス指定されたＲＡＭ記憶場所の文字欄からバス８３の
上に与えられる。同様にして、制御装置５３は、レベル
値をバス８４を経てレベル・レジスタ８５またはアドレ
ス加算器８６のいずれかに与えるようにＲＡＭ７５を制
御する。レベル値は、ＲＡＭアドレス・レジスタ６２に
よって呼出されたＲＡＭ記憶場所のレベル欄からバス８
４へ加えられる。バス８４上のレベル値のレベル・レジ
スタ８５およびアドレス加算器８６への経路指定は、伸
長装置の現存の状態に従って制御装置５３によって制御
される。
【０１１６】図３の伸長装置は外部ランダム・アクセス
記憶装置内で適当に位置が合うようにするために出力文
字信号にアドレスを割当てる装置を含んでいる。従っ
て、アドレス加算器８６はそのような記憶場所アドレス
を外部装置にバス８７を通して与える。アドレス加算器
８６は、アウトポインタ・レジスタ８８からの入力、Ｒ
ＡＭ７５からのバス８４を通してのレベル値およびレベ
ル・レジスタ７８からバス８９を通してのレベル値を受
ける。アドレス加算器８６はまた、バス９０を通してゼ
ロ値信号を受ける。制御装置５３は、アドレス加算器８
６を制御して、バス８４の上のレベル値、バス８９の上
のレベル値またはバス９０の上のレベル値のいずれかを
伸長装置の現存の状態およびその状態の間に存在する論
理的諸条件に従うアウトポインタ・レジスタ８８の中の
値を後で説明するようにして加える。加算の結果は、記
憶場所アドレスをバス８７の上に与える。
【０１１７】アドレス加算器８６の出力はまた、アウト
ポインタ・レジスタ８８への入力としても加えられる。
制御装置５３は、アウトポインタ・レジスタ８８を制御
して、現存のアウトポインタの値を加算器８６における
加算の結果で置き換えるか、または単にバス８７の上に
記憶場所のアドレスを発生するためのベース・アドレス
を加算器８６に与えるだけにする。制御装置５３はま
た、レベル・レジスタ７８および８５を制御して、レベ
ル・レジスタ８５からレベル・レジスタ７８へレベル値
を転送して、その転送経路にある加算器９１を介してそ
の値を１だけ大きくする。なお、制御装置５３は、レベ
ル・レジスタ７８および８５を制御して、レベル・レジ
スタ７８の内容をレベル・レジスタ８５へバス９２を介
して転送する。この装置はまた、レベル・レジスタ８５
およびアウトポインタ・レジスタ８８への入力を備え、
あとで説明する諸条件のもとでこれらのレジスタをゼロ
にする。
【０１１８】図３の伸長装置はまた、Ｃビット信号ＲＡ
Ｍアドレス・レジスタ６２へのバス９４を経て与える初
期設定計数器９３を備えている。計数器９３をそれに加
わるゼロの値にされた信号を介してゼロにセットでき
る。制御装置５３は、「計数」指令を介して計数器９３
を制御して、「計数」指令の加わるごとに計数器の内容
に１を加える。計数器９３は、それが計数値２C に達し
たとき、制御装置５３にリード９５の上のキャリアウト
またはオーバフロー信号を介して合図する。初期設定計
数器９３は、ＲＡＭ７５を初期設定するのに用いられ、
それの記憶場所のすべてを逐次に呼出して一定値２B 、
ゼロおよびゼロを接頭部符号、文字およびレベルの各欄
にそれぞれ書込むことによって空にする。
【０１１９】図３の伸長装置の基本動作は、次のように
要約される。
【０１２０】１．各データブロックごとに、ＲＡＭを空
に初期設定する。
【０１２１】２．各入力符号ごとに、符号を符号番号レ
ジスタに読出す。前の符号からのあるデータをストリン
グ・テーブル更新のために保存する。
【０１２２】３．符号レジスタ→ＲＡＭアドレス 接頭部符号、拡張文字、ストリング長さを作るＲＡＭを
読出す。
【０１２３】接頭部符号→２B なら；文字をストリング
長さによって決まった記憶場所において出力； 接頭部符号→符号番号レジスタ；ステップ３を繰返す、 接頭部符号＜２B なら；符号値を文字として出力；ステ
ップ４へ行く。
【０１２４】４．ストリング・テブルの終りにおいて文
字ストリングを更新： 前に受けた符号および最終出力文字をハッシュ（前の符
号、最終文字）によって作られた列から最初の空の記憶
場所に書込む；ステップ２へ行く。
【０１２５】図３を続けて参照すると、以下のものが図
３の伸長装置の状態機械記述語である。
【０１２６】状態０：各データブロックの始めにおける
「待ち状態」 初期設定計数器＝ゼロ アウトポインタ＝ゼロ データ使用可能信号を待つ；状態１へ行く。
【０１２７】状態１：「ＲＡＭを初期設定」 初期設定計数器→ＲＡＭアドレス２B 、ゼロ、ゼロ→Ｒ
ＡＭ入力 ＲＡＭを書込む 初期設定計数器へ＋１を加える 初期設定計数器＜２C ならば、状態１を繰返す； そうでなければ状態２へ行く。
【０１２８】状態２：「最初の入力符号を処理する」 入力符号記号→符号レジスタ１ 入力データ・ストローブ 符号値（下位Ｂビット）→最終文字レジスタ 記憶場所アドレス＝アウトポインタ；出力データ・スト
ローブ レベル・レジスタ１＝ゼロ 状態３へ行く。
【０１２９】状態３：「次の入力符号」 符号レジスタ１→符号レジスタ２ （レベル・レジスタ１）＋１→レベル・レジスタ２ （レベル・レジスタ２）＋（アウトポインタ）→アウト
ポインタ 新しい入力が使用可能でなければ；状態０へ行く。
【０１３０】入力符号を読出す→符号レジスタ１ 入力データ・ストローブ 符号レジスタ１≧２B なら： レベル・レジスタ１＝０ 符号レジスタ１→ＲＡＭアドレス 状態４へ行く。
【０１３１】符号レジスタ１＜２B ならば： 符号値（符号レジスタ１の下位Ｂビット）→最終文字レ
ジスタ 記憶位置アドレス＝アウトポインタ：出力データ・スト
ローブ 状態５へ行く。
【０１３２】状態４：「最初の文字サイクル」 ＲＡＭを読出す 符号（ＲＡＭ）≠２B ならば［正常の場合］： レベル（ＲＡＭ）→レベル・レジスタ１ 符号（ＲＡＭ）→ＲＡＭアドレス 文字（ＲＡＭ）→最終文字レジスタ 記憶場所アドレス＝アウトポインタ＋レベル（ＲＡ
Ｍ）； 出力データ・ストローブ 符号（ＲＡＭ）＝２B ならば［異常の場合］： レベル・レジスタ２→レベル・レジスタ１ 符号レジスタ２→ＲＡＭアドレス 記憶場所アドレス＝アウトポインタ＋レベル・レジスタ
２；出力データ・ストローブ 状態５へ行く。
【０１３３】状態５：「後の文字サイクル」 ＲＡＭアドレス≧２B ならば：ＲＡＭを読出す 符号（ＲＡＭ）→ＲＡＭアドレス 文字（ＲＡＭ）→最終文字レジスタ 記憶場所アドレス＝アウトポインタ＋レベル（ＲＡ
Ｍ）；出力データ・ストローブ 状態５へ行く。
【０１３４】ＲＡＭアドレス＜２B ならば： ＲＡＭアドレス（下位Ｂビット）→最終文字レジスタ 記憶場所アドレス＝アウトポインタ；出力データ・スト
ローブ 状態６へ行く。
【０１３５】状態６：「ストリング・テーブル更新」 ハッシュ（符号レジスタ２、最終文字レジスタ）→ＲＡ
Ｍアドレス ＲＡＭを読出す 符号（ＲＡＭ）＝２B およびＲＡＭアドレス＞２B なら
ば： 状態７へ行く。
【０１３６】その他の場合：新ハッシュ値で状態６を繰
返す。
【０１３７】これが最終ハッシュならば、状態３へ行
く。
【０１３８】状態７：「書込みサイクル」 ＲＡＭアドレスを変えないで 符号レジスタ２→符号（ＲＡＭ） 最終文字レジスタ→文字（ＲＡＭ） レベル・レジスタ２→レベル（ＲＡＭ） ＲＡＭを書込む。
【０１３９】状態３へ行く。
【０１４０】上に与えられた状態機械記述語に関する図
３の伸長装置の動作のさらに詳細な説明を次に行う。
【０１４１】［０］ 待ち状態． １ブロックの圧縮入
力符号信号を待っている間、図３の伸長装置は、この状
態にある。「待ち状態」の間、制御装置５３は、初期設
定計数器９３をゼロにリセットする。制御装置５３はま
た、出力文字信号の外部出力記憶装置への相次ぐ転送が
最低の使用可能なアドレスで始まるようにアウトポイン
タ・レジスタ８８をゼロにリセットする。入力符号を供
給する外部信号源からのリード５２の上のデータ使用可
能信号は、入力符号が利用できるときを指示するのに用
いられる。入力符号が使用可能になると、リード５２の
上のデータ使用可能信号は、制御装置５３に「初期設定
状態」に入るように合図する。
【０１４２】［１］ 初期設定状態． ランダム・アク
セス記憶装置ＲＡＭ７５の内容は、空であるように初期
設定される。ＲＡＭ７５はその２C の記憶場所の各々に
三つの種類の異なったデータ欄を含み、すなわちＣビッ
トの接頭部符号値、Ｂビットの拡張文字、およびＬビッ
トのレベル値を含む。各記憶場所は、文字のストリング
に対応し、そこでは記憶場所のアドレスが、そのストリ
ングの符号値であって、損記憶場所の内容は、その接頭
部ストリングおよび拡張文字によってそのストリングの
組成を与える。レベル欄は、接頭部ストリング内の文字
の数を与え、出力列の中の適当な位置にある出力文字を
位置指定するときに用いられる。Ｌビットは、どのスト
リング長さも２L の文字を超えない（ここでＬはＣ以下
である）という仮定のもとに、レベル値に与えられる。
ＲＡＭ７５のすべての記憶場所は、空記号２B をそれの
接頭部符号欄に入ることによって初期設定される。文字
値欄およびレベル値欄は、これらの欄が初期設定を必要
とせず、簡易化を望む場合、現存の値で残すことができ
るけれども、ゼロに初期設定される。最初の２B ＋１個
所の記憶場所は、これらの記憶場所が伸長装置の動作の
間別のやり方で呼出されることは決してないが、実現の
便宜上初期設定される。
【０１４３】初期設定は、Ｃビット初期設定計数器９３
の中の値をバス９４を経てＲＡＭアドレス・レジスタ６
２へゲートすることによってメモリ・サイクルを繰返し
て達成される。ＲＡＭの入力は、一定値２B およびゼロ
であるように選ばれる。ＲＡＭ７５は、選択された入力
データをＲＡＭアドレス・レジスタ６２によって指定さ
れた記憶場所に書込むように制御される。初期設定計数
器９３は、その現在の内容に１を加えることによって数
え上げるように指令される。この一連の事象は、各記憶
場所ごとに１回あて合計２C 回繰返される。２C のその
ような計数ののちに、初期設定計数器９３は、２C の計
数が発生したことを合図するオーバフローまたはキャリ
アウト信号を制御装置５３にリード９５に介して与え
る。これによって図３の伸長装置が「最初の符号状態」
に進む。
【０１４４】［２］ 最初の符号状態． 初期設定のの
ち、図３の伸長装置は、バス５０の上にある最初の入力
符号信号を読取って、そのＣビットをＣビット符号レジ
スタ５７に取入れる。次に入力データ・ストローブ５５
の上に制御装置５３によって一つの信号を与えて、次の
入力符号を外部装置によって入力バス５０の上に与えさ
せる。図２の圧縮装置に関して上に論じた理由により、
レジスタ５７に現在ある初期符号信号は、予め割当てら
れた単一文字のストリング符号の一つであるとわかって
いる。従って、この符号の下位Ｂビットは、データメッ
セジの最初の文字であるとわかり、この文字を伸長装置
からの最初の出力として伝送する。これは、符号レジス
タ５７の下位Ｂビットをバス６０を経て最終文字レジス
タ６１に転送することによって達成され、その文字は、
出力文字バス５１に直接与えられる。この最初の文字は
外部記憶装置の最初の出力記憶場所におかれることにな
っているので、ゼロの記憶場所アドレスがアウトポイン
タ・レジスタ８８にある値をアドレス加算器８６を通過
させて一定値ゼロを加えることによって発生される。従
って記憶場所アドレス・バス８７の上のアドレスは、要
求通りゼロである。出力バス５１およびアドレス・バス
８７が正しい新情報を含むことを指示する出力データ・
ストローブ・ライン５６の上の信号が外部装置に転送さ
れる。
【０１４５】続く伸長装置サイクルに備えて、レベル・
レジスタ８５は、ゼロにセットされる。これは受取った
ストリング内の接頭部ストリングの長さであるとわかっ
ているかである。次に「次の入力状態」の主処理サイク
ルに入る。
【０１４６】［３］ 次の入力状態． 各新入力符号
は、外部装置から読込まれて、それの処理が以下の論理
に従って開始される。符号レジスタ５７からの現在の符
号値は、たったいま処理された符号であって、それをあ
との更新サイクルに備えて保存するためにバス６５を経
て符号レジスタ６４に転送される。同様に、レベル・レ
ジスタ８５にある値は、その値を転送経路にある加算器
９１を用いて、１だけ大きくして、レベル・レジスタ７
８に転送される。この増分が行われるのは、作られるべ
き新ストリングが処理されたばかりのストリングの接頭
部より１文字長い接頭部ストリングをもっているからで
ある。今度は、アウトポインタ・レジスタ８８にあるア
ウトポインタ値が新ストリングからの文字を外部記憶装
置内に置く記憶場所アドレスを含むように更新される。
この記憶場所アドレスは、処理されたばかりのストリン
グの長さを前のベースアドレスに加えたものである。こ
れはレベル・レジスタ７８の中の更新されたばかりのレ
ベル値をアウトポインタ・レジスタ８８にあるアウトポ
インタ値へアドレス加算器８６によって加え、その結果
を、アウトポインタ・レジスタ８８に戻すことによって
達成される。
【０１４７】次に、新入力符号信号は、もしそれが使用
可能であれば読出されている。新入力符号が使用できな
いことをライン５２の上のデータ使用可能信号が指示す
る場合、そのメッセージを完全に処理してしまってお
り、「待ち状態」に新しいメッセージを待つために再び
入る。正規の状態においては、新入力符号信号が使用可
能で、それは入力バス５０から符号レジスタ５７にゲー
トされる。ライン５５の上の入力データ・ストローブ信
号は、外部装置に向けて発せられて、その装置に次の符
号信号を入力バス５０に与えさせる。
【０１４８】レジスタ５７にある新符号信号は、比較器
５８を用いて２B と比較される。符号レジスタ５７にあ
る新符号値が２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 −１ならば、：状態３へ行く 状態２へ行く 上に与えられた状態機械記述語に関する図５の伸長装置
の動作のさらに詳細な説明を次に行う。
【０２００】［０］ 待ち状態． １ブロックの圧縮入
力符号信号を待つ間、図５の伸長装置は、この状態にあ
る。圧縮入力符号を供給する外部信号源からのデータ使
用可能信号は、入力データが使用できるときを指示する
ために用いられる。入力符号が使用可能になると、リー
ド１５２の上のデータ使用可能信号は、「最初の符号状
態」に入るように制御装置１５３に合図する。
【０２０１】［１］ 最初の符号状態． この状態に入
ると、図５の伸長装置は、メッセージの最初のストリン
グ符号を読取る。これは、最初の符号に対してはゼロビ
ットである入力データライン１５０からのビットを読取
るシフト回路網１５６によって行われる。符号計数器１
６０は、ゼロにセットされて、符号回路１５９にゼロビ
ットの符号大きさＤを確立する。図４の圧縮装置の動作
に従って、一つのデータブロックの最初の圧縮符号信号
はゼロであってあからさまに伝送されない。従って、符
号レジスタ１５７は、ゼロにセットされ、最初の符号を
受けたことを示す。
【０２０２】どのゼロ符号に関しても、この最初の符号
は、Ｂビット文字信号を伴っている。従って、制御装置
１５３は、スタック１６１の先頭に記憶するために経路
１６２を経て伝送される最初のＢビットを読取るように
シフト回路網１５６を制御する。スタック１６１の先頭
にある文字は、出力文字バス１５０を通して使用可能で
ある。制御装置１５３は、ライン１５５を通して出力ス
トローブ信号を伝送することによってこの出力文字の使
用可能なことを知らせる。この初めの文字が伝送される
ので、それはあとの伝送に備えてスタック１６１の中に
保持されない。従って、スタック計数器１８４は、ゼロ
値を含むように初期設定される。初期符号を処理し終わ
ると、制御装置１５３は、この最初のストリングをスト
リング・テーブルに入れるために「ゼロストリング更新
状態」に入るように図５の伸長装置を制御する。
【０２０３】［２］ ゼロストリング更新状態． ゼロ
のストリング符号を受取ると、そのゼロストリング符号
にすぐに続く１文字ストリングに対するエントリが割当
てられるべき次の符号番号でストリング・テーブル内に
置かれる。従って、符号計数器１６０は、１だけ増分さ
れて結果として生ずる結果は、ＲＡＭアドレス・レジス
タ１６５にバス１６６を介して伝送される。この状況に
おいて、常にゼロである符号レジスタ１５７の中の値
は、符号レジスタ１７２へバス１７３を介して移され
る。ＲＡＭ１７７は、次に符号レジスタ１７２の内容を
バス１７８を介して新しいストリングの接頭部符号値と
して「書込む」ように制御される。この値は、ＲＡＭア
ドレス・レジスタ１６５によって指定されたアドレスに
ある接頭部符号欄に書込まれる。なお、スタック１６１
の先頭においてバス１７９を介して使用可能な出力文字
バス１５１に出力された最終文字は、このストリングの
拡張文字としてＲＡＭ１７７のアドレス指定された記憶
場所の文字欄に書込まれる。従って、この「ゼロストリ
ング更新状態」においては、ゼロの接頭部符号および受
けた最終のＢビットの拡張文字が書込まれ、そのストリ
ングに対する符号によってアドレス指定されたＲＡＭの
記憶場所に適当な単一文字ストリングを作る。次に、
「新符号状態」に入って次の入力符号信号を処理する。
【０２０４】［３］ 新符号状態． パースされた文字
ストリングを回復するための処理の初めにおいて、Ｄビ
ットの新しい圧縮符号信号がライン１５０から読取られ
る。しかし、初めには、符号レジスタ１５７における前
の符号を符号レジスタ１７２へバス１７３を経て転送し
て、それを次のストリング・テーブル更新に備えて保存
する。ライン１５２の上のデータ使用可能信号は、新符
号信号が使用できるかどうかを決めるために試験され
る。データが使用可能でなければ、現在のデータブロッ
クの終りに達したことになり、伸長装置は、その現在の
仕事を完了した「待ち状態」に戻される。
【０２０５】データが使用可能な場合は、入力の次のＤ
ビットが入力ライン１５０から符号レジスタ１５７の下
位Ｄビットにシフト回路網１５６およびバス１５８を介
して読込まれる。Ｄの値は、符号計数器１６０の中の現
在の値に従って符号大きさ回路１５９によって決定され
る。
【０２０６】この新符号値は、それが追加された新しい
文字のついたゼロ符号ストリングであるかどうかを決め
るためにゼロに対して試験される。従って、ゼロ検出器
１６５が制御装置１５３にリード１７０を介して符号レ
ジスタ１５７の内容がゼロであるかどうかを知らせる。
ゼロが検出されれば、以下のアクションが行われる。入
力データの次のＢビットは、シフト回路網１５６によっ
て入力ライン１５０から読出される。そのＢビットは、
バス１６２を経てスタック１６１の先頭に伝送され、ラ
イン１５５の上の出力ストローブは、新しい正しい文字
が使用できることを外部装置に知らせるように起動され
る。次に、検出器１６３は、符号計数器１６０の中の現
存する計数値が計数器１６０のオール１の状態である２
C −１に等しいかどうかを決定する。符号計数器１６０
がオール１を含む場合、ＲＡＭ１７７の中のストリング
・テーブルは、一杯であって、そこにはそれ以上の更新
データを加えない。現在の入力符号の処理は、そのとき
完了していて、伸長装置は、この「新符号状態」に再び
入って、次の圧縮符号信号を処理するように制御され
る。しかし、符号計数器１６０が２C −１より小さい値
を含む場合、受けたばかりの文字は、前に受けた符号信
号の拡張としてストリング・テーブルを更新すると共に
当然に新単一文字ストリングとしてそのストリング・テ
ーブルを更新するのに用いられる。図５の伸長装置は、
この更新を「単一文字更新状態」に入ることによって行
う。
【０２０７】符号レジスタ１５７がゼロ値を含まなかっ
た場合、その内容は、比較器１６７を介して符号計数器
１６０の中の既存の計数値と比較される。符号レジスタ
１５７が符号計数器１６０より大きな値を含む場合、比
較器１６７は、制御装置１５３にリード１６８を介して
受取ったばかりの符号がまだストリング・テーブルに入
れられていない前の符号の延長である異常な特殊の場合
が起こったことを知らせる。この状態において、新符号
ストリングの最終文字は、前のストリングの拡張文字に
等しく、前のストリングはまた、新符号ストリングの最
初の文字であり、新符号ストリングは、前のストリング
の始めの文字であり、前のストリングは、復号されたば
かりでスタック１６１の先頭にある文字である。従っ
て、「プッシュ」が新ストリングに対してこの文字を保
持するためにスタック１６１において実行され、スタッ
ク計数器１８４は、１だけ増分される。そのあとで、現
在のストリングに対する接頭部符号である符号レジスタ
１７２の中の符号信号は、バス１７６を経てＲＡＭアド
レスレジスタ１６５に転送され、「次の文字状態」に入
ってこのストリングの残部の正常な処理を行う。
【０２０８】しかし、符号レジスタ１５７の中の値がゼ
ロでもなく、また符号計数器１６０の中の既存の計数値
より大きくもない場合、符号レジスタ１５７の中の値
は、正常なストリング符号である。この符号は、符号レ
ジスタ１５７からの符号値をバス１７１を経てＲＡＭア
ドレス・レジスタ１６５に転送し、そのストリングの各
文字を処理し始めるために「次の文字状態」に入ること
によって処理される。
【０２０９】［４］ 次の文字状態． この状態に入る
と、ＲＡＭアドレス・レジスタ１６５は、文字の対応す
るストリングに伸長されるべきストリング符号を含んで
いる。従って、ストリング・テーブルＲＡＭ１７７は、
レジスタ１６５の中の符号値によってアドレス指定され
た記憶場所の内容を読取るように制御されて、そのスト
リングのための接頭部ストリング符号および拡張文字を
それぞれバス１８０および１８３の上に作る。バス１８
３の上の拡張文字は、スタック１６１の先頭に加えられ
て押下げられ、スタック計数器１８４は、１だけ増分さ
れる。
【０２１０】バス１８０の上の接頭部符号は、それがゼ
ロであるかどうかを決めるためにゼロ検出器１８１によ
って試験される。その接頭部符号がゼロであれば、スト
リング・テーブル内のアドレス指定された記憶場所は、
現在のストリング内の最終バイトを含み、「更新ストリ
ング・テーブル状態」に入ってスタック１６１の中に現
在あるストリング・データの処理を完了する。その接頭
部符号がゼロでなければ、接頭部ストリングは、その接
頭部符号をバス１８０を通してＲＡＭアドレス・レジス
タ１６５に転送して、この「次の文字状態」に再び入る
ことによって処理される一つ以上の文字を含んでいる。
【０２１１】［５］ ストリング・テーブル更新状態．
ストリング符号をその文字の列に伸長したのちに、発
生した最終文字は、そのストリング・テーブルを前の符
号値で更新するための拡張文字として用いられる。しか
し、これは二つの状態のないときにのみ起こる。ゼロ検
出器１７４が符号レジスタ１７２の中の前の符号値がゼ
ロに等しいことを決定する場合、このストリングの更新
は、既に起こってしまっており、直ちに「出力作成状
態」に入る。検出器１６３が、符号計数器１６０の中の
値が２C −１に等しいと決定する場合、ストリング・テ
ーブルは、一杯であって、それ以上の更新はできない。
この場合にはまた、直ちに「出力作成状態」に入る。こ
れらの二つの状態のどちらも起こらなければ、更新は、
以下のように行われる。符号計数器１６０の内容は、１
だけ増分され、増分された値は、ＲＡＭアドレス・レジ
スタ１６５にバス１６０を経て転送される。 ＲＡＭ１
７７は、次に割当てられた符号値のサイトであるアドレ
ス指定された記憶場所に符号レジスタ１７２からバス１
７８を経てくる接頭部符号値およびスタック１６１の先
頭からバス１７９を経てくる拡張文字を書込むように制
御される。そのあとで、「出力作成状態」に入る。
【０２１２】［６］ 出力作成状態． 現在のストリン
グの各文字は、スタック１６１の中にいまはあって、適
当な出力文字列を与えるようにバス１５１を通して後入
れ先出しで伝送される。スタック１６１は、ポップ・ア
ップされ、それによって伝送されるべき次の文字は、ス
タック１６１の先頭に置かれて、その結果、外部装置へ
の出力バス１５１を通して使用できる。ライン１５５の
上の出力ストローブ信号は、正しい文字が使用できるこ
とを知らせるために制御装置１５３によって発せられ
る。スタック計数器１８４は、１だけ減分されて、スタ
ック計数値がゼロ検出器１８５によってゼロに対して試
験される。スタック計数器１８４の中の計数値がゼロで
なければ、もっと多くのデータがスタック内にあって、
この「出力作成状態」に入ってもう一つの文字を与え
る。しかし、スタック計数器１８４の中の計数値がゼロ
の場合、現在のストリングの文字の伝送は、完了してお
り、「新符号状態」に入って次のストリングを始める。
【０２１３】［７］ 単一文字更新状態． 単一文字を
一つの符号ゼロ・ストリングの上の一つの明白な拡張と
して受取るとき、この文字は、前の符号値に基いたスト
リング・テーブル内で新しいストリングを作るための拡
張文字として使われる。このストリング・テーブル更新
は、前の符号値を含む符号レジスタ１７２の内容がゼロ
検出器１７４によって非ゼロであるとして検出される場
合だけ起る。ゼロ検出器１７４が、符号レジスタ１７２
の内容がゼロであると決定すれば、このストリングテー
ブル更新は、実行されない。符号レジスタ１７２が非ゼ
ロの値を含む場合、更新は、符号計数器１６０を１だけ
増分し、増分された値をＲＡＭアドレスレジスタ１６５
へバス１６６を経て伝送することによって行われる。Ｒ
ＡＭ１７７は、符号レジスタ１７２からバス１７８を経
てくる接頭部ストリング符号およびスタック１６１の先
頭からバス１７９を経てくる拡張文字をＲＡＭアドレス
レジスタ１６５の中の新符号によってアドレス指定され
た記憶場所の接頭部符号欄および文字欄のそれぞれに書
込むように制御される。
【０２１４】次に符号計数器１６０の内容は、計数器１
６０が値２C −１に達したかどうかを決めるために検出
器１６３によって試験される。この値に達した場合、ス
トリング・テーブルは、一杯であって、それ以上の更新
は、行われない。次に「次の符号状態」に入って次のス
トリングの処理を始める。しかし、計数器１６０の内容
が２C −１より小さければ、「ゼロストリング更新状
態」に入ってストリング・テーブルを受けたばかりの単
一文字ストリングで更新する。
【０２１５】図２〜図５に示した本発明の上述の実施例
は、例えば、ディスクリートなディジタル論理部品を用
いてハードウェアで実現される。表１〜４は、本発明に
よるデータ信号の圧縮および伸長を行うプログラム記憶
式ディジタル計算機にロードするソフトウェアで実現さ
れた本発明の１実施例を示している。明確に言えば、本
発明のプログラム格納計算機の実施例は、図２および図
３に関して先に述べた本発明の最高性能実施例をソフト
ウェアで実現する。表１〜４のプログラム格納計算機の
実施例はＦＯＲＴＲＡＮで実現されるので、互換性のあ
るＦＯＲＴＲＡＮコンパイラを備えた計算機ならどれで
も実行できる。圧縮装置および伸長装置は、それぞれ入
力および出力データを管理する主プログラムの中で呼出
されるべきサブルーチンとして実現される。圧縮装置お
よび伸長装置のサブルーチンは、基礎になっている計算
機のワードの大きさに関係のない任意の長さで密につめ
られた記号の配列について取る動作と置く動作をそれぞ
れ行うＩＢＩＴＳＧおよびＩＢＩＴＳＰという名の文字
操作サブプログラムを用いる。ＩＢＩＴＳＧおよびＩＢ
ＩＴＳＰサブプログラムは、それぞれ等しい大きさの記
号の直線配列の指定された位置にある選択されたビット
長の一つの記号をそれぞれ取ったり、置いたりする。Ｉ
ＢＩＴＳＧは、圧縮装置および伸長装置サブルーチンに
おいて用いるための機能サブプログラムとして実現さ
れ、ＩＢＩＴＳＰは、圧縮装置および伸長装置サブルー
チンの実行において呼び出されるべきサブルーチン・サ
ブプログラムとして実現される。表３および表４は、そ
れぞれＩＢＩＴＳＧおよびＩＢＩＴＳＰを示す。これら
のサブプログラムは、一例として与えられたものであっ
て、等価なサブプログラムが通常の熟練した計算機プロ
グラマによって容易に作られる。
【０２１６】
【表１】
【０２１７】
【表２】
【０２１８】
【表３】
【０２１９】
【表４】
【０２２０】表１および表２にそれぞれ示した圧縮装置
および伸長装置のサブルーチンは、それぞれＣＯＭＰお
よびＤＥＣＯＭＰという名称である。ＣＯＭＰサブルー
チンは、９ビット文字信号のストリングを１２ビット符
号記号信号に圧縮し、ＤＥＣＯＭＰサブルーチンは、１
２ビット符号記号信号を９ビット文字信号のストリング
に伸長する。例示したサブルーチンは、３６ビットワー
ド長を有する計算機を用いる。これらのサブルーチン
は、３２ビット計算機を用いて８ビット文字で動作する
ように容易に変換される。ＣＯＭＰおよびＤＥＣＯＭＰ
は、サブルーチンとして構成されるけれども、それらは
当然別々のプログラムとして等価に構成できる可能性の
あることがわかる。ＦＯＲＴＲＡＮがこれらのルーチン
を実施するために用いられるが、他の等価なプログラム
言語を同じ効果に用いることができるであろう。
【０２２１】さて、表１を参照すると、ＣＯＭＰ（ＩＢ
ＵＦＡ，ＮＡ，ＩＢＵＦＢ，ＮＢ）サブルーチンが示さ
れている。ＣＯＭＰサブルーチンは、配列ＩＢＵＦＡに
含まれたＮＡ個の９ビット文字のブロックについてデー
タ圧縮を行う。ＣＯＭＰは、配列ＩＢＵＦＢの中のＮＢ
個の１２ビット記号で構成された圧縮符号を作る。
【０２２２】表２を参照すると、バッファＩＢＵＦＢの
中に受け入れられたＮＢ個の１２ビット圧縮符号記号信
号のブロックについて伸長を行い、結果として生じた回
復された９ビットの文字信号を出力バッファＩＢＵＦＡ
につめて、結果として生じた文字の数の計数ＮＡを戻す
伸長サブルーチンＤＥＣＯＭＰ（ＩＢＵＦＢ、ＮＢ、Ｉ
ＢＵＦＡ、ＮＡ）が示されている。
【０２２３】表２の伸長装置ＤＥＣＯＭＰは、それのス
トリング・テーブルを文１０の中に合うように寸法を与
えられた４０９６ワード配列ＩＴＡＢＬＥの中に記憶す
る。文１１は、表２の実施例に対して９にセットされた
データ定数ＮＢＩＴＳＡを用いて出力文字信号の中のビ
ットの数をパラメータ化する。文１２は、読出されるべ
き次の入力記号信号を示す入力圧縮記号計数変数ＮＣＨ
Ｂを確定する。文１２はまた、ＮＣＨＢを１に初期設定
する。文１３は、出力バッファＩＢＵＦＡの中に置かれ
ていた文字の数を示す出力文字計数変数ＮＡを確定す
る。文１３はまた、出力バッファの中に置かれるべき最
初の出力文字を加えるときに、ＮＡを１に初期設定す
る。これは、文１８においてあとで説明するような方法
で起る。ＩＴＡＢＬＥの中の各ストリング・テーブル記
憶場所は、三つの整数の値をもつ欄で編成される。各ス
トリング・テーブル記憶場所は、記憶場所の内容を経て
遭遇した文字のストリングをビット１〜１２にある接頭
部ストリング符号、ビット１３〜２４にある接頭部スト
リングの長さおよびビット２５〜３６にあるストリング
拡張文字を介して記憶する。本実施例においては、この
アドレスは、表１に関して上に検討した理由のために符
号信号に１を加えたものである。
【０２２４】文１４および１５は、すべての記憶場所が
空であるということを示すようにストリング・テーブル
ＩＴＡＢＬＥを初期設定する。オールゼロは、プログラ
ムする便宜上、空状態を指示するように任意に選択され
る。オールゼロは、適合ストリングを記憶するときに決
して起り得ない不法構成である。適合ストリングがゼロ
の接頭部符号をもつとき、それは１の接頭部ストリング
長さをもつもので、オールゼロ構成は、この初期設定の
手順の間ストリング・テーブル内になされ得るだけであ
る。
【０２２５】初期処理が文１６において最初の入力符号
記号を読取って、最も最近読取られた符号記号を含むた
めに用いられる変数ＮＯＣＯＤＥの中にこのノード符号
を記憶することによって始められる。文１６は、最初の
入力符号記号の読取りを表３のＩＢＩＴＳＧ機能サブプ
ログラムを用いてＩＢＵＦＢの中のＮＣＨＢ番目の１２
ビット項目を入力することによって行う。文１７は、最
も最近発生された文字を含むために用いられる変数ＩＣ
ＨＡＲを定める。文１６において、ＮＯＣＯＤＥの中に
置かれたばかりの値が単一文字符号であるとわかってい
るので、それは、文１７においてＩＣＨＡＲを満たすた
めに直ちに用いられる。文１８は、出力バッファＩＢＵ
ＦＡの中のこの文字をＮＢＩＴＳＡの大きさの項目のＮ
Ａ番目のサイトに置く。文１８は、表４のＩＢＩＴＳＰ
サブルーチンを呼び出すことによってこの文字出力動作
を行う。そのあとで、ストリング・テーブルのこのスト
リングの拡張によるあとでの更新に備えて、文１９は変
数ＮＯＤＯＬＤの中にＮＯＣＯＤＥの中のストリング符
号を保存し、文２０はＬＥＶＯＬＤの中のストリングの
長さをこの最初のストリングに対する長さの既知の値と
一緒に保存する。伸長処理を初期設定にこのようにした
とき、文２１において主繰返し入る。文２１は、それへ
のあとでの転送を行うために１００のラベルを備えてい
る。
【０２２６】主ループのはじめにおいて、文２１は、記
号計数ＮＣＨＢを１だけ増分し、次に、文２２は、入力
記号計数ＮＣＨＢが処理されるべき記号の番号ＮＢを超
えるかどうかを決めるための試験を行う。現存の記号計
数ＮＣＨＢが伸長されるべき使用可能な記号の番号より
大きければ、その過程は完了であって、ＤＥＣＯＭＰが
サブルーチン・リターン文５７に転送することによって
終了になる。文５７は、その転送を行うためにラベル５
１０を備えている。しかし、伸長されるべきそれ以上の
入力データが使用可能なとき、文２３は、ＩＢＵＦＢの
ＮＣＨＢ番目の１２ビット位置から次の使用可能な記号
を読取る。文２３は、表３のＩＢＩＴＳＧ機能サブプロ
グラムを用いてこの動作を行う。文２３は、読取り符号
記号を処理されている現存の部分ストリングの符号を保
持するために用いられる変数であるＮＯＤＥＮＯの中に
置く。文２４はまた、入力符号記号を最も最近の入力符
号を入れておくのに用いられるＮＯＣＯＤＥに置く。文
２５は、ＮＯＤＥＮＯの中の符号値を試験して、それが
５１２を超えるかどうかを決め、５１２を超えれば、そ
のプログラムは、文２８に移って、正常な伸長過程を始
める。値５１２は、図２、図３に関して前に検討した理
由によって２B に等しい。文２８は、それへの転送を行
うためにラベル１２０を割当てられる。しかし、文２５
の試験がＮＯＤＥＮＯの中の新しい記号が５１２より小
さい値をもっていると決定すれば、その符号は、直接に
解釈される予め割当てられた符号値の単一文字ストリン
グを表す。この単一文字ストリングは、接頭部ストリン
グの長さがゼロである。従って、文２６は、処理されて
いるストリングの接頭部ストリング長さを保持するため
に作業用変数ＬＥＶＥＬを確定する。この場合にＬＥＶ
ＥＬは、ゼロにセットされる。そのあとで、文２７は、
すべての単一文字ストリングの処理が達成される場所で
ある文４０にプログラムを転送する。文４０はそれへの
転送を行うためのラベル２１０を備えている。
【０２２７】文２５がラベル１２０を介して文２８への
転送を行うと、新しい符号値が多重文字ストリングを表
すとわかっているＮＯＤＥＮＯに常駐している。文２８
は、現在のストリングがいままでのところストリング・
テーブルに入っていない直前のストリングの拡張である
異常な特殊な状況に対して試験する。この試験は、この
ストリング符号値を前に定めたことかどうかを決定する
ために新しい符号のストリング・テーブル記憶場所の内
容を調べることによって行われる。実際には、テーブル
は、上に検討したＦＯＲＴＲＡＮの必要条件を満たすた
めにＮＯＤＥＮＯ＋１のところにアドレス指定される。
テーブル・エントリがゼロでなければ、そのストリング
は、前に定められたのであって、転送が文３３に行われ
て正常の処理を続ける。ラベル１３０は、その転送を行
うために文３３に割当てられる。しかし、文２８の試験
がテーブル・エントリが空であることを決定すれば、現
在の符号は、直前のストリングの拡張であるとわかる。
従って、現在のストリングの接頭部ストリング長さは、
前のストリング長さに等しい。従って文２９は、ＬＥＶ
ＯＬＤの中の前のストリング長さを接頭部ストリング長
さ変数ＬＥＶＥＬの中に置く。その特殊な場合には、与
えられるべき最初の文字は、この現在のストリングの親
文字である直前のストリングの拡張文字であるとわか
り、その親文字は、直前のストリングの親文字に等し
く、その親文字または変数ＩＣＨＡＲに常駐する文字で
ある。従って、文３０は、表４のＩＢＩＴＳＰサブルー
チンを呼出してＩＯＨＡＲにある既存の値を新しいスト
リングの終りにある記憶場所において出力バッファＩＢ
ＵＦＡの中に置く。この記憶場所は、伸長装置によって
与えられていたすべての前の文字のＮＡ計数にＬＥＶＥ
Ｌ＋１の中の接頭部ストリングの長さの値を加えたもの
から決定される。新ストリングの最初の文字を出力した
のち、文３１は、ＮＯＤＯＬＤにある前のストリング符
号を復号されるべき接頭部ストリングとしてＮＯＤＥＮ
Ｏに転送し、文３２は、ストリングを復号する場所であ
る主ループに入るために文３４への転送を行う。ラベル
２００は、文３４への転送を行うために文３４に割当て
られている。
【０２２８】文２８によって行われた試験が現在の符号
がテーブル内に既にあるストリングを表すことを示すと
き、ラベル１３０を介して文３３への正常の符号解釈経
路がたどられる。ＦＯＲＴＲＡＮ ＢＩＴＳ関数を用い
る文３３は、呼出されたストリングの接頭部の長さをＮ
ＯＤＥＮＯ＋１の内容によってアドレス指定されたＩＴ
ＡＢＬＥの記憶場所のビット１３において始まる１２ビ
ットから読取る。この接頭部ストリング長さは、このス
トリングの拡張が入れられるストリング・テーブルのあ
とでの更新のためにＬＥＶＥＬに保存される。
【０２２９】文３４は、ＮＯＤＥＮＯ内の符号によって
表された部分ストリングをその接頭部ストリングと拡張
文字に分解する主ループに入る入口である。文３４は、
部分ストリングが接頭部ストリングをもっているかどう
かを決定するために部分ストリングの符号を５１２より
大きな値に対して調べる。部分ストリングの符号が５１
２より小さければ、それは単一文字によって予約された
値であり、文４０への転送が行われて、この単一文字ス
トリングを処理して終りにする。文４０に割当てられた
ラベル２１０は、その転送を行うために用いられる。Ｎ
ＯＤＥＮＯが適合多重符号信号を与える継続的な場合に
は、それのテーブル記憶位置の内容は、ＦＯＲＴＲＡＮ
のＢＩＴＳ関数を用いて呼出される。従って、文３５
は、ビット１３において始まる１２ビットの接頭部スト
リング長さを一時変数ＩＮＤＥＸの中に保存する。文３
６は、ビット２５において開始するＮＢＩＴＳＡビット
拡張文字をＩＣＨＡＲに置く。文３７は、次に、表４の
ＩＢＩＴＳＰサブルーチンを呼出して、この文字をすべ
ての前のストリングの合計ＮＡにＩＮＤＥＸに記憶され
たこの文字に関連した接頭部ストリングの長さを加えた
ものを１位置越えたところでその文字の記憶場所にある
出力バッファＩＢＵＦＡへ入れる。そのあとで文３８
は、ＢＩＴＳ関数を用いて、呼び出された記憶場所から
の１２ビット接頭部ストリング符号をＩＴＡＢＬＥに置
いて、その符号のビット１で開始して、この符号値をそ
れ以降の処理を行うためにＮＯＤＥＮＯに入れる。この
ストリング分解手順は、次に文３９を介してラベル２０
０を用いて文３４へ逆に送り返すことによって繰返され
る。
【０２３０】文４０は、ＮＯＤＥＮＯ内の残りの部分ス
トリング符号が単一文字ストリングを表すとき、処理を
移す先のプログラム内の記憶場所を切分ける。文４０へ
の転送は、各ストリングに対する処理の終りに行われ
る。単一文字ストリングに対する符号は、文字値である
ので、文４０は、ＮＯＤＥＮＯの内容をＩＣＨＡＲに転
送する。次の文４１は、表４のサブルーチンＩＢＩＴＳ
Ｐを呼出すことによってその文字を出力し、その文字を
前のストリングの合計ＮＡを過ぎた最初の文字位置にお
いて出力バッファＩＢＵＦＡの中に入れる。そのあと
で、このプログラムのテーブル更新段階に文４２で入っ
て、この最終文字によって拡張された直前のストリング
をストリング・テーブルに入れることができるかどうか
を決定する。このプログラムのテーブル更新段階は、文
４２において１に初期設定された探索された計数変数Ｎ
を使って前述の多重探索ハッシング手順を用いる。文４
３は、ＩＣＨＡＲ内の拡張文字値およびＮＯＤＯＬＤ内
の前の文字符号とからの更新を試みる場所である最初の
ハッシュアドレスを計算する。量１は、それを上述の理
由でＦＯＲＴＲＡＮ適法テーブル記憶場所に変換するた
めに、ハッシュアドレスに加えられ、この記憶場所アド
レスはＬＯＣの中に記憶される。
【０２３１】文４４および４５は、その探索サイトを調
べてそれが拡張文字を記憶するのに適当であるかどうか
を決定する。文４４は、拡張ストリングの記憶に使用で
きないあらかじめ割当てられた記憶場所１ないし５１３
（符号ゼロないし５１２に対応する）の一つに当たるか
どうかを決定する。ＬＯＣの中のアドレスがあらかじめ
割当てられた記憶場所１ないし５１３の中の一つに対応
すれば、文４６への転送が行われ、さらにハッシュアド
レスを発生する。その転送は、文４６に割当てられたラ
ベル２１８によって行われる。しかし、そのアドレスが
５１３より大きければ、文４５は、ＬＯＣ記憶場所の内
容を試験してその記憶場所が空であるかどうかを決定す
る。その探索サイトが空であれば、文５０への転送がラ
ベル２２０を介して行われ、そのストリング・テーブル
を更新する。しかし、その探索サイトが空でなければ、
そのプログラムは、文４６に進んでもう一つの記憶場所
のためのハッシュアドレスを計算する。文４６は、探索
計数Ｎを１だけ増分し、文４７は、増分された探索計数
を探索長さ限界（この実施例の場合７にセットされてい
る）に対して試験して、それ以上の探索サイトを試みる
べきかどうかを決める。探索長さ限界を越えていなかっ
たならば、そのテーブルの中に受入れできるスペースが
拡張ストリングに対して残っておらず、文５３への転送
がストリング処理を終らせるために行われる。ラベル２
２５がその転送を行うために文５３に割当てられる。し
かし、もう１回の探索が認められれば、文４８は、ＬＯ
Ｃに対する新しいハッシュ・アドレス値をＦＯＲＴＲＡ
Ｎの必要条件を満たすために用いられたばかりの値（モ
ジュロ４０９６）に加えられたＮＯＤＯＬＤについての
第２のハッシュ関数に１を足したものにより計算する。
次に文４９は、文４４への再入をラベル２１５を介して
行って、その探索を再開する。
【０２３２】文４５を介して適法アドレスをもつ探索サ
イトが空であることがわかったとき、文５０への転送が
行われた。突きとめられたサイトのアドレスは、この拡
張ストリングに対する表１の圧縮プログラムによって作
られたものであり、従って、このアドレスは、そのスト
リングの符号番号として用いられる。これは、そのスト
リングに対する記述データを呼出された記憶場所に書込
むことによって達成される。従って、文５０は、ＮＯＤ
ＯＬＤからの接頭部ストリング符号をその記憶場所の最
初の１２ビットの中に書込むためにＢＩＴＳ ＦＯＲＴ
ＲＡＮ関数を用いる。ＢＩＴＳ ＦＯＲＴＲＡＮ関数を
用いる文５２は、ＬＥＶＯＬＤからの接頭部ストリング
長さをその記憶場所の次の１２ビットに書込み、文５１
は、ＩＣＨＡＲからの拡張文字をその記憶場所の残りの
ビットに書込む。そのあとで、文５３〜５５において、
ストリング記帳（ｂｏｏｋｋｅｅｐｉｎｇ）の終りが行
われる。文５３は、ＮＯＣＯＤＥの内容をＮＯＤＯＬＤ
に転送し、それによってＮＯＣＯＤＥの中の最も最近読
取られた符号記号を前の符号ＮＯＤＯＬＤに変換する。
文５４は、この前の符号のＬＥＶＥＬ内の接頭部ストリ
ング長さを１だけ増分して、前のストリングが次のテー
ブル更新の際に接頭部ストリングとして入れられると
き、前のストリングのストリング長さを与える。この接
頭部ストリング長さの量は、ＬＥＶＯＬＤに記憶され
る。文５５は、出力文字の計数ＮＡを処理されたばかり
の最終のストリングの長さであるＬＥＶＥＬ＋１の大き
さだけ大きくする。ストリング記帳のこの終りが行われ
たのち、文５６は、ラベル１００を介して文２１への再
入を行い、次の入力圧縮符号記号信号を処理する。
【０２３３】文５７は、データ・ブロック処理の終りを
切分ける。表２のプログラムにおいて、クリーンアップ
処理は、必要ないので、制御が表２のサブルーチンＤＥ
ＣＯＭＰを呼出した主プログラムに戻されて、入力バッ
ファＩＢＵＦＢに記憶された圧縮符号記号信号のブロッ
クを伸長する。
【０２３４】表１ないし表４に関して説明した本発明の
実施例は、ＦＯＲＴＲＡＮプログラミング言語で与えら
れた圧縮および伸長サブルーチンとして例示されたが、
その圧縮および伸長サブルーチンは、当然に主プログラ
ムとしてフォーマットを作ることができた。これらのプ
ログラムは、例えばコンピュータまたはマイクロプロセ
ッサにおいて、ソフトウェアとして用いることができる
し、または、例えば、磁気ディスクまたはテープの制御
装置の入出力電子回路において用いるためのＲＯＭチッ
プの形でファームウェアとして構成してもよい。なお、
ＦＯＲＴＲＡＮ以外のプログラミング言語を用いること
もできるし、または同じ言語または他の言語における他
のプログラムコーディングを、ここで説明した機能を行
うのに用いて、本発明のデータ信号圧縮および伸長の諸
手順を実施することもできる。
【０２３５】マイクロプロセッサまたは他の形式のコン
ピュータのプログラム格納式のものが、ここで説明した
能力と技術の１実施例を、すなわち、基本的データ操作
の選択および状態順序づけ制御インプリメンテーション
の選択における以外は、ここで述べたデジタル論理式の
ものと区別できない実施例を与えることが分る。汎用コ
ンピュータにおける標準化されたデータ操作の動作を、
ワイヤおよび論理ゲートの形でなく再書込みできる記憶
装置に記憶されたものとしての容易に変更された形式の
制御ロジックと共に作ることの経済性はによって、実行
速度のある程度の相対的低下で特定の適用業務に対して
経済的に作ることができ、さ細な方法で経済的に製造で
き、かつ迅速に変更できる実施例を提案できる。
【０２３６】本発明のハードウェア実施例に関する上述
のハッシュ関数は、２０ビットの項目（１２の符号ビッ
トと８の文字ビット）を含む符号、文字タプルを１２ビ
ット・アドレス・スペースにマップする。ソフトウェア
実施例に関して用いられたハッシュ関数は、２１ビット
項目（１２符号ビットと９文字ビット）を２１ビット・
アドレス・スペースにマップする。２０ビットの値およ
び２１ビットの値のすべてが起こるわけではないので、
そのようなハッシュ関数を用いることができる。上述の
ハッシュ関数を前に述べた基準を満たすように設計し
た。なお、このハッシュ関数は、その諸仮定から生ずる
撞着を最小にするように設計され、第１には、幾つかの
個々の入力文字がほかのものよりより頻繁に用いられ、
低い番号の文字が頻繁に使われ易く、そして、第２に
は、幾つかの符号が他のものよりより頻繁に用いられ、
早期に生ずる符号が最も頻繁に用いられるであろう。上
述のものに代るハッシュ関数は、符号の左５ビットを回
転することによって最初のハッシュアドレスを発生し、
その文字ビットに排他的論理和演算を施して回転された
符号の高位ビットにすることにより実施できる。三つの
順次のアドレスが前の１２ビット・ハッシュ・アドレス
にモジュロ４０９６を加えることによって発生され、新
しい１２ビット番号が終端間で反転され、かつ結果とし
て生じた番号の最下位ビットを１に強制して左３ビット
を回転した符号番号を含んでいる。
【０２３７】図２ないし図５に関して説明した本発明の
実施例は、本発明の代りの実施例を与えるために上述の
ものと異なる組合わせで結合できる種々の随意選択的技
術を用いる。図２および図３の圧縮装置−伸長装置は、
単一文字ストリングのすべてでストリング・テーブルを
初期設定するが、一方、図４および図５の圧縮装置−伸
長装置は、ゼロストリングだけでストリング・テーブル
を初期設定する。図２および図３については、単一文字
ストリングの初期設定を単一文字そのものをこれらのス
トリングの符号番号として用い、２B より大きいアドレ
スに対してのみストリング・テーブルにアクセスするこ
とを可能にすることによって行われる。圧縮されるべき
文字のすべては、Ｂビット・バイトであるから、全ての
文字は、２B より小さな値をもっている。従って、２B
より小さい符号値をもつ単一文字ストリングが図２の圧
縮装置によってストリング・テーブルのアクセスなしで
伝送される。図３の伸長装置において単一文字ストリン
グとして認識され、それによって直接伝送されてもよ
い。図４および図５の圧縮装置−伸長装置は、ゼロスト
リングだけでテーブル初期設定を行うのであって、それ
のストリング・テーブルをゼロないし２C −１のすべて
のアドレスで呼出す。従って、図４の圧縮装置の実施例
においては、単一文字ストリングが、受けた文字を符号
番号ゼロでハッシュして、結果として生じたハッシュ・
アドレスにあるゼロのストリング接頭部符号を入れるこ
とによってストリング・テーブルに入れられる。図５の
伸長装置もまた接頭部符号ゼロを適当なストリング・テ
ーブルの記憶場所に入れることによって単一文字のスト
リングを記憶する。
【０２３８】このほかの変形例としては、図２および図
３の圧縮装置−伸長装置は、ストリングのハッシュ・テ
ーブル・アドレスをそれのストリング符号記号信号とし
て割当てるが、一方、図４および図５の圧縮装置−伸長
装置は、新ストリング・エントリーが作られるストリン
グ符号記号信号を各ストリングに逐次に割当てる。
【０２３９】なお別の変形例としては、図２および図３
の圧縮装置−伸長装置は、固定長符号値を各ストリング
に割当てるが、一方、図４および図５の圧縮装置−伸長
装置は、可変する長さの符号記号を各ストリングに割当
てる。図２および図３の実施例において、固定長はＣビ
ットの全アドレス長であるが、一方図４および図５の実
施例においては圧縮符号記号の長さはＣビットの長さが
得られるまでデータブロックの処理の間増える。
【０２４０】なお別の変形例としては、図３の伸長装置
は、伸長ストリング反転を行うためのストリング長さイ
ンデクシング機構を用いるが、一方、図５の伸長装置
は、この目的に後入れ先出しスタックを用いる。
【０２４１】前述のように、各変形例は、図２ないし図
５に開示された実施例において実施される。当業者がこ
れらの変形例を別途組合せて本発明の範囲内で追加の実
施例を作ることができる。上述の四つの変形例の各々
は、二つの可能性をもっているので、１６の別々の実施
例を構成できる。例えば図４の圧縮装置に関して、逐次
割当てストリング符号をＣビットの固定長出力として伝
送できる。その場合、符号大きさ回路１２３を除去でき
る。そのような実施例においては、図５の伸長装置は、
そのときやはり符号大きさ回路１５９を除くことになろ
う。そのような圧縮装置−伸長装置においてストリング
・テーブルをゼロストリングだけで初期設定する変形例
が組入れられると（図４および図５で説明したよう
に）、図４の圧縮装置のシフト回路網１１８を用いてオ
ールゼロの空白符号の伝送に続くＢビット・バイトと同
様に固定長Ｃビット圧縮符号信号を伝送するのに用いる
ことができる。同様にして、図５の伸長装置は、オール
ゼロの空白符号を受取ったのに続いて、Ｂビットバイト
信号を受取るためと共に固定長Ｃビット符号信号を受け
入れるためにシフト回路網１５６を用いるであろう。し
かし、図４および図５の圧縮装置−伸長装置を上述のよ
うに固定長符号の変形例を含むように変更し、さらにす
べての単一符号のストリングを使うストリング・テーブ
ル初期設定を用いるように変更するとすれば、図４の圧
縮装置のシフト回路網１１８を符号番号レジスタ１１９
からバス１２０を通して与えられる出力と共に除去する
ことになろう。そのような実施例においては、図５の伸
長装置はそのときバス１５８を介して符号レジスタ１５
７に直接に加えられる入力符号をもったシフト回路網１
５６を除去するであろう。さらに、図４の符号計数器１
２１をストリング・テーブル初期設定が行われたのち
に、２B にセットすることになり、図５の符号計数器１
６０をゼロの代りに２B に初期設定することになろう。
なお、符号レジスタ１１６からの図４のバス１１７は、
Ｂビット文字をレジスタ１１９の最下位位置に挿入する
ために符号番号レジスタ１１９に加えることになろう。
レジスタ１１９のＣ−Ｂの最上上位位置をゼロにセット
することになろう。図４および図５の圧縮装置−伸長装
置に対する上述の変更は、圧縮効率を犠牲にして性能を
向上させることになろう。
【０２４２】上述のことから、変更された図４のレジス
タ１１６および１１９とそれらの動作との間の関係は、
図２のレジスタ１７および１９とその動作との間の関係
と同一であることが分る。なお、すべての単一文字スト
リングを使ったテーブル初期設定を用いる変更された実
施例においては、図４の比較器１３４へのゼロの値をも
った入力は、用いられない。初めて遭遇する文字の単一
符号ストリングを含む単一文字のストリングは、新しく
遭遇した文字に対して、新しい文字に先立つオールゼロ
の空白符号信号を伝送するのではなく、図２に関して述
べたものと同一の方法で伝送される。
【０２４３】なお、すべての単一文字ストリングと固定
長圧縮符号信号とでのテーブル初期設定を用いる図４お
よび図５の変形された圧縮装置−伸長装置の実施例にお
いては、図５の伸長装置は、多重文字ストリングまたは
単一文字ストリングを受取ったかどうかを決定するため
に符号レジスタ１５７の内容をゼロにではなく２B に比
較することによって変更される。バス１６２は、符号レ
ジスタ１５７から出されて、単一文字ストリングを直接
にスタック１６１に伝送する。バス１８０の上の符号
は、一つのストリングの中の最初の文字にＲＡＭ１７７
のストリング・テーブルを通る逆方向トレースにおいて
遭遇したときを決定するためにゼロにではなく２B に比
較される。ＲＡＭアドレスレジスタ１６５からスタック
１６１に先頭へのバスは、図３の伸長装置に関して前述
したのと同様のやり方でトレースされたストリングの最
終文字をスタック１６１へ転送するように接続される。
図５のゼロ検出器１７４は、この変更実施例においても
はや必要ではなくなる。レジスタに入るゼロの値をもっ
た入力も必要なくなる。
【０２４４】単一文字のストリングのすべてでストリン
グ・テーブルを初期設定し、新しいストリング・エント
リが作られるとき、ストリング符号記号を逐次に割当
て、そして変化する長さの圧縮符号信号を伝送する圧縮
装置−伸長装置の実施例を作りたい場合は、図４および
図５の装置をそれ相応に変更できる。図４の圧縮装置
は、ストリング・テーブルの初期設定が行われたのち
に、符号計数器１２１を２Bにセットして、図５の計数
器１６０をゼロの代りに２B に初期設定することによっ
て変更できる。なお、文字レジスタ１１６からの図４の
バス１１７は、上述のように符号番号レジスタ１１９へ
加えられる。同様に図５の伸長装置は、多重文字ストリ
ングまたは単一文字ストリングを受取ったかどうかを決
定するために符号レジスタ１５７の内容をゼロとではな
く２B と比較することによって変更される。なお、バス
１８０の上の符号は、一つのストリング内の最初の文字
にＲＡＭ１７７のストリング・テーブルを通る逆方向ト
レースで遭遇したときを決定するのにゼロとではなく２
B と比較される。この実施例においては、図５のゼロ検
出器１７４もレジスタ１５７に入るゼロの値をもった入
力も必要でなくなる。
【０２４５】空白ストリングだけでストリング・テーブ
ルを初期設定するように図２および図３の圧縮装置−伸
長装置の実施例を変更したい場合、比較器２６は空白符
号および空符号に等しいハッシュ関数アドレスを放棄す
るように変更される。なお、比較器３２は、文字レジス
タ１７の中のＢビット文字を空白符号の伝送のあとに伝
送すべきかどうかを決定するために符号番号レジスタ１
９の中の値をゼロと比較するように変更される。Ｂビッ
ト文字をゼロを満たされたＣビット文字として伝送でき
るし、またはその代りにシフト回路網機構を前述のもの
と同様に用いることもできる。同様にして、図３の伸長
装置は、２B ではなくゼロを検出するためと符号レジス
タ５７を制御するためとに比較器５８を用いることによ
って空白符号に直接続く単一文字を伝送するように変更
できる。
【０２４６】上述のことから図２および図３の実施例
は、圧縮効率を犠牲にして最高性能を与えることがわか
るであろう。なお、図４および図５の実施例は、性能を
犠牲にして最高圧縮を与える。各変形例、すなわち、全
ての単一文字ストリングを用いてのテーブル初期設定；
新しいストリングを作るとき逐次に割当てられるストリ
ング符号記号；固定長符号値を伝送すること；および後
入れ先出しスタックを用いるストリング反転、を組合わ
せる上述の変更は応用業務（アプリケーション）に従っ
て好ましい実施例を与えることのできる最高性能と最高
圧縮との間の中間のものである。ストリング反転のため
の図５のスタック機械化は、図３のストリング長さイン
デクシング機構と容易に相互交換できる。ストリング長
さインデクシングを用いるとき、レベル欄は、ＲＡＭ記
憶場所に追加され、図３のインデクシング機構の構成要
素６１，７８，８５，８６，８８および９１が用いられ
る。スタック機構が用いられるとき、ＲＡＭのレベル欄
は必要でなく、図５の構成要素１６１，１８４および１
８５が用いられる。
【０２４７】上述のように、表１〜表４は図２および図
３の最高性能ハードウェア実施例の各変形例を用いる本
発明のプログラム格納式コンピュータの実施例を示す。
本発明の種々のソフトウェア実施例は、上述の各変形例
の種々の組合せを通常の熟練したコンピュータ・プログ
ラマによって普通に与えられるそのためのプログラムコ
ーディングと共に用いることによって提供することがで
きる。
【０２４８】まとめると、本発明は入力データの中で観
察された文字のストリングを、多分、圧縮されるべきデ
ータブロックの始めにおいてテーブルを初期設定できる
単一文字ストリングなどのストリングを除いて記憶する
ストリング・テーブルを用いる。それらのストリング
は、各ストリングの記憶されたセットが処理されている
データの統計に適応するようにストリングが入力データ
の文字ストリームの中に観測されるとき、テーブルに動
的に入れられる。Ｘ文字の各ストリングは、Ｘ−１文字
の接頭部ストリングと一つの拡張文字とを含み、その場
合に接頭部ストリングもまたテーブルの１構成要素であ
る。各ストリングは、一つの符号記号を割当てられ、記
憶されたストリングが入力データ文字ストリームの中で
遭遇されると、遭遇したストリングは、圧縮データの中
のその符号信号によって表される。各ストリングは、ス
トリングの符号記号、接頭部ストリングの符号記号、お
よびストリング拡張文字とによって判然とまたは暗黙裏
に（すなわち、直接にまたは間接的に）、のいずれかで
記憶される。データ文字信号のストリームは、各文字の
ストリングにそのストリームをパースすることによって
処理され、各ストリングは、ストリング・テーブルの中
に既に置かれている。このパーシングは、始めの文字か
ら出発して１度に１文字ずつ分離するデータ文字ストリ
ームの中への唯１回のパスにおいて達成される。各文字
は、拡張されたストリングがストリング・テーブル内に
あるものに一致する場合、前のストリングを拡張するの
に用いられる。そうでなければ、その文字は、新しいス
トリングを開始するのに用いられる。基本的には、圧縮
処理は、入力データストリームの中で各文字が出てきた
とき、以下のように各文字に次々に加えられる循環ステ
ップとして考えてもよい。
【０２４９】入力データストリームからのストリングＳ
がストリング・テーブル内に置かれていたとする。その
入力データ・ストリームの中で次に続く文字ｃに対し
て、そのテーブルは、拡張ストリングＳｃがその中に存
在するかどうかを決定するために探索される。ストリン
グＳｃがそのテーブルの中に存在すれば、次に続く文字
が試験されてその手続きが再び適用される。拡張ストリ
ングがそのテーブルに存在しなければ、ストリングＳに
対する符号記号が圧縮出力として伝送され、ストリング
Ｓｃがそのテーブルに入れられる。次に文字ｃは、次の
ストリングの最初の文字として用いられて、その手続き
は、次に続く入力文字を用いて再び適用される。
【０２５０】ストリングＳｃに対する探索は、一つのス
トリング・テーブルアドレスを与えるために文字ｃをス
トリングＳに対する符号と組合せることによって行われ
る。拡張ストリングＳｃは、既にそのアドレスの記憶場
所に記憶されていれば、そのストリングＳｃは、そのテ
ーブルの中に存在していることになる。その記憶場所が
空であれば、そのストリングは、そのテーブルの中に存
在しない。その場合には、ストリングＳに対する符号記
号が伝送され、ストリングＳｃが空記憶場所に入れられ
る。できれば、文字ｃとストリングＳに対する符号との
組合せが上述の限定探索ハッシュ手順によって行われる
のが好ましい。圧縮の間、圧縮手順の中の１点において
定められた可能なストリングの数がストリングの実際の
数およびある本質的なファクタによる経済的記憶装置の
大きさを超えることになるので、ハッシュ・テーブル機
械化は、あらかじめ割当てられていないストリングを記
憶するのに用いられる。一般的には、ハッシュ・テーブ
ルの各記憶場所が選択された数学的関数によって割当て
られた可能な項目の割当てられたセットを含むことので
きるものがハッシュ・テーブルである。前述の限定探索
ハッシュ・テーブル・プロセスにおいて、各可能なアド
レスが限られた数の記憶アドレスの小さなグループ内で
のみ現れる。この基準は、可能なエントリを探すためま
たはそれがテーブルの中にないことを定めるために必要
な探索の量を限定する。
【０２５１】圧縮の間ストリングが少なくともそれを識
別するためのその接頭部符号を用いて検索される。伸長
の間、ストリングがその符号記号によって直接に識別さ
れる。伸長装置のストリング・テーブルは、各ストリン
グ記憶場所に接頭部ストリング符号および拡張文字を記
憶し、そのストリング記憶場所は、そのストリングに対
する符号によってアドレス指定可能である。従って、入
力符号記号は、接頭部ストリングおよび拡張文字を与え
るテーブル内で探索される。次に接頭部ストリングは新
接頭部ストリングおよび新拡張文字を与えるテーブル内
で探索される。この過程は始めの単一文字ストリングに
出合うまで繰返される。
【０２５２】本発明の上述の各実施例において、ハッシ
ュアドレスまたは数が大きくなってゆく次々の値がスト
リングのための圧縮符号記号信号として用いられる。こ
れらの値の矛盾のない変更またはアイソモルフィズムも
またそれらのストリングに対する圧縮符号記号信号とし
て用いることができるとわかる。
【０２５３】本発明の上述の実施例の若干の変形を以下
のように容易にわかる設計変更を用いて行うことができ
る。
【０２５４】本発明では、圧縮装置がディスク装置また
はテープ装置のような同期チャネルに圧縮データを与え
ている場合、その出力速度がバッファリングを最小にす
るためにチャネルの入力速度に一致するように圧縮装置
の速度を増減するのが望ましいことがある。圧縮装置の
出力速度を達成された圧縮比によって制御し、その圧縮
比は遭遇したデータの形式に従って変わる。圧縮装置が
高すぎる速度で出力記号を作るように、その圧縮装置が
圧縮しにくいデータに遭遇した場合、圧縮装置を入力文
字の間で待機させることによって減速できる。圧縮装置
が非常に圧縮しやすいデータに遭遇するので、それが出
力記号をあまりゆっくり作る場合、その圧縮装置を圧縮
装置の効率を減らすことによってスピードアップでき
る。これは、出力符号記号を必要とするときは常に、文
字ストリング拡張を中止することによって行われてもよ
い。従って、圧縮装置が必要な出力速度を遅くするとき
は常に最長マッチより少ないストリングを選ぶことがで
きる。なお、圧縮有効度は、データブロックの初期部分
を処理するとき低くなり、そのブロックの処理が続くと
き増加する傾向があるので、圧縮符号ストリームの転送
を開始する前に圧縮を始めて圧縮速度の変化を相殺する
ことが望ましいことがある。この待ち時間損失は、圧縮
データを圧縮装置から外部装置に書込むときにのみ起こ
ることがわかる。圧縮データを外部装置から読出すとき
には、圧縮データが外部信号源から使用できるようにな
ったら直ちに伸長を開始できる。
【０２５５】さらに別の変更が選択された値より小さく
なるようにパースされたストリング長さを制御するため
に圧縮装置の一部分として計数器を用いることを含むこ
とがある。この特徴は、圧縮データの出力速度がさらに
予測しやすくなるように瞬時圧縮比の変動を小さくする
であろう。なお、そのような計数器は、最大ストリング
長さに敏感な伸長装置内の装置の価格を引下げるであろ
う。そのような装置には、図５の後入れ先出しスタック
１６１のほかに、レベル・レジスタ７８および８５、ア
ドレス加算器８６、アウトポインタ・レジスタ８８なら
びに図３のＲＡＭ７５のレベル欄がある。
【０２５６】本発明のさらに別の変更は、同時にではな
いけれども圧縮および伸長の両方に対して同じハードウ
ェア装置のセットを用いることであることがある。圧縮
および伸長の必要条件の間には、特にＲＡＭについて、
同時性を失ってもよいとき、かなりの価格の節約をこの
変更によって得ることができるという十分な類似性があ
る。なお、圧縮を実行する際に連想記憶装置をＲＡＭの
代りに用いることもできよう。そのような変更は、ハッ
シングの必要をなくして制御の複雑さを減らす。
【０２５７】
【発明の効果】本発明は、非常に様々なデータの種類に
ついて適応性のある可逆データ圧縮および伸長をデータ
統計またはデータ冗長度の形式について前もって何ら知
ることなしに達成し、かつその圧縮符号の伸長を実現す
る方法および経済的な装置を提供する。従って、関連の
データ圧縮装置と共同して、良好な圧縮比を、最も速い
今日の磁気テープおよび磁気ディスクデータ記憶装置な
らびに最も速い今日の商用通信リンクと共に用いるのに
適する高性能動作で達成することができる。
【図面の簡単な説明】
【図１】データ文字信号のストリームのパースされた部
分の略図である。
【図２】最高性能を与えるように実施された本発明によ
るデータ圧縮装置の略ブロック図である。
【図３】最高性能を与えるように実施された、図２の圧
縮装置からの符号信号の圧縮ストリームを伸長するのに
適応された本発明によるデータ伸長装置の略ブロック図
である。
【図４】最高圧縮を与えるように実施された本発明によ
るデータ圧縮装置の略ブロック図である。
【図５】図４の圧縮装置からの符号信号の圧縮ストリー
ムを伸長するように実施された本発明によるデータ伸長
装置の略ブロック図である。
【符号の説明】
１３ 制御装置 １７ 文字レジスタ １９ 符号番号レジスタ ２３ ハッシュ関数回路 ２６，３２ 比較器 ２８ ＲＡＭアドレス・レジスタ ２９ ＲＡＭ ３５ 初期設定計数器 ５３ 制御装置 ５７，６４ 符号レジスタ ５８，７２ 比較器 ６１ 最終文字レジスタ ６２ ＲＡＭアドレス・レジスタ ６９ ハッシュ関数回路 ７５ ＲＡＭ ７８，８５ レベル・レジスタ ８１ 検出器 ８６ アドレス加算器 ８８ アウトポインタ・レジスタ ９１ 加算器 ９３ 初期設定計数器 １１３ 制御装置 １１６ 文字レジスタ １１８ シフト回路網 １１９ 符号番号レジスタ １２１ 符号計数器 １２３ 符号大きさ回路 １２７ ハッシュ関数回路 １３０ ＲＡＭアドレス・レジスタ １３１ ＲＡＭ １４１ 初期設定計数器 １５３ 制御装置 １５６ シフト回路網 １５７，１７２ 符号レジスタ １５９ 符号大きさ回路 １６０ 符号計数器 １６１ スタック １６３ 検出器 １６５ ＲＡＭアドレス・レジスタ １６７ 比較器 １６９，１７４，１８１，１８５ ゼロ検出器 １７７ ＲＡＭ １８４ スタック計数器

Claims (20)

    (57)【特許請求の範囲】
  1. 【請求項１】 データ文字ストリームにおける、データ
    文字ストリングに対応する圧縮された符号信号ストリー
    ムから、当該データ文字ストリームを復元するデータ伸
    長方法において、 前記圧縮された符号信号ストリームを受信するステップ
    と、 その受信した符号信号から対応するデータ文字ストリン
    グを取り出すステップであって、受信した符号信号を用
    いて、前記符号信号に対応するデータ文字ストリングを
    ストアするメモリから、対応するデータ文字ストリング
    を検索するステップを含むステップと、 取り出されたデータ文字ストリングを用いて前記データ
    文字ストリームを復元するステップと、 前記取り出すステップに応答して、拡張されたストリン
    グを前記メモリにストアすることによって、前記符号信
    号に応答してデータ文字ストリングを前記メモリに供給
    するステップとを具え、取り出されたデータ文字ストリ
    ングを、次に取り出されたデータ文字ストリングの第１
    文字と連結させて、拡張されたストリングを形成し、お
    よび拡張されたストリングの各々を、対応する符号信号
    を用いて、前記メモリから検索可能な形態で、前記メモ
    リにストアすることを特徴とするデータ伸長方法。
  2. 【請求項２】 前記圧縮された符号信号ストリームは、
    前記データ文字ストリーム中のデータ文字を探索して、
    割り当てられた符号信号を持つデータ文字ストリングと
    の最長一致を決定して生成されたものに対応し、 決定された最長一致に対応する符号信号を用いて前記圧
    縮されたストリームを生成し、および 各決定された最長一致を、データ文字ストリームにおい
    て次に続く文字と連結させて、最長一致を決定するため
    に用いるデータ文字ストリングを供給することを特徴と
    する特許請求の範囲第１項に記載の方法。
  3. 【請求項３】 前記対応するデータ文字ストリングを取
    り出すステップは、受信した符号信号が最初にストアさ
    れた文字に対応するか否かを決定し、対応する場合は、
    当該文字を、取り出したデータ文字ストリングとして用
    いるステップを含むことを特徴とする特許請求の範囲第
    １項に記載の方法。
  4. 【請求項４】 複数の予め定めたストリングを最初にス
    トアし、および前記圧縮されたストリームを伸長する前
    に、対応する符号信号を前記複数の予め定めたストリン
    グに割り当てるステップを含むことを特徴とする特許請
    求の範囲第１項に記載の方法。
  5. 【請求項５】 最初にストアされた予め定めたストリン
    グは、前記データ文字ストリーム中の個別の文字に対応
    するストリングを含むことを特徴とする特許請求の範囲
    第４項に記載の方法。
  6. 【請求項６】 受信した符号信号を用いて前記メモリを
    アドレス指定して対応するデータ文字ストリングを検索
    することを特徴とする特許請求の範囲第１項に記載の方
    法。
  7. 【請求項７】 符号信号に応答して前記メモリから逆の
    順序でデータ文字ストリングを検索し、および検索され
    たデータ文字を反転させて、検索に用いた符号信号に対
    応するデータ文字ストリングを生成するステップを含む
    ことを特徴とする特許請求の範囲第６項に記載の方法。
  8. 【請求項８】 データ文字ストリームにおける、データ
    文字ストリングに対応する圧縮された符号信号ストリー
    ムから、当該データ文字ストリームを復元するデータ伸
    長装置において、 前記圧縮された符号信号ストリームを受信する手段と、 その受信した符号信号に応答して、対応するデータ文字
    ストリングを取り出す手段であって、受信した符号信号
    に応答して、前記符号信号に対応するデータ文字ストリ
    ングをストアするメモリから、対応するデータ文字スト
    リングを検索する手段を含む手段と、 取り出されたデータ文字ストリングを用いて前記データ
    文字ストリームを復元する手段と、 取り出されたデータ文字ストリングに応答して、拡張さ
    れたストリングを、前記メモリにストアすることによっ
    て、前記符号信号に応答してデータ文字ストリングを前
    記メモリに供給する手段とを具え、取り出されたデータ
    文字ストリングを、次に取り出されたデータ文字ストリ
    ングの第１文字と連結させて、拡張されたストリングを
    形成し、拡張されたストリングを、それぞれ、対応する
    符号信号を用いて、前記メモリから検索可能な形態で前
    記メモリにストアすることを特徴とするデータ伸長装
    置。
  9. 【請求項９】 前記圧縮された符号信号ストリームは、
    前記データ文字ストリーム中の連続データ文字を探索し
    て、割り当てられた符号信号を持つデータ文字ストリン
    グとの最長一致を決定して生成されたものに対応し、 決定された最長一致に対応する符号信号を用いて前記圧
    縮されたストリームを生成し、および 各決定された最長一致を、データ文字ストリームにおい
    て次に続く文字と連結させて、最長一致を決定するため
    に用いるデータ文字ストリングを供給することを特徴と
    する特許請求の範囲第８項に記載の装置。
  10. 【請求項１０】 前記対応するデータ文字ストリングを
    取り出す手段は、受信した符号信号が最初にストアされ
    た文字に対応するかを決定し、対応する場合は、当該文
    字を、取り出したデータ文字ストリングとして用いるこ
    とを特徴とする特許請求の範囲第８項に記載の装置。
  11. 【請求項１１】 複数の予め定めたストリングを最初に
    ストアし、および前記圧縮されたストリームを伸長する
    前に、対応する符号信号を前記複数の予め定めたストリ
    ングに割り当てる手段を含むことを特徴とする特許請求
    の範囲第８項に記載の装置。
  12. 【請求項１２】 最初にストアされた予め定めたストリ
    ングは、前記データ文字ストリームの個別の文字に対応
    するストリングを含むことを特徴とする特許請求の範囲
    第１１項に記載の装置。
  13. 【請求項１３】 前記メモリは、受信した符号信号に応
    答して対応するデータ文字を検索することを特徴とする
    特許請求の範囲第８項に記載の装置。
  14. 【請求項１４】 符号信号に応答して前記メモリから逆
    の順序でデータ文字ストリングを検索し、および検索さ
    れたデータ文字を反転させて、検索に用いた符号信号に
    対応するデータ文字ストリングを生成する手段を含むこ
    とを特徴とする特許請求の範囲第１３項に記載の装置。
  15. 【請求項１５】 入力されたデータ文字ストリームを圧
    縮して圧縮された符号信号ストリームにし、および前記
    符号信号を用いて、前記圧縮されたストリームを伸長し
    て前記データ文字ストリームを復元する方法において、 前記データ文字ストリームにおけるデータ文字を探索
    し、データ文字ストリングに関連する符号信号を有する
    第１メモリにストアされたデータ文字ストリングとの最
    長一致を決定するステップと、 最長一致が決定されたデータ文字ストリングに対応する
    符号信号を用いて、前記圧縮されたストリームを生成す
    るステップと、 拡張されたストリングを前記第１メモリにストアし、お
    よびそれに関連した符号信号を割り当てて、最長一致を
    決定するために用いるデータ文字ストリングを供給する
    ステップであって、最長一致を構成するデータ文字を、
    前記データ文字ストリーム中の次の文字と連結して、拡
    張されたストリングを形成するステップと により前記入力されたデータ文字ストリームを圧縮し、
    および 前記圧縮されたストリーム中の符号信号から対応するデ
    ータ文字ストリングを取り出すステップであって、前記
    符号信号に対応するデータ文字ストリングをストアする
    第２メモリから、符号信号を用いて、データ文字ストリ
    ングを検索するステップを含むステップと、 取り出されたデータ文字ストリングを用いて前記データ
    文字ストリームを復元するステップと、 前記取り出すステップに応答して、拡張されたストリン
    グを第２メモリにストアすることによって、前記符号信
    号に対応して、データ文字ストリングを前記第２メモリ
    に供給するステップとを具え、取り出されたデータ文字
    ストリングを、次に取り出されたデータ文字ストリング
    の第１文字と連結させて、拡張されたストリングを形成
    し、および拡張されたストリングを当該拡張されたスト
    リングに対応する受信された符号信号を用いて、前記第
    ２メモリから検索可能な形態で、前記第２メモリにスト
    アすることを特徴とするデータ圧縮伸長方法。
  16. 【請求項１６】 最初に、複数の同様の予め定めたスト
    リングを前記第１および第２メモリの各々にストアし、
    符号信号を割り当てるステップを含むことを特徴とする
    特許請求の範囲第１５項に記載の方法。
  17. 【請求項１７】 最初にストアされた予め定めたストリ
    ングは、前記データ文字ストリーム中の個別の文字に対
    応するストリングを含むことを特徴とする特許請求の範
    囲第１６項に記載の方法。
  18. 【請求項１８】 データ文字ストリームを圧縮して圧縮
    された符号信号ストリームにし、および前記符号信号を
    用いて、前記圧縮されたストリームを伸長して前記デー
    タ文字ストリームを復元する装置において、 前記入力されたデータ文字ストリームを圧縮する装置
    と、 前記圧縮されたストリームを伸長する装置とを具備し、 前記圧縮する装置は、 前記データ文字ストリームにおけるデータ文字を探索
    し、データ文字ストリングに関連する符号信号を有する
    データ文字ストリングとの最長一致を決定する手段と、 前記データ文字ストリングをストアする第１メモリと、 最長一致が決定されたデータ文字ストリングに対応する
    符号信号を用いて、前記圧縮されたストリームを生成す
    る手段と、 拡張されたストリングを前記第１メモリにストアし、お
    よびそれに関連した符号信号を割り当てて、最長一致を
    決定するために用いるデータ文字ストリングを供給する
    手段であって、最長一致を構成するデータ文字を、前記
    データ文字ストリーム中の次の文字と連結して、拡張さ
    れたストリングを形成する手段とを具え、 前記伸長する装置は、 前記符号信号に対応するデータ文字ストリングをストア
    する第２メモリと、 前記圧縮されたストリーム中の符号信号から対応するデ
    ータ文字ストリングを取り出す手段であって、前記第２
    メモリから、符号信号を用いて、データ文字ストリング
    を検索する手段と、 取り出されたデータ文字ストリングを用いて前記データ
    文字ストリームを復元する手段と、 取り出されたストリングに応答して、拡張されたストリ
    ングを前記第２メモリにストアすることによって、前記
    符号信号に対応して、デタ文字ストリングを前記第２メ
    モリに供給する手段とを具え、取り出されたデータ文字
    ストリングを、次に取り出されたデータ文字ストリング
    の第１文字と連結させて、拡張されたストリングを形成
    し、および拡張されたストリングを、当該拡張されたス
    トリングに対応する受信された符号信号を用いて、前記
    第２メモリから検索可能な形態で、前記第２メモリにス
    トアすることを特徴とする圧縮伸長装置。
  19. 【請求項１９】 最初に、複数の同様の予め定めたスト
    リングを前記第１および第２メモリの各々にストアし、
    符号信号を割り当てる手段を含むことを特徴とする特許
    請求の範囲第１８項に記載の装置。
  20. 【請求項２０】 最初にストアされた予め定めたストリ
    ングは、前記データ文字ストリーム中の個別の文字に対
    応するストリングを含むことを特徴とする特許請求の範
    囲第１９項に記載の装置。
JP4334804A 1983-06-20 1992-12-16 データ伸長方法および装置ならびにデータ圧縮伸長方法および装置 Expired - Lifetime JP2610084B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US06/505,638 US4558302A (en) 1983-06-20 1983-06-20 High speed data compression and decompression apparatus and method
US505638 1990-04-06

Related Child Applications (1)

Application Number Title Priority Date Filing Date
JP7341868A Division JPH08237138A (ja) 1983-06-20 1995-12-27 圧縮装置および圧縮方法

Publications (2)

Publication Number Publication Date
JPH07249996A JPH07249996A (ja) 1995-09-26
JP2610084B2 true JP2610084B2 (ja) 1997-05-14

Family

ID=24011192

Family Applications (3)

Application Number Title Priority Date Filing Date
JP59125473A Granted JPS60116228A (ja) 1983-06-20 1984-06-20 ディジタル信号ストリーム圧縮方法及び圧縮装置
JP4334804A Expired - Lifetime JP2610084B2 (ja) 1983-06-20 1992-12-16 データ伸長方法および装置ならびにデータ圧縮伸長方法および装置
JP7341868A Pending JPH08237138A (ja) 1983-06-20 1995-12-27 圧縮装置および圧縮方法

Family Applications Before (1)

Application Number Title Priority Date Filing Date
JP59125473A Granted JPS60116228A (ja) 1983-06-20 1984-06-20 ディジタル信号ストリーム圧縮方法及び圧縮装置

Family Applications After (1)

Application Number Title Priority Date Filing Date
JP7341868A Pending JPH08237138A (ja) 1983-06-20 1995-12-27 圧縮装置および圧縮方法

Country Status (5)

Country Link
US (1) US4558302A (ja)
EP (1) EP0129439B1 (ja)
JP (3) JPS60116228A (ja)
CA (1) CA1223965A (ja)
DE (1) DE3476617D1 (ja)

Families Citing this family (364)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS59231683A (ja) * 1983-06-01 1984-12-26 インタ−ナシヨナル　ビジネス　マシ−ンズ　コ−ポレ−シヨン データ圧縮方法
US4814746A (en) * 1983-06-01 1989-03-21 International Business Machines Corporation Data compression method
JPS61170442A (ja) * 1985-01-23 1986-08-01 松下電器産業株式会社 超音波ドツプラ血流装置
US4758955A (en) * 1985-07-19 1988-07-19 Carson Chen Hand-held spelling checker and method for reducing redundant information in the storage of textural material
US4899128A (en) * 1985-12-11 1990-02-06 Yeda Research And Development Co., Ltd. Method and apparatus for comparing strings using hash values
US4899149A (en) * 1986-02-28 1990-02-06 Gary Kahan Method of and apparatus for decoding Huffman or variable-length coees
AU7915387A (en) * 1986-09-09 1988-04-07 Inventronic Data Systems A.B. Arrangement for data compression
US4891643A (en) * 1986-09-15 1990-01-02 International Business Machines Corporation Arithmetic coding data compression/de-compression by selectively employed, diverse arithmetic coding encoders and decoders
US4905297A (en) * 1986-09-15 1990-02-27 International Business Machines Corporation Arithmetic coding encoder and decoder system
JPH0815263B2 (ja) * 1986-12-12 1996-02-14 株式会社日立製作所 データ圧縮復元方法
JPH0815262B2 (ja) * 1986-12-12 1996-02-14 株式会社日立製作所 データ圧縮復元処理装置
ATE180932T1 (de) * 1987-09-24 1999-06-15 Sand Technology Systems Int Bitfolgekompressor geeignet für boolesche operationen
US5036457A (en) * 1987-09-24 1991-07-30 Nucleus International Corporation Bit string compressor with boolean operation processing capability
US4881075A (en) * 1987-10-15 1989-11-14 Digital Equipment Corporation Method and apparatus for adaptive data compression
US4876541A (en) * 1987-10-15 1989-10-24 Data Compression Corporation Stem for dynamically compressing and decompressing electronic data
US4847619A (en) 1987-10-19 1989-07-11 Hewlett-Packard Company Performance-based reset of data compression dictionary
US4906991A (en) * 1988-04-29 1990-03-06 Xerox Corporation Textual substitution data compression with finite length search windows
US4899147A (en) * 1988-06-03 1990-02-06 Unisys Corporation Data compression/decompression apparatus with throttle, start-up and backward read controls
US5258910A (en) * 1988-07-29 1993-11-02 Sharp Kabushiki Kaisha Text editor with memory for eliminating duplicate sentences
US5016009A (en) * 1989-01-13 1991-05-14 Stac, Inc. Data compression apparatus and method
US5532694A (en) * 1989-01-13 1996-07-02 Stac Electronics, Inc. Data compression apparatus and method using matching string searching and Huffman encoding
US5126739A (en) * 1989-01-13 1992-06-30 Stac Electronics Data compression apparatus and method
US5003307A (en) * 1989-01-13 1991-03-26 Stac, Inc. Data compression apparatus with shift register search means
US5146221A (en) * 1989-01-13 1992-09-08 Stac, Inc. Data compression apparatus and method
AU624205B2 (en) * 1989-01-23 1992-06-04 General Electric Capital Corporation Variable length string matcher
US4929946A (en) * 1989-02-09 1990-05-29 Storage Technology Corporation Adaptive data compression apparatus including run length encoding for a tape drive system
DE3921646A1 (de) * 1989-06-30 1991-01-03 Siemens Ag Verfahren zu einer codierung einer elementfolge und einrichtung zur durchfuehrung des verfahrens
US5006849A (en) * 1989-07-26 1991-04-09 Astro, Inc. Apparatus and method for effecting data compression
US4971407A (en) * 1989-08-09 1990-11-20 Unisys Corp. Two stage run and string data compressor providing doubly compressed output
US4988998A (en) * 1989-09-05 1991-01-29 Storage Technology Corporation Data compression system for successively applying at least two data compression methods to an input data stream
US5010344A (en) * 1989-12-28 1991-04-23 International Business Machines Corporation Method of decoding compressed data
US5010345A (en) * 1989-12-28 1991-04-23 International Business Machines Corporation Data compression method
US5001478A (en) * 1989-12-28 1991-03-19 International Business Machines Corporation Method of encoding compressed data
US5184126A (en) 1989-12-28 1993-02-02 International Business Machines Corporation Method of decompressing compressed data
US5254990A (en) * 1990-02-26 1993-10-19 Fujitsu Limited Method and apparatus for compression and decompression of data
EP0871295B1 (en) * 1990-02-26 2004-03-24 Fujitsu Limited Method and apparatus for compression and decompression of data
FR2660088B1 (fr) * 1990-03-26 1992-06-26 Arditti David Dispositif de condensation de donnees numeriques.
US5479654A (en) * 1990-04-26 1995-12-26 Squibb Data Systems, Inc. Apparatus and method for reconstructing a file from a difference signature and an original file
US6816872B1 (en) 1990-04-26 2004-11-09 Timespring Software Corporation Apparatus and method for reconstructing a file from a difference signature and an original file
US5410671A (en) * 1990-05-01 1995-04-25 Cyrix Corporation Data compression/decompression processor
WO1991019248A1 (en) * 1990-05-30 1991-12-12 Adaptive Solutions, Inc. Neural network using virtual-zero
US5497488A (en) * 1990-06-12 1996-03-05 Hitachi, Ltd. System for parallel string search with a function-directed parallel collation of a first partition of each string followed by matching of second partitions
US5023610A (en) * 1990-06-13 1991-06-11 Cordell Manufacturing, Inc. Data compression method using textual substitution
US5049881A (en) * 1990-06-18 1991-09-17 Intersecting Concepts, Inc. Apparatus and method for very high data rate-compression incorporating lossless data compression and expansion utilizing a hashing technique
DE69128053T2 (de) * 1990-08-06 1998-02-26 Fujitsu Ltd., Kawasaki, Kanagawa Wörterbuch-Suchsystem
JP3012679B2 (ja) * 1990-10-19 2000-02-28 富士通株式会社 データ圧縮方法
EP0688104A2 (en) * 1990-08-13 1995-12-20 Fujitsu Limited Data compression method and apparatus
JP3012677B2 (ja) * 1990-10-19 2000-02-28 富士通株式会社 Ｚｌ符号化方法
JP3012678B2 (ja) * 1990-10-19 2000-02-28 富士通株式会社 データ圧縮方法
US5051745A (en) * 1990-08-21 1991-09-24 Pkware, Inc. String searcher, and compressor using same
US5087913A (en) * 1990-08-27 1992-02-11 Unisys Corporation Short-record data compression and decompression system
US5151697A (en) * 1990-10-15 1992-09-29 Board Of Regents Of The University Of Washington Data structure management tagging system
US5142282A (en) * 1990-11-07 1992-08-25 Hewlett-Packard Company Data compression dictionary access minimization
US5136291A (en) 1990-11-30 1992-08-04 Unisys Corporation Transmitting binary data files using electronic mail
US5150430A (en) * 1991-03-15 1992-09-22 The Board Of Trustees Of The Leland Stanford Junior University Lossless data compression circuit and method
CA2065578C (en) * 1991-04-22 1999-02-23 David W. Carr Packet-based data compression method
US5369773A (en) * 1991-04-26 1994-11-29 Adaptive Solutions, Inc. Neural network using virtual-zero
US5179378A (en) * 1991-07-30 1993-01-12 University Of South Florida Method and apparatus for the compression and decompression of data using Lempel-Ziv based techniques
US5159336A (en) * 1991-08-13 1992-10-27 Iomega Corporation Tape controller with data compression and error correction sharing a common buffer
US5140321A (en) * 1991-09-04 1992-08-18 Prime Computer, Inc. Data compression/decompression method and apparatus
US5455943A (en) * 1992-10-08 1995-10-03 Salient Software, Inc. Method and apparatus for finding longest and closest matching string in history buffer prior to current string
US5426779A (en) * 1991-09-13 1995-06-20 Salient Software, Inc. Method and apparatus for locating longest prior target string matching current string in buffer
US5175543A (en) * 1991-09-25 1992-12-29 Hewlett-Packard Company Dictionary reset performance enhancement for data compression applications
US5243341A (en) * 1992-06-01 1993-09-07 Hewlett Packard Company Lempel-Ziv compression scheme with enhanced adapation
US5355493A (en) * 1991-11-20 1994-10-11 International Business Machines Corporation System for encoding units of entity/relationship data to include prefixes with codes for length, action, and unit identifier
US5726824A (en) * 1991-12-10 1998-03-10 Exabyte Corporation Head positioning in a multi-track magnetic tape recorder/player
CA2077271C (en) * 1991-12-13 1998-07-28 David J. Craft Method and apparatus for compressing data
US5396228A (en) * 1992-01-16 1995-03-07 Mobile Telecommunications Technologies Methods and apparatus for compressing and decompressing paging data
US5229768A (en) * 1992-01-29 1993-07-20 Traveling Software, Inc. Adaptive data compression system
US5406278A (en) * 1992-02-28 1995-04-11 Intersecting Concepts, Inc. Method and apparatus for data compression having an improved matching algorithm which utilizes a parallel hashing technique
US5371499A (en) * 1992-02-28 1994-12-06 Intersecting Concepts, Inc. Data compression using hashing
US5379036A (en) * 1992-04-01 1995-01-03 Storer; James A. Method and apparatus for data compression
US5239298A (en) * 1992-04-17 1993-08-24 Bell Communications Research, Inc. Data compression
US5339076A (en) * 1992-04-27 1994-08-16 Integrated Information Technology Data compression using content addressable memory
US5353024A (en) * 1992-05-01 1994-10-04 Intersecting Concepts, Inc. Method for data compression having an improved encoding algorithm which utilizes a token stacking technique
US5408542A (en) * 1992-05-12 1995-04-18 Apple Computer, Inc. Method and apparatus for real-time lossless compression and decompression of image data
US5664029A (en) * 1992-05-13 1997-09-02 Apple Computer, Inc. Method of disregarding changes in data in a location of a data structure based upon changes in data in nearby locations
US5485526A (en) * 1992-06-02 1996-01-16 Hewlett-Packard Corporation Memory circuit for lossless data compression/decompression dictionary storage
US5818873A (en) * 1992-08-03 1998-10-06 Advanced Hardware Architectures, Inc. Single clock cycle data compressor/decompressor with a string reversal mechanism
US5469161A (en) * 1992-08-13 1995-11-21 International Business Machines Corporation Algorithm for the implementation of Ziv-Lempel data compression using content addressable memory
US5406279A (en) * 1992-09-02 1995-04-11 Cirrus Logic, Inc. General purpose, hash-based technique for single-pass lossless data compression
US5479587A (en) * 1992-09-03 1995-12-26 Hewlett-Packard Company Page printer having adaptive data compression for memory minimization
US5434776A (en) * 1992-11-13 1995-07-18 Microsoft Corporation Method and system for creating multi-lingual computer programs by dynamically loading messages
US5440753A (en) * 1992-11-13 1995-08-08 Motorola, Inc. Variable length string matcher
US5323155A (en) * 1992-12-04 1994-06-21 International Business Machines Corporation Semi-static data compression/expansion method
US5467087A (en) * 1992-12-18 1995-11-14 Apple Computer, Inc. High speed lossless data compression system
US5455576A (en) 1992-12-23 1995-10-03 Hewlett Packard Corporation Apparatus and methods for Lempel Ziv data compression with improved management of multiple dictionaries in content addressable memory
US5389922A (en) * 1993-04-13 1995-02-14 Hewlett-Packard Company Compression using small dictionaries with applications to network packets
US5640551A (en) * 1993-04-14 1997-06-17 Apple Computer, Inc. Efficient high speed trie search process
US6357047B1 (en) 1997-06-30 2002-03-12 Avid Technology, Inc. Media pipeline with multichannel video processing and playback
US5351046A (en) * 1993-05-28 1994-09-27 Adcox Thomas A Method and system for compacting binary coded decimal data
JP3171510B2 (ja) 1993-06-01 2001-05-28 ヒューレット・パッカード・カンパニー 辞書ベースのメモリ内のデータを圧縮および圧縮解除する方法
US5463389A (en) * 1993-09-24 1995-10-31 Motorola, Inc. Data compression method and device utilizing children arrays
US5406281A (en) * 1993-10-12 1995-04-11 Codex Corporation Encoder/decoder and method for efficient string handling in data compression
US5384568A (en) * 1993-12-02 1995-01-24 Bell Communications Research, Inc. Data compression
US5563595A (en) * 1993-12-23 1996-10-08 International Business Machines Corporation Method and apparatus for compressing data
WO1995018996A2 (en) * 1993-12-30 1995-07-13 Connectix Corporation Lossless data compression system and method
JP3522331B2 (ja) * 1994-04-22 2004-04-26 株式会社セタ データ圧縮方法
US5659635A (en) * 1994-04-26 1997-08-19 Konica Corporation Image processing apparatus for compressing and decompressing image data
US5502439A (en) * 1994-05-16 1996-03-26 The United States Of America As Represented By The United States Department Of Energy Method for compression of binary data
US5635931A (en) * 1994-06-02 1997-06-03 International Business Machines Corporation System and method for compressing data information
AUPM607994A0 (en) * 1994-06-03 1994-06-30 Masters, John A data conversion technique
US5585793A (en) * 1994-06-10 1996-12-17 Digital Equipment Corporation Order preserving data translation
US5532693A (en) * 1994-06-13 1996-07-02 Advanced Hardware Architectures Adaptive data compression system with systolic string matching logic
US5627533A (en) * 1994-08-05 1997-05-06 Hayes Microcomputer Products, Inc. Adjusting encoding table size and memory allocation for data compression in response to input data
US5617517A (en) * 1994-09-20 1997-04-01 Seiko Epson Corporation Two-dimensional method and system for compressing bi-level images
US6460036B1 (en) 1994-11-29 2002-10-01 Pinpoint Incorporated System and method for providing customized electronic newspapers and target advertisements
US5758257A (en) 1994-11-29 1998-05-26 Herz; Frederick System and method for scheduling broadcast of and access to video programs and other data using customer profiles
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
US5642112A (en) * 1994-12-29 1997-06-24 Unisys Corporation Method and apparatus for performing LZW data compression utilizing an associative memory
US5805911A (en) * 1995-02-01 1998-09-08 Microsoft Corporation Word prediction system
US5771010A (en) * 1995-03-22 1998-06-23 Ibm Corporation Apparatus for compressing data using a Lempel-Ziv-type algorithm
US5686912A (en) * 1995-05-08 1997-11-11 Hewlett-Packard Company Data compression method and apparatus with optimized transitions between compressed and uncompressed modes
US5526363A (en) * 1995-05-16 1996-06-11 Telco Systems, Inc. Multicontext compression system with shared data structures
DE69624755T2 (de) * 1995-05-22 2003-04-24 Matsushita Electric Industrial Co., Ltd. Informationssuchgerät für das Suchen von Text, um Zeichenfolgen wiederaufzufinden, die mit einem Schlüsselwort übereinstimmen
US5636369A (en) * 1995-05-26 1997-06-03 Datron/Transco, Inc. Fast pattern-detection machine and method
US5729737A (en) * 1995-07-13 1998-03-17 Armour; William M. Selective data compression system
US5825830A (en) * 1995-08-17 1998-10-20 Kopf; David A. Method and apparatus for the compression of audio, video or other data
US5689255A (en) * 1995-08-22 1997-11-18 Hewlett-Packard Company Method and apparatus for compressing and decompressing image data
JP3273119B2 (ja) 1995-09-29 2002-04-08 京セラ株式会社 データ圧縮・伸長装置
US5778255A (en) * 1995-10-10 1998-07-07 International Business Machines Corporation Method and system in a data processing system for decompressing multiple compressed bytes in a single machine cycle
US5805086A (en) * 1995-10-10 1998-09-08 International Business Machines Corporation Method and system for compressing data that facilitates high-speed data decompression
US5710719A (en) * 1995-10-19 1998-01-20 America Online, Inc. Apparatus and method for 2-dimensional data compression
US5838963A (en) * 1995-10-25 1998-11-17 Microsoft Corporation Apparatus and method for compressing a data file based on a dictionary file which matches segment lengths
JP3566441B2 (ja) * 1996-01-30 2004-09-15 シャープ株式会社 テキスト圧縮用辞書作成装置
US5892506A (en) * 1996-03-18 1999-04-06 Discreet Logic, Inc. Multitrack architecture for computer-based editing of multimedia sequences
CA2173677C (en) * 1996-04-09 2001-02-20 Benoit Sevigny Processing image data
US5818542A (en) * 1996-04-10 1998-10-06 Discreet Logic, Inc. Processing image data
US5839100A (en) * 1996-04-22 1998-11-17 Wegener; Albert William Lossless and loss-limited compression of sampled data signals
US20030195848A1 (en) 1996-06-05 2003-10-16 David Felger Method of billing a purchase made over a computer network
US7555458B1 (en) 1996-06-05 2009-06-30 Fraud Control System.Com Corporation Method of billing a purchase made over a computer network
US8229844B2 (en) 1996-06-05 2012-07-24 Fraud Control Systems.Com Corporation Method of billing a purchase made over a computer network
US5703581A (en) * 1996-06-14 1997-12-30 Lucent Technologies Inc. Method and apparatus for data compression and decompression
US5654703A (en) * 1996-06-17 1997-08-05 Hewlett-Packard Company Parallel data compression and decompression
US5831558A (en) * 1996-06-17 1998-11-03 Digital Equipment Corporation Method of compressing and decompressing data in a computer system by encoding data using a data dictionary
RU2190295C2 (ru) * 1996-07-24 2002-09-27 Юнисиз Корпорейшн Система уплотнения и разуплотнения данных с непосредственным обновлением каталога, которое чередуют с поиском строк
US5861827A (en) * 1996-07-24 1999-01-19 Unisys Corporation Data compression and decompression system with immediate dictionary updating interleaved with string search
US5883670A (en) * 1996-08-02 1999-03-16 Avid Technology, Inc. Motion video processing circuit for capture playback and manipulation of digital motion video information on a computer
US5951623A (en) 1996-08-06 1999-09-14 Reynar; Jeffrey C. Lempel- Ziv data compression technique utilizing a dictionary pre-filled with frequent letter combinations, words and/or phrases
US5760716A (en) * 1996-08-21 1998-06-02 Autodesk, Inc. Vector data compression
US6272235B1 (en) * 1997-03-03 2001-08-07 Bacus Research Laboratories, Inc. Method and apparatus for creating a virtual microscope slide
US6404906B2 (en) * 1997-03-03 2002-06-11 Bacus Research Laboratories,Inc. Method and apparatus for acquiring and reconstructing magnified specimen images from a computer-controlled microscope
US5764994A (en) * 1996-09-16 1998-06-09 International Business Machines Corporation Method and system for compressing compiled microcode to be executed within a data processing system
US6038665A (en) * 1996-12-03 2000-03-14 Fairbanks Systems Group System and method for backing up computer files over a wide area computer network
US5794254A (en) * 1996-12-03 1998-08-11 Fairbanks Systems Group Incremental computer file backup using a two-step comparison of first two characters in the block and a signature with pre-stored character and signature sets
JP3540109B2 (ja) * 1996-12-24 2004-07-07 富士通株式会社 データ圧縮方法及び装置
US6009192A (en) * 1996-12-19 1999-12-28 Xerox Corporation Color correction of a compressed image
US6385341B1 (en) * 1997-04-17 2002-05-07 Microsoft Corporation Technique for decoding variable length data codes
US5818368A (en) * 1997-04-18 1998-10-06 Premier Research, Llc Method and apparatus for lossless digital data compression
US6105083A (en) * 1997-06-20 2000-08-15 Avid Technology, Inc. Apparatus and method for controlling transfer of data between and processing of data by interconnected data processing elements
US6366988B1 (en) * 1997-07-18 2002-04-02 Storactive, Inc. Systems and methods for electronic data storage management
US6163625A (en) * 1997-10-21 2000-12-19 Canon Kabushiki Kaisha Hybrid image compressor
US6377965B1 (en) 1997-11-07 2002-04-23 Microsoft Corporation Automatic word completion system for partially entered data
US5896321A (en) * 1997-11-14 1999-04-20 Microsoft Corporation Text completion system for a miniature computer
US5955976A (en) * 1997-12-02 1999-09-21 Hughes Electronics Corporation Data compression for use with a communications channel
JP3730385B2 (ja) 1997-12-05 2006-01-05 株式会社東芝 デ−タ圧縮装置
JP3421700B2 (ja) 1998-01-22 2003-06-30 富士通株式会社 データ圧縮装置及び復元装置並びにその方法
US6138254A (en) * 1998-01-22 2000-10-24 Micron Technology, Inc. Method and apparatus for redundant location addressing using data compression
US6075470A (en) * 1998-02-26 2000-06-13 Research In Motion Limited Block-wise adaptive statistical data compressor
US6212301B1 (en) 1998-06-25 2001-04-03 Accusoft Corporation Systems and methods for digital image compression
US6301394B1 (en) * 1998-09-25 2001-10-09 Anzus, Inc. Method and apparatus for compressing data
US7058597B1 (en) 1998-12-04 2006-06-06 Digital River, Inc. Apparatus and method for adaptive fraud screening for electronic commerce transactions
US7617124B1 (en) * 1998-12-04 2009-11-10 Digital River, Inc. Apparatus and method for secure downloading of files
US20030195974A1 (en) 1998-12-04 2003-10-16 Ronning Joel A. Apparatus and method for scheduling of search for updates or downloads of a file
US6624761B2 (en) 1998-12-11 2003-09-23 Realtime Data, Llc Content independent data compression method and system
US6377930B1 (en) 1998-12-14 2002-04-23 Microsoft Corporation Variable to variable length entropy encoding
US6404931B1 (en) 1998-12-14 2002-06-11 Microsoft Corporation Code book construction for variable to variable length entropy encoding
US6263363B1 (en) 1999-01-28 2001-07-17 Skydesk, Inc. System and method for creating an internet-accessible working replica of a home computer on a host server controllable by a user operating a remote access client computer
US7538694B2 (en) 1999-01-29 2009-05-26 Mossman Holdings Llc Network device with improved storage density and access speed using compression techniques
US6885319B2 (en) * 1999-01-29 2005-04-26 Quickshift, Inc. System and method for generating optimally compressed data from a plurality of data compression/decompression engines implementing different data compression algorithms
US6603414B1 (en) * 1999-01-29 2003-08-05 Compaq Computer Corporation Method for digital compression of characters
US6819271B2 (en) 1999-01-29 2004-11-16 Quickshift, Inc. Parallel compression and decompression system and method having multiple parallel compression and decompression engines
US6289130B1 (en) 1999-02-02 2001-09-11 3Com Corporation Method for real-time lossless data compression of computer data
US6920250B1 (en) 1999-03-04 2005-07-19 Xerox Corporation Additive model for efficient representation of digital documents
US6601104B1 (en) 1999-03-11 2003-07-29 Realtime Data Llc System and methods for accelerated data storage and retrieval
US6611213B1 (en) 1999-03-22 2003-08-26 Lucent Technologies Inc. Method and apparatus for data compression using fingerprinting
US6966002B1 (en) 1999-04-30 2005-11-15 Trymedia Systems, Inc. Methods and apparatus for secure distribution of software
US7360252B1 (en) 1999-04-30 2008-04-15 Macrovision Corporation Method and apparatus for secure distribution of software
US20060005021A1 (en) * 1999-06-09 2006-01-05 Andres Torrubia-Saez Methods and apparatus for secure distribution of software
US6169499B1 (en) * 1999-06-19 2001-01-02 Unisys Corporation LZW data compression/decompression apparatus and method with embedded run-length encoding/decoding
AU6017400A (en) * 1999-07-16 2001-02-05 Vertex Software Co., Amount-of-data reducing method and reduced amount-of-data generating system
US6320523B1 (en) * 1999-07-30 2001-11-20 Unisys Corporation Method and apparatus for reducing the time required for compressing data
US6188333B1 (en) * 1999-08-12 2001-02-13 Unisys Corporation LZW data compression apparatus and method using look-ahead mathematical run processing
US7630986B1 (en) 1999-10-27 2009-12-08 Pinpoint, Incorporated Secure data interchange
US6919967B1 (en) 1999-11-18 2005-07-19 Hewlett-Packard Development Company, L.P. Printing performance enhancements for variable data publishing
WO2001050612A1 (en) 2000-01-05 2001-07-12 Realnetworks, Inc. Systems and methods for multiple-file data compression
US20010047473A1 (en) 2000-02-03 2001-11-29 Realtime Data, Llc Systems and methods for computer initialization
US20070271191A1 (en) * 2000-03-09 2007-11-22 Andres Torrubia-Saez Method and apparatus for secure distribution of software
FR2806227B1 (fr) * 2000-03-09 2003-09-05 Auteuil Participation Et Conse Procede pour le codage d'images
US6236341B1 (en) 2000-03-16 2001-05-22 Lucent Technologies Inc. Method and apparatus for data compression of network packets employing per-packet hash tables
US6388584B1 (en) 2000-03-16 2002-05-14 Lucent Technologies Inc. Method and apparatus for data compression of network packets
GB0007974D0 (en) * 2000-04-01 2000-05-17 Discreet Logic Inc Processing image data
US6522784B1 (en) 2000-04-11 2003-02-18 International Business Machines Corporation Enhanced compression of gray-level images
US6307488B1 (en) 2000-05-04 2001-10-23 Unisys Corporation LZW data compression and decompression apparatus and method using grouped data characters to reduce dictionary accesses
US6983074B1 (en) 2000-06-14 2006-01-03 Adobe Systems Incorporated Data compression system and technique
CN1446404A (zh) 2000-08-15 2003-10-01 西加特技术有限责任公司 操作码的双模数据压缩
US6348881B1 (en) * 2000-08-29 2002-02-19 Philips Electronics No. America Corp. Efficient hardware implementation of a compression algorithm
US9143546B2 (en) 2000-10-03 2015-09-22 Realtime Data Llc System and method for data feed acceleration and encryption
US8692695B2 (en) 2000-10-03 2014-04-08 Realtime Data, Llc Methods for encoding and decoding data
US6359548B1 (en) 2000-10-16 2002-03-19 Unisys Corporation Data compression and decompression method and apparatus with embedded filtering of infrequently encountered strings
US6792423B1 (en) * 2000-11-28 2004-09-14 International Business Machines Corporation Hybrid longest prefix match and fixed match searches
US6829289B1 (en) * 2000-12-05 2004-12-07 Gossett And Gunter, Inc. Application of a pseudo-randomly shuffled hadamard function in a wireless CDMA system
US8385470B2 (en) * 2000-12-05 2013-02-26 Google Inc. Coding a signal with a shuffled-Hadamard function
US8374218B2 (en) 2000-12-05 2013-02-12 Google Inc. Combining signals with a shuffled-hadamard function
US6883087B1 (en) 2000-12-15 2005-04-19 Palm, Inc. Processing of binary data for compression
SE0004736D0 (sv) * 2000-12-20 2000-12-20 Ericsson Telefon Ab L M Mapping system and method
US7386046B2 (en) 2001-02-13 2008-06-10 Realtime Data Llc Bandwidth sensitive data compression and decompression
US6606040B2 (en) * 2001-02-13 2003-08-12 Mosaid Technologies, Inc. Method and apparatus for adaptive data compression
US20020116672A1 (en) * 2001-02-19 2002-08-22 Ando Electric Co., Ltd. Pattern data transmission device and pattern data transmission method
US6392568B1 (en) * 2001-03-07 2002-05-21 Unisys Corporation Data compression and decompression method and apparatus with embedded filtering of dynamically variable infrequently encountered strings
JP3990115B2 (ja) * 2001-03-12 2007-10-10 株式会社東芝 サーバ側プロキシ装置及びプログラム
US6426711B1 (en) * 2001-05-14 2002-07-30 Unisys Corporation Character table implemented data compression method and apparatus
JP3913004B2 (ja) 2001-05-28 2007-05-09 キヤノン株式会社 データ圧縮方法及び装置及びコンピュータプログラム及び記憶媒体
US7164369B2 (en) 2001-06-19 2007-01-16 Sharp Laboratories Of America, Inc. System for improving storage efficiency of digital files
US6400286B1 (en) 2001-06-20 2002-06-04 Unisys Corporation Data compression method and apparatus implemented with limited length character tables
US7382878B2 (en) * 2001-06-22 2008-06-03 Uponus Technologies, Llc System and method for data encryption
US20030018647A1 (en) * 2001-06-29 2003-01-23 Jan Bialkowski System and method for data compression using a hybrid coding scheme
US6707400B2 (en) * 2001-08-02 2004-03-16 Telefonaktiebolaget Lm Ericsson (Publ) Method and apparatus for fast longest match search
US20030088537A1 (en) * 2001-08-08 2003-05-08 Nec Eluminant Technologies, Inc. High speed data compression and decompression apparatus and method
US7062088B1 (en) 2001-08-28 2006-06-13 Adobe Systems Incorporated Variable lossy compression
WO2003021970A1 (en) * 2001-09-04 2003-03-13 Faroudja Cognition Systems, Inc. Low bandwidth video compression
US6650261B2 (en) 2001-09-06 2003-11-18 Xerox Corporation Sliding window compression method utilizing defined match locations
US7185041B1 (en) 2001-10-05 2007-02-27 Unisys Corporation Circuit and method for high-speed execution of modulo division
US6466144B1 (en) * 2001-11-30 2002-10-15 Unisys Corporation Data decompressor for use with a data compressor implemented with limited length character tables and compact string codes
WO2003062749A2 (en) 2002-01-23 2003-07-31 M-Spatial Limited Schematic generation
US7085271B2 (en) * 2002-03-14 2006-08-01 Hewlett-Packard Development Company, L.P. Method and system for performing flow based hash transformation to generate hash pointers for a network device
US6628211B1 (en) 2002-03-19 2003-09-30 Unisys Corporation Prefix table implemented data compression method and apparatus
US7126948B2 (en) * 2002-03-21 2006-10-24 Hewlett-Packard Development Company, L.P. Method and system for performing a hash transformation to generate a hash pointer for an address input by using rotation
LV13012B (en) * 2002-03-22 2003-06-20 Datoru Drosibas Tehnologijas S Method and apparatus for lossless compression and decompression of data
US7039106B2 (en) * 2002-03-25 2006-05-02 Intel Corporation Processing digital data prior to compression
US6501395B1 (en) 2002-04-10 2002-12-31 Hewlett-Packard Company System, method and computer readable medium for compressing a data sequence
US6624762B1 (en) 2002-04-11 2003-09-23 Unisys Corporation Hardware-based, LZW data compression co-processor
US6650259B1 (en) * 2002-05-06 2003-11-18 Unisys Corporation Character table implemented data decompression method and apparatus
US7154848B2 (en) * 2002-05-29 2006-12-26 General Dynamics Corporation Methods and apparatus for generating a multiplexed communication signal
US7280496B2 (en) * 2002-08-02 2007-10-09 General Dynamics Corporation Methods and apparatus for coupling a satellite to an earth terminal
US7280497B2 (en) * 2002-08-02 2007-10-09 General Dynamics Corporation Methods and apparatus for coupling an earth terminal to a satellite
ATE543178T1 (de) 2002-09-04 2012-02-15 Microsoft Corp Entropische kodierung mittels anpassung des kodierungsmodus zwischen niveau- und lauflängenniveau-modus
US6714145B1 (en) 2002-09-26 2004-03-30 Richard Marques Method and apparatus for integer-based encoding and decoding of bits
US6670897B1 (en) 2002-10-03 2003-12-30 Motorola, Inc. Compression/decompression techniques based on tokens and Huffman coding
US6819272B2 (en) * 2002-11-06 2004-11-16 Hewlett-Packard Development Company, L.P. System, method and computer readable medium for compressing a data sequence for partial decompressing
US7609722B2 (en) * 2003-02-14 2009-10-27 Atheros Communications, Inc. Method and apparatus for transmitting and receiving compressed frame of data over a wireless channel
GB2400287A (en) * 2003-04-02 2004-10-06 Autodesk Canada Inc Three-Dimensional Image Compositing
GB2400289A (en) * 2003-04-04 2004-10-06 Autodesk Canada Inc Selecting functions in a Context-Sensitive Menu
US7433519B2 (en) * 2003-04-04 2008-10-07 Avid Technology, Inc. Bitstream format for compressed image data
US7403561B2 (en) * 2003-04-04 2008-07-22 Avid Technology, Inc. Fixed bit rate, intraframe compression and decompression of video
GB2400290A (en) * 2003-04-04 2004-10-06 Autodesk Canada Inc Multidimensional image data processing in a hierarchical dat structure
US8639760B2 (en) * 2003-06-10 2014-01-28 Hewlett-Packard Development Company, L.P. Hard imaging devices, hard imaging systems, articles of manufacture, hard imaging device electronic mail processing methods
US6879270B1 (en) 2003-08-20 2005-04-12 Hewlett-Packard Development Company, L.P. Data compression in multiprocessor computers
US7009533B1 (en) 2004-02-13 2006-03-07 Samplify Systems Llc Adaptive compression and decompression of bandlimited signals
US7394410B1 (en) 2004-02-13 2008-07-01 Samplify Systems, Inc. Enhanced data converters using compression and decompression
US7071852B1 (en) 2004-02-13 2006-07-04 Samplify Systems Llc Enhanced test and measurement instruments using compression and decompression
US7088276B1 (en) 2004-02-13 2006-08-08 Samplify Systems Llc Enhanced data converters using compression and decompression
US7079051B2 (en) * 2004-03-18 2006-07-18 James Andrew Storer In-place differential compression
US7565343B2 (en) * 2004-03-31 2009-07-21 Ipt Corporation Search apparatus and search management method for fixed-length data
US20050256722A1 (en) * 2004-05-14 2005-11-17 Clark Adam L System and method for lossless audio encoding and decoding
US7664173B2 (en) * 2004-06-07 2010-02-16 Nahava Inc. Method and apparatus for cached adaptive transforms for compressing data streams, computing similarity, and recognizing patterns
GB0416481D0 (en) 2004-07-23 2004-08-25 Hewlett Packard Development Co Method, apparatus and system for data block rearrangement for LZ data compression
US7256715B1 (en) * 2005-01-07 2007-08-14 Altera Corporation Data compression using dummy codes
US6970110B1 (en) 2005-01-08 2005-11-29 Collins Dennis G Probability centrifuge algorithm with minimum laterally adiabatically-reduced Fisher information calculation
US20060200481A1 (en) * 2005-03-04 2006-09-07 Khalid Goyan Method and system for data optimization and protection in DSP firmware
US7167115B1 (en) 2005-08-26 2007-01-23 American Megatrends, Inc. Method, apparatus, and computer-readable medium for data compression and decompression utilizing multiple dictionaries
US8489562B1 (en) 2007-11-30 2013-07-16 Silver Peak Systems, Inc. Deferred data storage
US8929402B1 (en) * 2005-09-29 2015-01-06 Silver Peak Systems, Inc. Systems and methods for compressing packet data by predicting subsequent data
US8811431B2 (en) 2008-11-20 2014-08-19 Silver Peak Systems, Inc. Systems and methods for compressing packet data
US7164370B1 (en) 2005-10-06 2007-01-16 Analog Devices, Inc. System and method for decoding data compressed in accordance with dictionary-based compression schemes
US8674855B2 (en) * 2006-01-13 2014-03-18 Essex Pa, L.L.C. Identification of text
US7365658B2 (en) * 2006-02-28 2008-04-29 The Board Of Trustees Of The University Of Arkansas Method and apparatus for lossless run-length data encoding
DE102006011022A1 (de) * 2006-03-09 2007-10-25 Netviewer Gmbh Zweidimensionales adaptives Bildkompressionsverfahren
KR101583268B1 (ko) 2006-03-27 2016-01-08 닐슨 미디어 리서치 인코퍼레이티드 무선통신장치에 표현되는 미디어 컨텐츠의 미터링 방법 및 시스템
US7586424B2 (en) * 2006-06-05 2009-09-08 Donald Martin Monro Data coding using an exponent and a residual
US7770091B2 (en) * 2006-06-19 2010-08-03 Monro Donald M Data compression for use in communication systems
US20080017227A1 (en) * 2006-07-19 2008-01-24 Ward Barry D Walking aid apparatus
US8755381B2 (en) 2006-08-02 2014-06-17 Silver Peak Systems, Inc. Data matching using flow based packet data storage
US8885632B2 (en) 2006-08-02 2014-11-11 Silver Peak Systems, Inc. Communications scheduler
DE102006047465A1 (de) * 2006-10-07 2008-04-10 Deutsche Telekom Ag Verfahren und Vorrichtung zur Kompression und Dekompression digitaler Daten auf elektronischem Wege unter Verwendung einer Kontextgrammatik
US8453241B2 (en) * 2006-12-18 2013-05-28 Illinois Institute Of Technology Method for securing streaming multimedia network transmissions
US20090070877A1 (en) * 2006-12-18 2009-03-12 Carol Davids Method for securing streaming multimedia network transmissions
US7834784B1 (en) 2007-01-18 2010-11-16 Cisco Technology, Inc. Data redundancy elimination mechanism including fast lookup of data patterns exhibiting spatial locality
US7814284B1 (en) 2007-01-18 2010-10-12 Cisco Technology, Inc. Redundancy elimination by aggregation of multiple chunks
US7439887B2 (en) * 2007-02-13 2008-10-21 Seiko Epson Corporation Method and apparatus for GIF decompression using fixed-size codeword table
US20080263433A1 (en) * 2007-04-14 2008-10-23 Aaron Eppolito Multiple version merge for media production
US8751022B2 (en) * 2007-04-14 2014-06-10 Apple Inc. Multi-take compositing of digital media assets
US20080256136A1 (en) * 2007-04-14 2008-10-16 Jerremy Holland Techniques and tools for managing attributes of media content
US20080256448A1 (en) * 2007-04-14 2008-10-16 Nikhil Mahesh Bhatt Multi-Frame Video Display Method and Apparatus
US20090055395A1 (en) * 2007-08-24 2009-02-26 Texas Instruments Incorporated Method and Apparatus for XML Data Processing
US8458460B2 (en) * 2007-09-27 2013-06-04 Intel Corporation Digest generation from instruction op-codes
KR100945247B1 (ko) * 2007-10-04 2010-03-03 한국전자통신연구원 가상 환경을 이용한 비실행 파일 내의 악성 코드 분석 방법및 장치
US8514927B2 (en) * 2007-11-20 2013-08-20 Texas Instruments Incorporated Compression code for transferring rate matched data between devices
US8307115B1 (en) 2007-11-30 2012-11-06 Silver Peak Systems, Inc. Network memory mirroring
CN100595596C (zh) * 2007-12-12 2010-03-24 北京四方继保自动化股份有限公司 电网广域测量系统(wams)中动态数据压缩存储方法
US20090198716A1 (en) * 2008-02-04 2009-08-06 Shawn Allen Howarth Method of building a compression dictionary during data populating operations processing
US8503991B2 (en) 2008-04-03 2013-08-06 The Nielsen Company (Us), Llc Methods and apparatus to monitor mobile devices
US8179974B2 (en) 2008-05-02 2012-05-15 Microsoft Corporation Multi-level representation of reordered transform coefficients
US9717021B2 (en) 2008-07-03 2017-07-25 Silver Peak Systems, Inc. Virtual network overlay
US8743683B1 (en) 2008-07-03 2014-06-03 Silver Peak Systems, Inc. Quality of service using multiple flows
US10164861B2 (en) 2015-12-28 2018-12-25 Silver Peak Systems, Inc. Dynamic monitoring and visualization for network health characteristics
US10805840B2 (en) 2008-07-03 2020-10-13 Silver Peak Systems, Inc. Data transmission via a virtual wide area network overlay
US7864086B2 (en) 2008-10-06 2011-01-04 Donald Martin Monro Mode switched adaptive combinatorial coding/decoding for electrical computers and digital data processing systems
US7791513B2 (en) * 2008-10-06 2010-09-07 Donald Martin Monro Adaptive combinatorial coding/decoding with specified occurrences for electrical computers and digital data processing systems
US7786903B2 (en) 2008-10-06 2010-08-31 Donald Martin Monro Combinatorial coding/decoding with specified occurrences for electrical computers and digital data processing systems
US7786907B2 (en) 2008-10-06 2010-08-31 Donald Martin Monro Combinatorial coding/decoding with specified occurrences for electrical computers and digital data processing systems
US7764202B2 (en) * 2008-11-26 2010-07-27 Red Hat, Inc. Lossless data compression with separated index values and literal values in output stream
US7750826B2 (en) * 2008-11-26 2010-07-06 Red Hat, Inc. Data structure management for lossless data compression
US7864085B2 (en) * 2009-02-05 2011-01-04 Lsi Corporation Data compression method and apparatus
WO2010097942A1 (ja) * 2009-02-27 2010-09-02 富士通株式会社 電子署名プログラム、電子署名装置、および電子署名方法
US8179291B2 (en) * 2009-05-04 2012-05-15 International Business Machines Corporation Method and system for compression of logical data objects for storage
US7944375B2 (en) * 2009-06-02 2011-05-17 International Business Machines Corporation Wear reduction methods by using compression/decompression techniques with fast random access
CN101572552B (zh) * 2009-06-11 2012-07-18 哈尔滨工业大学 基于内容可寻址存储器的高速无损数据压缩系统
US7982636B2 (en) * 2009-08-20 2011-07-19 International Business Machines Corporation Data compression using a nested hierachy of fixed phrase length static and dynamic dictionaries
DE102009028743B4 (de) 2009-08-20 2011-06-09 Robert Bosch Gmbh Verfahren und Steuergerät zur Entzerrung eines Kamerabildes
RU2473960C2 (ru) * 2010-05-26 2013-01-27 Учреждение Российской академии наук Институт проблем управления им. В.А. Трапезникова РАН Способ нахождения максимальных повторяющихся участков последовательности символов конечного алфавита и способ вычисления вспомогательного массива
WO2012090564A1 (ja) * 2010-12-28 2012-07-05 インターナショナル・ビジネス・マシーンズ・コーポレーション データ要素列を処理する装置及び方法
US20120194564A1 (en) 2011-01-31 2012-08-02 White Christopher J Display with secure decompression of image signals
US9177500B2 (en) 2011-01-31 2015-11-03 Global Oled Technology Llc Display with secure decryption of image signals
EP2501133A3 (de) 2011-03-16 2013-07-31 Basler AG Verfahren und Vorrichtung zur Bandbreitenreduktion für Bilddaten
US8456331B2 (en) 2011-04-15 2013-06-04 Cavium, Inc. System and method of compression and decompression
US8350732B2 (en) * 2011-05-11 2013-01-08 Cavium, Inc. Compression with adjustable quality/bandwidth capability
US9130991B2 (en) 2011-10-14 2015-09-08 Silver Peak Systems, Inc. Processing data packets in performance enhancing proxy (PEP) environment
US9626224B2 (en) 2011-11-03 2017-04-18 Silver Peak Systems, Inc. Optimizing available computing resources within a virtual environment
JP5766588B2 (ja) 2011-11-16 2015-08-19 クラリオン株式会社 検索端末装置、検索サーバ装置、及びセンタ連携型検索システム
US8779950B2 (en) 2012-03-05 2014-07-15 Dcba, Llc Command encoded data compression
EP2850763B1 (en) 2012-05-18 2017-09-13 Telefonica S.A. A method and a system for csi reporting in lte networks according to the mobility of the user equipment
JP5826114B2 (ja) 2012-05-25 2015-12-02 クラリオン株式会社 データ解凍装置、データ圧縮装置、データの解凍プログラム、データの圧縮プログラム、及び、圧縮データ配信システム
CN104123309B (zh) * 2013-04-28 2017-08-25 国际商业机器公司 用于数据管理的方法和系统
US9176973B1 (en) 2013-06-14 2015-11-03 Timmes, Inc. Recursive-capable lossless compression mechanism
US9241044B2 (en) 2013-08-28 2016-01-19 Hola Networks, Ltd. System and method for improving internet communication by using intermediate nodes
US10410244B2 (en) 2013-11-13 2019-09-10 Bi Science (2009) Ltd Behavioral content discovery
US9767265B2 (en) * 2014-05-06 2017-09-19 Anchor Id, Inc. Authentication with parental control functionality
US9640376B1 (en) 2014-06-16 2017-05-02 Protein Metrics Inc. Interactive analysis of mass spectrometry data
US9948496B1 (en) 2014-07-30 2018-04-17 Silver Peak Systems, Inc. Determining a transit appliance for data traffic to a software service
US9875344B1 (en) 2014-09-05 2018-01-23 Silver Peak Systems, Inc. Dynamic monitoring and authorization of an optimization device
US9385751B2 (en) 2014-10-07 2016-07-05 Protein Metrics Inc. Enhanced data compression for sparse multidimensional ordered series data
US9543980B2 (en) 2014-10-10 2017-01-10 Massachusettes Institute Of Technology Systems and methods for model-free compression and model-based decompression
US10354421B2 (en) 2015-03-10 2019-07-16 Protein Metrics Inc. Apparatuses and methods for annotated peptide mapping
US11057446B2 (en) 2015-05-14 2021-07-06 Bright Data Ltd. System and method for streaming content from multiple servers
US10911065B2 (en) * 2015-10-20 2021-02-02 Sinan Karaca Computer system and method including selectively compressing data files and directories based on an operator indication and representing the amount of available free space
KR102379182B1 (ko) 2015-11-20 2022-03-24 삼성전자주식회사 연속 데이터 압축 장치 및 방법
EP3219356A1 (en) 2016-03-14 2017-09-20 Max-Planck-Gesellschaft zur Förderung der Wissenschaften e.V. Apparatus for applying electric pulses to living myocardial tissue
JP6735469B2 (ja) 2016-03-22 2020-08-05 パナソニックＩｐマネジメント株式会社 ログ収集装置、監視カメラ、およびログ収集方法
US10432484B2 (en) 2016-06-13 2019-10-01 Silver Peak Systems, Inc. Aggregating select network traffic statistics
US9967056B1 (en) 2016-08-19 2018-05-08 Silver Peak Systems, Inc. Forward packet recovery with constrained overhead
US9742434B1 (en) 2016-12-23 2017-08-22 Mediatek Inc. Data compression and de-compression method and data compressor and data de-compressor
US10319573B2 (en) 2017-01-26 2019-06-11 Protein Metrics Inc. Methods and apparatuses for determining the intact mass of large molecules from mass spectrographic data
US11044202B2 (en) 2017-02-06 2021-06-22 Silver Peak Systems, Inc. Multi-level learning for predicting and classifying traffic flows from first packet data
US10771394B2 (en) 2017-02-06 2020-09-08 Silver Peak Systems, Inc. Multi-level learning for classifying traffic flows on a first packet from DNS data
US10892978B2 (en) 2017-02-06 2021-01-12 Silver Peak Systems, Inc. Multi-level learning for classifying traffic flows from first packet data
US10257082B2 (en) 2017-02-06 2019-04-09 Silver Peak Systems, Inc. Multi-level learning for classifying traffic flows
CN107180018B (zh) * 2017-05-17 2018-11-20 上海兆芯集成电路有限公司 基于散列的加速压缩方法以及使用此方法的装置
US10097202B1 (en) * 2017-06-20 2018-10-09 Samsung Electronics Co., Ltd. SSD compression aware
US10340945B2 (en) 2017-07-24 2019-07-02 iDensify LLC Memory compression method and apparatus
US12400846B2 (en) 2017-08-01 2025-08-26 Protein Metrics, Llc Interactive analysis of mass spectrometry data including peak selection and dynamic labeling
US10546736B2 (en) 2017-08-01 2020-01-28 Protein Metrics Inc. Interactive analysis of mass spectrometry data including peak selection and dynamic labeling
US11626274B2 (en) 2017-08-01 2023-04-11 Protein Metrics, Llc Interactive analysis of mass spectrometry data including peak selection and dynamic labeling
US11212210B2 (en) 2017-09-21 2021-12-28 Silver Peak Systems, Inc. Selective route exporting using source type
US10510521B2 (en) 2017-09-29 2019-12-17 Protein Metrics Inc. Interactive analysis of mass spectrometry data
US12224169B2 (en) 2017-09-29 2025-02-11 Protein Metrics, Llc Interactive analysis of mass spectrometry data
US10637721B2 (en) 2018-03-12 2020-04-28 Silver Peak Systems, Inc. Detecting path break conditions while minimizing network overhead
US11640901B2 (en) 2018-09-05 2023-05-02 Protein Metrics, Llc Methods and apparatuses for deconvolution of mass spectrometry data
WO2020148746A1 (en) 2019-01-20 2020-07-23 Arilou Information Security Technologies Ltd. System and method for data compression based on data position in frames structure
US11290708B2 (en) 2019-02-19 2022-03-29 Edgy Bees Ltd. Estimating real-time delay of a video data stream
US11346844B2 (en) 2019-04-26 2022-05-31 Protein Metrics Inc. Intact mass reconstruction from peptide level data and facilitated comparison with experimental intact observation
JP6614735B1 (ja) * 2019-05-07 2019-12-04 国立大学法人 筑波大学 データの圧縮及び解凍方法、データ圧縮方法、データ圧縮装置、データ圧縮プログラム、データ解凍方法、データ解凍装置、データ解凍プログラム
US11276204B1 (en) 2020-08-31 2022-03-15 Protein Metrics Inc. Data compression for multidimensional time series data
US12512853B2 (en) 2023-07-13 2025-12-30 Maxlinear, Inc. Data compression in a data transform accelerator

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4021782A (en) * 1974-01-07 1977-05-03 Hoerning John S Data compaction system and apparatus
US4366551A (en) * 1977-06-24 1982-12-28 Holtz Klaus E Associative memory search system
JPS5719857A (en) * 1980-07-09 1982-02-02 Nec Corp Data compression storage device
JPS57101937A (en) * 1980-12-16 1982-06-24 Nec Corp Data storage device
DE3118676A1 (de) * 1981-05-12 1982-12-02 Heinz Karl Eckhart Dr Jur Verfahren zur kompression redundanter folgen serieller datenelemente
US4464650A (en) * 1981-08-10 1984-08-07 Sperry Corporation Apparatus and method for compressing data signals and restoring the compressed data signals
JPS59231683A (ja) * 1983-06-01 1984-12-26 インタ−ナシヨナル　ビジネス　マシ−ンズ　コ−ポレ−シヨン データ圧縮方法

Also Published As

Publication number Publication date
EP0129439B1 (en) 1989-02-01
JPH07249996A (ja) 1995-09-26
JPH08237138A (ja) 1996-09-13
JPS60116228A (ja) 1985-06-22
CA1223965A (en) 1987-07-07
DE3476617D1 (en) 1989-03-09
US4558302A (en) 1985-12-10
JPH0568893B2 (ja) 1993-09-29
US4558302B1 (ja) 1994-01-04
EP0129439A1 (en) 1984-12-27

Similar Documents

Publication Publication Date Title
JP2610084B2 (ja) データ伸長方法および装置ならびにデータ圧縮伸長方法および装置
US5608396A (en) Efficient Ziv-Lempel LZI data compression system using variable code fields
US5414425A (en) Data compression apparatus and method
US5016009A (en) Data compression apparatus and method
US5126739A (en) Data compression apparatus and method
JP2713369B2 (ja) データ圧縮装置及び方法
US5410671A (en) Data compression/decompression processor
US6829695B1 (en) Enhanced boolean processor with parallel input
US5532694A (en) Data compression apparatus and method using matching string searching and Huffman encoding
US6334123B1 (en) Index relational processor
US5955976A (en) Data compression for use with a communications channel
AU637826B2 (en) Improved data compression apparatus
US7538695B2 (en) System and method for deflate processing within a compression engine
CA2077271C (en) Method and apparatus for compressing data
JP2863065B2 (ja) マッチングストリング探索およびハフマン符号化を用いたデータ圧縮装置および方法ならびにデータ伸長装置および方法
US20090058693A1 (en) System and method for huffman decoding within a compression engine
US6310563B1 (en) Method and apparatus for enhanced decompressor parsing
JPH0869370A (ja) データ圧縮方法およびシステム
WO2009005758A2 (en) System and method for compression processing within a compression engine
JPH0779262B2 (ja) 圧縮データの符号化方法
JPH08234959A (ja) データ圧縮システム及び方法
US5610603A (en) Sort order preservation method used with a static compression dictionary having consecutively numbered children of a parent
US6507877B1 (en) Asynchronous concurrent dual-stream FIFO
US6535150B1 (en) Method and apparatus for implementing run-length compression
EP0079442B1 (en) Data translation apparatus translating between raw and compression encoded data forms

Legal Events

Date Code Title Description
EXPY Cancellation because of completion of term