JP2006295853A - 符号化装置、復号装置、および、符号化方法ならびに復号方法 - Google Patents

Abstract

【課題】 符号化における一致長とその一致長符号との関係を動的に変化させて、一致長符号により表現可能な長さを自立的に切り替える。
【解決手段】 データバッファ１１０におけるスライド窓を辞書として、文字列検索部１３０は入力データの部分文字列と一致する文字列を検索する。内部状態保持部１４０に保持された内部状態に対応して、一致長拡張テーブル１５０は一致長とその一致長符号との関係を保持している。一致長符号化部１６０は内部状態に基づいて一致長拡張テーブル１５０を参照して、一致長とその一致長符号との対応付けを動的に決定する。文字列符号化部１７０はスライド窓における相対位置と一致長符号により符号列を生成する。
【選択図】 図１

Description

本発明は、ＬＺＳＳ（Lempel-Ziv-Storer-Szymanski）符号に基づく符号化装置ならびに復号装置に関し、特に符号化における一致長とその符号との関係を動的に変化させる符号化装置、復号装置、および、これらにおける処理方法ならびに当該方法をコンピュータに実行させるプログラムに関する。

ＬＺＳＳ符号は、辞書に基づいた符号化による符号の一つであり、可逆なデータ圧縮を提供するものである（例えば、非特許文献１参照。）。このＬＺＳＳ符号による符号化では、符号化対象の入力データを固定長Ｍビットの記号（例えば、文字。以下では、文字として統一的に説明する。）として区切り、その文字を最小単位として扱う。データは１つの長い文字列であり、文字列中の一部の連続して並んだ文字を部分文字列として扱う。データ全体を複数の部分文字列へと分解し、部分文字列毎に符号ＣＯＤＥを割り当てる。各部分文字列に割り当てられる符号ＣＯＤＥには２種類あり、符号化済みデータＱｅｎｃにおいて一致する部分文字列を参照する符号ＰＴＲと文字そのものを対応させた符号ＲＡＷとがある。そして、ＰＴＲまたはＲＡＷのどちらの符号であるかを示す１ビットの符号ＦＬＧが設けられる。符号ＦＬＧと符号ＣＯＤＥとが対になって１つの部分文字列の符号となる。

入力データの最初の文字から順番に各部分文字列の長さを確定していくことで各部分文字列の分解が徐々に進行する。分解された部分文字列は互いに重なる部分はなく、１つの部分文字列が分解されたとき、その部分文字列の末尾文字の直後に位置する文字が次の部分文字列の先頭文字となるように分解される。分解された部分文字列は次々と符号化される。分解される前には部分文字列の先頭文字Ｈのみが確定しており長さは未定であるが、次のような手順で分解されて長さが決定される。

まず、分解対象の部分文字列ｓの先頭文字Ｈと一致する文字を符号化済みのデータＱｅｎｃから探索する。この符号化済みデータＱｅｎｃは入力データの最初の文字から分解済み部分文字列の末尾文字までの入力データに等しい文字列である。符号化済みデータＱｅｎｃには予め決められた範囲Ｑｅｗｉｎが設定されており、分解対象の部分文字列ｓからの相対的な位置により範囲が決まる。符号化済みデータＱｅｎｃは範囲Ｑｅｗｉｎ内にある文字のみが参照できるようになっている。この範囲Ｑｅｗｉｎは、スライド窓もしくはスライド辞書などと呼称される。

符号化済みデータＱｅｎｃの範囲Ｑｅｗｉｎを検索して先頭文字Ｈと一致する文字が１つ以上発見されたとき、その各文字を先頭文字とした部分文字列のすべてを比較対象として、分解対象の部分文字列ｓの長さを徐々に増やしては比較して一致するものがあるか探索する。そして、一致する最長の部分文字列が最長一致文字列ｍｓｔｒとなり、その長さが最長一致長ｍｌｅｎとなる。範囲Ｑｅｗｉｎは、分解対象の部分文字列ｓの先頭文字Ｈからの相対的な位置により特定される。この位置がＮＰビットで表されるとすると、範囲Ｑｅｗｉｎは最大で「２のＮＰ乗」個の文字を格納できる。この範囲Ｑｅｗｉｎに格納可能な文字の上限値を以下ではＮで表す。

ＬＺＳＳ符号の符号化の際は、最長一致長ｍｌｅｎと、ある閾値ＰＴＨとが比較されて、以下の要領で実現される。まず、「最長一致長ｍｌｅｎが閾値ＰＴＨより大きいとき」には、その最長一致長ｍｌｅｎが一致長符号で表現できる最大の長さｌｍａｘ以下なら、一致長ｌｅｎにｍｌｅｎを設定する。一方、その最長一致長ｍｌｅｎがｌｍａｘより大きければ、一致長ｌｅｎにはｌｍａｘを設定する。このようにして一致長ｌｅｎが設定されると、Ｈを先頭として一致長ｌｅｎの部分文字列ｓが分解されて、ｍｓｔｒの先頭文字ｍＨの位置ｍｐｏｓを示す番号をＮＰビットで表した符号ｐと、一致長ｌｅｎをＮＣビットで表した符号ｃとを合わせた（ＮＰ＋ＮＣ）ビットが符号ＰＴＲとなる。このとき、符号ＦＬＧは「０」を示す。

例えば、閾値ＰＴＨを「２」とすると、図４３（ａ）のように、３文字の部分文字列「ｆｇｈ」がデータバッファ１１０内のスライド窓１１１に存在することが探索された場合、一致長は「３」となる。また、この例ではスライド窓１１１における先頭文字「ｆ」の相対位置が「４」であることから、符号ＰＴＲは、（４，３）となる。また、符号ＦＬＧは「０」となる。

これに対し、「最長一致長ｍｌｅｎが閾値ＰＴＨ以下のとき」または「符号化済みデータに一致するものがないとき」には、部分文字列として先頭文字Ｈのみが分解され、先頭文字ＨがそのままＭビットの符号ＲＡＷとなる。このとき、符号ＦＬＧは「１」を示す。

例えば、図４３（ｂ）のように、先頭文字「ｋ」に一致する文字がスライド窓１１１に存在しない場合、その先頭文字「ｋ」そのものが符号ＲＡＷとなる。また、符号ＦＬＧは「１」となる。

一方、ＬＺＳＳ符号の復号は、符号化時に生成された順番に入力符号の最初から最後まで符号に対応した全ての部分文字列を復号する。復号された部分文字列は復号済みデータＱｄｅｃとしてＱｄｅｃの末尾に連結されて、元のデータが１つの長い文字列として徐々に復号されていく。復号済みデータＱｄｅｃは、符号化のときの符号化済みデータＱｅｎｃと同様に、復号時に復号対象の部分文字列ｓからの相対的な位置を示す番号で参照される。入力符号の各符号ＦＬＧが「０」か「１」かによって、それぞれに対応した符号ＣＯＤＥがＰＴＲかＲＡＷのどちらの符号であるかを判断する。符号ＲＡＷであるとき、符号ＣＯＤＥを１文字の部分文字列として復号済みデータＱｄｅｃに連結される。符号ＰＴＲであるとき、符号ｐから一致部分文字列の先頭文字位置が復号され、符号ｃから一致長が復号されることにより、復号済みデータＱｄｅｃ内から部分文字列が特定される。そして、その部分文字列が先頭文字から一文字ずつ複製され、復号済みデータＱｄｅｃに連結されて、符号ＣＯＤＥに対応した部分文字列が復号される。先頭から１文字ずつ複製して連結されることによって、一致文字列と復号対象の文字列に重なる部分があっても正しく復号される。一致長符号ｃはＮＣビットで表されるため、対応する一致長は（ＰＴＨ＋１）から（（２のＮＣ乗）＋ＰＴＨ）の値となる。
植松友彦著，「文書データ圧縮アルゴリズム入門」，ＣＱ出版株式会社，１９９４年１０月１５日，ｐ．１３１−１４８

このように、ＬＺＳＳ符号の符号ＰＴＲは、データバッファ上の位置ｍｐｏｓを示す番号と一致部分文字列の長さｌｅｎに対応した符号からなる。長さｌｅｎを固定ビット長ＮＣの符号に１対１で対応させることを考えると、ＮＣが短いビット長であれば限られた少ない長さしか割り当てることができないが、ＮＣが長いビット長であればそれだけ多くの長さを対応させることができる。その一方で、同じ情報を表すならば、なるべくビット長が短い方が圧縮の効果が高い。

符号化済みデータの検索範囲Ｑｅｗｉｎは、８０００文字くらいが良いと一般的にいわれている（例えば、上述の非特許文献１参照。）。この検索範囲Ｑｅｗｉｎによって、位置ｍｐｏｓのビット数ＮＰが決定される。例えばこの範囲Ｑｅｗｉｎを４０９２文字とすれば、１２ビットでちょうど表現できる。しかし、１０００文字などの長い一致長に分解される部分文字列は頻出するわけではなく、むしろ短い部分文字列に分解される頻度の方が高い。それゆえ、位置ｍｐｏｓと比べて長さｌｅｎのビット数は少なく設定されることが多く、検索範囲Ｑｅｗｉｎが４０９２文字のときに仮に１０００文字の部分文字列を見つけることができたとしても、長さｌｅｎのビット数から制限された一致長の最大値の長さの部分文字列までしか分解できない。例えば、一致長符号が４ビットで、閾値ＰＴＨを２とすると、この一致長符号で表現できるのは「３」乃至「１８」の１６通りの長さとなる。したがって、最大一致長が１０００文字であっても、結局、１８文字ごとに分解して符号化することになる。

このような無駄を避けるための方法として、１６通りのうちの１つの一致長符号に長さを拡張することを示すエスケープコードを割り当てて、エスケープコードを復号したときはさらに別の固定長ビットを読むようにして、段階的にビット長を増やす可変ビット長の符号を使うことも考えられる。しかし、それでも１０００文字のような長い文字まで拡張するには、数個のエスケープコードで数段階の拡張をした符号になるため、やはりあまり短い符号を割り当てることができず、しかも処理が複雑になるという問題もある。

そこで、本発明は、符号化における一致長とその符号との関係を動的に変化させて、一致長符号により表現可能な長さを自立的に切り替えることを目的とする。

本発明は、上記課題を解決するためになされたものであり、その第１の側面は、入力データを保持するデータバッファの所定の検索範囲において上記入力データの符号化対象の部分記号列との一致を検索する検索手段と、所定の内部状態を保持する内部状態保持手段と、上記内部状態保持手段に保持された内部状態に従って上記検索手段において一致が検索された上記部分記号列の一致長に一致長符号を割り当てた後で当該一致長に応じて上記内部状態保持手段に保持された内部状態を更新する一致長符号化手段と、上記検索部において一致が検索された上記部分記号列の位置と上記一致長符号化手段によって割り当てられた上記一致長符号とに基づいて上記部分記号列を符号化する記号列符号化手段とを具備することを特徴とする符号化装置である。これにより、内部状態に従って割り当てられた一致長符号に基づいて部分記号列が符号化されるという作用をもたらす。

