JPH026252B2 - - Google Patents

Description

【発明の詳細な説明】 以下の順序で本発明を説明する。

Ａ 産業上の利用分野 Ｂ 従来技術 Ｃ 発明が解決しようとする問題点 Ｄ 問題点を解決するための手段 Ｅ 実施例 Ｆ 発明の効果 Ａ 産業上の利用分野 この発明は、テキスト圧縮及び伸張方法に関す
るものである。

Ｂ 従来技術 この技術分野には、さまざまな広範囲の特許及
び論文が存在する。例えば、米国特許第4545032
号は、基本的な英語の語彙のための数字コードを
利用した辞書またはテーブル変換の基本的技術の
うちの１つを教示する。しかし、これにおいては
単語が接頭部と接尾部と語幹に分解され、辞書エ
ントリまたはテーブル・エントリの重みづけラン
キングが考慮されあるいは適用された様子がな
い。また、用途分野に基づき異なるテーブルまた
は辞書の間で切換できるようにするという概念を
も全く考慮された様子がない。

米国特許第4597057号は、標準的なASCIIコー
ド・テキストが、“単語”としてアルフアベツト、
数字及び句読点要素に分割することができ、“単
語”が接頭部と接尾部と語幹に分割されるような
圧縮技術の典型的な例を与える。これらの接頭
部、接尾部及び語幹は上述の米国特許第4545032
号に類似する方法で数字エンコーデイングを利用
する。

米国特許第4295124号は、数字コードを英語テ
キスト・キヤラクタに適用するための、辞書また
はテーブル索引チイプの変換のより初期の例であ
る。これにおいては、ハツシングによつて第２の
代表コードを生成するために、入力ASCIIでエン
コードされたテキスト単語が使用される。このコ
ードは、テキスト単語の予め配列された辞書メモ
リに対する比較のためのメモリ・アドレスとして
使用することができる。そして、一致が見出され
ると、ハツシング・アドレスが識別子として送ら
れる。もし一致が見出されないなら補助的な辞書
が構築されるが、単語は、最初に遭遇した時点で
圧縮されずに送られる。次にその同一の単語に遭
遇したとき、両方の辞書がチエツクされ、もしそ
の単語が第２の構築された辞書中に見出されたな
ら、そのハツシング・アドレスが送られる。この
記述は有効であり有効な技術であると思われるけ
れども、これは、テキストの利用分野に対応して
注意深く選択され得る多くの辞書の柔軟性を採用
せず、エントリを辞書に割り当てるために点数の
重みづけられた図式を採用しているようには見え
ない。

米国特許第4386416号は、上述の米国特許第
4295124号に類似するが、メモリ・ライブラリ・
アドレスからのコードと、ライブラリ中に見出さ
れない単語の異なるエンコード表現のどちらが利
用されているかを表示するエスケープ・コードを
利用している。しかし、やはりこれにおいても、
辞書エントリのための点数の重みづけ図式が採用
されているようには見えず、また、辞書の特定の
サブセツトを識別するためにプリアンブルまたは
ヘツダを利用する技術が、テキストの所与の圧縮
において採用されていない。

Ｃ 発明が解決しようとする問題点 上述の記述から、テキスト圧縮のための方法、
技術及びシステムに関して多くの仕事がなされて
いるけれども、研究者や開発者は今日まで複数の
拡張辞書を使用することを避けていることが明ら
かである。このことはおそらく、データ記憶条件
を扱うことと、辞書間の切換えの際の複雑さによ
るものと思われる。さらに、エントリを辞書に割
当てる発生の重みづけ頻度の初期の研究は、本願
発明の知見とは逆に、辞書エントリの重みづけ頻
度の使用が、純粋の発生頻度ほどには有利でない
ことを見出している。さて、上述の従来技術によ
る最善の圧縮比率は１：４ないし１：５の範囲で
あるが、本願発明者らは、エントリを重みづけし
た使用頻度に基づき選択して複数の辞書を使用す
ることにより、１：６以上で１：８程度の圧縮比
率が定型的に達成可能であることを期待し得ない
知見として見出したのである。

上述の従来技術の欠点に鑑み、本発明の目的
は、辞書自体がそのエントリを、遭遇した単語の
重みづけられた使用頻度によつて配列されてなる
辞書索引タイプの改善されたテキスト圧縮及び伸
張技術を提供することにある。

本発明の別の目的は、圧縮されるテキストの特
定の使用分野に応じて複数の辞書が採用され、圧
縮のためにどの辞書の選択がなされたかを表示す
るために圧縮においてプリアンブルまたはヘツダ
が利用されるような改善されたテキスト圧縮及び
伸張技術を提供することにある。

Ｄ 問題点を解決するための手段 本発明においては、単語のエントリが、使用さ
れる領域の統計的研究に基づく使用ランキングの
重みづけられた頻度でランクされてなる複数の言
語用途特定辞書を与えることによつて達成され
る。例えば、“docket”や“versus”や“case”
などの単語は、通常の英語の用途よりも法律文書
により頻度にあらわれる。同様の専門的な慣用語
は、工業や、商業や、会計、医療、農業、石油化
学など、どの専門分野でも見出される。本発明に
おいては、テキスト圧縮及び伸張システムのユー
ザーが、使用分野に個別の適合化された複数の辞
書を構築する。このことは、ユーザー環境からの
サンプル・テキストにつき、各個別の単語のキヤ
ラクタ数と、その単語の発生回数をともに計数す
ることを含む走査および解析技術を利用すること
によつて達成される。そのような複数の辞書は、
個々のユーザーに対して高い程度の圧縮を達成す
るように構成され最大の効果を与えるように適用
することができる。また、圧縮テキスト中には、
所与のテキスト・ソース入力に対して圧縮を実行
する際に実際に採用された適当な辞書のユーザー
の選択を表示するために、プリアンブルまたはヘ
ツダが構成される。ヘツダは、受け手に、伸張ル
ーチンおいて使用のためにどの辞書及び制御テー
ブルがロードされるべきかを指令するために使用
される。簡単には、単語が、単一バイト制御テー
ブル自体以外で見出される場合に、各個々の単語
または単語の群の圧縮されたテキストにおけるソ
ースを表示するために、制御テーブル中の単一バ
イト・エントリを採用することができる。制御コ
ード及び辞書セグメント表示子のみならず何らか
のリストをも含む単一バイト制御テーブルから80
ないし224個の頻繁に遭遇する単語までに亘る辞
書の階層が、圧縮または伸張の検索のための最高
優先度の辞書である。第１のバイトがメモリ中の
特定辞書セグメントを表示し、第２のバイトがセ
グメント内のオフセツトまたはメモリ・アドレス
位置を表示するような２または３バイトのエンコ
ードされた辞書エントリもまた採用される。この
システムは、デイスクまたはカセツトなどの大容
量記憶と、大容量記憶機構から読み取ることによ
つて使用のためさまざまな制御テーブル及び辞書
をアセンブルすることができる通常サイズの作業
用読み取り／書き込みメモリをもつ典型的なマイ
クロプロセツサ・コンピユータ上で実施すること
ができる。尚、圧縮及び伸張のための詳細なフロ
ーチヤートは後で詳細に説明する。

Ｅ 実施例 本発明の圧縮技術は、所与の媒体上により多く
のデータを記憶することを可能ならしめ、あるい
は任意の位置の間の伝送リンクを介して短い時間
でより多くのデータを送ることを可能ならしめ
る。これによつて達成される圧縮比は、６ないし
８の高さであり、伝送ヘツダ及び辞書表示子を追
加する効果を考慮に入れても全体的な圧縮比はわ
ずかしか低下しない。データ処理部門において
は、ハード・コピー文書のための遅延は著しくコ
ストがかかる。そのような多くの部門では、別の
遠隔部門との間で多量の情報を共有する必要性に
より通信ネツトワークに莫大な投資がなされてい
る。ネツトワークの拡大と、採用される組織に対
する多くの費用が、効率的なテキスト圧縮及び伸
張方法及びシステムの開発を要請する要因であ
る。さらに、画像デイスプレイとデスク・トツ
プ・コンピユータが増加してきて、処理される情
報の主要な部分は、スクリーン上に存在するテキ
スト・データである。それゆえ、採用される記憶
スペースまたは伝送媒体の量を最小化する何らか
の効率的な圧縮技術は大きな恩恵となろう。前記
従来技術のところで述べたように多くの圧縮技術
が開発されているけれども、これらの技術のうち
のほとんどは、1.5：１ないし２：１程度の圧縮
比をもたらすものにすぎなかつた。

本発明のテキスト圧縮技術は、テキストを生成
し利用する者の基本的言語におけるある単語の長
さ及び反復的発生の程度に関与するものである。
これには多くのオプシヨンが与えられる。それら
のオプシヨンは、採用される基本的な辞書のタイ
プを選択することによつて特定の環境及び特定の
文書自体に適合される。このとき、予め定められ
た既存の辞書、またはテキスト圧縮のために特に
生成された辞書、または個々のテキスト自体のた
めにオン・ラインで生成された辞書を、単独また
は組合して使用することができる。これらの辞書
は、処理を簡単化するために、アドレスのバイト
幅境界上に配列されている。単一バイト・アドレ
スをもつそれらの辞書は、高い程度の圧縮を利用
するが、所与の８ビツト・バイトには256個の異
なるエントリしか存在し得ないので長さが限定さ
れる。２バイトの圧縮単語辞書は、それよりもは
るかに多くの単語を定義することを可能ならしめ
る。すなわち、65536個の単語または２バイト・
エントリ・アドレスが可能である。３バイト・ア
ドレスに拡張すると最大16777216個のエントリが
可能となるが、これは英語で遭遇するすべての単
語の数をはるかに超えている。また、グラフイツ
ク・デイスプレイ及びオーデイオ再生のための辞
書も可能である。というのは、これらは、グラフ
イツクまたはオーデイオ装置による出力のための
特定の信号の単なるデイジタル表示にすぎないか
らである。実質的には、本発明の方法によつて、
キヤラクタで綴られた任意の言語を同様に処理す
ることができる。しかし、ここでは説明の便宜上
英語のみが使用される。

