JPH03270416A - データ圧縮および復元方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔概要〕 ＬＺ−符号において、並列処理により復号化を可能とし
たデータ圧縮方式および並列処理により復号化する方式
に関し、 復号処理を高速化することを目的とし、入力文字列につ
いて異なる文字部分列ごとに順次符号化して、現われる
順にアドレス指定して辞書に登録し、登録されている辞
書アドレスより常に一定数小さい辞書参照アドレスを設
定し、現在の符号化対象文字部分列を上記辞書参照アド
レスまでの範囲での辞書を参照し、辞書参照アドレスの
範囲で登録済の過去の文字部分列のうち一致する最大長
の文字部分列を求め、その複製として現在の符号化対象
文字部分列を符号化し、復号側において並列処理を可能
とする構成を持つ。

〔産業上の利用分野〕

データ通信においては、データを圧縮することで、通信
速度を向上させることができる。

特に、画像データの通信においては、データ量が多いた
め、データ圧縮、復号処理の高速化が望まれる。

本発明は、並列処理により高速度で復号化可能なデータ
圧縮および復号方式に関する。

データを圧縮する方法として、人力文字列を順次異なる
文字部分列ごとに順次符号化して記憶し、符号化済の過
去の最長の文字部分列の複製として現在の文字部分列を
符号化するデータ圧縮方式がある。

このような符号化方式には、増分分解型のＺｉｖ−Ｌｅ
ｍｐｅｌ符号による方式とそれを改良したＬＺ−符号に
よる方式があるが、本発明は、ＬＺ−符号による方式に
関するものである。

ＬＺπ符号符号の符号化側においては、辞書に登録され
たデータを全て検索して、次に符号化データを決定し、
復号化側では、符号データを、これまで復元したデータ
をもとにして復号化し、復号データを得ている。即ち、
復号化側では、１つ前の符号が復号されていることが復
号化の前提条件となるため、復号処理は１符号ごとにす
るシーケンシャルな動作となり、通常の方法では、複数
の符号を同時に並列に復号化することは不可能である。

本発明は、ＬＺＷ符号における符号化方式を改良し、復
号処理を並列実行できるようにした。

〔従来技術〕

ＬＺＷ符号によるデータ圧縮は、文字列を異なる文字部
分列に分は辞書に登録されている過去に出現した文字列
のうちから最長−成文字列を探し、その番号により符号
化する。同時に、一致した最長文字列より一文字延ばし
た文字列をあらたに新たに出現した文字列として辞書に
登録するものである。

第８〜１０図により従来のＬＺＷ符号化方弐を説明する
。

第８図（ａ）、　（ｂ）、　（Ｃ）は、簡単のため、ａ
、ｂｃの３文字よりなる場合についてデータを符号化し
て圧縮する場合および復号する場合を示している。

ＬＺＷ符号では、予め辞書に全文字につき一文字からな
る文字列を初期値として登録してから符号化を始める。

そして、文字列から、辞書に登録しである最長−数文字
部分列を捜し、その登録コードωをコードとして出力す
る。

一方、辞書には、その最長−成文字列に、不一致となっ
た次の一文字（拡張文字Ｋ）を足した文字列を継ぎ足し
た文字列を（ω、Ｋ）の組で表して辞書に登録する。

復号は符号化の逆の操作を行う。即ち、入力したコード
ωに対応する文字列の表現の組（ωＫ）を求める。次に
、同様に、ω°に対応する文字列の表現の組を求め、そ
のつと求めた拡張文字Ｋをスタンつておく。

この手順を繰り返して、番号ωが一文字に一致するまで
繰り返し最後にスタックした文字を出力し、各文字列を
復元する。

そして、辞書には、罰回使ったコードωと今回復号した
文字列の第１文字にの＆１１（ω、Ｋ）を登録し、復元
辞書を更新する。

第８図（ａ）、（ｂ）により、従来のＬＺＷ符号化方法
をａ、ｂ、ｃの三文字のみよりなる場合について、具体
的に説明する。

予め、初期化において、登録辞書には一文字ａ、ｂ、ｃ
をそれぞれコード１，２．３として登録しておく。

（１）　　図（ａ）に示す入力文字列において、先ず、
先頭の文字ａを人力する。ａは辞書にあるので、ａのコ
ードが１なので、ω−１として、次の文字ｂ　（Ｋ＝ｂ
）を入力する。その文字部分列ａｂ（ω＝１．に＝ｂ）
は辞書に登録されていないので、登録コード１を出力し
、ａｂ（ｌｂ）を登録コード４で辞書に登録する。