また、この第１の側面において、上記一致長符号化手段は、上記一致長符号が所定の閾値に満たない場合には上記内部状態保持手段に保持された内部状態を最も低い段階にリセットし、上記一致長符号がその最大値を示している場合には上記内部状態保持手段に保持された内部状態をより高い段階に遷移させ、上記一致長符号が上記閾値を満たしながら上記最大値に満たない場合には上記内部状態保持手段に保持された内部状態をより低い段階に遷移させるという内部状態の状態遷移を制御することができる。これにより、部分記号列の一致の状況に応じて内部状態を遷移させるという作用をもたらす。

また、この第１の側面において、上記一致長符号化手段は、上記一致長符号が所定の閾値に満たない場合には上記内部状態保持手段に保持された内部状態に依らず上記一致長ごとに定められた符号を上記一致長符号として割り当て、上記一致長符号が上記閾値を満たす場合には上記内部状態および上記一致長によって定められる符号を上記一致長符号として割り当てることができる。これにより、一致長符号と閾値との関係に応じて、一致長符号の決定の際に内部状態を考慮するか否かを決定させるという作用をもたらす。

また、この第１の側面において、上記内部状態保持手段に保持された上記内部状態に対応して上記一致長符号に割り当てるべき一致長をそれぞれ定める一致長拡張手段をさらに具備し、上記一致長符号化手段が、上記一致長符号が所定の閾値に満たない場合には上記内部状態保持手段に保持された内部状態に依らず上記一致長ごとに定められた符号を上記一致長符号として割り当て、上記一致長符号が上記閾値を満たす場合には上記一致長拡張手段に定められた符号を上記一致長符号として割り当てるようにすることができる。これにより、一致長符号に割り当てるべき一致長を内部状態に対応して定める一致長拡張手段を設け、一致長符号と閾値との関係に応じてこの一致長拡張手段を参照という作用をもたらす。

また、本発明の第２の側面は、符号列から復号された部分記号列を保持する復号バッファと、上記符号列を保持する符号バッファから上記部分記号列の位置と一致長符号とを含む部分記号列符号を取得する符号取得手段と、所定の内部状態を保持する内部状態保持手段と、上記内部状態保持手段に保持された内部状態に従って上記一致長符号に対応する部分記号列の長さを一致長として復号した後で当該一致長に応じて上記内部状態保持手段に保持された内部状態を更新する一致長復号手段と、上記部分記号列の位置および上記一致長に基づいて上記復号バッファを参照して上記部分記号列符号に対応する部分記号列を復号する記号列復号手段とを具備することを特徴とする復号装置である。これにより、内部状態に従って割り当てられた一致長符号に基づいて部分記号列が復号されるという作用をもたらす。

また、この第２の側面において、上記一致長復号手段は、上記一致長符号が所定の閾値に満たない場合には上記内部状態保持手段に保持された内部状態を最も低い段階にリセットし、上記一致長符号がその最大値を示している場合には上記内部状態保持手段に保持された内部状態をより高い段階に遷移させ、上記一致長符号が上記閾値を満たしながら上記最大値に満たない場合には上記内部状態保持手段に保持された内部状態をより低い段階に遷移させるという内部状態の状態遷移を制御することができる。これにより、部分記号列の一致の状況に応じて内部状態を遷移させるという作用をもたらす。

また、この第２の側面において、上記一致長復号手段は、上記一致長符号が所定の閾値に満たない場合には上記内部状態保持手段に保持された内部状態に依らず上記一致長符号ごとに定められた部分記号列の長さを一致長として復号し、上記一致長符号が上記閾値を満たす場合には上記内部状態および上記一致長符号によって定められる部分記号列の長さを一致長として復号することができる。これにより、一致長符号と閾値との関係に応じて、一致長符号の決定の際に内部状態を考慮するか否かを決定させるという作用をもたらす。

また、この第２の側面において、上記内部状態保持手段に保持された上記内部状態に対応して上記一致長符号に割り当てるべき一致長をそれぞれ定める一致長拡張手段をさらに具備し、上記一致長復号手段は、上記一致長符号が所定の閾値に満たない場合には上記内部状態保持手段に保持された内部状態に依らず上記一致長符号ごとに定められた部分記号列の長さを一致長として復号し、上記一致長符号が上記閾値を満たす場合には上記一致長拡張手段に定められた値を一致長として復号することができる。これにより、一致長符号に割り当てるべき一致長を内部状態に対応して定める一致長拡張手段を設け、一致長符号と閾値との関係に応じてこの一致長拡張手段を参照という作用をもたらす。

また、この第２の側面において、上記符号バッファに上記符号列を所定のブロックを単位として供給するよう制御する符号バッファ制御手段をさらに具備し、上記一致長復号手段が、上記ブロックを復号するたびに次に行うべき処理を記憶しておいて、前回記憶しておいた上記次に行うべき処理に従って次のブロックを復号するよう制御してもよい。これにより、小容量の符号バッファでも符号列をブロック毎に区切りながら復号させるという作用をもたらす。

また、本発明の第３の側面は、圧縮プログラムから伸張された部分記号列を保持する伸張プログラムバッファと、上記圧縮プログラムを保持する圧縮プログラムバッファから上記部分記号列の位置と一致長符号とを含む部分記号列符号を取得する符号取得手段と、所定の内部状態を保持する内部状態保持手段と、上記内部状態保持手段に保持された内部状態に従って上記一致長符号に対応する部分記号列の長さを一致長として復号した後で当該一致長に応じて上記内部状態保持手段に保持された内部状態を更新する一致長復号手段と、上記部分記号列の位置および上記一致長に基づいて上記伸張プログラムバッファを参照して上記部分記号列符号に対応する部分記号列を復号する記号列復号手段とを具備することを特徴とする圧縮プログラムの伸張装置である。これにより、内部状態に従って割り当てられた一致長符号に基づいて圧縮プログラム中の部分記号列が復号されるという作用をもたらす。

また、本発明の第４の側面は、入力データを保持するデータバッファの所定の検索範囲において上記入力データの符号化対象の部分記号列との一致を検索する手順と、所定の内部状態に従って上記一致が検索された上記部分記号列の一致長に一致長符号を割り当てる手順と、当該一致長に応じて上記内部状態を更新する手順と、上記部分記号列の上記データバッファにおける相対アドレスと上記一致長符号とに基づいて上記部分記号列を符号化する手順とを具備することを特徴とする符号化方法またはこれら手順をコンピュータに実行させるプログラムである。これにより、内部状態に従って割り当てられた一致長符号に基づいて部分記号列が符号化されるという作用をもたらす。

また、本発明の第５の側面は、符号バッファに保持された符号列を復号して、復号された部分記号列を復号バッファに保持させる復号方法において、上記符号バッファから上記部分記号列における相対アドレスと一致長符号とを含む部分記号列符号を取得する手順と、所定の内部状態に従って上記一致長符号に対応する部分記号列の長さを一致長として復号する手順と、上記復号された一致長に応じて上記内部状態を更新する手順と、上記部分記号列における相対アドレスおよび上記一致長に基づいて上記復号バッファを参照して上記部分記号列符号に対応する部分記号列を復号する手順とを具備することを特徴とする復号方法。またはこれら手順をコンピュータに実行させるプログラムである。これにより、内部状態に従って割り当てられた一致長符号に基づいて部分記号列が復号されるという作用をもたらす。

本発明によれば、符号化における一致長とその符号との関係を動的に変化させて、一致長符号により表現可能な長さを自立的に切り替えるという優れた効果を奏し得る。

次に本発明の実施の形態について図面を参照して詳細に説明する。

図１は、本発明の実施の形態における符号化装置１００の一構成例を示す図である。この符号化装置１００は、データバッファ１１０と、データバッファ制御部１２０と、文字列検索部１３０と、内部状態保持部１４０と、一致長拡張テーブル１５０と、一致長符号化部１６０と、文字列符号化部１７０とを備えている。

データバッファ１１０は、符号化対象である入力データを適宜保持するバッファである。このデータバッファ１１０に保持された入力データは、符号化された後もすぐには消去されず、検索のために符号化済みデータとして一時的に保持され続ける。この符号化済みデータの検索範囲は、スライド窓またはスライド辞書等と呼ばれる。

データバッファ制御部１２０は、符号化の進行状況に応じてデータバッファ１１０に関する制御を行うものである。具体的には、データバッファ制御部１２０は、データバッファ１１０に対する入力データの入力処理や符号化済みデータの出力処理、および、スライド窓の管理等を行う。

文字列検索部１３０は、データバッファ１１０におけるスライド窓の直後に位置する部分文字列について、その部分文字列と一致する文字列をスライド窓において検索するものである。この文字列検索部１３０によって一致する所定の長さ以上の文字列が検索された場合には、その文字列のスライド窓における位置およびその一致長が生成される。一方、部分文字列の先頭文字に一致する文字が検索されなかった場合や、検索された文字列が所定の長さに満たない場合には、スライド窓の直後に位置する先頭文字がそのまま供給される。

内部状態保持部１４０は、本発明の実施の形態における内部状態を保持するものである。この内部状態は、後述のように符号化の進行状況に応じて状態遷移するものであり、所定条件下において一致長とその符号との間の関係を定める一因となるものである。

一致長拡張テーブル１５０は、一致長とその符号との間の関係を、内部状態保持部１４０に保持された内部状態に応じて定めるものである。

一致長符号化部１６０は、文字列検索部１３０において生成された一致長に一致長符号を割り当てるものである。すなわち、一致長符号化部１６０は、一致長拡張テーブル１５０を参照して、内部状態保持部１４０に保持された内部状態に対応した一致長符号を割り当てる。但し、一致長符号が一定の閾値に満たない場合には、内部状態保持部１４０に保持された内部状態に依らずに、一致長に対応する一致長符号が割り当てられる。

文字列符号化部１７０は、部分文字列を符号化するものであり、文字列検索部１３０によって一致する所定の長さ以上の文字列が検索された場合には、その文字列のスライド窓における位置および一致長符号化部１６０に割り当てられた一致長符号をその文字列の符号として供給する。一方、部分文字列の先頭文字に一致する文字が検索されなかった場合や、検索された文字列が所定の長さに満たない場合には、スライド窓の直後に位置する先頭文字がその文字の符号としてそのまま供給される。

図２は、本発明の実施の形態における符号のデータ構造を示す図である。図２（ａ）のように、符号ＣＯＤＥには符号ＰＴＲおよび符号ＲＡＷの２種類の形式が存在する。符号ＰＴＲは、スライド窓において一致する文字列の先頭文字の位置ｐとその一致長符号ｃから成る。また、符号ＲＡＷは文字データそのものを示す。

符号ＦＬＧは、符号ＣＯＤＥが何れの形式であるかを示すものであり、ここでは符号ＦＬＧが"０"の場合に符号ＣＯＤＥが符号ＰＴＲであることを示し、符号ＦＬＧが"１"の場合に符号ＣＯＤＥが符号ＲＡＷであることを示している。

符号ＦＬＧのビット幅が１ビットで、符号ＣＯＤＥのビット幅が１６ビットであると想定すると、これら符号ＦＬＧおよび符号ＣＯＤＥのメモリ上の配置は図２（ｂ）のようにすることが考えられる。すなわち、１６個の符号ＣＯＤＥ＃０乃至１５のそれぞれに対応する１６個の符号ＦＬＧ＃０乃至１５をまとめて配置することにより、メモリの断片化を回避している。なお、この配置は一例に過ぎず、対応する符号ＦＬＧと符号ＣＯＤＥを隣合せに配置してもよく、また、例えば３２個以上の符号ＦＬＧをまとめて配置するようにしてもよい。