好適なテキスト圧縮技術の基本的な技法は、所
与の文書中にあらわれる実際の英語の単語を、
１、２または３バイト・アドレス・パターンで置
きかえることである。尚ここで使用される“文
書”という用語は、人間のオペレータによつて作
成されあるいは利用されるエンコードされたテキ
スト・データ、グラフイツク・データまたはオー
デイオ・データを定義するために使用される。こ
のとき、キー・ストローク入力が、デイスク・テ
ープなどに記録され、あるいは典型的な英語のソ
ース・テキストとしてメモリに記憶することがで
きる。そのようなソース・テキストは実際は
ASCIIコードのアルフアベツト数字キヤラクタ
と、スペース・キヤラクタと、句読点と、大文字
化、大文字小文字の切換、行送りなどの制御キヤ
ラクタの列である。辞書単語エントリの割り当て
は、使用頻度と長さに従う相対的な重みづけ点数
に基づく。この相対的な重みづけられた点数は、
特定の文書または、法律、技術、医学などの特定
の環境内での単語の発生頻度及び各単語の長さに
基づく。圧縮されたビツト・パターンを１、２ま
たは３バイト（８、16または24ビツト）に限定す
ることにより、現在利用可能なバイト指向コンピ
ユータ上でこれらの技術を実施することがきわめ
て実現しやすくなる。

この基本的な圧縮技術は少くとも１つ、通常は
複数の辞書を利用する。最も基本的でコンパクト
な辞書は256個のエントリの単一バイト圧縮テー
ブルである。このテーブルは、所与の圧縮におい
てどの辞書が採用されているかを知らせる表示子
をデコードするために必要な制御パターンと、問
題にしている環境において最も頻繁にあらわれる
単語と、任意の必要なパターンまたは信号を含む
ように生成される。単一バイト・アドレス圧縮は
明らかに、256個の固有の２進パターンに限定さ
れる。これらのパターンのうちのいくつかは制御
シーケンス、及び所与の圧縮において採用されて
いる個々の辞書セグメントの定義のために留保し
なくてはならない。単一バイト圧縮テーブルまた
はメモリは、このように、最高の相対的実績
（merit）をもち、256個の可能なパターンから留
保制御パターンの数を引いた数にあてはめられる
単語に限定されることになる。この技法は、小さ
い文書に対して十分な利点を以て使用することが
できる。小さい文書とは例えばわずか２〜３ペー
ジから成るものである。

もし２バイト圧縮辞書またはメモリが構成され
るなら、それは最大65536個のエントリを定義す
ることが可能である。しかし、１つのビツトは、
２バイト・パターンが使用されていることを示す
ために留保しなくてはならず、従つて実際には
32768個の辞書エントリのみが可能である。見方
を変えると、256個の単語からなる128個のセグメ
ントが可能である。しかし、多くの場合、会計士
または法律家などの専門家グループで日常的に使
用される語彙は数千語程度あろう。もし２バイト
または65536個の可能なエントリからなる最大の
基本的な辞書サイズが選択されるなら、最初のバ
イトの少なくとも１ビツトは２バイト・エンコー
デイング・パターンが採用されているという事実
を識別するために使用する必要があるだろう。と
いうのは、伸張ルーチンは、圧縮されたバイトを
２バイトまたは３バイトのどちらかで単一にグル
ープ分けする方法を知らなくてはならないからで
ある。こうして、最初のバイトについては256個
の可能なバイトではなく、128個のパターンしか
残されず、実際には全体で256個のパターンから
なる128個の区分をめいめい利用できるのみであ
る。各々の例で２バイト辞書のどの256個単語セ
グメントが使用されているかを表示するために
128個の８ビツト・パターンが制御テーブル中で
留保されなくてはならない。こうして、２バイ
ト・アドレスの最初の“バイト”は、制御テーブ
ルから入手されなくてはならない。このことは、
単一バイト制御テーブル中のもとの256個の可能
なパターンのうち、制御シーケンスや高い実績の
単語などに使用できる128個のパターンを残すこ
とになろう。

もし基本的な辞書サイズが恣意的に32768から
その半分、すなわち16384に限定されるなら、単
一バイト・テーブルには、制御シーケンスや高実
績単語のために利用可能な192個のビツト・パタ
ーンが残される。もしわずか8192個のパターンか
らなる基本的な２バイト辞書サイズが選択される
なら（これはおそらく有用な選択であろう）、224
ビツト・パターンが単一バイト・テーブル中で制
御シーケンス、エンコード・フオーマツト表示子
及び高実績単語のために残されることになろう。

一般的には、256個のもとの可能なビツト・パ
ターンのうちで単一バイト制御テーブルに残され
るビツト・パターンの数は、採用される２または
３バイト辞書中の単語を収めるために選択される
基本的な辞書サイズを256で割つた値で、256から
引いた値である。すなわち、本発明においてデー
タをエンコードする方法は、直接的なテーブル・
エントリによるが、どのテーブルを使用している
かを表示するために圧縮されたテキスト中には表
示子が配置されなくてはならない。256個の可能
なエントリからなる基本的な制御テーブルは、採
用し得る２バイト辞書中の256個のエントリ毎に、
また各３バイト辞書中の65536個のエントリ毎に
１つのパターンを留保していなくてはならない。
これらは“辞書セグメント”と呼ばれ、各テキス
ト圧縮例で採用された各辞書の各セグメント毎に
固有の識別パターンが留保される。もちろん、制
御テーブルを２バイト・テーブルに拡張すること
も可能であるけれども、このことは全体的な圧縮
比に否定的な影響を及ぼすことになろう。たいて
いの場合、高い圧縮比は、基本単語サイズに少な
い数のエントリを選択することによつて達成する
ことができる。多くの部門または組織は、わずか
数千の実用語彙を有するのみであろう。それゆ
え、圧縮比は8192個の単語領域（２バイト・パタ
ーン辞書の可能なサイズの1/4）を選択すること
によつて最適化することができる。これには、単
一バイト制御テーブルとして32個の留保ビツト・
パターンしか必要としない。というのは32×256
＝8192だからである。ここで示した例において
は、単一バイト制御テーブル中でもともと利用可
能な256個のうち224個の可能なエントリが残る。
この224個のエントリは、高使用頻度の単語と、
制御キヤラクタと、所望ならアルフアベツト数字
キヤラクタに好都合に割当てることができる。

本発明に本質的な柔軟性を手短かに説明するこ
とにより、所与のテキスト圧縮のために選択され
た可能な辞書の複合的な集合をどのようにして伸
張または圧縮解除のユーザーに伝達されるかが考
慮される。このことは、本発明においては、圧縮
されたテキストに対してプリアンブルまたはヘツ
ダを利用することによつて達成される。

第６Ａ及び６Ｂ図は、本発明で採用されるヘツ
ダ・エンコーデイング・フオーマツトを図式的に
示すものである。これらの図において、ラインＡ
は、バイト０として識別されるヘツダの開始をあ
らわす。ビツトAAは本発明において、使用中の
単一バイト圧縮テーブルのタイプを定義するため
に利用される。このとき２つのタイプが可能であ
る。すなわち、単一バイト・テーブル中の256個
の可能なパターンに対する割当ての予備配列集合
からなる現存するデフオールト値単一バイト圧縮
テーブルが採用されるか、または別の現存する単
一バイト圧縮テーブルが使用される予定であつ
て、それが予め定義された外部記憶媒体上で見出
され得る。あるいは、圧縮されたテキスト・バイ
ト・ストリング内に実際に単一バイト圧縮テーブ
ルが与えられるか、または２または３バイト・ア
ドレス・サイズの辞書を伝送することができる。
これら４つの可能な場合は、ビツトAAの値を次
のようにセツトすることによつてエンコードされ
る。すなわち、もしビツトAAがゼロなら、新し
いヘツダがあらわれるまで、そのヘツダに続くテ
キスト圧縮ストリングの残りの部分でデフオール
ト単一バイト圧縮テーブルが使用される。もし
AAの値が01なら、留保された割り当てられてい
ない代替のテーブルが使用される。このパターン
は、使用すべき辞書が圧縮されたテキスト中に伝
送される予定であることを表示するために使用さ
れ得る。AAの値の10は、デイスクまたはテープ
などの予定の外部記憶媒体上でユーザーによつて
見出されなくてはならない既存単一バイト圧縮テ
ーブルを使用すべきであることを定義する。例を
挙げると、医学の分野で、癌の専門家に最適化さ
れた単一バイト圧縮テーブルを、所与のテキスト
圧縮のために採用すべき場合がある。ビツトAA
が11である場合は、単一バイト圧縮テーブルが実
際に生成され、後に続く圧縮ストリング内で供給
されることになつていることを示す。ラインＡの
残りのビツトＢ〜Ｇは、他の単語辞書のうちどの
タイプが、ヘツダに続く圧縮されたテキストの所
与のストリームのための圧縮ルーチン中で採用さ
れるかを定義するための表示子として使用され
る。

例えば、本発明では、ビツトＢが、拡張３バイ
ト幅アドレス辞書のための表示子であると定義さ
れる。もしビツトＢの値が０なら、３バイト辞書
は採用されず、もしそれが１なら、ある定義可能
な３バイト辞書が採用される。どの３バイト辞書
（それが存在するとして）が採用されるかという
定義は、後でヘツダ・フオーマツトにおいて扱わ
れるが、これについては後述する。