（２）　次に、いま入力したｂを文字列の先頭文字とし
て（ω＝２とする）、次の文字ａ　（Ｋ＝ａ）を人力す
る。

そこで、作成された文字部分列ｂａ（ω＝２゜Ｋ＝ａ　
）は、辞書に未登録であるので、登録コード２を出力し
、ｂａ　（２ａ）を登録コード５として、に登録する。

（３）　さらに、（２）で入力したａを文字列の先頭と
して（ω＝１）次の文字ｂ　（Ｋ＝ｂ）を入力する。

文字列ａｂは、既に登録コード４で登録されているので
、ωを現在の文字部分列ａｂの登録コード４として続く
文字Ｃを人力する（ω＝４．に＝Ｃ）。

文字列ａｂｃは未登録であるので、一致した最長文字部
分列ａｂを登録コード４で出力し、文字列ａｂｃ（４ｃ
）を登録コード６で、辞書に登録する。

（４）　そこで、今人力した文字Ｃを文字列の先頭文字
として（ω＝３）、続く文字すを入力する（Ｋ＝ｂ）。

文字列ｃｂ（３ｂ）は辞書に未登録であるので、文字Ｃ
を登録コード３（初期化において登録済）で出力し、文
字列ｃｂ（３ｂ）を登録コード７として辞書に登録する
。

以下同様の手順により、続く文字列について、登録済の
文字部分列から一致する最大長の文字部分列の登録コー
ドにより出力し、未登録の文字部分列は新たに登録コー
ドを定めて辞書に登録し、辞書を更新してゆく。

図（ｂ）は図（ａ）の入力文字列について、ＬＺＷ符号
により作成した参照辞書を示す。

人力されたコードを復号する場合には、例えば、符号８
が入力されると、図示の変換テーブルにより、８＝５ｂ
を読み取り、次に５＝２ａ、であるので、８＝２ａｂと
し、さらに２＝ｂから文字列ｂａｂを復号する。

図（Ｃ）に、ＬＺＷ符号の復号方式を示す。

図（Ｃ）は図（ａ）における文字列の出力コードを復号
する場合を示す。

復号は、符号化の手順の逆の操作を行う。

あらかしめ、初期化において、登録辞書には一文字ａ、
ｂ、ｃをそれぞれコードｌ、　　２．３として登録して
おく。

図示の入力コードを復号する場合により、従来のＬＺＷ
符号の復号手順を説明する。

（１）　先ず、最初の人力コード１が人力されると、辞
書を参照して文字ａを出力する。

ここで、入力コードｌは直前コードレジスタ（Ｏｌｄｃ
ｏｄｅ　）に残しておく。

（２）　次に入力コード２によりｂを出力する。

このとき、（１）の処理における入力コード１と、今復
元した文字列のｂの組の符号１ｂを辞書に登録コード４
として登録する。

そして、入力コード２は、０１ｄｃｏｄｅに保存してお
く。

（３）　次に人力コード符号４により辞書を参照してｌ
ｂを読み取り、さらにｌｂから文字列ａｂを復元する。

そして、（２）で復元した文字列の第１文字ａと０１ｄ
ｃｏｄｅの２とにより変換コード２ａを辞書に登録コー
ド５で登録する。

入力コード４は０１ｄｃｏｄｅに移して保存する。

（４）　次の入力コード３を入力する。

３はＣとして辞書に登録済であるから文字Ｃを復元し、
０１ｄｃｏｄｅのコード４といま復号した文字Ｃにより
変換コード４Ｃを辞書に登録コード６で登録する。

そして、入力コード３を０１ｄｃｏｄｅに移して保存す
る。

（５）　次の入力コード５を読み取る。

入力コード５は既に変換コード２ａとして登録されてい
るので、２ａより、文字部分列ｂａを復号する。

そして、今復号した文字部分列の第１文字すと０１ｄｃ
ｏｄｅに保存されているコード３により３ｂを辞書に登
録コード７で登録する。　入力コード５は０１ｄｃｏｄ
ｅに移して保存する。

同様の順を繰り返して、人力コードを順次復号し、辞書
を更新してゆく。

第９図に、従来のＬＺＷ符号化方式の符号化のフローを
示す。

上記の文字列ａｂａｂｃについて符号化する場合を例と
してフローを説明する。

■　初期化である。即ち、−文字ａ、ｂ、ｃを辞書に登
録する（ａ＝１．ｂ＝２、Ｃ−３）。

同時に、辞書の先頭アドレスｎを設定する。