図３は、本発明の実施の形態における内部状態の状態遷移の一例を示す図である。内部状態ｓｔａｔｅは、０からＳＭＡＸの「ＳＭＡＸ＋１」個の状態をとり得る。内部状態ｓｔａｔｅは、符号化における一致長符号ｃに応じて状態が遷移する。

現在の内部状態ｓｔａｔｅをｓｔとすると、１つ前の部分文字列の一致長符号ｃによって、内部状態ｓｔａｔｅを０、ｓｔ−１、ｓｔ＋１、または、ＳＭＡＸの何れかへと遷移させる。内部状態ｓｔａｔｅが大きくなるにつれ、一致長符号ｃにはより長い一致長が割り当てられていることを意味する。

一致長符号ｃは、０からＣＭＡＸの「ＣＭＡＸ＋１」個の値をとり得る。ここで、一致長符号ｃにおいて、０≦ＣＴＨ＜ＣＭＡＸを満たす閾値ＣＴＨを想定する。一致長符号ｃに対応する一致長は、０≦ｃ≦ＣＴＨの場合は内部状態に依存しないＬ（ｃ）により表される。これは、ＬＺＳＳ符号と同様の割当て方法である。一方、ＣＴＨ＜ｃ≦ＣＭＡＸの場合はそのときの内部状態に依存するＬ（ｃ）［ｓｔ］により表される。これは、実際に一致した長さが長い部分文字列の後には短い文字列を符号化することが多いことや、単純なデータでない限り短い文字列の頻度が多いと予想されることによるものである。

内部状態ｓｔａｔｅの初期状態は０であり、このとき一致長符号ｃはＬＺＳＳ符号のように短い長さが割り当てられている。部分文字列が１つ符号化されたときの一致長が状態ｓｔにおける最大値のＬ（ＣＭＡＸ）［ｓｔ］を示している場合、実際に一致した長さ（最長一致長ｍｌｅｎ）より短い一致長に符号化されていると考えられる。そこで、この場合、Ｌ（ＣＭＡＸ）［ｓｔ］を長くして次の処理でより長い一致長に対応できるように、内部状態ｓｔａｔｅを１つ大きい状態へ遷移させる。

また、一致長がＬ（ＣＭＡＸ）［ｓｔ］より短く、Ｌ（ＣＴＨ）［ｓｔ］以上であれば、緩やかにＬ（ＣＭＡＸ）［ｓｔ］を短くしていくように内部状態ｓｔａｔｅを１つ小さい状態へと遷移させる。

さらに、一致長がＬ（ＣＴＨ）［ｓｔ］より短いときは、長い部分文字列の頻度が少ないと考えられるため、直ちに初期状態の割り当てに戻すために内部状態ｓｔａｔｅを０へと遷移させる。また、ＲＡＷ符号のとき一致長は０と解釈し、このときも直ちに内部状態ｓｔａｔｅを０へと遷移させる。

なお、以下の本発明の実施の形態においては、一致長符号ｃのビット幅ＮＣを４ビット、位置ｐのビット幅ＮＰを１２ビット、一致長符号ｃの閾値ＣＴＨを１３、一致長符号ｃの最大値ＣＭＡＸを１５、内部状態ｓｔａｔｅの最大値ＳＭＡＸを３と想定して説明する。

図４は、本発明の実施の形態における一致長符号ｃと一致長ｌｅｎとの関係の一例を示す図である。図４（ａ）に示すように、一致長符号ｃが０から１３（ＣＴＨ）の場合には内部状態に依存しない一定値（ｃ＋ＰＴＨ＋１）が割り当てられ、一致長符号ｃがＣＴＨを超える１４および１５の場合には内部状態に依存した値が割り当てられている。ここで、ＰＴＨは一致長が短すぎる場合には一致長符号を割り当てないようにするために設けられた閾値であり、ここではＰＴＨ＝２としている。従って、ここでは一致長が２以下の場合には、一致長符号が割り当てられず、符号ＲＡＷに文字そのものが割り当てられることになる。

図４（ｂ）は、内部状態ｓｔａｔｅに対応して一致長ｌｅｎを決定するためのＬ（ｃ）［ｓｔａｔｅ］の値を定めるテーブルであり、図１における一致長拡張テーブル１５０に相当する。このテーブルにおける値は、任意のｘおよびｙについて以下の条件を満たせばよい。すなわち、「ｘ＞ＣＴＨ」においてＬ（ｘ）［ｙ］は、「Ｌ（ＣＴＨ）＜Ｌ（ｘ）［ｙ］、かつ、Ｌ（ｘ）［ｙ］＜Ｌ（ｘ＋１）［ｙ］、かつ、Ｌ（ｘ）［ｙ］＜Ｌ（ｘ）［ｙ＋１］」の条件を満たす整数であればよい。つまり、ｘまたはｙが増加するとＬ（ｘ）［ｙ］が長くなるように値が決められている必要がある。この図４の例では、内部状態が３の場合には、一致長符号ｃ＝１５に対して最大で「１７９２」の一致長が割り当てられることになる。

図５は、本発明の実施の形態における復号装置２００の一構成例を示す図である。この復号装置２００は、符号バッファ２１０と、符号バッファ制御部２２０と、符号取得部２３０と、内部状態保持部２４０と、一致長拡張テーブル２５０と、一致長復号部２６０と、文字列復号部２７０と、復号バッファ２８０とを備える。

符号バッファ２１０は、復号対象である符号列を適宜保持するバッファである。この符号バッファ２１０に対して符号列を保持させるには、符号列全体を一括して保持させる方法と、所定のブロックに分割して保持させる方法とが考えられる。

符号バッファ制御部２２０は、復号の進行状況に応じて符号バッファ２１０に関する制御を行うものである。具体的には、符号バッファ制御部２２０は、符号列を一括して、もしくは分割して保持させる制御を行う。

符号取得部２３０は、符号バッファ２１０から所望の符号を取得して、符号ＦＬＧに応じて符号ＣＯＤＥを解釈するものである。すなわち、符号ＦＬＧが"０"を示す場合には符号ＰＴＲから位置ｐおよび一致長符号ｃを抽出し、符号ＦＬＧが"１"を示す場合には符号ＲＡＷから文字データを抽出する。

内部状態保持部２４０は、本発明の実施の形態における内部状態を保持するものであり、図１により説明した符号化装置１００の内部状態保持部１４０と同様の働きを行う。また、一致長拡張テーブル２５０は、一致長とその符号との間の関係を、内部状態保持部１４０に保持された内部状態に応じて定めるものであり、図１により説明した符号化装置１００の一致長拡張テーブル１５０と同様の働きを行う。

一致長復号部２６０は、符号取得部２３０において抽出された一致長符号からその一致長符号に対応する一致長を決定するものである。すなわち、一致長復号部２６０は、一致長拡張テーブル２５０を参照して、内部状態保持部２４０に保持された内部状態に対応した一致長に復号する。但し、一致長符号が一定の閾値に満たない場合には、内部状態保持部２４０に保持された内部状態に依らずに、一致長符号に対応する一致長に復号する。

文字列復号部２７０は、文字または文字列を復号して、復号された文字または文字列を復号バッファ２８０に保持させるものである。すなわち、符号ＰＴＲであれば符号取得部２３０から供給された位置および一致長復号部２６０から供給された一致長に基づいて復号バッファ２８０を参照して文字列を復号する。また、符号ＲＡＷであればその文字データにより文字を復号する。

復号バッファ２８０は、文字列復号部２７０によって復号された文字または文字列を保持するものである。この復号バッファ２８０に保持された文字列は、復号データとして出力されるとともに、文字列復号部２７０における復号に用いられる。

次に本発明の実施の形態における符号化装置１００および復号装置２００の動作について図面を参照して説明する。

図６は、以下の説明で用いられる本発明の実施の形態におけるデータバッファ１１０とスライド窓１１１との関係を示す図である。図６（ａ）に示すように、この例では、データバッファ１１０として「２Ｎ＋ＦＭＡＸ＋１」個の文字を格納する容量を有するものと想定する。ここで、Ｎはスライド窓１１１の最大容量であり、ＦＭＡＸは一致長の最大値（Ｌ（ＣＭＡＸ）［ＳＭＡＸ］）である。

図６（ｂ）に示すように、スライド窓１１１は最初にデータバッファ１１０の先頭に配置される。このスライド窓１１１は、データバッファ１１０の有効領域の開始アドレスｂｓｔａｒｔから「ｒ−１」の範囲として位置付けられる。ここで、変数ｒはスライド窓１１１の直後の先頭文字の位置である。

符号化処理が進むに従って、スライド窓１１１は右方向に移動していく。そして、図６（ｃ）に示すように変数ｒが２Ｎ以上になると、スライド窓１１１は左方向にＮ個戻されて、図６（ｄ）に示すように位置付けられる。以下、このような動作を前提として符号化について説明する。

図７は、本発明の実施の形態における符号化処理のメインフローを示す流れ図である。まず、符号化処理に用いられる変数が初期化され（ステップＳ７１０）、データバッファ１１０が初期化される（ステップＳ７２０）。そして、変数ｒがデータバッファ１１０の有効領域の終了アドレスｂｅｎｄよりも小さいことを条件として、以下の処理が繰り返される。

変数ｒにおける先頭文字を基準として、スライド窓１１１において一致する文字列が検索される（ステップＳ７３０）。これにより、実際に一致した長さ（最長一致長ｍｌｅｎ）が閾値ＰＴＨより長ければ符号ＰＴＲに符号化され（ステップＳ７５０）、閾値ＰＴＨ以下であれば符号ＲＡＷに符号化される（ステップＳ７６０）。符号ＲＡＷの符号化の場合には、これに先立って変数ｆｌｇＭの下位から変数ｆｌａｇ＿ｃｏｕｎｔビット目に"１"が設定される（ステップＳ７０２）。この変数ｆｌｇＭは、Ｍ個の符号ＦＬＧをＬＳＢ（Least Significant Bit）から順番に一つにまとめたＭビットのデータである。また、変数ｆｌａｇ＿ｃｏｕｎｔは、符号ＦＬＧの個数を計数するカウンタである。

変数ｆｌａｇ＿ｃｏｕｎｔが「Ｍ−１」になると（ステップＳ７０３）、変数ｆｌｇＭにＭ個の符号ＦＬＧを設定し終わったことになるため、Ｍ個の符号ＦＬＧおよび符号ＣＯＤＥを出力する（ステップＳ７７０）。その後、次の処理のために変数ｆｌｇＭはリセットされる（ステップＳ７０４）。

そして、変数ｆｌａｇ＿ｃｏｕｎｔは１つ加算される（ステップＳ７０５）。このとき、Ｍによる剰余算が行われるため、加算により変数ｆｌａｇ＿ｃｏｕｎｔがＭになった場合には、結果的にゼロにリセットされる。

また、データバッファ１１０の有効領域の開始アドレスｂｓｔａｒｔおよび変数ｒに、それぞれ最長一致長ｍｌｅｎに１を加えたものが加算される（ステップＳ７０６）。これにより、符号化済みとなった部分文字列の長さ分、スライド窓１１１が移動する。