ビツトＣ〜Ｇはめいめいが、ビツトＢと同様に
使用される個別のビツト表示子であるが、これら
は別の２バイト幅アドレス辞書の使用を示すため
に使用される。図示の例では、５個の異なる２バ
イト幅アドレス辞書を採用することが可能であ
る。

次に、ヘツダの残りのバイトと、それらをバイ
ト０における表示子ビツトと組み合わせて使用す
る方法について説明する。

バイト１は圧縮されたテキストの開始であるか
または、デフオールト条件制御テーブル以外の
個々の制御テーブルが使用されるならバイト１は
制御テーブル番号として解釈されることになる。
もしバイト０中のビツトAAが00または11ならバ
イト１はゼロとなる。もしビツトAAが10に等し
いなら、外部記憶媒体から圧縮解除システムによ
つてアクセスされるべき特定の制御テーブルを識
別するために、８ビツト幅の制御テーブル数がバ
イト１にあらわれることになる。もしビツトAA
が11に等しいなら、バイト１は実際に、圧縮され
たテキスト・ストリーム中の供給された制御テー
ブルの開始地点であり、バイト１〜ｎが、制御テ
ーブル・プラス1024のバイトに割当てられるべき
すべての供給された制御テーブルの長さの和であ
る供給された制御テーブルである。1024は256×
４に等しく、このとき256個の４バイト・パター
ンが書かれる。４バイトの各グループのバイト１
は可能な256バイト・シーケンスの長さ表示子で
ある。４バイトの各グループ中の次の３バイト
は、供給された辞書ストリング中の単語のシーケ
ンス番号である。こうして、適当な時期に、バイ
ト１〜ｎによつて供給された制御テーブルは、先
ず、すべての供給された単語エントリと、次に１
バイト制御テーブル配列の256バイト・アレイ内
のそれらの割り当てを含むことになる。その各割
り当ては４バイトを要し、そのとき４バイトのグ
ループ中の最初のバイトがエントリの256バイト
までのバイト長をあらわし、４バイトのグループ
からの次の３バイトが、制御テーブル定義部分に
続く辞書ストリング中に単語が供給されたときに
テーブル・エントリに関連づけらるべき実際の単
語のシーケンス番号を表示する。

第６Ｂ図において、ヘツダのための３バイト辞
書テーブル定義セグメントであるラインＢが始ま
る。バイトｎ＋１で、バイト０のビツトＭが０で
あるか１であるかに応じて３バイト辞書定義が生
じることになる。例えば、もしバイト０のビツト
Ｂがゼロであつたなら、第６Ｂ図におけるバイト
ｎ＋１及びｎ＋２中のフイールドBA、BB及び
BCがゼロであり、すなわち詳細に定義する必要
のある３バイト辞書が採用されないので、ビツト
は存在しない。しかし、もしバイト０のビツトＢ
が１に等しかつたなら、フイールドBAは１ビツ
ト幅であり、バイトｎ＋１中のフイールドBBは
７ビツト幅である。バイトBBは、採用される３
バイト辞書の65536単語セグメントの数であると
解釈される。バイトｎ＋２であるフイールドBC
は、どの３バイト辞書が使用されたかを表示する
番号である。フイールドBAは、フイールドBB
及びフイールドBCが必要かどうかを定義する。
もしフイールドBAがゼロなら、BCはゼロまた
はビツトがない。というのは、特定の３バイト辞
書を定義する必要がなく、すなわちデフオールト
条件または予備配列された３バイト辞書が使用さ
れるからである。しかしもし、フイールドBAが
１にセツトされているなら、フイールドBCが、
利用すべき選択された３バイト辞書の識別番号で
ある。

ヘツダ・フオーマツトを実現する規則について
説明を続けると、バイトｎ＋３が、場合に応じて
採用されることもある最初の可能な２バイト補助
辞書のための定義区域である。バイト０のビツト
Ｃは、１つのタイプの２バイト辞書が採用される
かどうかを決定する。もしバイト０のビツトＣが
０に等しいなら、それ以上の定義は不要であるの
でバイトｎ＋３及びｎ＋４中のフイールドCA、
CB及びCCがすべて０にセツトされる。しかしも
し、バイト０のビツトＣが１なら、フイールド
CAはビツト１でありフイールドCBは幅７ビツト
となる。ビツトCAは、デフオールト２バイト辞
書、または特に定義すべき２バイト辞書のどちら
が採用されているかを決定する表示子である。も
しCAが０にセツトされているなら、デフオール
ト条件または予備配列２バイト辞書が使用され、
通常は所与の２バイト辞書のための特定数である
バイトｎ＋４フイールドCCは、デフオールト条
件が呼び出されているがゆえに全く与えられる必
要がない。しかしもし、フイールドCAが１に等
しいなら、フイールドCDは、定義されている最
初の２バイト辞書のために利用された256単語長
セグメントの数であり、フイールドCCは、その
２バイト辞書のための識別番号である。

このフオーマツトまたは規約は、今しがた説明
した第６Ａ図ラインＡのバイト０のビツトＤ、
Ｅ、Ｆ及びＧの状況に基づきラインＢ，Ｃ及Ｄに
示すバイトｎ＋１〜ｎ＋12に対しても同様に続け
られる。もしバイト０における２バイト辞書のた
めの可能なすべての５個の表示子が採用されるな
ら、実際の圧縮されたテキストの開始はラインＤ
のバイトｎ＋13まで始まらず、それはラインＤの
バイトｎ＋ｎにおいてテキストの終端があらわれ
るまで中間番号のバイトに対して続くことにな
る。

次に、所与のヘツダにおける最初のバイトであ
るバイト０のいくつかの例について説明する。

場合１ この場合、ヘツダのバイト０がすべて０にセツ
トされていると仮定しよう。すると、第６Ａ図及
びそれに関連する説明を参照すると、２及び３バ
イト表示子ビツトＢ〜Ｇのどれも１にセツトされ
ていないので、単一バイト圧縮技術が使用される
ものとして定義されている。さらに、ビツトAA
が０にセツトされているので、デフオールト単一
バイト圧縮テーブルが利用され、これはデフオー
ルト・テーブルであるので、規約によつて既に、
受け手またはユーザーの側の伸張プログラムのた
めのアドレス空間中に存在している。このこと
は、受け手と送り手が通信を介して前以て、デフ
オールト・テーブル値を確立しそれらを双方のシ
ステムに入力するように取決めていることを意味
する。これは１バイト幅テーブルであるから、
256個の可能なエントリがある。これらのエント
リのうちのあるものは制御シーケンスに割振ら
れ、あるものは特殊キヤラクタに、あるものは文
字に、そしてあるものは数字に、それぞれ割振ら
れている。しかし、特殊なユーザー設備語彙で出
会う高い頻度の単語には膨大なエントリが留保さ
れる。

制御シーケンス、特殊キヤラクタ、文字または
数字の実際の数、及び高頻度の単語は、ユーザー
の好みと経験に基づきユーザーによつて選択され
る。これらのパターンを割当てる方法は典型的に
はユーザーが、ユーザーの環境からさまざまな代
表的なテキストを走査して、遭遇する相対的に高
頻度の単語を作業用語彙中に統計的に分離するこ
とである。これを実行するための方法は後述す
る。しかし、256個のパターンのうちのいくつか
は、遭遇することになる通常あらわれる制御のた
めに割振る必要があろう。例えば、スペース・キ
ヤラクタと、アルフアベツトの大文字小文字のす
べてと、数字キヤラクタは通常別々のエントリで
定義される。行の終了及び文書の終了の制御コー
ドはどの場合にも留保する必要があり、多重スペ
ース・コードは有用な追加である。カンマとスペ
ースの組み合わせ、またはピリオドとスペースの
組み合わせもまた有用な定義であり、それは、コ
ーデイング技術などの変化を表示するための任意
に採用されたエスケープ・キヤラクタである。ま
た、規約によつて、この特定のバイト・パターン
の発生に続くテキスト中のバイトが、現在使用中
のテーブルの代わりに使用されるべきテーブル番
号を示すために使用することのできるテーブル切
換表示子バイト・パターンを留保しなくてはなら
ない。

バイト０がすべて０である上述の例では、圧縮
されたテキストが圧縮されたテキスト・バイト・
ストリング中のバイト１で開始することになり、
ヘツダ自体は単一バイトである、バイト０であ
る。

第６Ａ及び６Ｂ図に記述されたネーミング及び
フオーマツト規約によれば、ヘツダの最初のバイ
トであるバイト０は、使用された辞書の特定のア
レイ及びタイプを定義する制御バイトであり、ヘ
ツダの残りのフオーマツトが、エンコードされつ
つあるテキストの所与の圧縮で採用された補助的
辞書の個別の特定の長さ及び識別を定義する。

場合２ この場合は、バイト０が１と７個の０にセツト
されていると仮定しよう。これは、第６Ａ及び６
Ｂ図において確立された規約によれば、単一バイ
ト圧縮技術自体が採用されているけれども、非デ
フオールトあるいは補助単一バイト定義テーブル
が、外部記憶媒体上に在駐するこのテーブルにア
クセスしなくてはならない圧縮解除アルゴリズム
によつて使用されることになることを示す。この
テーブルは通常、ユーザーによつて、BASTAB
などの導入選択接頭部とそれに続く、例えばヘツ
ダ・ストリング中のバイト１に含まれる数値の接
尾部からなる名称を与えられている。外部記憶媒
体上の単一バイト圧縮テーブルのためのネーミン
グ規約は、例えば、デフオールト・テーブル値で
ある“BASTAB.0”または、圧縮されたテキス
ト・バイト・ストリング内に供給されたテーブル
である“BASTAB.1”などである。“BASTAB.
n”は、外部記憶媒体上に在駐する追加的なテー
ブルであり、ここでｎは２と255の間の任意の値
である。圧縮解除の間に、バイト０の読み取りに
続いて、圧縮解除プログラムが外部記憶媒体上の
識別された単一バイト圧縮テーブルにアクセス
し、それを、プロセツサの読取／書込メモリ中の
圧縮解除プログラム・アドレス空間に読み込む。