図のフローは、２５６文字ある場合についてのものであ
るので、先頭アドレスとしてｎ＝２５６を設定しである
が、今の場合は、ａ、ｂ、ｃ三文字のみの場合を考えて
いるので、ｎ＝４を初期値として考える。

（１）　■　文字列の第１文字Ｋ　（Ｋ＝ａ）を語頭文
字列のωとする。

（２）　■　次の文字すを読む。

■　入力文字列の最後の文字の処理を終わっている場合
には、次の文字にはないので、終了処理に進む。

今は、入力文字列があるので、■に進む。

■　今ω＝ａ、に＝ｂであり、ωに＝ａ　ｂの文字部分
列は辞書にないので、■に進む。

■　辞書の書き込み可能領域の最大アドレスＮＭＡＸよ
り現時点の辞書アドレスｎが小さいか判断する。今の場
合、辞書アドレスｎはＮＭＡＸより小さいので■に進む
。

■　ω＝ａの登録コード（コード（ω））として１を出
力する。辞書にωに＝ａｂを登録コード４で登録する。

■　入力文字にの登録コードをωに移し、同時に辞書の
アドレスｎを１つ進める。

（３）　再び、■に戻り、次の文字ａを入力する。

今、ω−２であるので■でωに＝２ａを辞書と照合する
。未登録であり、ｎ＜ＮＭＡＸであるので、■でｂの登
録コード２（コード（ω））を出力する。そしてωに＝
２ａを辞書に登録コード５（ｎ−５）で登録する。さら
にωにいま入力した文字ａのコード１を移す。そして再
び■に戻る。

（４）　次の文字すを入力する。

この場合は、■における判断で、ωに＝１ｂは登録済で
あるので、■に進み、ω＝４とする。そこで、■に戻る
。

（５）　次の文字ＣをＫとして人力し、以降の処理を行
う。

■は、最終文字が、入力済の場合で、最終文字は■の処
理でωに入力されている状態であるから、そのコード（
コード（ω））を出力して符号の作成処理を終了する。

第１０図は、従来のＬＺＷ符号化方式の復号化のフロー
を示す。

第８図において例として説明した文字列の出力符号を用
いてフローを説明する。

復号化には、入力コードメモリ（ＣＯＤＥ）　、人力コ
ードを格納する入力メモリ（ＩＮｃｏｄｅ）　、直前コ
ードを格納するメモリ（Ｏｌｄｃｏｄｅ　）　、復号文
字の第１文字を格納するメモリ（ＦＩＮｃｈａ　ｒ　）
順次復元される復号文字を１時格納するメモリ（スタッ
ク）を用いる。

（１）■　初期化により、−文字についての符号は予め
、作成しておく。

最初のコードを読み込む（今の場合、■）。

０１ｄｃｏｄｅに読み込んだコードを入れる。

入力コード１と辞書の登録コードを参照して、文字にと
してａを出力する。

ａをＦＩＮｃｈａ　ｒに移して一時保存する。

（２）　■　次のコード（ＣＯＤＥ）を読み、ＩＮｃ。

ｄｅに入れる。

■　最後の符号まで読み取ってコードがない場合には処
理を終了する。

いまの場合は次のコード２があるので、■に進む。

■　Ｋをスタックに移す。第８図（ｂ）における登録コ
ード８のように、８が５ｂで５が２ａであるようなコー
ドの場合は、ωにの文字Ｋを順次スタツクに入力し、ω
を順次変換していってωＫが一文字になるまで処理を繰
り返す。

今の例の場合にとしてコード２に対応するｂをスタック
に格納する。

■　スタックに格納された文字すを出力する。

■　復号文字の第１文字、いまの場合は文字すをＦＩＮ
ｃｈａｒに格納する。

そして、（Ｏｌｄｃｏｄｅ　、　Ｋ）の組を辞書に登録
する。

今の場合、０１ｄｃｏｄｅには初期化において読み込ん
だ文字列の第１文字ａのコード１が格納されている。ま
たに＝ｂであるのでｌｂを登録コード４で格納する（新
しく登録する文字部分列の辞書アドレス（＝登録コード
）ｎは４から始まるものとする）。

ｎを１インクリメントする。

さらに、０１ｄｃｏｄｅにＩＮｃｏｄｅのデータを移す
、いまの場合、ＩＮｃｏｄｅのデータは２であるから、
０１ｄｃｏｄｅを２とする。

（３）　そこで、■に戻り、次の符号を読む。