そして、変数ｒが２Ｎ以上になると、図６（ｄ）によって説明したようにスライド窓１１１が左方向にＮ個戻されて、データバッファ１１０が更新される（ステップＳ７８０）。

以上の処理を繰り返した後、変数ｆｌａｇ＿ｃｏｕｎｔが０でなければ未だ出力されていない符号が存在することになるため、残りの符号ＦＬＧおよび符号ＣＯＤＥを出力して（ステップＳ７９０）、符号化処理を終了する。

図８は、本発明の実施の形態における符号化処理変数の初期化処理の手順を示す流れ図である。この符号化処理変数の初期化処理は、図７の符号化処理におけるステップＳ７１０に相当するものである。

まず、符号ＦＬＧの個数を計数する変数ｆｌａｇ＿ｃｏｕｎｔおよびＭ個の符号ＦＬＧをまとめた変数ｆｌｇＭがそれぞれ０にリセットされる（ステップＳ７１１）。そして、部分文字列を検索する長さの最大値を表すＦＭＡＸに、この例における最大値であるＬ（１５）［３］が設定される（ステップＳ７１２）。また、内部状態ｓｔａｔｅが０にリセットされる（ステップＳ７１３）。

そして、データバッファ１１０の有効領域の開始アドレスｂｓｔａｒｔが０にリセットされるとともに、スライド窓１１１の直後の先頭文字の位置を示す変数ｒに「Ｎ−Ｌ（１５）［０］＋１」が設定される（ステップＳ７１３）。図６（ｂ）によって説明したようにスライド窓１１１は、この開始アドレスｂｓｔａｒｔから「ｒ−１」の範囲として位置付けられる。

なお、これらの符号化処理変数の初期化処理において、ステップＳ７１２乃至Ｓ７１４は、本発明の実施の形態に特有の処理である。

図９は、本発明の実施の形態におけるデータバッファ１１０の初期化処理の手順を示す流れ図である。このデータバッファ初期化処理は、図７の符号化処理におけるステップＳ７２０に相当するものである。

まず、データバッファ１１０の有効領域の終了アドレスｂｅｎｄが０にリセットされる（ステップＳ７２１）。そして、この終了アドレスｂｅｎｄが変数ｒ以上になるまで１つずつ加算されながら（ステップＳ７２３）、データバッファ１１０の各要素ｄａｔａ＿ｂｕｆｆｅｒ［ｂｅｎｄ］に０が設定されていく（ステップＳ７２２）。

このようにして当初のスライド窓１１１に０が設定されると、データバッファ１１０の残りの部分に入力データが読み込まれる（ステップＳ７２９）。

図１０は、本発明の実施の形態におけるデータ入力処理の手順を示す流れ図である。このデータ入力処理は、図９のデータバッファ初期化処理におけるステップＳ７２９および後述する図１６のデータバッファ更新処理におけるステップＳ７８９に相当するものである。

このデータ入力処理では、終了アドレスｂｅｎｄがデータバッファ１１０の終端になるまで、すなわち「２Ｎ＋ＦＭＡＸ」になるまで、１つずつ加算されながら（ステップＳ７２９８）、以下の処理が繰り返される。まず、入力データを１文字入力して（ステップＳ７２９１）、入力データの状況を示す変数ｄａｔａ＿ｓｔａｔｕｓがデータ終了の旨を示していなければ（ステップＳ７２９６）データバッファ１１０の要素ｄａｔａ＿ｂｕｆｆｅｒ［ｂｅｎｄ］にその１文字のデータが設定される（ステップＳ７２９７）。

図１１は、本発明の実施の形態における１文字入力処理の手順を示す流れ図である。この１文字入力処理は、図１０のデータ入力処理におけるステップＳ７２９１に相当するものである。

まず、データバッファ１１０に入力データが残っているかチェックして（ステップＳ７２９２）、入力データがあればその入力データのＭビット分を読み進めて、その値を変数ｄａｔａに保持して（ステップＳ７２９３）、変数ｄａｔａ＿ｓｔａｔｕｓにデータ有効の旨を設定する（ステップＳ７２９４）。一方、入力データがなければ、変数ｄａｔａ＿ｓｔａｔｕｓにデータ終了の旨を設定する（ステップＳ７２９５）。

図１２は、本発明の実施の形態における最長一致文字列検索処理の手順を示す流れ図である。この最長一致文字列検索処理は、図７の符号化処理におけるステップＳ７３０に相当するものである。

まず、変数ｒｄにデータバッファ１１０の有効領域の終了アドレスｂｅｎｄと変数ｒの差分を求め（ステップＳ７３１）、変数ｒｄの値がＦＭＡＸ以上であれば変数ｆｆにＦＭＡＸを設定し（ステップＳ７３４）、変数ｒｄの値がＦＭＡＸ未満であれば変数ｆｆに変数ｒｄの値を設定する（ステップＳ７３３）。すなわち、この変数ｆｆには最長一致長の検索範囲が設定されることになる。

続いて、一致文字列の先頭位置を表す変数ｍｐｏｓおよび最長一致長を表す変数ｍｌｅｎが０にリセットされる（ステップＳ７３５）。そして、変数ｉにスライド窓の境界を表す「ｒ−１」が設定された後に（ステップＳ７３６）、変数ｉがデータバッファ１１０の有効領域の開始アドレスｂｓｔａｒｔより小さくなるまで１つずつ減算されながら（ステップＳ７４４）、以下の処理が繰り返される。

この繰返し処理において、ｄａｔａ＿ｂｕｆｆｅｒ［ｉ］とｄａｔａ＿ｂｕｆｆｅｒ［ｒ］が一致する場合には（ステップＳ７３７）、変数ｊに０が設定された後（ステップＳ７３８）、変数ｊが変数ｆｆ以上になるまで１つずつ加算されながら（ステップＳ７４３）、さらに次の処理が繰り返される。すなわち、ｄａｔａ＿ｂｕｆｆｅｒ［ｉ＋ｊ＋１］とｄａｔａ＿ｂｕｆｆｅｒ［ｒ＋ｊ＋１］が一致し（ステップＳ７３９）、かつ、変数ｊが最長一致長ｍｌｅｎよりも大きければ（ステップＳ７４１）新たな先頭位置として変数ｍｐｏｓに変数ｉの値が設定され、新たな最長一致長として変数ｍｌｅｎに変数ｊの値が設定される（ステップＳ７４２）。

この最長一致文字列検索処理により、スライド窓においてスライド窓の直後の先頭文字と同じ文字があるかが検索され、あればその文字が先頭文字となる最長一致文字列が検索される。最長一致文字列が検索されると、「一致長−１」が変数ｍｌｅｎに、その文字のデータバッファにおける位置が変数ｍｐｏｓにそれぞれ設定される。また、スライド窓にそのような文字が検索されないときは、変数ｍｌｅｎに０が設定された状態で次の処理に進むことになる。

図１３は、本発明の実施の形態におけるＰＴＲ符号化処理の手順を示す流れ図である。このＰＴＲ符号化処理は、図７の符号化処理におけるステップＳ７５０に相当するものである。

後述するように、一致長符号決定処理（ステップＳ７５１）において、一致長符号ｃが決定され、また、内部状態ｓｔａｔｅの遷移が行われる。そして、変数ｒのＮによる剰余算の結果が変数ｒＮに設定され、変数ｍｐｏｓのＮによる剰余算の結果が変数ｐｏｓに設定される（ステップＳ７５３）。その結果、変数ｒＮの値が変数ｐｏｓの値よりも大きければ（ステップＳ７５４）、変数ｒＮの値から変数ｐｏｓの値を減算した値が変数ｐに設定される（ステップＳ７５５）。一方、変数ｒＮの値が変数ｐｏｓの値以下であれば（ステップＳ７５４）、Ｎと変数ｒＮの値とを加えた値から変数ｐｏｓの値を減算した値が変数ｐに設定される（ステップＳ７５６）。これにより、変数ｐにはスライド窓における一致文字列の先頭の相対位置が設定される。

このようにして得られた相対位置ｐの下位１２ビットと一致長符号ｃの下位４ビットとを上位側から結合した計１６ビットの値が配列ＣＰＴＲ［ｆｌａｇ＿ｃｏｕｎｔ］に設定される（ステップＳ７５７）。この配列ＣＰＴＲ［ｆｌａｇ＿ｃｏｕｎｔ］は変数ｆｌａｇ＿ｃｏｕｎｔに相当する符号ＰＴＲを保持する配列である。

図１４は、本発明の実施の形態における一致長符号決定処理の手順を示す流れ図である。この一致長符号決定処理は、図１３のＰＴＲ符号化処理におけるステップＳ７５１に相当するものである。

まず、一致長符号ｃに最長一致長ｍｌｅｎから閾値ＰＴＨを減算した値が設定される（ステップＳ７５１１）。これは、ＬＺＳＳ符号と同様の符号割当て方法であり、本発明の実施の形態においては、最長一致長ｍｌｅｎが「１３＋ＰＴＨ」よりも小さい場合（ステップＳ７５１２）にこの符号割当てが採用される。この場合、内部状態ｓｔａｔｅは０に初期化される（ステップＳ７５２１）。また、本発明の実施の形態に特有な処理として、以下の処理が行われる。

最長一致長ｍｌｅｎが「１３＋ＰＴＨ」以上で、かつ、「Ｌ（１４）［ｓｔａｔｅ］」よりも小さい場合（ステップＳ７５１３）、最長一致長ｍｌｅｎが「１３＋ＰＴＨ」に設定されるとともに、一致長符号ｃが１３に決定される（ステップＳ７５１５）。この場合、内部状態ｓｔａｔｅが０より大きければ（ステップＳ７５２２）、１つ小さい値になるよう状態遷移が行われる（ステップＳ７５２３）。

最長一致長ｍｌｅｎが「Ｌ（１４）［ｓｔａｔｅ］」以上で、かつ、「Ｌ（１５）［ｓｔａｔｅ］」よりも小さい場合（ステップＳ７５１４）、最長一致長ｍｌｅｎが「Ｌ（１４）［ｓｔａｔｅ］」に設定されるとともに、一致長符号ｃが１４に決定される（ステップＳ７５１６）。この場合も、内部状態ｓｔａｔｅが０より大きければ（ステップＳ７５２２）、１つ小さい値になるよう状態遷移が行われる（ステップＳ７５２３）。

最長一致長ｍｌｅｎが「Ｌ（１５）［ｓｔａｔｅ］」以上である場合（ステップＳ７５１４）、最長一致長ｍｌｅｎが「Ｌ（１５）［ｓｔａｔｅ］」に設定されるとともに、一致長符号ｃが１５に決定される（ステップＳ７５１７）。この場合、内部状態ｓｔａｔｅが最大値ＳＭＡＸより小さければ（ステップＳ７５２４）、１つ大きい値になるよう状態遷移が行われる（ステップＳ７５２５）。

このようにして、一致長符号ｃが決定するとともに、内部状態ｓｔａｔｅの状態遷移が行われる。