上述のように、単一バイト圧縮テーブル内のビ
ツト・パターンのうちの１つは通常、テーブル切
換表示子バイトのために留保されている。これ
は、１つの単一バイト圧縮テーブルから別の単一
バイト圧縮テーブルへの切換を行うために使用さ
れる。圧縮されたバイト・ストリング中でテーブ
ル切換パターンに遭遇したときは何時でも、規約
により次のバイトがエンコードされ、次に利用す
べきテーブルの番号を含むものとして解釈される
ことになる。この新しいテーブルは、次に外部記
憶媒体から読み出されて、もしそれが圧縮解除プ
ログラム・アドレス可能メモリ空間に在駐してい
ないなら、それはそのメモリ空間に配置される。

場合３ バイト０が11000000にセツトされていると仮定
する。第６Ａ及び６Ｂ図の記述に基づくこの規約
は、単一バイト圧縮テーブルが採用され、テキス
トの圧縮解除のために使用すべき初期テーブル
が、相対的バイト位置番号３で始まる圧縮された
テキスト・バイト・ストリング内に実際に送られ
るテーブルであることを表示する。ヘツダに続く
テキスト・ストリング中の相対的バイト位置１及
び２は、供給された単一バイト圧縮テーブルの全
体の長さの２進値を含む。そのテーブルは、圧縮
されたバイト・ストリング内に供給され、圧縮さ
れたバイト・ストリングから抽出されて圧縮解除
プログラムのアドレス可能メモリ空間に配置され
なくてはならない。圧縮されたテキスト・テーブ
ルが次にバイト３で始まり、その後に実際の圧縮
されたテキストが続くことになるテーブルの長さ
によつて決定されるカウントで終了する。

場合４ バイト０が00100000にセツトされていると仮定
する。このパターンは、第６Ａ及び６Ｂ図の規約
によれば、デフオールト制御テーブルとして定義
されるタイプの単一バイト圧縮テーブルと、フイ
ールドBA中に定義されるタイプの３バイト辞書
の組合せが使用されていることを定義する。この
場合のバイトｎ＋１はバイト１である。というの
は、ここで指定したヘツダの構成では制御テーブ
ル番号または供給された制御テーブルが必要とさ
れないからである。バイト１の下位７ビツトは、
採用された３バイト辞書中で利用された65536単
語長セグメントの数（引く１）としての長さであ
る。もし特定の３バイト辞書が使用されバイト３
が圧縮されたテキストの開始点であるなら、バイ
ト２であるフイールドBCが３バイト辞書のため
の識別番号を定義し、またはフイールドBA（バ
イト１の最高位ビツト）が、デフオールト３バイ
ト・テーブル条件を記述する０であつた場合、バ
イト２が圧縮されたテキストの開始点となる。

記述された３バイト辞書中の単語の数は、採用
された65536単語群の数である。７ビツトがその
長さを決定し得ると仮定すると、１ないし128個
のそのような群を決定することができよう。それ
ゆえ、３バイト圧縮タイプの辞書の全体の長さに
おける単語の数は少くとも65536語であるが
8388608語以上ではない。単一バイト圧縮制御テ
ーブルにおいては、採用される65536語の群の数
に等しい制御パターンの数が、任意の時点で３バ
イト辞書のどの区域が使用されつつあるかを識別
するために留保される必要がある。このように、
３バイト辞書中で見出された単語の出現をエンコ
ードするために、その識別子の最初の部分は、そ
の単語を含むことが分かつている３バイト辞書の
セグメントを表示する制御テーブルからの１バイ
ト識別子となる。次の２バイトは、エンコードさ
れる実際の単語が見出される辞書のセグメント内
の相対的オフセツトを表示する。

こうして、もし65536語からなる単一の群が３
バイト圧縮テーブル中で使用されたなら、単一バ
イト圧縮制御テーブル中の単一１バイト・ビツ
ト・パターンが、３バイト圧縮解除辞書が必要で
あることを圧縮解除プログラムに知らせるために
使用される。圧縮解除ルーチンが圧縮されたテキ
スト・バイト・ストリング中で特定の単一バイ
ト・パターンに遭遇するとき、その後の２バイト
は、65536語３バイト辞書内のどの単語がもとの
テキストからあらわされているかを指定するため
に、併せて読まれなくてはならない。

尚ついでながら、もしそのような65536語の群
の数が比較的小さいなら、現在の小型システム中
のランダム・アクセス・メモリの利用可能性を考
慮すると、３バイト圧縮辞書全体を圧縮解除プロ
グラムのアドレス空間にロードすることが可能で
ある。65536語の各群は典型的には１メガバイト
記憶の半分よりもやや少ない領域を占有するの
で、約５文字の平均単語長を仮定すると、数メ
ガ・バイトのアドレス空間を圧縮解除プログラム
に対して有効に割り振ることが、大型プロセツサ
上で実現可能である。小型プロセツサ上では、オ
ペレーテイング・プログラムのために十分なアド
レス空間を留保するために通常そのような群を数
個収める余地しかない。

３バイト辞書が圧縮解除プログラムのアドレス
空間中に配置することを要望し得るよりも大きい
場合、辞書は、必要に応じて65536語セグメント
中で外部記憶媒体からアクセスされる。実際の３
バイト辞書を収めるために必要な外部記憶空間の
量を減少させるために利用し得る技術もある。こ
れらの技術の多くは、IBM及びその他の会社に
よつて利用されている仮想記憶アクセス方法とし
て知られている。この技術は、何らかの外部記憶
が使用されているときに外部記憶の必要条件を最
小限に抑えるためのものであるが、本発明には直
接関係がないので詳細な説明は省略する。

前述したように、単一バイト圧縮テーブル内の
１ビツト・パターンが、テーブル切換表示子のた
めに留保されなくてはならない。もし３バイト・
テーブルが採用されたなら、３バイト・テーブル
切換表示子が留保されなくてはならない。こうし
て、圧縮解除アルゴリズムがこの特定のパターン
に出会うとき、その後のバイトは、外部記憶媒体
上でアクセスすべき特定の３バイト辞書の名前を
含むことができる。

場合５ この場合は、バイト０が0010000、00001000、
00000100、00000010または00000001のうちの任意
の値をとると仮定する。この例では、２バイト圧
縮辞書の異なる５つのタイプのうちのどれかが採
用されている。その５つのタイプに対する制限は
随意であり、第６Ａ図のラインＡにおけるバイト
０のための８ビツト・バイト・フオーマツトの使
用に基づく。

もし、５つ以上のタイプの２バイト辞書が必要
なら、この説明で使用されているバイト０を、16
ビツト・フイールドないしそれ以上に拡張するこ
とができる。いかなる場合でも、利用しうる２バ
イト辞書の数は、以下に示すタイプまたは他のタ
イプのうちの１つまたはそれ以上である。すなわ
ち、文書自体に固有の辞書、すなわち実際にテキ
スト内に供給される固有の辞書の構築をもたらす
後述する走査および優先化ルーチンによつて生成
されるの辞書である。あるいは、特定のユーザー
環境の分野が採用されている特殊なジヤーゴンま
たは固有名詞を含む補助的な辞書である。あるい
は、特定の人間または人間集団の固有の語彙のた
めの個人的辞書または、グラフイツク辞書あるい
はオーデイオ辞書である。尚、定義および利用可
能なそのような辞書の数は実質的には無制限であ
り、それらを利用しているという事実は圧縮解除
ルーチンまたはユーザーに有効に通信されうるこ
とを理解されたい。

上述の３バイト辞書の例に関連して、２バイト
辞書の各々は利用中の辞書のタイプのための辞書
版切り替え表示子として利用される単一バイト圧
縮制御テーブル内にビツト・パターンを持つこと
ができる。もちろん、選択されたすべての２バイ
ト辞書で利用される256語のセグメントの数の値
に等しい単一バイト圧縮制御テーブル中のビツ
ト・パターンの数も同様に留保しておかなくては
ならない。圧縮解除アルゴリズムが圧縮されたテ
キスト・バイト・ストリングにおいてこれらのう
ちの任意のパターンに遭遇するとき、定義によつ
て、アルゴリズムは、それ以下のバイトを、所与
の識別された２バイト辞書からの最初のバイトに
よつて識別された特定の256語の群内の単語の数
を意味するものとみなす。各辞書からのそのよう
な各256語セグメントは自己の制御パターンを割
り当てられているので、あいまいさがなく、その
特定の辞書およびその辞書の特定の256語セグメ
ントは制御パターン自体から知られ、従つて、そ
の群内の単語の特定の数のみが移送されなくては
ならない。結局、２バイト辞書内にあらわれる単
語をエンコードするためには、２バイトしか必要
でない。その最初のバイトは、単一バイト圧縮制
御テーブル内に記憶されている制御パターンのう
ちの１つに一致しなくてはならない。第２のバイ
トは、見出された２バイト辞書の特定の256語セ
グメント内のその単語自体を番号またはシーケン
ス番号である。

