(57)【特許請求の範囲】
【請求項１】
２ｎ（但し、ｎは０以上の整数定数）個の長さの文字列データを入力とし、その情報を損なうことなしにデータを圧縮したコード列データを出力する文字列データ圧縮符号化装置であって、
圧縮前の文字列データを先頭から順次読み込む入力処理手段と、
圧縮符号化後のコード列データを先頭から順次出力する出力処理手段と、
ある有限の容量の辞書と、
前記入力処理手段から入力された長さ２ｎの入力文字列データをその前半部と後半部のそれぞれ半分の長さの２つの部分列に区切り、得られた該部分列の前半部と後半部に区切り、これを繰り返して、長さ１，２，４，８，１６、…２ｎの部分列に分解するために参照される分解規則と、
前記分解規則を参照して前記入力処理手段から入力された前記入力文字列データを順次読み込みながら、前記長さ１，２，４，８，６、…，２ｎの部分列を取り出して、異なる文字列毎に異なる登録番号を付与して、前記辞書にその容量の許す限り格納し、該辞書を参照しながら、該入力文字列データを読み込むことにより、該入力文字列データの中に同一の文字列が複数回繰り返して出現したことを検出する検出手段と、
前記入力文字列データに同一の文字列からなる部分列が複数回繰り返して出現する場合には、１回目は文字列と該文字列の登録番号の組を出力するように前記出力処理手段に指示し、２回目以降は、該部分列を指し示す登録番号のみを出力するよう該出力処理手段に指示する出力制御手段とを有することを特徴とする文字列データ圧縮符号化装置。
【請求項２】
任意の長さの文字列データが入力された場合に、入力文字列データの長さがちょうど２ｎ（但し、ｎはなるべく小さい整数定数）となるように、空白を表す特別な文字を文字列データの末尾に複数個追加する手段を有する請求項１記載の文字列データ圧縮符号化装置。
【請求項３】
前記検出手段は、
長さ２以上の任意の文字列ａを、前半部と後半部のそれぞれ半分の長さの２つの部分列ａ１と部分列ａ２に分解し、該部分列ａ１と該部分列ａ２の文字列がすでに前記辞書に格納されている場合に、該部分列ａ１と該部分列ａ２の文字列を指し示す登録番号の組を持って文字列ａを表現し、該組に該文字列ａを表す新たな登録番号を与えて該辞書に格納する格納手段を有し、
前記出力制御手段は、
長さ２以上の文字列ａを出力する際に、前半部と後半部の２つの部分列ａ１，部分列ａ２の文字列が前記辞書に格納されていない場合には、該部分列ａ１，部分列ａ２の文字列を順次出力させることにより、文字列ａを表現し、該部分列ａ１、該部分列ａ２の片方または両方の文字列が該辞書に格納済の場合には、格納済の文字列を出力する代わりに該文字列が指し示す登録番号を出力させる手段を有する請求項１記載の文字列データ圧縮符号化装置。
【請求項４】
前記格納手段は、
前記辞書の容量が限界に達して、新しい文字列ｘを格納できなくなった場合に、これまでに格納された文字列の中で、他の文字列の前半部または後半部としてまだ一度も使われていない文字列ｙを検索し、該文字列ｙを表す該文字列ｙの前半部と後半部を指し示す登録番号の組を一旦消去し、消去した文字列ｙと同じ登録番号で指し示される記憶領域に新しい文字列ｘを表す情報を格納し、以降の処理を進める手段を有する請求項３記載の文字列データ圧縮符号化装置。
【請求項５】
文字列データ圧縮符号化装置により圧縮符号化されたコード列データから元の文字列データを復元して取り出す文字列データ復元装置であって、
圧縮符号化されたコード列データを先頭から順次読み込む入力処理手段と、
復元した文字列データを先頭から順次出力する出力処理手段と、
文字列データを圧縮したときに用いた文字列データ圧縮符号化装置の辞書と同等または、それ以上の容量の辞書と、
前記入力処理手段から取得した圧縮符号化されたコード列データを順次読み込む際に、単純な文字列として表現された部分列を読み込んだ場合には、該文字列をそのまま出力するように前記出力処理手段に指示し、部分列の登録番号と文字列の組を読み込んだ場合には、前記辞書に該文字列を該登録番号を付与して格納し、部分列の登録番号のみを読み込んだ場合には、該登録番号が指し示す部分列を該辞書から取り出して出力するように該出力処理手段に指示する復元制御手段とを有することを特徴とする文字列データ復元装置。
【請求項６】
前記復元制御手段は、
圧縮符号化された前記コード列データを順次読み込む際に、前半部と後半部の２つの部分列の組によって表現された文字列が入力された場合に、該前半部と該後半部の部分列の登録番号の組をもって該文字列を表現して前記辞書に格納する手段と、
前記辞書に格納された部分列を取り出して、出力する際には、該部分列の前半部と後半部の部分列を該辞書から順次参照し、それらの部分列がさらに前半部と後半部の組として表現されている場合には、さらにそれらを順次参照し、長さ１の部分列を取り出して出力させる手段を更に有する請求項５記載の文字列データ復元装置。
【請求項７】
任意の２個の文字に対して１個の文字を計算して出力する、ある二項演算が定義されている場合に、長さが同じ２本の文字列データを入力として、先頭からそれぞれ同じ位置にある文字同士について、所定の二項演算を計算した結果を表す１本の文字列データを出力する文字列データ演算処理装置であって、
圧縮符号化されたコード列データを先頭から順次読み込む第１の入力手段と、復元した文字列データを先頭から順次出力する第１の出力手段と、文字列データを圧縮した時に用いた文字列データ圧縮符号化装置の辞書と同等または、それ以上の容量の第１の辞書と、該第１の入力手段から取得した圧縮符号化されたコード列データを順次読み込む際に、短単純な文字列として表現された部分列を読み込んだ場合には、該文字列をそのまま出力するように該第１の出力手段に指示し、部分列の登録番号と文字列の組を読み込んだ場合には、該第１の辞書に該文字列を該登録番号を付与して格納し、部分列の登録番号のみを読み込んだ場合には、該登録番号が指し示す部分列を該第１の辞書から取り出して出力するように該第１の出力手段に指示する復元制御手段とを有する２つの文字列データ復元装置からなり、入力されたコード列データを文字列データにそれぞれ復元して転送する２つの入力処理手段と、
前記入力処理手段から転送された２つの文字列データの、先頭からそれぞれ同じ位置にある文字同士の二項演算を順次計算し、その結果を新たな文字列データとして転送する演算処理手段と、
圧縮前の文字列データを先頭から順次読み込む第２の入力手段と、圧縮符号化後のコード列データを先頭から順次出力する第２の出力手段と、ある有限の容量の第２の辞書と、該第２の入力手段から入力された長さ２ｎの入力文字列データをその前半部と後半部のそれぞれ半分の長さの２つの部分列に区切り、得られた該部分列の前半部と後半部に区切り、これを繰り返して、長さ１，２，４，８，１６、…２ｎの部分列に分解するために参照される分解規則と、該分解規則を参照して該第２の入力手段から入力された該入力文字列データを順次読み込みながら、該長さ１，２，４，８，１６、…２ｎの部分列を取り出して、異なる文字列毎に異なる登録番号を付与して、該第２の辞書にその容量の許す限り格納し、該第２の辞書を参照しながら、該入力文字列データを読み込むことにより、該入力文字列データの中に同一の文字列が複数回繰り返して出現したことを検出する検出手段と、該入力文字列データに同一の文字列からなる部分列が複数回繰り返して出現する場合には、１回目は文字列と該文字列の登録番号の組を出力するように該第２の出力手段に指示し、２回目以降は、該部分列を指し示す登録番号のみを出力するよう該第２の出力手段に指示する出力制御手段とを有する文字列データ圧縮符号化装置であり、前記演算処理手段から転送された前記文字列データを圧縮符号化してコード列データとして出力する出力処理手段とを有することを特徴とする文字列データ演算処理装置。
【請求項８】
前記入力処理手段と前記出力処理手段は、部分列がそれぞれの前記第１の辞書または前記第２の辞書に格納または参照された場合に、それぞれの登録番号の情報を転送する転送手段を更に有し、
前記転送手段から前記登録番号の情報を取得し、ある２つの入力部分列の組に対する二項演算の結果がどの部分列に対応したかを、２つの入力部分列と１つの出力部分列の３つの部分列の登録番号の組として、ある有限の容量の演算高速化辞書に該容量が許す限り格納し、該演算高速化辞書を参照しながら演算処理を順次行うことにより、同一の入力部分列の組が複数回出現したことを検出する検出手段と、
同一の入力部分列の組が出現したときには、前記入力処理手段において、部分列の登録番号を文字列データに復元する処理を省略するように制御し、前記出力処理手段において前記演算高速処理辞書に格納されている演算結果の部分列の登録番号をそのまま出力するように制御する制御手段を更に有する請求項７記載の文字列データ演算処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、文字列データ圧縮符号化装置及び文字列データ復元装置及び文字列データ演算処理装置に係り、特に、データの通信及び加工及び、文字列データを圧縮符号化して効率よく伝送または保存し、圧縮符号化された文字列データ同士の演算処理を高速に実行するための文字列データ圧縮符号化装置及び文字列データ復元装置及び文字列データ演算処理装置に関する。
【０００２】
【従来の技術】
入力文字列を、過去に現れた文字列の複製として符号化するデータ圧縮方式として、Ｌｅｍｐｅｌ−Ｚｉｖ符号化方式が広く知られている。また、これを改良した方式に関する多数の特許が出願されている。例えば、特許第２５９０２８７号には、Ｌｅｍｐｅｌ−Ｚｉｖ符号化方式を改良した方式に関する発明が記載されている。
【０００３】
一般に、Ｌｅｍｐｅｌ−Ｚｉｖ符号化方式は、過去に入力された文字列の履歴（の一部）を記憶するメモリと、その中に含まれる部分列を登録・検索する辞書を持ち、入力文字列データを順次読み込みながら、辞書に部分列を登録し、これを参照して同一の部分列を検出することにより、データ圧縮を行う方式である。Ｌｅｍｐｅｌ−Ｚｉｖ符号化方式にはユニバーサル型と増分分解型の２つの方式がある。
【０００４】
ユニバーサル型Ｌｅｍｐｅｌ−Ｚｉｖ符号化方式は、入力文字列を符号化する際に、過去の入力文字列の任意の位置から現在の文字列に一致する最大長の文字列部分を区切り（文字列部分列という）、その文字部分列のメモリ上の位置と文字列部分列の長さにより指定してデータ圧縮を行う方式である。
増分分類型Ｌｅｍｐｅｌ−Ｚｉｖ符号化方式は、過去にコード化された最大長の文字列に新たに出現した一文字を付加した文字列を符号化して登録し、現在の文字列を過去に現れた文字部分列の最長文字部分列の複製として符号化する方式である。
【０００５】
いずれの方式においても、文字列データの圧縮率を高めることと、圧縮・復元処理を効率よく実行できること、の２点を目的として発明及び改良がなされている。即ち、圧縮符号化されたコード列データは、一旦、復元処理を通して元の文字列データに戻した後に、種々の演算処理に供されることを想定している。圧縮符号化されたコード列データを復元処理を通さずに直接演算処理を行うことは、従来技術では考慮されておらず、このような演算処理を効率よく行えるように工夫された符号にはなっていない。
【０００６】
一方、データを圧縮して記憶装置に格納し、圧縮したままの状態で高速に演算処理を行う方法として、「二分決定グラフ」と呼ばれるデータ構造を用いた論理関数データの表現方式及び演算方式が知られている。その処理方式は、Ｒ．Ｅ．  Ｂｒｙａｎｔ：”Ｇｒａｐｈ−Ｂａｓｅｄ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｂｏｏｌｅａｎ  Ｆｕｎｃｔｉｏｎ  Ｍａｎｉｐｕｌａｔｉｏｎ”，  ＩＥＥＥ  Ｔｒａｎｓ．  ｃｏｍｐｕｔ．，  Ｖｏｌ．  Ｃ−３５，  Ｎｏ．８，  ｐｐ．６７７−６９１（以後、論文１と呼ぶ）に記載されている。また、情報処理学会誌「情報処理」１９９３年５月号５８４〜６３０ページの「特集  ＢＤＤ（二分決定グラフ）」（以後、記事２と呼ぶ）にも詳しい解説記事が掲載されている。
【０００７】
論理関数データとは、ある複数個の入力変数に０，１の論理値の組み合わせがそれぞれ与えられたときに、関数値として０，１のいずれの論理値が出力されるか、という論理関数の情報を表したものである。
二分決定グラフが発明される以前は、論理関数データを表現するために、２ｎ  通りの入力変数値の組み合わせ（ｎは入力変数の個数）に対する関数値を羅列した「真理値表」と呼ばれる０，１の数列の形式で表現する方式が多く用いられている。図１２は、Ｘ１  ，Ｘ２  ，Ｘ３  の３変数を入力とする論理関数データを表現する真理値表の一例である。
【０００８】
二分決定グラフは、グラフを用いた論理関数データの表現方法であって、
・すべての入力変数に、ある固定した順序を与える手段（以下、順序付け処理と呼ぶ）、
・入力変数の中のある１つの変数に０及び１の論理値を代入することにより、論理関数から２つの部分関数を導出する手段（以下、展開処理と呼ぶ）、
・上記展開処理を、上記順序付け処理により与えられる順序に従って、０，１を代入する入力変数がなくなるまで繰り返し、個々の展開処理を表す中間節点、個々の展開処理により得られた２つの部分関数を指す０−枝及び１−枝、展開処理の繰り返しの結果得られた０，１の論理値を表す０−終端節点と１−終端節点、を用いた図１３のような二分木グラフを生成する手段（以下、二分木生成処理と呼ぶ）、
・上記二分木生成処理において、図１４のように、該二分木のある２つの中間節点の０−枝同士、１−枝同士がそれぞれ同一の節点を指しているかどうかを調べ、そのような論理的に等価な２つの中間節点を発見した場合に、その一方の中間節点を消去し、他方の中間節点を共有して用いる手段（以下、共有化処理と呼ぶ）、
・個々の中間節点において、図１５のようにその０−枝と１−枝が、共に同じ節点を指しているときには、該中間節点を取り除き、枝を直結させる手段（以下、非冗長化処理と呼ぶ）、
からなる。
【０００９】
上記の処理を組み合わせて行うことにより、図１６のような二分決定グラフが得られる。この二分決定グラフは、図１７のように中間節点を列挙した表の形式で記憶装置に格納することができる。このときに必要とする記憶量は、二分決定グラフの節点数に比例したものとなる。論理関数データを真理値表で表現した場合は、入力変数の値の組み合わせの数（変数の個数をｎとすると２ｎ  通り）の記憶量が常に必要となるが、２分決定グラフを用いるとそれよりも少ない記憶量となる場合がしばしばあり、ときには、圧縮率が数百倍に達する例もある。そのため、二分決定グラフは論理関数データの圧縮記憶方式として、近年広く利用されている。
【００１０】
さらに、論文１、及び記事２には、二分決定グラフ同士の二項演算処理方式が記憶されている。即ち、２つの二分決定グラフが記憶装置に格納されているときに、それらの二分決定グラフが表す論理関数データ同士の二項論理演算（論理関、論理和、排他的論理和、等）を実行し、その演算結果の論理関数データを表現する新しい二分決定グラフを生成し、記憶装置に格納する方法が述べられている。
【００１１】
その演算方法は、与えられた２つの二分決定グラフの最も上位の変数に０及び１を代入することにより、各々対応する２つの中間節点の組に分解し、得られた中間節点の組をさらに分解し、これを繰り返して、多数の終端節点の組を得る。それらの終端節点の組の各々に対する２項演算結果を表す終端節点を新たに生成し、そのようにして得られた演算結果を再び二分決定グラフに組み上げることにより、新しい二分決定グラフを生成する。このとき、演算処理中に現れた中間節点の組とその組に対する演算結果とを辞書に登録することにより、同じ中間節点の組を検出したときには、それ以上分解せず、直ちに辞書に登録されている中間節点を参照して演算結果とする、という高速化手段を具備している。
【００１２】
この演算方法の計算時間は、演算対象として与えられた２つの二分決定グラフの節点数と、演算結果として生成された二分決定グラフの節点数の総和にほぼ比例する。従って、真理値表データ形式を用いた論理演算方式と比較すると、二分決定グラフによるデータ圧縮率にほぼ比例して、演算処理高速化の効果が得られる。
【００１３】
【発明が解決しようとする課題】
Ｌｅｍｐｅｌ−Ｚｉｖ符号化方式では、圧縮符号化されたコード列データは、一旦、復元処理を通して元の文字列データに戻した後に、種々の演算処理に供されることを想定している。圧縮符号化を行うことにより、伝送データ量または、記憶領域が節約できるが、圧縮・復元のための処理時間が余計に必要となる。圧縮率と処理時間は一般にトレードオフの関係にあると考えられている。
【００１４】
しかし、圧縮符号化されたコード列データを復元せずに直接演算処理をすることができれば、圧縮・復元のための処理時間が不要になるばかりでなく、データの圧縮率に比例して演算処理時間を短縮することも可能になると考えられる。
そのためには、圧縮符号化の際の部分列の区切り方を、演算処理しやすいように工夫する必要がある。ところが、従来のＬｅｍｐｅｌ−Ｚｉｖ符号化方式では、入力される文字列データの内容により異なる位置で部分列が区切られるため、２本の圧縮コード列同士の二項演算処理を実行しようとすると、それぞれの部分列データの対応関係が複雑となり、圧縮したままでは効率よく演算処理を実行することができないという問題がある。
【００１５】
一方、二分決定グラフを用いた二項論理演算処理方式では、圧縮したままのデータ形式で二項演算処理を実行することができ、圧縮率にほぼ比例する高速化が実現されている。
しかし、二分決定グラフを用いた二項論理演算処理方式では、演算対象の２つの二分決定グラフは記憶装置内に節点表として格納された状態で演算処理装置に引き渡され、演算結果の二分決定グラフも記憶装置内に節点表として生成される。従って、これらの二分決定グラフの全ての節点が前以って記憶装置内に格納可能であることが必要条件となっている。従来の技術の項で記載した二分決定グラフの共有化処理と非冗長化処理では、節点の一致判定を高速に行うために、全ての節点を記憶装置内の辞書に登録・検索する方式が用いられている。辞書の容量は有限であり、演算結果の二分決定グラフが辞書に入り切らなくなった場合には、処理の途中で異常終了し、演算処理の結果を得ることができないという問題がある。
【００１６】
さらに、二分決定グラフを用いた二項演算処理方式では、演算対象の２つの二分決定グラフのすべての節点を記憶装置に格納してからでなければ演算処理を開始できない。即ち、前段の処理が完了しないと次段の処理を開始できない。よって、連続する演算処理を直列接続してパイプライン式に並行実行することができないという問題がある。
【００１７】
本発明は、上記の点に鑑みなされたもので、圧縮符号化されたコード列データを必ずしも完全に復元せずに直接演算処理することができ、データ圧縮率に応じて演算処理の高速化が可能となるような、文字悦データ圧縮符号化装置及び文字列データ復元装置及び文字列データ演算処理装置を提供することを目的とする。
また、本発明は、従来の二分決定グラフを用いた演算処理方式のようにすべての入力データを記憶装置内に格納してから演算を開始するのではなく、入力された圧縮コード列データを先頭から順次読み込むと同時に演算処理を実行し、演算結果を順次出力することが可能な文字列データ圧縮符号化装置及び文字列データ復元装置及び文字列データ演算処理装置を提供することを目的とする。
【００１８】
【課題を解決するための手段】
図１は、本発明の原理構成図（圧縮符号化装置）である。
本発明（請求項１）は、２ｎ（但し、ｎは０以上の整数定数）個の長さの文字列データを入力とし、その情報を損なうことなしにデータを圧縮したコード列データを出力する文字列データ圧縮符号化装置であって、
圧縮前の文字列データを先頭から順次読み込む入力処理手段１１０と、
圧縮符号化後のコード列データを先頭から順次出力する出力処理手段１２０と、
ある有限の容量の辞書１３０と、
入力処理手段１１０から入力された長さ２ｎの入力文字列データをその前半部と後半部のそれぞれ半分の長さの２つの部分列に区切り、得られた該部分列の前半部と後半部に区切り、これを繰り返して、長さ１，２，４，８，１６、…２ｎの部分列に分解するために参照される分解規則１５０と、
分解規則１５０を参照して入力処理手段１１０から入力された入力文字列データを順次読み込みながら、長さ１，２，４，８，６、…，２ｎの部分列を取り出して、異なる文字列毎に異なる登録番号を付与して、辞書にその容量の許す限り格納し、該辞書を参照しながら、該入力文字列データを読み込むことにより、該入力文字列データの中に同一の文字列が複数回繰り返して出現したことを検出する検出手段１４１と、
入力文字列データに同一の文字列からなる部分列が複数回繰り返して出現する場合には、１回目は文字列と該文字列の登録番号の組を出力するように出力処理手段１２０に指示し、２回目以降は、該部分列を指し示す登録番号のみを出力するよう該出力処理手段１２０に指示する出力制御手段１４２とを有する。
【００１９】
本発明（請求項２）は、任意の長さの文字列データが入力された場合に、入力文字列データの長さがちょうど２ｎ  （但し、ｎはなるべく小さい整数定数）となるように、空白を表す特別な文字を文字列データの末尾に複数個追加する手段を有する。
本発明（請求項３）は、検出手段１４１において、
長さ２以上の任意の文字列ａを、前半部と後半部のそれぞれ半分の長さの２つの部分列ａ１と部分列ａ２に分解し、該部分列ａ１と該部分列ａ２の文字列がすでに辞書に格納されている場合に、該部分列ａ１と該部分列ａ２の文字列を指し示す登録番号の組を持って文字列ａを表現し、該組に該文字列ａを表す新たな登録番号を与えて該辞書１３０に格納する格納手段を有し、
出力制御手段１４２において、
長さ２以上の文字列ａを出力する際に、前半部と後半部の２つの部分列ａ１，部分列ａ２の文字列が辞書１３０に格納されていない場合には、該部分列ａ１，部分列ａ２の文字列を順次出力させることにより、文字列ａを表現し、該部分列ａ１、該部分列ａ２の片方または両方の文字列が該辞書１３０に格納済の場合には、格納済の文字列を出力する代わりに該文字列が指し示す登録番号を出力させる手段を有する。
【００２０】
本発明（請求項４）は、格納手段において、
辞書１３０の容量が限界に達して、新しい文字列ｘを格納できなくなった場合に、これまでに格納された文字列の中で、他の文字列の前半部または後半部としてまだ一度も使われていない文字列ｙを検索し、該文字列ｙを表す該文字列ｙの前半部と後半部の文字列を指し示す登録番号の組を一旦消去し、消去した文字列ｙと同じ登録番号で指し示される記憶領域に新しい文字列ｘを表す情報を格納し、以降の処理を進める手段を有する。
【００２１】
図２は、本発明の原理構成図（文字列データ復元装置）である。
本発明（請求項５）は、文字列データ圧縮符号化装置により圧縮符号化されたコード列データから元の文字列データを復元して取り出す文字列データ復元装置であって、
圧縮符号化されたコード列データを先頭から順次読み込む入力処理手段２１０と、
復元した文字列データを先頭から順次出力する出力処理手段２２０と、
文字列データを圧縮したときに用いた文字列データ圧縮符号化装置の辞書と同等または、それ以上の容量の辞書２３０と、
入力処理手段２１０から取得した圧縮符号化されたコード列データを順次読み込む際に、単純な文字列として表現された部分列を読み込んだ場合には、該文字列をそのまま出力するように出力処理手段２２０に指示し、部分列の登録番号と文字列の組を読み込んだ場合には、辞書２３０に該文字列を該登録番号を付与して格納し、部分列の登録番号のみを読み込んだ場合には、該登録番号が指し示す部分列を該辞書２３０から取り出して出力するように該出力処理手段２２０に指示する復元制御手段２４０とを有する。
【００２２】
本発明（請求項６）は、復元制御手段２４０において、
圧縮符号化されたコード列データを順次読み込む際に、前半部と後半部の２つの部分列の組によって表現された文字列が入力された場合に、該前半部と該後半部の部分列の登録番号の組をもって該文字列を表現して辞書２３０に格納する手段と、
辞書２３０に格納された部分列を取り出して、出力する際には、該部分列の前半部と後半部の部分列を該辞書２３０から順次参照し、それらの部分列がさらに前半部と後半部の組として表現されている場合には、さらにそれらを順次参照し、長さ１の部分列を取り出して出力させる手段を更に有する。
【００２３】
図３は、本発明の原理構成図（文字列データ演算処理装置）である。
本発明（請求項７）は、任意の２個の文字に対して１個の文字を計算して出力する、ある二項演算が定義されている場合に、長さが同じ２本の文字列データを入力として、先頭からそれぞれ同じ位置にある文字同士について、所定の二項演算を計算した結果を表す１本の文字列データを出力する文字列データ演算処理装置であって、
圧縮符号化されたコード列データを先頭から順次読み込む第１の入力手段と、復元した文字列データを先頭から順次出力する第１の出力手段と、文字列データを圧縮した時に用いた文字列データ圧縮符号化装置の辞書と同等または、それ以上の容量の第１の辞書と、該第１の入力手段から取得した圧縮符号化されたコード列データを順次読み込む際に、短単純な文字列として表現された部分列を読み込んだ場合には、該文字列をそのまま出力するように該第１の出力手段に指示し、部分列の登録番号と文字列の組を読み込んだ場合には、該第１の辞書に該文字列を該登録番号を付与して格納し、部分列の登録番号のみを読み込んだ場合には、該登録番号が指し示す部分列を該第１の辞書から取り出して出力するように該第１の出力手段に指示する復元制御手段とを有する２つの文字列データ復元装置からなり、入力されたコード列データを文字列データにそれぞれ復元して転送する２つの入力処理手段３１０，３２０と、
入力処理手段３１０，３２０から転送された２つの文字列データの、先頭からそれぞれ同じ位置にある文字同士の二項演算を順次計算し、その結果を新たな文字列データとして転送する演算処理手段３３０と、
圧縮前の文字列データを先頭から順次読み込む第２の入力手段と、圧縮符号化後のコード列データを先頭から順次出力する第２の出力手段と、ある有限の容量の第２の辞書と、該第２の入力手段から入力された長さ２ｎの入力文字列データをその前半部と後半部のそれぞれ半分の長さの２つの部分列に区切り、得られた該部分列の前半部と後半部に区切り、これを繰り返して、長さ１，２，４，８，１６、…２ｎの部分列に分解するために参照される分解規則と、該分解規則を参照して該第２の入力手段から入力された該入力文字列データを順次読み込みながら、該長さ１，２，４，８，１６、…２ｎの部分列を取り出して、異なる文字列毎に異なる登録番号を付与して、該第２の辞書にその容量の許す限り格納し、該第２の辞書を参照しながら、該入力文字列データを読み込むことにより、該入力文字列データの中に同一の文字列が複数回繰り返して出現したことを検出する検出手段と、該入力文字列データに同一の文字列からなる部分列が複数回繰り返して出現する場合には、１回目は文字列と該文字列の登録番号の組を出力するように該第２の出力手段に指示し、２回目以降は、該部分列を指し示す登録番号のみを出力するよう該第２の出力手段に指示する出力制御手段とを有する文字列データ圧縮符号化装置であり、演算処理手段３３０から転送された文字列データを圧縮符号化してコード列データとして出力する出力処理手段３６０とを有する。
【００２４】
本発明（請求項８）は、入力処理手段３１０、３２０と出力処理手段３６０において、部分列がそれぞれの第１の辞書または第２の辞書に格納または参照された場合に、それぞれの登録番号の情報を転送する転送手段を更に有し、
転送手段から登録番号の情報を取得して、ある２つの入力部分列の組に対する二項演算の結果がどの部分列に対応したかを、２つの入力部分列と１つの出力部分列の３つの部分列の登録番号の組として、ある有限の容量の演算高速化辞書に該容量が許す限り格納し、該演算高速化辞書を参照しながら演算処理を順次行うことにより、同一の入力部分列の組が複数回出現したことを検出する検出手段と、
同一の入力部分列の組が出現したときには、入力処理手段３１０、３２０において、部分列の登録番号を文字列データに復元する処理を省略するように制御し、出力処理手段３６０において演算高速処理辞書に格納されている演算結果の部分列の登録番号をそのまま出力するように制御する制御手段を更に有する。
【００２５】
本発明の圧縮符号化装置は、２ｎ  （但し、ｎは０以上の整数定数）個の長さの文字列データを入力とし、その情報を損なうことなしに、データを圧縮したコード列データを出力する。当該圧縮符号化装置によれば、長さ２ｎ  の入力文字列データを、その前半部と後半部のそれぞれ半分の長さの２つの部分列に区切り、得られた部分列をさらにそれぞれの前半部と後半部に区切り、これを繰り返して長さ、１，２，４，８，１６，…，２（ｎ−１）  の多数の部分列に分解するという分解規則を用いている。
【００２６】
さらに、上記の分解規則に基づいて、入力文字列データを順次読み込みながら、上記の長さ１，２，４，８，１６，…，２（ｎ−１）  の部分列を取り出して、異なる文字列毎に異なる登録番号を付与して、辞書にその容量を許す限り格納する。この辞書を参照しながら、入力文字列データを読み込むことにより、文字列データの中に同一の文字列が複数回繰り返して出現したことを検出することができる。入力文字列データに同一の文字列からなる部分列が複数回繰り返して出現する場合には、１回目は文字列とその登録番号の組を出力し、２回目以降は、当該文字列を指し示す登録番号のみを出力することにより、データを圧縮符号化する。
【００２７】
また、本発明の圧縮符号化装置において、入力文字列データの長さの制限を取り除く、すなわち、入力文字列データの長さがちょうど２ｎ  （但し、ｎはなるべく小さい整数定数）となるように、空白を表す特別な文字を文字列データの末尾に複数個追加し、これを圧縮符号化する。
また、本発明の圧縮符号化装置において、長さ１，２，４，８，１６，…，２（ｎ−１）  の部分列を、そのまま列挙して辞書に格納するのではなく、前半部と後半部の２つの部分列に分解して格納する。即ち、長さ２以上の文字列ａを、前半部と後半部のそれぞれ半分の長さの２つの部分列ａ１とａ２に分解し、ａ１とａ２の文字列がすでに辞書に格納されている場合に、２つの文字列を指し示す登録番号の組を持って文字列ａを表現し、これに文字列ａを表す新たな登録番号を与えて、辞書に格納する。これにより、長さ２以上の部分列はすべて、前半部と後半部の部分列を指し示す登録番号の組により表現される。
【００２８】
また、長さ２以上の文字列ａを出力する際に、前半部と後半部の２つの部分列ａ１、ａ２の文字列が辞書に格納されていない場合には、２つの文字列を順次出力することにより、文字列ａを表現し、そうでない場合、（すなわちａ１，ａ２の片方または両方の文字列が辞書に格納済の場合）には、格納済の文字列を出力する代わりにそれを指し示す登録番号を出力することにより、データを圧縮符号化することが可能となる。
【００２９】
また、本発明の圧縮符号化装置において、文字列データの部分列に分解して辞書に格納する処理において、辞書の容量が限界に達して、新しい文字列ｘを格納できなくなった場合に、これまでに格納された文字列の中で、他の文字列の前半部または、後半部としてまだ一度も使われていない文字列ｙを探し出して、その文字列ｙを表す情報（文字列の前半部と後半部の文字列を指し示す登録番号の組）を一旦消去し、消去した文字列ｙと同じ登録番号で指し示される記憶領域に新しい文字列ｘを表す情報を格納し、以降の処理を進める。
【００３０】
本発明の文字列データ復元装置は、データ圧縮符号化装置により圧縮符号化されたコード列データを順次読み込む際に、単純な文字列で表現された部分列を読み込んだときはその文字列をそのまま出力し、部分列の登録番号と文字列の組を読み込んだ場合には、文字列にその登録番号を付与して辞書に格納し、登録番号のみを読み込んだ場合は、その登録番号が指し示す部分列を辞書から取り出して出力することにより、文字列データを復元する。
【００３１】
さらに、本発明の文字列データ復元装置は、文字列データを前半部と後半部の２つの部分列に分解して圧縮符号化されたデータを復元する。即ち、圧縮符号化されたコード列データを順次読み込む際に、前半部と後半部の２つの部分列の組によって表現された文字列が入力された場合に、前半部と後半部の部分列の登録番号の組を持ってその文字列を表現して辞書に格納し、一方、辞書に登録された部分列を取り出して出力する際には、その前半部と後半部の部分列を辞書から順次参照し、それらの部分列がさらに前半部と後半部の組として表現されている場合には、さらに、それらを順次参照し、遂に長さ１の部分列を取り出してこれを出力することを繰り返して、部分列全体を出力する。
【００３２】
本発明の文字列データ演算処理装置は、データ圧縮符号化装置により圧縮さた状態の２本のコード列データを順次読み込み、これらの圧縮化コード列を復元したら得られるであろう２本の文字列データについて、先頭からそれぞれ同じ位置にある文字同士について、所定の二項演算を計算した結果を表す１本の文字列データを生成し、これを圧縮化方式で圧縮された状態で順次出力する。また、２つの入力処理手段において入力されたコード列データを文字列データにそれぞれ復元して演算処理手段に転送し、当該演算処理手段において、入力処理手段から転送されて来た２本の文字列データの、先頭からそれぞれ同じ位置にある文字同士の二項演算を順次計算し、その結果を新たな文字列データとして出力処理手段に転送し、当該出力処理手段において、演算処理手段から転送されてきた文字列データを圧縮符号化してコード列データとして出力する。
【００３３】
さらに、本発明の文字列データ演算処理装置に、検出手段、制御手段と、ある有限の容量の演算高速化辞書を設け、２個の入力処理手段と、出力処理手段において、部分列がそれぞれの辞書に格納されたり参照されたりしたときに、それぞれの登録番号の情報を検出手段に転送する。当該検出手段において、ある２つの入力部分列の組に対する二項演算の結果がどの部分列に対応したかを、それら３つの部分列の登録番号の組として、演算高速化辞書にその容量が許す限り格納し、この辞書を参照しながら演算を順次行うことにより、同一の入力部分列の組が複数回現れたことを検出する。制御手段において、同一の入力部分列の組が出現したときには、入力処理手段において部分列の登録番号を文字列データに復元する処理を省略し、出力処理手段において演算高速化辞書に格納されている演算結果の部分列の登録番号をそのまま出力することにより、演算処理を高速化することが可能となる。
【００３４】
上記のように、本発明では、Ｌｅｍｐｅｌ−Ｚｉｖ符号化方式のように、入力文字列データの内容によって異なる位置で部分列を切り出すのではなく、文字列データを前半部と後半部の２つの部分列に固定的に区切り、各部分列をさらに前半部と後半部の２つの部分列に区切り、これを繰り返して長さ１，２，４，８，１６，…２（ｎ−１）  の部分列に区切るという分解規則を用いている。そして、入力データを先頭から順次読み込みながら、それらの部分列を取り出して、２分決定グラフと同様のデータを先頭から順次読み込みながら、それらの部分列を取り出して、二分決定グラフと同様のデータ構造として辞書に登録する。
【００３５】
このような固定的な分解方式を採用すると、自由な区切り位置を許す場合に比べて、一致する部分列を検出する機会が減り圧縮率が低下するという可能性もある。しかしながら、上記のように区切り位置を固定することにより、文字列データの内容に関わりなく、データの先頭から２ｋ  （１＜ｋ＜ｎ）の倍数に当たる位置が常に部分列の境界となるため、複数の圧縮コード列の各々の部分列同士の対応関係が単純になる。
【００３６】
そこで、２本の圧縮コード列を入力として、それらの文字列同士の二項演算結果を新たな圧縮コード列として出力する処理において、ある２つの入力部分列の組に対する二項演算の結果が出力コード列のどの部分列に対応するかを、それらの３つの部分列の登録番号の組として、演算高速化辞書にその容量が許す限り格納し、この辞書を参照しながら演算処理を順次行うことにより、同一の入力部分列の組が複数回出現したことを検出することができる。２回目以降の出現時には、演算結果の部分列を示す辞書登録番号だけを出力することによって、同じ演算処理を繰り返す手間が省略されて高速化が可能になる。
【００３７】
本発明で用いている圧縮コード列の二項演算の高速化方式は、従来の二分決定グラフによる二項論理演算の高速化方式と同じ原理に基づく。しかしながら、本発明は、従来のように二分決定グラフの全ての節点の表が記憶装置に格納された状態で入力データとして与えられるのではなく、圧縮符号化されたコード列データを入力として順次読み込むと同時に演算結果を順次出力するという点で、従来の方法と本質的に異なる。
【００３８】
また、本発明では、文字列の圧縮及び復元の処理中に、辞書の容量が限界に達して、新しい文字列ｘを格納できなくなった場合に、これまでに格納された文字列の中で、他の文字列の前半部または、後半部としてまだ一度も使われていない文字列ｙを探し出して、その文字列ｙを表す情報（文字列と前半部と後半部の文字列を指し示す登録番号の組）を一旦消去し、消去し文字列ｙと同じ登録番号で指し示される記憶領域に新しい文字列ｘを表す情報を格納し、以降の処理を継続することが可能である。文字列ｙの情報を消去したことにより、部分列の一致を検出する機会が減少して圧縮率が低下する恐れはあるが、これにより文字列データの情報が失われたり歪んだりすることはないため、演算処理は正しく行うことが可能となる。
【００３９】
つまり、本発明では、記憶装置の容量が十分でない場合でも、その容量に応じた圧縮率及び高速化率で演算処理を行うことが可能である。これに対して従来の二分決定グラフを用いた二項論理演算方式では、記憶装置に格納された二分決定グラフの節点表が入力データとして引き渡されるため、記憶装置の容量を超える大規模データを扱うことは原理的に不可能である。
【００４０】
さらに、本発明では、圧縮符号化されたコード列データを入力として順次読み込みと同時に演算結果のコード列データを順次出力するので、処理を複数段直列に接続してパイプライン式に並列実行することができる。従来の二分決定グラフを用いた二項論理演算処理方式では、前段の処理が完了しないと次段の処理を開始できないため、パイプライン式に並列実行して高速化を図ることができないが、本発明は、この点についても従来の方法より優れていると言える。
【００４１】
【発明の実施の形態】
１．文字列データ圧縮符号化装置：
最初に文字列データ圧縮符号化装置について説明する。
図４は、本発明の文字列データ圧縮符号化装置の構成を示す。
同図に示す文字列データ圧縮符号化装置１００は、２ｎ  （但し、ｎ≧０の整数定数）個の長さの文字列データを入力とし、その情報を損なうことなしにデータを圧縮したコード列データを出力する。
【００４２】
当該文字列データ圧縮符号化装置１００は、圧縮前の文字列データを先頭から順次読み込む入力処理部１１０と、圧縮符号化後のコード列データを先頭から順次出力する出力処理部１２０と、ある有限の容量の辞書１３０、それらを制御する圧縮符号化制御部１４０及び分解規則１５０から構成される。
当該文字列データ圧縮符号化装置１００では、入力文字列データの長さは丁度２ｎ  （ｎ≧０のある整数）個であることが仮定されている。もしもそれ以外の長さの文字列データが入力された場合は、入力処理部１１０において、空白を表す特別な文字を文字列データの末尾に複数個追加し、圧縮符号化制御部１４０に送られる文字列データの長さがちょうど２ｎ  （但し、ｎはなるべく小さい整数定数）になるようにする。
【００４３】
圧縮符号化制御部１４０おいては、入力処理部１１０から転送されてくる文字列データを多数の部分列に分解し、辞書１３０に格納する。その部分列の区切り位置は文字列データの内容によらず、ある一定の分解規則１５０に基づく。即ち、長さ２ｎの入力文字列データを、その前半部と後半部のそれぞれ半分の長さの２つの部分列に区切り、得られた部分列をさらにそれぞれの前半部と後半部に区切り、それを繰り返して長さ１，２，４，８，１６、…、２ｎの多数の部分列に分解するという規則を用いている。図５は、本発明の文字列データを部分列に分解した例を示しており、同図の例では、長さ８の文字列データを部分列に分解する様子が示されている。
【００４４】
圧縮符号化制御部１４０においては、上記の分解規則５０に基づいて、入力文字列データを先頭から順次読み込みながら、上記の長さ１，２，４，８，１６，２ｎの部分列を取り出して、異なる文字列毎に異なる登録番号を付与して、辞書１３０にその容量の許す限り格納する。この辞書を参照しながら入力文字列データを読み込むことにより、文字列データの中に同一の文字列が複数回繰り返して出現したことを検出する。
【００４５】
２．文字列データ復元装置：
次に、文字列データ復元装置について説明する。
図６は、本発明の文字列データ復元装置の構成を示す。
同図に示す文字列データ復元装置２００は、文字列データ圧縮符号化装置１００により圧縮符号化されたコード列データを元の文字列に復元するものである。
【００４６】
当該文字列データ復元装置２００は、圧縮コード列データを先頭から順次読み込む入力処理部２１０と、復元文字列データを先頭から順次出力する出力処理部２２０と、文字列データを圧縮したときに用いた文字列データ圧縮符号化装置１００の辞書１３０と同等以上の容量の辞書と、それらを制御する復元制御部２４０から構成される。
【００４７】
復元制御部２４０においては、圧縮符号化されたコード列データを順次読み込む際に、単純な文字列で表現された部分列を読み込んだ場合は、その文字列を出力処理部２２０からそのまま出力し、部分列の登録番号とその文字列の組を読み込んだ場合には、その部分列を該登録番号を付与して辞書２３０に格納し、部分列の登録番号のみを読み込んだ場合には、その登録番号が指し示す部分列を辞書２３０から取り出して出力することにより文字列データを復元する。
【００４８】
さらに、復元制御部２４０においては、圧縮符号化されたコード列データを順次読み込む際に、前半部と後半部の２つの部分列の組によって表現された文字列が入力された場合に、前半部と後半部の文字列の登録番号の組を持ってその文字列を表現して辞書２３０に格納する。結果的に、前述の文字列データ圧縮符号化装置１００により圧縮符号化を行ったときに内部で作られた辞書１３０と全く同じ内容の辞書が復元される。
【００４９】
さらに、復元制御部２４０においては、辞書２３０に格納された部分列を取り出して出力する際に、その前半部と後半部の部分列を辞書２３０から順次参照し、それらの部分列からさらに前半部と後半部の組として表現されている場合には、さらに、それらを順次参照し、遂に長さ１の部分列を取り出してこれを出力することを繰り返して、部分列全体を出力する。
【００５０】
３．文字列データ演算処理装置：
次に、文字列データ演算処理装置について説明する。
図７は、本発明の文字列データ演算処理装置の構成を示す。
同図に示す文字列データ演算処理装置は、入力処理部３１０、３２０として、２つの圧縮コード列復元装置（前述の文字列データ復元装置と同様の構成）と、出力処理部３６０として、圧縮符号化装置（前述の文字列データ圧縮符号化装置と同様の構成）と、二項演算を行う演算処理部３３０と、ある有限の容量の演算高速化辞書３５０と、それらを制御する制御部３４０からなる。
【００５１】
この装置は、任意の２個の文字に対して１個の文字を計算して出力する、ある二項演算（例えば、論理積、論理和のような論理演算や加減乗除のような算術演算）が定義されているときに、前述の符号化方式で圧縮された状態の２本のコード列データを順次読み込み、それらの圧縮化コード列を復元したら得られるであろう２本の文字列データについて、先頭からそれぞれ同じ位置にある文字同士について、所定の二項演算を計算した結果を表す１本の文字列データを生成し、これを前述の符号化方式で圧縮され状態で順次出力するものである。
【００５２】
２つの入力処理部３１０、３２０においては、圧縮コード列データを先頭から順次読み込み、文字列データにそれぞれ復元して演算処理部３３０に転送し、演算処理部３３０において、入力処理部３１０、３２０から転送されてきた２本の文字列データの、先頭からそれぞれ同じ位置にある文字同士の二項演算を順次計算し、その演算結果を新たな文字列データとして出力処理部３６０に転送する。出力処理部３６において、演算処理部３３０から転送されてきた文字列データを圧縮符号化してコード列データとして出力する。
【００５３】
しかし、単に文字列データを復元して、先頭から順に演算して、再度圧縮するというだけでは、常に復元文字列データの長さに比例する計算時間が必要となり、効率的でない。そこで、本発明では、以下に説明するような演算処理高速化の手段を備えている。
２つの入力処理部３１０、３２０と出力処理部３６０においては、部分列がそれぞれの辞書に格納されたり参照されたりしたときに、それぞれの登録番号の情報を制御部３４０に定期的に報告する。
【００５４】
制御部３４０においては、ある２つの入力部分列の組に対する二項演算の結果がどの部分列に対応したかを常に監視し、それら３つの部分列の登録番号の組が得られる毎に、演算高速化辞書３５０にその容量が許す限り格納し、この演算高速化辞書３５０を参照しながら演算を順次行うことにより、同一の入力部分列の組が複数回現れたことを検出する。
【００５５】
さらに、制御部３４０においては、同一の入力部分列の組を検出したときには、２回目以降は、入力処理部３１０、３２０において部分列の登録番号を文字列データに復元する処理を省略するように制御指令を送り、出力処理部３６０において、演算高速化辞書３５０に格納されている演算結果の部分列の登録番号をそのまま出力するように制御指令を送る。
【００５６】
以上の方法により、同一の入力部分列の組が多数出現する場合には、単純に復元して演算して再圧縮する方式に比べて、全体の処理時間を短縮することができる。その高速化の割合は、同一の入力部分列の組が出現する頻度によって決まり、演算処理高速化辞書３５０の容量が十分にあるときには、入力と出力のコード列データの圧縮率にほぼ比例した高速化率が得られる。
【００５７】
【実施例】
以下、図面と共に本発明の実施例を説明する。
［第１の実施例］
第１の実施例として図４に示す文字列データ圧縮符号化装置１００に基づいて説明する。
【００５８】
図８は、本発明の第１の実施例の文字列データ圧縮符号化装置の動作を説明するための図であり、「ＡＢＡＢＡＢＡＡ」という長さの８の文字列データを入力した場合の動作の例を示す。
図９は、本発明の第１の実施例の文字列データの部分列を登録した辞書の一例を示す。以下、図８と図９の例に基づいて説明する。
【００５９】
文字列は左から１文字ずつ入力処理部１１０により読み込まれる。まず最初に「Ａ」という長さ１の文字が認識される。次に、「Ｂ」という長さ１の文字が認識される。ここで、「ＡＢ」という部分列が初めて出現するので、これを部分列１という登録番号を付与して辞書１３０に登録する。辞書には文字「Ａ」と「Ｂ」を連結した長さ２の部分文字列として格納される。
【００６０】
次に、第３文字目と第４文字目を読み込んだところで、再び「ＡＢ」という部分列を認識する。これは、すでに登録されている部分列１と同一の文字列であるので、新たに登録する必要はない。
次に、第１文字目から４文字目までの部分列「ＡＢＡＢ」を認識する。これは、新しい文字列であるから部分列２という登録番号を付与して辞書１３０に登録する。この文字列の前半部「ＡＢ」と後半部「ＡＢ」はそれぞれ部分列１と同一の文字列であるので、辞書１３０には部分列１を２つ連結した長さ４の部分列として格納する。
【００６１】
引き続いて、第５文字目と６文字目を読み込み、「ＡＢ」という部分列を認識するが、これはやはり部分列１と同一の文字列であるので、新たに登録する必要はない。
次に、第７文字目と８文字目を読み込み「ＡＡ」という部分列を認識する。これは、新しく出現した文字列であるので、部分列３という登録番号を付与して辞書１３０に登録する。辞書１３０には、文字「Ａ」を２つ連結した長さ２の部分列として格納される。
【００６２】
次に、第４文字目から８文字目までの文字列「ＡＢＡＡ」が認識される。これも初めて出現する文字列であるので、部分列４という登録番号を付与して辞書１３０に登録する。辞書１３０には部分列１と部分列３を連結した長さ４の部分列として格納される。
最後に第１文字目から８文字目までの部分列を認識し、これを部分列５という登録番号を付与して辞書１３０に登録する。辞書１３０には、部分列２と部分列４を連結した長さ８の部分列として格納される。
【００６３】
以上のようにして、入力文字データは部分列に分解されて辞書１３０に格納される。
次に、上記のように読み込まれた入力データがどのように圧縮符号化されて出力されるかを説明する。図１０は、本発明の第１の実施例の文字列データを圧縮符号化したコード列データの一例を示す。同図に示すコード列データは、図８に示す文字列データを圧縮符号化したものである。
【００６４】
圧縮符号化制御部１４０は、入力文字列データに同一の文字列からなる部分列が複数回繰り返して出現する場合には、１回目は文字列とその登録番号の情報を出力し、２回目以降は部分列を指し示す登録番号のみを出力することにより、データを圧縮符号化する。図１０では、まず、文字「Ａ」、「Ｂ」をそのまま出力し、次に、「（列１＝Ａ，Ｂ）」という符号により、「ＡＢ」が部分列１という登録番号で登録されたことを出力する。以後は、「ＡＢ」という文字列を出力する代わりに、「列１」という符号だけを出力して、データを圧縮する。
【００６５】
圧縮コード列データを出力するタイミングに関しては、入力文字列データを最後まで読み終えるのを待つことなく、新しい部分列が認識される登録される毎に、入力と同時並行的に出力が行われる。
このような圧縮符号化を行うことにより得られるコード列データの長さは、入力文字列データの中に新しく出現した部分列の個数にほぼ比例する。従って、同一の部分列が多数出現する入力文字列データを与えた場合には、非常に高い圧縮率を得ることができる。
【００６６】
辞書１３０を登録・参照するための計算時間は、ランダムアクセス可能な記憶装置を前提とすれば、ハッシュテーブルの技法により、辞書の登録データ数に依存せず、ある定数の時間で１回の登録・参照の処理を実行できる。従って、全体の計算時間は、入力文字列データの長さにほぼ比例する。
ところで、現実の装置においては、無限容量の辞書を実現することは不可能であり、ある有限の容量の辞書１３０を用いることになる。従って、大規模な文字列データを入力した場合に、辞書１３０が満杯になり、新たな部分列を格納できなくなることを考慮しなくてはならない。
【００６７】
そこで、本実施例では、辞書１３０が満杯になった場合には、これまでに格納された部分列の中で、他の部分列の前半部または後半部として使われていない部分列を探し出して、その部分列を表す情報（文字列の前半部と後半部の部分列を指し示す登録番号の組）を一旦消去し、消去した部分列と同じ登録番号で指し示される記憶領域に新しい部分列を表す情報を格納し、以降の処理を進めることとする（以後、この処理を「辞書溢れ続行処理」と呼ぶ）。
【００６８】
上記の辞書溢れ続行処理を行うことにより、過去の部分列の情報の一部が失われるため、本来は一致検出して圧縮できるはずだった部分列が検出できなくなる恐れがある。圧縮できなかった文字列は、そのまま出力されるので、圧縮率が低下することはあるが、情報が失われたり、歪んだりする心配はない。復元装置において、圧縮装置と同等以上の容量の辞書があれば、正しく元通りに復元可能であることが保証される。
【００６９】
また、現実の文字列データにおいては、距離的に近い位置にある部分列の方が複数回出現する可能性が高いと仮定すると、上記の辞書溢れ続行処理のように、使用頻度の低い部分列を消去して最新の部分列に置き換えた方が、限られた辞書容量をより有効に利用することになり、結果として圧縮率の低下を少なく抑えられると考えられる。
【００７０】
辞書溢れ続行処理を実施する際には、消去してもよい部分列を高速に発見するために、ある部分列が他の部分列から参照されている回数を数えるカウンタを、個々の部分列情報に付加し、新たに参照されたり、参照が失われたりしたときには、このカウンタの値を増減させるようにする。そして、カウンタの値が０になっている部分列を常にリストアップしておくことにより、必要なときに即座に辞書１３０を更新することができる。
【００７１】
［第２の実施例］
以下の第２の実施例は、図６に示す文字列データ復元装置２００に基づいて説明する。
当該文字列データ復元装置２００では、前述の第１の実施例における図１０に示す圧縮符号化されたコード列データが入力された場合には、図９に示す内容の辞書が復元される。
【００７２】
例えば、図９において、部分列４として辞書２３０に格納されている部分列を取り出して出力するためには、復元制御部２４０は、先ず部分列４の前半部である部分列１を参照し、さらに、部分列１の前半部を参照して「Ａ」を出力し、次に、部分列１の後半部を参照して「Ｂ」を出力し、これをもって部分列１の出力が完了する。
【００７３】
次に、部分列４に一旦戻り、その後半部である部分列３を参照し、以下同様にして「Ａ」「Ａ」を出力する。このようにして部分列４全体を出力することができる。
復元文字列データを出力するタイミングに関しては、圧縮コード列データを最後まで読み終えるのを待つことなく、入力処理部２１０または、辞書２３０から部分列を取り出す毎に、同時並行的に出力が行われる。
【００７４】
［第３の実施例］
第３の実施例として、図７に示す文字列データ演算処理装置について説明する。当該文字列データ演算処理装置は、圧縮コード列データ同士の二項演算処理を行うものであり、前述の第２の実施例の圧縮コード列復元装置２００を入力処理部３１０、３２０とし、前述の第１の実施例の文字列データ圧縮符号化装置１００を出力処理部３６０とし、入力処理部３１０、３２０から入力された２つの復元文字列データの二項演算を行う演算処理部３３０とある有限の容量の演算処理高速化辞書３５０とこれらの各構成要素を制御する制御部３４０から構成されている。
【００７５】
制御部３４０では、２つの入力処理部３１０、３２０及び出力処理部３６０から部分列がそれぞれが有する辞書（図６の辞書２３０に相当）に格納されたり、参照された場合に、それぞれの登録番号の情報を取得し、ある２つの入力部分列の組に対する演算処理部３３０における二項演算の結果がどの部分列に対応したかを監視し、当該２つの部分列とよび二項演算の結果が対応する部分列の３つの部分列の登録番号の組が得られる毎に、演算処理高速化辞書３５０に格納する。そして、この演算処理高速化辞書３５０を参照して、同一の入力部分列の組が複数回出現したことを検出する。
【００７６】
ここで、同一の入力部分列の組を検出した場合に、２回目以降は、入力処理部３１０、３２０に対して、部分列の登録番号を文字列データに復元する処理を省略するように指令を出し、出力処理部３６０では、演算処理高速化辞書３５０に格納されている演算結果の部分列の登録番号をそのまま出力するように指令を出す。これにより、同じ演算処理を繰り返すことないため、高速化が可能となる。
【００７７】
図１１は、本発明の第３の実施例の演算処理高速化辞書の例を示す。当該演算処理高速化辞書３５０には、２つの入力と１つの演算結果の合わせて３つの部分列の登録番号が１組として登録する。ランダムアクセス可能な記憶装置を前提とすれば、ハッシュテーブルの技法により、当該辞書３５０のエントリ数に依存せずに、ある定数時間で、１回の登録・参照を行うことができる。
【００７８】
現実の装置では、演算処理高速化辞書３５０の容量は有限なものであるが、当該辞書３５０が満杯になった場合には、古い情報を適宜消去して新しい情報を上書きする。これにより省略できるはずの部分列を検出する機会が失われ、演算処理速度が低下する恐れがある。しかし、その場合でも速度が低下するだけで演算結果のコード列データの内容には影響はない。
【００７９】
なお、本発明は、上記の実施例に限定されることなく、特許請求の範囲内で種々変更・応用が可能である。
【００８０】
【発明の効果】
上述のように、本発明によれば、圧縮符号化されたコード列データを必ずしも完全に復元せずに直接演算処理を行う装置を提供できる。これにより、データの圧縮率にほぼ比例して、処理の高速化が可能となる。
また、本発明によれば、すべての入力データを前もって記憶装置内に格納可能でない場合でも、入力された圧縮コード列データの先頭から順次、演算処理を実行し、演算結果を順次出力することが可能である。これにより、従来手法では扱えなかった大規模なデータの演算処理が行えるようになる。
【００８１】
さらに、本発明によれば、複数個の演算処理装置を直列に接続することにより、パイプライン式に並行実行して高速化を図ることができる。
【図面の簡単な説明】
【図１】本発明の原理構成図（文字列データ圧縮符号化装置）である。
【図２】本発明の原理構成図（文字列データ復元装置）である。
【図３】本発明の原理構成図（文字列データ演算処理装置）である。
【図４】本発明の文字列データ圧縮符号化装置の構成図である。
【図５】本発明の部分列の分解規則を説明するための図である。
【図６】本発明の文字列データ復元装置の構成図である。
【図７】本発明の文字列データ演算処理装置の構成図である。
【図８】本発明の第１の実施例の文字列データ圧縮符号化装置の動作を説明するための図である。
【図９】本発明の第１の実施例の文字列データの部分列を登録した辞書の一例である。
【図１０】本発明の第１の実施例の文字列データを圧縮符号化したコード列データの一例である。
【図１１】本発明の第３の実施例の演算処理高速化辞書の例である。
【図１２】Ｘ１  ，Ｘ２  ，Ｘ３  の３変数を入力とする論理関数データを表現する真理値表の一例である。
【図１３】論理関数データに対して入力変数に０，１を代入することにより展開して得られる二分木状のグラフの一例である。
【図１４】二分決定グラフの共有化処理を説明するための図である。
【図１５】二分決定グラフの非冗長化処理を説明するための図である。
【図１６】論理関数データを表現する二分決定グラフの一例である。
【図１７】二分決定グラフを記憶装置に格納するためにグラフの節点を列挙した表の一例である。
【符号の説明】
１００  文字列データ圧縮符号化装置
１１０  入力処理手段、入力処理部
１２０  出力処理手段、出力処理部
１３０  辞書
１４０  圧縮符号化制御部
１４１  検出手段
１４２  出力制御手段
１５０  分解規則
２００  文字列データ復元装置
２１０  入力処理手段、入力処理部
２２０  出力処理手段、出力処理部
２３０  辞書
２４０  復元制御手段、復元制御部
３００  文字列データ演算処理装置
３１０、３２０  入力処理手段
３３０  演算処理手段
３４０  制御部
３５０  演算処理高速化辞書
３６０  出力処理手段
【図１】
0003555506.tif 000002
【図２】
0003555506.tif 000003
【図３】
0003555506.tif 000004
【図４】
0003555506.tif 000005
【図５】
0003555506.tif 000006
【図６】
0003555506.tif 000007
【図７】
0003555506.tif 000008
【図８】
0003555506.tif 000009
【図９】
0003555506.tif 000010
【図１０】
0003555506.tif 000011
【図１１】
0003555506.tif 000012
【図１２】
0003555506.tif 000013
【図１３】
0003555506.tif 000014
【図１４】
0003555506.tif 000015
【図１５】
0003555506.tif 000016
【図１６】
0003555506.tif 000017
【図１７】
0003555506.tif 000018