次の符号は４である。そこで、■で辞書を参照すると符
号４は１ｂであるから、■でωに＝１ｂから、スタック
に順次すとａを格納し、■で文字ａｂを出力する。さら
に、復号文字列の第１文字ａをＦＩＮｃｈａｒに格納す
る。そして、いま０１ｄｃｏｄｅは２と復号文字の第１
文字をに＝ａにより、（２゜ａ）の組合せにより、符号
２ａを辞書に登録コード５　（ｎ＝５）で登録する。モ
してｎを１インクリメントする。

さらに、０１ｄｃｏｄｅに人力符号を移し、いまの場合
０１ｄｃｏｄｅを４とする。そして、■以降の処理を繰
り返す。

上記のように、入力コードを復号し、復号した文字列の
コードを記憶しておいて、次の入力コードにより、次の
文字列を復号した時点において、記憶しであるコードに
対応する文字部分列より１文字延ばした、未登録の文字
部分列を辞書に登録し、辞書を復元する。

図のフローにおいて、■は、例外的な処理の場合である
。

上記のように、ＬＺＷ号符号による圧縮処理では、符号
化においては、注目文字部分列の符号化を終了した時点
で、−文字のばした文字部分列を辞書に登録できるが、
復号化において、注目文字列を１文字延ばすときは、次
の文字部分列の先頭文字と合わせて辞書に登録するため
、次の文字列の復号が終了した時点でないと登録を行う
ことができない。

そのため、入力された符号を復元するために必要な登録
コードが、辞書に登録されていないような場合を生じる
ことがある。このような場合には、入力符号を復号でき
ないわけであるが、■はその場合の復号処理を行うため
のものである。

例えば、第８図（Ｃ）の入力コードにおいて、入力コー
ド１０が入力された場合を考える。

この時、０１ｄｃｏｄｅは１であり、ＦＩＮｃｈａｒは
ａである。

この時点では、辞書への登録は登録コード９までてあり
、１０は登録されていない。

そのため、入力コード１０を復元することができない。

そこで、■により、ＦＩＮｃｈａｒのａおよび、０１ｄ
ｃｏｄｅの１により、１ａをＩＮｃｏｄｅに入力する。

その後は、■以降の通常の場合と同様の処理により、ａ
ａを出力し、ｌａを辞書に符号１０で登録する。

〔発明が解決しようとする課題〕

従来のＬＺＷ符号は学習を重ねることにより圧縮率が向
上する。学習した結果のデータを辞書としてメモリに蓄
え、符号化、復号化の処理はこれら辞書に蓄えられたデ
ータへのアクセスを中心に処理が行われる。しかも、従
来のＬＺ−符号においては、前述のように、復号処理は
、１つ前の符号が復号されていることが前提になってい
るため、復号処理はｌ符号ごとに復号するシーケンシャ
ルな動作方式をとらざるを得す、並列処理により復号化
することは不可能であった。

そのため、従来のＬＺ−符号は、辞書に蓄えられたデー
タ量が増大するにつれ、符号化、復号化の処理には非常
に多くの時間を必要とするものであった。

本発明は、ＬＺ−符号において、復号処理を、複数の圧
縮符号について同時に復号する並列実行を可能にするデ
ータ圧縮方式を得ることを目的とする。

〔課題を解決するための手段〕

本発明は、ＬＺ−符号において、符号化側で符号化検索
のために参照する辞書の大きさを、全文字部分列の登録
されている辞書の大きさより小さくするようにした。

即ち、現時点における辞書の最大アドレスをｎとすると
、現文字部分列を符号化するために参照しする辞書はｎ
より小さいアドレスｎｓまでの部分とする。

この２つのアドレスの差、ｄｘ＝ｎ−ｎｓがあるため、
復号化側では、復号処理において、現在登録されている
辞書のｄｘ前までの辞書のデータにより復号することが
できる。

そのため、復号側では、アドレスの差分ｄｘ個の符号に
ついては、並列に復号することが可能になる。

そのため、復号処理を高速化することができる。

本発明のデータ圧縮処理の基本構成を第１図により説明
する。