上述の定義と第６Ａ及び６Ｂ図に関連する説明
から明らかなように、ヘツダのバイト０における
ビツト・パターンの数多くの置換が採用され得
る。事実、バイト０につき８ビツト・バイト・フ
オーマツトを仮定すると、256個の異なるパター
ンが存在する。ヘツダにおいてバイト０に続くバ
イトは、第６Ａ及び６Ｂ図に関連して前述した、
採用された辞書の好みの順序によつて決定される
シーケンス中で評価される。例えば、もしバイト
０が00100000としてエンコードされたなら、その
圧縮テーブルのためのデフオールト値を使用する
単一バイト圧縮テーブルと、デフオールト３バイ
ト圧縮辞書が採用される。バイト１は、規約によ
つて、デフオールト３バイト圧縮辞書の長さを定
義しなくてはならず、すなわち、第６Ａ及び６Ｂ
図のバイトｎ＋１のフイールドBAが０にセツト
され、フイールドBBが、辞書に実際に採用され
た65536語セグメントの数としての長さである。

上述の説明から明らかなように、複数の辞書を
使用することができ、一般的な場合、各辞書はｊ
個までのセグメントを含み得る。所与の辞書のた
めの所与のセグメントがこうしてＤ（ｉ、ｊ）に
よつて定義され、それは制御テーブル内にある特
定のビツト・パターンによつて呼び出すことがで
きる。所与の圧縮例で使用されているすべての辞
書に採用されたセグメントの数の合計は、セグメ
ントが圧縮されたテキスト・ストリング内であら
われたときにセグメントを識別するために個々の
ビツト・パターン中に留保しなくてはならない。
すなわち、圧縮されたテキスト・ストリング中に
採用される識別された各辞書の各セグメント毎に
制御テーブルに１つのビツト・パターンが存在す
ることになる。こうして、圧縮されたデータ・セ
ツト中の単一バイトによつてあらわされる単語ま
たは句の数が、単一バイト中の可能な全体の数か
ら、制御テーブル中で識別子を留保されなくては
ならないすべてのセグメントの全体の数と、特殊
キヤラクタ、文字、数字及び制御シーケンスまた
は信号のために制御テーブル内に確保される制御
ビツト・パターンの数とを引いた値である。ここ
で採用されている任意の規約によると、辞書セグ
メントを識別するために使用される制御テーブル
内のビツト・パターンの数に、制御テーブルの頂
部、すなわちすべて１のビツト・パターンから始
まつて順次的に、辞書セグメントの全数に割当て
が行なわれるように下位番号のビツト・パターン
の方へ進行して割り当てが行なわれる。次に、制
御ビツト・パターン、特殊キヤラクタ、文字、数
字などに残りの制御テーブル空間が割り当てら
れ、残りのスペースがあればそれは最高頻度の単
語群に渡すことができる。

上述の規約に含意されていることであるが、エ
ンコーデイング側での辞書の検索は圧縮技術を使
用する者によつて定義された優先順位に従うこと
になる。検索のための典型的なシーケンスは、先
ず単一バイト圧縮単語パターンの制御テーブルを
検索し、もし使用されるなら２バイト辞書を検索
し、その後もし使用されるなら３バイト辞書を検
索するものである。

前述のように、所与の例における２バイト辞書
の数は、バイト０のための８ビツト・バイト・フ
オーマツトにより任意的に５個に限定されてい
る。しかし、採用された２バイト辞書の各々と制
御テーブル自体と３バイト辞書は、各自が、辞書
のタイプのための版切替ビツトパターンを圧縮さ
れたストリング中に挿入し、その後、辞書のどの
版が次にアクセスされるべきかを識別するバイト
による規約に従つて呼び出し得る256個までの版
を有することができる。

制御テーブル割当ての例として、各々が65536
語からなる16個のセグメント（全体で1048576語）
をもつ３バイト辞書が選択され辞書Ａと呼ばれる
ような例を考えてみよう。また、各々が256語か
らなる32個のセグメントを有する２バイト辞書が
選択され、辞書Ｂと呼ばれると仮定する。さらに
また、各々が256個の単語からなる８個のセグメ
ント（全体で2048語）を有する２バイト辞書が選
択され、テキストを圧縮するための辞書Ｃと呼ば
れると仮定する。すると、単一バイト制御テーブ
ル中に制御ビツト・パターンを割振る際に次のス
テツプが実行されることになる。

先ず、３バイト辞書Ａの16個のセグメントをあ
らわすために、制御テーブル中に16個の８ビツ
ト・パターンが割振られる。次に、２バイト辞書
Ｂの32個のセグメントをあらわすために32個の８
ビツト・パターンが割振られ、続いて、２バイト
辞書Ｃの８個のセグメントをあらわすために、８
ビツト・パターンが割振られる。次に、遭遇すべ
きさまざまな特殊キヤラクタ、制御シーケンス、
文字、数字等に複数の８ビツト制御パターンが割
振られる。そして次に、単一バイト幅の制御テー
ブル中の256個のもとの可能なパターンのうちの
残りのビツト・パターンが、この後説明する技術
に従つて選択された高い得点の単語に割振られ
る。最後に、これらの辞書の選択を行つたエーコ
ーデイング・グループによつて示された特殊な辞
書が、圧縮ルーチンを開始するためにメモリに読
み込まれることになる。

さて、実際の圧縮ルーチンについて説明するた
めに、システム及びその動作方法について詳しく
説明する。

第１図を参照すると、本発明の好適な実施例に
基づく典型的なテキスト圧縮及び伸張動作のため
の全体的なシステム・ブロツク図が示されてい
る。テキストの入力源は典型的な読取／書込デイ
スク、人間のオペレータによつて制御されるキー
ボード、カセツト、またはACIIまたはEBCDIC
によりエンコードされた入来テキストがある遠隔
位置から受信される通信ネツトワーク・アダプタ
である。このテキスト入力装置は、第１図では点
線１で囲まれて、テキスト入力１と総称される。
マルチプレクサ２は、マイクロプロセツサ４から
のアドレス・バス上で受け取つたアドレスに従つ
て圧縮または伸張すべきテキストの入力源として
の可能な入力のうちの１つを受け取り選択するた
めのものである。尚、記憶媒体からの信号を適正
な電圧に変換し、マルチプレクサ２に与えるため
にフオーマツトすべく、デイスク、キーボードま
たはカセツトのための個別のアダプタ、または通
信ネツトワーク・アダプタが設けられることを理
解されたい。マルチプレクサ２の他方の側には、
直列から並列、または並列から直列へのフオーマ
ツト変換を行うためのアダプタ５及び６が接続さ
れており、これにより、システム中で、直列また
は並列のアドレス及びデータ・バスの利用が可能
となり、また、点線１の囲み内の直列または並列
入出力装置に適正な通信がはかられる。たいてい
の場合読取専用である主要制御記憶７が、制御用
マイクロプロセツサ４のアドレスおよびデータ・
バスに接続されている。また、デイスク記憶の形
態である大容量記憶が、大容量記憶８として示さ
れている。残りの囲み９，10及び11は、制御プロ
セツサにより構成され、その作業用メモリ空間と
して使用される読取／書込アドレス可能メモリの
部分を示す。ブロツク９は、索引と、辞書セグメ
ント・マツプ及び制御テーブルを伴う主要辞書を
含み、それらすべては、ユーザーによる所与の選
択に従い、または前述のヘツダのバイト０の読取
りに応答して大容量記憶８から読み込まれたもの
である。

ブロツク１０は、送信Ｉ／０バツフアであり、
ブロツク１１は受信Ｉ／０バツフアである。これ
らのバツフアは、アドレス可能なメモリ空間中
で、後述する圧縮または伸張アルゴリズムの動作
の間に、圧縮または伸張すべきデータが一時的に
バツフアされる領域として構成されている。辞書
に対する主要記憶９内の空間の割当てもまた、後
述する辞書セグメント索引と、辞書セグメント・
マツプを含む。

所与のユーザーにより示された個々の辞書がメ
モリ９に読み込まれていると仮定すると、プロセ
ツサ４は、辞書検索時間を最小限に抑えるための
索引を構築することになる。これらは、前以て構
築して、辞書自体が大型記憶８からロードされる
時点で読み込むようにしてもよい。索引セツト
は、メンバーの集合から成り、その各自メンバー
は、セグメントのために定義すべき制御テーブル
中に留保されるセグメント番号を含むことにな
る。この索引番号は、単語の長さに対応するエン
トリと、使用される単語群の照合順序における辞
書セグメントの最下位または最初のセグメントに
対応する単語自体のためのエントリの２つのエン
トリを有する。索引番号はまた、そのセグメント
中の最後のまたは最高位照合順序単語エントリに
対する、その単語の長さ及びその単語自体の２つ
のエントリをもつ。言いかえると、辞書セグメン
ト索引は、定義すべき各セグメント毎に、そのセ
グメント内にアルフアベツト順にあらわれる最下
位照合順序エントリの長さ及び実際の単語エント
リと、そのセグメント内にあらわれる最高位照合
順序エントリの長さ及び実際の単語エントリを含
む。この照合順序は通常アルフアベツト順でよ
い。照合順の例が第２図に示されている。

第２図の例で仮定されている照合順は、IBM
システム／370コンピユータ・アーキテクチヤで
使用されているものである。これは、最初に、特
殊キヤラクタを、システムのユーザーに知られて
いる定義された順序に並べ、次にアルフアベツト
の大文字小文字を並べ、最後にシーケンスの最高
位照合順序に数字を並べた、割振られた階層ソー
テイング照合順序である。この照合順序は、ソー
トすべき可能なエントリには、全体的なアルフア
ベツト順に等価に見えるかもしれない。各辞書の
実際の辞書エントリは、こうして先ず照合され照
合順にソートされる。また、各辞書セグメント
は、所与の長さと、所与のエントリ辞書（場合に
よつては数字または文字）の、ある低照合順エン
トリで始まり、セグメント索引は、使用される辞
書のそのセグメント内にあらわれる最高位照合順
エントリで終わる。辞書セグメント索引は、後述
する２分検索技術を用いて辞書検索時間を短縮す
るために使用される。