図１５は、本発明の実施の形態におけるＲＡＷ符号化処理の手順を示す流れ図である。このＲＡＷ符号化処理は、図７の符号化処理におけるステップＳ７６０に相当するものである。

ここでは、文字データそのものが利用されるため、スライド窓の直後の文字ｄａｔａ＿ｂｕｆｆｅｒ［ｒ］が配列ＣＲＡＷ［ｆｌａｇ＿ｃｏｕｎｔ］に設定される（ステップＳ７６１）。この配列ＣＲＡＷ［ｆｌａｇ＿ｃｏｕｎｔ］は変数ｆｌａｇ＿ｃｏｕｎｔに相当する符号ＲＡＷを保持する配列である。この場合、最長一致長ｍｌｅｎは０に設定される（ステップＳ７６２）。また、本発明の実施の形態に特有な処理として、内部状態ｓｔａｔｅが０に初期化される（ステップＳ７６３）。

図１６は、本発明の実施の形態におけるデータバッファ更新処理の手順を示す流れ図である。このデータバッファ更新処理は、図７の符号化処理におけるステップＳ７８０に相当するものである。

ここでは、変数ｉが０に設定された上で（ステップＳ７８１）、「Ｎ＋ＦＭＡＸ」以下である間、１つずつ加算されながら（ステップＳ７８３）、ｄａｔａ＿ｂｕｆｆｅｒ［ｉ］にｄａｔａ＿ｂｕｆｆｅｒ［ｉ＋Ｎ］の値が繰り返し移動されていく（ステップＳ７８２）。そして、データバッファ１１０の有効領域の開始アドレスｂｓｔａｒｔ、終了アドレスｂｅｎｄ、および、変数ｒがそれぞれＮ減算される（ステップＳ７８４）。これにより、スライド窓１１１は左方向にＮ個戻されて、図６（ｄ）に示すように位置付けられる。その後、図１０により説明したデータ入力処理により、データバッファ１１０の残りの部分に入力データが読み込まれる（ステップＳ７８９）。

図１７は、本発明の実施の形態における符号出力処理の手順を示す流れ図である。この符号出力処理は、図７の符号化処理におけるステップＳ７７０およびＳ７９０に相当するものである。

ここでは、最初に符号ＦＬＧが出力された後（ステップＳ７９１）、変数ｋが０に設定された上で（ステップＳ７９２）、Ｍより小さい間、１つずつ加算されながら（ステップＳ７９６）、以下の処理が繰り返し行われる。すなわち、ｆｌｇＭの下位からｋビット目が"１"であれば（ステップＳ７９３）符号ＲＡＷが出力され（ステップＳ７９４）、"０"であれば符号ＰＴＲが出力される（ステップＳ７９５）。

図１８は、本発明の実施の形態におけるＦＬＧ符号出力処理の手順を示す流れ図である。このＦＬＧ符号出力処理は、図１７の符号出力処理におけるステップＳ７９１に相当するものである。ここでは、ｆｌｇＭの下位Ｍビットが出力先へ出力される（ステップＳ７９１１）。

図１９は、本発明の実施の形態におけるＲＡＷ符号出力処理の手順を示す流れ図である。このＲＡＷ符号出力処理は、図１７の符号出力処理におけるステップＳ７９４に相当するものである。ここでは、配列ＣＲＡＷ［ｋ］の下位Ｍビットが出力先へ出力される（ステップＳ７９４１）。

図２０は、本発明の実施の形態におけるＰＴＲ符号出力処理の手順を示す流れ図である。このＰＴＲ符号出力処理は、図１７の符号出力処理におけるステップＳ７９５に相当するものである。

このＰＴＲ符号出力処理は、Ｍが８の場合と１６の場合とで処理内容が以下のように異なる。Ｍが８の場合、配列ＣＰＴＲ［ｋ］の下位Ｍビットが先に出力先に出力され（ステップＳ７９５１）、その後、配列ＣＰＴＲ［ｋ］の下位２Ｍビットの上位Ｍビットが出力先に出力される（ステップＳ７９５２）。一方、Ｍが１６の場合、配列ＣＰＴＲ［ｋ］の下位Ｍビットが出力先に出力される（ステップＳ７９５３）。

以上のようにして入力データは符号列に符号化される。このようにして符号化された符号列を復号する際、符号列の全てを一度に復号する方法と、符号列におけるＢ個の文字をブロックとしてブロック毎に復号する方法とが考えられる。ここでは、最初に符号列の全てを一度に復号する一括復号処理について説明する。

図２１は、本発明の実施の形態における一括復号処理のメインフローを示す流れ図である。符号列が符号バッファ２１０に転送された後（ステップＳ８０１）、符号に関する情報が初期化され（ステップＳ８１０）、復号のための変数が初期化される（ステップＳ８２０）。そして、復号すべき符号が終了するまで（ステップＳ８３０およびＳ８０２）、以下の処理が繰り返される。

符号ＦＬＧ（変数ｆｌａｇ）が取得され（ステップＳ８４０）、変数ｆｌａｇが"１"であれば、符号ＲＡＷを復号するために、Ｍビットの符号が取得された後で（ステップＳ８５０）符号ＲＡＷの復号処理が行われる（ステップＳ８６０）。一方、変数ｆｌａｇが"０"であれば、符号ＰＴＲを復号するために、符号ＰＴＲが取得された後で（ステップＳ８８０）符号ＰＴＲの復号処理が行われる（ステップＳ８９０）。なお、符号ＰＴＲの取得に先立って、復号すべき符号が終了いないか判定が行われる（ステップＳ８７０およびＳ８０４）。

図２２は、本発明の実施の形態における符号情報初期化処理の手順を示す流れ図である。この符号情報初期化処理は、図２１の一括復号処理におけるステップＳ８１０および図３３の分割復号初期化処理におけるステップＳ９１０に相当するものである。

ここでは、処理済の符号文字数を計数する変数ｃｏｄｅ＿ｃｏｕｎｔが０にリセットされるとともに（ステップＳ８１１）、符号ＦＬＧの数を計数する変数ｆｌａｇ＿ｃｏｕｎｔが０にリセットされる（ステップＳ８１２）。また、変数ｃｏｄｅ＿ｌｅｎｇｔｈに復号すべき符号の全体の長さが設定される（ステップＳ８１３）。なお、ここにいう符号の長さは、Ｍビットからなる文字の符号列における文字数として表現される。

図２３は、本発明の実施の形態における復号初期化処理の手順を示す流れ図である。この復号初期化処理は、図２１の一括復号処理におけるステップＳ８２０および図３３の分割復号初期化処理におけるステップＳ９２０に相当するものである。

ここでは、復号されたデータの格納先配列ｄｓｔのアドレスが設定される（ステップＳ８２１）。そして、復号対象の先頭文字の位置を示す変数ｒが０に設定され（ステップＳ８２２）、また、内部状態ｓｔａｔｅが０に初期化される（ステップＳ８２３）。

図２４は、本発明の実施の形態における符号終了判定処理の手順を示す流れ図である。この符号終了判定処理は、図２１の一括復号処理におけるステップＳ８３０および図３４の分割復号処理におけるステップＳ９３０に相当するものである。

ここでは、変数ｃｏｄｅ＿ｃｏｕｎｔと変数ｃｏｄｅ＿ｌｅｎｇｔｈが比較されて（ステップＳ８３１）、変数ｃｏｄｅ＿ｃｏｕｎｔが変数ｃｏｄｅ＿ｌｅｎｇｔｈよりも小さければ変数ｃｏｄｅ＿ｓｔａｔｕｓに符号が未だ有る旨が設定され（ステップＳ８３２）、変数ｃｏｄｅ＿ｃｏｕｎｔが変数ｃｏｄｅ＿ｌｅｎｇｔｈ以上になると変数ｃｏｄｅ＿ｓｔａｔｕｓに符号が終了した旨が設定される（ステップＳ８３３）。すなわち、復号された符号の数を計数しておくことにより、復号処理の終了判定が行われる。

図２５は、本発明の実施の形態におけるＦＬＧ符号取得処理の手順を示す流れ図である。このＦＬＧ符号取得処理は、図２１の一括復号処理におけるステップＳ８４０および図３４の分割復号処理におけるステップＳ９４０に相当するものである。

変数ｆｌａｇ＿ｃｏｕｎｔが０でなければ（ステップＳ８４１）、変数ｆｌａｇに変数ｆｌａｇＭのＬＳＢの値が設定され（ステップＳ８４２）、変数ｆｌａｇＭはＬＳＢ方向に１ビットシフトされる（ステップＳ８４３）。また、変数ｆｌａｇ＿ｃｏｕｎｔは１つ減算される（ステップＳ８４４）。

変数ｆｌａｇ＿ｃｏｕｎｔが０であれば（ステップＳ８４１）、Ｍビットの符号（変数ｃｏｄｅ）が取得された後（ステップＳ８４５）、その取得された変数ｃｏｄｅが変数ｆｌａｇＭに設定され（ステップＳ８４６）、変数ｆｌａｇ＿ｃｏｕｎｔに値Ｍが設定される（ステップＳ８４７）。

図２６は、本発明の実施の形態におけるＭＢＩＴ符号取得処理の手順を示す流れ図である。このＭＢＩＴ符号取得処理は、図２１の一括復号処理におけるステップＳ８５０および図２５のＦＬＧ符号取得処理におけるステップＳ８４５に相当するものである。

ここでは、変数ｃｏｄｅ＿ｂｕｆｆｅｒの示す符号バッファの要素ｃｏｄｅ＿ｂｕｆｆｅｒ［ｃｏｄｅ＿ｃｏｕｎｔ］が変数ｃｏｄｅに設定される（ステップＳ８５１）。そして、変数ｃｏｄｅ＿ｃｏｕｎｔが１つ加算される（ステップＳ８５２）。

図２７は、本発明の実施の形態におけるＲＡＷ符号取得処理の手順を示す流れ図である。このＲＡＷ符号取得処理は、図２１の一括復号処理におけるステップＳ８６０ならびに図３８の選択復号処理におけるステップＳ９７９２およびＳ９７８２に相当するものである。

ここでは、変数ｃｏｄｅの内容が格納先配列ｄｓｔ［ｒ］に格納された後（ステップＳ８６１）、変数ｒが１つ加算される（ステップＳ８６２）。また、内部状態ｓｔａｔｅが０に初期化される（ステップＳ８６３）。

図２８は、本発明の実施の形態におけるＰＴＲ符号取得処理の手順を示す流れ図である。このＰＴＲ符号取得処理は、図２１の一括復号処理におけるステップＳ８８０に相当するものである。

このＰＴＲ符号取得処理は、Ｍが８の場合と１６の場合とで処理内容が以下のように異なる。Ｍが８の場合、まず、変数ｃｏｄｅ０にｃｏｄｅ＿ｂｕｆｆｅｒ［ｃｏｄｅ＿ｃｏｕｎｔ］の値が設定され（ステップＳ８８１）、変数ｃｏｄｅ１にｃｏｄｅ＿ｂｕｆｆｅｒ［ｃｏｄｅ＿ｃｏｕｎｔ＋１］の値が設定される（ステップＳ８８２）。また、ｃｏｄｅ＿ｃｏｕｎｔは２つ加算される（ステップＳ８８３）。そして、変数ｃｏｄｅ１の下位Ｍビットと変数ｃｏｄｅ０の下位Ｍビットとを上位側から並べて結合した計２Ｍビットが変数ｃｏｄｅに設定される（ステップＳ８８４）。