図において、１は入力文字列、２は人力文字列を１文字
づつ読み取る文字読み出し部、３は文字読み取り部２に
より読み取られた文字により構成される文字部分列、４
は辞書を参照して文字部分列と照合をする辞書照合部で
、一致した場合には、文字読み出し部２が次の一文字を
読み出して、新たな文字部分列を作成するようにし、一
致しなかった場合には、不一致となった文字部分列を辞
書書き込み処理部に出力し、同時に一致した最大文字列
を符号化処理部に出力するもの、５は辞書照合部の不一
致となった文字部分列のうちの最後の１文字を除いた最
大−成文字列、６は最大−成文字列を符号化する符号化
処理部、７は辞書照合部で不一致となった最大−数文字
部分列に次の１文字を加えた登録文字列もの、８は登録
文字列の書き込み処理部、９は異なる文字部分列を出現
した順にアドレスを指定して登録した辞書、１０はあら
かじめ１文字等の文字を登録しておく初期登録辞書、１
１は辞書への書き込みの終了処理、１４は文字部分列を
照合する時点における辞書アドレスｎを判定する辞書ア
ドレス判定部、１５は辞書アドレスｎを表わすデータ、
１６は辞書アドレスｎと照合処理において参照する辞書
のアドレスである辞書参照アドレスｎｓとの差ｄｘ設定
部、１７は差分ｄｘのデータ、１８は辞書参照アドレス
ｎｓ設定部、１９は辞書参照アドレスｎｓのデータであ
る。

〔作用〕

第１図の基本構成の作用を、具体的な文字列を例として
説明する。

文字がａ、ｂ、ｃの三文字のみよりなり、人力文字列ａ
ｂａｂｃｂａｂ・・・の場合について考える。

辞書には、あらかじめ、三文字ａ、ｂ、ｃはそれぞれ登
録番号（辞書アドレスｎ）１．２．３で登録しておく。

辞書アドレスｎと辞書参照アドレスｎｓの差ｄｘ＝３と
する。

ｄｘ＝３に対応して、始めの３つの符号が出力されるま
では、従来のＬＺ−符号方式により符号化する。

（１）　即ち、文字読み出し部２は第１文字ａを読み取
り、辞書照合部ｌは辞書を参照して、致を判定する。そ
こで、文字読み取り部２は次の第２文字すを読み取る。

辞書照合部４は文字部分列すを辞書を参照し、不一致を
判定する。

そこで辞書書き込み処理部は文字部分列ａｂを登録番号
４で登録する。

同時に、符号化処理部６は第文字ａを符号ｌで出力する
。

（２）　同様に、文字読み出し部２は次に、第３番目の
文字ａを読み取り、文字部分列ｂａを辞書照合部は照合
する。

その結果、その文字部分列は不一致となるので、ｂａを
辞書に登録番号５で登録し、第２番目の文字すを符号２
で出力する。

（３）　次に、第４番目のｂを読み取り、文字部分列ｂ
ａを作成する。この文字部分列は、照合処理により一致
となるので、次の第５番目の文字Ｃを読み取り、文字部
分列ａｂｃを作成する。文字部分列ａｂｃは不一致とな
るので、辞書に登録番号６て登録する。同時に最大−数
文字部分列ａｂを登録番号４で符号化して出力する。

以上は、従来のＬＺ−符号符号による符号化方式である
。これ以降、本発明の符号化方式により符号化してゆく
。

（４）次に、第６番目の文字すを読み取る。現時点でｎ
＝６であるので、辞書参照アドレスｎ５＝３となり、現
在の文字部分列ｃｂの照合は、辞書のアドレス３までと
する。

文字部分列ｃｂは辞書参照アドレス３までに登録されて
いないので、照合不一致となり文字部分列ｃｂの登録処
理をする。

文字部分列ｃｂを登録番号７で登録し、同時に最大−数
文字部分列であるＣを登録番号３により符号化して出力
する。

ｎおよびｎｓをそれぞれ１インクリメントする。

（５）　次に、第７番目の文字ａを読み取る。

現時点において、ｎ５ｗ４であるから、文字部分列の参
照は参照辞書アドレス４までである。

現文字部分列ｂａは参照辞書アドレスまでの範囲にない
ので、照合結果は不一致となる。

本発明のデータ圧縮方式では、このような辞書参照アド
レスの範囲では登録されていないが、辞書アドレスｎｓ
＋１からｎ−１の範囲に既に登録されている文字部分列
が現れることがある。このような場合該当する文字部分
列を二重登録しても、登録処理をしないようにしても、
復号例の処理方式に対応させておけば、いずれでもよい
。

ここでは二重登録を可能とする。文字列ｂａについて登
録するとともに、最大−数文字部分列すを登録コード２
で符号化して出力する。

以下同様に続く入力文字列を照合時の辞書のアドレスｎ
よりｄｘだけ常に小さい辞書参照アドレスｎｓにより照
合して、最大−数文字列部分を符号化し、新しく現れる
文字部分列の登録処理を進めてゆく。

次に、本発明によるＬＺ−符号の復号化方式を説明する
。

第２図は本発明の圧縮データの復号処理の基本構成を示
す。