上述の例では、第２図に示すように、辞書セグ
メント索引には56個のセグメントが定義されてい
る。内訳は、３バイト辞書には32個のセグメント
選択された２バイト辞書の各々に、16個及び８個
のセグメントである。単一バイト制御テーブル
は、単一バイトに基づき迅速に検索することがで
きるのでセグメントは全く必要ではないが、一貫
性のため単一バイト・テーブルのためのセグメン
ト索引が採用されている。

さらに、実際のセグメント番号とエントリ位置
を開始メモリ・アドレス位置と相関させるための
辞書セグメント・メモリ・マツプが構成される。
これには、セグメント番号と、キヤラクタの数に
おける最初のエントリの長さと、そのようなエン
トリがあらわれる開始メモリ・アドレスが含まれ
る。そして、その後には、すべてのセグメント
と、すべてのキヤラクタ長さと、すべての開始メ
モリ・アドレスが辞書セグメント・メモリ・マツ
プにロードされてしまうまで、長さと開始アドレ
スをもつセグメント内の次のエントリが続く。こ
れにより、後述のとおり２分検索技術が著しく容
易になる。というのは、もし辞書エントリを検索
するために２分検索技術が使用されるなら、圧縮
または伸張すべき所与の単語について一致するエ
ントリをきわめて高速で見出すことが可能だから
である。辞書セグメント・メモリ・マツプはま
た、制御テーブル内の単語に対応するエントリを
も含む。上述の例においては、通常の特殊キヤラ
クタ及び辞書セグメント表示子の割当てが完了し
た後制御テーブルには168個のビツト・パターン
が残されていることになる。

もし圧縮ルーチンに従うなら、この圧縮のため
になされた特定の辞書選択を記述するヘツダが圧
縮されたデータ・セツトに書き込まれることにな
ろう。例えばヘツダは、上述の例では0011100に
0001111が続き、それに0011111が続き、それに
00000111が続く。このことは、16個のセグメント
からなる３バイト辞書と、32個のセグメントから
なる２バイト辞書と、８個のセグメントからなる
２バイト辞書が採用されているという事実を決定
する。さらに、次の３バイトの各々の最初のビツ
トがその例に示すように０にセツトされているの
で、最初のバイト00111000が、すべての辞書及び
制御テーブルがそのデフオールト値定義にセツト
されていることを記述する。

次に、所与のテキスト入力または文書が走査さ
れて単語が抽出される。このことは、通常、従来
技術で知られているように、キヤラクタ・コード
に続く句読点またはスペースに出会うまでテキス
ト・ストリングを検査することによつて実行され
る。次に、そのキヤラクタ・コードとスペース・
コードの集まりが、辞書エントリに対して比較す
べき“単語”と見なされる。大文字も同様に処理
され、大文字が検出された場合にそのことを表示
するコードが圧縮されたデータ・セツトに書かれ
る。圧縮されたデータ・セツトのために適当な制
御シーケンスが書かれ、その最初のキヤラクタ
が、辞書検索のために小文字に変更されることに
なる。“すべてが大文字である”状況も存在し、
この状況のために適当なシーケンスが圧縮された
データ・セツトに書かれ、以て検索のためにすべ
てのキヤラクタが小文字に変更される。

次に、比較的に高い優先度あるいは高い得点の
単語をあらわす制御テーブル中のエントリに対し
て単語がチエツクされる。このことは、２分検索
技術を利用し、第２図の制御テーブル辞書セグメ
ント・メモリ・マツプを用いて行なわれれる。も
し入力単語と、制御テーブル単語リストの間で一
致があらわれたなら、この単語をあらわす単一バ
イト・パターンが圧縮されたデータ・セツトに書
き込まれ、処理はこれの直前のステツプから続く
ことになる。

もし単一バイト制御テーブル中で一致が見出さ
れなれないなら、最初の２バイト辞書中でそれが
見出されるはずである場合に最初の２バイト辞書
内のどのセグメントがその単語を含んでいる可能
性があるかを判断するために索引セツトが使用さ
れる。第２図の辞書セグメント索引がこの目的の
ために利用される。このことは、索引セツトの最
初のメンバーを選択して、その索引セツトがあら
わすセグメント中の最低及び最高エントリに対し
てその単語を比較することによつて行なわれる。
もしその単語が所与のセグメントの所与の索引セ
ツト・メンバーの最低及び最高エントリの照合シ
ーケンス範囲内に含まれているなら、圧縮すべき
その単語が検索されている特定の辞書内に実際に
含まれているかどうかを判断するために、辞書セ
グメント・メモリ・マツプ中で、その特定のセグ
メント内でのその単語の２分検索が実行されるこ
とになる。この２分検索は、目的メモリ・アドレ
スを見出すために辞書セグメント・メモリ・マツ
プを使用する。そしてもし一致が見出されたな
ら、そのセグメント番号及びそのセグメント内の
単一バイト単語番号が書き込まれる。３バイト辞
書の場合、単語番号のためのオフセツトには、セ
グメント番号に続く２バイトが必要である。

定義された１つの２バイト辞書中で一致が見出
されないなら、定義されたすべての２バイト辞書
が検査されてしまうまで後の２バイト辞書が検索
されることになる。

もしどの辞書にも一致が見出されないなら、２
つの方法のうちの１つを用いてその単語が書き出
される。すなわち、単語が圧縮されないでそのま
まキヤラクタ毎にEBCDICまたはASCII表示とし
て圧縮されたデータ・テキストに送られ、または
書かれるか、あるいは、圧縮されたデータ・テキ
ストに特殊な制御シーケンスが書かれ、続いて非
圧縮キヤラクタ表示が書かれ、さらに続いて、非
圧縮部分の終わりに到達したことを表示する別の
制御シーケンス・バイトが書かれる。どちらの技
術を選択するかは任意である。テキストの非圧縮
部分の出現を表示するためのエスケープ・シーケ
ンスまたは制御シーケンスの使用は、単一バイト
制御テーブル中にきわめてわずかの制御シーケン
スを記述する必要を生じさせる。しかし、もし
個々のキヤラクタ表示が制御テーブル中に留保さ
れているなら、圧縮されたテキスト・ストリーム
中に制御シーケンスまたはエスケープ・シーケン
スを入力することによつて非圧縮テキストが後に
続くことを表示することは不要である。このこと
は、非圧縮EBCDICまたはASCIIキヤラクタが制
御テーブル中で一致エントリを知出すことになる
がゆえにそれらが正確に受信されデコードされる
ので正しい。

さて、次に、マイクロプロセツサとプログラム
言語が与えられたなら、熟練したプログラマをし
て動作プログラムを書くことを可能ならしめるデ
ータ圧縮アルゴリズム・フロー・チヤートの例を
与える。

第４Ａ−１，４Ａ−２，４Ｂ，４Ｃ，４Ｄ，４
Ｅ、及び４Ｆ図は、異なるタイプの辞書を用いた
さまざまな圧縮技術のフローチヤートである。こ
れらのフローチヤートは、一見して理解され、ま
たマイクロプロセツサの命令セツトに容易に変換
され得るものであるけれども、関与する圧縮技術
について説明を加えておくことにする。

最初のタスクは第４Ａ−１図のブロツク１２で
始まり、そこで圧縮ルーチンが開始される。ブロ
ツク１３で問われる最初の質問は、ユーザーが圧
縮のためのデフオールト条件において使用すべき
単一バイト・テーブルのみを選択したかどうかと
いうことである。もしその答えがイエスなら、ブ
ロツク１４で示されているように、すべて０のヘ
ツダが書き込まれ、文書の圧縮がブロツク３２
（第４Ｂ図）で開始される。このルーチンは、圧
縮すべき文書のEBCDICまたはASCIIコードを含
む文書フアイルから単にキヤラクタをフエツチす
ることにある。キヤラクタが単語の終了である場
合、すなわちスペースまたは句読点マークが見出
されるかあるいは文書終了キヤラクタが見出され
る場合は何時でも、単語が分離されたものとして
決定される。この単語の全体は次に、前述の２分
検索技術を用いて単一バイト圧縮テーブルに比較
される。そし一致が見出されると、単一バイト・
テーブル内のその単語のアドレス位置に対応する
ビツト値がその単語の圧縮されたバージヨンとし
て書き込まれる。これは、例えば、送出用圧縮テ
キストを構築するために第１図中のバツフア10に
配置してもよく、またはユーザーの選択に応じて
主メモリ９に配置することもできる。ブロツク３
８（第４Ｂ図）では、分離された最後の単語にテ
キスト終了表示子が見出されたか否かが問われ、
もしそうなら、テキスト終了ビツト・パターン
が、圧縮されたデータ・セツトに書き込まれなく
てはならず、そうして圧縮プログラムが終了す
る。もしブロツク３２での答えがノーなら、第１
図のブロツク１１中の単語バツフアがクリアさ
れ、プログラム・ルーチンは、文書フアイルから
別のキヤラクタをフエツチしそれをブロツク３３
中の単語バツフア11に配置することによつて開始
に戻る。この処理は、文書中のすべての単語がエ
ンコードされ、あるいは使用されているどの辞書
においても一致が見出されないときに書き出すこ
とによる別の方法で処理されるまで続く。ルーチ
ンのこの部分は、フローをブロツク４３（第４Ｃ
図）へ導くブロツク３６からの出口に見出され
る。もし単一バイト・テーブルが１つのみ使用さ
れているなら、一致が見出されないという場合
に、前述したようにEBCDICまたはASCIIキヤラ
クタを直接利用することによつてその単語を書き
出すか、またはブロツク４４で示すように圧縮さ
れたデータ・セツトにエスケープ・ビツト・パタ
ーンを書くことによつてエンコードの際にこの変
化を表示することのどちらかが必要である。もし
エスケープ・パターンが使用されるなら、これに
続いて、単語バツフア１１から各キヤラクタが圧
縮されたデータ・セツトに書き込まれ、非圧縮キ
ヤラクタのストリングが別のエスケープ・ビツ
ト・パターンで完成される。前述のように、単一
バイト・バツフアが、通常の文字及びキヤラクタ
のすべてのコードを含む場合、エスケープ・ビツ
ト・パターンは不要である。単語の比較と、単語
のための単一バイト・バツフアの内容の間に一致
が見出されなかつた場合、バツフア中の単語をキ
ヤラクタ毎に圧縮されたデータ・セツトに書き込
むべきであると結論することだけが必要となろ
う。そして、単一バイト・テーブルの内容に対し
てキヤラクタ毎に比較することによつて単語の一
致が見出されないので、そのことが伸張プログラ
ム中で認識されることになる。しかし、キヤラク
タが前以て記憶されているときは、“キヤラクタ”
の一致が見出される。この技術はフローには示さ
れていないけれども、この説明から明らかであ
る。

