(57)【特許請求の範囲】
【請求項１】
入力される文字列と、辞書に既に登録した文字部分列との最長一致検索により符号化を行うデータ圧縮装置の辞書検索登録方法に於いて、
予め定めた数の複数文字を入力し、
前記複数文字を入力する毎に、インデックスで表わされた既に検索済みの文字列に続く前記複数の入力文字から内部ハッシュによってハッシュ値を生成し、
該ハッシュ値により、前記複数の入力文字を対象に前記辞書の検索及び登録を行い、
前記内部ハッシュのハッシュ関数として、複数の入力文字と既に検索された辞書に登録済み文字列のインデックスとの排他的論理和を求めることを特徴とするデータ圧縮装置の辞書検索登録方法。
【請求項２】
請求項１記載のデータ圧縮装置の辞書検索登録方法に於いて、
前記複数の入力文字の数をｎとした場合、インデックスで表わされた既に検索済みの文字列に続く文字数毎に設けたｎ個の辞書を、内部ハッシュにより生成した文字数毎のハッシュ値により、同時に辞書検索することを特徴とするデータ圧縮装置の辞書検索登録方法。
【請求項３】
請求項１記載のデータ圧縮装置の辞書検索登録方法に於いて、前記ハッシュ値の各ビットが均等且つ対称となるように、前記複数の入力文字と前記辞書のインデックスとの排他的論理和を求めることを特徴とするデータ圧縮装置の辞書検索登録方法。
【請求項４】
請求項３記載のデータ圧縮装置の辞書検索登録方法に於いて、前記複数の入力文字と前記辞書のインデックスとのビット数が相違して排他的論理和を求める各ビットが均等且つ対称とならない場合には、上位ビット側で排他的論理和を求めるようにビット配置することを特徴とするデータ圧縮装置の辞書検索登録方法。
【請求項５】
入力される文字列Ｋと、辞書に既に登録した文字部分列との最長一致検索により符号化を行うデータ圧縮装置の辞書検索登録方法に於いて、
予め定めた数の複数文字を入力し、
前記複数文字を入力する毎に、インデックスで表わされた既に検索済みの文字列に続く前記複数の入力文字から内部ハッシュによってハッシュ値を生成し、
該ハッシュ値により、前記複数の入力文字を対象に前記辞書の検索を行い、
該辞書検索で不一致を検出した際に生成するリハッシュ値として、最初のハッシュ値に対応した乱数列を順に発生して再度辞書を検索し、
前記内部ハッシュのハッシュ関数として、複数の入力文字と既に検索された辞書に登録済み文字列のインデックスとの排他的論理和を求めることを特徴とするデータ圧縮装置の辞書検索登録方法。
【請求項６】
請求項５記載のデータ圧縮装置の辞書検索登録方法に於いて、前記リハッシュ値として、最初のハッシュ値を拡大ガロア体ＧＦ（２m ）上の１つの元（αi ）とし、該元（αi ）に同じ拡大ガロア体ＧＦ（２m ）上の全ての元（α1 ，α2 ，・・・・α2**m-1）とから拡大ガロア体上での排他的論理和により乱数列を順に発生させることを特徴とするデータ圧縮装置の辞書検索登録方法。
【請求項７】
請求項６記載のデータ圧縮装置の辞書検索登録方法に於いて、
前記拡大ガロア体上の全ての元（α1 ，α2 ，・・・・α2**m-1）を、１つ前に生成した元（αi-1 ）と原始元（α1 ）との拡大ガロア体上での累積乗算により順に発生させることを特徴とするデータ圧縮装置の辞書検索登録方法。
【請求項８】
請求項５記載のデータ圧縮装置の辞書検索登録方法に於いて、２m 個の状態に対応して２m 個が連なる相異なる前記乱数列を、２m 個の状態を拡大ガロア体ＧＦ（２m ）上の元（α）として捉え、該元（α）の値と原始元（α1 ）の拡大ガロア体上の累積乗算により順に発生させるデータ圧縮装置の辞書検索登録方法。
【請求項９】
予め定めた複数文字を入力する毎に、インデックスで表わされた既に検索済みの文字列に続く前記複数の入力文字から内部ハッシュによってハッシュ値を生成し、該ハッシュ値により前記複数の入力文字を対象に前記辞書の検索及び登録を行って得られた圧縮データから文字列を復元するデータ復元装置の辞書検索登録方法に於いて、
入力された符号から辞書の検索により文字列を復元する毎に、入力符号に続くすでに復元された複数の入力文字から内部ハッシュによってハッシュ値を生成し、
該ハッシュ値により、前記複数の復元文字を対象に前記辞書の登録を行い、
前記内部ハッシュのハッシュ関数として、複数の入力文字と既に検索された辞書に登録済み文字列のインデックスとの排他的論理和を求めることを特徴とするデータ圧縮装置の辞書検索登録方法。
【請求項１０】
予め定めた複数文字を入力する毎に、インデックスで表わされた既に検索済みの文字列に続く前記複数の入力文字から内部ハッシュによってハッシュ値を生成し、該ハッシュ値により前記複数の入力文字を対象に前記辞書の検索及び登録を行って得られた圧縮データから文字列を復元するデータ復元装置の辞書検索登録方法に於いて、
入力された符号から辞書の検索により文字列を復元する毎に、入力符号に続くすでに復元された複数の入力文字から内部ハッシュによってハッシュ値を生成し、
該ハッシュ値により、前記複数の復元文字を対象に前記辞書の登録を行い、該辞書登録の際に、既に同じハッシュ値を使用した登録を検出した際に、最初のハッシュ値に対応した乱数列を順に発生して再度辞書に登録し、
前記内部ハッシュのハッシュ関数として、複数の入力文字と既に検索された辞書に登録済み文字列のインデックスとの排他的論理和を求めることを特徴とするデータ圧縮装置の辞書検索登録方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、入力文字列と辞書に既に登録した文字部分列との最長一致検索により符号化を行うデータ圧縮装置及び復元装置の辞書検索登録方法に関し、特に複数の入力文字と登録済文字列から内部ハッシュによりインデックスを生成して辞書を検索登録するデータ圧縮装置および復元装置の辞書検索登録方法に関する。
【０００２】
【従来の技術】
近年、文字コード、ベクトル情報、画像など様々な種類のデータがコンピュータで扱われるようになっており、扱われるデータ量も急速に増加してきている。大量のデータを扱うときは、データの中の冗長な部分を省いてデータ量を圧縮することで、記憶容量を減らしたり、速く伝送したりできるようになる。
【０００３】
様々なデータを１つの手順でデータ圧縮できる方法としてユニバーサル符号化が提案されている。ここで、本発明の分野は、文字コードの圧縮に限らず、様々なデータに適用できるが、以下では、情報理論で用いられている呼称を踏襲し、データの１ワード単位を文字と呼び、データが任意の複数ワードにつながったものを文字列と呼ぶことにする。
【０００４】
ユニバーサル符号の代表的な方法として、ジブ・レンペル（Ziv-Lempel）符号がある（詳しくは、例えば、宗像「Ziv-Lempelのデータ圧縮法」、情報処理、Vol.26,No.1,1985年を参照のこと）。
ジブ・レンペル符号には、スライド辞書法と、動的辞書法(Incremental
parsing)の２つのアルゴリズムが提案されている。さらに、スライド辞書型アルゴリズムの改良として、ＬＺＳＳ符号がある（T.C. Bell,"Better OPM/L TextCompression",IEEE Trans. on Commun., Vol.COM-34,No.12, Dec. 1986参照）。
【０００５】
また動的辞書型アルゴリズムの改良としては、ＬＺＷ（Lempel-Ziv-Welch）符号がある（T.A. Welch,"A Technique for High-Performance Data Compression",Computer, June 1984参照）。これらの符号のうち、高速処理ができることと、アルゴリズムの簡単さからＬＺＷ符号が記憶装置のファイル圧縮などで使われるようになっている。
【０００６】
図２３にＬＺＷ符号における辞書の木構成を示し、図２４にＬＺＷ符号における文字列の符号化を示す。ＬＺＷ符号化は、書き替え可能な辞書を持ち、入力文字列（ソースデータ）中を相異なる文字列に分け、この文字列を出現した順に番号をつけて辞書に登録すると共に、現在入力している文字列を辞書に登録してある最長一致文字列の番号で表して、符号化するものである。
【０００７】
図２５はＬＺＷ符号化処理の具体例であり、説明を簡単にするため、ａ，ｂ，ｃの３文字の場合を例にとっている。このため符号化に使用する図２６の辞書には、文字ａ，ｂ，ｃの各々が初期登録されている。
図２５において、入力データは左から右へ読み込む。最初の文字ａを入力したとき、辞書には文字ａの他に一致する文字列がないので、参照番号（インデックス）を符号語として出力する。そして、拡張した文字列ａｂに参照番号４をつけて辞書に登録する。実際の登録は文字列（１ｂ）の形となる。
【０００８】
続いて２番目の文字ｂが文字列の先頭になる。辞書には文字ｂの他に一致する文字列がないので、参照番号２を符号語として出力し、拡張した文字列ｂａを実際には２ａの形で参照番号５をつけて辞書に登録する。３番目の文字ａが次の文字列の先頭になる。以下、同様にこの処理を続ける。
図２７のフローチャートは、ＬＺＷ符号化のアルゴリズムである。まずステップＳ１で予め全文字につき１文字からなる文字列を初期値として辞書に登録してから符号化を始める。ステップＳ２では入力した最初の文字Ｋを辞書検索の参照番号（インデックス）ωとし、これを語頭文字列（prefix string ）とする。次にステップＳ３で入力データの次の文字Ｋを読み込み、ステップＳ４ではステップＳ２で求めた語頭文字列ωにステップＳ３で読み込んだ文字Ｋを加えた文字列（ωＫ）が現在の辞書にあるか否か検索する。
【０００９】
ステップＳ４で文字列（ωＫ）が辞書にあれば、ステップＳ５で文字列（ωＫ）を参照番号ωに置き換え、ステップＳ５で入力データが終了かどうかを判断した後、再びステップＳ３に戻って文字列（ωＫ）が辞書から探せなくなるまで最大一致長の検索を続ける。
次にステップＳ４で文字列（ωＫ）が辞書になければ、ステップＳ７に進んで、ステップＳ２で求めた文字Ｋの参照番号ωを符号語code（ω）として出力し、また文字列（ωＫ）に新たな参照番号を付加して辞書に登録し、さらにステップＳ２の入力文字Ｋを参照番号ωに置き換えるとともに、辞書アドレスＮをインクリメントして、ステップＳ５のチェックを受けた後、ステップＳ２に戻って次の文字Ｋを読み込む。
【００１０】
図２８はＬＺＷ復号化処理の具体例であり、説明を簡単にするため、ａ，ｂ，ｃの３文字の組み合わせを例にとっている。まず最初の入力符号は１であり、１文字ａ，ｂ，ｃについては、図２６のように既に参照番号１，２，３として辞書に登録されているため、辞書の参照により符号１に一致する参照番号の文字列ａに置き換えて出力する。
【００１１】
次の符号２についても同様にして文字ｂに置き換えて出力する。このとき前回処理した符号１と今回復号した最初の１文字ｂとを組み合わせた（１ｂ）に新たな参照番号４を付加して辞書に登録する。３番目の符号４は辞書の探索により１ｂからａｂと置き換えて文字列ａｂを出力する。同時に前回処理した符号２と今回復号した文字列の１番目の文字ａとの組み合わせ文字列２ａ（＝ｂａ）を新たな参照番号５を付加して辞書に登録する。以下同様に、この処理を繰り返す。
【００１２】
ここで、図２８の復号化には次の例外処理がある。この例外処理は、第６番目の入力符号８の復号で生ずる。符号８は復号時に辞書に定義されておらず、復号できない。この場合には、前回処理した符号５に前回復号した文字列ｂａの最初の一文字ｂを加えた文字列５ｂを求め、更に２ａｂ，ｂａｂと置き換えられて出力される。そして、文字列の出力語に前回の符号語５に今回復号した文字列の文字ｂを加えた文字列５ｂに参照番号８を付加して辞書に登録する。
【００１３】
この例外処理は図２９の復号化処理フローのステップＳ４，ステップＳ９の処理を通じて行われ、最終的にステップＳ７で文字列の出力と新たな文字列に参照番号を付加した辞書への登録が行われる。
図２９のフローチャートは、ＬＺＷ復号化のアルゴリズムであり、図２７の符号化の逆の操作を行う。まずステップＳ１において符号化と同様に予め辞書に全文字につき１文字からなる文字列を初期値として登録してから復号を始める。ステップＳ２で最初の符号（参照番号）を読み込み、現在のCODEをOLDcode とし、最初の符号は既に辞書に登録された一文字の参照番号いずれかに該当することから、入力符号CODEに一致する文字code（Ｋ）を探し出し、文字Ｋを出力する。尚、出力した文字（Ｋ）は後の例外処理のためcharにセットしておく。
【００１４】
次にステップＳ３に進んで次の符号を読み込んでCODEにNEWcode としてセットする。次にステップＳ４に進み、ステップＳ３で入力された符号CODEが辞書に定義（登録）されているか否かチェックする。通常、入力した符号語は前回までの処理で辞書に登録されているため、ステップＳ５に進んで符号CODEに対応する文字列code（ωＫ）を辞書から読み出し、ステップＳ６で文字列Ｋを一時的にスタックし、参照番号code（ω）を新たなCODEとして再度ステップＳ５に戻し、このステップＳ５，ステップＳ６の手順を再帰的に参照番号ωが一文字に至るまで繰り返す。
【００１５】
最後にステップＳ７に進んで、ステップＳ６でスタックした文字をＬＩＬＯ  （Last In Fast Out）形式でポップアップして出力する。同時にステップＳ７において、前回使った符号ωと今回復元した文字列の最初の一文字Ｋを組（ω，Ｋ）と表した文字列に新たな参照番号を付加して辞書に登録する。
尚、ステップＳ４において登録されていない符号であった（符号化において直前の参照番号を参照する場合におきる）場合、ステップＳ９にて、OLDcode を  CODEに、code(OLDcode,char)をNEWcode に戻した後にステップＳ５へ進むようにする。また図２８の第６番目の入力符号８の復号を生ずる例外処理は、ステップＳ４，ステップＳ９の処理を通じて行われ、最終的にステップＳ７で文字列の出力と新たな文字列に参照番号を付加した辞書への登録が行われる。
【００１６】
【発明が解決しようとする課題】
しかしながら、このような従来のＬＺＷ符号等を用いたデータ圧縮及び復元の処理にあっては、辞書に対する文字登録が１バイト単位に行われており、このため符号化又は復号化における辞書検索が１バイトずつしか行うことができず、辞書の検索及び登録に時間がかかる問題があった。
【００１７】
この問題を具体的に説明すると次のようになる。図３０は、従来のデータ圧縮処理における辞書の検索登録のブロックであり、複数入力部１００、単数入力一致検出部１０２、単数入力登録部１０４及び辞書メモリ１０６で構成されている。
図３１は図３０における辞書検索処理である。いま第１番目の文字Ｋ１を入力すると、辞書メモリ１０６の登録で実現されている木構造の接点アドレスを示すインデックスωと入力文字Ｋ１をステップＳ１で組み合せ、ステップＳ２で内部ハッシュによってハッシュ値Ｈ（ω，Ｋ１）を求め、ステップＳ３でハッシュ値Ｈ（ω，Ｋ１）をインデックスとして辞書メモリ１０６の検索を行う。
【００１８】
この辞書検索によって辞書メモリ１０６から読み出したインデックスω’と文字Ｋ１’が、ハッシュ値の生成に使用したインデックスωと文字Ｋ１に各々一致するかどうかをステップＳ５で比較する。両者の一致を検出すると、ステップＳ１に戻って新たなインデックスと次の文字で新ハッシュ値を作り、辞書検索を繰り返す。
【００１９】
一致しない場合は、ステップＳ６でリハッシュ関数の定義に従ってリハッシュ値を求めて、インデックスωと文字Ｋ１に各々一致するまで辞書検索を繰り返す。最初のハッシュ値による検索で辞書登録がなかったり、又はリハッシュ値による検索で辞書登録がなかった場合には、ステップＳ４で符号化及び辞書の登録を行う。
【００２０】
このような従来の辞書検索は、入力した文字の１バイト単位にハッシュ処理及びリハッシュ処理を伴う辞書の検索処理と登録処理を行わなければならないため、辞書の検索登録に時間がかかる問題があった。
本発明は、このような従来の問題点に鑑みてなされたもので、辞書の検索と登録を高速化して処理時間を短縮できるようにしたデータ圧縮装置及び復元復元の辞書検索登録方法を提供することを目的とする。
【００２１】
【課題を解決するための手段】
図１は本発明の原理説明図である。データ圧縮装置を例にとると、本発明は、図１（Ａ）のように、入力される文字列と辞書１６に既に登録した文字部分列との最長一致検索により符号化を行うデータ圧縮復元に用いる辞書検索登録方法として、複数入力検索手段１０で、予め定めた数の複数の入力文字（Ｋ１，Ｋ２，・・・Ｋｎ）と既に検索された辞書に登録済文字列を示すインデックス（ω）から内部ハッシュによってハッシュ値Ｈ（ω，Ｋ１，Ｋ２，・・・Ｋｎ）を生成し、次に複数入力一致検出手段１２でハッシュ値をインデックスとして複数の入力文字（Ｋ１，Ｋ２，・・・Ｋｎ）を対象に辞書１６の検索を行う。この検索により文字列の登録が無ければ、複数入力登録手段１４で文字列（ω，Ｋ１，Ｋ２，・・・Ｋｎ）の辞書１６への登録を行う。
【００２２】
ここで、複数の入力文字の数をｎとした場合、インデックスで表わされた既に検索済みの文字列ωに続く文字数毎に設けたｎ個の辞書、即ち（ω、Ｋ１）、  （ω，ｋ１，Ｋ２）、・・・（ω，Ｋ１，Ｋ２，・・Ｋｎ）毎に設けたｎ個の辞書を、内部ハッシュにより生成した文字数毎のハッシュ値Ｈ（ω、Ｋ１）、Ｈ  （ω，ｋ１，Ｋ２）、・・・Ｈ（ω，Ｋ１，Ｋ２，・・Ｋｎ）により、同時に辞書検索する。
【００２３】
また内部ハッシュのハッシュ関数として、複数の入力文字と既に検索された辞書に登録済文字列のインデックスの排他的論理和をとる。この場合、ハッシュ値の各ビットが均等且つ対称となるように、複数の入力文字と辞書のインデックスとの排他的論理和を求める。ここで、複数の入力文字と辞書のインデックスとのビット数が相違して排他的論理和を求める各ビットが均等且つ対称とならない場合には、上位ビット側で排他的論理和を求めるようにビット配置する。
【００２４】
また本発明は、入力される文字列Ｋと、辞書に既に登録した文字部分列との最長一致検索により符号化を行うデータ圧縮装置の辞書検索登録方法について、図１（Ｂ）のように、ハッシュ値発生手段２０によって、予め定めた数の複数の入力文字（Ｋ１，Ｋ２，・・・Ｋｎ）と既に検索された辞書に登録済文字列を示すインデックス（ω）から内部ハッシュによってハッシュ値Ｈ（ω，Ｋ１，Ｋ２，・・・Ｋｎ）を生成し、次に辞書検索手段２２によって、複数入力一致検出手段１２でハッシュ値をインデックスとして複数の入力文字（Ｋ１，Ｋ２，・・・Ｋｎ）を対象に辞書１６の検索を行い、更に、一致／不一致検出手段２４によって辞書検索で不一致を検出した際に、リハッシュ手段２６で生成するリハッシュ値として、最初のハッシュ値に対応した乱数列を順に発生して再度辞書を検索する。
【００２５】
このリハッシュ値としては、最初のハッシュ値を拡大ガロア体ＧＦ（２m ）上の１つの元（αi ）とし、この元（αi ）に同じ拡大ガロア体ＧＦ（２m ）上の全ての元（α1 ，α2 ，・・・・α2**m-1）とから拡大ガロア体上での排他的論理和により乱数列を順に発生させる。
具体的には、拡大ガロア体ＧＦ（２m ）上の全ての元（α1 ，α2 ，・・・・α2**m-1）を、１つ前に生成した元（αi-1 ）と原始元（α1 ）との拡大ガロア体上での累積乗算により順に発生させる。
【００２６】
更に、２m 個の状態に対応して２m 個が連なる相異なる乱数列を、２m 個の状態を拡大ガロア体ＧＦ（２m ）上の元（α）として捉え、この元（α）の値と原始元（α1 ）の拡大ガロア体上の累積乗算により順に発生させる。
更に本発明はデータ復元装置の辞書検索登録方法を提供する。データ復元装置は、予め定めた複数文字を入力する毎に、インデックスで表わされた既に検索済みの文字列に続く複数の入力文字から内部ハッシュによってハッシュ値を生成し、このハッシュ値により前記複数の入力文字を対象に前記辞書の検索及び登録を行って得られた圧縮データから文字列を復元する。
【００２７】
このようなデータ復元装置につき本発明の辞書検索登録方法は、入力された符号から辞書の検索により文字列を復元する毎に、入力符号に続くすでに復元された複数の入力文字から内部ハッシュによってハッシュ値を生成し、このハッシュ値により、複数の復元文字を対象に辞書の登録を行う。
またデータ復元時のリハッシュによる辞書の再登録として、本発明の辞書検索登録方法は、入力された符号から辞書の検索により文字列を復元する毎に、入力符号に続くすでに復元された複数の入力文字から内部ハッシュによってハッシュ値を生成し、このハッシュ値により、複数の復元文字を対象に辞書の登録を行った際に、既に同じハッシュ値を使用した辞書の登録済みを検出した場合に、最初のハッシュ値に対応した乱数列を順に発生して再度辞書に登録する。
【００２８】
このように本発明は、複数文字（複数バイト分の文字）を一括した辞書の検索と登録ができることで、データ圧縮及び復元における辞書の検索登録時間が短くて済み処理時間を短縮できる。特に、本発明の内部ハッシュでは、複数文字（Ｋ1 〜Ｋn ）を同時検索することで処理時間を短縮する。具体的には、１バイトからｎバイトの各バイト数単位毎に入力検索手段１０及び一致検出手段１２を設けて並列的に同時動作させることで、高速化を図る。
【００２９】
また本発明によれば、内部ハッシュのデータ構造を用いることで、辞書メモリの高速検索と登録を可能とする。更に、リハッシュ値として拡大ガロア体の元を用いることで、最初のハッシュ値に対応して全く異なるリハッシュ値を発生させることができ、内部ハッシュの衝突を極力避ける効果がある。
【００３０】
【発明の実施の形態】
図２は本発明の辞書検索登録方法の基本概念を示すブロック図であり、データ圧縮装置を例にとっている。本発明の辞書検索登録方法を採用したデータ圧縮装置は、予め定めた複数の入力文字を検索する複数入力検出部１０、複数の入力文字と検索された複数文字の一致検出を行う複数入力一致検出部１２、複数の入力文字を一度に登録する複数入力登録部１４、及び複数文字の検索と登録が可能な辞書メモリ１６で構成される。このように複数文字を一括して検索及び登録することで、処理時間を短縮することができる。
【００３１】
図３は、図２のデータ圧縮装置における複数文字を一括して行う辞書の検索と登録の処理である。まず複数入力検索部１０にあっては、ステップＳ１に示すように、予め定めたｎ個の文字Ｋ１，Ｋ２，・・・Ｋｎと既に登録済みの文字列を示す木構造の節点アドレス（インデックス）ωの組合わせ（ω，Ｋ１，Ｋ２，・・・Ｋｎ）を複数入力文字として、ステップＳ２のように内部ハッシュ構造によって所定のハッシュ関数に従ったハッシュ値Ｈ（ω，Ｋ１，Ｋ２，・・・，Ｋｎ）を作成する。
【００３２】
このように作成したハッシュ値を使用して辞書メモリ１６の辞書検索を行い、辞書メモリ１６の検索で得られた（ω´，Ｋ１´，Ｋ２´，・・・Ｋｎ´）がステップＳ１の複数入力文字における（ω，Ｋ１，Ｋ２，・・・Ｋｎ）のそれぞれと一致するか否か、ステップＳ３で比較する。即ち、複数入力一致検出部１２で一致検出を行う。
【００３３】
ここで辞書検索内容と複数入力文字が全て一致していた場合には、ステップＳ４で一致検出を判別して、新たに得られた辞書の節点アドレス（インデックス）と次のｎ個の入力文字を複数入力文字として同様な辞書検索を行う。
一方、ステップＳ３の辞書検索結果の一致検出で不一致となった場合には、ステップＳ４からステップＳ５に進み、予め定めたハッシュ関数定義に従ってリハッシュ値を作成し、ステップＳ２でリハッシュ値を用いた辞書検索を行う。
【００３４】
最初の複数入力文字によるハッシュ値あるいはリハッシュ値による辞書検索により、ステップＳ３でハッシュ値に対応する登録内容が辞書から検索できなかった場合、即ち辞書メモリ１６にハッシュ値に対応する登録が存在しなかった場合には、検出無しとしてステップＳ６に進み、このときのハッシュ値またはリハッシュ値をインデックスとして複数文字の辞書メモリ１６に対する一括登録を行う。
【００３５】
図４は１バイト構成のｎ個の文字を複数入力する場合の図２の複数入力検索部１０、複数入力一致検出部１２の並列処理構成のブロック図である。即ち、複数入力検索部１０は、１バイト検索部１０−１、２バイト検索部１０−２、・・・，ｎバイト検索部１０−ｎの並列構成となる。また複数入力一致検出部１２は、一致／不一致検出部１２−１，１２−２，・・・，１２−ｎの並列構成となる。そして、総合一致／不一致判断部３０により各バイトごとの一致／不一致検出部１２−１の検出結果の総合的な一致または不一致の判断を行う。
【００３６】
図５は、ＬＺＷ符号の木構造から見た本発明の複数文字を一括して辞書の検索と登録を行う場合の辞書の検索及び登録範囲を示している。この木構造にあっては、３バイト分の複数文字を検索登録する場合であり、先頭の１文字目を木構造の節点アドレス（インデックス）ωとすると、木構造の２文字目は辞書１６−１に登録され、３文字目までは辞書１６−２に登録され、４文字目までは辞書１６−３に登録され、それぞれの辞書１６−１，１６−２，１６−３から先頭１文字目の節点アドレス（インデックス）ωに続くそれぞれの複数文字を検索する。
【００３７】
更に、木構造の５文字目は辞書１６−１に登録され、図示していないが木構造の６文字目までは辞書１６−２に登録され、更に７文字目までは辞書１６−３に登録されるという形で繰り返される。
この図５のような例えば３バイトまでの複数文字を検索登録するための辞書構造について、図４に示した並列処理のハードウェアを使用することで、各辞書１６−１，１６−２，１６−３の辞書検索を同時に効率的に行うことができる。またソフトウェアにあっては逐次処理となるが、この場合には文字数の多い辞書１６−３，１６−２，１６−１の順に辞書検索を進めることで、より効率的な辞書検索が実現できる。
【００３８】
図６は図５の３バイト分の複数文字の検索と登録を内部ハッシュにより行う場合のブロック図である。まず１バイト入力検索部１０−１は、ハッシュ値発生部１１−１と１バイト目までの１文字を登録した辞書メモリ１６−１から構成される。この１バイト入力検索部１０−１における１バイト検索では、検索したいインデックスω１と入力した１文字Ｋ１からハッシュ関数Ｈ（ω１，Ｋ１）に基づいてハッシュ値を作成し、ハッシュ値として作成されたアドレスにより辞書メモリ１６−１を検索する。
【００３９】
辞書メモリ１６−１には登録の有無を示すフラグＦが設けられ、フラグＦがセット状態にあるときにはインデックスωと文字Ｋが登録されている。この場合、ハッシュ関数Ｈ（ω１，Ｋ１）によるハッシュ値をアドレスとして辞書メモリ１６−１を検索することで、フラグＦのセットで登録の存在を検出し、同時にインデックスω１´と１文字Ｋ１´が読み出される。
【００４０】
１バイト入力一致検出部１２−１は比較部１３−１１を有し、辞書メモリ１６−１から読み出したフラグＦがリセット即ちＦ＝０であるか否か検出し、検出無判断部１５−１１から検出無しの出力▲１▼を生ずる。また比較部１３−１２で入力したインデックスω１と辞書から読み出したインデックスω１´を比較し、同時に比較部１３−１３で入力した１文字Ｋ１と辞書から読み出した１文字Ｋ１´を比較する。
【００４１】
この比較結果は一致／不一致判断部１５−１２に与えられ、不一致であればリハッシュ値を生成して再度、辞書メモリ１６−１の検索を行う。一致していれば一致出力▲４▼を下側に示す総合一致／不一致判断部１７−２に出力する。
次の２バイト入力検索部１０−２は、ハッシュ値発生部１１−２で検索したいインデックスω１と２バイト目までの２文字Ｋ１，Ｋ２からハッシュ値Ｈ（ω１，Ｋ１，Ｋ２）を作成し、そのアドレスで辞書メモリ１６−２を検索する。この辞書検索により得られたフラグＦ、インデックスω１´、文字Ｋ１´，Ｋ２´のそれぞれを、２バイト一致検出部１２−２に設けた比較部１３−２１，１３−２２，１３−２３，１３−２４で比較する。
【００４２】
このときフラグＦがＦ＝０であれば、検出無判断部１５−２１より下側の総合検出無判断部１７−１に対し検出無しの出力▲２▼を出す。また比較部１３−２２〜１３−２４で読み出した（ω１´，Ｋ１´，Ｋ２´）を、入力した（ω１，Ｋ１，Ｋ２）とそれぞれ比較し、一致／不一致判断部１５−２２で判断し、不一致であればリハッシュ値を生成して辞書メモリ１６−２の再検索を行い、一致していれば下側の総合一致／不一致判断部１７−２に対し一致出力▲５▼を生ずる。
【００４３】
更に３バイト入力検索部１０−３にあっては、ハッシュ値発生部１１−３で検索したいインデックスω１と３バイト目までの３文字（Ｋ１，Ｋ２，Ｋ３）からハッシュ値Ｈ（ω１，Ｋ１，Ｋ２，Ｋ３）を作り、そのアドレスで辞書メモリ１６−３を検索する。この場合、３バイト目の辞書には図５の木構造から明らかなように、登録の存在の有無を示すと同時に次に続くインデックスω４が登録されている。
【００４４】
これを３バイト一致検出部１２−３の比較部１３−３１に入力して、もしω４＝０であれば検出無判断部１５−３１でアドレスに対応する登録無しとして、下側の総合検出無判断部１７−１に検出無しの出力▲３▼を生ずる。ω４が０以外の有効値、即ち適宜の後続するインデックスの値をとっている場合には、辞書メモリ１６−３よりインデックスω１´、文字Ｋ１´，Ｋ２´，Ｋ３´がそれぞれ得られ、ハッシュ値の作成に使用したインデックスω１及び入力文字Ｋ１，Ｋ２，Ｋ３のそれぞれとの比較が行われ、比較結果に基づき一致／不一致判断部１５−３２が出力▲６▼を下側の総合一致／不一致判断部１７−２に出力する。
【００４５】
総合検出無判断部１７−１及び総合一致／不一致判断部１７−２は、３つの辞書メモリ１６−１〜１６−３からの検出の有無及び一致／不一致の判断結果から、辞書検索を中止するか継続するかを決める。即ち、全ての辞書メモリ１６−１〜１６−３に検出有りで且つ辞書検索結果が一致と判断した場合には、辞書検索を継続するためインデックスω１をω４に置き換えて、検索続行のフィードバックとして各バイトのハッシュ値発生部１１−１，１１−２，１１−３に供給し、同様の動作を行う。
【００４６】
この検索続行条件が満たされなかった場合には、辞書メモリ１６−１〜１６−３の辞書登録を行う。即ち、全ての辞書メモリ１６−１〜１６−３で検出無しの場合は、辞書メモリ１６−１に対する１文字の登録を行う。また辞書メモリ１６−１で検出有り、辞書メモリ１６−２，１６−３で検出無しの場合には、辞書メモリ１６−２，１６−３に対する２文字目の登録を行う。更に辞書メモリ１６−１，１６−２で検出有り、辞書メモリ１６−３で検出無しの場合には、辞書メモリ１６−３に３文字目の登録を行う。
【００４７】
図７，図８，図９は、図６の１〜３バイトごとのハッシュ値発生部１１−１〜１１−３における複数バイト検索でのハッシュ値の発生法の実施形態である。この実施形態にあっては、インデックスωを１６ビット、各文字Ｋ１，Ｋ２，Ｋ３を各々８ビット、ハッシュ値Ｈを１６ビットとした場合を例にとっている。
図７は１バイト検索の場合であり、レジスタ３２の文字Ｋの８ビットとレジスタ３４のインデックスω１の１６ビットの内の上位８ビットとの排他的論理和ＥＸＯＲをとって１６ビットのハッシュ値Ｈの上位８ビットとし、下位８ビットはレジスタ３４のインデックスω１の下位８ビットをそのまま使う形をとっている。
【００４８】
図８の２バイト検索の場合のハッシュ値の発生は、レジスタ３２−１，３２−２の２文字Ｋ１，Ｋ２の各８ビットとレジスタ３４のインデックスω１の１６ビットの各ビットごとの排他的論理和ＥＸＯＲをとって、１６ビットのハッシュ値Ｈ（ω１，Ｋ１，Ｋ２）を作り出している。
更に図９の３バイト検索に使用するハッシュ値の発生は、レジスタ３２，３６による２文字Ｋ１，Ｋ２の各８ビットに対するレジスタ４０のインデックスω１の１６ビットとの排他的論理和ＥＸＯＲをまずとっている。ここでレジスタ４０におけるインデックスω１の１６ビットのビット配置は、中央に第１０〜１５の６ビットを位置させ、残り第０〜第９ビットを両側に分けて配置している。
【００４９】
更にレジスタ３８に３番目の文字Ｋ３の８ビットをセットし、レジスタ４０の中間の８ビットとの排他的論理和ＥＸＯＲを更にとることで、１６ビットのハッシュ値Ｈ（ω１，Ｋ１，Ｋ２，Ｋ３）を作り出している。このような３バイト検索の場合のハッシュ値の作成は、生成されるハッシュ値の各ビットが均等且つ対称となるようにインデックスω１、文字Ｋ１，Ｋ２，Ｋ３のビットを配置している。
【００５０】
しかし、図９の３バイト検索の場合には、３番目の文字Ｋ３が８ビットでインデックスω１が１６ビットとビット値が異なることから、この場合には排他的論理和の対称となるビットが１６ビットのハッシュ値の上位ビットに反映するようにビット配置を行っている。このようなビット配置により、作成されるハッシュ値の衝突を極力回避することができる。
【００５１】
図１０，図１１，図１２は、図７，図８，図９と同様に、１バイト検索，２バイト検索，３バイト検索のそれぞれについて１２ビットのハッシュ値を作成する場合を例にとっている。即ち、この場合にはインデックスωが１２ビットであり、各文字８ビットから１６ビットのハッシュ値を作成している。
この１２ビットのハッシュ値にあっては、図１０，図１１の１バイト検索，２バイト検索については文字とインデックスのビット数に差があるが、図１２の３バイト検索については３文字Ｋ１，Ｋ２，Ｋ３の組合せで１２ビットのインデックスについて全て３つの排他的論理和ＥＸＯＲとすることができ、１２ビットのハッシュ値の各ビットの均等の対称性を完全に保つことができる。
【００５２】
具体的には、レジスタ４０，４６に文字Ｋ１，Ｋ２を格納すると同時に、文字Ｋ３を上下４ビットずつ分けてレジスタ４４，４６に格納し、各レジスタ４４，４６を１２ビット構成とし、レジスタ４８の１２ビットのインデックスω１にビット数を一致させている。この結果、インデックスと文字Ｋ１，Ｋ２，Ｋ３から３つのビットを対象に、均等且つ対称に配置した１２ビットのハッシュ値Ｈ（ω，Ｋ１，Ｋ２，Ｋ３）を作ることができる。
【００５３】
図１３は、本発明の辞書検索登録方法におけるリハッシュ値の発生方法を実現するブロック図である。即ち、図４及び図５に示したように、本発明の内部ハッシュによる辞書の検索登録にあっては、一致／不一致検出によって不一致が検出された場合にリハッシュ値を発生させて再度、検索を行う。このリハッシュ値を発生させる機能は、図１３に示すハッシュ値発生部２０、辞書検索部２２、一致／不一致検出部２４及びリハッシュ部２６で構成される内部ハッシュ機構で実現される。
【００５４】
図１４は、図１３における内部ハッシュ法によるリハッシュ値の発生処理の概念であり、１バイト検索を例にとっている。即ち、ハッシュ値発生部２０においてインデックスω１と文字Ｋ１からハッシュ関数Ｈ（ω１，Ｋ１）によりハッシュ値を求め、辞書検索部２２で辞書メモリ１６−１を検索し、存在の有無を示すフラグＦ及びインデックスω１´と文字Ｋ１´を読み出す。
【００５５】
続いて一致／不一致検出部２４において、比較部１３−１１でフラグＦ＝０でなく、比較部１３−１２，１３−１３によるインデックスと文字の比較で一致／不一致判断部１５−１２が両者の一致を判断すると、リハッシュ部２６を起動してリハッシュ値ＲＨを生成する。このリハッシュ値ＲＨの生成は、一般形としてはリハッシュ関数ＲＨｍ（Ｈ（ω１，Ｋ１）），ｍ＝１，２，・・・ＮＭＡＸで決まる乱数列からリハッシュアドレスを順に発生する。
【００５６】
図１５は図１４のリハッシュ部２６の具体例であり、ハッシュ値入力部５０、演算部５２及び排他的論理和回路５４で構成される。このリハッシュ部２６の構成にあっては、まず最初のハッシュ値をハッシュ値入力部５０において拡大ガロア体ＧＦ(2**m)の元αと見做す。一方、演算部５２にあっては、予め用意した拡大ガロア体ＧＦ(2**m)の元α1 ，α2 ，α3 ，・・・αmax （但しｍａｘ＝２m −１）を生成する。尚、２＊＊ｍは、２のｍ乗を示す。
【００５７】
そして排他的論理和回路５４において、ハッシュ値入力部５０より出力されるガロア体上の元αと演算部５２より順々に発生される拡大ガロア体上の元αｉの排他的論理和、即ち拡大ガロア体上での和をとって、これをリハッシュ値とする。もちろん、演算部５２における拡大ガロア体上の元の順次発生は、排他的論理和回路５２で作成されたリハッシュ値による辞書の検索で、不一致検出となった場合に繰り返される。
【００５８】
図１６は図１５の演算部５２の具体例である。演算部５２は、拡大ガロア体上の元を順々に発生するもので、拡大ガロア体ＧＦ（２m ）の原始元αを設定するレジスタ５６、拡大ガロア体乗算回路６０、拡大ガロア体の単位元αm-1 を初期値として選択し、その後は拡大ガロア体乗算回路６０の出力を選択する選択回路５８で構成される。
【００５９】
ここで拡大ガロア体としてｍ＝４の４次元の２元ベクトルをもつ場合を例にとると、この場合、拡大ガロア体はＧＦ（２4 ）で表わすことができる。これらの元はαのべき乗で表現される。この場合の元αの数は２4 個＝１６個であり、元は０，α0 ＝１，α1 ，α1 ，・・・α14，α15となる。この元αは原始多項式と呼ばれる式の根から求めることができ、原始元と呼ばれる。
【００６０】
即ち、ガロア体ＧＦ（２4 ）の原始多項式は、
ｆ（ｘ）＝ｘ4 ＋ｘ＋１
で表現することができる。
図１７は、ガロア体ＧＦ（２4 ）におけるｉ＝０〜１５個の元に対する４次元のベクトル表現（Ｘ3 ，Ｘ2 ，Ｘ2 ，Ｘ0 ）とべき乗表現０，α1 〜α5 の関係を表わしている。ｉ＝０は零元と呼ばれ、ｉ＝１〜１４がそれぞれ原始元となり、これはべき乗表現でα1 〜α14で表わされる。更にｉ＝１５は単位元と呼ばれ、べき乗表現でα15となり、これはα0 に等しい。
【００６１】
図１５のハッシュ値入力部５０にあっては、例えばハッシュ値入力が１バイト構成で８ビットであったとすると、４バイト単位に分けたハッシュ値Ｘ3 〜Ｘ0 について、ｉで表現される元の値を、ハッシュ値を拡大ガロア体上の元として出力する。また図１６のレジスタ５６にあっては、拡大ガロア体ＧＦ（２4 ）の開始元α1 をＰとして拡大ガロア体乗算回路６０にセットする。また選択回路５８は、初期値として拡大ガロア体ＧＦ２m の単位元α15を選択してＰＱとして、拡大ガロア体乗算回路６０に出力している。
【００６２】
拡大ガロア体乗算回路６０は図１８に示す論理回路である。即ち、レジスタ５６からの開始元α1 としての入力Ｐと選択回路５８で選択された入力Ｑの各４ビットについて図示の論理演算を行い、最終的にＥＸＯＲにおいて原始多項式ｆ  （ｘ）＝ｘ4 ＋ｘ＋１の剰余を求めて、これを拡大ガロア体上の元を表わす値Ｒとして順々に出力する。
【００６３】
ｍ＝４としたときの拡大ガロア体ＧＦ（２4 ）で発生できるリハッシュ値の最大アドレスは、オールビットが１となったときの原始多項式より
ｆ（２）＝２4 ＋２＋１＝１９
となる。
更に図１８の拡大ガロア体乗算回路６０及び図１５に示した排他的論理和で実現される拡大ガロア体上での加算は、図１９の和の結合表に従って行われる。また図１８の拡大ガロア体乗算回路６０におけるＡＮＤ回路による乗算は、図２０の積の結合表に従って行われる。
【００６４】
本発明におけるリハッシュ値を生成するための拡大ガロア体としては、ｍ＝４以外に更に大きな値をとることができる。図２１は、ｍ＝１２とした拡大ガロア体ＧＦ（２12）における元とリハッシュ値の関係を一部について表わしている。拡大ガロア体ＧＦ（２12）の原始多項式は、
ｆ（ｘ）＝ｘ12＋ｘ6 ＋ｘ4 ＋ｘ＋１
で与えられる。この場合のオールビット１となるときのリハッシュ値の最大アドレスは４１７９である。また図２１のリハッシュ値にあっては、０，１，２，・・・，８，９，ａ，ｂ，・・・，ｅ，ｆの１６進表示としている。
【００６５】
図２２は、ｍ＝１６とした場合の拡大ガロア体ＧＦ（２16）における元とリハッシュ値の関係を一部について示している。拡大ガロア体ＧＦ（２16）における原始多項式は、
ｆ（ｘ）＝ｘ16＋ｘ6 ＋ｘ4 ＋ｘ＋１
で与えられる。このときオールビット１となるリハッシュ値の最大アドレスは６５６１９となる。
【００６６】
以上の実施例は、データ圧縮装置での辞書検索登録方法を例にとるものであったが、このデータ圧縮装置で得られた圧縮データから元の文字列を復元するデータ復元装置についても、同じ辞書の登録方法が適用される。
即ち、本発明の辞書検索登録方法を採用するデータ復元装置は、予め定めた複数文字を入力する毎に、インデックスで表わされた既に検索済みの文字列に続く複数の入力文字から内部ハッシュによってハッシュ値を生成し、このハッシュ値により前記複数の入力文字を対象に前記辞書の検索及び登録を行って得られた圧縮データから文字列を復元する。
【００６７】
このようなデータ復元装置につき本発明の辞書検索登録方法は、入力された符号ωから辞書メモリの検索により文字列を復元する毎に、入力符号ωに続くすでに復元された複数の文字（Ｋ１，Ｋ２，Ｋ３，・・・Ｋｎ）から内部ハッシュによってハッシュ値Ｈ（ω，Ｋ１，Ｋ２，Ｋ３，・・・Ｋｎ）を生成し、このハッシュ値により、複数の復元文字（ω，Ｋ１，Ｋ２，Ｋ３，・・・Ｋｎ）を対象に辞書の登録を行う。
【００６８】
この複数文字単位の復元については、図２〜図１２の圧縮時と同じ辞書の登録方法がそのまま適用される。
またデータ復元時のリハッシュによる辞書の再登録として、本発明の辞書検索登録方法は、入力された符号ωから辞書の検索により文字列を復元する毎に、入力符号に続くすでに復元された複数の文字（Ｋ１，Ｋ２，Ｋ３，・・・Ｋｎ）から内部ハッシュによってハッシュ値Ｈ（ω，Ｋ１，Ｋ２，Ｋ３，・・・Ｋｎ）を生成し、このハッシュ値により、複数の復元文字を対象に辞書の登録を行った際に、既に同じハッシュ値を使用した辞書の登録済みを検出した場合に、最初のハッシュ値に対応した乱数列を順に発生して再度辞書に登録する。
【００６９】
このリハッシュ処理についても、図１３〜図２２の圧縮時と同じ辞書の登録方法がそのまま適用される。
尚、上記の実施例は、辞書検索の具体的方法として内部ハッシュによるデータ構造を例にとるものであったが、本発明はこれに限定されず、外部ハッシュによるリスト構造についても適用することができる。
【００７０】
【発明の効果】
以上説明してきたように本発明によれば、ＬＺＷ等のデータ圧縮装置及び復元装置における辞書の検索と登録において、複数文字を一度に検索し登録できるので、圧縮及び復元処理をより一層高速化することができる。
また辞書検索結果が不一致の場合のリハッシュ値の発生に拡大ガロア体の元を用いることで、最初のハッシュ値に対し全く異なるリハッシュ値を発生することができ、これによって内部ハッシュの衝突を可能な限り回避することができる。
【図面の簡単な説明】
【図１】本発明の原理説明図
【図２】本発明の辞書検索登録方法を実現するデータ圧縮装置のブロック図
【図３】図２の内部ハッシュ法による辞書検索登録の処理説明図
【図４】文字数ｎにおける内部ハッシュ法による辞書検索登録の並列処理のブロック図
【図５】本発明によるＬＺＷ符号の検索と登録の辞書範囲を示す木構造の説明図
【図６】内部ハッシュ法により３バイト一括検索を行う本発明の辞書検索登録のブロック図
【図７】１バイト検索の１６ビットハッシュ値を作るハッシュ値生成部のブロック図
【図８】２バイト検索の１６ビットハッシュ値を作るハッシュ値生成部のブロック図
【図９】３バイト検索の１６ビットハッシュ値を作るハッシュ値生成部のブロック図
【図１０】１バイト検索の１２ビットハッシュ値を作るハッシュ値生成部のブロック図
【図１１】２バイト検索の１２ビットハッシュ値を作るハッシュ値生成部のブロック図
【図１２】３バイト検索の１２ビットハッシュ値を作るハッシュ値生成部のブロック図
【図１３】リハッシュ部を備えた本発明の辞書検索登録方法を実現するデータ圧縮装置のブロック図
【図１４】図１３のリハッシュ値の発生処理の説明図
【図１５】図１３のリハッシュ部の具体的なブロック図
【図１６】拡大ガロア体の元を順々に発生する図１５の演算部のブロック図
【図１７】拡大ガロア体ＧＦ（２4 ）の元とリハッシュ値の対応関係の説明図
【図１８】図１６の拡大ガロア体乗算回路の論理回路図
【図１９】拡大ガロア体ＧＦ（２4 ）の加算で使用する和の結合表の説明図
【図２０】拡大ガロア体ＧＦ（２4 ）の乗算で使用する積の結合表の説明図
【図２１】拡大ガロア体ＧＦ（２12）の元とリハッシュ値の対応関係の説明図
【図２２】拡大ガロア体ＧＦ（２16）の元とリハッシュ値の対応関係の説明図
【図２３】従来のＬＺＷ符号における辞書の木構造の説明図
【図２４】ＬＺＷ符号における文字列の符号化の説明図
【図２５】ＬＺＷ符号化の具体例の説明図
【図２６】図２５の符号化で使用する辞書の説明図
【図２７】ＬＺＷ符号化アルゴリズムのフローチャート
【図２８】ＬＺＷ復号化の具体例の説明図
【図２９】ＬＺＷ復号化アルゴリズムのフローチャート
【図３０】従来の内部ハッシュ法による辞書検索と登録のブロック図
【図３１】従来の内部ハッシュ法による辞書検索と登録の処理説明図
【符号の説明】
１０：複数入力検索部
１０−１〜１０−ｎ：１〜ｎバイト検索部
１１−１〜１１−３：ハッシュ値発生部
１３−１１〜１３−３４：比較部
１２−１〜１２−ｎ：一致／不一致検出部
１２：複数入力一致検出部
１４：複数入力登録部
１５−１１，１５−２１，１５−３１：検出無判断部
１６，１６−１〜１６−３：辞書メモリ（辞書）
１７−１：総合検出無判断部
１７−２，３０：総合一致／不一致判断部
２０：ハッシュ値発生部
２２：辞書検索部
２４：一致／不一致検出部
２６：リハッシュ部
３０：総合一致／不一致判断部
32,32-1,32-2,34,36,38,40,42,44,46,48：レジスタ
５０：ハッシュ値入力部
５２：乱数列発生部
５４：排他的論理和回路
５６：レジスタ
５８：選択回路
６０：拡大ガロア体乗算回路
【図１】
0003835489.tif 000002
【図２】
0003835489.tif 000003
【図３】
0003835489.tif 000004
【図４】
0003835489.tif 000005
【図５】
0003835489.tif 000006
【図６】
0003835489.tif 000007
【図７】
0003835489.tif 000008
【図８】
0003835489.tif 000009
【図９】
0003835489.tif 000010
【図１０】
0003835489.tif 000011
【図１１】
0003835489.tif 000012
【図１２】
0003835489.tif 000013
【図１３】
0003835489.tif 000014
【図１４】
0003835489.tif 000015
【図１５】
0003835489.tif 000016
【図１６】
0003835489.tif 000017
【図１７】
0003835489.tif 000018
【図１８】
0003835489.tif 000019
【図１９】
0003835489.tif 000020
【図２０】
0003835489.tif 000021
【図２１】
0003835489.tif 000022
【図２２】
0003835489.tif 000023
【図２３】
0003835489.tif 000024
【図２４】
0003835489.tif 000025
【図２５】
0003835489.tif 000026
【図２６】
0003835489.tif 000027
【図２７】
0003835489.tif 000028
【図２８】
0003835489.tif 000029
【図２９】
0003835489.tif 000030
【図３０】
0003835489.tif 000031
【図３１】
0003835489.tif 000032