図において、２１は、入力符号、２２は入力符号読み取
り部、２３．２４．２５はそれぞれの符号番号（１）、
（２）、（３）として並列処理するために入力符号、２
６．２７．２８は入力符号を並列処理するための復号部
、２９は復号文字列、３０は初期登録辞書で、１文字等
の文字をあらかじめ登録しておくもの、３１は辞書、３
３は辞書書き込み処理部、３４は書き込みの終了処理、
３５．３６．３７は入力符号を辞書と参照する照合処理
、４０は新しく出現する文字部分列を作成するため、復
号されている現文字列より一つ前に復号された直前文字
部分列、４１は新しい文字部分列を作成するための現文
字部分列、４２は直前文字部分列と現文字部分列の第１
文字により登録文字部分列を作成する登録文字部分列作
成部である。

第２図の基本構成の作用は、次の通りである。

入力符号が１２４３２４・・・であり、復元文字はａ、
ｂ、ｃの３文字のみよりなり、ａ、ｂ、Ｃについては、
あらかじめ、それぞれ登録番号ｌ、２．３で辞書に登録
しておく。

ｄｘ＝３として、３つの入力符号について、並列に復号
処理する場合を考える。

ｄχ＝３に対応して、最初の３つの符号については、従
来どうりのＬＺ−符号の復号方式により復号化する。

（１）　第１番目の符号Ｉは、初期登録辞書３０を参照
しして、復号部により文字ａを復号する。

そして、直前文字部分列として残す。

（２）　次に、第２番目の符号２を入力し、初期登録辞
書３０を参照して、同様に文字すを復号し、同時に、（
１）で復号した直前文字ａとにより、登録文字部分列作
成部４２は文字部分列ａｂを作威し、辞書書き込み処理
部３３は登録番号４（辞書アドレス４）で登録する。　
そして、復号した文字すを直前文字部分列として残す。

（３）　同様に、第３番目の符号４を読み取り、辞書を
参照して文字部分列ａｂを復号する。同時に直前文字す
とにより、（２）で復号した文字部分列すとにより文字
部分列ｂａ登録番号５で辞書に登録する。そして、復号
した文字部分列ａｂを直前文字部分列として残す。

ここまでは、従来のＬＺ−符号の復号化方式である。以
降は、本発明の並列処理により復号処理を進めて行く。

（４）　続く３つの符号３．２．４を読み取り、それぞ
れ、入力順に符号番号（１）、（２）、（３）として、
現時点で復元されている辞書（辞書アドレス４）を参照
して各符号を復号する。

即ち、入力符号（１）は、３であるので復号部２６によ
り、辞書３１を参照して文字Ｃを復号する。

入力符号（２）は、２であるので、復号部２７により辞
書３１を参照して文字すを復号する。

入力符号（３）は、４であるので復号部２８により辞書
３１を参照して、文字部分列ａｂを復号する。

０そして、辞書の復元は、符号番号のに順に従って、復
号文字部分列より、従来と同し方法で復号してゆく。

即ち、入力符号（１）の復号文字Ｃを現文字列とし、直
前文字部分列ａｂとにより、文字部分列ａｂｃを登録番
号６で登録する。そして、Ｃを直前文字として残し、次
の復号文字すとにより文字部分列ｃｂを辞書に登録番号
７で登録する。そして、復号文字すを直前文字として残
す。

同様に、次の復号文字のａｂを現文字列として、その先
頭文字ａと１つ前の文字すとにより、登録文字部分列作
成部４２は登録文字部分列を作成する。この文字部分列
は登録済であるが、二重登録を許す方式の場合には辞書
に登録し、二重登録をしない方式の場合には登録しない
。ここでは、復号化に合わせてｂａを登録コード８で登
録する。

並列処理により復号された各文字列は、入力番号の順に
直列文字列に並べ換えて、文字列ａｂａｂｃｂａｂ・・
・を復号する。

以下同様の手順で、入力符号を３つづつ取り出して並列
復元処理を進め、全入力符号を復号する。

なお、上記の例では、３つづつの入力符号を並列処理す
る場合について説明したが、ｄｘを任意にとることによ
り並列処理する装置数を可変にとることが可能である。

〔実施例〕

本発明のデータ圧縮方式および復元方式の実施例を第３
図〜第７図により説明する。

第３図は、符号化処理の装置構成実施例を示す。