第４Ｃ図のブロツク４３はまた、このルーチン
に含まれている検索の階層をも示す。もし単一バ
イト・テーブルが検索される唯一のテーブルでな
いなら、単語バツフアの内容が、ブロツク４５に
示されているように、ユーザーによつて選択され
た任意の２バイト辞書に対して比較される。もし
どの２バイト辞書でも一致が見出されないなら、
ブロツク４７で、３バイト辞書が使用されること
になつているかどうかが問われ、もしその答えが
イエスなら、一致が見出されるまで、使用中の３
バイト辞書に対して比較がなされるか、または、
一致が見出されない場合に、プログラムは、非圧
縮形式で単語を書くためにブロツク４４に戻る。

第４Ａ−１図のブロツク１８に戻つて、もし単
一バイト辞書またはテーブルが、圧縮すべき文書
の内容に基づき生成されるべきであるなら、すな
わち、もし考察中の文書のための特殊な辞書が生
成されるべきであるなら、ブロツク１９において
文書を開くことにより、すなわち文書の処理が単
語毎に実行され得るメモリ中の領域を初期化する
ことによつてプログラムが始まり、次にプログラ
ムはブロツク２０に進む。ここで文書が走査さ
れ、その文書内で見出された個々の固有の単語の
すべてについてリストがメモリ中に構築される。
この処理が完了すると、各単語の出現回数にその
単語のキヤラクタの長さを掛けることによつて文
書中の各単語に対する相対的な重みづけ得点が計
算される。こうして得られた得点表が大きさによ
つてソートされ、最大値（最高得点の単語）が、
（アルフアベツト、数字、特殊キヤラクタ及び制
御キヤラクタの割振り完了後に）単一バイト・テ
ーブル内に残つているビツト位置に割り振られ
る。ユーザーは、制御キヤラクタ等を妥当に選択
することによつて、単一バイト・テーブル中で何
個のビツト・パターンが利用可能となるかを定義
する必要があろう。これにより、256個の利用可
能なパターンのうちある個数が残される。次に、
圧縮されたデータ・ストリームを開始するため
に、ブロツク２８（第４Ａ−２図）で固有のヘツ
ダが書き込まれる。この後、ブロツク２９に示す
ように、ブロツク２６からの、単一バイト・テー
ブル中にあらわされたすべての単語の長さをあら
わす２バイト・パターンであるセグメント・メモ
リ位置マツプが続き、さらに辞書で使用されるべ
き単語の実際のリストが続く。

もし３バイト辞書または２バイト辞書が必要で
あると定義されるなら、ブロツク５２及び６２が
事象のシーケンスを記述する。圧縮ルーチンを呼
び出すユーザーによつて行なわれた辞書の特定の
選択が注目され、特に記述されている以外の選択
のセツトの場合、それが辞書構造として生成され
る。第４Ａ−１図ないし第４Ｆ図のフローチヤー
トは、単一バイト圧縮テーブル、単一バイト補助
圧縮テーブル、または任意のスタイルの２バイト
または３バイト辞書を書くための任意の可能性を
処理する。どの辞書を使用するかの選択は、完全
に、圧縮ルーチンを呼び出す人間の裁量の余地の
範囲にある。その結果の辞書の選択は、既に詳細
に説明したように圧縮されたデータ・ストリーム
を開始する情報ヘツダの構成に反映される。ヘツ
ダが構成されると、圧縮ルーチンは、各単語を、
利用すべき辞書の選択されたリストに対して比較
し、第４Ａ−１図ないし第４Ｆ図の命令に従つて
圧縮されたデータ・セツトを構成するために、あ
る解析パターンに従う。

一方、伸張は非常に簡単な動作であつて、第３
図を参照して説明される。これにおいては、アド
レス可能な主メモリ９中の区域として複数のテー
ブルＡ，Ｂ，Ｃ及びＤが定義される。テーブル
Ｄ，Ｃ，Ｂ及びＡにロードされる値は、圧縮され
たデータ・セツトに対応して受け取られたヘツダ
に応じて書き込まれる。ヘツダの解析により、マ
イクロプロセツサ中のプログラムが大容量記憶ま
たはメモリにアクセスし、第３図に示すようなテ
ーブルＤ，Ｃ，Ｂ及びＡを初期化するために必要
な値をフエツチすることが可能となる。

第３図に示された記述は、テキストの伸張が、
間接アドレス指定スキームによつて達成されつつ
あることを示す。伸張プログラムに関連づけられ
た４つのメモリ・テーブルＤ，Ｃ，Ｂ及びＡは次
のようにして定義される。すなわち、テーブルＤ
は、圧縮されたストリームの第１のビツト・パタ
ーンをテーブルＣ内のオフセツトの列にマツプす
るために使用される。言いかえると、テーブルＣ
は、ヘツダの第１のバイトに対応する可能なすべ
ての順列組み合わせを含み、テーブルＤは、ヘツ
ダＣを解析しテーブルＣ中でどのパターンが表示
されるべきかを選択するために使用される。テー
ブルＣは、各単語、句、制御シーケンス文字また
は数字の伸張を処理するために場合に応じて伸張
プログラム内のどのサブルーチンの選択が呼び出
されなくてはならないかを表示する転送ベクト
ル・テーブルである。言いかえると、テーブルＤ
は、ヘツダを解析しどの辞書が使用されるべきか
を解析するために、ヘツダに対する比較として使
用される。テーブルＣは、各タイプの伸張を処理
するために必要なサブルーチンに対する方向を含
む。

ヘツダ中に記述された各辞書の各固有のバージ
ヨンはまた、そのために定義された２個の追加的
なテーブルＡ及びＢをもつ。テーブルＢは、２バ
イト留保フイールドと、２バイト単語長フイール
ドと、４バイト・アドレス・フイールドを含む間
接アドレス・テーブルである。このように、テー
ブルＢは問題の辞書のためのセグメント・メモリ
位置である。第２のテーブルであるテーブルＡ
は、伸張された単語自体を含み、辞書単語リスト
である。

伸張ルーチンの場合ヘツダは、どの辞書構造が
記述されたかを判断するために解析される。ここ
で、主メモリ９中で利用可能な汎用レジスタ空間
の存在を仮定する詳細な例を与える。

もし単一バイト・テーブルのみが使用されるべ
きなら、ポインタは、主メモリ９内の汎用レジス
タＲ３中で任意に初期化される。ポインタは、圧
縮されたテキスト自体の第１のバイトが始まる地
点である圧縮されたテキスト中のバイト数を表示
するために初期化される。また、別の任意の汎用
レジスタ・メモリＲ４中に別のポインタが確立さ
れる。それは、伸張されたテキスト記憶領域が始
まるメモリ９の記憶空間中のアドレスを指定す
る。汎用レジスタ空間Ｒ５で任意に初期化される
別のポインタが、テーブルＤの開始が位置づけら
れているメモリ中でアドレスを指定する。別のポ
インタが、メモリ内のテーブルＣの開始を指定す
るために任意の汎用レジスタＲ６中で初期化され
る。さらに別のポインタが汎用レジスタＲ７中で
任意に初期化されてテーブルＢの開始を指定し、
別のレジスタＲ８が初期化されて、テーブルＡの
開始へのポインタを含む。これらのテーブルの値
が次に、例えば記憶８からフエツチされ、上述の
レジスタ中のポインタにより識別された地点で始
まる主メモリ中にロードされる。

次に伸張が始まる。すなわち、ポインタによつ
て記述された位置で始まる圧縮されたテキストか
ら１バイトがフエツチされ、第１図に定義された
受信バツフア１１としての汎用レジスタＲ９中に
配置される。言いかえると、Ｒ９には、レジスタ
Ｒ３の内容によつて表示された位置からそのバイ
トがロードされる。テーブルＤの開始アドレスは
次に汎用レジスタＲ９の内容に加えることができ
る。すなわち、Ｒ５の値がＲ９に加えられる。こ
れにより、Ｒ９によつて示された位置のバイトに
新しい値がもたらされ、その値は汎用レジスタＲ
１０にロードされる。これは、圧縮されたテキス
トの第１のバイト中で見出されたパターンの結果
として選択されたマツピング・バイトであり、そ
のバイトが、単語、制御キヤラクタ、特殊シンボ
ル、制御シーケンス、文字または数字などをあら
わすかどうかを決定する。

