• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:

    公开号:WO1991013395A1
    申请号:PCT/JP1991/000252
    申请日:1991-02-26
    公开日:1991-09-05
    发明作者:Shigeru Yoshida；Yasuhiko Nakano；Yoshiyuki Okada；Hirotaka Chiba
    申请人:Fujitsu Limited；
    IPC主号:G06T9-00
    专利说明:
    [0001] 明 細 書 データ圧縮および復元の方法および装置 技 術 分 野
    [0002] 本発明はデータ圧縮および復元の方法、 特にユニバーサル 符号化用の増分分解形の符号化に用いられる L Z W方式
    [0003] (Lempe l-Z i v- We l ch方式） のデータ圧縮および復元の方法に 関する。
    [0004] 本発明による方法および装置は例えば、 新聞製版システム と して電子計算機化されたタィプセッティ ング（CTS) におけ る画像データ圧縮システム、 電子計算機システムのフ ァ イ ル 装置におけるフアイル圧縮、 例えば磁気ディスク装置に格納 されるデータ圧縮、 等に適用可能である。 従 来 技 術
    [0005] 従来の L Z W方式のデータ圧縮方法は、 データ圧縮のュニ バーサル性が重要視され、 辞書の状態として、 第 1文字のみ または全一文字のみを登録した空白に近い状態からデータの 符号化が開始されるようになっている。
    [0006] そのため、 従来の L Z W方式のデータ圧縮方法は、 入力さ れたデータの最初の部分において学習量が小であり、 辞書へ 登録される文字列の数が小であり、 したがって圧縮率が低い という問題点がある。
    [0007] L Z W方式の符号化においてユニバーサル性は重要である。 しかし種々のデータのうち入力されたデータとして特定の種 類だけ特に多く出現するときは、 辞書は必ずしも空白に近い 状態から符号化する必要はないという点が考慮されるべきで ある。 このことは L Z W方式の復号についても同様である。
    [0008] また、 従来の L Z W符号では、 入力文字列の中を相異なる 文字列に分けて符号化するとき、 現在符号化中の各文字列は 以前の文字列とは独立に出現するとして符号化する形をとつ ている。
    [0009] 従ってこの方法は、 文字列中の各文字が以前の文字と独立 に出現する情報源、 すなわち無記憶情報源、 の場合は問題が ない。 しかし、 実際の文章など、 多くのデータは以前に出現 した文字に依存して出現する情報源、 すなわち記憶をもつ情 報源、 とみなされるため、 従来の L Z W符号化では文字列が 出現する履歴を十分利用できておらず、 データ圧縮後も文字 列の出現の従属性については冗長性が残る問題点があった。
    [0010] なお、 本発明の分野においては、 データの 1 ヮ一ド単位が 文字と称され、 データが複数ワー ド連続したものを文字列と 称する。
    [0011] 従来の L Z方式 （Lempe l -Z i v方式） または L Z W方式の増 分分解形のデータ圧縮および復元の方法は、 例えば、 特公昭 63 - 56726 号公報、 米国特許第 446465号明細書、 米国特許第 4558302号明細書等に記載されている。 発明の開示
    [0012] 本発明の 1つの目的は、 L Z W方式のデータ圧縮および復 元用の符号化および復号において、 入力されたデータの最初 の部分においても圧縮の度合いが低下しないようにし、 それ により増分分解形のデータ符号化における圧縮率を向上させ る と ((し め る 0
    [0013] 本発明の他の 1つの目的は、 増分分解形のデータ符号化に おいて、 参照辞書の規模を犬にしても圧縮の度合いが低下し ないようにし、 それにより増分分解形のデータ符号化におけ る圧縮率を向上させることにある。
    [0014] 本発明の他の 1つの目的は、 符号化が行われた直前文字列 の最終の文字との従属関係に基づく索引を用い、 複数辞書の うちの 1つを指定して符号化および復号を行うにあたり該従 属関係を統合し、 複数辞書の初期登録が簡単であるようにし、 データ符号化の効率を向上させることにある。
    [0015] 本発明の他の 1つの目的は、 直前の文字列の最終の文字の ような、 直前の文字列との関係において現在の文字列の符号 を決定し辞書に登録するにあたり、 符号化されるべき文字の 部分列に対し直前の文字列の最柊の文字との従属関係を辞書 に導入し、 文字列間の冗長の度合いを低減させ、 それにより データ符号化における圧縮率を向上させることにある。
    [0016] 本発明においては 1つの形態として、 入力された文字列を 辞書に登録された符号化ずみの部分列のうち、 最長の一致を 示す部分列の参照番号を指定するとともに符号語として得ら れた参照審号に 1文字が付加された部分列に新たな参照蕃号 を付与して該辞書に登録することにより符号化を行い、 該部 分列の参照番号により表わされる符号語により該辞書に登録 されている部分列を探索してもとの部分列を復元するととも に以前に処理された符号語に今回復元された部分列の先頭文 字が付加された部分列に新たな参照審号を付与して該辞書に 登録することにより復号を行う、 増分分解形のデータ圧縮お よび復元方法において、
    [0017] サンプルのデータを対象とする符号化により辞書登録され た部分列のうち出現の頻度の大なる部分列のみを、 符号化済 みの部分列であるとの判断のもとに、 該辞書に初期値として 登録することにより、 該辞書の初期化を行う、
    [0018] ことを特徵とするデータ圧縮および復元方法、 が提供される c また、 本発明においては 1つの形態として、 入力された文 字列を辞書に登録された符号化ずみの部分列のうち、 最長の 一致を示す部分列の参照審号を指定するとともに符号語とし て得られた参照審号に 1文字が付加された部分列に新たな参 照審号を付与して該辞書に登録することにより符号化を行い， 該部分列の参照番号により表わされる符号語により該辞書に 登録されている部分列を探索してもとの部分列を復元すると ともに以前に処理された符号語に今回復元された部分列の先 頭文字が付加された部分列に新たな参照番号を付与して該辞 書に登録することにより復号を行う、 増分分解形のデータ圧 縮および復元方法において、
    [0019] 連続する 2つの部分列の最初の部分列の最終の文字ごとに. または最終の文字による群ごとに次位の部分列を登録して登 録辞書を作成し、 該最終の文字または最終の文字による群ご とに、 登録される部分列の登録番号を付与し、 該登録審号に もとづいて符号化されるべき部分列の符号語を作成し、 さらに、 該作成された符号により構成されたデータから、 複 号された部分列の前位の部分列の最终の文字または最終の文 字による群ごとに辞書の復元を行い、 該復元された辞書を用 いて、 該複号された部分列の前位の部分列の最終の文字と今 回入力の符号から、 入力された符号を文字の部分列に複号す ることを特徵とするデータ圧縮および復元方法が提供される c 図面の簡単な説明
    [0020] 第 1図は従来形の増分分解形の L Z W方式のデータ圧縮お よび復元方法を説明する図、
    [0021] 第 2図および第 3図は従来形の増分分解形の L Z W方式の 符号化および復号の過程を示す図、
    [0022] 第 4図は本発明の 1つの形態におけるデータ圧縮および復 元方法用のシステムの例を示す図、
    [0023] 第 5図は第 4図のシステムに用いられるプログラム用の記 憶装置およびデータ用の記憶装置の構成を示す図、
    [0024] 第 6図は第 4図のシステムの動作を説明するフローチヤ一 ト図、
    [0025] 第 7図および第 8図はいずれも第 6図のフローチャー ト図 に闋連する動作を説明するフローチャー ト図、
    [0026] 第 9図はサンプルのデータによる辞書初期値の作成処理を 説明するフ口一チャー ト図、
    [0027] 第 10図は辞書圧縮の処理を説明するフ σ —チャー ト図、 第 11図は符号化処理を説明するフローチャー ト図、 第 12図は復号処理を説明するフ ロ ーチャー ト図、
    [0028] 第 13図は追加コ一ドの登録を説明する図、
    [0029] 第 14図は部分列に対応して記憶装置へ登録されるデータを 説明する図、
    [0030] 第 15図は復号操作を説明する図、
    [0031] 第 16図は本発明の他の 1つの形態におけるデータ圧縮およ び復元方法用のシステムの例を示す図、
    [0032] 第 17図は圧縮符号生成の過程を説明するフ ロ ーチャ ー ト図、 第 18図は最適符号変換の例を説明する図、
    [0033] 第 19図は参照辞書の単位の最適符号の設定の例を説明する 図、
    [0034] 第 20図は最適符号を適用した圧縮符号の例を説明する図、 第 21図は文字グループ間での遷移回数の測定の結果を説明 する図、
    [0035] 第 22図は文字グループ間での遷移回数の順位を説明する図、 第 23図は最適符号の例および遷移コ一ドによる符号語の例 を説明する図、
    [0036] 第 24図は本発明の他の 1つの形態におけるデータ圧縮およ び復元方法用のシステムの例を示す図、
    [0037] 第 25図は第 24図のシステムにおけるプログラム用の記憶装 置およびデータ用記憶装置の構成を示す図、
    [0038] 第 26図は符号化のァルゴリズムを説明する図、
    [0039] 第 27図は復号化のアルゴリズムを説明する図、
    [0040] 第 28図は本発明の他の 1つの形態におけるデータ圧縮およ び復元方法用のシステムの例を示す図、 第 29図は直前の文字列の最絡の文字を根とする辞書の木を 説明する図、
    [0041] 第 30図はデータ圧縮のコ一ドの文字列への復号を行う構成 を示す図、
    [0042] 第 31図は符号化用の装置の例を示す図、
    [0043] 第 32図は符号化用の装置の動作を説明するフ ロ ーチャー ト 図、
    [0044] 第 33図および第 34図は全体辞書の例および個別辞書の例を 示す図、
    [0045] 第 35図は個別辞書の木の例を示す図、
    [0046] 第 36図は符号語の例を示す図、
    [0047] 第 37図は復号のための装置の例を示す図、
    [0048] 第 38図 （A )， ( B ) 、 および （C ) は符号化の過程を説明 するフ ロ ーチ ヤ一ト図、
    [0049] 第 39図は辞書の木の例および文字列の符号化の例を説明す る図、
    [0050] 第 40図は本発明によるデータ圧縮および復元用の装置につ いての説明を抄録として記述するための図である。 発明を実施するための最良の形態
    [0051] 好適な実施例の説明に先立ち、 従来の増分分解形のデータ 圧縮システムを第 1図について、 従来の L Z W方式による符 号化処理の過程を第 2図について、 復号処理の過程を第 3図 について、 それぞれ説明する。
    [0052] 第 1図のデータ圧縮システムは圧縮器 1および辞書 2を有 し、 文字列、 例えば、 文字 a , b , cのみから成る、 ababcbababが圧縮器 1 に入力される。 入力された文字列につ いて、 単独文字の部分例 （ス ト リ ング） a ， b , cのそれぞ れは初期値として蕃号 1 ， 2 ， 3に対応して辞書 2に登録さ れる。 文字の連続からなる部分列 ab， ba， abc, cb, bab, baba, aa， aaa, aaa については学習して審号 4〜 12に対応 して辞書 2 に登録される。 このように部分列の登録された辞 書 2に対して圧縮器 1 は検索を行う。 圧縮器 1 において辞書 2に登録された部分列を用いて圧縮が行われ、 その結果が圧 綰データとして出力される。
    [0053] 従来の L Z W方式の符号化処理は、 書き替え可能な辞書を 持ち、 入力された文字列の中を相異なる文字列すなわち部分 列に分け、 この文字列を出現した順に参照審号を付与して辞 書に登録すると共に、 現在入力される文字列を辞書に登録し てある最長一致の文字列の参照番号で表して符号化するもの でめる。
    [0054] 第 2図の L Z W方式の符号化処理では、 まずステップ S 1 で予め辞書に全文字につき一文字からなる文字列を初期値と して登録してから符号化を始める。 S 1の符号化は入力した 最初の文字 Kにより辞書を検索して参照審号 ωを求め、 これ を語頭文字列（pref i x st r i ng) とする。 次に S 2で入力デー 夕の次の文字 Kを読み込み、 S 3で全ての文字入力の読込み が終了したか否か点検した後、 S 4に進んで S 1を求めた語 頭文字列 ωに S 2で読み込んだ文字 Kを加えた " Κ " が辞 書にあるか否か探索する。 S 4で文字列 " Κ" が辞書になければ、 S 6に進んで S 1で求めた文字 Κの参照番号 ωを ωをあらわすコー ド code (ω) と して出力し、 また文字列 "ω Κ" に新たな参照 番号を付与して辞書に登録し、 更に S 2の入力文字 Κを参照 審号 ωに置換すると共に辞書ァ ド レス ηを増分して S 2に戻 つて次の文字 Κを読み込む。
    [0055] 一方、 S 4で文字列 "ω Κ" が辞書にあれば S 5で文字列 "ω Κ" を参照審号 ωに置換し、 再び S 2に戻って S 4で文 字列 " ω Κ " が辞書から探索されることができなく なるまで 最長一致の検索を続ける。
    [0056] 第 3図の復号処理は第 2図の符号化の逆の操作を行なう。 第 3図の復号では、 符号化時と同様に予め辞書に全文字に つき一文字からなる文字列を初期値として登録してから復号 を始める。
    [0057] まず S 1で最初の符号すなわち参照番号読み込み、 現在の コー ドを OLDcode とし、 最初の符号は既に辞書に登録された 一文字の参照番号いずれかに該当することから、 入力符号コ — ドに一致する文字コー ド code (K) を探し出し、 文字 Kを 出力する。
    [0058] なお出力した文字 Kは後の例外処理のため FINchar にセッ ト しておく。
    [0059] 次に S 2に進んで次の符号を読み込んでコ一ドに INcodeと してセッ トする。 S 3で新たな符号があるか否か、 すなわち 符号入力の終了の有無を点検して S 4に進み、 S 3で入力さ れた符号コ一ドが辞書に定義すなわち登録されているか否か 点検する。 通常、 入力した符号語は前回までの処理で辞書に 登録されているため、 S 5に進んで符号コ一ドに対応する文 字列コ一ド code {ω Κ) を辞書から読み出し、 S 6で文字 Κ を一時的にスタ ッ ク し、 参照番号 code ( ω ) を新たな符号コ ー ドとして再度 S 5に戻り、 この S 5 , S 6の手順を参照番 号 ωがー文字 Kに至るまで反復し、 最後に S 7に進んで S 6 でスタ ッ ク した文字を F0(Last In First Out) 型式で出力 する。 同時に S 7 において、 前回使った符号 ωと今回復元し た文字列の最初の 1文字 Κを組 " ω， Κ" と表した文字列に、 新たな参照審号を付与して辞書に登録する。
    [0060] 本発明の 1つの形態におけるデータ圧縮および復元方法用 のシステムの例が第 4図に示される。
    [0061] 第 4図のシステムにおいて、 符号化時には、 入力文字列を 辞書に登録された既に符号化済みの部分列の内、 最長一致の 部分列の参照蕃号で指定して符号化すると共に参照番号とし て指定された符号語に次の 1文字を付加した部分列に新たな 参照番号を付加して辞書 105 に登録し、 復号時には、 部分列 の参照審号で指定された符号語を辞書 105 に登録された部分 列の検索により元の部分列を復元すると共に、 前回復元され た符号語に今回復号された部分列の最初の 1文字を付加した 部分列を新たな参照審号を指定して辞書 105 に登録する増分 分解形の符号としての L Z W符号を用いたデータ圧縮方式が 対象とされる。
    [0062] 第 4図のシステムにおいては、 辞書 105 の初期化時に、 所 望のサンプルの文字列を対象とした前記符号化により辞書登 録された部分列の内、 出現頻度の高い部分列を既に符号化済 みの部分列と見做して前記辞書 105 に初期値として登録する, 第 4図のシステムにおいては、 種々の種類のデータの内、 入力されたデータとして特定の種類だけ特に多く現れるデー タをサンプルのデータとして準備し、 第 6図に示されるよう に、 出現頻度の高いサンプルのデータについて L Z W符号化 により辞書を作成し （ S 1 ) 、 作成辞書の中の出現頻度の高 い部分列のみを残すように辞書を圧縮して辞書の初期値を作 り出す （ S 2 ) 。
    [0063] そして第 7図、 第 8図に示されるように、 サンプルのデ一 タの学習により求めた初期値を辞書に登録する初期化処理を 行なった後に、 L Z W符号化及び L Z W復号を行ない、 入力 データの初めの部分でも十分な量の部分列の登録が辞書に得 られていることから、 圧縮率が向上する。
    [0064] 具体的には、 サンプルのデータの L Z W符号化の際に、 辞 書の参照蕃号毎に力ゥンタを設け、 各参照審号が符号化時に 使われた回数を計数するようにし、 計数値の小さい文字列を 辞書から削除し、 高頻度で出現する文字列のみ辞書に残した 辞書を求める。 そして、 予め記憶装置に取り出しておいた高 頻度の文字列を初期値として辞書に登録した後、 符号化或い は復号する方法、 または、 予め作成した高頻度の文字列を初 期値と して辞書の先頭に書き替えをしない固定部分として設 定しておき、 符号化或いは復号する方法のいずれかの方法で 符号化または復号を行う。
    [0065] 第 4図のシステムに用いられるプログラム用の記憶装置お よびデータ用の記憶装置の構成が第 5図に示される。
    [0066] 第 5図の構成において、 112は制御手段としての C P Uで あり、 CPU112に対してはプログラムメ モ リ 114 とデータメ モ リ 126 が接続される。
    [0067] プログラムメ モ リ 114 には制御用プログラム 116 、 L Z W 符号を用いた最長一致の検索を行なう最長一致検索用プ口グ ラ ム 118 、 入力された文字列を L Z W符号に変換する符号化 用プログラム 120 、 符号化用プログラム 120 でし Z W符号に 変換された符号を元の文字列に復元する復号用プログラム 122 、 及び所望のサンプルのデータを対象とした L Z W符号 化で得られた辞書登録の内の出現頻度の高い部分列を辞書初 期值として作り出す辞書初期値作成用プログラム 124 を備え 。
    [0068] 一方、 データメ モ リ 126 には、 これから符号化しようとす る文字列、 或いはこれから復号しょうとする符号列を格納す るデータバッ ファ 128 と、 L Z W符号を対象とした符号化及 び復号の際に逐次作成されながら使用される辞書 110 を備え る。
    [0069] 第 5図の構成におけるデータ圧縮が下記に説明される。 まず、 符号化及び復号に先立ち、 データメ モ リ 126 のデー タバッファ 128 に対しては所望のサンプルのデータが格納さ れる。 このサンプルのデータ と しては種々の入力されたデ一 夕の内、 統計的に出現頻度が高い特定種類のデータを使用す る。 データバッ ファ 128 にサンプルのデータが格納された状 態で CPU112は制御用プログラム 116 による制御のもとに辞書 初期値作成ソ フ ト 124 を起動し、 辞書初期値作成処理を行な う。 具体的には、 辞書初期値作成用プログラム 124 は符号化 用プログラム 120 を使用してデータバッファ 128 のサンプル のデータを対象とした L Z W符号化処理を実行し、 符号化済 み文字列に参照番号を付加したデータを辞書 110 に順次登録 していく。 この辞書登録に際しては参照審号毎に力ゥンタが 設けられており、 符号化時に、 或る参照番号の文字列を経由 した最長一致の検索が行なわれると、 その都度カウンタが増 分され、 各文字列の出現頻度が計数される。
    [0070] サンプルのデータを対象とした Z W符号化が終了すると、 データメ モ リ 126 に得られた辞書 110 の内、 カウンタのカウ ン トがしきい値 T以上出現した文字列のみを残すように辞書 110 を圧縮することで辞書初期値を作成する。
    [0071] このように作成された辞書初期値はデータメモリ 126 の特 定の領域に保存しておき、 符号化または復号を行なう初期化 処理の際に辞書 110 に登録する。 また、 辞書初期値を符号化 及び復号に使用する辞書 110 の先頭部分にそのまま残してお き、 この辞書初期値の部分を書き替え禁止領域とするように することが可能である。
    [0072] 次に、 サンプルのデータによる辞書初期値の作成処理が第 9図を参照して説明される。
    [0073] まずステップ S 1でサンプルのデータを構成する文字列の 第 1審目の文字を舍むように辞書を初期化する。 すなわち、 第 1審目の文字コ一ド i を辞書のァ ド レス i に登録する。 次 に、 辞書への現在の登録文字列の数を示す力ゥ ン ト πを一文 字全体の文字数 nとし、 続いて入力された最初の一文字 Kの 辞書検索で得られた参照番号 ωを、 語頭文字列 ωとする。
    [0074] ステップ S 1の初期化にあっては、 サンプルのデータを構 成する文字列の全一文字を参照番号を付けて辞書に登録する ようにすることが可能である。
    [0075] 次に S 2に進み、 次の入力文字 Κを読み込み、 S 3で文字 Κがあるか否か、 すなわち入力された文字列の読込みが終了 したか否か点検して S 4に進む。 S 4においては、 第 1蕃目 に入力された文字の参照番号 ω、 即ち語頭文字列 に 2蕃目 の入力された文字 Κを組み合わせた文字列 "ω Κ" が辞書に あるか否か検索する。
    [0076] このとき、 2文字目までしか入力していないので辞書には 文字列 κω Κ" が存在せず、 従って S 5に進み、 文字列 αω Κ" を辞書ア ド レス ηに登録し、 2番目の文字 Κを語頭 文字列 ωに置き換え、 更に参照審号 ωの出現頻度を示すカウ ン ト cnt(n ) を作成して零にリ セ ッ ト し、 辞書への現在登録 している文字列の数を示す力ゥン ト nを増分する。
    [0077] S 4で文字列 "ω Κ" が辞書に存在した場合には S 5に進 み、 文字列 "ω Κ" を語頭文字列 ωに置換し、 それにより参 照審号 ωの文字列が使用されたことになるので、 参照番号 ω の文字列を示すカ ウ ン ト cnt((y) を増分する。
    [0078] 以上の S 2〜 S 6にわたる処理の反復により入力された全 文字の処理が終了すると S 3から S 7に進み、 その時点で得 られた辞書の最終ァドレス nと辞書の内容を記憶装置に書き 込んで一連の辞書作成処理を終了する。 このようにして作成された辞書について、 高頻度の文字列 のみを辞書に残す辞書圧縮の処理のフローチャー トが第 10図 に示される。
    [0079] まず S 1で第 9図の処理で得られた辞書の最^ァド レス n と辞書の内容をメモ リ に書き込み、 辞書ァ ド レス i を零にリ セ ッ トする。
    [0080] 続いて S 2で辞書ア ド レスを増分し、 S 3で最終ア ド レス に達したか否か点検した後、 S 4に進んで辞書ァ ド レス i の カウ ン ト cnt ( i ) が予め定められた出現頻度を示すしきい値 Tより小さいか否か点検する。
    [0081] もし、 カウ ン ト cnt ( i ) がしきい値 Tより小さければ S 5 に進んで、 現在の辞書ァ ド レス i を削除して次の辞書ァ ドレ ス j に置き換える削除処理を行なう。 次いで S 6に進み、 削 除された辞書ァ ド レス i に続く次の辞書ァ ド レス 〗 が最終ァ ドレス n以内にあるか点検し、 最終ァ ド レス n以内にあれば S 7 に進んで、 辞書ァ ド レス i 以降に i = より大きい参照 審号 ωをもつ文字列が存在するか否か点検する。
    [0082] 削除された辞書ァ ド レス 〗 以降に参照審号 ωより大きい参 照審号をもつ文字列が存在したならば S 8に進んで、 文字列 の中の参照番号 ωの値を減分により 1つ減らし、 S 9に進ん で辞書ァ ド レス j の文字列 " ω K " を 1つ前の辞書ァ ド レス j 一 1 に登録する。 そして、 処理が済んだ辞書ァ ド レス j を 次の処理のために j + 1 と増分して S 6に戻り、 辞書ァ ド レ ス j が最終ァ ド レス nを越えるまで S 6 . S 7 . S 8及び S 9の処理を反復する。 すなわち、 しきい値 Tより小さい出 現頻度の文字列を削除した場合には、 削除した文字列のァド レス以降に存在する文字列の中の参照審号を 1 つ減らし、 且 つ登録ァド レスを 1つ変位させる処理を反復する。
    [0083] S 6〜S 9の処理が終了すると S 6から S 10に進み、 文字 列を 1つ削除したことから最終ァド レス nを 1つ減分し、 再 び S 2に戻って辞書ア ド レス i を増分して次の文字列に対す る出現頻度の計数僚の点検を行ない、 S 3で最終ア ド レス n が判別するまで反復する。
    [0084] S 3で最終ァド レス nへの到達が判別されると S 11に進ん で辞書の最終ァド レス nと辞書の内容を記憶装置に書き込み、 これにより圧縮された辞書初期値の形成が完了する。
    [0085] このようにして得られた辞書初期値を使用した符号化処理 のフローチャー トが第 11図に示される。
    [0086] 符号化においては、 まず S 1で予めサンプルのデータに基 づいて生成されている辞書初期値を記憶装置から読み出し、 読み出した辞書の最終ァ ド レス IIと辞書の内容を辞書として 使用するメモ リ に書込む。 この辞書初期値の書込みが従来の 符号化処理と異なる点である。 続いて S 1 においては入力し た最初の文字 Kにより辞書を検索して一致した文字列の参照 番号 ωを取り出して語頭文字列とし、 S 2で次の文字 Κを入 力し、 S 3で入力文字の終了の有無を点検した後、 語頭文字 列 ωに今回入力した文字 Κを組み合われた文字列 " ω Κ " が 辞書にあるか否か点検する。
    [0087] 従来の方法においては、 入力データの初期段階で文字列 ( ω Κ ) が辞書に存在する割合は少なかった。 第 9図のフロ 一においては、 S Iでサンプルのデータの学習により得られ た辞書初期値としての文字列を既に格納しているため、 S 4 で文字列 " ω Κ" が辞書にあることが判別されて S 5 に進み、 文字列 "ωκ" を語頭文字列 ωに置換して再び S 2に戻り、 以下、 辞書の検索結果が得られなくなるまで最長一致の部分 列を検索する処理を反復する。 この結果、 入力データの参照 についても辞書から検索できる部分列の連鎖数が増加し、 圧 縮率が向上する。
    [0088] 勿論、 S 4で部分列 （ω Κ) が辞書になかったときは S 6 に進んで、 そのときの参照番号 ωを符号語 code ( ω ) として 出力し、 今回処理した参照番号 ωに次の文字 Κを付加した文 字列 " ω Κ" を、 新たな参照審号を付与して辞書に登録し、 1文字 Κを新たな語頭文字列に置換し、 S 2に戻って新たな 部分列の最長一致を求める符号化処理を行なう。
    [0089] 復号処理のフ ローが第 12図に示される。 S 1 で第 9図、 第 10図のフ口一における処理で得られた辞書初期値をメモリか ら読み出して、 読み出した辞書の最終ア ドレス ηと辞書の内 容を復号時に辞書として使用するメ モ リ に書き込む。
    [0090] S 1で既に得られた辞書初期値の辞書の登録が終了すると、 S 2で最初の符号を読み取り、 S 3で符号入力の読み取りが 全て終了したか否か点検して S 4に進み、 符号が辞書に定義 されているか否か点検する。 S 4で辞書に定義されているこ とが判別されると S 5に進み、 符号語に対応する参照審号を もつ文字列 " ω Κ " を読み出し、 文字列 " ω Κ " が得られれ ば S 6 に進んで文字 Κをスタ ッ ク し、 文字 Κを除いた参照番 号 の検索により次の文字列 " Κ " を S 5で求め、 参照蕃 号 ωが文字 Κに帰着するまで S 5 , S 6の処理を行なった後、 S 7 に進み、 S 6でスタ ック した一連の文字を L I F0型式で出 力する。
    [0091] S 4で符号が辞書に定義されていない場合の S 8における 例外処理は、 S 1 における辞書初期値の登録により発生頻度 がかなり低減しており、 ほとんど例外処理に移行することな く符号から文字列を復号することが可能となる。
    [0092] このように、 復号については入力した最初の符号から辞書 に文字列として既に登録されているため、 従来の復号にあつ ては、 最初、 まず 1文字から復元していたが、 第 12図のフロ 一における復号においては最初の符号から文字列に復元する なお、 第 11図、 第 12図の符号化及び復号の処理にあっては、 辞書の初期値を記憶装置から登録してから符号化あるいは復 号を始めるようにしているが、 これに限らず、 学習により得 られた初期値を辞書の先頭に格納して書き替えしない禁止部 分として設定して、 辞書初期化による消去を禁止することで 符号化あるいは復号するようにすることが可能である。
    [0093] また、 前記においては辞書の初期値をサンプルのデータを 構成している 1つの文字列から作成しているが、 これに限ら ず、 これ以外に複数個のサンプルのデータをつないだものを 入力して辞書の初期値を作成するようにすることが可能であ る。 また、 1つのサンプルのデータから作成した初期値を登 録した後に、 次のサンプルのデータを使用して辞書を作り、 この辞書の中の高頻度の文字列のみを取り出すという処理を 反復し、 累積して複数のサ ンプルのデータに共通な辞書の初 期値を作成するようにすることが可能である。
    [0094] 本発明の他の形態におけるデータ圧縮および復元方法用の システムの例が第 16図に示される。
    [0095] 第 16図のシステムにおいて、 201は文字列供給部、 202は 入力された文字列を一時格納する入力バッ フ ァ、 203は符号 化装置であって、 入力データを参照辞書に照合する参照辞書 照合部 209 、 符号語作成部 210 、 文字列を参照辞書に登録す る参照辞書登録部 211 、 参照辞書単位の最適符号を定める最 適符号変換部 212 、 参照辞書単位ごとに登録文字数を計数す る登録文字列数計数部 213 、 参照辞書単位の最適符号を設定 する最適符号設定部 214 とよりなるもの、 204は参照辞書単 位を表わす符号を最適値に設定する前に仮に定める参照辞書 単位の仮符号設定部、 205は複数の参照辞書単位より構成さ れる参照辞書であって、 16グループの参照辞書単位で構成し た場合について例示されたもの、 で、 例えば、 参照辞書単位 205 - 1 は文字列の先頭文字が aよりなるもの、 参照辞書単 位 205— 2は文字列の先頭文字が bよりなるもの等の異なる 文字グループについて文字列に対応させて文字列の符号語を 登録してあるもの、 206は圧縮された入力文字列の符号を出 力する圧縮符号出力部である。
    [0096] 第 16図のシステムの動作に関して、 符号語の形式について 仮符号から最適符号への変換の例が第 18図に示される。 符号 語形式 217 について、 参照辞書単位の符号 218 と参照辞書単 位の登録位置を示すィ ンデッ クス 219 からなるものが示され る。 参照辞書単位の仮符号による符号語の形式 220 について、 参照辞書単位の蕃号が最適値に変換された後の符号語 221 が 示される。
    [0097] 第 16図のシステムの動作は次の通りである。
    [0098] まず、 入力された文字列 201 は入力バッ フ ァ 202 に格納さ れ、 参照辞書照合手段により、 文字列を参照辞書単位
    [0099] 205— 1 , 05 - 2 , … 205— 16を参照して過去に登録され た文字列のうちから最大長の文字列を選択する。
    [0100] そして、 符号語作成部 210 は選択した文字列の参照辞書単 位の審号 218 と選択した文字列の参照辞書単位での登録位置 を示すィ ンデッ クス 219 よりなる符号語形式 217 を作成する c その際、 1回に送信する入力文字列の全ての文字について圧 縮処理が終わるまでは、 参照辞書単位の識別符号は仮符号設 定手段 204 の設定した仮の符号を設定しておく。
    [0101] そこで、 参照辞書登録部 211 は選択された過去に登録され た最大文字列に一致する入力文字列部分に次の一文字を付加 した文字列を新たな文字列成分として参照辞書単位に登録す o
    [0102] ここで、 登録文字列数計数部 213 は、 各参照辞書に文字列 が登録される度に登録文字列数すなわち例えば aで始まる辞 書に登録されるデータの個数もしく は任意の文字列の一つ前 の文字列の最 ^文字の属する参照辞書単位から続く文字列の 属する参照辞書単位へ遷移する回数を各参照辞書単位ごとに 計数する。
    [0103] 1回に送信する全入力文字について圧縮処理がなされると 最適符号設定部 214 は各参照辞書単位に登録されている登録 文字列数をまたは、 参照辞書間の上記遷移回数より遷移確率 を求め、 登録文字列数が大または遷移確率が高い参照辞書単 位に付す符号語については登録文字列数が小または遷移確率 の低い符号語より短い符号を設定する。
    [0104] このように求められた最適符号により、 最適符号変換部 212 は参照辞書単位の仮符号により作成した符号語を最適符号に 変換する。
    [0105] 参照辞書単位の仮符号により表わした符号語の例 220 が示 されている。 また、 符号語 220 を参照辞書単位の最適符号に 変換した例 221 が示されている。
    [0106] 圧縮符号生成過程のフロ ーチャー トが第 17図に示される。 第 17図において、 は登録文字列であり、 Κは入力された 文字列のうちの参照辞書の登録文字列 ωに一致する部分の次 の文字シンボルを表わす。 過程は下記のとおりである。
    [0107] ( S 1 ) 参照辞書を初期化する。
    [0108] ( S 2 ) 参照辞書単位に、 例えば、 均等に仮符号を付与する。 続く処理は入力された文字列の先頭文字を処理する場合
    [0109] (第 1 ) と第 2文字目以降の場合 （第 2 ) とに分けて説明さ れる。
    [0110] (第 1 ) 入力文字列の先頭文字を読み取る処理。
    [0111] ( S 3 ) 入力文字の先頭文字を読み取る。
    [0112] ( S 4 ) 読み取った文字の次に文字があるかないか判断し、 あれば、 その文字を読み取る。 次に （ S 4 ) において無しに 進む場合は、 全入力文字を読み取って圧縮処理を終了した場 合であるから、 一文字のみを伝送する場合をのぞいて、 通常 は （ S 5 ) に進む。
    [0113] ( S 5 ) 入力文字列の先頭文字を読み取るステップでは当然 辞書に書き込みはないので （ S 7 ) に進む。
    [0114] ( S 7 ) 参照辞書に登録文字列、 いまの場合は入力された文 字列の先頭文字である、 を対応させて、 符号を登録する。
    [0115] ( S 8 ) 文字列を登録した文字列数あるいは 1つ前の文字列 の最終文字の属する参照辞書単位から続く文字列の属する参 照辞書単位へ遷移する回数を計数するため、 登録数をプラ ス 1する。 そこで、 （ S 3 ) に戻って、 次の文字を読み取り、
    [0116] ( S 4 ) を繰り返す。
    [0117] (第 2 ) 入力文字列の第 2蕃目の文字以降の処理。
    [0118] ( S 3 ) 次の文字 Kを読み取る。
    [0119] ( S 4 ) で文字がない場合は、 伝送する文書の最終文字まで， すべて処理した場合である。
    [0120] ( S 5 ) ( S 4 ) で読み取った文字があれば、 （ S 5 ) に進 む。 文字列 ω Κがなければ、 （ S 7 )， （S 8 ) を再度行って，
    [0121] ( o 3 ) る。
    [0122] ( S 6 ) ( S 5 ) で <oKが辞書にある場合は、 その文字列は 登録済であるので、 文字列を参照辞書に照合するために用い る文字列の Κを に置換する。 再び （ S 3 ) に戻って次の 文字を読み取り、 同様の処理を反復する。 （ S 4 ) で読み取 る文字が無くなれば、 すべての文字の処理を終えたので、
    [0123] ( S 9 ) に進む。
    [0124] ( S 9 ) 各参照辞書単位に登録されている文字列数もしく は 参照辞書単位間の遷移数を数える。
    [0125] ( 5 10) 参照辞書単位に登録されている文字数をまたは参照 辞書単位間の遷移数を考慮して、 参照辞書単位の最適符号を 設定する。
    [0126] ( 5 11) 符号 に付されている参照辞書単位を表わす仮符号 を最適符号に変換処理する。
    [0127] ( 5 12) 圧縮符号を出力する。
    [0128] このように、 大規模の参照辞書を用いても、 辞書を分割し たため、 登録文字列のィ ンデックスを短い符号で表現でき、 効率的に符号が生成される。
    [0129] 辞書を分割したことによる符号語の構成が増加するが、 参 照辞書単位を表わす符号を可変長符号としたことにより、 入 力された全文字列の圧縮符号における符号語の占める割合を 少なくすることができる。
    [0130] このように、 辞書を大規模にすることにより、 イ ンデッ ク スの符号が長くなり、 圧縮率が低下することがなく、 辞書を 大規模にするに見合っただけの十分なデータ圧縮が行われる。
    [0131] 参照辞書の単位の最適符号の設定の例が第 19図に示される。 第 19図においては参照辞書単位が 3つの場合の登録成分の イ ンデッ クスの割り当ての例が示される。
    [0132] 例えば、 文字列が a , b , cのみより成るような場合、 T , は先頭文字が aよりなる文字列のグループ、 T 2 は先頭文字 が bよりなるグループ、 T 3 は先頭文字が cよりなる文字グ ループとするように、 各参照辞書単位に文字列の先頭文字に 対応して登録する。 各節に対応させてィ ンデックスを割り当てるのではなく、 登録順に蕃号をつけていく。
    [0133] そして、 文字列線分を表わす符号語は第 19図に示されるよ うに、 参照辞書単位の番号を表わす木の番号 （ツ リー） 番号 224 と登録位置を示すィ ンデッ クス 222 により構成する。
    [0134] 例えば、 参照辞書単位 3 (T3)の登録位置 8の文字列は第 19図に示されるように参照辞書単位の番号 Τ 3 と登録位置に 8を付すことにより表わす。
    [0135] 第 19図においては、 参照辞書単位の番号を表わす符号、 す なわちッ リ一審号、 を例示するように、 登録文字列数の多い ッ リ一、 すなわち節点数の多いッ リ一、 は、 例えば、 節点数 20の には短い符号 " 0 " を付し、 登録文字数の少ない Τ2，Τ 3 には長い符号 "10", "01" 等を付すようにする。
    [0136] 最適符号を適用した圧縮符号の例が第 20図に示される。
    [0137] 第 20図においては、 入力文字列 aabababaaba…を増分分解 型 Z L方式 （Ziv Lempel方式） に変換する方式が説明される < 第 20図においては、 参照辞書単位の審号を仮符号 "000"， "001 "により表した場合の入力文字列を圧縮した場合の圧縮 符号が示される。
    [0138] 第 20図においては、 参照辞書単位の仮符号を、 最適符号に 変換した入力文字列の圧縮符号が示される。
    [0139] 第 21図〜第 23図は他の例が示される。
    [0140] 第 21図においては、 連続する文字列の成分における最^文 字から先頭文字への遷移の一例が示される。 第 21図の表には 文字グループ間での遷移回数測定の結果が示される。 第 21図において、 251は現登録文字列を基準にして、 1つ 前の登録文字列、 252は現登録文字列、 253は次の登録文字 列、 254は 1つ前の登録文字列 251 の最終文字、 255は現登 録文字の先頭文字、 256は現登録文字の最終文字、 257は次 の登録文字の先頭文字である。
    [0141] 第 21図においては、 参照辞書単位、 即ち、 第 17図における ツ リ ーの根を 16個にし、 連続する文字列の最終文字から先頭 文字への遷移を考え、 それぞれ 2
    [0142] 5の文字が属するツ リー間の遷 移の確率を測定することにより、 遷移確率が高い場合には短 い符号を設定し、 低い場合には長い符号を選定し、 遷移コー ドと してイ ンデックスとともに符号語として付すものである 第 21図においては、 1つ前の登録文字列の最終文字の属す るグループナンバー、 すなわち 16個、 第 3図におけるツ リー、 から現登録文字の先頭文字の属するグループナンバーへの遷 移回数の測定値を表わす。
    [0143] 第 21図においては、 各数字が出現回数をあらわす。 例えば、 グループナンバー 4からグループナンバー 6への遷移は 83回 生じたことを表わす。
    [0144] 第 22図は第 21図における測定値を遷移回数の順位に書き直 したデータを示す。
    [0145] 第 22図においては、 1個前の登録文字の最終文字の属する グループナンバーから、 現登録文字の先頭文字の属するグル —プナ ンバーへの遷移を任意の 1 個前のグループナンバーに ついて順位付けされている。
    [0146] 数字 0 は遷移回数が一審多かったことを示し、 15は遷移回 数の一番少なかったことを表わす。
    [0147] 例えば、 1つ前の登録文字列のグループナンバーが 4から 現登録文字列のグループナンバー 6へ遷移する順位は、 1個 前のグループナンバー 4から現登録文字列のグループナンバ 一へ遷移するあらゆる場合のうちで 2蕃目に多い順位である ことを示す。
    [0148] 第 23図においては、 第 21図の結果により、 参照辞書単位、 すなわち第 21図におけるグループナンバー、 に付与する最適 符号を設定する方法が示される。
    [0149] 第 23図においては登録文字グループナンバ一間での遷移の 頻度の順位により符号語に付与するための符号の例が示され o
    [0150] 出現頻度の高い場合には短い符号を付与し、 反対に、 出現 頻度の低い場合には長い符号を付与する。
    [0151] いま、 現登録文字列のグループナンバー 6、 すなわち に対応するもの、 で、 そのィ ンデックスが 125の文字列を符 号化する場合を考える。
    [0152] そして、 前登録文字列のグループナンバーが 0 とする。
    [0153] この場合、 第 22図に示される表により、 頻度は 10であるか ら、 最適符号として 1110101を付す。
    [0154] 第 23図においては、 その符号語が示される。
    [0155] このように、 符号語を解釈するために、 1つ前の文字列の 最終文字の属する参照辞書単位を必要とするが、 出力されて いる圧縮符号列に 1つ前の文字列の最終文字が送られている ので、 それにより現文字列のグループナンバーが識別される, 本発明の他の形態におけるデータ圧縮および復元方法用の システムの例が第 24図に示される。
    [0156] 第 24図のシステムにおいては、 入力文字列を辞書 310 に登 録された既に符号化済みの部分列の内、 最長一致の部分列の 参照蕃号で指定して L Z W方式の符号に符号化することが行 われる。
    [0157] 第 24図のシステムにおいては、 辞書 310 を、 処理対象とな る全文字種の数より少ない所定数の辞書 310— 1〜 310— N から成る辞書群で構成して各辞書 310— ：！ 〜 310— Nごとに 全文字種を 1文字ごとに参照番号を付与して初期登録する。 入力された文字列の符号化時には、 以前に符号化済みの文 字列との従属関係すなわち履歴を示す索引情報に従って辞書 群の中の特定の辞書 310— i を指定して符号化し、 同時に指 定辞書 310— i に入力文字列がなかった場合には、 以前の符 号化済み文字列の参照番号に次の 1文字を付加した文字列を 新たな参照審号を付与して登録するこ とを特徴とする。
    [0158] 入力された文字列の符号化時には、 直前に符号化済みの文 字列の最絡文字コ一ドの一部分から得られた索引情報に従つ て辞書群の中の特定の辞書 310— 1を指定する。 さらに具体 的には、 直前に符号化済みの文字列の最終文字コ一ドの上位 ビッ トで示される索引情報に従って前記辞書群の中の特定の 辞書 310— i を指定する。
    [0159] 一方、 入力された文字列の符号化時には、 直前に符号化済 みの文字列の最終文字コー ドによりルッ クアツプテーブルを 参照して得られた索引情報に従って前記辞書群の中の特定の 辞書 310— 1を指定してもよい。 具体的には、 直前に符号化 済みの文字列の最^文字コ一ドの上位ビッ トによりルッ クァ ップテーブルを参照して得られた索引情報に従って前記辞書 群の中の特定の辞書 310— i を指定する。
    [0160] 第 24図のシステムにおいては、 入力された文字列を辞書 310 に登録された既に符号化済みの部分列のうち、 最長一致の部 分列の参照番号で指定して符号化された符号語から元の文字 列を復元するデータ復元方式を対象とし、 辞書 310 を、 処理 対象となる全文字種の数より少ない所定数の辞書 310— 1〜 310— Nから成る辞書群で構成して各辞書 310 _ 1〜
    [0161] 310 - Nごとに全文字種を 1文字ごとに参照審号を付けて初 期登録する。 入力符号語の復元時には、 以前に復元済みの文 字列との従属関係を示す索引情報に従って前記辞書群の中の 特定の辞書 310— 1を指定して復元し、 復元毎に、 以前に復 元済み文字列の参照番号に、 今回復元した文字列の最初の 1 文字を付加した文字列を新たな参照審号を付与して登録する。 ここで復元時に使用する特定辞書 310— i の指定は、 符号化 の場合と同様である。
    [0162] 第 24図のシステムによれば、 次の作用が得られる。
    [0163] まず直前文字列の最終文字との従属関係を示す履歴は、 そ のままだと 256通りの状態があるが、 文字の出現には偏りが あり、 256通りのうち出現しない状態もある。 そこで、 最終 文字の履歴をマージして縮小し、 有意義な少数通りの状態、 例えば 8〜： 16通りに帰着させ、 辞書の数を減らす。
    [0164] 履歴の状態数が少数であるため、 全文字種 256個の各辞書 への初期値と して登録数は、 履歴数、 即ち辞書数 X 256個で あり、 大きな無駄は出ないようにできる。
    [0165] 履歴をまとめる方法と して、 例えば、 符号化済直前文字列 の最終文字の上位 4 ビッ トを取れば、 履歴は 16個の状態にま とめられる。 履歴のまとめ方としては、 辞書を有効に使う上 では均等に出現する状態を用いるのが望ま しい。 しかし、 必 ずしも文字中に生のデータのビッ トを用いる必要はなく、 そ の代りに、 データの大まかな性質に合わせて、 符号化済直前 文字列の最終文字を履歴の状態に対応付けるルツクア ツプ* テーブル（LUT) を用意して、 直前文字の履歴状態、 即ち辞書 の索引を指定することが可能である。
    [0166] 第 24図のシステムにおけるプログラム用記憶装置、 データ 用記憶装置の構成が第 25図に示される。
    [0167] 第 25図において、 312は制御手段と しての。 P Uであり、 CPU312に対してはプログラムメモ リ 314 とデータメモリ 326 が接続される。
    [0168] プロ グラ ムメ モ リ 314 にはコ ン ト ロ ールプロ グラ.厶 316 、 L Z W符号を用いた最長一致の検索を行なう最長一致検索プ ログラ ム 318 、 入力文字列を L Z W方式の符号に変換する符 号化プログラ厶 320 、 符号化プログラム 320 で Z W符号に 変換された符号を元の文字列に復元する復号プログラム 322 、 及び処理対象となる全文字種、 例えば 256個の文字種を初期 登録する辞書初期値作成プロ グラ ム 324 を備える。
    [0169] データメ モ リ 326 〖こは、 これから符号化しょうとする文字 列、 またはこれから復号しょうとする符号列を格納するデー タバッ フ ァ 328 と、 L Z W方式の符号を対象とした符号化及 び復号の際に逐次作成されながら使用される辞書 310 を備え る o
    [0170] 辞書 310 は、 例えば符号化済み文字列の最終文字コードの 上位 4 ビッ トでなる従属関係を示す索引情報により分類され る場合を例にとると、 256個の全文字種に対し 16個の辞書 310 一 1 ~ 310— 16で構成される。 符号化文字列の最終文字コ ー ドの上位 4 ビッ トによる辞書の索引指定は、 直接指定しても 良いが、 以下の説明にあっては、 ルッ クアップテーブル（LUT) を参照して辞書の索引を読出して指定する場合を例にとる。 データ圧縮及び復元の概略が以下に説明される。
    [0171] CPU312はコ ン トロールプログラ厶 316 による制御のもとに 辞書初期値作成プログラム 324 を起動し、 辞書初期値作成処 理を行なう。 具体的には、 辞書初期値作成プロ グラ ム 324 は すべての文字種 256 に 1文字ごとに参照審号を付与して辞書 を構成する 16個の辞書 310 _ 1 〜 310— 16のそれぞれに登録 する。
    [0172] データメ モ リ 326 のデータバッ フ ァ 328 は符号化すべきデ 一夕を外部から一定長の複数文字分を一時に格納し、 符号化 プログラム 320 の要求に従って一文字ずつ受渡す。 そして、 データバッファ 328 の文字が空になるたびに、 同様に外部か ら複数文字分を取込む。
    [0173] 符号化のァルゴリズムが第 26図のフ口一チャー トにより説 明される。
    [0174] まず S 1 においては次の処理を行う。 ( i ) 直前文字列の最終文字で選択する N個の各辞書 D i 、 ここに i = 1 , …， N、 に一文字からなる文字列全種を初期 値として予め登録する。 すべての文字種 256 に対し辞書の総 数 Nは N = 16個と少なく なっている。
    [0175] ( ϋ ) 各辞書 D i の参照審号の総数を ri i で管理し、 初期化 のとき、 辞書数: N個の n i に
    [0176] Ή i =文字種 + 1
    [0177] をセッ 卜する。
    [0178] (iii) 直前の文字列からの履歴、 即ち直前文字列の最絡文字 コ一ドの上位 4 ビッ トを P Kとし、 初期値と して P Kに P K = 0をセッ トする。
    [0179] (iv) 最初の文字を入力 Kと し、 これを参照審号すなわち語 頭文字列 ωに直す。
    [0180] ( V ) 直前文字列の最終文字 Κ 1から履歴状態に対応つける ルッ クァップテーブルをセッ トする。 但し、 最初は直前文字 列はないので、 直前文字列の最終文字を示す Κ 1 は Κ 1 == 0 にセッ トすると共に、 Κ 1 = 0でルックアップテーブルから 得られる索引 Ρ Κは P K= 0 となるようにルッ クアップテー ブルをセッ ト しておく。
    [0181] このような S 1の処理が終了すると S 4〜 S 7の手順に従 つて符号化する。 この S 4 ~ S 7の手順は、 従来と同じであ o
    [0182] しかし、 従来の L ZW符号化において辞書は 1個だけだつ たのに代えて、 最初は S 1、 それ以降は S 6 に示す符号化済 みの文字列の最終文字 K 1 によりルッ クアツプテーブルを参 照して得られた履歴状態 LUT(Kl) = P Kによって複数個の辞 書から特定の辞書 DPKを選択して、 選択した辞書 DPKに登録 されている文字列と照合して最長一致文字列を探索し、 最長 一致を一文字延長した文字列 ω Kを選択した辞書 DPKに登録 するようになつている。
    [0183] S 6で辞書 DPKに登録した後は、 辞書 DPKの参照番号を管 理する力ゥ ンタ n PKが n PK= n PK+ l と 1つ増分される。 ま た、 前述したように次の文字列の辞書を選ぶために最終文字 Κ 1よりルッ クアツプテーブルを用いて新たな履歴状態 Ρ Κ が求められる。
    [0184] 復号ァルゴリズムが第 27図のフローチャー トを参照して説 明される。
    [0185] 復号は、 符号化の逆の動作となる。 まず S 1 (Α) に示す 辞書の初期化は符号化の場合と同様である。 S I (Β) ~ S 9の手順は、 従来と同様である。 しかし、 入力したコー ド から S 4で参照審号 ωを復号した後、 直前の文字列の最終文 字から求めた履歴状態 Ρ Κを使用して辞書 DPKを選び、 選択 した辞書 DPKの中から参照審号 ωに対応する文字列を求める ようになつている。
    [0186] 辞書への新たな文字列の登録は、 L ZW符号化の場合と同 様であるが、 符号化のときょり 1テンポ遅れて行なわれる。 即、 符号化の際には注目文字列の符号化を終了した時点で一 文字伸ばした文字列 ωΚ、 すなわち注目文字列プラ ス次の 1 文字、 を辞書に登録しているが、 復号では、 注目文字列 ωを 一文字延長するときは次の文字列の先頭文字と合わせて辞書 に登録するため、 次の文字列の復元が^了した時点で登録を 行なう。
    [0187] 具体的には S 9に示すように、 直前文字列の参照番号
    [0188] OLD roと復元文字列の第 1文字 1の組を、 直前の前の文字 列の最終文字からの履歴状態 P K 1で選ばれた辞書 D P K I に 登録する。 そこで、 復元した文字列を延長して次に登録する ときのために現在の履歴状態 P Kを P K 1 に移しておき、 復 元文字列の最終文字 K 2より、 新たな履歴状態を求める。
    [0189] なお前記においては、 全文字種 256個に対し辞書を履歴状 態に従って 16個で構成する場合を例にとるものであつたが、 それに限らず、 全て文字種の総数以下の適宜の辞書数とする ことができる。
    [0190] また文字種の数も必要に応じて適宜に選定されることが可 tsである。
    [0191] 本発明の他の形態におけるデータ圧縮および復元方法用の システムの例が第 28図に示される。
    [0192] 第 28図のシステムにおいて、 文字列が 3文字 a , b , cの みより成る文字列において、 直前文字列の最^文字ごとに辞 書を作成し、 辞書に初期値を登録しておかない状態から始め る場合について、 例示的に示したものである。
    [0193] 第 28図のシステムにおいて、 401は入力文字列、 402は最 終文字を根とする木ごとに登録文字部分列のィ ンデックス
    [0194] " I (Π) "を登録した辞書、 例えば、 aを根とする木における 文字部分列 ab, abc のイ ンデッ クスはそれぞれ 0 ， 1等であ ることを示すもの、 403は一文字ずつ入力文字列を読み出す 文字読出し部、 404は対象とする現文字部分列、 405は現文 字部分列を辞書を参照して、 登録されている文字部分列より 現文字部分列と一致する最大長の文字部分列を読み取る辞書 参照部、 408は読み出した文字列の最長一致文字部分を辞書 に登録されているィ ンデックスに基づいてコード化し、 最長 一致文字列に文字列の次の一文字を延長した新しく現れた現 文字部分列に、 直前文字列の最終文字ごとにィ ンデックスを 定める符号化部、 409は現文字列部分辞書に登録する辞書登 録部、 410は最長一致文字部分列の最終文字部分を記憶する 最終文字記憶部、 411は直前文字列の最終文字を根とする辞 書の木の例である。
    [0195] 入力文字列 " ababct^- " を符号化する場合を例として、 第 28図のシステムの作用を具体的に説明する。
    [0196] 直前文字列の最終文字を根とする辞書の木は、 第 29図に示 されるように、 例えば、 文字部分列として aを出力する場合- 直前文字部分列の最終文字が aに続く aと、 bに続く aでは それぞれ aを拫とする木の aと bを根とする木の aとして区 別して出力しなければならない。
    [0197] そのような各根につく 1文字を出力するためには、 （ i ) 木の根となる各文字と 1文字との組合せ " aa, ab, ac， ba〜: 等を符号化側、 復号側の両方に、 あらかじめ初期値として作 成しておき、 このコードにより aに続く a、 bに続く a等を 区別して出力する前述の方法をとるか、 （ ii ) そのような木 の根につく 1文字があらたに現れた場合には生データとして の 1文字を出力するようにする方法をとらなければならない, ここでは、 直前の文字列の最絡文字を辞書の木の根とし、 木の根につながる初期値を登録しておかず、 木の根に直接つ ながる 1文字を生のデータとして出力する後者の場合を例と して説明する。
    [0198] (第 1 ) 文字列読出し部 403 は最初の文字 aを読み出し、 文字部分列 404 とする。 辞書参照部 405 は辞書を参照し、 a が未登録であることを確認する。
    [0199] 符号化部 408 は、 生データを指定するコ一 ドと してィ ンデ ッ クス 0を設定する。
    [0200] 辞書登録部 409 は、 直前文字列の最終文字 0の木に aを辞 書の登録位置 " n = l " に登録する。
    [0201] 同時に、 イ ンデッ クス 0 と文字 aを出力する。
    [0202] そして、 直前文字列の最終文字として aを記憶する。
    [0203] (第 2 ) 第 2番目の文字 bを読み取る。
    [0204] そこで、 直前文字列の最終文字 a と入力された文字 bとに よる文字列 a bを辞書を参照する。 a bは未登録であるので、 文字列 " a b " を辞書の登録位置 " 2 " に、 aを根とする木 の第 1蕃目の登録文字部分列として登録する。
    [0205] そして、 いま入力された bは aを根とする木に現れた 1文 字であるので、 イ ンデッ クス 0 と bを生のデータとして出力 し、 直前の文字列の最終文字として、 bを記憶する。
    [0206] (第 3 ) 第 3番目の文字 aを入力する。
    [0207] そこで、 直前の文字列の最終文字 bと読み取った a とによ る文字列 " b a " を辞書を参照する。
    [0208] b aは無いので、 文字部分列 " b a " を直前文字列の最終 文字 bを根とする木の最初の文字として辞書の登録位置 κ n = 3 " に登録する。
    [0209] 出力された文字部分列の最終文字 aを直前文字列の最終文 字として記憶する。
    [0210] (第 4 ) 第 4審目に文字 bを読み取る。
    [0211] そこで、 直前文字列の最終文字 a と読み取った bとによる 文字列 " a b " を辞書と参照する。
    [0212] " a b " は登録位置 " 3 " に登録されているので、 さらに 次の文字 cを読み取る。
    [0213] 文字列 " abc "は辞書に未登録であるので、 符号化部 408 は、 最長一致文字列 K a b " を、 aを根とする木における " a b " のィ ンデッ クス 1 により第 4審目の文字 bを表わすコ一ドと してコード化して出力し、 同時に、 辞書の登録位置 " 4 " に 新しく現れた文字列 " abc"を aを根とする木の 2審目の文字 列として登録する。
    [0214] 出力された最長一致文字列の最終文字 bを直前文字列の最 終文字として記憶する。
    [0215] (第 5 ) 第 5審目の文字 cを読み取る。
    [0216] 記憶してある最終文字 cと読み取った bとの文字列 b cは 未登録であるので文字列 b cを、 bを根とする木の最初の文 字部分列として辞書の登録位置 " 5 " 、 すなわち "ィ ンデッ ク ス 5 " で登録する。
    [0217] そして、 cは直前の文字列の最終文字 bを根とする辞書の 木の根につながる文字であるので、 イ ンデッ ク ス 0 と文字 c を生のデータにより出力する。 以下、 同様の手続きを進め、 出力コー ド" OaObOa lOc—" を 得る。
    [0218] 第 28図のシステムにおける、 データ圧縮のコ一ドの文字列 への復号を行う構成が第 30図に示される。
    [0219] 第 30図の構成において、 421は入力コ一ド、 422は入力コ — ドより復元した辞書、 423は入力コー ド読み取り手段、 424 は入力コ一ドの表わすィ ンデックスと復元された直前文字列 の最終文字、 425は辞書参照部、 426はィ ンデッ クスと直前 文字列の最終文字に対応する辞書の登録文字列より文字列を 復号する文字部分列復号部、 427は復元文字列より復号文字 を出力する復元文字出力部、 428は復元した文字部分列の最 終文字を記憶する最終文字記憶部、 429は復号文字列と次に 復号される復号文字列の第 1文字により構成される文字部分 列を直前文字列の最終文字の木にィ ンデッ ク スにより登録す る辞書復元部である。
    [0220] 符号化したコード " OaObOa lO—" を復号する場合を例とし て具体的に説明する。
    [0221] (第 1 ) 入力コー ド読み取り部 423 は入力コー ド aを読み 取る。 生データであるので、 文字部分列復号部 426 は文字 a を復号し、 出力する。 そして、 復号辞書 422 の登録位置 " 1 " に文字 aを直前文字列の最終文字 0の木と して、 イ ンデッ ク ス " 1 " で登録する。 同時に、 復号文字列の最終文字 aを記
    [0222] 1思 3 る o
    [0223] (第 2 ) 同様に、 次のコー ド l bを読み取り、 生データで あるので、 文字 bを復号して出力し、 記憶してある文字 aと いま読み取った bとの文字列 a bを aを根とする木の辞書の 登録位置 " 2 " にィ ンデッ クス " 1 " で登録する。 さらに、 復号した文字部分列の最終文字 bを記憶する。
    [0224] (第 3 ) 次のコー ド aを読み出し、 文字列 aを復元し、 記 憶してある最終文字 bといま読み取った bとの文字列 b aを bを根とする木の辞書に登録位置 " 3 " 、 イ ンデッ クス " 1 ' で登録する。 そして、 復元した aを記憶する。
    [0225] (第 4 ) 第 4番目のコー ド 1を読み取る。 いま、 直前の文 字部分列の最終文字は aで入力符号は 1であるから、 辞書参 照部 425 は辞書を参照し、 文字部分列 a bを読み出す。 そし て、 文字部分列復号部 426 は文字部分列 K a b " を復号する c さらに、 その復号文字部分列と直前の最終文字列の最終文字 aに基づいて、 復号文字出力部 427 は文字 bを出力する。 最 文字記憶部 428 は復号した文字列の最終文字 bを記憶する c (第 5 ) 第 5番目のコード cを読み取る。
    [0226] 生のデータであるので、 文字 cを復号するとともに、 前の (第 4 ) の項で復号した文字部分列 a bといま復号した文字 cにより文字列 a b cを aを根とする木の辞書に登録位置 " 4 " 、 ィ ンデッ クス " 2 " で登録し辞書を復元する。
    [0227] 上記の説明においては、 直前文字列の最終文字ごとに辞書 の木を作成する場合について、 説明したが、 それに限らず、 最終文字をその種類等によりグループにまとめて、 グループ ごとに辞書の木を作成し、 続く文字部分列を登録するように することが可能である。
    [0228] 第 28図のシステムに用いられる符号化用の装置の例が第 31 図に示される。
    [0229] 第 31図の装置においては、 辞書を文字部分列を登録する全 体辞書と、 直前の文字列の最^文字ごとに、 続く文字部分列 を全体辞書の登録位置に対応付けてィ ンデッ クスにより登録 した個別辞書とに分けて作成している。
    [0230] 第 31図の装置において、 430は入力文字列を符号化するた めの入力文字列 Kを格納するメ モリ、 431は文字部分列コ一 ド ωを格納するメ モ 、J、 432は直前文字部分列の最終文字 P Kの格納メモリ、 433は符号化の対象としている現文字列 の最終文字 K 1の格納メモリ、 434はメモリより成る全体辞 書 D ( n ) 、 435はメモリより成る個別辞書で 0 , a , b , c…等 256の各文字ごとに構成されるもの、 436は辞書の木 における文字部分列の登録階層の深さを計測する力ゥンタ、 437 - 0〜 437 - 255 は個別辞書 0〜255 の各ィ ンデッ クス m ( 0 ) 〜m (255) のカウ ンタ、 438は全体辞書の登録番号 ηのカ ウ ンタ、 439は辞書を参照しさらに辞書を作成する辞 書参照および作成手段、 440は読み取った文字部分列を符号 化する符号作成手段、 441は作成した文字部分列の符号を出 力する符号出力手段、 442はプログラムに従ってデータの符 号化処理の実行、 制御を行う C P Uである。
    [0231] 第 31図の装置における符号化のための動作の過程が第 32図 に示される。
    [0232] 文字列と して" ababcbaba—" を符号化した場合の全体辞書 と個別辞書の例が第 33図および第 34図に示される。
    [0233] 文字列を符号化した場合の個別辞書の木の例が第 35図に示 される。
    [0234] 第 35図の例においては、 直前の文字列の最終文字の木の根 に直接つながる文字が最初に現れた場合には生のデータとし てのその 1文字を送るようにしている。
    [0235] 符号語の例が第 36図に示される。 モード 1 は、 上記の各個 別辞書の木の根に直接繋がる文字が新たに出現した場合を示 す。
    [0236] モー ド 1では、 ィ ンデッ クス 0、 すなわち生のデータを指 定、 と文字の生のデータの組を符号語として送ることとする。
    [0237] モー ド 1以外の文字または文字列が出現したときは、 第 36 図に示されるように、 各木におけるその文字列のィ ンデック スを符号語として送ることとする。
    [0238] 第 32図のフロ一が以下に説明される。
    [0239] 初期条件の設定ステップ S 1 は、 個別辞書を 256個備える 場合を示しているが、 説明を簡単にするため、 文字列として、 文字 a , b , cの 3文字のみよりなる文字列" aba bc；…" を符 号化する場合を考える。
    [0240] まず、 S 1 において装置の全体を初期化する。
    [0241] 初期条件と して、 （条件 1 ) 直前文字列の最終文字 P Kを 0 とする。 （条件 2 ) 文字列コード格納メ モ リの初期値をい まの場合 0 とする。 この例においては、 256としてある。
    [0242] (条件 3 ) 辞書の木の深さ D Pの測定カウ ンタを 0 とする。
    [0243] (条件 4 ) 全体辞書の先頭の登録位置を示す先頭ア ド レスを 今の場合 4 とする。 この例においては、 256と してある。 個 別辞書のイ ンデッ クスの個数をそれぞれ 0 とする。 いまの場 合、 個別辞書は 0 , a ' b . cの 4つよりなるので、 それぞ れの辞書に登録されるィ ンデッ クスの個数 m (0), m (a), m (b), m (C) を 0 とする。
    [0244] (第 1 ) S 2において、 入力文字列 ababcbaba…の先頭文 字 aを読み取る。
    [0245] S 3における判断は文字列を全部読み取って、 処理を終了 するかの判断であるので、 S 4に進む。
    [0246] 直前文字列 0に続く文字列 aは全体辞書に未登録であるか り、 S Dに進む。
    [0247] いま、 深さ D Pは 0であるから S 12に進む。
    [0248] いまの場合、 上記のモー ド 1 に該当する場合であるので、
    [0249] S 12において、 m ( 0 ) = 0 と生のデータ aにより符号語と して 0 aを出力する。
    [0250] そこで、 S 13において、 全体辞書 D (n = 4 ) にいま入力 した文字列 a、 ここに ωの初期値を 0 としてあるので 0 aで ある、 を登録し、 個別辞書 0 ( P K = 0 ) にイ ンデッ クス I
    [0251] ( η = 4 ) とし、 個別辞書 0の登録ィ ンデックス個数 m ( 0 ) を 1つ増分し、 1、 すなわち、 個別辞書 0の木には登録文字 はなかった、 を登録する。
    [0252] 次に、 S 14において、 全体辞書の登録位置 nを 1つ増分す る o
    [0253] 次に、 最終文字列 P Kをいま読み取った a と し、 文字列コ — ド を読み取った文字 aのコー ド、 すなわち初期条件にお いて設定した 1、 とする。
    [0254] (第 2 ) 次の第 2番目の文字 bを読み取る。 K = 1 bは、 辞書に未登録であるので、 S 6に進み、 DP= 0であるから、 ステップ （12) に進む。
    [0255] そこで、 いまは、 m (a) = 0、 生の文字 bのモード 1の 場合であるから、 O bを外部に出力する。
    [0256] そこで、 S13において、 wK= l bを辞書 D ( n = 5 ) に 登録し、 さらに、 個別辞書にも個別辞書 a (PK= a) にィ ンデッ クス I (n = 5 ) とし、 個別辞書 aのィ ンデッ クスの 登録個数 m (a) を 1つ増分し、 1、 すなわち、 個別辞書 a の木には登録文字はなかった、 を登録する。 S 14において、 nを 1増分する。 そして、 最終文字 P Kをいま読み取った b とし、 入力文字コード ωを初期条件としてさだめた bのコー ド 2とする。
    [0257] (第 3 ) 次に、 第 3番目の文字 aを読み取る。
    [0258] ωΚ= 2 bは未登録であるので、 S 6に進み、 DP= 0で あるから、 S 12でモード 1として、 m ( b ) = 0、 すなわち. bの個別辞書の木には文字列はまだない、 であるから、 生の データ bとの組 1 bを出力する。
    [0259] そこで、 S 13において、 全体辞書に ω K = 2 bを
    [0260] D (n = 6 ) に登録し、 同時に、 個別辞書 b (PK= b) に イ ンデッ クス I (n = 6 ) として m ( b ) を 1つ増分し、 1. すなわち、 個別辞書 bの木には登録文字はなかった、 を登録 する。 次に、 S14において、 mを 1つ増分とし、 PKを a、 ω= 1として次の文字 bを読み取る。
    [0261] (第 4) 次に、 第 4番目の文字 bを読み取る。
    [0262] S 4の判断において、 ωΚ = 1 bは、 全体辞書を参照する と、 コー ド η = 5で登録済であるから、 S 5に進む。
    [0263] そこで、 を今全体辞書から読み取った η = 5とし、 階層 の深さ D Ρを 1つ増分して D Ρ = 1、 いま読み取った bを最 ^文字格納メ モ リ K 1に格納する。
    [0264] (第 5 ) 次の第 5番目の文字 cを読み取る。
    [0265] 次に、 S 4において、 ωΚ= 5 cが全体辞書に登録されて いるか判断する。
    [0266] Κ= 5 cは未登録であるから、 S 6に進む。
    [0267] いま、 DP = 1であるから、 S 7に進む。
    [0268] S 7において、 ω= 5 ( η = 5 ) に対応する個別辞書を参 照し、 イ ンデッ ク ス I (η = 5 ) = 1を直前文字列の最綏文 字 aに続く bの符号語を、 モー ド 2として、 出力する。
    [0269] 次に、 S 8において、 wK= 5 b (abc) を全体辞書の n = 7の登録位置に登録する。 同時に個別辞書 aに n = 7に 対応させて in (P K) を 1つ増分し、 イ ンデッ ク ス 1 = 2、 こ こに n = 7である、 を登録する。 すなわち、 個別辞書 aに おける 2審目に登録された文字列である。
    [0270] そして、 ' nを 1つ増分し、 深さ DPを 0とする。
    [0271] さ らに、 P Kを最終文字格納メ モ リ K 1に格納されている bとし、 ωを K 1のコード 2とする。 そして S 4において、 再度いま読み取った第 5審目の文字 cを Κとして ωΚ= 2 c が全体辞書に登録されているかどうか判断する。
    [0272] 2 cは全体辞書に未登録であるので、 S 6に進み、
    [0273] D P= 0であるから、 S12に進み、 文字 cを生データとして モー ド 1の符号語 0 bを出力する。 そこで、 S 13において、 全体辞書に ωΚ= 2 cを η = 8で 登録し、 いま P K= bであるから、 個別辞書 bに n = 8、 m ( b ) を 1つ増分し、 1 = 1、 すなわち n = 8、 bの木の 2審目の文字列、 を登録する。
    [0274] さらに、 nを 1つ増分し、 P Kをいま読み取った c とし、 cの初期条件における値としての、 ω = 3として、 次の文字 を読み取る。
    [0275] 以下同様にして、 入力文字列 "ababcbabaa—" の出力符号 として "0a0b0al0c0bll3—" を得る。
    [0276] 次に、 上記の符号からの文字列の復号を説明する。 復号の ための装置の構成の例が第 37図に示される。
    [0277] 第 37図の装置において、 471は入力コー ド格納メ モ リ 、 472 は個別辞書のィ ンデッ ク スにより符号語で送られてく る入力 コ一ドを全体辞書における文字列のコ ードに復元した復元コ ードを格納するメ モ リ （ΙΝω) 、 473は復元された直前の文 字部分列を格納するメ モ リ （OLDo 、 474は復元された直前 の文字部分列の最終文字を格納するメ モ リ （P K) 、 475は 直前のさらに直前の文字部分列の最終文字格納メモリ （PK1)
    [0278] 476は復元文字列の第 1文字格納メ モ リ （K l ) 、 477は入 力符号より復元された文字部分列より随時復元する全体辞書 D (η ) 、 478は復元文字列より随時復元する個別辞書 q、 すなわち P Kのィ ンデッ クス、 479_ 0〜 479— 255 は 255 個の個別辞書のィ ンデックス個数の力ゥンタ、 480は入力コ 一ドより個別辞書を参照する辞書参照手段、 481は全体辞書 より文字部分列を復号する文字部分列復号手段、 482は復号 文字部分列より文字部分列を全体辞書および対応する個別辞 書を復元する辞書復元手段、 483はプログラムに従って、 復 号処理を進める C P Uである。
    [0279] 符号化の過程が第 38図 (Ah (B), (C) に示される。 第 38図 （A) に示されるように、 初期化から入力符号が定義さ れているかどうかを判断し、 入力符号が定義されている場合 には、 個別辞書を参照して全体辞書における文字列を表わす コ一ドに変換する。
    [0280] 第 38図 （B) のフ ローにおいては、 モー ド 1の符号を復号 する。
    [0281] 第 38図 （C ) のフ ローにおいては、 全体辞書の登録符号よ り、 文字列を復号する。
    [0282] 入力符号と して前記の符号" OaObOalOc：…" が入力された場 合を例として、 下記に説明される。
    [0283] 先ず、 装置の初期化を行う。
    [0284] 初期条件においては、 個別辞書を 256備える場合を示し、 256個の一文字については 0〜255 の初期条件を与えてある 場合を示す。 初期条件は、 Ρ Κ= 0、 ωの初期値を 256 、 ΡΚ 1 = 0、 全体辞書の先頭ァ ド レスを η = 256 、 OLDw = 0、 各個別辞書の in ( 0 ) 〜m (255) を 0 とする。
    [0285] 説明を簡単にするため a , b , cの 3文字のみよりなる場 合について考え、 a , b , cについて初期条件でそれぞれコ ー ド 1 , 2 , 3を設定する。 さらに ωの初期値を 0 とする。
    [0286] (第 1 ) S 2において先頭の入力コー ド 0 aを入力する。
    [0287] S の判断においてコ一ドが未定義であるので、 S 6に進 む。
    [0288] S 6の判断は、 直前の文字列の辞書の木の根に直接つく符 号をあらわすモード 1か、 あるいは、 L ZW符号化処理にお いて例外的に生じる符号の未定義なコ一ド入力のあった場合 かを判定する。
    [0289] いまは、 モード 1であるので、 第 38図 （B) の S 7に進む S 7において、 入力符号 0 aが生データ K = aとして入力 されるのにもとづき、 文字 aを出力する。
    [0290] ここで、 直前の文字列はないので、 S12に進み、 復元した 文字列 aと P K= 0より全体辞書 D、 すなわち n = 4、 に、 0 aを登録し、 全体辞書を復元する。 さらに、 m ( 0 ) を増 分し P K= 0と m ( 0 ) = 0、 n = 4により個別辞書 1を復 兀す。
    [0291] さらに、 S13において、 nを増分し、 PKにいま復元した a、 P K = 0を OLDwに移す。
    [0292] (第 2 ) 第 2番目の入力コー ド 0 bを読み取る。
    [0293] この場合も、 モード 1のコードであるから、 S 4から S 6 に進み、 さらに S 7に進む。
    [0294] 第 38図 （B) のフローにおいて前記の （第 1 ) において 0 aを処理した場合と同様に、 生のデータ bを出力し、 全体 辞書の登録位置 π = 5に a bを登録する。 さらに、 直前文字 部分列の最終文字 aに対応する個別辞書 aに、 n = 5、 イ ン デッ クス = 1を登録して個別辞書を復元する。
    [0295] (第 3 ) 第 3の入力コード 0 aを入力する。 符号 0 aは、 同様にモード 1であるから、 前記の処理をく り返し、 復元コ ー ドとして aを出力し、 全体辞書に b aを書き込み、 個別辞 書 bに n = 6、 イ ンデッ クス = 1を書き込む。
    [0296] そこで、 m ( b ) = 1 , n - 7 . P K = a . OLDa) = bと して、 次の符号を読み取る。
    [0297] (第 4) 第 4番目のコー ドは 1である。
    [0298] 符号 1は定義されているので、 第 38図 （A) における S 5 に進 、
    [0299] 直前の文字列が aで、 入力符号が 1であるので、 復元され た個別辞書を参照し、 対応する全体辞書の登録位置を確認す る
    [0300] その結果、 n = 5 , <oK = 1 bに入力コ一ドを変換し、 Ι Νωに書き込み第 38図 （C) の S 15に進む。
    [0301] 第 38図 （C) は、 L ZW符号における復号処理のフローで ある。
    [0302] S16, S 17は従来の復号と同様である。
    [0303] すなわち、 S 16でコ一 ド 1 bを順次スタ ックに符号 b , a の順に格納し、 S 17で最後に格納した aを残して、 上部の b を出力する。
    [0304] 直前の文字部分列は辞書に登録されているので、 S 21に進 み、 直々前の文字列の最終文字格納メ モ リ に PK= a、 復号 文字の列 a bの最終文字 bを PKに書き込み、 復号文字部分 列の第 1文字 aを K 1に書き込む。
    [0305] 同時に、 OLDa)を復号コー ド l b (ΙΝ ) を書き込み、 次 のコー ドを読み取る。
    [0306] (第 5 ) 第 5番目の符号 0 cを読み取る。 モード 1のコードであるので、 第 38図 （B ) の S 7に進み, S 8において、 cを出力する。
    [0307] この場合、 直前文字文字列が辞書に未登録の状態であるの で、 S 10において、 0し の 1 bといま入力した c とにより， 全体辞書の n = 7の位置に文字列 a b cを登録し、 同時に m ( a ) を 1つ増分し個別辞書 aにイ ンデックス = 2を書き 込 、。
    [0308] S 11において、 nを 1つ増分し、 S 12において、 現在の文 字列、 すなわち最終文字 bにおいて cを読み込んだ時点にお ける文字列 b c、 の登録処理をする。 同時に個別辞書 bへの 登録処理をする。
    [0309] 以下同様の手順により、 入力コードを全部読み取り、 復号 する。
    [0310] なお、 第 38図 （B ) のフローにおける S 10 , S 11のステツ プは、 従来技術において、 L Z W符号化の例外として説明さ れた場合の処理と同様である。
    [0311] なお、 前記においては、 各個別辞書の木の根につく 1文字 については、 生のデータを出力する場合について説明したが, これに限らず、 各個別辞書の木の根に続く一文字の可能な組 合わせについて、 あらかじめ、 符号化側、 復号側において作 成しておき、 その作成コ一ドにより上記 1文字については出 力するようにすることが可能である。
    [0312] また、 出力する符号語は、 常に "注目文字列の個別ィ ンデ ッ クス ω、 次の 1文字 K " の組であらわし、 この "次の 1文 字" を直前文字列の最終文字として用い次の 1文字を符号化 するようにし、 符号化、 復号の過程を簡単なものにすること が可能である。
    [0313] 第 28図のシステムにおける辞書の木の構成および字列の符 号化方法が第 39図を参照しつつ説明される。
    [0314] 第 39図に示されるように、 直前の最終文字との従属関係に おいて、 現文字部分列の符号を付与する。
    [0315] そして、 直前の文字列の最終文字ごとに先頭文字およびそ の展開文字で木を構成するようにし、 各木毎に、 各文字列の 審号を付与する。
    [0316] 例えば、 直前の文字が aに対して、 一文字 aがつく ときは、 その aをその木におけるィ ンデッ クス 1 とし、 直前の文字 a に対する文字列 " a b " はイ ンデッ クス 7、 直前の文字 aに 对する一文字 bはイ ンデッ クス 2 とする。 また、 直前の文字 列が bの場合の一文字 aは直前文字列 bの木のィ ンデッ クス 1、 " a b " はその木におけるイ ンデッ クス 4、 というよう に、 直前文字列を根とする木毎に各文字列のィ ンデックスを 付与する。
    [0317] このようにすることにより、 各文字が等確率で出現する場 合には、 イ ンデックス、 すなわち各辞書の木における各部分 文字列の登録審号、 の長さを 256分の 1 とすることができる。 通常、 個別の木の大きさは、 個別の木を全部合わせた全体 の木の大きさの 10数分の一になり、 文字部分列を識別する符 号の長さが短く なり、 圧縮率が大になる。
    [0318] 本発明によるデータ圧縮および復元用の装置についての説 明を抄録と して記述するための図が第 40図に示される。 第 40 図の装置においては、 供給される文字列を 1字ずつ読み出し 符号化の対象となる現文字部分列を保持する文字部分列保持 部 （404)、 直前文字列の最^文字ごとに文字部分列を該最終 文字に従属させて記憶する辞書 （402)、 現文字部分列を直前 の文字列の最終文字との関係で辞書に登録ずみ文字部分列の 中から現文字部分列と一致する最大長の文字部分列を読み取 る辞書参照部 （405)、 読み出した文字列の最大一致文字部分 を符号化する符号化部 （408)、 最大一致文字列に次の一文字 を伸ばした新しく現れた現文字部分列に、 直前文字列の最終 文字ごとにィ ンデックスを定めて辞書に登録する辞書登録部 ( 409)、 最大一致文字部分列の最 文字部分を記憶する最終 文字記憶部 （410)、 供給されるコードを 1つずつ読み取るコ 一ド読取部 （423)、 入力コードより復元した辞書 （422)、 入 カコードの表すィ ンデックスと復元された直前文字列の最終 文字 （424)、 辞書参照部 （425)、 イ ンデッ クスと直前文字列 の最^文字に関係付けた辞書の登録文字列より文字列を複号 する複号部 （426)、 複号した文字部分列の最終文字を記憶す る最終文字記憶部 （428)、 および復元文字列と次に複号され る複号文字列の第 1文字により構成される文字部分列を直前 の最終文字に従属させて辞書に登録する辞書復元部 （429)、 が設けられている。
    权利要求:
    Claims 請 求 の 範 囲
    1. 入力された文字列を辞書に登録された符号化ずみの部 分列のうち、 最長の一致を示す部分列の参照審号を指定する とともに符号語として得られた参照番号に 1文字が付加され た部分列に新たな参照番号を付与して該辞書に登録すること により符号化を行い、
    該部分列の参照蕃号により表わされる符号語により該辞書に 登録されている部分列を探索してもとの部分列を復元すると ともに以前に処理された符号語に今回復元された部分列の先 頭文字が付加された部分列に新たな参照審号を付与して該辞 書に登録することにより復号を行う、
    増分分解形のデータ圧縮および復元方法において、
    サンプルのデータを対象とする符号化により辞書登録され た部分列のうち出現の頻度の大なる部分列のみを、 符号化済 みの部分列であるとの判断のもとに、 該辞書に初期値として 登録することにより、 該辞書の初期化を行う、
    ことを特徴とするデータ圧縮および復元方法。
    2. 該サンプルのデータを符号化して得られる辞書の初期 値を辞書に登録し、 その後に符号化および復号を行う、 請求の範囲第 1項記載の方法。
    3. 該サンプルのデータを符号化して得られる辞書の初期 値を該辞書の初めの書き替えが禁止されている部分に固定的 に設定する、
    請求の範囲第 1項記載の方法。
    4. サンプルのデータを供給するサンプルデータ供給部、 該供給されるサンプルのデータの符号化を行う符号化部、 該 符号化されたデータを文字の部分列と出現の頻度を対応させ つつ記憶する記憶部、 および該記憶されたデータにつき出現 の頻度が予め定められたしきい値より犬なるものを選別する 選別部を有する辞書初期化用手段、
    該辞書初期化用手段の出力を受け初期値登録部とデータ登 録部に区分して登録を行う辞書記憶手段、 および該辞書記憶 装置と協働してデータの符号化および復号を行う符号化手段 および復号手段、
    を具備し、 それにより、 サンプルのデータを対象とする符号 化により辞書登録された部分列のうち出現の頻度の犬なる部 分列のみが、 符号化済みの部分列であるとの判断のもとに、 該辞書に初期値として登録され、 それにより該辞書の初期化 が行われる、
    ことを特徴とするデータ圧縮および復元装置。
    5. 入力された文字列を辞書に登録された符号化ずみの部 分列のうち、 最長の一致を示す部分列の参照蕃号を指定する とともに符号語として得られた参照審号に 1文字が付加され た部分列に新たな参照番号を付与して該辞書に登録すること により符号化を行い、
    該部分列の参照番号により表わされる符号語により該辞書に 登録されている部分列を検索してもとの部分列を復元すると ともに以前に処理された符号語に今回復元された部分列の先 頭文字が付加された部分列に新たな参照番号を付与して該辞 書に登録することにより復号を行う、
    増分分解形のデータ圧縮および復元方法において、
    それぞれ相異なる先頭文字の群からなる複数の参照辞書単 位により参照辞書を作成し、
    参照辞書単位を表わす記号と参照辞書に登録されている部 分列のうち最長の一致を示す部分列の登録位置を表わす記号 により符号語を構成することにより入力された文字列の順次 の相異なる部分列を符号化し、
    部分列の先頭文字とその前位の部分列の最終文字の間の遷 移確率を文字群相互間において求め参照辞書単位相互間の遷 移確率を算出し、 そして、
    部分列が前位の部分列からの遷移確率が大であるとき、 符 号語を、 可変長符号語として、 遷移確率の小なる部分列に付 与する符号語より短い記号により表わす、
    ことを特徴とする、 増分分解形のデータ圧縮および復元方法。
    6. 出現可能な文字を複数の文字群に分割し該文字群ごと に参照辞書単位を作成する過程をさらに具備する、
    請求の範囲第 5項記載の方法。
    7. 使用頻度の犬なる参照辞書単位を表わす符号を、 使用 頻度の小なる参照辞書単位を表わす符号よりも短い記号で表 わす過程をさらに具備する、
    請求の範囲第 5項記載の方法。
    8. 入力された文字列を辞書に登録された符号化ずみの部 分列のうち、 最長の一致を示す部分列の参照審号を指定する とともに符号語と して得られた参照番号に 1文字が付加され た部分列に新たな参照番号を付与して該辞書に登録すること により符号化を行い、
    該部分列の参照番号により表わされる符号語により該辞書に 登録されている部分列を検索してもとの部分列を復元すると ともに以前に処理された符号語に今回復元された部分列の先 頭文字が付加された部分列に新たな参照番号を付与して該辞 書に登録することにより復号を行う、
    増分分解形のデータ圧縮および復元方法において、
    処理されるべき文字の種類の全部の数より小なる数の辞書 から成る辞書群により該辞書を作成し、 各辞書ごとに、 1文 字ごとの全文字種の 1つの文字、 または 1文字ごとの全文字 種を含む複数の文字からなる、 高い頻度で出現する文字列を， 参照番号を付与して初期登録し、
    符号化ずみの文字列に対する従属関係を示す索引情報にし たがって該辞書群のなかの特定の辞書を指定することにより 入力された文字列を符号化し、 そして、
    該指定された辞書に入力された文字列が存在しないときは- 符号化ずみの文字列の参照審号に次位の 1つの文字を付加し た文字列に新たな参照審号を付与して登録する、
    ことを特徴とする増分分解形のデータ圧緒および復元方法。
    9. 直前に符号化済みの文字列の最^文字コードの一部分 から得られた索引情報に従って前記辞書群の中の特定の辞書 を指定することにより λ力された文字列の符号化を行う、 請求の範囲第 8項記載の方法。
    10. 直前に符号化済みの文字列の最終文字コードの上位ビ ッ 卜で示される索引情報に従って前記辞書群の中の特定の辞 書を指定することにより入力された文字列の符号化を行う、 請求の範囲第 9項記載の方法。
    11. 直前に符号化済みの文字列の最終文字コ ー ドによりル ックアツプテーブルを参照して得られた索引情報に従って前 記辞書群の中の特定の辞書を指定することにより入力された 文字列の符号化を行う、
    請求の範囲第 8項記載の方法。
    12. 直前に符号化済みの文字列の最終文字コ一ドの上位ビ ッ トから作成された索引情報に従って前記辞書群の中の特定 の辞書を指定することにより入力された文字列の符号化を行
    Ό、
    請求の範囲第 11項記載の方法。
    13. 入力された文字列を辞書に登録された符号化ずみの部 分列のうち、 最長の一致を示す部分列の参照審号を指定する とともに符号語として得られた参照番号に 1文字が付加され た部分列に新たな参照番号を付与して該辞書に登録すること により符号化を行い、
    該部分列の参照審号により表わされる符号語により該辞書に 登録されている部分列を探索してもとの部分列を復元すると ともに以前に処理された符号語に今回復元された部分列の先 頭文字が付加された部分列に新たな参照審号を付与して該辞 書に登録することにより復号を行う、
    増分分解形のデータ圧縮および復元方法において、
    処理されるべき文字の種類の全部の数より小なる数の辞書 から成る辞書群により該辞書を作成し、 各辞書ごとに、 1文 字ごとの全文字種の 1つの文字、 または 1文字ごとの全文字 種を含む複数の文字からなる、 高い頻度で出現する文字列を， 参照番号を付与して初期登録し、
    符号化ずみの文字列に対する従属関係を示す索引情報にし たがって該辞書群のなかから特定の辞書を指定することによ り入力コー ドを復号し、 そして、
    復元ずみの文字列の参照審号に今回復元した文字列の最初 の 1つの文字を付加した文字列に新たな参照審号を付与して 登録する、
    ことを特徴とする増分分解形のデータ圧縮および復元方法。
    14. 直前に復元済みの文字列の最終文字コードの一部分か ら得られた索引情報に従って辞書群の中の特定の辞書を指定 することにより入力された符号の復号を行う、
    請求の範囲第 13項記載の方法。
    15. 直前に復元済みの文字列の最終文字コードの上位ビッ トで示される索引情報に従って辞書群の中の特定の辞書を指 定することにより入力された符号の復号を行う、
    請求の範囲第 14項記載の方法。
    16. 直前に復元済みの文字列の最終文字コ ードによりルツ クアツプテーブルを参照して得られた索引情報に従って辞書 群の中の特定の辞書を指定することにより入力符号の復号を 行う、
    請求の範囲第 13項記載の方法。
    17. 直前に復元済みの文字列の最終文字コー ドの上位ビッ トによりルッ クアツプテーブルを参照して得られた索引情報 に従って辞書群の中の特定の辞書を指定することにより入力 符号の復号を行う、
    請求の範囲第 16項記載の方法。
    18. 入力された文字列を辞書に登録された符号化ずみの部 分列のうち、 最長の一致を示す部分列の参照審号を指定する とともに符号語として得られた参照審号に 1文字が付加され た部分列に新たな参照蕃号を付与して該辞書に登録すること により符号化を行い、
    該部分列の参照審号により表わされる符号語により該辞書に 登録されている部分列を検索してもとの部分列を復元すると ともに以前に処理された符号語に今回復元された部分列の先 頭文字が付加された部分列に新たな参照審号を付与して該辞 書に登録することにより復号を行う、
    増分分解形のデータ圧縮および復元方法において、
    連続する 2つの部分列の最初の部分列の最鉻の文字ごとに、 または最終の文字による群ごとに次位の部分列を登録して登 録辞書を作成し、
    該最終の文字または最終の文字による群ごとに、 登録され る部分列の登録番号を付与し、 そして、
    該登録番号にもとづいて符号化されるべき部分列の符号語 を作成する、
    ことを特徴とする増分分解形のデータ圧縮および復元方法。
    19. 該作成された符号により構成されたデータから、 復号 された部分列の前位の部分列の最終の文字または最終の文字 による群ごとに辞書の復元を行い、 そして、
    該復元された辞書を用いて、 該復号された部分列の前位の 部分列の最终の文字と今回入力の符号から、 入力された符号 を文字の部分列に復号する、
    請求の範囲第 18項記載の方法。
    类似技术:
    公开号 | 公开日 | 专利标题
    Adjeroh et al.2008|The Burrows-Wheeler Transform:: Data Compression, Suffix Arrays, and Pattern Matching
    US4988998A|1991-01-29|Data compression system for successively applying at least two data compression methods to an input data stream
    US6873986B2|2005-03-29|Method and system for mapping strings for comparison
    JP3006766B2|2000-02-07|圧縮された状態におけるデータをエンコードし、デコードし、伝送する方法と装置
    US5627748A|1997-05-06|Method of identifying pattern matches in parameterized strings and square matrices
    US5861827A|1999-01-19|Data compression and decompression system with immediate dictionary updating interleaved with string search
    US7164370B1|2007-01-16|System and method for decoding data compressed in accordance with dictionary-based compression schemes
    DE10301362B4|2005-06-09|Blockdatenkompressionssystem, bestehend aus einer Kompressionseinrichtung und einer Dekompressionseinrichtung, und Verfahren zur schnellen Blockdatenkompression mit Multi-Byte-Suche
    US5333313A|1994-07-26|Method and apparatus for compressing a dictionary database by partitioning a master dictionary database into a plurality of functional parts and applying an optimum compression technique to each part
    US5883588A|1999-03-16|Data compression system and data compression device for improving data compression rate and coding speed
    Navarro et al.1999|A general practical approach to pattern matching over Ziv-Lempel compressed text
    JP3152868B2|2001-04-03|検索装置および辞書／テキスト検索方法
    JP3234104B2|2001-12-04|圧縮データをサーチする方法及びシステム
    US6522268B2|2003-02-18|Systems and methods for multiple-file data compression
    US7358874B2|2008-04-15|Data compression using a stream selector with edit-in-place capability for compressed data
    US6646577B2|2003-11-11|Method of performing Huffman decoding
    US6047298A|2000-04-04|Text compression dictionary generation apparatus
    TW312771B|1997-08-11|
    Silva de Moura et al.2000|Fast and flexible word searching on compressed text
    US5652878A|1997-07-29|Method and apparatus for compressing data
    Bell1986|Better OPM/L text compression
    US6664903B2|2003-12-16|Method, apparatus, computer program and storage medium for data compression
    US5371499A|1994-12-06|Data compression using hashing
    EP0813167B1|2003-10-01|Method and apparatus for font compression and decompression
    US5936560A|1999-08-10|Data compression method and apparatus performing high-speed comparison between data stored in a dictionary window and data to be compressed
    同族专利:
    公开号 | 公开日
    EP0871295A3|1998-12-23|
    DE69133377T2|2004-08-05|
    EP0472730B1|2000-05-10|
    KR920701899A|1992-08-12|
    DE69133481T2|2006-04-06|
    EP0871295A2|1998-10-14|
    EP0472730A4|1992-12-16|
    EP0878915A2|1998-11-18|
    EP0871294A3|1998-12-30|
    EP0472730A1|1992-03-04|
    KR950013228B1|1995-10-26|
    EP0871294A2|1998-10-14|
    DE69133481D1|2005-09-15|
    EP0871295B1|2004-03-24|
    EP0871294B1|2005-08-10|
    EP0878915A3|1998-12-30|
    DE69133377D1|2004-04-29|
    DE69132187D1|2000-06-15|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    1991-09-05| AK| Designated states|Kind code of ref document: A1 Designated state(s): KR US |
    1991-09-05| AL| Designated countries for regional patents|Kind code of ref document: A1 Designated state(s): DE FR GB |
    1991-10-24| WWE| Wipo information: entry into national phase|Ref document number: 1991904319 Country of ref document: EP |
    1992-03-04| WWP| Wipo information: published in national office|Ref document number: 1991904319 Country of ref document: EP |
    2000-05-10| WWG| Wipo information: grant in national office|Ref document number: 1991904319 Country of ref document: EP |
    优先权:
    申请号 | 申请日 | 专利标题
    JP2045163A|JP3038223B2|1990-02-26|1990-02-26|データ圧縮方式|
    JP2/45163||1990-02-26||
    JP2062325A|JP2590287B2|1990-03-13|1990-03-13|データ圧縮方法およびデータ圧縮装置|
    JP2/62325||1990-03-13||
    JP2/70379||1990-03-20||
    JP2070379A|JP2774350B2|1990-03-20|1990-03-20|データ圧縮方法および圧縮データのデータ復元方法|
    JP2275835A|JP2825960B2|1990-10-15|1990-10-15|データ圧縮方法及び復元方法|
    JP2/275835||1990-10-15||DE69132187T| DE69132187D1|1990-02-26|1991-02-26|Verfahren zur komprimierung und wiederherstellung von daten und gerät dazu|
    KR91701461A| KR950013228B1|1990-02-26|1991-02-26|데이타 압축과 복원방법 및 그 장치|
    EP19910904319| EP0472730B1|1990-02-26|1991-02-26|Data compression and restoration method and device therefor|
    [返回顶部]