一方、Ｍが１６の場合、変数ｃｏｄｅにｃｏｄｅ＿ｂｕｆｆｅｒ［ｃｏｄｅ＿ｃｏｕｎｔ］の値が設定され（ステップＳ８８５）、また、ｃｏｄｅ＿ｃｏｕｎｔは１つ加算される（ステップＳ８８６）。

図２９は、本発明の実施の形態におけるＰＴＲ符号取得処理の手順を示す流れ図である。このＰＴＲ符号取得処理は、図２１の一括復号処理におけるステップＳ８９０ならびに図３８の選択復号処理におけるステップＳ９７９７およびＳ９７８７に相当するものである。

変数ｃｏｄｅの上位１２ビットが変数ｉに設定され（ステップＳ８９１）、変数ｃｏｄｅの下位４ビットが変数ｊに設定される（ステップＳ８９２）。そして、一致長符号が復号され（ステップＳ８９３）、また、符号化されていた部分文字列が複製により復号される（ステップＳ８９５）。

図３０は、本発明の実施の形態における一致長復号処理の手順を示す流れ図である。この一致長復号処理は、図２９のＰＴＲ復号処理におけるステップＳ８９３に相当するものである。

まず、変数ｊの値（一致長符号に相当）に閾値ＰＴＨを加算した値が変数ｊに設定される（ステップＳ８９３１）。これにより、ＬＺＳＳ符号と同様の復号により変数ｊに「一致長−１」が設定される。本発明の実施の形態においては、一致長符号が１３以下の場合にこの符号割当てが採用される。また、本発明の実施の形態に特有な処理として、以下の処理が行われる。

変数ｊの値が「１５＋ＰＴＨ」の場合（ステップＳ８９３２）、変数ｊには「Ｌ（１５）［ｓｔａｔｅ］」が設定される（ステップＳ８９３３）。この場合、内部状態ｓｔａｔｅが最大値より小さければ（ステップＳ８９４１）内部状態ｓｔａｔｅが１つ加算される（ステップＳ８９４２）。

変数ｊの値が「１４＋ＰＴＨ」の場合（ステップＳ８９３４）、変数ｊには「Ｌ（１４）［ｓｔａｔｅ］」が設定される（ステップＳ８９３５）。

また、変数ｊの値が「１５＋ＰＴＨ」より小さい場合（ステップＳ８９３２）、変数ｊの値が「１３＋ＰＴＨ」以上で、かつ、内部状態ｓｔａｔｅが０より大きければ（ステップＳ８９４３）内部状態ｓｔａｔｅから１つ減算され（ステップＳ８９４４）、それ以外であれば内部状態ｓｔａｔｅが０に初期化される（ステップＳ８９４５）。

このような一致長復号処理により、変数ｊに「一致長−１」が設定され、内部状態ｓｔａｔｅの状態遷移が行われる。

図３１は、本発明の実施の形態における複製処理の手順を示す流れ図である。この複製処理は、図２９のＰＴＲ復号処理におけるステップＳ８９５に相当するものである。

変数ｋには変数ｒから変数ｉを減算した値が設定され（ステップＳ８９５１）、変数ｅｎｄには変数ｋに変数ｊを加算した値が設定される（ステップＳ８９５２）。これにより、変数ｋには複製すべき部分文字列の先頭の位置が設定され、変数ｅｎｄには複製すべき部分文字列の末尾の位置が設定される。

そして、変数ｋおよび変数ｒがそれぞれ１つずつ加算されながら（ステップＳ８９５６）、変数ｋが変数ｅｎｄの値以下である間、配列ｄｓｔ［ｋ］の値が配列ｄｓｔ［ｒ］に複製される（ステップＳ８９５５）。但し、変数ｋの値が０であれば（ステップＳ８９５３）、配列ｄｓｔ［ｒ］には０が設定される（ステップＳ８９５４）。

以上のようにして符号列は一括して復号される。次に、符号列におけるＢ個の文字をブロックとして、ブロック毎に復号する分割復号処理について説明する。

図３２は、本発明の実施の形態における分割復号処理のメインフローを示す流れ図である。分割復号のための初期化処理が行われた後（ステップＳ９０１）、復号すべき符号が終了するまで（ステップＳ９０４）、繰り返しＢ個の符号が符号バッファ２１０に転送されて（ステップＳ９０３）、分割復号処理が行われる（ステップＳ９７０）。

図３３は、本発明の実施の形態における分割復号初期化処理の手順を示す流れ図である。この分割復号初期化処理は、図３２の分割復号のメインフローにおけるステップＳ９０１に相当するものである。

ここでは、図２１の一括復号処理と同様に、符号に関する情報が初期化され（ステップＳ９１０）、復号のための変数が初期化される（ステップＳ９２０）。そして、次におこなうべき処理を保持する変数ｏｐに符号ＦＬＧの取得処理を意味する値ＯＰ＿ＦＬＧが設定される（ステップＳ９０２）。

図３４は、本発明の実施の形態における分割復号処理の手順を示す流れ図である。この分割復号処理は、図３２の分割復号のメインフローにおけるステップＳ９７０に相当するものである。

ここでは、まずブロック符号情報の初期化が行われ（ステップＳ９７１）、復号状況を保持する変数ｄｅｃｏｄｅ＿ｓｔａｔｕｓに復号途中である旨が設定される（ステップＳ９７２）。そして、符号バッファ２１０が空になるか（ステップＳ９７３およびＳ９７４）、復号すべき符号が終了するまで（ステップＳ９３０およびＳ９７５）、以下の処理が繰り返される。

変数ｏｐに値ＯＰ＿ＦＬＧが設定されている場合（ステップＳ９７８）、符号ＦＬＧ（変数ｆｌａｇ）が取得されて（ステップＳ９４０）、変数ｆｌａｇが"１"であれば（ステップＳ９８７）変数ｏｐに値ＯＰ＿ＲＡＷが設定され（ステップＳ９８８）、"０"であれば変数ｏｐに値ＯＰ＿ＰＴＲが設定される（ステップＳ９８９）。

また、変数ｏｐに値ＯＰ＿ＦＬＧ以外が設定されている場合（ステップＳ９７８）、Ｍビットの符号が取得されて（ステップＳ９５０）、復号処理の進行状況に合わせて選択的に復号処理が行われる（ステップＳ９７９）。

復号すべき符号が終了すると（ステップＳ９７５）、変数ｄｅｃｏｄｅ＿ｓｔａｔｕｓに復号完了の旨が設定され（ステップＳ９７６）、符号情報として復号処理済の符号文字数を計数する変数ｃｏｄｅ＿ｃｏｕｎｔが更新される（ステップＳ９７７）。

図３５は、本発明の実施の形態におけるブロック符号情報初期化処理の手順を示す流れ図である。このブロック符号情報初期化処理は、図３４の分割復号処理におけるステップＳ９７１に相当するものである。ここでは、符号バッファ２１０の読出し位置を示す変数ｃｏｄｅ＿ｏｆｆｓｅｔが０にリセットされる（ステップＳ９７１１）。

図３６は、本発明の実施の形態におけるバッファ空判定処理の手順を示す流れ図である。このバッファ空判定処理は、図３４の分割復号処理におけるステップＳ９７３に相当するものである。

ここでは、変数ｃｏｄｅ＿ｏｆｆｓｅｔがブロックサイズＢよりも小さければ（ステップＳ９７３１）変数ｃｏｄｅ＿ｓｔａｔｕｓにデータが未だ有る旨が設定され（ステップＳ９７３２）、変数ｃｏｄｅ＿ｏｆｆｓｅｔがブロックサイズＢ以上であれば変数ｃｏｄｅ＿ｓｔａｔｕｓにデータが空である旨が設定される（ステップＳ９７３３）。

図３７は、本発明の実施の形態におけるＭＢＩＴ符号取得処理の手順を示す流れ図である。このＭＢＩＴ符号取得処理は、図３４の分割復号処理におけるステップＳ９５０に相当するものである。

ここでは、変数ｃｏｄｅ＿ｂｕｆｆｅｒの示す符号バッファの要素ｃｏｄｅ＿ｂｕｆｆｅｒ［ｃｏｄｅ＿ｏｆｆｓｅｔ］が変数ｃｏｄｅに設定される（ステップＳ９５１）。そして、変数ｃｏｄｅ＿ｏｆｆｓｅｔが１つ加算される（ステップＳ９５２）。

図３８は、本発明の実施の形態における選択復号処理の手順を示す流れ図である。この選択復号処理は、図３４の分割復号処理におけるステップＳ９７９に相当するものである。

この選択復号処理は、Ｍが８の場合と１６の場合とで処理内容が以下のように異なる。すなわち、符号ＰＴＲはＭによって２文字か１文字になるため、符号取得と復号の処理は、２文字のときはＯＰ＿ＰＴＲとＯＰ＿ＰＴＲ２の２つの処理に分割され、１文字のときはＯＰ＿ＰＴＲのみで処理される。

Ｍが８の場合、変数ｏｐに値ＯＰ＿ＲＡＷが設定されていれば（ステップＳ９７９１）、符号ＲＡＷの復号が行われた後に（ステップＳ９７９２）変数ｏｐに値ＯＰ＿ＦＬＧが設定される（ステップＳ９７９３）。変数ｏｐに値ＯＰ＿ＰＴＲが設定されていれば（ステップＳ９７９１）、変数ｃｏｄｅ０に変数ｃｏｄｅの下位Ｍビットが設定された後に（ステップＳ９７９４）変数ｏｐに値ＯＰ＿ＰＴＲ２が設定される（ステップＳ９７９５）。また、変数ｏｐに値ＯＰ＿ＰＴＲ２が設定されていれば（ステップＳ９７９１）、変数ｃｏｄｅの下位Ｍビットと変数ｃｏｄｅ０の下位Ｍビットとが上位側から結合された計２Ｍビットが変数ｃｏｄｅに設定された後に（ステップＳ９７９６）、符号ＰＴＲの復号が行われ（ステップＳ９７９７）、変数ｏｐに値ＯＰ＿ＦＬＧが設定される（ステップＳ９７９８）。

一方、Ｍが１６の場合、変数ｏｐに値ＯＰ＿ＲＡＷが設定されていれば（ステップＳ９７８２）、符号ＲＡＷの復号が行われた後に（ステップＳ９７９２）変数ｏｐに値ＯＰ＿ＦＬＧが設定される（ステップＳ９７８３）。また、変数ｏｐに値ＯＰ＿ＰＴＲが設定されていれば（ステップＳ９７８１）、符号ＰＴＲの復号が行われた後に（ステップＳ９７８７）、変数ｏｐに値ＯＰ＿ＦＬＧが設定される（ステップＳ９７８８）。

図３９は、本発明の実施の形態における符号情報更新処理の手順を示す流れ図である。この符号情報更新処理は、図３４の分割復号処理におけるステップＳ９７７に相当するものである。ここでは、変数ｃｏｄｅ＿ｃｏｕｎｔに変数ｃｏｄｅ＿ｏｆｆｓｅｔの値が加算される（ステップＳ９７７１）。これにより、変数ｃｏｄｅ＿ｃｏｕｎｔには復号処理済の符号文字数が保持される。