図において、５０は入力文字Ｋを格納する入力文字格納
レジスタ、５１は文字部分列ωを格納する文字部分列格
納レジスタ、５２は辞書アドレスｎを格納する辞書アド
レスレジスタ、５３は辞書参照アドレスｎｓを格納する
辞書参照アドレスレジスタ、５４はアドレス差分ｄｘを
格納するアドレス差分レジスタ、５５はメモリよりなる
プログラム処理における作業領域、５６は辞書を格納す
る辞書メモリ、５７は文字部分列の登録処理等を行う辞
書作成手段、５８は文字部分列の符号を作成する符号作
成手段、５９は符号出力手段、６０は入力文字を読み取
る入力文字読み取り手段である。

第４図に第３図の装置構成のフローの実施例を示す。

図示の番号に従って説明する。

■　１文字等の文字をあらかしめ辞書に登録する等の初
期化をする。

辞書アドレスｎに辞書の現登録文字列数を書き込む。

入力文字列の第１番目の文字を文字部分列格納レジスタ
ωに格納する。

■　予め定めたｄｘ個のコードを出力するまでは、従来
のＬＺＷ符号の符号化方式に従って符号化する。

■　辞書参照アドレスｎｓをｎ−ｄｘとする。

■　入力文字列から次の文字人力Ｋを読み取る。

■　入力文字があれば■に進む。

■、■　読み取った文字部分列ωＫが辞書の辞書参照ア
ドレスｎｓまでの範囲に見出せなくなるまで■〜■の処
理を繰り返し、文字部分列ωＫが辞書に存在しないこと
をｉｔ認すると■に進む。

■　ＮＭＡＸは、辞書定義領域の最大アドレスであり、
ｎがＮＭＡＸを超えた場合には文字部分列の登録処理を
行わない。辞書アドレスｎがＮＭＡＸ以下であれは■に
進む。

■　最大−数文字部分列であるωのコードを出力し、ω
Ｋを辞書アドレスｎに登録する。そして、辞書アドレス
をｎ＋１、辞書参照アドレスを１ｓ＋ｌとする。

最後に読み取ったＫを文字部分列格納レジスタωに格納
して■以下かの処理を繰り返す。

［相］　入力文字列を全て読み取って読み取るべき入力
文字がなくなると、それまで読み取ってあっり最大−数
文字部分列ωをコードで出力して処理を終了する。

なお、上記のフローは、文字部分列の二重登録を許す場
合のフローであるが、二重登録をしない場合には、登録
処理はしないで、最大−数文字部分列ωをコードで出力
し、Ｋを文字部分列格納レジスタωに格納する。そして
、辞書アドレスｎと参照辞書アドレスｎｓの１インクリ
メントをしないで■にもとり、符号化処理を繰り返し進
めて行く。

第５図に本発明の復号化の装置構成の実施例を示す。

図の装置は、共有メモリ方式のマルチマイクロプロセッ
サにより構成されている。

図において、７０は共有データメモリで、メインＣＰＵ
と復号用のＣＰＵの引数の受渡し、辞書の領域として使
用さるもの、７１は共有メモリへのアクセスに対してメ
インＣＰＵと並列処理での復号化する複数の復号用復号
用ＣＰＵのバスの切り替えを行うバス制御スイッチ、７
２は全体の処理を制御するメインＣＰＵ、７３−１〜７
３−ｍは並列処理により復号処理を実行する復号用ＣＰ
Ｕで、ｄｘの数だけ用意されるもの、７４はメインＣＰ
Ｕのコントロールプログラム等を格納し、メインプログ
ラムの実行作業領域であるローカルメモリ、７４−１〜
７４−ｍは復号プログラムを格納し並列処理による入力
符号を復号作業の作業領域であるローカルメモリで、作
業用の変数の格納や復号用のスタックとして使用さるも
の、７５゜７５−１〜７５−ｍは、例えば、入力コード
を順次変換コードを介して出力文字に変換する際（入力
コード８→５　ｂ−＋２　ａ　ｂ−＋ｂ　ａ　ｂ　　第
８図（ｃ）参照・）に入力された文字列順に復号文字を
出力する処理するＦＩＦＯバッファ、７６は各ＦＩＦＯ
バッファ７５−１〜７５−ｍの並列復号文字を直列文字
列に変換するマルチプレクセ、７７はＦＩＦＯバッファ
７５とマルチプレクセ〕７６からの並列文字列をそれぞ
れの復号用のＣＰＵに渡さされた符号番号に従って符号
番号順に直列文字列に変換するマルチプレクセである。

図の構成において、それぞれの復号用のＣＰＵは終了を
割り込みによりメインＣＰＵ７２に知らせる。

第６図および第７図により、第５図の装置構成のフロー
の実施例を説明する。