このマツピング・バイトは、４を掛けられ、す
なわちＲ１０は左へ２位置シフトされ、転送ベク
トル・テーブルであるテーブルＣのための開始ア
ドレスがこの積に加えられる。これにより、今や
レジスタＲ１０で示された位置において転送ベク
トル・テーブル中に位置が示されてなるサブルー
チンに対する動作の制御がもたらされる。サブル
ーチンのその部分は次に、マツピング・バイト・
テーブルで識別された特殊シンボル、制御シーケ
ンス、文字または数字を処理するために初期化さ
れる。特殊シンボル、制御シーケンス、文字、数
字等の各々は固有のサブルーチンをもつ。しか
し、単一バイト圧縮テーブル中の単語はすべて伸
張のための共通のサブルーチンを共有する。単語
伸張のためのサブルーチンはメモリ中に存在し、
単一バイト圧縮テーブル中に見出される単語を処
理する。そのサブルーチンは、Ｒ９に、Ｒ３によ
つて示された位置からのバイトをロードすること
によつて、圧縮されたテキスト・バイト・ストリ
ングから圧縮されたバイトをフエツチする。Ｒ９
中の圧縮されたバイトの値には８が掛けられ、す
なわち左へ３ビツト、シフトされ、テーブルＢの
開始アドレスがその結果の積に加えられる。言い
かえると、Ｒ７の内容がＲ９に加えられて、その
ことにより、伸張された単語自体の長さ及び位置
に対するポインタがもたらされる。その単語の長
さ及び位置は、Ｒ９の値よりも２つ大きい値と、
Ｒ９の値よりも４つ大きい値によつて、それぞれ
表示される。これらの値はそれぞれ、汎用レジス
タＲ１０及びＲ１１にロードされる。その結果
は、テーブルＡの辞書単語メモリから主メモリ９
中の伸張テキスト作業領域へ移動されることにな
る伸張された単語自体である。上述の例では、Ｒ
１０の内容によつて表示された長さをもつＲ１１
中に表示された位置からの単語がＲ４によつて表
示される位置へ移動される。ポインタは次に、次
の圧縮されたバイト、及び次の伸張されたテキス
ト・エントリの位置に対応して更新されることに
なる。上述では、レジスタＲ３が１だけ増分さ
れ、Ｒ１０の値がＲ４に加えられる。伸張プログ
ラムは次に、圧縮されたバイト・ストリングから
次のバイトをフエツチするために戻り、上述の処
理を反復する。

伸張ルーチンの制御は、フアイル終了制御キヤ
ラクタまたはシーケンスを認識した時点で、フア
イル終了サブルーチンに渡される。フアイル終了
サブルーチンは次に、ユーザーによつて選択され
た方法で圧縮されたデータ・ストリームを処分す
る。すなわち、圧縮されたデータ・ストリーム
は、マルチプレクサ２を介して遠隔位置と通信す
るために通信ネツトワーク・アダプタに出力さ
れ、または第１図のブロツク１中のデイスクまた
はカセツト上に記憶することができる。あるい
は、それはまた、後の検索のために、デイスク大
容量記憶８にロードすることもできる。

別の単一バイト圧縮テーブルを用いた伸張ルー
チンの場合、あるいは圧縮されたテーブル・バイ
ト・ストリング内で見出された制御シーケンスに
テーブル切替キヤラクタが表示されている場合、
テーブルＡ，Ｂ，Ｃ及びＤのための別のテーブル
値が記憶からアクセスされ、現存するＡ，Ｂ，Ｃ
及びＤのためのテーブル値に重なる作業メモリ空
間にロードされる。そして伸張ルーチンは上述の
ように進む。単一バイト・テーブルといくつかの
追加の辞書が記述されている場合、ヘツダが、ど
の単一バイト圧縮テーブル及び他のどの辞書が記
述されているか、及び、使用すべき他の記述され
た辞書毎のセグメントの数を表示する。Ａ，Ｂ，
Ｃ及びＤのための適当なテーブル値が次に所定の
外部記憶媒体からロードされ、上述した伸張プロ
グラムのアドレス空間に配置され、伸張処理は上
述のように進行する。各辞書の各セグメントは、
圧縮された単数または複数のバイトを、表示され
た辞書の表示されたセグメント内の適正な単語に
マツプするための自身の対応するサブルーチンを
もつ。例えば、２バイト辞書の場合、特定の２バ
イトの特定のセグメントのためのサブルーチン
が、単語辞書であるテーブルＡ内で伸張された辞
書を見出すために、適正なテーブルＢへのオフセ
ツトとしての単語の２バイト圧縮表現の第２のバ
イトを使用することになる。３バイト辞書の場
合、３バイト辞書の特定のセグメントのサブルー
チンが、選択したその特定の辞書のためのテーブ
ルＡに配置されている辞書内で伸張された単語ま
たは句を見出すために、その辞書のための適正な
テーブルＢへのオフセツトとしての単語の３バイ
ト圧縮表現の第２及び第３のバイトを使用する。

第５図を参照すると、圧縮されたテキストのバ
イト・ストリングの図式的な表示が示されてい
る。このとき、ヘツダは第６Ａ及び６Ｂ図で詳細
に扱われるので、表示されていない。第５図のラ
インＡにおいて、エスケープ・ビツト・パターン
が図示された第２のバイトであり、前述したよう
に、エスケープ・ビツト・パターンの使用を回避
することもできるけれども、それはこの例では使
用されている。エスケープ・ビツト・パターンの
後には、通常のEBCDICまたはASCIIコードであ
ることを除いてはコード化されていない最初のキ
ヤラクタが続く。というのは、それは、どの辞書
にも見出されなかつた単語をあらわすからであ
る。そして、何個の介在キヤラクタが出現し、ど
の辞書にも見出されなかつた単語の最後のキヤラ
クタのエンコードのあと、第２のエスケープ・ビ
ツト・パターンが続く。圧縮された単語が再びラ
インＢで始まり、これはラインＡの続きである。
ここでは単一バイトの圧縮された単語が先ずあら
われ、それに、２バイト辞書により圧縮された単
語が続く。それの２つのフイールドの情報は、所
与の２バイト辞書のセグメント数と、その辞書内
の単語の相対的位置をあらわす。これらの後に
は、この例では、さらに別の単一バイト圧縮単語
が続き、さらに多重スペース検出ビツト・パター
ンが続き、ラインＣで、検出された多重スペース
の数が続く。この後、３バイト辞書の圧縮された
単語のセグメント数と、３バイト辞書の識別され
たセグメント内のその単語の相対的位置を示す２
バイトとが続く。

エスケープ・ビツト・パターン以外にも、他の
制御パターンも定義され単一バイト圧縮制御テー
ブル内にロードされなくてはならない。バージヨ
ン切替制御パターンについて前述したが、これは
圧縮されたテキスト・ストリーム中で出会うと、
次のバイトが、使用されつつある辞書の新しいバ
ージヨン番号を表示するように意図されている。
それは、使用されつつある辞書が同一のタイプの
辞書の別のバージヨンに重なるべきときに、圧縮
ルーチン中でエンコードされる。テキスト中で空
白スペースが連続して複数あらわれるときは、最
良の圧縮のために、認識されたときに多重スペー
ス制御キヤラクタを必要とする別の事象である。
その後には、あらわれるべき空白スペースの数を
表示する別のバイトが続く。１バイト制御キヤラ
クタを考えると、次の第２のバイトにおいて制御
の256個のバージヨンを表示できることが明らか
である。こうして、辞書バージヨン切替制御キヤ
ラクタの場合、次のバイトが、同一の辞書の256
個のバージヨンのうちの任意の１つを記述するこ
とができる。これは、単一バイト辞書を他のバー
ジヨンで置き換えることによつて、１つのバイト
中であらわし得る単語の数を増加させることがで
きる。

以上の記載から、採用される辞書の数及びタイ
プに多くの変更がなし得る一方で、受信側に、圧
縮を行う際にどの辞書及びどのサイズの辞書が使
用されたかを識別するために、同一の基本ヘツダ
構成スキームが使用されることが見てとれる。同
様に、辞書中にエントリを確立するための使用度
合の重みづけられた頻度が、テキストを圧縮する
ためのきわめて有効な手段であることが示され
た。尚、“テキスト”自体は、アルフアベツト・
データでも、音声データでもよく、または記憶あ
るいは伝送のため凝縮すべき他の同様のデイジタ
ル・データ・キヤラクタ情報でよい。

Ｆ 発明の効果 以上のように、この発明によれば、用途に応じ
て複数の辞書の使用を可能ならしめたことによ
り、テキスト文書のきわめて効率的な圧縮が行な
われる。

【図面の簡単な説明】

第１図は、本発明に基づくテキスト圧縮及び伸
張システムの図式的ブロツク図、第２図は、辞書
と索引を含むセグメントへのメモリ空間の割り当
てを示す図、第３図は、第１図のプロセツサによ
り伸張動作を示す図、第４図は、第４Ａ−１図と
第４Ａ−２図の結合を示す図、第４Ａ図、第４Ａ
−１図、第４Ａ−２図、第４Ｂ図、第４Ｃ図、第
４Ｄ図、第４Ｅ図、第４Ｆ図は第１図のプロセツ
サによる圧縮動作を示す図、第５図は、圧縮され
たテキストのフオーマツトの典型的な例を示す
図、第６Ａ図、第６Ｂ図は、圧縮されたデータ・
レコード中のヘツダまたはプリアンブル区域にお
けるビツト位置の割り当てを示す図である。

Claims (1)

1. 【特許請求の範囲】 １ 非圧縮のコード化されたデータ・ストリーム
   を複数のユニツトに分離し、 上記複数のユニツトを、上記非圧縮のコード化
   されたユニツトに関連して記憶された各ユニツト
   毎に対応する圧縮されたコードをもつ複数の辞書
   のうちの少なくとも１つのユーザーが選択した辞
   書と比較し、 上記データの圧縮に使用される上記ユーザーが
   選択した辞書の各々の識別子を決定するための表
   示を含む圧縮されたデータ・ヘツダを出力し、 上記比較段階で一致が見出された場合に入来ユ
   ニツトに対応する圧縮されたコードを出力し、一
   致が見出されない場合に非圧縮のコード化された
   キヤラクタ・ストリームを出力する段階を有す
   る、 データ圧縮方法。