以上のようにして、符号列はＢ個の文字をブロックとして、ブロック毎に復号される。なお、複数の符号バッファを設けて、それらを切り替えて利用するようにしてもよい。この場合には、次のブロックの読込みをしている間に前のブロックの復号処理を行うことができる。

次に本発明の実施の形態における符号化により達成される圧縮率の具体例について説明する。

図４０は、本発明の実施の形態における部分文字列の圧縮率を示す図である。ここでは、符号ＣＯＤＥの内容毎に１つの部分文字列の圧縮率が２種類示されている。一方は一文字が８ビット（Ｍ＝８）で閾値ＰＴＨが２（一致長符号"０"に一致長"３"を割り当てる）の場合であり、他方は一文字が１６ビット（Ｍ＝１６）で閾値ＰＴＨが１（一致長符号"０"に一致長"２"を割り当てる）の場合である。

符号ＦＬＧの１ビットと符号ＣＯＤＥのビット数を合わせたものが１つの部分文字列の符号長である。その符号長を部分文字列の長さで割って求めているため、小さいほど効率がよいことを示す。従来法では「一致長−ＰＴＨ−１」が１５までしか表現できないため、最も良い圧縮率は、Ｍ＝８で１１．８１％、Ｍ＝１６で６．２５％でしかなかった。

そこで、本発明の実施の形態により一致長を長くすると、この例では、Ｍ＝８で０．１２％、Ｍ＝１６で０．０６％にまで小さくすることができる。但し、長い一致長の文字列が元々存在しなければこの符号に割り当てることができないため、長い一致長の文字列が存在するような入力データである必要がある。

プログラムは命令コードと変数の初期値などのデータから構成されており、一般的に命令コードとデータは管理しやすいように分離されてメモリに配置されている。通常の場合、命令コードのすぐ後にデータが配置される。命令コードは命令１つが短い部分文字列と把握することができるため、短い最長一致文字列の頻度が多いことが予想される。またＣ言語などのコンパイラによって生成される命令コードはある程度テンプレート化されており、近似した処理は近似した命令コードとして生成される。それゆえ、似たような関数は命令コードもほとんど変わらないこともしばしばある。このような場合には長い一致文字列で分解できることが期待できる。

また、データについて、変数の初期値には０が多いことなどから、比較的長い一致文字列に分解できることが多い。このような特徴をもつプログラムには本発明の符号割り当てによって圧縮率を向上させることが期待できる。

図４１は、本発明の実施の形態における部分文字列の最長一致長の分布例を示す図である。ここでは、相対位置ＮＰを１２ビット、一致長符号ＮＣを１１ビット、文字幅Ｍを８ビット、閾値ＰＴＨを２として、２０００文字ほどの一致長でも分解できるようにして、あるプログラムをＬＺＳＳ方式で分解したときの、それぞれの部分文字列の最長一致長を順番にプロットしたものである。すなわち、横方向にプログラムにおける部分文字列の出現順序、縦方向にその部分文字列の最長一致長を示している。

プログラムは１８９５２０バイトのサイズであり、５２５９０個の部分文字列に分解されている。２０文字以下の一致長がほとんどであるが、１００文字を超えるものもあるのがわかる。特に、最後の部分にはデータ領域が配置されており、このデータ領域において長い一致長を示していることがわかる。

このプログラムをＭ＝８、ＰＴＨ＝２、ＮＣ＝４、ＮＰ＝１２で符号化したとき、従来のＬＺＳＳ法による圧縮率は４６．２０％であるが、本発明による圧縮率は４３．７８％になる。このように、長い最長一致長で分解可能なプログラムにおいては、圧縮率の向上が実現できる。特に、単純なデータの繰り返しが非常に多い場合には圧縮率が２０％以上改善されることも期待できる。

なお、ここで説明した符号のビット数の例として、ＮＣ＝４、ＮＰ＝１２が選択された。これにより、符号ＰＴＲは１６ビットとなる。符号ＦＬＧはＭビットごとにパックされており、８ビットまたは１６ビットである。符号ＲＡＷは文字そのままであり、これも８ビットまた１６ビットである。このようにすべての符号が８の倍数になるように符号のビット数を決めておくと、余計なビット操作が不要になるため、ソフトウエア処理などに適している。本発明の実施の形態では、ＮＣ＝４のままで、一致長符号ｃに対する一致長の割り当てだけを変更しているため、長い一致長で符号化可能であることに加え、符号を８の倍数のビット数単位で処理できるため、高速なソフトウエア処理が可能である。

図４２は、コンピュータシステムによる圧縮プログラムの伸張処理への本発明の実施の形態の適用例を示す図である。このコンピュータシステムでは、プロセッサ３１０と、ＲＡＭ３２０と、ＲＯＭ３３０とがシステムバス３４０により相互に接続されていると想定する。

プロセッサ３１０はＲＡＭ３２０を作業領域としてプログラムの実行を行う。ＲＡＭ３２０には高速大容量なＳＲＡＭ等が用いられることが多く、一方、ＲＯＭ３３０には比較的小容量なフラッシュメモリ等が用いられることが多い。

ＲＯＭ３３０には圧縮されたプログラム（以下、プログラムＡと呼ぶ。）が圧縮プログラムコード３３２として格納されているものとする。この圧縮プログラムコード３３２はＲＡＭ３２０の圧縮プログラムバッファ３２２に一旦転送される。ＲＡＭ３２０には、プログラムＡを伸張するためのプログラム（以下、プログラムＸと呼ぶ。）が伸張処理用プログラム３２１として予め保持されているものとする。プロセッサ３１０は、プログラムＸを実行することにより、圧縮プログラムバッファ３２２に保持されたプログラムＡを伸張して、伸張プログラムバッファ３２３に格納する。

この伸張処理用プログラム３２１における伸張処理には、本発明の実施の形態による復号処理を適用することができる。すなわち、本発明の実施の形態により符号化されたプログラムＡを保持する圧縮プログラムバッファ３２２を符号バッファ２１０として、伸張プログラムバッファ３２３を復号バッファ２８０とすれば、本発明の実施の形態に係る復号方法を実行する伸張処理用プログラム３２１（プログラムＸ）によってプログラムＡを伸張することができる。

このように、プログラムをフラッシュメモリなどの外部メモリに保存しておいて、これを内部の高速なメモリに転送してからプロセッサで実行して起動する装置においては、外部メモリからの読出しにかかる処理が起動時間に支配的な影響を与える。そこで、外部メモリに圧縮された状態でプログラムを保存しておいて転送後に伸張すれば、より高速な処理が可能となる。この際、伸張処理に要する時間よりも、圧縮により短縮される時間の方が一般に長いことから、全体として起動時間が短縮されることが期待できる。また、ネットワーク配信などによりプログラムが転送されてから起動するような装置においても同様に通信時間が短縮でき、起動時間が短縮されることが期待できる。

以上説明したように、本発明の実施の形態によれば、内部状態保持部１４０および２４０に保持された内部状態に応じて一致長拡張テーブル１５０および２５０を参照することにより、一致長符号化部１６０および一致長復号部２６０で一致長とその一致長符号との対応付けを動的に決定して、一致長符号により表現可能な長さを自立的に切り替えることができる。

なお、本発明の実施の形態は本発明を具現化するための一例を示したものであり、以下に示すように特許請求の範囲における発明特定事項とそれぞれ対応関係を有するが、これに限定されるものではなく本発明の要旨を逸脱しない範囲において種々の変形を施すことができる。

すなわち、請求項１において、検索手段は例えば文字列検索部１３０に対応する。また、内部状態保持手段は例えば内部状態保持部１４０に対応する。また、一致長符号化手段は例えば一致長符号化部１６０に対応する。また、記号列符号化手段は例えば文字列符号化部１７０に対応する。

また、請求項４において、一致長拡張手段は例えば一致長拡張テーブル１５０に対応する。

また、請求項５において、復号バッファは例えば復号バッファ２８０に対応する。また、符号取得手段は例えば符号取得部２３０に対応する。また、内部状態保持手段は例えば内部状態保持部２４０に対応する。また、一致長復号手段は例えば一致長復号部２６０に対応する。また、記号列復号手段は例えば文字列復号部２７０に対応する。

また、請求項８において、一致長拡張手段は例えば一致長拡張テーブル２５０に対応する。

また、請求項９において、符号バッファ制御手段は例えば符号バッファ制御部２２０に対応する。

また、請求項１０において、伸張プログラムバッファは例えば伸張プログラムバッファ３２３に対応する。また、圧縮プログラムバッファは例えば圧縮プログラムバッファ３２２に対応する。また、符号取得手段は例えば符号取得部２３０に対応する。また、内部状態保持手段は例えば内部状態保持部２４０に対応する。また、一致長復号手段は例えば一致長復号部２６０に対応する。また、記号列復号手段は例えば文字列復号部２７０に対応する。

また、請求項１１または１３において、入力データを保持するデータバッファの所定の検索範囲において前記入力データの符号化対象の部分記号列との一致を検索する手順は例えばステップＳ７３０に対応する。また、所定の内部状態に従って一致が検索された部分記号列の一致長に一致長符号を割り当てる手順は例えばステップＳ７５１１乃至Ｓ７５１７に対応する。また、当該一致長に応じて内部状態を更新する手順は例えばステップＳ７５２１乃至Ｓ７５２５に対応する。また、部分記号列のデータバッファにおける相対アドレスと一致長符号とに基づいて部分記号列を符号化する手順は例えばステップＳ７５７に対応する。

また、請求項１２または１４において、符号バッファから部分記号列における相対アドレスと一致長符号とを含む部分記号列符号を取得する手順は例えばステップＳ８８０に対応する。また、所定の内部状態に従って一致長符号に対応する部分記号列の長さを一致長として復号する手順は例えばステップＳ８９３１乃至Ｓ８９３５に対応する。また、復号された一致長に応じて内部状態を更新する手順は例えばステップＳ８９４１乃至Ｓ８９４５に対応する。また、部分記号列における相対アドレスおよび一致長に基づいて復号バッファを参照して部分記号列符号に対応する部分記号列を復号する手順は例えばステップＳ８９５に対応する。

なお、本発明の実施の形態において説明した処理手順は、これら一連の手順を有する方法として捉えてもよく、また、これら一連の手順をコンピュータに実行させるためのプログラム乃至そのプログラムを記憶する記録媒体として捉えてもよい。