第６図は、メインＣＰＵにおけるフローである。

図の番号に従ってフローを説明する。

■　従来のＬＺＷ符号化方法により、ｄｘ個のコードを
復号する。

■　辞書参照アドレスｎｓをｎ−ｄｘとして、辞書参照
アドレスを設定する。

■　新たな符号を読み取る。読み取る符号がなければ、
処理を終了し、符号があれば、■に進む。

■　ｄｘ個の符号を、人力符号と並列処理符号について
、入力順につけた符号番号を引数として並列復号処理を
する。

■　全ての復号の終了を確認することにより、並列復号
の同期をとり、辞書に復号文字部分列を登録する。

■　二重登録を許す場合にはｄｘ個辞書に登録されるの
で、辞書アドレスｎおよび参照辞書アドレスｎｓをｄｘ
だけインイクリメントする。

以上の処理を新たな符号の読み取りがなくなるまで繰り
返す。

なお、図のフローは文字部分列の二重登録を許す場合の
フローであるが、二重登録を許さない場合のフローは■
におけるｎとｎｓのインクリメントを登録されて更新さ
れた数だけとなる。

第７図に、第６図におけるフローの番号■における処理
のフローを示す。

この部分は、並列復号処理における各ＣＰＵにおける復
号処理のフローである。

図において、■〜■は、人力符号に、並列処理において
入力順を示す符号番号を付して処理を進める点を除いて
、第１０図におけるフローと処理が同じであるのでこの
部分の説明は省略する。

■は、直前文字列ωと読み取り文字Ｋ（新たな文字部分
列ωＫ）と符号番号を決定し、復号化の終了を、メイン
ＣＰＵに知らせる。

〔発明の効果〕

本発明によれば、シーケンシャルに符号化されたＬＺＷ
符号による圧縮データであっても、復号化側で並列処理
が可能となるため、復号処理を高速化できる。

【図面の簡単な説明】

第１図は、本発明のデータ圧縮方式の基本構成を示す図
である。 第２図は、本発明の圧縮データの復号方式の基本構成を
示す図である。 第３図は、本発明の符号化処理の装置構成実施例を示す
図である。 第４図は、本発明の符号化のフローの実施例を示す図で
ある。 第５図は、本発明の符号化の装置構成の実施例を示す図
である。 第６図は、復号処理フローの実施例を示す図である。 第７図は、並列復号処理フローの実施例を示す図である
。 第８図は、従来のＬＺＷ符号の符号化と復号化の方式を
示す図である。 第９図は、従来のＬＺＷ符号化方式のフローを示す図で
ある。 第１０図は、従来のＬＺＷ復号化方式のフローを示す図
である。 第１図において １　：　入力文字列、 ２　：　文字読みだし部、 ３　；　文字部分列、 ４　：　辞書照合部、 ５　：　最大−数文字部分列、 ６　：　符号化処理部、 ７　：　登録文字部分列、 ８　：　書き込み処理部、 ９　：　辞書、 ｌＯ：　初期登録辞書、 １１：　書き込み終了処理、 １４：　辞書アドレス判定部、 １５：　辞書アドレスデータ、・ １６：　　ｄｘ設定部、 １７：　　ｄｘデーク、 】８：　辞書参照アドレス設定部、 Ｉ９：　辞書参照アドレスデータ、

Claims (1)

1. 【特許請求の範囲】 １）入力文字列について異なる文字部分列ごとに順次符
   号化して、現われる順にアドレス指定して辞書に登録し
   、 登録されている辞書アドレスより常に一定数小さい辞書
   参照アドレスを設定し、 現在の符号化対象文字部分列を上記辞書参照アドレスま
   での範囲での辞書を参照し、 当該辞書参照アドレスの範囲で登録済の過去の文字部分
   列のうち一致する最大長の文字部分列を求め、その複製
   として現在の符号化対象文字部分列を符号化し、復号側
   において並列処理を可能とすることを特徴とするデータ
   圧縮方式。 ２）請求項１に記載のデータ圧縮方式により、作成され
   た入力符号を、並列処理サイクルごとに並列処理する入
   力符号を取り出し、 各並列入力符号を辞書を参照して復号し、復号文字によ
   り辞書を更新し、 並列復号文字を、対応する入力符号の入力順に直列復号
   文字に変換して出力することを特徴とする並列処理によ
   る圧縮データ復元方式。 ３）並列に復号する処理を共有メモリ方式のマルチマイ
   クロプロセッサにより行うことを特徴とする請求項２に
   記載の圧縮データ復元方式。