本発明の実施の形態における符号化装置１００の一構成例を示す図である。 本発明の実施の形態における符号のデータ構造を示す図である。 本発明の実施の形態における内部状態の状態遷移の一例を示す図である。 本発明の実施の形態における一致長符号ｃと一致長ｌｅｎとの関係の一例を示す図である。 本発明の実施の形態における復号装置２００の一構成例を示す図である。 以下の説明で用いられる本発明の実施の形態におけるデータバッファ１１０とスライド窓１１１との関係を示す図である。 本発明の実施の形態における符号化処理のメインフローを示す流れ図である。 本発明の実施の形態における符号化処理変数の初期化処理の手順を示す流れ図である。 本発明の実施の形態におけるデータバッファ１１０の初期化処理の手順を示す流れ図である。 本発明の実施の形態におけるデータ入力処理の手順を示す流れ図である。 本発明の実施の形態における１文字入力処理の手順を示す流れ図である。 本発明の実施の形態における最長一致文字列検索処理の手順を示す流れ図である。 本発明の実施の形態におけるＰＴＲ符号化処理の手順を示す流れ図である。 本発明の実施の形態における一致長符号決定処理の手順を示す流れ図である。 本発明の実施の形態におけるＲＡＷ符号化処理の手順を示す流れ図である。 本発明の実施の形態におけるデータバッファ更新処理の手順を示す流れ図である。 本発明の実施の形態における符号出力処理の手順を示す流れ図である。 本発明の実施の形態におけるＦＬＧ符号出力処理の手順を示す流れ図である。 本発明の実施の形態におけるＲＡＷ符号出力処理の手順を示す流れ図である。 本発明の実施の形態におけるＰＴＲ符号出力処理の手順を示す流れ図である。 本発明の実施の形態における一括復号処理のメインフローを示す流れ図である。 本発明の実施の形態における符号情報初期化処理の手順を示す流れ図である。 本発明の実施の形態における復号初期化処理の手順を示す流れ図である。 本発明の実施の形態における符号終了判定処理の手順を示す流れ図である。 本発明の実施の形態におけるＦＬＧ符号取得処理の手順を示す流れ図である。 本発明の実施の形態におけるＭＢＩＴ符号取得処理の手順を示す流れ図である。 本発明の実施の形態におけるＲＡＷ符号取得処理の手順を示す流れ図である。 本発明の実施の形態におけるＰＴＲ符号取得処理の手順を示す流れ図である。 本発明の実施の形態におけるＰＴＲ符号取得処理の手順を示す流れ図である。 本発明の実施の形態における一致長復号処理の手順を示す流れ図である。 本発明の実施の形態における複製処理の手順を示す流れ図である。 本発明の実施の形態における分割復号処理のメインフローを示す流れ図である。 本発明の実施の形態における分割復号初期化処理の手順を示す流れ図である。 本発明の実施の形態における分割復号処理の手順を示す流れ図である。 本発明の実施の形態におけるブロック符号情報初期化処理の手順を示す流れ図である。 本発明の実施の形態におけるバッファ空判定処理の手順を示す流れ図である。 本発明の実施の形態におけるＭＢＩＴ符号取得処理の手順を示す流れ図である。 本発明の実施の形態における選択復号処理の手順を示す流れ図である。 本発明の実施の形態における符号情報更新処理の手順を示す流れ図である。 本発明の実施の形態における部分文字列の圧縮率を示す図である。 本発明の実施の形態における部分文字列の最長一致長の分布例を示す図である。 コンピュータシステムによる圧縮プログラムの伸張処理への本発明の実施の形態の適用例を示す図である。 ＬＺＳＳ符号による符号化の例を示す図である。

符号の説明

１００ 符号化装置
１１０ データバッファ
１１１ スライド窓
１２０ データバッファ制御部
１３０ 文字列検索部
１４０ 内部状態保持部
１５０ 一致長拡張テーブル
１６０ 一致長符号化部
１７０ 文字列符号化部
２００ 復号装置
２１０ 符号バッファ
２２０ 符号バッファ制御部
２３０ 符号取得部
２４０ 内部状態保持部
２５０ 一致長拡張テーブル
２６０ 一致長復号部
２７０ 文字列復号部
２８０ 復号バッファ
３１０ プロセッサ
３２１ 伸張処理用プログラム
３２２ 圧縮プログラムバッファ
３２３ 伸張プログラムバッファ
３３２ 圧縮プログラムコード
３４０ システムバス

Claims (14)

1. 入力データを保持するデータバッファの所定の検索範囲において前記入力データの符号化対象の部分記号列との一致を検索する検索手段と、
   所定の内部状態を保持する内部状態保持手段と、
   前記内部状態保持手段に保持された内部状態に従って前記検索手段において一致が検索された前記部分記号列の一致長に一致長符号を割り当てた後で当該一致長に応じて前記内部状態保持手段に保持された内部状態を更新する一致長符号化手段と、
   前記検索部において一致が検索された前記部分記号列の位置と前記一致長符号化手段によって割り当てられた前記一致長符号とに基づいて前記部分記号列を符号化する記号列符号化手段と
   を具備することを特徴とする符号化装置。
2. 前記一致長符号化手段は、前記一致長符号が所定の閾値に満たない場合には前記内部状態保持手段に保持された内部状態を最も低い段階にリセットし、前記一致長符号がその最大値を示している場合には前記内部状態保持手段に保持された内部状態をより高い段階に遷移させ、前記一致長符号が前記閾値を満たしながら前記最大値に満たない場合には前記内部状態保持手段に保持された内部状態をより低い段階に遷移させることを特徴とする請求項１記載の符号化装置。
3. 前記一致長符号化手段は、前記一致長符号が所定の閾値に満たない場合には前記内部状態保持手段に保持された内部状態に依らず前記一致長ごとに定められた符号を前記一致長符号として割り当て、前記一致長符号が前記閾値を満たす場合には前記内部状態および前記一致長によって定められる符号を前記一致長符号として割り当てることを特徴とする請求項１記載の符号化装置。
4. 前記内部状態保持手段に保持された前記内部状態に対応して前記一致長符号に割り当てるべき一致長をそれぞれ定める一致長拡張手段をさらに具備し、
   前記一致長符号化手段は、前記一致長符号が所定の閾値に満たない場合には前記内部状態保持手段に保持された内部状態に依らず前記一致長ごとに定められた符号を前記一致長符号として割り当て、前記一致長符号が前記閾値を満たす場合には前記一致長拡張手段に定められた符号を前記一致長符号として割り当てることを特徴とする請求項１記載の符号化装置。
5. 符号列から復号された部分記号列を保持する復号バッファと、
   前記符号列を保持する符号バッファから前記部分記号列の位置と一致長符号とを含む部分記号列符号を取得する符号取得手段と、
   所定の内部状態を保持する内部状態保持手段と、
   前記内部状態保持手段に保持された内部状態に従って前記一致長符号に対応する部分記号列の長さを一致長として復号した後で当該一致長に応じて前記内部状態保持手段に保持された内部状態を更新する一致長復号手段と、
   前記部分記号列の位置および前記一致長に基づいて前記復号バッファを参照して前記部分記号列符号に対応する部分記号列を復号する記号列復号手段と
   を具備することを特徴とする復号装置。
6. 前記一致長復号手段は、前記一致長符号が所定の閾値に満たない場合には前記内部状態保持手段に保持された内部状態を最も低い段階にリセットし、前記一致長符号がその最大値を示している場合には前記内部状態保持手段に保持された内部状態をより高い段階に遷移させ、前記一致長符号が前記閾値を満たしながら前記最大値に満たない場合には前記内部状態保持手段に保持された内部状態をより低い段階に遷移させることを特徴とする請求項５記載の復号装置。
7. 前記一致長復号手段は、前記一致長符号が所定の閾値に満たない場合には前記内部状態保持手段に保持された内部状態に依らず前記一致長符号ごとに定められた部分記号列の長さを一致長として復号し、前記一致長符号が前記閾値を満たす場合には前記内部状態および前記一致長符号によって定められる部分記号列の長さを一致長として復号することを特徴とする請求項５記載の復号装置。
8. 前記内部状態保持手段に保持された前記内部状態に対応して前記一致長符号に割り当てるべき一致長をそれぞれ定める一致長拡張手段をさらに具備し、
   前記一致長復号手段は、前記一致長符号が所定の閾値に満たない場合には前記内部状態保持手段に保持された内部状態に依らず前記一致長符号ごとに定められた部分記号列の長さを一致長として復号し、前記一致長符号が前記閾値を満たす場合には前記一致長拡張手段に定められた値を一致長として復号することを特徴とする請求項５記載の復号装置。
9. 前記符号バッファに前記符号列を所定のブロックを単位として供給するよう制御する符号バッファ制御手段をさらに具備し、
   前記一致長復号手段は、前記ブロックを復号するたびに次に行うべき処理を記憶しておいて、前回記憶しておいた前記次に行うべき処理に従って次のブロックを復号することを特徴とする請求項５記載の復号装置。
10. 圧縮プログラムから伸張された部分記号列を保持する伸張プログラムバッファと、
    前記圧縮プログラムを保持する圧縮プログラムバッファから前記部分記号列の位置と一致長符号とを含む部分記号列符号を取得する符号取得手段と、
    所定の内部状態を保持する内部状態保持手段と、
    前記内部状態保持手段に保持された内部状態に従って前記一致長符号に対応する部分記号列の長さを一致長として復号した後で当該一致長に応じて前記内部状態保持手段に保持された内部状態を更新する一致長復号手段と、
    前記部分記号列の位置および前記一致長に基づいて前記伸張プログラムバッファを参照して前記部分記号列符号に対応する部分記号列を復号する記号列復号手段と
    を具備することを特徴とする圧縮プログラムの伸張装置。
11. 入力データを保持するデータバッファの所定の検索範囲において前記入力データの符号化対象の部分記号列との一致を検索する手順と、
    所定の内部状態に従って前記一致が検索された前記部分記号列の一致長に一致長符号を割り当てる手順と、
    当該一致長に応じて前記内部状態を更新する手順と、
    前記部分記号列の前記データバッファにおける相対アドレスと前記一致長符号とに基づいて前記部分記号列を符号化する手順と
    を具備することを特徴とする符号化方法。
12. 符号バッファに保持された符号列を復号して、復号された部分記号列を復号バッファに保持させる復号方法において、
    前記符号バッファから前記部分記号列における相対アドレスと一致長符号とを含む部分記号列符号を取得する手順と、
    所定の内部状態に従って前記一致長符号に対応する部分記号列の長さを一致長として復号する手順と、
    前記復号された一致長に応じて前記内部状態を更新する手順と、
    前記部分記号列における相対アドレスおよび前記一致長に基づいて前記復号バッファを参照して前記部分記号列符号に対応する部分記号列を復号する手順と
    を具備することを特徴とする復号方法。
13. 入力データを保持するデータバッファの所定の検索範囲において前記入力データの符号化対象の部分記号列との一致を検索する手順と、
    所定の内部状態に従って前記一致が検索された前記部分記号列の一致長に一致長符号を割り当てる手順と、
    当該一致長に応じて前記内部状態を更新する手順と、
    前記部分記号列の前記データバッファにおける相対アドレスと前記一致長符号とに基づいて前記部分記号列を符号化する手順と
    をコンピュータに実行させることを特徴とするプログラム。
14. 符号バッファに保持された符号列を復号して、復号された部分記号列を復号バッファに保持させるプログラムであって、
    前記符号バッファから前記部分記号列における相対アドレスと一致長符号とを含む部分記号列符号を取得する手順と、
    所定の内部状態に従って前記一致長符号に対応する部分記号列の長さを一致長として復号する手順と、
    前記復号された一致長に応じて前記内部状態を更新する手順と、
    前記部分記号列における相対アドレスおよび前記一致長に基づいて前記復号バッファを参照して前記部分記号列符号に対応する部分記号列を復号する手順と
    をコンピュータに実行させることを特徴とするプログラム。
    

Images