データ圧縮装置、データ伸長装置、データ圧縮プログラム、及びデータ伸長プログラム
【課題】ブロックストリーム処理においてテキストデータの圧縮率を向上させる。
【解決手段】テキストデータの入力を受け付け、テキストデータを複数のブロックに分割するデータ取得部１１０と、文字列と符号とが対応付けられて格納された基準辞書に基づき、処理対象ブロックに出現する文字列のうち、基準辞書に登録されていない文字列と、基準辞書において処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた差分辞書を生成する差分辞書生成部１１２と、作成した差分辞書と基準辞書とに基づき、処理対象辞書を生成する辞書作成部１１１と、生成した処理対象辞書を参照し、処理対象ブロックに出現する文字列を対応する符号に置き換えることで、処理対象ブロックを圧縮する符号化部１１３と、符号化部１１３が圧縮した処理対象ブロックのデータと、生成した差分辞書とを出力する出力部１１４と、を備える。
【解決手段】テキストデータの入力を受け付け、テキストデータを複数のブロックに分割するデータ取得部１１０と、文字列と符号とが対応付けられて格納された基準辞書に基づき、処理対象ブロックに出現する文字列のうち、基準辞書に登録されていない文字列と、基準辞書において処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた差分辞書を生成する差分辞書生成部１１２と、作成した差分辞書と基準辞書とに基づき、処理対象辞書を生成する辞書作成部１１１と、生成した処理対象辞書を参照し、処理対象ブロックに出現する文字列を対応する符号に置き換えることで、処理対象ブロックを圧縮する符号化部１１３と、符号化部１１３が圧縮した処理対象ブロックのデータと、生成した差分辞書とを出力する出力部１１４と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ圧縮装置、データ伸長装置、データ圧縮プログラム、及びデータ伸長プログラムに関する。
【背景技術】
【０００２】
テキストデータ（プレーンなテキスト形式のデータや、ＣＳＶ（Comma Separated Values）形式のデータ、ＸＭＬ（eXtensible Markup Language）データ等）を圧縮する方法として、辞書型符号化方式が知られている。辞書型符号化方式は、圧縮対象のデータ列中に出現する文字や文字列にそれぞれ所定の番号（符号）を割り当てて辞書を作成しておき、この辞書に基づいて実際の入力文字の符号化を行う。辞書式符号化方式には、辞書の保存が必要な静的辞書式符号化（ＢＰＥ(Byte Pair Encoding)やＳＴＶＦ(Suffix-Tree based VF coding) 等）と、辞書の保存が不要な動的辞書式符号化（ＬＺ７７やＬＺ７８等）がある。データベースから出力されたデータなど、重複した値文字列を多く含むようなデータでは、静的辞書式符号化を適用してから、さらに動的辞書式符号化を適用することで、動的辞書式符号化のみの適用より圧縮率が向上することが知られている。また、静的辞書式符号化は、圧縮データを伸長することなくパターン検索するのに適した方式であることも知られている。
【０００３】
また、入力データを適当な大きさに分割したブロックを逐次処理（ストリーム処理）するブロックストリーム処理が知られている。多くの静的辞書式符号化方式は、辞書作成と符号化の２パスで符号化を行うため、逐次処理を行うことができないが、ブロックストリーム処理を適用することで、限られた計算領域しか用いずに、逐次処理を行うことができる。また、ブロックストリーム処理は、より細かい単位でのストリーム処理（文字ストリーム処理や単語ストリーム処理）に比べて、より軽量なインデックスを用いたフィルタリングを行える、等の利点がある。
【０００４】
そこで、ブロックストリーム処理において圧縮率を向上させる圧縮・伸長アルゴリズムが提案されている（例えば、特許文献１）。また、単語ストリーム処理において、辞書を使用してデータを圧縮する技術も提案されている（例えば、特許文献２）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平９−２１４３５３号公報
【特許文献２】特開平１１−１６８３９０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、ブロックストリーム処理を用いて入力データの辞書式符号化を行う場合に、上記特許文献１および２の技術では、次の問題がある。特許文献１の技術では、各ブロックにおける辞書サイズの削減について考慮していないため、十分な圧縮率を得られない恐れがある。特許文献２の技術は、単語ストリーム処理を行っているので、ブロックストリーム処理に特有の利点を失ってしまう。また、特許文献２の技術をブロックストリーム処理に自然に拡張することは可能だが、その場合、各ブロックの辞書の増大により、やはり十分な圧縮率が得られない恐れがある。
【０００７】
本件は、上記の事情に鑑みて成されたものであり、ブロックストリーム処理において、テキストデータの圧縮率を向上させるデータ圧縮装置、データ伸長装置、データ圧縮プログラム、及びデータ伸長プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、明細書開示のデータ圧縮装置は、テキストデータの入力を受け付ける入力部と、前記テキストデータを所定の規則に基づき複数のブロックに分割する分割部と、文字列と符号とが対応付けられて格納された辞書データである基準辞書に基づき、処理対象ブロックに出現する文字列のうち、該基準辞書に登録されていない文字列と、該基準辞書において前記処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書を生成する差分辞書生成部と、前記作成した差分辞書と前記基準辞書とに基づき、辞書データである処理対象辞書を生成する処理対象辞書生成部と、前記生成した処理対象辞書を参照し、前記処理対象ブロックに出現する文字列を対応する符号に置き換えることで、該処理対象ブロックを圧縮する圧縮部と、前記圧縮部が圧縮した前記処理対象ブロックのデータと、前記生成した差分辞書とを出力する出力部と、を備える。
【０００９】
また、上記課題を解決するために、明細書開示のデータ伸長装置は、処理対象ブロック毎に、文字列と符号とが対応付けられて格納された辞書データである基準辞書に基づき、該処理対象ブロックに出現する文字列のうちで該基準辞書に登録されていない文字列と該基準辞書において前記処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書と、符号列である圧縮データとの入力を受け付ける入力部と、前記圧縮データを所定の規則に基づき複数のブロックに分割する分割部と、処理対象ブロック毎に、前記受け付けた基準辞書と該処理対象ブロックの差分辞書とに基づき、辞書データである処理対象辞書を生成する処理対象辞書生成部と、処理対象ブロック毎に、前記生成した処理対象辞書に基づいて、該処理対象ブロックを復号する復号部と、を備える。
【００１０】
また、上記課題を解決するために、明細書開示のデータ圧縮プログラムは、コンピュータに、テキストデータの入力を受け付ける入力ステップと、前記テキストデータを所定の規則に基づき複数のブロックに分割する分割ステップと、文字列と符号とが対応付けられて格納された辞書データである基準辞書に基づき、処理対象ブロックに出現する文字列のうち、該基準辞書に登録されていない文字列と、該基準辞書において前記処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書を生成する差分辞書生成ステップと、前記作成した差分辞書と前記基準辞書とに基づき、辞書データである処理対象辞書を生成する処理対象辞書生成ステップと、前記生成した処理対象辞書を参照し、前記処理対象ブロックに出現する文字列を対応する符号に置き換えることで、該処理対象ブロックを圧縮する圧縮ステップと、前記圧縮部が圧縮した前記処理対象ブロックのデータと、前記生成した差分辞書とを出力する出力ステップと、を実行させる。
【００１１】
上記課題を解決するために、明細書開示のデータ伸長プログラムは、コンピュータに、処理対象ブロック毎に、文字列と符号とが対応付けられて格納された辞書データである基準辞書に基づき、該処理対象ブロックに出現する文字列のうちで該基準辞書に登録されていない文字列と該基準辞書において前記処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書と、符号列である圧縮データとの入力を受け付ける入力ステップと、前記圧縮データを所定の規則に基づき複数のブロックに分割する分割ステップと、処理対象ブロック毎に、前記受け付けた基準辞書と該処理対象ブロックの差分辞書とに基づき、辞書データである処理対象辞書を生成する処理対象辞書生成ステップと、処理対象ブロック毎に、前記生成した処理対象辞書に基づいて、該処理対象ブロックを復号する復号ステップと、を実行させる。
【発明の効果】
【００１２】
明細書開示のデータ圧縮装置、及びデータ圧縮プログラムによれば、ブロックストリーム処理において、テキストデータの圧縮率を向上できる。
【００１３】
明細書開示のデータ伸長装置、及びデータ伸長プログラムによれば、ブロックストリーム処理において、テキストデータの圧縮率を向上させた圧縮データを、伸長できる。
【図面の簡単な説明】
【００１４】
【図１】実施例に係るデータ圧縮装置を含むシステム構成の一例を示す図である。
【図２】データ圧縮装置のハードウェア構成の一例を示す図である。
【図３】データ圧縮装置が有する機能を実現する手段の一例を示す機能ブロック図である。
【図４】辞書型符号化方式の概要を説明する図である。
【図５】データ圧縮装置が実行するデータ圧縮処理の一例を示すフローチャートである。
【図６】辞書更新処理の一例を示すフローチャートである。
【図７】被圧縮データの一例を示す図である。
【図８】圧縮データを作成する過程の一例を説明するための図である。
【図９】差分辞書作成処理の一例を示すフローチャートである。
【図１０】圧縮データを作成する過程の一例を説明するための図である。
【図１１】圧縮データを作成する過程の一例を説明するための図である。
【図１２】圧縮データを作成する過程の一例を説明するための図である。
【図１３】圧縮データを作成する過程の一例を説明するための図である。
【図１４】圧縮データを作成する過程の一例を説明するための図である。
【図１５】圧縮データを作成する過程の一例を説明するための図である。
【図１６】圧縮データを作成する過程の一例を説明するための図である。
【図１７】圧縮データの一例を示す図である。
【図１８】比較例１、比較例２及び実施例により作成される圧縮データの一例を説明するための図である。
【図１９】比較例１、比較例２及び実施例により作成される圧縮データの一例を説明するための図である。
【図２０】比較例１、比較例２、及び実施例による圧縮データのサイズ比較の一例を示す模式図である。
【図２１】実施例に係るデータ伸長装置を含むシステム構成の一例を示す図である。
【図２２】データ伸長装置が有する機能を実現する手段の一例を示す機能ブロック図である。
【図２３】データ伸長処理の一例を示すフローチャートである。
【図２４】圧縮データを伸長する過程の一例を説明するための図である。
【図２５】辞書復元処理の一例を示すフローチャートである。
【図２６】圧縮データを伸長する過程の一例を説明するための図である。
【図２７】圧縮データを伸長する過程の一例を説明するための図である。
【図２８】データ圧縮／伸長装置を含むシステム構成の一例を示す図である。
【発明を実施するための形態】
【００１５】
以下、本件の実施形態について、添付図面を参照しつつ説明する。
［データ圧縮装置］
【００１６】
本件のデータ圧縮装置について説明する。図１は本件のデータ圧縮装置を含むシステム構成の一例を示す図である。図１に示すように、データ圧縮装置１００は、ネットワーク４０を介して、記憶装置１０、センサ装置２０、及びデータ処理装置３０と接続されている。
【００１７】
記憶装置１０は、ハードディスクドライブ等で構成され、圧縮対象のデータ（以後、被圧縮データと記載する）、及び圧縮後のデータを格納する。
【００１８】
センサ装置２０は、例えば、企業の従業員出入り口に設置される入退出管理装置である。センサ装置２０は、センサにより取得したデータをデータ圧縮装置１００へ送信する。例えば、センサ装置２０は、従業員が所持するＩＤカードの情報を取得して、従業員番号、氏名、及び勤務地を被圧縮データとしてデータ圧縮装置１００へ送信する。センサ装置２０は、センサと、センサが取得したデータを処理する情報処理装置とからなるセンサネットワークであっても良い。
【００１９】
データ処理装置３０は、パーソナルコンピュータ等で構成され、入力されたデータに対し、演算等の予め定められたデータ処理を行う。データ処理装置３０は、予め定められた処理を施したデータを被圧縮データとして、データ圧縮装置１００へ送信する。また、データ処理装置３０は、データ圧縮装置１００から、データ圧縮装置１００が圧縮したデータを受け付ける。
【００２０】
ネットワーク４０は、例えば、ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等で構成される。ネットワーク４０は、センサ装置２０、データ処理装置３０、及びデータ圧縮装置１００が送信するデータを、送信先に伝送する。
【００２１】
データ圧縮装置１００は、記憶装置１０、センサ装置２０、及びデータ処理装置３０から被圧縮データを受信する。被圧縮データは、ＣＳＶ形式、ＸＭＬ形式等の構造を有するテキストデータである。データ圧縮装置１００は、被圧縮データを複数のブロックに分割し、ブロック毎に圧縮処理を実行して圧縮データを生成する。データ圧縮装置１００は、圧縮データを記憶装置１０へ格納する。または、データ圧縮装置１００は、圧縮データをデータ処理装置３０へ送信する。
【００２２】
次に、図２を用いてデータ圧縮装置１００のハードウェア構成について説明する。図２に示すように、データ圧縮装置１００は、入出力部１０１、ＲＯＭ(Read Only Memory)１０２、中央処理装置（ＣＰＵ:Central Processing Unit）１０３、及びＲＡＭ(Random Access Memory)１０４を備える。
【００２３】
入出力部１０１は、記憶装置１０、センサ装置２０、及びデータ処理装置３０から被圧縮データを受け付ける。また、入出力部１０１は、圧縮データを記憶装置１０、及びデータ処理装置３０へ出力する。ＲＯＭ１０２は、被圧縮データを圧縮するためのプログラム等を格納する。ＣＰＵ１０３は、ＲＯＭ１０２に格納されたプログラムを読み込んで実行する。ＲＡＭ１０４は、プログラムを実行する際に使用される一時的なデータを保存する。また、ＲＯＭ１０２に格納されたプログラムのＣＰＵ１０３による演算によって、図３に示すデータ圧縮装置１００が有する機能が実現される。
【００２４】
次に、図３を参照して、データ圧縮装置１００が有する機能の一例について説明する。図３は、データ圧縮装置１００が有する機能を実現する手段の一例を示す機能ブロック図である。
【００２５】
データ圧縮装置１００は、データ取得部１１０、辞書作成部１１１、差分辞書作成部１１２、符号化部１１３、及び出力部１１４を備える。
【００２６】
データ取得部１１０は、記憶装置１０、センサ装置２０、及びデータ処理装置３０等が送信した被圧縮データ（テキストデータ）を受け付ける入力部としての機能と、被圧縮データを所定の規則に基づき複数のブロックに分割する分割部としての機能を有する。データ取得部１１０は、分割した被圧縮データを、辞書作成部１１１に出力する。
【００２７】
辞書作成部１１１（処理対象辞書生成部）は、被圧縮データを所定の規則に基づき分割した複数ブロックのうち、圧縮処の対象となるブロック（以後、処理対象ブロックという）のデータを符号化する際に必要な辞書を、データ取得部１１０から入力されたデータを元に作成する。辞書は、符号項目と、値項目とを有しており、辞書作成部１１１は、処理対象ブロックのデータに出現する文字列を値項目に登録し、文字列に対応付けられる所定の符号を符号項目に登録する。例えば、入力データが図４（１）に示すデータであり、符号化する項目が「地区」の場合、辞書作成部１１１は、地区の列に出現する文字列と、所定の符号とを対応付けた、図４（２）に示す辞書を作成する。
【００２８】
符号化部１１３（圧縮部）は、ブロック毎に、辞書作成部１１１が作成した辞書を用いて、データを符号化し、出力部１１４に出力する。例えば、符号化部１１３は、図４（２）に示した辞書を用いて、図４（１）の「地区」の文字列を符号に置換することによって被圧縮データを符号化する。符号化されたデータは、図４（３）となる。
【００２９】
差分辞書作成部１１２（差分辞書生成部）は、差分辞書を作成し、出力部１１４へ出力する。差分辞書作成部１１２は、処理対象ブロックとは異なる基準ブロックの符号化に用いた辞書と、処理対象ブロックに含まれる符号化対象の文字列とに基づいて差分辞書を作成する。差分辞書は、符号化に使用される辞書と同様に、符号項目と値項目とを有する。差分辞書作成部１１２は、処理対象ブロックに出現する文字列のうち、基準ブロックの符号化に用いた辞書に登録されていない文字列を差分辞書の値項目に登録する。また、差分辞書作成部１１２は、差分辞書に登録した文字列に対して、基準ブロックの辞書において、基準ブロックの辞書には登録されているが処理対象ブロックには出現しない文字列に対応付けられている符号を割り当てる。例えば、基準ブロックの辞書が図４（４）であり、処理対象ブロックに含まれる符号化対象の文字列が図４（５）であるとする。この場合、差分辞書作成部１１２は、処理対象ブロックには出現するが基準ブロックの辞書には登録されていない文字列「Ｎｅｗ Ｙｏｒｋ」を差分辞書に登録する。また、差分辞書作成部１１２は、処理対象ブロックには出現しないが基準ブロックには登録されている文字列「Ｌａｓ Ｖｅｇａｓ」に割り当てられている符号「３」を、差分辞書に登録した文字列「Ｎｅｗ Ｙｏｒｋ」に対して割り当てる。その結果、差分辞書は図４（６）となる。
【００３０】
出力部１１４は、差分辞書と符号化されたデータとを、ブロック毎に、記憶装置１０、又は、データ処理装置３０に出力する。
【００３１】
次に、データ圧縮装置１００が実行する処理の一例について、図５及び図６を用いて説明する。図５は、データ圧縮装置１００が実行する圧縮処理の一例を示すフローチャートである。本実施例では、連続する２つのブロックにおける前方のブロックを基準ブロックと記載し、後方のブロックを処理対象ブロックと記載する。
【００３２】
辞書作成部１１１は、基準ブロックの辞書Ｄｉｃ０を空テーブルで初期化する（ステップＳ１０）。これは、被圧縮データの最初のブロックが処理対象ブロックである場合、基準ブロックが存在しないためである。
【００３３】
次に、辞書作成部１１１は、処理対象ブロックの符号化に使用する辞書（処理対象辞書）Ｄｉｃ１、及び読み込んだレコード数をカウントするための変数Ｍをそれぞれ初期化する（ステップＳ１２）。初期化によって、辞書Ｄｉｃ１は空テーブルとなり、Ｍの値は０となる。
【００３４】
データ取得部１１０は、被圧縮データに処理するレコードが存在するか否か判定する（ステップＳ１４）。データ取得部１１０は、処理するレコードが存在する場合（ステップＳ１４／ＹＥＳ）、レコードを取得し、Ｍに１を加算する（ステップＳ１６）。
【００３５】
次に、辞書作成部１１１は、処理対象ブロックの辞書を作成するため、辞書更新処理を実行する（ステップＳ１８）。ここで、ステップＳ１８の辞書更新処理について、図６を用いて説明する。
【００３６】
図６は、処理対象ブロックの辞書を作成する辞書更新処理の一例を示すフローチャートである。
【００３７】
辞書作成部１１１は、取得したレコードに含まれる文字列が辞書Ｄｉｃ１のエントリに存在するか否か判定する（ステップＳ５０）。辞書作成部１１１は、取得したレコードに含まれる文字列が辞書Ｄｉｃ１のエントリに存在しない場合（ステップＳ５０／ＮＯ）、文字列と符号とを対応付けたエントリを辞書Ｄｉｃ１に新規登録し（ステップＳ５２）、更新処理を終了する。一方、辞書作成部１１１は、取得したレコードに含まれる文字列が辞書Ｄｉｃ１のエントリに存在する場合、更新処理を終了する。
【００３８】
図５に戻り、圧縮処理の一例について説明を続ける。データ取得部１１０は、Ｍの値が、予め定められた値ＭＢよりも小さいか否か判定する（ステップＳ２０）。ここで、ＭＢは、１ブロックに含まれるレコード数を定める。ＭＢの値は、被圧縮データが保持していても良いし、ユーザが予め決定しておいても良い。また、ＭＢの値は、全ブロックを通して同一でも良いし、ブロック毎に異なっても良い。
【００３９】
Ｍの値がＭＢの値よりも小さい場合、処理対象ブロックのレコードが、未だ全て読み込まれていないことを意味する。従って、データ取得部１１０は、Ｍの値がＭＢの値よりも小さい場合（ステップＳ２０／ＹＥＳ）、ステップＳ１４に戻って処理を継続する。
【００４０】
Ｍの値がＭＢの値と等しい場合、処理対象ブロックのレコードが全て読みこまれたことを意味する。そこで、データ取得部１１０が、Ｍの値がＭＢの値と等しいと判定すると（ステップＳ２０／ＮＯ）、差分辞書作成部１１２は、差分辞書作成処理（ステップＳ２２）を実行する。差分辞書作成処理の詳細については後述する。
【００４１】
出力部１１４は、差分辞書作成部１１２が差分辞書作成処理で作成した差分辞書Δを出力する（ステップＳ２４）。次に、辞書作成部１１１は、基準ブロックの辞書Ｄｉｃ０と差分辞書Δとをマージして符号化用の辞書を構築し、それを新たな辞書Ｄｉｃ１とする（ステップＳ２６）。具体的には、辞書Ｄｉｃ０と差分辞書Δとの間で重複する符号がある場合には、重複する符号に対応付けられた辞書Ｄｉｃ０の文字列を、差分辞書Δの文字列で置換する。また、辞書Ｄｉｃ０に登録されていない符号が差分辞書Δに登録されている場合には、辞書Ｄｉｃ０に差分辞書Δのエントリを追加する。つまり、符号化部１１３が使用する辞書Ｄｉｃ１は、処理対象ブロックに出現する文字列のうち、基準ブロックで使用された辞書に定義されている文字列には、基準ブロックの辞書と同一の符号が割り当てられた辞書となる。また、辞書Ｄｉｃ１は、基準ブロックの辞書に登録されていない文字列には、基準ブロックの辞書において処理対象ブロックに出現しない文字列に対応付けられた符号が割り当てられた辞書となる。
【００４２】
符号化部１１３は、ステップＳ２６で更新された辞書Ｄｉｃ１を使用して、処理対象ブロックに出現する文字列を符号化する（ステップＳ２８）。出力部１１４は、符号化部１１３が符号化したデータを出力する（ステップＳ３０）。ステップＳ２４及びステップＳ３０の処理によって、処理対象ブロックの圧縮データが作成される。
【００４３】
辞書作成部１１１は、次ブロックの圧縮処理のために、辞書Ｄｉｃ０を初期化し（ステップＳ３２）、ステップＳ１２の処理へ戻る。本フローチャートでは、連続する２つのブロックのうち、前方のブロックを基準ブロック、後方のブロックを処理対象ブロックとしている。従って、今回処理したブロックは次に処理するブロックの基準ブロックとなるので、辞書Ｄｉｃ０は、辞書Ｄｉｃ１で初期化される。
【００４４】
データ取得部１１０は、処理するレコードが存在しない場合（ステップＳ１４／ＮＯ）、Ｍの値が０か否か判定する（ステップＳ３４）。
【００４５】
Ｍの値が０の場合とは、次のブロックが存在しない場合である。従って、データ取得部１１０はＭの値が０の場合（ステップＳ３４／ＹＥＳ）、データ圧縮処理を終了する。
【００４６】
Ｍの値が０ではない場合とは、最後の処理対象ブロックに存在するデータの読込が全て終了した場合である。そこで、データ取得部１１０が、Ｍの値が０ではないと判定すると（ステップＳ３４／ＮＯ）、差分辞書作成部１１２はステップＳ２２、出力部１１４はステップＳ２４及びステップＳ３０、符号化部１１３はステップＳ２８、辞書作成部１１１はステップＳ２６の処理をそれぞれ実行する。ステップＳ２２〜ステップＳ３０の処理は、前述した各ステップの処理と同じであるため、説明を省略する。以上の処理により、被圧縮データは、ブロック毎に差分辞書と符号化データを含んで圧縮される。
【００４７】
次に、図７〜図１７を参照しつつ、具体的なデータを用いて、上述した圧縮処理によるデータ圧縮について説明すると共に、差分辞書作成処理の詳細について説明する。図７は、本説明で用いる被圧縮データの一例である。本実施例では、地区項目に入力されている文字列を符号化した圧縮データを作成するとする。また、３レコード（つまり、ＭＢ＝３）を１ブロックとして、ブロックストリーム処理によりデータを圧縮するものとする。
【００４８】
データ圧縮装置１００は、図５のステップＳ１０及びＳ１２の初期化処理を行う。次に、処理対象となるレコードが存在するため（ステップＳ１４／ＹＥＳ）、データ取得部１１０が、図８（１）に示す１行目のレコードを取得する（ステップＳ１６）。
【００４９】
次に、辞書作成部１１１が、辞書Ｄｉｃ１の更新処理（ステップＳ１８）を実行する。この時点で辞書Ｄｉｃ１は空テーブルであるため、辞書Ｄｉｃ１において、Ｓａｎ Ｆｒａｎｃｉｓｃｏを値項目に有するエントリは存在しない（ステップＳ５０／ＮＯ）。従って、辞書作成部１１１は、Ｓａｎ Ｆｒａｎｃｉｓｃｏに符号「１」を割り当てたエントリを辞書Ｄｉｃ１に新規登録し（ステップＳ５２）、処理を終了する。更新後の辞書Ｄｉｃ１は図８（２）となる。
【００５０】
Ｍ（＝１）＜ＭＢ（＝３）であり（ステップＳ２０／ＹＥＳ）、次のレコードが存在するため（ステップＳ１４／ＹＥＳ）、データ取得部１１０は、図８（３）に示す２行目のレコードを取得する（ステップＳ１６）。
【００５１】
図６の辞書更新処理において、Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．は、辞書Ｄｉｃ１に存在しないため（ステップＳ５０／ＮＯ）、辞書作成部１１１は、Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．に符号「２」を割り当てたエントリを辞書Ｄｉｃ１に新規登録し（ステップＳ５２）、処理を終了する。更新後の辞書Ｄｉｃ１は、図８（４）となる。
【００５２】
Ｍ（＝２）＜ＭＢ（＝３）であり（ステップＳ２０／ＹＥＳ）、次のレコードが存在するため（ステップＳ１４／ＹＥＳ）、データ取得部１１０は、図８（５）に示す３行目のレコードを入力する。
【００５３】
図６の辞書更新処理において、Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．は、既に辞書Ｄｉｃ１に存在しているため（ステップＳ５０／ＹＥＳ）、辞書作成部１１１は、辞書Ｄｉｃ１にエントリは新規登録せず、処理を終了する。
【００５４】
Ｍ（＝３）がＭＢ（＝３）と一致するため（ステップＳ２０／ＮＯ）、差分辞書作成部１１２が、差分辞書作成処理（ステップＳ２２）を実行する。
【００５５】
ここで、具体例を用いながら、差分辞書作成処理について説明する。図９は、差分辞書作成処理の一例を示すフローチャートである。
【００５６】
差分辞書作成部１１２は、差分辞書Δを基準ブロックの辞書Ｄｉｃ０で初期化する（ステップＳ６０）。なお、最初のブロックでは、辞書Ｄｉｃ０は空集合となっているため、差分辞書Δも空集合となる。
【００５７】
次に、差分辞書作成部１１２は、基準ブロックの辞書Ｄｉｃ０の値項目の集合と、更新処理を実行した辞書Ｄｉｃ１の値項目の集合との差集合Ｄｉｆｆ０を求める（ステップＳ６２）。図９では、辞書Ｄｉｃ０の値項目の集合をＤｉｃ０．ｖａｌ、辞書Ｄｉｃ１の値項目の集合を辞書Ｄｉｃ１．ｖａｌと記載する。
【００５８】
次に、差分辞書作成部１１２は、辞書Ｄｉｃ１の値項目の集合と、辞書Ｄｉｃ１の値項目の集合との差集合Ｄｉｆｆ１を求める（ステップＳ６４）。更に、差分辞書作成部１１２は辞書Ｄｉｃ１の値項目の集合と、辞書Ｄｉｃ０の値項目の集合との積集合ＮｏＤｉｆｆを求める（ステップＳ６６）。
【００５９】
図８に示した具体例において、辞書Ｄｉｃ０の値項目の集合Ｄｉｃ０．ｖａｌは空集合であり、辞書Ｄｉｃ１の値項目の集合Ｄｉｃ１．ｖａｌ＝｛Ｓａｎ Ｆｒａｎｃｉｓｃｏ，Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．｝である。この場合、辞書Ｄｉｃ０には存在するが辞書Ｄｉｃ１には存在しない値項目は、存在しない。従って、ステップＳ６２の処理を実行すると、差集合Ｄｉｆｆ０は空集合となる。また、辞書Ｄｉｃ０には存在しないが辞書Ｄｉｃ１には存在する値項目は、Ｓａｎ Ｆｒａｎｃｉｓｃｏ及びＷａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．である。従って、ステップＳ６４の処理を実行すると、差集合Ｄｉｆｆ１＝｛Ｓａｎ Ｆｒａｎｃｉｓｃｏ，Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．｝となる。更に、辞書Ｄｉｃ０と、辞書Ｄｉｃ１との間に共通する値項目は存在しないため、ステップＳ６６の処理を実行すると、積集合ＮｏＤｉｆｆは空集合となる。
【００６０】
次に、差分辞書作成部１１２は、Ｄｉｆｆ１が空集合か否か判定する（ステップＳ６８）。差分辞書作成部１１２は、Ｄｉｆｆ１が空集合ではない場合（ステップＳ６８／ＮＯ）、差分辞書作成部１１２は、Ｄｉｆｆ０が空集合か否か判定する（ステップＳ７０）。
【００６１】
差分辞書作成部１１２は、Ｄｉｆｆ０が空集合の場合（ステップＳ７０／ＹＥＳ）、Ｄｉｆｆ１の全ての要素を差分辞書Δに新規登録する（ステップＳ７６）。そして、差分辞書作成部１１２は、ＮｏＤｉｆｆの要素と一致する値を持つエントリを差分辞書Δから全て除去し（ステップＳ７８）、差分辞書Δを辞書作成部１１１及び出力部１１４に出力する（ステップＳ８０）。
【００６２】
具体例では、Ｄｉｆｆ１は空集合ではなく（ステップＳ６８／ＮＯ）、Ｄｉｆｆ０は空集合である（ステップＳ７０／ＹＥＳ）。したがって、差分辞書作成部１１２は、ステップＳ７６の処理を実行する。ステップＳ７６の処理実行後の差分辞書Δは図１０（１）となる。また、具体例において、ＮｏＤｉｆｆは空集合であるため、ステップＳ７８において、差分辞書Δから除去するエントリは存在しない。従って、差分辞書作成部１１２は、ステップＳ８０の処理を実行し、図１０（１）に示す差分辞書Δを辞書作成部１１１及び出力部１１４に出力する。図９の差分辞書作成処理における他のステップについては、後述する。
【００６３】
差分辞書作成処理が終了すると、出力部１１４が差分辞書Δを圧縮データの一部として出力する（ステップＳ２４）。次に、辞書作成部１１１は、辞書Ｄｉｃ０と差分辞書Δとに基づいて、辞書Ｄｉｃ１を更新する（ステップＳ２６）。今回は、辞書Ｄｉｃ０が空集合であるため、差分辞書Δのエントリが辞書Ｄｉｃ０に追加され、符号化に使用される辞書Ｄｉｃ１となる（図１０（２））。
【００６４】
符号化部１１３は、図１０（２）に示す、辞書作成部１１１が作成した辞書を用いて、図１０（３）に示すように、１行目〜３行目までのレコードを符号化する。
【００６５】
上述のように符号化されたブロックＢ１は、次に圧縮処理が実行されるブロックの基準ブロックとなる。従って、辞書作成部１１１は、ブロックＢ１の辞書Ｄｉｃ１で、辞書Ｄｉｃ０を初期化する（ステップＳ３２）。初期化された辞書Ｄｉｃ０は、図１１（１）となる。
【００６６】
次に、データ取得部１１０は、図１１（２）に示す、ブロックＢ２の１行目のレコードを取得する（ステップＳ１６）。新しいブロックの処理を開始するにあたり、ステップＳ１２において辞書Ｄｉｃ１は初期化されて空テーブルとなっており、辞書Ｄｉｃ１には、Ｓａｎ Ｆｒａｎｃｉｓｃｏの値を持つエントリが存在しない（ステップＳ５０／ＮＯ）。従って、図６の辞書更新処理により、辞書Ｄｉｃ１には、図１１（３）に示す、Ｓａｎ Ｆｒａｎｃｉｓｃｏに符号「１」を割り当てたエントリが新規登録される（ステップＳ５２）。
【００６７】
データ取得部１１０は、同様にして、図１１（４）に示す、ブロックＢ２の２行目のレコードを取得する（ステップＳ１６）。辞書Ｄｉｃ１には、Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．の値を持つエントリが存在しないため（ステップＳ５０／ＮＯ）、図１１（５）に示すように、Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．に符号「２」を割り当てたエントリが、辞書Ｄｉｃ１に新規登録される（ステップＳ５２）。
【００６８】
データ取得部１１０は、次に、図１１（６）に示す、ブロックＢ２の３行目のレコードを取得する（ステップＳ１６）。辞書Ｄｉｃ１には、Ｎｅｗ Ｙｏｒｋの値を持つエントリが存在しないため（ステップＳ５０／ＮＯ）、図１１（７）に示すように、Ｎｅｗ Ｙｏｒｋに符号「３」を割り当てたエントリが、辞書Ｄｉｃ１に新規登録される（ステップＳ５２）。
【００６９】
ここで、Ｍの値が３となり、所定のレコード数を読み込んだため（ステップＳ２０／ＮＯ）、差分辞書作成部１１２が差分辞書作成処理（ステップＳ２２）を行う。
【００７０】
ステップＳ２２では、前述した図９のステップＳ６０〜ステップＳ６６の処理を、差分辞書作成部１１２が実行する。その結果、初期化された差分辞書Δは、図１２（１）となり、Ｄｉｆｆ０は空集合、Ｄｉｆｆ１＝｛Ｎｅｗ Ｙｏｒｋ｝、ＮｏＤｉｆｆ＝｛Ｓａｎ Ｆｒａｎｃｉｓｃｏ，Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．｝となる。
【００７１】
Ｄｉｆｆ１が空集合ではなく（ステップＳ６８／ＮＯ）、Ｄｉｆｆ０が空集合であるため（ステップＳ７０／ＹＥＳ）、Ｄｉｆｆ１の要素が差分辞書Δに新規登録される（ステップＳ７６）。その結果、具体例において、ステップＳ７６の処理実行後の差分辞書Δは図１２（２）となる。
【００７２】
次に、差分辞書作成部１１２は、ステップＳ７８の処理を実行する。具体例では、ＮｏＤｉｆｆの要素（Ｓａｎ ＦｒａｎｃｉｓｃｏとＷａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．）を値に持つエントリが、現在の差分辞書Δに存在する。従って、差分辞書作成部１１２は、差分辞書Δから、（Ｓａｎ ＦｒａｎｃｉｓｃｏとＷａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．）を値に持つエントリを削除し（ステップＳ７８）、差分辞書Δを出力部１１４及び辞書作成部１１１に出力する（ステップＳ８０）。出力される差分辞書Δは、図１２（３）となる。
【００７３】
次に、辞書作成部１１１は、図１３（１）に示す辞書Ｄｉｃ０と、図１３（２）に示す差分辞書Δとに基づいて、辞書Ｄｉｃ１を更新する（ステップＳ２６）。この場合、差分辞書Δに含まれる符号「３」は、辞書Ｄｉｃ０には登録されていない符号であるので、辞書Ｄｉｃ０に差分辞書Δのエントリを追加したものを、辞書Ｄｉｃ１とする。その結果、辞書Ｄｉｃ１は図１３（３）となる。
【００７４】
符号化部１１３は、図１３（３）の辞書を用いて、ブロックＢ２のデータを符号化する（ステップＳ２８）。符号化されたデータは図１３（４）となる。
【００７５】
ブロックＢ２は、次に圧縮処理が実行されるブロックの基準ブロックとなる。従って、辞書作成部１１１は、ブロックＢ２の辞書Ｄｉｃ１で、辞書Ｄｉｃ０を初期化する（ステップＳ３２）。初期化された辞書Ｄｉｃ０は、図１４（１）となる。
【００７６】
次に、データ取得部１１０は、図１４（２）に示す、ブロックＢ３の１行目のレコードを取得する（ステップＳ１６）。新しいブロックの処理を開始するにあたり、辞書Ｄｉｃ１は初期化されて空テーブルとなっているため、辞書Ｄｉｃ１には、Ｃｈｉｃａｇｏの値を持つエントリは存在しない（ステップＳ５０／ＮＯ）。従って、辞書更新処理により、辞書Ｄｉｃ１には、図１４（３）に示す、Ｃｈｉｃａｇｏに符号「１」を割り当てたエントリが新規登録される（ステップＳ５２）。
【００７７】
データ取得部１１０は、図１３（４）に示す、ブロックＢ３の２行目のレコードを取得する（ステップＳ１６）。辞書Ｄｉｃ１には、Ｓａｎ Ｆｒａｎｃｉｓｃｏの値を持つエントリが存在しないため（ステップＳ５０／ＮＯ）、図１４（５）に示すように、Ｓａｎ Ｆｒａｎｃｉｓｃｏに符号「２」を割り当てたエントリが辞書Ｄｉｃ１に新規登録される（ステップＳ５２）。
【００７８】
データ取得部１１０は、次に、図１４（６）に示す、ブロックＢ３の３行目のレコードを取得する（ステップＳ１６）。辞書Ｄｉｃ１には、Ｓａｎ Ｆｒａｎｃｉｓｃｏの値を持つエントリが既に存在するので（ステップＳ５０／ＹＥＳ）、辞書Ｄｉｃ１は変更されず、図１４（５）のままである。
【００７９】
ここで、Ｍの値が３となり、所定のレコード数を読み込んだため（ステップＳ２０／ＮＯ）、差分辞書作成部１１２が差分辞書作成処理（ステップＳ２２）を行う。
【００８０】
ステップＳ２２では、前述した図９のステップＳ６０〜ステップＳ６６の処理を、差分辞書作成部１１２が実行する。その結果、具体例において、初期化された差分辞書Δは図１５（１）となる。また、Ｄｉｆｆ０＝｛Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．，Ｎｅｗ Ｙｏｒｋ｝、Ｄｉｆｆ１＝｛Ｃｈｉｃａｇｏ｝、ＮｏＤｉｆｆ＝｛Ｓａｎ Ｆｒａｎｃｉｓｃｏ｝となる。具体例において、Ｄｉｆｆ１は空集合ではなく（ステップＳ７０／ＮＯ）、Ｄｉｆｆ０も空集合ではない（ステップＳ７０／ＮＯ）。
【００８１】
図９のフローチャートにおいて、差分辞書作成部１１２は、Ｄｉｆｆ０が空集合ではない場合（ステップＳ７０／ＮＯ）、集合Ｄｉｆｆ０の要素ｄ０、集合Ｄｉｆｆ１の要素ｄ１を取得し、差分辞書Δにおけるｄ０をｄ１に置換する。そして、差分辞書作成部１１２は、Ｄｉｆｆ０から要素ｄ０を、Ｄｉｆｆ１から要素ｄ１をそれぞれ削除する（ステップＳ７２）。その後、差分辞書作成部１１２は、ステップＳ６８に戻り処理を継続する。
【００８２】
具体例で、差分辞書Δにおいて、Ｄｉｆｆ０の要素であるＷａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．が、Ｄｉｆｆ１の要素であるＣｈｉｃａｇｏで置換される。また、Ｄｉｆｆ０からＷａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．が削除され、Ｄｉｆｆ１からＣｈｉｃａｇｏが削除される。その結果、ステップＳ７２実行後の差分辞書Δは、図１５（２）となり、また、Ｄｉｆｆ０＝｛Ｎｅｗ Ｙｏｒｋ｝、Ｄｉｆｆ１は空集合となる。Ｄｉｆｆ１が空集合であるとは、基準ブロックの辞書Ｄｉｃ０に存在するが処理対象ブロックには出現しない文字列の数が、辞書Ｄｉｃ０には存在しないが処理対象ブロックには出現する文字列の数を超えているということである。
【００８３】
そこで、図９のフローチャートにおいて、差分辞書作成部１１２は、Ｄｉｆｆ１が空集合の場合（ステップＳ６８／ＹＥＳ）、差分辞書Δにおいて、Ｄｉｆｆ０の要素と一致する値を全てＮＵＬＬに置換する（ステップＳ７４）。次に、差分辞書作成部１１２は、Ｎｏｄｉｆｆの要素と一致する値を持つエントリを差分辞書Δから全て除去し（ステップＳ７８）、差分辞書Δを出力部１１４及び辞書作成部１１１出力する（ステップＳ８０）。
【００８４】
具体例においては、差分辞書Δにおいて、Ｄｉｆｆ０の要素であるＮｅｗ ＹｏｒｋがＮＵＬＬに置換される（ステップＳ７４）。この処理の結果、ステップＳ７４実行後の差分辞書Δは図１５（３）となる。そして、差分辞書作成部１１２は、ステップＳ７８において、現在の差分辞書ΔからＮｏＤｉｆｆの要素（Ｓａｎ Ｆｒａｎｃｉｓｃｏ）の値を持つエントリを除去する。その結果、ステップＳ８０で出力される差分辞書Δは、図１５（４）となる。
【００８５】
次に、辞書作成部１１１は、図１６（１）に示す辞書Ｄｉｃ０と、図１６（２）に示す差分辞書Δとに基づいて、ブロックＢ３の符号化に用いる辞書Ｄｉｃ１を更新する（ステップＳ２６）。辞書Ｄｉｃ０と差分辞書Δとは、符号「２」及び「３」が重複するので、辞書Ｄｉｃ０において、符号「２」及び「３」が割り当てられている文字列を、差分辞書Δの文字列で上書きし、辞書Ｄｉｃ１を更新する。その結果、辞書Ｄｉｃ１は、図１６（３）となる。
【００８６】
符号化部１１３は、図１６（３）に示される辞書Ｄｉｃ１を用いて、ブロックＢ３のデータを符号化する（ステップＳ２８）。符号化されたデータは、図１６（４）となる。
【００８７】
このようにして、図７に示す被圧縮データは、図１７に示すように、ブロック毎に、差分辞書Δと符号化データとを有する圧縮データとなり出力される。
【００８８】
以上の説明から明らかなように、本実施例に係るデータ圧縮装置は、ブロックにおいて、処理対象ブロックに出現する文字列のうち、基準辞書に登録されていない文字列と、基準辞書において処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書を生成する。これにより、ブロックストリーム処理においてテキストデータを圧縮する場合、ブロック毎に差分辞書と符号化データとを含む圧縮データを作成し、かつ差分辞書で文字列に割り当てる符号を再利用して、圧縮率を向上させることができる。
【００８９】
ここで、図１８及び図１９を用いて、比較例１及び２と、本実施例とによる被圧縮データの圧縮率を比較する。図１８（１）は、本説明で使用する被圧縮データを示す。本説明では、４レコードを１ブロックとして処理することとする。
【００９０】
まず、比較例１による圧縮データの作成について説明する。図１８（２）は、比較例１により被圧縮データを圧縮した場合のデータ例である。比較例１は、ブロック毎に、ブロックに出現する文字列と、符号とを対応付けた辞書を登録して、圧縮データを作成する。また、ブロックが変わる都度、符号を１から採番し直す。
【００９１】
具体的に、図１８（１）のデータを用いて説明する。図１８（１）に示す被圧縮データのブロックＢ１において、ブロックに出現する文字列は、Ｓａｎ Ｆｒａｎｃｉｓｃｏ、Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．、Ｌｏｓ Ａｎｇｅｌｓ、Ｎｅｗ Ｏｒｌｅａｎｓの４つである。従って、比較例１では、上記４つの文字列と符号とを対応付けた辞書をブロックＢ１の辞書として登録し、図１８（２）に示すように、辞書と符号化データとを含むブロックＢ１の圧縮データを作成する。
【００９２】
次に、比較例１では、ブロックＢ２において、ブロックに出現するＷａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．、Ｎｅｗ Ｙｏｒｋ、Ｃｈｉｃａｇｏ、及びＬｏｓ Ａｎｇｅｌｓの４つの文字列と、符号とを対応付けた辞書をブロックＢ２の辞書として登録する。また、ブロックＢ３では、ブロックに出現するＷａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．、Ｎｅｗ Ｙｏｒｋ、Ｃｈｉｃａｇｏ、及びＬｏｓ Ａｎｇｅｌｓの４つの文字列と、符号とを対応付けた辞書をブロックＢ３の辞書として登録する。そして、ブロック毎に登録された辞書を用いて、被圧縮データを符号化する。その結果、比較例１の圧縮データは、図１８（２）となる。
【００９３】
次に、比較例２による圧縮データの作成について説明する。図１９（１）は、比較例２により被圧縮データを圧縮した場合のデータ例である。比較例２は、ブロック毎に、本実施例と同様の差分辞書を作成するが、差分辞書に登録される文字列に、新たに採番した符号を割り当てる。すなわち、比較例２は、基準ブロックには出現するが処理対象ブロックには出現しない文字列に対応付けられていた符号の再利用は行わない。
【００９４】
比較例２について、具体的に説明する。比較例２において、ブロックＢ１は最初の処理対象ブロックであるため、基準ブロックの辞書が存在しない。従って、ブロックＢ１については、比較例２においても、比較例１と同様のエントリを持つ差分辞書が登録される。次に、ブロックＢ２において、比較例２はブロックＢ１の辞書には登録されていないがブロックＢ２には出現する文字列に対して、差分辞書を登録する。つまり、Ｎｅｗ Ｙｏｒｋ、及びＣｈｉｃａｇｏの文字列を差分辞書に登録する。ここで、比較例２では、差分辞書に登録された文字列に、新たに採番した符号を割り当てる。ブロックＢ１において、符号は「４」まで使用されているので、比較例２は、新規の符号「５」及び「６」をＮｅｗ Ｙｏｒｋ及びＣｈｉｃａｇｏにそれぞれ割り当てる。ブロックＢ３では、ブロックＢ２の符号化に使用された辞書には存在しないがブロックＢ３には出現する文字列に対して、差分辞書を登録する。つまり、Ｌａｓ Ｖｅｇａｓ及びＭｅｘｉｃｏ Ｃｉｔｙの文字列を差分辞書に登録する。そして、ブロックＢ２の差分辞書を作成する際に、符号を「６」まで採番済みであるので、Ｌａｓ Ｖｅｇａｓ及びＭｅｘｉｃｏ Ｃｉｔｙには、新規の符号「７」及び「８」をそれぞれ割り当てる。以上のようにして、比較例２は、図１９（１）に示すように、差分辞書と符号化データとを含む圧縮データをブロック毎に作成する。
【００９５】
図１９（２）は、本実施例により図１８（１）の被圧縮データを圧縮した場合のデータ例である。本実施例において、ブロックＢ１は最初の処理対象ブロックであるため、基準ブロックの辞書が存在しない。従って、ブロックＢ１については、実施例においても、比較例１及び２と同様のエントリを持つ差分辞書が登録される。次に、ブロックＢ２において、実施例はブロックＢ１の辞書には登録されていないがブロックＢ２には出現する文字列に対して、差分辞書を登録する。つまり、Ｎｅｗ Ｙｏｒｋ、及びＣｈｉｃａｇｏの文字列を差分辞書に登録する。そして、実施例では、ブロックＢ１の辞書において、ブロックＢ１の辞書には登録されているがブロックＢ２には出現しない文字列に割り当てられている符号を再利用する。図１９（２）の例では、ブロックＢ２には出現しないＳａｎ Ｆｒａｎｃｉｓｃｏ及びＮｅｗ Ｏｒｌｅａｎｓに対して、ブロックＢ１の辞書で割り当てられている符号「１」及び「４」を再利用し、Ｎｅｗ Ｙｏｒｋ、及びＣｈｉｃａｇｏに対して割り当てる。また、ブロックＢ３では、ブロックＢ３には出現しないＬｏｓ Ａｎｇｅｌｓ及びＣｈｉｃａｇｏに対して、ブロックＢ２を符号化した辞書で割り当てられている符号「３」及び「４」を再利用し、Ｌａｓ Ｖｅｇａｓ及びＭｅｘｉｃｏ Ｃｉｔｙに割り当てる。以上のようにして、本実施例は、図１９（２）に示すように、差分辞書と符号化データとを含む圧縮データをブロック毎に作成する。
【００９６】
次に、比較例１及び２と、本実施例との圧縮率を比較する。
【００９７】
比較例１では、上述したように、ブロック毎に、ブロックに出現する文字列と符号とを対応付けた辞書を作成する。従って、図１８（２）に示すように、ブロック毎に登録された辞書間で重複した値を含むこととなる。例えば、ブロックＢ１の辞書と、ブロックＢ２の辞書とでは、Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．とＬｏｓ Ａｎｇｅｌｓとが重複している。また、ブロックＢ２の辞書とブロックＢ３の辞書とでは、Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．とＮｅｗ Ｙｏｒｋとが重複している。このため、比較例１では、辞書全体のサイズが大きくなり、圧縮率の悪化を引き起こす。
【００９８】
比較例２では、ブロックＢ２の辞書には、ブロックＢ１で出現する文字列は登録されず、ブロックＢ２で初めて出現した文字列のみが差分辞書に登録される。従って、比較例１と比較して、辞書サイズを小さくすることができる。
【００９９】
しかし、比較例２では、基準ブロックには出現しないが処理対象ブロックでは出現する文字列に、新たに採番した符号を割り当てる。従って、比較例１のようにブロック毎に辞書を出力する場合と比べて、符号数が増加してしまい、符号の符号長が長くなってしまう恐れがある。そこで、比較例２のように、符号を新たに採番する場合と、本実施例のように再利用する場合との間の圧縮率の違いについて説明する。
【０１００】
被圧縮データＤを、Ｎ個のブロックに分割したとする（Ｄ＝Ｂ１・Ｂ２・Ｂ３・・・ＢＮ）。すると、比較例２の場合、つまり、符号を再利用しない場合に必要な符号の総数は、最大で被圧縮データＤに含まれるエントリの数となる。一方、本実施例のように、符号を再利用する場合、必要な符号の総数は、最大で、ブロックＢｉ（ｉ＝１〜Ｎ）に含まれるエントリの数となる。
【０１０１】
符号化に整数を用いると仮定すると、比較例２の場合、符号が２５６種類までならば、符号長１バイトで符号化できるが、それ以上の場合、６５５３６種類までは符号長２バイトが必要となり、それ以上となると符号長はさらに長くなる。一方、本実施例の場合、必要な符号の総数は、最大でブロックＢｉに含まれるエントリ数であるため、１ブロックに含まれるレコード数を２５６以下とすれば、符号長が１バイトを超えることはない。
【０１０２】
図２０は、比較例１、比較例２、及び本実施例によってデータを圧縮した場合の、圧縮データのファイルサイズを模式的に示した図である。図２０中、ハッチングを施した部分は辞書データを表し、ハッチングを施していない部分は、符号化データを表す。図２０からもわかるように、比較例１と比較例２とでは、比較例２の方が、辞書サイズが小さくなるため、圧縮データサイズも小さくなる。
【０１０３】
また、比較例２と本実施例とでは、本実施例の方が、符号を再利用することのより、符号長が長くなる可能性を低減できるため、比較例２と比較して更に圧縮データサイズを小さくすることができる。つまり、本実施例では、差分辞書を用いることで、辞書に登録されるエントリ数を削減できるため、辞書データのファイルサイズを削減できる。更に、符号を再利用することによって、符号長を短くして、符号に必要なデータサイズを削減できるため、更に圧縮率を向上できる。
［データ伸長装置］
【０１０４】
次に、本件に係るデータ伸長装置について説明する。図２１は、本件に係るデータ伸長装置を含むデータ伸長システムの一構成例を示している。
【０１０５】
データ伸長装置２００は、ネットワーク４０を介して、記憶装置１０、及びデータ処理装置３０と接続している。
【０１０６】
記憶装置１０は、伸長対象のデータ（被伸長データと記載する）を格納している。また、データ伸長装置２００は、伸長されたデータを格納する。
【０１０７】
データ処理装置３０は、データ伸長装置２００に被伸長データを送信する。また、データ伸長装置２００が伸長したデータを受信する。
【０１０８】
データ伸長装置２００のハードウェア構成は、データ圧縮装置１００のハードウェア構成と同様であるため、説明を省略する。ただし、データ伸長装置２００の場合、ＲＯＭ１０２は、被伸長データを伸長するためのプログラムを格納する。また、ＲＯＭ１０２に格納されたプログラムのＣＰＵ１０３による演算によって、図２２に示すデータ伸長装置２００が有する機能が実現される。
【０１０９】
次に、図２２を用いて、データ伸長装置２００が有する機能を実現する手段について説明する。図２２は、データ伸長装置２００の機能ブロック図の一例である。
【０１１０】
図２２に示すように、データ伸長装置２００は、ブロック取得部２０１と、差分辞書及び圧縮データの入力を受け付ける入力部としての機能を実現するデータ取得部２０２及び差分辞書取得部２０３と、辞書復元部２０４と、復号部２０５と、出力部２０６とを備える。
【０１１１】
ブロック取得部２０１は、記憶装置１０から取得した、あるいは、データ処理装置３０から受信した、複数のブロックで構成された被伸長データを所定の規則に基づき複数のブロックに分割する分割部としての機能を有する。ブロック取得部２０１は、被伸長データから伸長処理の対象となるブロック（処理対象ブロック）を取得する。被伸長データを構成する各ブロックは、差分辞書と符号化データとを有する。
【０１１２】
データ取得部２０２は、ブロック取得部２０１が取得した処理対象ブロックから、符号化データを取得する。
【０１１３】
差分辞書取得部２０３は、処理対象ブロックから、差分辞書を取得する。
【０１１４】
辞書復元部２０４（処理対象辞書生成部）は、差分辞書取得部２０３が取得した差分辞書と、処理対象ブロックとは異なる基準ブロックの復号に使用した辞書とに基づいて、処理対象ブロックの符号化データを作成した際に使用された辞書（処理対象辞書）を復元する。本実施例では、連続する２つのブロックにおいて、前方のブロックを基準ブロックとし、後方のブロックを処理対象ブロックとする。
【０１１５】
復号部２０５は、辞書復元部２０４が復元した辞書を用いて、データ取得部２０２が取得した符号化データを復号する。
【０１１６】
出力部２０６は、復号部２０５が復号したブロックのデータを、記憶装置１０に格納する、または、データ処理装置３０に送信する。
【０１１７】
次に、データ伸長装置２００が実行する伸長処理について説明する。図２３は、データ伸長装置２００が実行する伸長処理の一例を示すフローチャートである。
【０１１８】
まず、辞書復元部２０４は、基準ブロックの辞書Ｄｉｃを空テーブルで初期化する（ステップＳ１００）。被伸長データの最初のブロックが処理対象ブロックである場合、基準ブロックが存在しないためである。
【０１１９】
ブロック取得部２０１は、被伸長データに処理対象となるブロックが存在するか否かを判定する（ステップＳ１０２）。ブロック取得部２０１は、ブロックが存在する場合には（ステップＳ１０２／ＹＥＳ）、ブロックを取得する（ステップＳ１０４）。ブロック取得部２０１は、ブロックが存在しない場合には（ステップＳ１０２／ＮＯ）、本処理を終了する。
【０１２０】
ブロック取得部２０１がブロックを取得すると（ステップＳ１０４）、差分辞書取得部２０３が取得されたブロックに含まれる差分辞書Δを取得する（ステップＳ１０６）。
【０１２１】
次に、辞書復元部２０４が、処理対象ブロックの復号に使用される辞書Ｄｉｃ１の復元処理を実行する（ステップＳ１０８）。辞書復元処理の詳細は後述する。
【０１２２】
復元部２０５は、ステップＳ１０８の処理で復元された辞書Ｄｉｃ１を用いて、符号化データを復号する（ステップＳ１１０）。
【０１２３】
出力部２０６は、復号されたデータを出力する（ステップＳ１１２）。次に、辞書復元部２０４が、処理対象ブロックの復号に使用した辞書Ｄｉｃ１を使用して、辞書Ｄｉｃを初期化する（ステップＳ１１４）。本実施例では、基準ブロックと処理対象ブロックとは連続する２つのブロックであるため、ステップＳ１１０で復号に使用した辞書Ｄｉｃ１が、次の処理対象ブロックに対する基準ブロックの辞書Ｄｉｃとなるからである。
【０１２４】
次に、具体的なデータを用いて、上述した伸長処理によるデータ伸長について説明するとともに、辞書復元処理の詳細について説明する。ここでは、図１７に示した圧縮データに伸長処理を施し、復号データを得るものとする。
【０１２５】
まず、ブロック取得部２０１が、ブロックＢ１を取得する（ステップＳ１０４）。差分辞書取得部２０３は、図２４（１）に示す、ブロックＢ１に含まれる差分辞書Δを取得する（ステップＳ１０６）。次に、辞書復元部２０４が辞書復元処理を実行する（ステップＳ１０８）。
【０１２６】
ここで、辞書復元処理について、具体例を参照しつつ説明する。図２５は辞書復元処理の一例を示すフローチャートである。辞書復元部２０４は、まず、処理対象ブロックのデータ復号に使用される辞書Ｄｉｃ１及び、集合ＤｉｆｆＩＤを初期化する（ステップＳ１２０）。辞書復元部２０４は、辞書Ｄｉｃ１を辞書Ｄｉｃで初期化し、ＤｉｆｆＩＤを差分辞書Δの符号項目の値集合（図２５では、Δ．ＩＤと記載）で初期化する。
【０１２７】
具体例では、ブロックＢ１は、最初のブロックであるので基準ブロックの復号に用いた辞書Ｄｉｃは空テーブルとなっている。従って、ステップＳ１２０の初期化の結果、辞書Ｄｉｃ１は空テーブルとなり、また、ＤｉｆｆＩＤ＝｛１，２｝となる。
【０１２８】
次に、辞書復元部２０４は、ＤｉｆｆＩＤに要素が存在するか否か判定する（ステップＳ１２２）。ＤｉｆｆＩＤに要素が存在する場合（ステップＳ１２２／ＹＥＳ）、辞書復元部２０４は、ＤｉｆｆＩＤにおける最小の要素ｋを取得し、ＤｉｆｆＩＤから要素ｋを消去する（ステップＳ１２４）。次に、辞書復元部２０４は、ステップＳ１２４で取得したｋが辞書Ｄｉｃ１のエントリ数以下か否か判定する（ステップＳ１２６）。図２５では、辞書Ｄｉｃ１のエントリ数を｜Ｄｉｃ１｜で表す。
【０１２９】
ｋの値が辞書Ｄｉｃ１のエントリ数より大きい場合（ステップＳ１２６／ＮＯ）、辞書復元部２０４は、辞書Ｄｉｃ１の末尾に、Ｄｉｃ１［ｋ］＝Δ［ｋ］となるエントリを追加する。その後、辞書復元部２０４はステップＳ１２２に戻り処理を継続する。ここで、Ｄｉｃ１［ｋ］は、辞書Ｄｉｃ１において符号「ｋ」と対応付けられている文字列を表し、Δ［ｋ］は、差分辞書Δにおいて符号「ｋ」と対応付けられている文字列を表す。
【０１３０】
具体例では、ＤｉｆｆＩＤに要素が存在するので、辞書復元部２０４は、ＤｉｆｆＩＤにおける最小の要素ｋ＝１を取得し、ＤｉｆｆＩＤからｋ＝１を消去する（ステップＳ１２４）。その結果、ＤｉｆｆＩＤ＝｛２｝となる。
【０１３１】
ｋ（＝１）が、辞書Ｄｉｃ１のエントリ数（＝０）よりも大きいため、辞書復元部２０４は、辞書Ｄｉｃ１において符号「１」と対応付けられた文字列が、差分辞書Δにおいて符号「１」と対応付けられた文字列となるエントリを、辞書Ｄｉｃ１の末尾に追加する（ステップＳ１３０）。その結果、ステップＳ１３０の処理後の辞書Ｄｉｃ１は、図２４（２）となる。
【０１３２】
辞書復元部２０４は、ＤｉｆｆＩＤに、未だ要素が存在するので（ステップＳ１２２／ＹＥＳ）、ＤｉｆｆＩＤからｋ＝２を取得し、ＤｉｆｆＩＤからｋ＝２を除去する（ステップＳ１２４）。この結果、ＤｉｆｆＩＤは空集合となる。
【０１３３】
ｋ＝２は、辞書Ｄｉｃ１のエントリ数（＝１）より大きいため、辞書復元部２０４は、辞書Ｄｉｃ１において符号「２」と対応付けられた文字列が、差分辞書Δにおいて符号「２」と対応付けられた文字列となるエントリを、辞書Ｄｉｃ１の末尾に追加する。ステップＳ１３０の処理後の辞書Ｄｉｃ１は、図２４（３）となる。先ほどのステップＳ１２４の処理で、ＤｉｆｆＩＤは空集合となっている。
【０１３４】
図２５のフローチャートにおいて、ＤｉｆｆＩＤに要素が存在しない場合（ステップＳ１２２／ＮＯ）、辞書復元部２０４は、辞書Ｄｉｃ１を出力し（ステップＳ１３２）、本処理を終了する。辞書復元処理の他のステップについては、後述する。
【０１３５】
具体例において、辞書復元部２０４は、ＤｉｆｆＩＤが空集合であるので（ステップＳ１２２／ＮＯ）、辞書Ｄｉｃ１を出力する（ステップＳ１３２）。図２４（４）が復元された辞書Ｄｉｃ１である。
【０１３６】
復号部２０５は、図２４（４）に示す辞書Ｄｉｃ１を用いて、データ取得部２０２が取得したブロックＢ１に含まれる符号化データを復号する（ステップＳ１１０）。復号されたデータは、図２４（５）となる。
【０１３７】
ブロック取得部２０１は、次のブロック（ブロックＢ２）が存在するので（ステップＳ１０２／ＹＥＳ）、ブロックＢ２を取得する。差分辞書取得部２０３は、図２６（１）に示す、ブロックＢ２に含まれる差分辞書Δを取得する（ステップＳ１０６）。次に、辞書復元部２０４が辞書復元処理（ステップＳ１０８）を実行する。
【０１３８】
まず、辞書復元部２０４は、辞書Ｄｉｃ１を、基準ブロックとなるブロックＢ１の復号に用いた辞書Ｄｉｃで初期化する（ステップＳ１２０）。また、ＤｉｆｆＩＤをΔ．ＩＤで初期化する（ステップＳ１２０）。その結果、初期化された辞書Ｄｉｃ１は図２６（２）となり、ＤｉｆｆＩＤ＝｛３｝となる。
【０１３９】
次に、辞書復元部２０４は、ＤｉｆｆＩＤに要素が存在するので（ステップＳ１２２／ＹＥＳ）、ＤｉｆｆＩＤからｋ＝３を取得し、ＤｉｆｆＩＤからｋ＝３を除去する（ステップＳ１２４）。この結果、ＤｉｆｆＩＤは空集合となる。ｋ＝３は辞書Ｄｉｃ１のエントリの数（＝２）よりも大きいので（ステップＳ１２６／ＹＥＳ）、辞書復元部２０４は、辞書Ｄｉｃ１の符号「３」と対応付けられた文字列が、差分辞書Δにおいて符号「３」と対応付けられた文字列となるエントリを、辞書Ｄｉｃ１に追加する（ステップＳ１３０）。ステップＳ１３０の処理後の辞書Ｄｉｃ１は、図２６（３）となる。
【０１４０】
辞書復元部２０４は、ＤｉｆｆＩＤが空集合となっているので（ステップＳ１２２／ＮＯ）、図２６（４）に示す辞書Ｄｉｃ１を出力する（ステップＳ１３２）。
【０１４１】
復号部２０５は、図２６（４）に示す辞書を使用して、ブロックＢ２に含まれる符号化データを復号する（ステップＳ１１０）。その結果、復号されたデータは図２６（５）となる。
【０１４２】
ブロック取得部２０１は、次のブロックが存在するので（ステップＳ１０２／ＹＥＳ）、ブロックＢ３を読み込む（ステップＳ１０４）。差分辞書取得部２０３は、図２７（１）に示す差分辞書ΔをブロックＢ３から取得する（ステップＳ１０６）。辞書復元部２０４が、辞書復元処理を実行する（ステップＳ１０８）。
【０１４３】
辞書復元部２０４は、辞書Ｄｉｃ１を、基準ブロックとなるブロックＢ２の復号に用いた辞書Ｄｉｃで初期化する（ステップＳ１２０）。また、ＤｉｆｆＩＤをΔ．ＩＤで初期化する（ステップＳ１２０）。その結果、初期化された辞書Ｄｉｃ１は、図２７（２）となり、ＤｉｆｆＩＤ＝｛２，３｝となる。
【０１４４】
辞書復元部２０４は、ＤｉｆｆＩＤに要素が存在するので（ステップＳ１２２／ＹＥＳ）、ＤｉｆｆＩＤから最小の要素ｋ＝２を取得し、ＤｉｆｆＩＤからｋ＝２を除去する（ステップＳ１２４）。その結果、ＤｉｆｆＩＤ＝｛３｝となる。ここで、具体例において、ｋ＝２が辞書Ｄｉｃ１のエントリ数（＝３）以下となっている。
【０１４５】
図２５のフローチャートにおいて、ｋの値が、辞書Ｄｉｃ１のエントリ数以下である場合（ステップＳ１２６／ＹＥＳ）、辞書復元部２０４は、辞書Ｄｉｃ１において符号「ｋ」と対応付けられている文字列を、差分辞書Δにおいて符号「ｋ」と対応付けられている文字列で上書きする（ステップＳ１２８）。そして、ステップＳ１２８の処理を終えると、辞書復元部２０４は、ステップＳ１２２に戻り処理を継続する。
【０１４６】
具体例において、辞書復元部２０４は、ｋ＝２が辞書Ｄｉｃ１のエントリ数（＝３）以下であるので、ステップＳ１２８の処理を実行する。すなわち、辞書Ｄｉｃ１の符号「２」と対応付けられた文字列を、差分辞書Δにおいて符号「２」に対応付けられた文字列で上書きする。ステップＳ１２８の処理後の辞書Ｄｉｃ１は、図２７（３）となる。
【０１４７】
次に、辞書復元部２０４は、ＤｉｆｆＩＤに未だ要素が存在するので（ステップＳ１２２／ＹＥＳ）、要素ｋ＝３を取得し、ＤｉｆｆＩＤからｋ＝３を除去する（ステップＳ１２４）。その結果、ＤｉｆｆＩＤは空集合となる。
【０１４８】
取得したｋ（＝３）は、辞書Ｄｉｃ１のエントリ数（＝３）以下であるので（ステップＳ１２６／ＹＥＳ）、辞書復元部２０４はステップＳ１２８の処理を実行する。すなわち、辞書Ｄｉｃ１において符号「３」と対応付けられた文字列を、差分辞書Δにおいて符号「３」と対応付けられた文字列で上書きする。その結果、ステップＳ１２８の処理後の辞書Ｄｉｃ１は、図２７（４）となる。
【０１４９】
ＤｉｆｆＩＤが空集合となったので（ステップＳ１２２／ＮＯ）、辞書復元部２０４は、図２７（５）に示す辞書Ｄｉｃ１を出力する。復号部２０５は、ブロックＢ３に含まれるデータを、図２７（５）に示す辞書で復号する。その結果、復号されたデータは、図２７（６）になる。
【０１５０】
ブロックＢ３の次に、処理対象となるブロックは存在しないため（ステップＳ１０２／ＮＯ）、データ伸長装置２００は、データ伸長処理を終了する。
【０１５１】
以上の説明から明らかなように、本実施例に係るデータ伸長装置２００は、基準ブロックの符号化に使用された辞書と、処理対象ブロックの差分辞書との間に重複する符号が存在する場合、重複する符号に対応する基準ブロックの文字列を、差分辞書の文字列で置換する。その結果、上述したデータ圧縮方法により作成された圧縮データを伸長して、元のデータを復元することができる。
【０１５２】
以上、本件実施例について詳述したが、本件は係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【０１５３】
例えば、本実施例では、連続する２つのブロックにおいて、前方のブロックを基準ブロックとし、後方のブロックを処理対象ブロックとして、順次圧縮処理、伸長処理を行った。しかしながら、基準ブロックを被圧縮データの最初のブロックとし、処理対象ブロックを、最初のブロック以外の、任意のブロックＢｉとしても良い。つまり、データ圧縮装置１００は、処理対象ブロックの圧縮処理において、常に、最初のブロックを基準ブロックとして差分辞書を作成するようにしても良い。連続する２つのブロックを本実施例を用いて圧縮した場合、例えば、ブロックＢｉのデータを伸長するためには、ブロックＢ１〜ブロックＢｉ−１の符号化に用いられた辞書をそれぞれ復元してから、ブロックＢｉの辞書を復元し、データを復号する必要がある。しかしながら、最初のブロックとの差分辞書を作成するようにした場合、最初のブロックの差分辞書と、ブロックＢｉの差分辞書とを使用すれば、ブロックＢｉの符号化に用いられた辞書を復元できるため、ブロックＢ１〜ブロックＢｉ−１において順次辞書を復元する必要がない。従って、指定されたブロックのデータを復号するまでの時間を短縮することができる。また、本実施例における被圧縮データは構造を有するテキストデータであるが、被圧縮データが構造を有しないプレーンなテキスト形式のデータである場合も、同様に実施することができる。さらに、本実施例では、静的辞書式符号化手法として、単純な「値の符号化方式」を採用したが、その他の静的辞書式符号化手法を用いても、同様に実施することが可能である。
【０１５４】
なお、上記のデータ圧縮装置、及びデータ伸長装置が有する機能は、コンピュータによって実現することができる。その場合、データ圧縮装置、及びデータ伸長装置が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。
【０１５５】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ（Digital Versatile Disc）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）などの可搬型記録媒体の形態で販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１５６】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０１５７】
また、本実施例では、データ圧縮装置及びデータ伸長装置を別々の装置として記載したが、図２８に示すように１つの情報処理装置がデータ圧縮装置及びデータ伸長装置としての機能を果すように構成しても良い。また、例えば、インターネット等の通信網に接続されたサーバコンピュータを本件のデータ圧縮装置及びデータ伸長装置の少なくとも一方とし、これに接続されたパーソナルコンピュータ等の通信装置に、データ圧縮及びデータ伸長の少なくとも一つを行うサービスをサーバコンピュータから提供するようにしても良い（ＡＳＰ(Application Service Provider)）。
【０１５８】
また、本実施例ではネットワーク４０を介して、データ圧縮装置１００又はデータ伸長装置２００は、記憶装置１０、センサ装置２０、及びデータ処理装置３０とデータの送受信を行うこととした。しかしながら、データ圧縮装置１００又はデータ伸長装置２００を、記憶装置１０、センサ装置２０、及びデータ処理装置３０のそれぞれと直接接続（ローカル接続）して、データの送受信を行うように構成しても良い。また、本実施例では、地区項目のみを符号化したが、他の項目についても符号化が可能なことはいうまでもない。
【符号の説明】
【０１５９】
１００…データ圧縮装置
１１０…データ取得部
１１１…辞書作成部
１１２…差分辞書作成部
１１３…符号化部
１１４…出力部
２００…データ伸長装置
２０１…ブロック取得部
２０２…データ取得部
２０３…差分辞書取得部
２０４…辞書復元部
２０５…復号部
【技術分野】
【０００１】
本発明は、データ圧縮装置、データ伸長装置、データ圧縮プログラム、及びデータ伸長プログラムに関する。
【背景技術】
【０００２】
テキストデータ（プレーンなテキスト形式のデータや、ＣＳＶ（Comma Separated Values）形式のデータ、ＸＭＬ（eXtensible Markup Language）データ等）を圧縮する方法として、辞書型符号化方式が知られている。辞書型符号化方式は、圧縮対象のデータ列中に出現する文字や文字列にそれぞれ所定の番号（符号）を割り当てて辞書を作成しておき、この辞書に基づいて実際の入力文字の符号化を行う。辞書式符号化方式には、辞書の保存が必要な静的辞書式符号化（ＢＰＥ(Byte Pair Encoding)やＳＴＶＦ(Suffix-Tree based VF coding) 等）と、辞書の保存が不要な動的辞書式符号化（ＬＺ７７やＬＺ７８等）がある。データベースから出力されたデータなど、重複した値文字列を多く含むようなデータでは、静的辞書式符号化を適用してから、さらに動的辞書式符号化を適用することで、動的辞書式符号化のみの適用より圧縮率が向上することが知られている。また、静的辞書式符号化は、圧縮データを伸長することなくパターン検索するのに適した方式であることも知られている。
【０００３】
また、入力データを適当な大きさに分割したブロックを逐次処理（ストリーム処理）するブロックストリーム処理が知られている。多くの静的辞書式符号化方式は、辞書作成と符号化の２パスで符号化を行うため、逐次処理を行うことができないが、ブロックストリーム処理を適用することで、限られた計算領域しか用いずに、逐次処理を行うことができる。また、ブロックストリーム処理は、より細かい単位でのストリーム処理（文字ストリーム処理や単語ストリーム処理）に比べて、より軽量なインデックスを用いたフィルタリングを行える、等の利点がある。
【０００４】
そこで、ブロックストリーム処理において圧縮率を向上させる圧縮・伸長アルゴリズムが提案されている（例えば、特許文献１）。また、単語ストリーム処理において、辞書を使用してデータを圧縮する技術も提案されている（例えば、特許文献２）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平９−２１４３５３号公報
【特許文献２】特開平１１−１６８３９０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、ブロックストリーム処理を用いて入力データの辞書式符号化を行う場合に、上記特許文献１および２の技術では、次の問題がある。特許文献１の技術では、各ブロックにおける辞書サイズの削減について考慮していないため、十分な圧縮率を得られない恐れがある。特許文献２の技術は、単語ストリーム処理を行っているので、ブロックストリーム処理に特有の利点を失ってしまう。また、特許文献２の技術をブロックストリーム処理に自然に拡張することは可能だが、その場合、各ブロックの辞書の増大により、やはり十分な圧縮率が得られない恐れがある。
【０００７】
本件は、上記の事情に鑑みて成されたものであり、ブロックストリーム処理において、テキストデータの圧縮率を向上させるデータ圧縮装置、データ伸長装置、データ圧縮プログラム、及びデータ伸長プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、明細書開示のデータ圧縮装置は、テキストデータの入力を受け付ける入力部と、前記テキストデータを所定の規則に基づき複数のブロックに分割する分割部と、文字列と符号とが対応付けられて格納された辞書データである基準辞書に基づき、処理対象ブロックに出現する文字列のうち、該基準辞書に登録されていない文字列と、該基準辞書において前記処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書を生成する差分辞書生成部と、前記作成した差分辞書と前記基準辞書とに基づき、辞書データである処理対象辞書を生成する処理対象辞書生成部と、前記生成した処理対象辞書を参照し、前記処理対象ブロックに出現する文字列を対応する符号に置き換えることで、該処理対象ブロックを圧縮する圧縮部と、前記圧縮部が圧縮した前記処理対象ブロックのデータと、前記生成した差分辞書とを出力する出力部と、を備える。
【０００９】
また、上記課題を解決するために、明細書開示のデータ伸長装置は、処理対象ブロック毎に、文字列と符号とが対応付けられて格納された辞書データである基準辞書に基づき、該処理対象ブロックに出現する文字列のうちで該基準辞書に登録されていない文字列と該基準辞書において前記処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書と、符号列である圧縮データとの入力を受け付ける入力部と、前記圧縮データを所定の規則に基づき複数のブロックに分割する分割部と、処理対象ブロック毎に、前記受け付けた基準辞書と該処理対象ブロックの差分辞書とに基づき、辞書データである処理対象辞書を生成する処理対象辞書生成部と、処理対象ブロック毎に、前記生成した処理対象辞書に基づいて、該処理対象ブロックを復号する復号部と、を備える。
【００１０】
また、上記課題を解決するために、明細書開示のデータ圧縮プログラムは、コンピュータに、テキストデータの入力を受け付ける入力ステップと、前記テキストデータを所定の規則に基づき複数のブロックに分割する分割ステップと、文字列と符号とが対応付けられて格納された辞書データである基準辞書に基づき、処理対象ブロックに出現する文字列のうち、該基準辞書に登録されていない文字列と、該基準辞書において前記処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書を生成する差分辞書生成ステップと、前記作成した差分辞書と前記基準辞書とに基づき、辞書データである処理対象辞書を生成する処理対象辞書生成ステップと、前記生成した処理対象辞書を参照し、前記処理対象ブロックに出現する文字列を対応する符号に置き換えることで、該処理対象ブロックを圧縮する圧縮ステップと、前記圧縮部が圧縮した前記処理対象ブロックのデータと、前記生成した差分辞書とを出力する出力ステップと、を実行させる。
【００１１】
上記課題を解決するために、明細書開示のデータ伸長プログラムは、コンピュータに、処理対象ブロック毎に、文字列と符号とが対応付けられて格納された辞書データである基準辞書に基づき、該処理対象ブロックに出現する文字列のうちで該基準辞書に登録されていない文字列と該基準辞書において前記処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書と、符号列である圧縮データとの入力を受け付ける入力ステップと、前記圧縮データを所定の規則に基づき複数のブロックに分割する分割ステップと、処理対象ブロック毎に、前記受け付けた基準辞書と該処理対象ブロックの差分辞書とに基づき、辞書データである処理対象辞書を生成する処理対象辞書生成ステップと、処理対象ブロック毎に、前記生成した処理対象辞書に基づいて、該処理対象ブロックを復号する復号ステップと、を実行させる。
【発明の効果】
【００１２】
明細書開示のデータ圧縮装置、及びデータ圧縮プログラムによれば、ブロックストリーム処理において、テキストデータの圧縮率を向上できる。
【００１３】
明細書開示のデータ伸長装置、及びデータ伸長プログラムによれば、ブロックストリーム処理において、テキストデータの圧縮率を向上させた圧縮データを、伸長できる。
【図面の簡単な説明】
【００１４】
【図１】実施例に係るデータ圧縮装置を含むシステム構成の一例を示す図である。
【図２】データ圧縮装置のハードウェア構成の一例を示す図である。
【図３】データ圧縮装置が有する機能を実現する手段の一例を示す機能ブロック図である。
【図４】辞書型符号化方式の概要を説明する図である。
【図５】データ圧縮装置が実行するデータ圧縮処理の一例を示すフローチャートである。
【図６】辞書更新処理の一例を示すフローチャートである。
【図７】被圧縮データの一例を示す図である。
【図８】圧縮データを作成する過程の一例を説明するための図である。
【図９】差分辞書作成処理の一例を示すフローチャートである。
【図１０】圧縮データを作成する過程の一例を説明するための図である。
【図１１】圧縮データを作成する過程の一例を説明するための図である。
【図１２】圧縮データを作成する過程の一例を説明するための図である。
【図１３】圧縮データを作成する過程の一例を説明するための図である。
【図１４】圧縮データを作成する過程の一例を説明するための図である。
【図１５】圧縮データを作成する過程の一例を説明するための図である。
【図１６】圧縮データを作成する過程の一例を説明するための図である。
【図１７】圧縮データの一例を示す図である。
【図１８】比較例１、比較例２及び実施例により作成される圧縮データの一例を説明するための図である。
【図１９】比較例１、比較例２及び実施例により作成される圧縮データの一例を説明するための図である。
【図２０】比較例１、比較例２、及び実施例による圧縮データのサイズ比較の一例を示す模式図である。
【図２１】実施例に係るデータ伸長装置を含むシステム構成の一例を示す図である。
【図２２】データ伸長装置が有する機能を実現する手段の一例を示す機能ブロック図である。
【図２３】データ伸長処理の一例を示すフローチャートである。
【図２４】圧縮データを伸長する過程の一例を説明するための図である。
【図２５】辞書復元処理の一例を示すフローチャートである。
【図２６】圧縮データを伸長する過程の一例を説明するための図である。
【図２７】圧縮データを伸長する過程の一例を説明するための図である。
【図２８】データ圧縮／伸長装置を含むシステム構成の一例を示す図である。
【発明を実施するための形態】
【００１５】
以下、本件の実施形態について、添付図面を参照しつつ説明する。
［データ圧縮装置］
【００１６】
本件のデータ圧縮装置について説明する。図１は本件のデータ圧縮装置を含むシステム構成の一例を示す図である。図１に示すように、データ圧縮装置１００は、ネットワーク４０を介して、記憶装置１０、センサ装置２０、及びデータ処理装置３０と接続されている。
【００１７】
記憶装置１０は、ハードディスクドライブ等で構成され、圧縮対象のデータ（以後、被圧縮データと記載する）、及び圧縮後のデータを格納する。
【００１８】
センサ装置２０は、例えば、企業の従業員出入り口に設置される入退出管理装置である。センサ装置２０は、センサにより取得したデータをデータ圧縮装置１００へ送信する。例えば、センサ装置２０は、従業員が所持するＩＤカードの情報を取得して、従業員番号、氏名、及び勤務地を被圧縮データとしてデータ圧縮装置１００へ送信する。センサ装置２０は、センサと、センサが取得したデータを処理する情報処理装置とからなるセンサネットワークであっても良い。
【００１９】
データ処理装置３０は、パーソナルコンピュータ等で構成され、入力されたデータに対し、演算等の予め定められたデータ処理を行う。データ処理装置３０は、予め定められた処理を施したデータを被圧縮データとして、データ圧縮装置１００へ送信する。また、データ処理装置３０は、データ圧縮装置１００から、データ圧縮装置１００が圧縮したデータを受け付ける。
【００２０】
ネットワーク４０は、例えば、ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等で構成される。ネットワーク４０は、センサ装置２０、データ処理装置３０、及びデータ圧縮装置１００が送信するデータを、送信先に伝送する。
【００２１】
データ圧縮装置１００は、記憶装置１０、センサ装置２０、及びデータ処理装置３０から被圧縮データを受信する。被圧縮データは、ＣＳＶ形式、ＸＭＬ形式等の構造を有するテキストデータである。データ圧縮装置１００は、被圧縮データを複数のブロックに分割し、ブロック毎に圧縮処理を実行して圧縮データを生成する。データ圧縮装置１００は、圧縮データを記憶装置１０へ格納する。または、データ圧縮装置１００は、圧縮データをデータ処理装置３０へ送信する。
【００２２】
次に、図２を用いてデータ圧縮装置１００のハードウェア構成について説明する。図２に示すように、データ圧縮装置１００は、入出力部１０１、ＲＯＭ(Read Only Memory)１０２、中央処理装置（ＣＰＵ:Central Processing Unit）１０３、及びＲＡＭ(Random Access Memory)１０４を備える。
【００２３】
入出力部１０１は、記憶装置１０、センサ装置２０、及びデータ処理装置３０から被圧縮データを受け付ける。また、入出力部１０１は、圧縮データを記憶装置１０、及びデータ処理装置３０へ出力する。ＲＯＭ１０２は、被圧縮データを圧縮するためのプログラム等を格納する。ＣＰＵ１０３は、ＲＯＭ１０２に格納されたプログラムを読み込んで実行する。ＲＡＭ１０４は、プログラムを実行する際に使用される一時的なデータを保存する。また、ＲＯＭ１０２に格納されたプログラムのＣＰＵ１０３による演算によって、図３に示すデータ圧縮装置１００が有する機能が実現される。
【００２４】
次に、図３を参照して、データ圧縮装置１００が有する機能の一例について説明する。図３は、データ圧縮装置１００が有する機能を実現する手段の一例を示す機能ブロック図である。
【００２５】
データ圧縮装置１００は、データ取得部１１０、辞書作成部１１１、差分辞書作成部１１２、符号化部１１３、及び出力部１１４を備える。
【００２６】
データ取得部１１０は、記憶装置１０、センサ装置２０、及びデータ処理装置３０等が送信した被圧縮データ（テキストデータ）を受け付ける入力部としての機能と、被圧縮データを所定の規則に基づき複数のブロックに分割する分割部としての機能を有する。データ取得部１１０は、分割した被圧縮データを、辞書作成部１１１に出力する。
【００２７】
辞書作成部１１１（処理対象辞書生成部）は、被圧縮データを所定の規則に基づき分割した複数ブロックのうち、圧縮処の対象となるブロック（以後、処理対象ブロックという）のデータを符号化する際に必要な辞書を、データ取得部１１０から入力されたデータを元に作成する。辞書は、符号項目と、値項目とを有しており、辞書作成部１１１は、処理対象ブロックのデータに出現する文字列を値項目に登録し、文字列に対応付けられる所定の符号を符号項目に登録する。例えば、入力データが図４（１）に示すデータであり、符号化する項目が「地区」の場合、辞書作成部１１１は、地区の列に出現する文字列と、所定の符号とを対応付けた、図４（２）に示す辞書を作成する。
【００２８】
符号化部１１３（圧縮部）は、ブロック毎に、辞書作成部１１１が作成した辞書を用いて、データを符号化し、出力部１１４に出力する。例えば、符号化部１１３は、図４（２）に示した辞書を用いて、図４（１）の「地区」の文字列を符号に置換することによって被圧縮データを符号化する。符号化されたデータは、図４（３）となる。
【００２９】
差分辞書作成部１１２（差分辞書生成部）は、差分辞書を作成し、出力部１１４へ出力する。差分辞書作成部１１２は、処理対象ブロックとは異なる基準ブロックの符号化に用いた辞書と、処理対象ブロックに含まれる符号化対象の文字列とに基づいて差分辞書を作成する。差分辞書は、符号化に使用される辞書と同様に、符号項目と値項目とを有する。差分辞書作成部１１２は、処理対象ブロックに出現する文字列のうち、基準ブロックの符号化に用いた辞書に登録されていない文字列を差分辞書の値項目に登録する。また、差分辞書作成部１１２は、差分辞書に登録した文字列に対して、基準ブロックの辞書において、基準ブロックの辞書には登録されているが処理対象ブロックには出現しない文字列に対応付けられている符号を割り当てる。例えば、基準ブロックの辞書が図４（４）であり、処理対象ブロックに含まれる符号化対象の文字列が図４（５）であるとする。この場合、差分辞書作成部１１２は、処理対象ブロックには出現するが基準ブロックの辞書には登録されていない文字列「Ｎｅｗ Ｙｏｒｋ」を差分辞書に登録する。また、差分辞書作成部１１２は、処理対象ブロックには出現しないが基準ブロックには登録されている文字列「Ｌａｓ Ｖｅｇａｓ」に割り当てられている符号「３」を、差分辞書に登録した文字列「Ｎｅｗ Ｙｏｒｋ」に対して割り当てる。その結果、差分辞書は図４（６）となる。
【００３０】
出力部１１４は、差分辞書と符号化されたデータとを、ブロック毎に、記憶装置１０、又は、データ処理装置３０に出力する。
【００３１】
次に、データ圧縮装置１００が実行する処理の一例について、図５及び図６を用いて説明する。図５は、データ圧縮装置１００が実行する圧縮処理の一例を示すフローチャートである。本実施例では、連続する２つのブロックにおける前方のブロックを基準ブロックと記載し、後方のブロックを処理対象ブロックと記載する。
【００３２】
辞書作成部１１１は、基準ブロックの辞書Ｄｉｃ０を空テーブルで初期化する（ステップＳ１０）。これは、被圧縮データの最初のブロックが処理対象ブロックである場合、基準ブロックが存在しないためである。
【００３３】
次に、辞書作成部１１１は、処理対象ブロックの符号化に使用する辞書（処理対象辞書）Ｄｉｃ１、及び読み込んだレコード数をカウントするための変数Ｍをそれぞれ初期化する（ステップＳ１２）。初期化によって、辞書Ｄｉｃ１は空テーブルとなり、Ｍの値は０となる。
【００３４】
データ取得部１１０は、被圧縮データに処理するレコードが存在するか否か判定する（ステップＳ１４）。データ取得部１１０は、処理するレコードが存在する場合（ステップＳ１４／ＹＥＳ）、レコードを取得し、Ｍに１を加算する（ステップＳ１６）。
【００３５】
次に、辞書作成部１１１は、処理対象ブロックの辞書を作成するため、辞書更新処理を実行する（ステップＳ１８）。ここで、ステップＳ１８の辞書更新処理について、図６を用いて説明する。
【００３６】
図６は、処理対象ブロックの辞書を作成する辞書更新処理の一例を示すフローチャートである。
【００３７】
辞書作成部１１１は、取得したレコードに含まれる文字列が辞書Ｄｉｃ１のエントリに存在するか否か判定する（ステップＳ５０）。辞書作成部１１１は、取得したレコードに含まれる文字列が辞書Ｄｉｃ１のエントリに存在しない場合（ステップＳ５０／ＮＯ）、文字列と符号とを対応付けたエントリを辞書Ｄｉｃ１に新規登録し（ステップＳ５２）、更新処理を終了する。一方、辞書作成部１１１は、取得したレコードに含まれる文字列が辞書Ｄｉｃ１のエントリに存在する場合、更新処理を終了する。
【００３８】
図５に戻り、圧縮処理の一例について説明を続ける。データ取得部１１０は、Ｍの値が、予め定められた値ＭＢよりも小さいか否か判定する（ステップＳ２０）。ここで、ＭＢは、１ブロックに含まれるレコード数を定める。ＭＢの値は、被圧縮データが保持していても良いし、ユーザが予め決定しておいても良い。また、ＭＢの値は、全ブロックを通して同一でも良いし、ブロック毎に異なっても良い。
【００３９】
Ｍの値がＭＢの値よりも小さい場合、処理対象ブロックのレコードが、未だ全て読み込まれていないことを意味する。従って、データ取得部１１０は、Ｍの値がＭＢの値よりも小さい場合（ステップＳ２０／ＹＥＳ）、ステップＳ１４に戻って処理を継続する。
【００４０】
Ｍの値がＭＢの値と等しい場合、処理対象ブロックのレコードが全て読みこまれたことを意味する。そこで、データ取得部１１０が、Ｍの値がＭＢの値と等しいと判定すると（ステップＳ２０／ＮＯ）、差分辞書作成部１１２は、差分辞書作成処理（ステップＳ２２）を実行する。差分辞書作成処理の詳細については後述する。
【００４１】
出力部１１４は、差分辞書作成部１１２が差分辞書作成処理で作成した差分辞書Δを出力する（ステップＳ２４）。次に、辞書作成部１１１は、基準ブロックの辞書Ｄｉｃ０と差分辞書Δとをマージして符号化用の辞書を構築し、それを新たな辞書Ｄｉｃ１とする（ステップＳ２６）。具体的には、辞書Ｄｉｃ０と差分辞書Δとの間で重複する符号がある場合には、重複する符号に対応付けられた辞書Ｄｉｃ０の文字列を、差分辞書Δの文字列で置換する。また、辞書Ｄｉｃ０に登録されていない符号が差分辞書Δに登録されている場合には、辞書Ｄｉｃ０に差分辞書Δのエントリを追加する。つまり、符号化部１１３が使用する辞書Ｄｉｃ１は、処理対象ブロックに出現する文字列のうち、基準ブロックで使用された辞書に定義されている文字列には、基準ブロックの辞書と同一の符号が割り当てられた辞書となる。また、辞書Ｄｉｃ１は、基準ブロックの辞書に登録されていない文字列には、基準ブロックの辞書において処理対象ブロックに出現しない文字列に対応付けられた符号が割り当てられた辞書となる。
【００４２】
符号化部１１３は、ステップＳ２６で更新された辞書Ｄｉｃ１を使用して、処理対象ブロックに出現する文字列を符号化する（ステップＳ２８）。出力部１１４は、符号化部１１３が符号化したデータを出力する（ステップＳ３０）。ステップＳ２４及びステップＳ３０の処理によって、処理対象ブロックの圧縮データが作成される。
【００４３】
辞書作成部１１１は、次ブロックの圧縮処理のために、辞書Ｄｉｃ０を初期化し（ステップＳ３２）、ステップＳ１２の処理へ戻る。本フローチャートでは、連続する２つのブロックのうち、前方のブロックを基準ブロック、後方のブロックを処理対象ブロックとしている。従って、今回処理したブロックは次に処理するブロックの基準ブロックとなるので、辞書Ｄｉｃ０は、辞書Ｄｉｃ１で初期化される。
【００４４】
データ取得部１１０は、処理するレコードが存在しない場合（ステップＳ１４／ＮＯ）、Ｍの値が０か否か判定する（ステップＳ３４）。
【００４５】
Ｍの値が０の場合とは、次のブロックが存在しない場合である。従って、データ取得部１１０はＭの値が０の場合（ステップＳ３４／ＹＥＳ）、データ圧縮処理を終了する。
【００４６】
Ｍの値が０ではない場合とは、最後の処理対象ブロックに存在するデータの読込が全て終了した場合である。そこで、データ取得部１１０が、Ｍの値が０ではないと判定すると（ステップＳ３４／ＮＯ）、差分辞書作成部１１２はステップＳ２２、出力部１１４はステップＳ２４及びステップＳ３０、符号化部１１３はステップＳ２８、辞書作成部１１１はステップＳ２６の処理をそれぞれ実行する。ステップＳ２２〜ステップＳ３０の処理は、前述した各ステップの処理と同じであるため、説明を省略する。以上の処理により、被圧縮データは、ブロック毎に差分辞書と符号化データを含んで圧縮される。
【００４７】
次に、図７〜図１７を参照しつつ、具体的なデータを用いて、上述した圧縮処理によるデータ圧縮について説明すると共に、差分辞書作成処理の詳細について説明する。図７は、本説明で用いる被圧縮データの一例である。本実施例では、地区項目に入力されている文字列を符号化した圧縮データを作成するとする。また、３レコード（つまり、ＭＢ＝３）を１ブロックとして、ブロックストリーム処理によりデータを圧縮するものとする。
【００４８】
データ圧縮装置１００は、図５のステップＳ１０及びＳ１２の初期化処理を行う。次に、処理対象となるレコードが存在するため（ステップＳ１４／ＹＥＳ）、データ取得部１１０が、図８（１）に示す１行目のレコードを取得する（ステップＳ１６）。
【００４９】
次に、辞書作成部１１１が、辞書Ｄｉｃ１の更新処理（ステップＳ１８）を実行する。この時点で辞書Ｄｉｃ１は空テーブルであるため、辞書Ｄｉｃ１において、Ｓａｎ Ｆｒａｎｃｉｓｃｏを値項目に有するエントリは存在しない（ステップＳ５０／ＮＯ）。従って、辞書作成部１１１は、Ｓａｎ Ｆｒａｎｃｉｓｃｏに符号「１」を割り当てたエントリを辞書Ｄｉｃ１に新規登録し（ステップＳ５２）、処理を終了する。更新後の辞書Ｄｉｃ１は図８（２）となる。
【００５０】
Ｍ（＝１）＜ＭＢ（＝３）であり（ステップＳ２０／ＹＥＳ）、次のレコードが存在するため（ステップＳ１４／ＹＥＳ）、データ取得部１１０は、図８（３）に示す２行目のレコードを取得する（ステップＳ１６）。
【００５１】
図６の辞書更新処理において、Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．は、辞書Ｄｉｃ１に存在しないため（ステップＳ５０／ＮＯ）、辞書作成部１１１は、Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．に符号「２」を割り当てたエントリを辞書Ｄｉｃ１に新規登録し（ステップＳ５２）、処理を終了する。更新後の辞書Ｄｉｃ１は、図８（４）となる。
【００５２】
Ｍ（＝２）＜ＭＢ（＝３）であり（ステップＳ２０／ＹＥＳ）、次のレコードが存在するため（ステップＳ１４／ＹＥＳ）、データ取得部１１０は、図８（５）に示す３行目のレコードを入力する。
【００５３】
図６の辞書更新処理において、Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．は、既に辞書Ｄｉｃ１に存在しているため（ステップＳ５０／ＹＥＳ）、辞書作成部１１１は、辞書Ｄｉｃ１にエントリは新規登録せず、処理を終了する。
【００５４】
Ｍ（＝３）がＭＢ（＝３）と一致するため（ステップＳ２０／ＮＯ）、差分辞書作成部１１２が、差分辞書作成処理（ステップＳ２２）を実行する。
【００５５】
ここで、具体例を用いながら、差分辞書作成処理について説明する。図９は、差分辞書作成処理の一例を示すフローチャートである。
【００５６】
差分辞書作成部１１２は、差分辞書Δを基準ブロックの辞書Ｄｉｃ０で初期化する（ステップＳ６０）。なお、最初のブロックでは、辞書Ｄｉｃ０は空集合となっているため、差分辞書Δも空集合となる。
【００５７】
次に、差分辞書作成部１１２は、基準ブロックの辞書Ｄｉｃ０の値項目の集合と、更新処理を実行した辞書Ｄｉｃ１の値項目の集合との差集合Ｄｉｆｆ０を求める（ステップＳ６２）。図９では、辞書Ｄｉｃ０の値項目の集合をＤｉｃ０．ｖａｌ、辞書Ｄｉｃ１の値項目の集合を辞書Ｄｉｃ１．ｖａｌと記載する。
【００５８】
次に、差分辞書作成部１１２は、辞書Ｄｉｃ１の値項目の集合と、辞書Ｄｉｃ１の値項目の集合との差集合Ｄｉｆｆ１を求める（ステップＳ６４）。更に、差分辞書作成部１１２は辞書Ｄｉｃ１の値項目の集合と、辞書Ｄｉｃ０の値項目の集合との積集合ＮｏＤｉｆｆを求める（ステップＳ６６）。
【００５９】
図８に示した具体例において、辞書Ｄｉｃ０の値項目の集合Ｄｉｃ０．ｖａｌは空集合であり、辞書Ｄｉｃ１の値項目の集合Ｄｉｃ１．ｖａｌ＝｛Ｓａｎ Ｆｒａｎｃｉｓｃｏ，Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．｝である。この場合、辞書Ｄｉｃ０には存在するが辞書Ｄｉｃ１には存在しない値項目は、存在しない。従って、ステップＳ６２の処理を実行すると、差集合Ｄｉｆｆ０は空集合となる。また、辞書Ｄｉｃ０には存在しないが辞書Ｄｉｃ１には存在する値項目は、Ｓａｎ Ｆｒａｎｃｉｓｃｏ及びＷａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．である。従って、ステップＳ６４の処理を実行すると、差集合Ｄｉｆｆ１＝｛Ｓａｎ Ｆｒａｎｃｉｓｃｏ，Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．｝となる。更に、辞書Ｄｉｃ０と、辞書Ｄｉｃ１との間に共通する値項目は存在しないため、ステップＳ６６の処理を実行すると、積集合ＮｏＤｉｆｆは空集合となる。
【００６０】
次に、差分辞書作成部１１２は、Ｄｉｆｆ１が空集合か否か判定する（ステップＳ６８）。差分辞書作成部１１２は、Ｄｉｆｆ１が空集合ではない場合（ステップＳ６８／ＮＯ）、差分辞書作成部１１２は、Ｄｉｆｆ０が空集合か否か判定する（ステップＳ７０）。
【００６１】
差分辞書作成部１１２は、Ｄｉｆｆ０が空集合の場合（ステップＳ７０／ＹＥＳ）、Ｄｉｆｆ１の全ての要素を差分辞書Δに新規登録する（ステップＳ７６）。そして、差分辞書作成部１１２は、ＮｏＤｉｆｆの要素と一致する値を持つエントリを差分辞書Δから全て除去し（ステップＳ７８）、差分辞書Δを辞書作成部１１１及び出力部１１４に出力する（ステップＳ８０）。
【００６２】
具体例では、Ｄｉｆｆ１は空集合ではなく（ステップＳ６８／ＮＯ）、Ｄｉｆｆ０は空集合である（ステップＳ７０／ＹＥＳ）。したがって、差分辞書作成部１１２は、ステップＳ７６の処理を実行する。ステップＳ７６の処理実行後の差分辞書Δは図１０（１）となる。また、具体例において、ＮｏＤｉｆｆは空集合であるため、ステップＳ７８において、差分辞書Δから除去するエントリは存在しない。従って、差分辞書作成部１１２は、ステップＳ８０の処理を実行し、図１０（１）に示す差分辞書Δを辞書作成部１１１及び出力部１１４に出力する。図９の差分辞書作成処理における他のステップについては、後述する。
【００６３】
差分辞書作成処理が終了すると、出力部１１４が差分辞書Δを圧縮データの一部として出力する（ステップＳ２４）。次に、辞書作成部１１１は、辞書Ｄｉｃ０と差分辞書Δとに基づいて、辞書Ｄｉｃ１を更新する（ステップＳ２６）。今回は、辞書Ｄｉｃ０が空集合であるため、差分辞書Δのエントリが辞書Ｄｉｃ０に追加され、符号化に使用される辞書Ｄｉｃ１となる（図１０（２））。
【００６４】
符号化部１１３は、図１０（２）に示す、辞書作成部１１１が作成した辞書を用いて、図１０（３）に示すように、１行目〜３行目までのレコードを符号化する。
【００６５】
上述のように符号化されたブロックＢ１は、次に圧縮処理が実行されるブロックの基準ブロックとなる。従って、辞書作成部１１１は、ブロックＢ１の辞書Ｄｉｃ１で、辞書Ｄｉｃ０を初期化する（ステップＳ３２）。初期化された辞書Ｄｉｃ０は、図１１（１）となる。
【００６６】
次に、データ取得部１１０は、図１１（２）に示す、ブロックＢ２の１行目のレコードを取得する（ステップＳ１６）。新しいブロックの処理を開始するにあたり、ステップＳ１２において辞書Ｄｉｃ１は初期化されて空テーブルとなっており、辞書Ｄｉｃ１には、Ｓａｎ Ｆｒａｎｃｉｓｃｏの値を持つエントリが存在しない（ステップＳ５０／ＮＯ）。従って、図６の辞書更新処理により、辞書Ｄｉｃ１には、図１１（３）に示す、Ｓａｎ Ｆｒａｎｃｉｓｃｏに符号「１」を割り当てたエントリが新規登録される（ステップＳ５２）。
【００６７】
データ取得部１１０は、同様にして、図１１（４）に示す、ブロックＢ２の２行目のレコードを取得する（ステップＳ１６）。辞書Ｄｉｃ１には、Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．の値を持つエントリが存在しないため（ステップＳ５０／ＮＯ）、図１１（５）に示すように、Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．に符号「２」を割り当てたエントリが、辞書Ｄｉｃ１に新規登録される（ステップＳ５２）。
【００６８】
データ取得部１１０は、次に、図１１（６）に示す、ブロックＢ２の３行目のレコードを取得する（ステップＳ１６）。辞書Ｄｉｃ１には、Ｎｅｗ Ｙｏｒｋの値を持つエントリが存在しないため（ステップＳ５０／ＮＯ）、図１１（７）に示すように、Ｎｅｗ Ｙｏｒｋに符号「３」を割り当てたエントリが、辞書Ｄｉｃ１に新規登録される（ステップＳ５２）。
【００６９】
ここで、Ｍの値が３となり、所定のレコード数を読み込んだため（ステップＳ２０／ＮＯ）、差分辞書作成部１１２が差分辞書作成処理（ステップＳ２２）を行う。
【００７０】
ステップＳ２２では、前述した図９のステップＳ６０〜ステップＳ６６の処理を、差分辞書作成部１１２が実行する。その結果、初期化された差分辞書Δは、図１２（１）となり、Ｄｉｆｆ０は空集合、Ｄｉｆｆ１＝｛Ｎｅｗ Ｙｏｒｋ｝、ＮｏＤｉｆｆ＝｛Ｓａｎ Ｆｒａｎｃｉｓｃｏ，Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．｝となる。
【００７１】
Ｄｉｆｆ１が空集合ではなく（ステップＳ６８／ＮＯ）、Ｄｉｆｆ０が空集合であるため（ステップＳ７０／ＹＥＳ）、Ｄｉｆｆ１の要素が差分辞書Δに新規登録される（ステップＳ７６）。その結果、具体例において、ステップＳ７６の処理実行後の差分辞書Δは図１２（２）となる。
【００７２】
次に、差分辞書作成部１１２は、ステップＳ７８の処理を実行する。具体例では、ＮｏＤｉｆｆの要素（Ｓａｎ ＦｒａｎｃｉｓｃｏとＷａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．）を値に持つエントリが、現在の差分辞書Δに存在する。従って、差分辞書作成部１１２は、差分辞書Δから、（Ｓａｎ ＦｒａｎｃｉｓｃｏとＷａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．）を値に持つエントリを削除し（ステップＳ７８）、差分辞書Δを出力部１１４及び辞書作成部１１１に出力する（ステップＳ８０）。出力される差分辞書Δは、図１２（３）となる。
【００７３】
次に、辞書作成部１１１は、図１３（１）に示す辞書Ｄｉｃ０と、図１３（２）に示す差分辞書Δとに基づいて、辞書Ｄｉｃ１を更新する（ステップＳ２６）。この場合、差分辞書Δに含まれる符号「３」は、辞書Ｄｉｃ０には登録されていない符号であるので、辞書Ｄｉｃ０に差分辞書Δのエントリを追加したものを、辞書Ｄｉｃ１とする。その結果、辞書Ｄｉｃ１は図１３（３）となる。
【００７４】
符号化部１１３は、図１３（３）の辞書を用いて、ブロックＢ２のデータを符号化する（ステップＳ２８）。符号化されたデータは図１３（４）となる。
【００７５】
ブロックＢ２は、次に圧縮処理が実行されるブロックの基準ブロックとなる。従って、辞書作成部１１１は、ブロックＢ２の辞書Ｄｉｃ１で、辞書Ｄｉｃ０を初期化する（ステップＳ３２）。初期化された辞書Ｄｉｃ０は、図１４（１）となる。
【００７６】
次に、データ取得部１１０は、図１４（２）に示す、ブロックＢ３の１行目のレコードを取得する（ステップＳ１６）。新しいブロックの処理を開始するにあたり、辞書Ｄｉｃ１は初期化されて空テーブルとなっているため、辞書Ｄｉｃ１には、Ｃｈｉｃａｇｏの値を持つエントリは存在しない（ステップＳ５０／ＮＯ）。従って、辞書更新処理により、辞書Ｄｉｃ１には、図１４（３）に示す、Ｃｈｉｃａｇｏに符号「１」を割り当てたエントリが新規登録される（ステップＳ５２）。
【００７７】
データ取得部１１０は、図１３（４）に示す、ブロックＢ３の２行目のレコードを取得する（ステップＳ１６）。辞書Ｄｉｃ１には、Ｓａｎ Ｆｒａｎｃｉｓｃｏの値を持つエントリが存在しないため（ステップＳ５０／ＮＯ）、図１４（５）に示すように、Ｓａｎ Ｆｒａｎｃｉｓｃｏに符号「２」を割り当てたエントリが辞書Ｄｉｃ１に新規登録される（ステップＳ５２）。
【００７８】
データ取得部１１０は、次に、図１４（６）に示す、ブロックＢ３の３行目のレコードを取得する（ステップＳ１６）。辞書Ｄｉｃ１には、Ｓａｎ Ｆｒａｎｃｉｓｃｏの値を持つエントリが既に存在するので（ステップＳ５０／ＹＥＳ）、辞書Ｄｉｃ１は変更されず、図１４（５）のままである。
【００７９】
ここで、Ｍの値が３となり、所定のレコード数を読み込んだため（ステップＳ２０／ＮＯ）、差分辞書作成部１１２が差分辞書作成処理（ステップＳ２２）を行う。
【００８０】
ステップＳ２２では、前述した図９のステップＳ６０〜ステップＳ６６の処理を、差分辞書作成部１１２が実行する。その結果、具体例において、初期化された差分辞書Δは図１５（１）となる。また、Ｄｉｆｆ０＝｛Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．，Ｎｅｗ Ｙｏｒｋ｝、Ｄｉｆｆ１＝｛Ｃｈｉｃａｇｏ｝、ＮｏＤｉｆｆ＝｛Ｓａｎ Ｆｒａｎｃｉｓｃｏ｝となる。具体例において、Ｄｉｆｆ１は空集合ではなく（ステップＳ７０／ＮＯ）、Ｄｉｆｆ０も空集合ではない（ステップＳ７０／ＮＯ）。
【００８１】
図９のフローチャートにおいて、差分辞書作成部１１２は、Ｄｉｆｆ０が空集合ではない場合（ステップＳ７０／ＮＯ）、集合Ｄｉｆｆ０の要素ｄ０、集合Ｄｉｆｆ１の要素ｄ１を取得し、差分辞書Δにおけるｄ０をｄ１に置換する。そして、差分辞書作成部１１２は、Ｄｉｆｆ０から要素ｄ０を、Ｄｉｆｆ１から要素ｄ１をそれぞれ削除する（ステップＳ７２）。その後、差分辞書作成部１１２は、ステップＳ６８に戻り処理を継続する。
【００８２】
具体例で、差分辞書Δにおいて、Ｄｉｆｆ０の要素であるＷａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．が、Ｄｉｆｆ１の要素であるＣｈｉｃａｇｏで置換される。また、Ｄｉｆｆ０からＷａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．が削除され、Ｄｉｆｆ１からＣｈｉｃａｇｏが削除される。その結果、ステップＳ７２実行後の差分辞書Δは、図１５（２）となり、また、Ｄｉｆｆ０＝｛Ｎｅｗ Ｙｏｒｋ｝、Ｄｉｆｆ１は空集合となる。Ｄｉｆｆ１が空集合であるとは、基準ブロックの辞書Ｄｉｃ０に存在するが処理対象ブロックには出現しない文字列の数が、辞書Ｄｉｃ０には存在しないが処理対象ブロックには出現する文字列の数を超えているということである。
【００８３】
そこで、図９のフローチャートにおいて、差分辞書作成部１１２は、Ｄｉｆｆ１が空集合の場合（ステップＳ６８／ＹＥＳ）、差分辞書Δにおいて、Ｄｉｆｆ０の要素と一致する値を全てＮＵＬＬに置換する（ステップＳ７４）。次に、差分辞書作成部１１２は、Ｎｏｄｉｆｆの要素と一致する値を持つエントリを差分辞書Δから全て除去し（ステップＳ７８）、差分辞書Δを出力部１１４及び辞書作成部１１１出力する（ステップＳ８０）。
【００８４】
具体例においては、差分辞書Δにおいて、Ｄｉｆｆ０の要素であるＮｅｗ ＹｏｒｋがＮＵＬＬに置換される（ステップＳ７４）。この処理の結果、ステップＳ７４実行後の差分辞書Δは図１５（３）となる。そして、差分辞書作成部１１２は、ステップＳ７８において、現在の差分辞書ΔからＮｏＤｉｆｆの要素（Ｓａｎ Ｆｒａｎｃｉｓｃｏ）の値を持つエントリを除去する。その結果、ステップＳ８０で出力される差分辞書Δは、図１５（４）となる。
【００８５】
次に、辞書作成部１１１は、図１６（１）に示す辞書Ｄｉｃ０と、図１６（２）に示す差分辞書Δとに基づいて、ブロックＢ３の符号化に用いる辞書Ｄｉｃ１を更新する（ステップＳ２６）。辞書Ｄｉｃ０と差分辞書Δとは、符号「２」及び「３」が重複するので、辞書Ｄｉｃ０において、符号「２」及び「３」が割り当てられている文字列を、差分辞書Δの文字列で上書きし、辞書Ｄｉｃ１を更新する。その結果、辞書Ｄｉｃ１は、図１６（３）となる。
【００８６】
符号化部１１３は、図１６（３）に示される辞書Ｄｉｃ１を用いて、ブロックＢ３のデータを符号化する（ステップＳ２８）。符号化されたデータは、図１６（４）となる。
【００８７】
このようにして、図７に示す被圧縮データは、図１７に示すように、ブロック毎に、差分辞書Δと符号化データとを有する圧縮データとなり出力される。
【００８８】
以上の説明から明らかなように、本実施例に係るデータ圧縮装置は、ブロックにおいて、処理対象ブロックに出現する文字列のうち、基準辞書に登録されていない文字列と、基準辞書において処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書を生成する。これにより、ブロックストリーム処理においてテキストデータを圧縮する場合、ブロック毎に差分辞書と符号化データとを含む圧縮データを作成し、かつ差分辞書で文字列に割り当てる符号を再利用して、圧縮率を向上させることができる。
【００８９】
ここで、図１８及び図１９を用いて、比較例１及び２と、本実施例とによる被圧縮データの圧縮率を比較する。図１８（１）は、本説明で使用する被圧縮データを示す。本説明では、４レコードを１ブロックとして処理することとする。
【００９０】
まず、比較例１による圧縮データの作成について説明する。図１８（２）は、比較例１により被圧縮データを圧縮した場合のデータ例である。比較例１は、ブロック毎に、ブロックに出現する文字列と、符号とを対応付けた辞書を登録して、圧縮データを作成する。また、ブロックが変わる都度、符号を１から採番し直す。
【００９１】
具体的に、図１８（１）のデータを用いて説明する。図１８（１）に示す被圧縮データのブロックＢ１において、ブロックに出現する文字列は、Ｓａｎ Ｆｒａｎｃｉｓｃｏ、Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．、Ｌｏｓ Ａｎｇｅｌｓ、Ｎｅｗ Ｏｒｌｅａｎｓの４つである。従って、比較例１では、上記４つの文字列と符号とを対応付けた辞書をブロックＢ１の辞書として登録し、図１８（２）に示すように、辞書と符号化データとを含むブロックＢ１の圧縮データを作成する。
【００９２】
次に、比較例１では、ブロックＢ２において、ブロックに出現するＷａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．、Ｎｅｗ Ｙｏｒｋ、Ｃｈｉｃａｇｏ、及びＬｏｓ Ａｎｇｅｌｓの４つの文字列と、符号とを対応付けた辞書をブロックＢ２の辞書として登録する。また、ブロックＢ３では、ブロックに出現するＷａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．、Ｎｅｗ Ｙｏｒｋ、Ｃｈｉｃａｇｏ、及びＬｏｓ Ａｎｇｅｌｓの４つの文字列と、符号とを対応付けた辞書をブロックＢ３の辞書として登録する。そして、ブロック毎に登録された辞書を用いて、被圧縮データを符号化する。その結果、比較例１の圧縮データは、図１８（２）となる。
【００９３】
次に、比較例２による圧縮データの作成について説明する。図１９（１）は、比較例２により被圧縮データを圧縮した場合のデータ例である。比較例２は、ブロック毎に、本実施例と同様の差分辞書を作成するが、差分辞書に登録される文字列に、新たに採番した符号を割り当てる。すなわち、比較例２は、基準ブロックには出現するが処理対象ブロックには出現しない文字列に対応付けられていた符号の再利用は行わない。
【００９４】
比較例２について、具体的に説明する。比較例２において、ブロックＢ１は最初の処理対象ブロックであるため、基準ブロックの辞書が存在しない。従って、ブロックＢ１については、比較例２においても、比較例１と同様のエントリを持つ差分辞書が登録される。次に、ブロックＢ２において、比較例２はブロックＢ１の辞書には登録されていないがブロックＢ２には出現する文字列に対して、差分辞書を登録する。つまり、Ｎｅｗ Ｙｏｒｋ、及びＣｈｉｃａｇｏの文字列を差分辞書に登録する。ここで、比較例２では、差分辞書に登録された文字列に、新たに採番した符号を割り当てる。ブロックＢ１において、符号は「４」まで使用されているので、比較例２は、新規の符号「５」及び「６」をＮｅｗ Ｙｏｒｋ及びＣｈｉｃａｇｏにそれぞれ割り当てる。ブロックＢ３では、ブロックＢ２の符号化に使用された辞書には存在しないがブロックＢ３には出現する文字列に対して、差分辞書を登録する。つまり、Ｌａｓ Ｖｅｇａｓ及びＭｅｘｉｃｏ Ｃｉｔｙの文字列を差分辞書に登録する。そして、ブロックＢ２の差分辞書を作成する際に、符号を「６」まで採番済みであるので、Ｌａｓ Ｖｅｇａｓ及びＭｅｘｉｃｏ Ｃｉｔｙには、新規の符号「７」及び「８」をそれぞれ割り当てる。以上のようにして、比較例２は、図１９（１）に示すように、差分辞書と符号化データとを含む圧縮データをブロック毎に作成する。
【００９５】
図１９（２）は、本実施例により図１８（１）の被圧縮データを圧縮した場合のデータ例である。本実施例において、ブロックＢ１は最初の処理対象ブロックであるため、基準ブロックの辞書が存在しない。従って、ブロックＢ１については、実施例においても、比較例１及び２と同様のエントリを持つ差分辞書が登録される。次に、ブロックＢ２において、実施例はブロックＢ１の辞書には登録されていないがブロックＢ２には出現する文字列に対して、差分辞書を登録する。つまり、Ｎｅｗ Ｙｏｒｋ、及びＣｈｉｃａｇｏの文字列を差分辞書に登録する。そして、実施例では、ブロックＢ１の辞書において、ブロックＢ１の辞書には登録されているがブロックＢ２には出現しない文字列に割り当てられている符号を再利用する。図１９（２）の例では、ブロックＢ２には出現しないＳａｎ Ｆｒａｎｃｉｓｃｏ及びＮｅｗ Ｏｒｌｅａｎｓに対して、ブロックＢ１の辞書で割り当てられている符号「１」及び「４」を再利用し、Ｎｅｗ Ｙｏｒｋ、及びＣｈｉｃａｇｏに対して割り当てる。また、ブロックＢ３では、ブロックＢ３には出現しないＬｏｓ Ａｎｇｅｌｓ及びＣｈｉｃａｇｏに対して、ブロックＢ２を符号化した辞書で割り当てられている符号「３」及び「４」を再利用し、Ｌａｓ Ｖｅｇａｓ及びＭｅｘｉｃｏ Ｃｉｔｙに割り当てる。以上のようにして、本実施例は、図１９（２）に示すように、差分辞書と符号化データとを含む圧縮データをブロック毎に作成する。
【００９６】
次に、比較例１及び２と、本実施例との圧縮率を比較する。
【００９７】
比較例１では、上述したように、ブロック毎に、ブロックに出現する文字列と符号とを対応付けた辞書を作成する。従って、図１８（２）に示すように、ブロック毎に登録された辞書間で重複した値を含むこととなる。例えば、ブロックＢ１の辞書と、ブロックＢ２の辞書とでは、Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．とＬｏｓ Ａｎｇｅｌｓとが重複している。また、ブロックＢ２の辞書とブロックＢ３の辞書とでは、Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．とＮｅｗ Ｙｏｒｋとが重複している。このため、比較例１では、辞書全体のサイズが大きくなり、圧縮率の悪化を引き起こす。
【００９８】
比較例２では、ブロックＢ２の辞書には、ブロックＢ１で出現する文字列は登録されず、ブロックＢ２で初めて出現した文字列のみが差分辞書に登録される。従って、比較例１と比較して、辞書サイズを小さくすることができる。
【００９９】
しかし、比較例２では、基準ブロックには出現しないが処理対象ブロックでは出現する文字列に、新たに採番した符号を割り当てる。従って、比較例１のようにブロック毎に辞書を出力する場合と比べて、符号数が増加してしまい、符号の符号長が長くなってしまう恐れがある。そこで、比較例２のように、符号を新たに採番する場合と、本実施例のように再利用する場合との間の圧縮率の違いについて説明する。
【０１００】
被圧縮データＤを、Ｎ個のブロックに分割したとする（Ｄ＝Ｂ１・Ｂ２・Ｂ３・・・ＢＮ）。すると、比較例２の場合、つまり、符号を再利用しない場合に必要な符号の総数は、最大で被圧縮データＤに含まれるエントリの数となる。一方、本実施例のように、符号を再利用する場合、必要な符号の総数は、最大で、ブロックＢｉ（ｉ＝１〜Ｎ）に含まれるエントリの数となる。
【０１０１】
符号化に整数を用いると仮定すると、比較例２の場合、符号が２５６種類までならば、符号長１バイトで符号化できるが、それ以上の場合、６５５３６種類までは符号長２バイトが必要となり、それ以上となると符号長はさらに長くなる。一方、本実施例の場合、必要な符号の総数は、最大でブロックＢｉに含まれるエントリ数であるため、１ブロックに含まれるレコード数を２５６以下とすれば、符号長が１バイトを超えることはない。
【０１０２】
図２０は、比較例１、比較例２、及び本実施例によってデータを圧縮した場合の、圧縮データのファイルサイズを模式的に示した図である。図２０中、ハッチングを施した部分は辞書データを表し、ハッチングを施していない部分は、符号化データを表す。図２０からもわかるように、比較例１と比較例２とでは、比較例２の方が、辞書サイズが小さくなるため、圧縮データサイズも小さくなる。
【０１０３】
また、比較例２と本実施例とでは、本実施例の方が、符号を再利用することのより、符号長が長くなる可能性を低減できるため、比較例２と比較して更に圧縮データサイズを小さくすることができる。つまり、本実施例では、差分辞書を用いることで、辞書に登録されるエントリ数を削減できるため、辞書データのファイルサイズを削減できる。更に、符号を再利用することによって、符号長を短くして、符号に必要なデータサイズを削減できるため、更に圧縮率を向上できる。
［データ伸長装置］
【０１０４】
次に、本件に係るデータ伸長装置について説明する。図２１は、本件に係るデータ伸長装置を含むデータ伸長システムの一構成例を示している。
【０１０５】
データ伸長装置２００は、ネットワーク４０を介して、記憶装置１０、及びデータ処理装置３０と接続している。
【０１０６】
記憶装置１０は、伸長対象のデータ（被伸長データと記載する）を格納している。また、データ伸長装置２００は、伸長されたデータを格納する。
【０１０７】
データ処理装置３０は、データ伸長装置２００に被伸長データを送信する。また、データ伸長装置２００が伸長したデータを受信する。
【０１０８】
データ伸長装置２００のハードウェア構成は、データ圧縮装置１００のハードウェア構成と同様であるため、説明を省略する。ただし、データ伸長装置２００の場合、ＲＯＭ１０２は、被伸長データを伸長するためのプログラムを格納する。また、ＲＯＭ１０２に格納されたプログラムのＣＰＵ１０３による演算によって、図２２に示すデータ伸長装置２００が有する機能が実現される。
【０１０９】
次に、図２２を用いて、データ伸長装置２００が有する機能を実現する手段について説明する。図２２は、データ伸長装置２００の機能ブロック図の一例である。
【０１１０】
図２２に示すように、データ伸長装置２００は、ブロック取得部２０１と、差分辞書及び圧縮データの入力を受け付ける入力部としての機能を実現するデータ取得部２０２及び差分辞書取得部２０３と、辞書復元部２０４と、復号部２０５と、出力部２０６とを備える。
【０１１１】
ブロック取得部２０１は、記憶装置１０から取得した、あるいは、データ処理装置３０から受信した、複数のブロックで構成された被伸長データを所定の規則に基づき複数のブロックに分割する分割部としての機能を有する。ブロック取得部２０１は、被伸長データから伸長処理の対象となるブロック（処理対象ブロック）を取得する。被伸長データを構成する各ブロックは、差分辞書と符号化データとを有する。
【０１１２】
データ取得部２０２は、ブロック取得部２０１が取得した処理対象ブロックから、符号化データを取得する。
【０１１３】
差分辞書取得部２０３は、処理対象ブロックから、差分辞書を取得する。
【０１１４】
辞書復元部２０４（処理対象辞書生成部）は、差分辞書取得部２０３が取得した差分辞書と、処理対象ブロックとは異なる基準ブロックの復号に使用した辞書とに基づいて、処理対象ブロックの符号化データを作成した際に使用された辞書（処理対象辞書）を復元する。本実施例では、連続する２つのブロックにおいて、前方のブロックを基準ブロックとし、後方のブロックを処理対象ブロックとする。
【０１１５】
復号部２０５は、辞書復元部２０４が復元した辞書を用いて、データ取得部２０２が取得した符号化データを復号する。
【０１１６】
出力部２０６は、復号部２０５が復号したブロックのデータを、記憶装置１０に格納する、または、データ処理装置３０に送信する。
【０１１７】
次に、データ伸長装置２００が実行する伸長処理について説明する。図２３は、データ伸長装置２００が実行する伸長処理の一例を示すフローチャートである。
【０１１８】
まず、辞書復元部２０４は、基準ブロックの辞書Ｄｉｃを空テーブルで初期化する（ステップＳ１００）。被伸長データの最初のブロックが処理対象ブロックである場合、基準ブロックが存在しないためである。
【０１１９】
ブロック取得部２０１は、被伸長データに処理対象となるブロックが存在するか否かを判定する（ステップＳ１０２）。ブロック取得部２０１は、ブロックが存在する場合には（ステップＳ１０２／ＹＥＳ）、ブロックを取得する（ステップＳ１０４）。ブロック取得部２０１は、ブロックが存在しない場合には（ステップＳ１０２／ＮＯ）、本処理を終了する。
【０１２０】
ブロック取得部２０１がブロックを取得すると（ステップＳ１０４）、差分辞書取得部２０３が取得されたブロックに含まれる差分辞書Δを取得する（ステップＳ１０６）。
【０１２１】
次に、辞書復元部２０４が、処理対象ブロックの復号に使用される辞書Ｄｉｃ１の復元処理を実行する（ステップＳ１０８）。辞書復元処理の詳細は後述する。
【０１２２】
復元部２０５は、ステップＳ１０８の処理で復元された辞書Ｄｉｃ１を用いて、符号化データを復号する（ステップＳ１１０）。
【０１２３】
出力部２０６は、復号されたデータを出力する（ステップＳ１１２）。次に、辞書復元部２０４が、処理対象ブロックの復号に使用した辞書Ｄｉｃ１を使用して、辞書Ｄｉｃを初期化する（ステップＳ１１４）。本実施例では、基準ブロックと処理対象ブロックとは連続する２つのブロックであるため、ステップＳ１１０で復号に使用した辞書Ｄｉｃ１が、次の処理対象ブロックに対する基準ブロックの辞書Ｄｉｃとなるからである。
【０１２４】
次に、具体的なデータを用いて、上述した伸長処理によるデータ伸長について説明するとともに、辞書復元処理の詳細について説明する。ここでは、図１７に示した圧縮データに伸長処理を施し、復号データを得るものとする。
【０１２５】
まず、ブロック取得部２０１が、ブロックＢ１を取得する（ステップＳ１０４）。差分辞書取得部２０３は、図２４（１）に示す、ブロックＢ１に含まれる差分辞書Δを取得する（ステップＳ１０６）。次に、辞書復元部２０４が辞書復元処理を実行する（ステップＳ１０８）。
【０１２６】
ここで、辞書復元処理について、具体例を参照しつつ説明する。図２５は辞書復元処理の一例を示すフローチャートである。辞書復元部２０４は、まず、処理対象ブロックのデータ復号に使用される辞書Ｄｉｃ１及び、集合ＤｉｆｆＩＤを初期化する（ステップＳ１２０）。辞書復元部２０４は、辞書Ｄｉｃ１を辞書Ｄｉｃで初期化し、ＤｉｆｆＩＤを差分辞書Δの符号項目の値集合（図２５では、Δ．ＩＤと記載）で初期化する。
【０１２７】
具体例では、ブロックＢ１は、最初のブロックであるので基準ブロックの復号に用いた辞書Ｄｉｃは空テーブルとなっている。従って、ステップＳ１２０の初期化の結果、辞書Ｄｉｃ１は空テーブルとなり、また、ＤｉｆｆＩＤ＝｛１，２｝となる。
【０１２８】
次に、辞書復元部２０４は、ＤｉｆｆＩＤに要素が存在するか否か判定する（ステップＳ１２２）。ＤｉｆｆＩＤに要素が存在する場合（ステップＳ１２２／ＹＥＳ）、辞書復元部２０４は、ＤｉｆｆＩＤにおける最小の要素ｋを取得し、ＤｉｆｆＩＤから要素ｋを消去する（ステップＳ１２４）。次に、辞書復元部２０４は、ステップＳ１２４で取得したｋが辞書Ｄｉｃ１のエントリ数以下か否か判定する（ステップＳ１２６）。図２５では、辞書Ｄｉｃ１のエントリ数を｜Ｄｉｃ１｜で表す。
【０１２９】
ｋの値が辞書Ｄｉｃ１のエントリ数より大きい場合（ステップＳ１２６／ＮＯ）、辞書復元部２０４は、辞書Ｄｉｃ１の末尾に、Ｄｉｃ１［ｋ］＝Δ［ｋ］となるエントリを追加する。その後、辞書復元部２０４はステップＳ１２２に戻り処理を継続する。ここで、Ｄｉｃ１［ｋ］は、辞書Ｄｉｃ１において符号「ｋ」と対応付けられている文字列を表し、Δ［ｋ］は、差分辞書Δにおいて符号「ｋ」と対応付けられている文字列を表す。
【０１３０】
具体例では、ＤｉｆｆＩＤに要素が存在するので、辞書復元部２０４は、ＤｉｆｆＩＤにおける最小の要素ｋ＝１を取得し、ＤｉｆｆＩＤからｋ＝１を消去する（ステップＳ１２４）。その結果、ＤｉｆｆＩＤ＝｛２｝となる。
【０１３１】
ｋ（＝１）が、辞書Ｄｉｃ１のエントリ数（＝０）よりも大きいため、辞書復元部２０４は、辞書Ｄｉｃ１において符号「１」と対応付けられた文字列が、差分辞書Δにおいて符号「１」と対応付けられた文字列となるエントリを、辞書Ｄｉｃ１の末尾に追加する（ステップＳ１３０）。その結果、ステップＳ１３０の処理後の辞書Ｄｉｃ１は、図２４（２）となる。
【０１３２】
辞書復元部２０４は、ＤｉｆｆＩＤに、未だ要素が存在するので（ステップＳ１２２／ＹＥＳ）、ＤｉｆｆＩＤからｋ＝２を取得し、ＤｉｆｆＩＤからｋ＝２を除去する（ステップＳ１２４）。この結果、ＤｉｆｆＩＤは空集合となる。
【０１３３】
ｋ＝２は、辞書Ｄｉｃ１のエントリ数（＝１）より大きいため、辞書復元部２０４は、辞書Ｄｉｃ１において符号「２」と対応付けられた文字列が、差分辞書Δにおいて符号「２」と対応付けられた文字列となるエントリを、辞書Ｄｉｃ１の末尾に追加する。ステップＳ１３０の処理後の辞書Ｄｉｃ１は、図２４（３）となる。先ほどのステップＳ１２４の処理で、ＤｉｆｆＩＤは空集合となっている。
【０１３４】
図２５のフローチャートにおいて、ＤｉｆｆＩＤに要素が存在しない場合（ステップＳ１２２／ＮＯ）、辞書復元部２０４は、辞書Ｄｉｃ１を出力し（ステップＳ１３２）、本処理を終了する。辞書復元処理の他のステップについては、後述する。
【０１３５】
具体例において、辞書復元部２０４は、ＤｉｆｆＩＤが空集合であるので（ステップＳ１２２／ＮＯ）、辞書Ｄｉｃ１を出力する（ステップＳ１３２）。図２４（４）が復元された辞書Ｄｉｃ１である。
【０１３６】
復号部２０５は、図２４（４）に示す辞書Ｄｉｃ１を用いて、データ取得部２０２が取得したブロックＢ１に含まれる符号化データを復号する（ステップＳ１１０）。復号されたデータは、図２４（５）となる。
【０１３７】
ブロック取得部２０１は、次のブロック（ブロックＢ２）が存在するので（ステップＳ１０２／ＹＥＳ）、ブロックＢ２を取得する。差分辞書取得部２０３は、図２６（１）に示す、ブロックＢ２に含まれる差分辞書Δを取得する（ステップＳ１０６）。次に、辞書復元部２０４が辞書復元処理（ステップＳ１０８）を実行する。
【０１３８】
まず、辞書復元部２０４は、辞書Ｄｉｃ１を、基準ブロックとなるブロックＢ１の復号に用いた辞書Ｄｉｃで初期化する（ステップＳ１２０）。また、ＤｉｆｆＩＤをΔ．ＩＤで初期化する（ステップＳ１２０）。その結果、初期化された辞書Ｄｉｃ１は図２６（２）となり、ＤｉｆｆＩＤ＝｛３｝となる。
【０１３９】
次に、辞書復元部２０４は、ＤｉｆｆＩＤに要素が存在するので（ステップＳ１２２／ＹＥＳ）、ＤｉｆｆＩＤからｋ＝３を取得し、ＤｉｆｆＩＤからｋ＝３を除去する（ステップＳ１２４）。この結果、ＤｉｆｆＩＤは空集合となる。ｋ＝３は辞書Ｄｉｃ１のエントリの数（＝２）よりも大きいので（ステップＳ１２６／ＹＥＳ）、辞書復元部２０４は、辞書Ｄｉｃ１の符号「３」と対応付けられた文字列が、差分辞書Δにおいて符号「３」と対応付けられた文字列となるエントリを、辞書Ｄｉｃ１に追加する（ステップＳ１３０）。ステップＳ１３０の処理後の辞書Ｄｉｃ１は、図２６（３）となる。
【０１４０】
辞書復元部２０４は、ＤｉｆｆＩＤが空集合となっているので（ステップＳ１２２／ＮＯ）、図２６（４）に示す辞書Ｄｉｃ１を出力する（ステップＳ１３２）。
【０１４１】
復号部２０５は、図２６（４）に示す辞書を使用して、ブロックＢ２に含まれる符号化データを復号する（ステップＳ１１０）。その結果、復号されたデータは図２６（５）となる。
【０１４２】
ブロック取得部２０１は、次のブロックが存在するので（ステップＳ１０２／ＹＥＳ）、ブロックＢ３を読み込む（ステップＳ１０４）。差分辞書取得部２０３は、図２７（１）に示す差分辞書ΔをブロックＢ３から取得する（ステップＳ１０６）。辞書復元部２０４が、辞書復元処理を実行する（ステップＳ１０８）。
【０１４３】
辞書復元部２０４は、辞書Ｄｉｃ１を、基準ブロックとなるブロックＢ２の復号に用いた辞書Ｄｉｃで初期化する（ステップＳ１２０）。また、ＤｉｆｆＩＤをΔ．ＩＤで初期化する（ステップＳ１２０）。その結果、初期化された辞書Ｄｉｃ１は、図２７（２）となり、ＤｉｆｆＩＤ＝｛２，３｝となる。
【０１４４】
辞書復元部２０４は、ＤｉｆｆＩＤに要素が存在するので（ステップＳ１２２／ＹＥＳ）、ＤｉｆｆＩＤから最小の要素ｋ＝２を取得し、ＤｉｆｆＩＤからｋ＝２を除去する（ステップＳ１２４）。その結果、ＤｉｆｆＩＤ＝｛３｝となる。ここで、具体例において、ｋ＝２が辞書Ｄｉｃ１のエントリ数（＝３）以下となっている。
【０１４５】
図２５のフローチャートにおいて、ｋの値が、辞書Ｄｉｃ１のエントリ数以下である場合（ステップＳ１２６／ＹＥＳ）、辞書復元部２０４は、辞書Ｄｉｃ１において符号「ｋ」と対応付けられている文字列を、差分辞書Δにおいて符号「ｋ」と対応付けられている文字列で上書きする（ステップＳ１２８）。そして、ステップＳ１２８の処理を終えると、辞書復元部２０４は、ステップＳ１２２に戻り処理を継続する。
【０１４６】
具体例において、辞書復元部２０４は、ｋ＝２が辞書Ｄｉｃ１のエントリ数（＝３）以下であるので、ステップＳ１２８の処理を実行する。すなわち、辞書Ｄｉｃ１の符号「２」と対応付けられた文字列を、差分辞書Δにおいて符号「２」に対応付けられた文字列で上書きする。ステップＳ１２８の処理後の辞書Ｄｉｃ１は、図２７（３）となる。
【０１４７】
次に、辞書復元部２０４は、ＤｉｆｆＩＤに未だ要素が存在するので（ステップＳ１２２／ＹＥＳ）、要素ｋ＝３を取得し、ＤｉｆｆＩＤからｋ＝３を除去する（ステップＳ１２４）。その結果、ＤｉｆｆＩＤは空集合となる。
【０１４８】
取得したｋ（＝３）は、辞書Ｄｉｃ１のエントリ数（＝３）以下であるので（ステップＳ１２６／ＹＥＳ）、辞書復元部２０４はステップＳ１２８の処理を実行する。すなわち、辞書Ｄｉｃ１において符号「３」と対応付けられた文字列を、差分辞書Δにおいて符号「３」と対応付けられた文字列で上書きする。その結果、ステップＳ１２８の処理後の辞書Ｄｉｃ１は、図２７（４）となる。
【０１４９】
ＤｉｆｆＩＤが空集合となったので（ステップＳ１２２／ＮＯ）、辞書復元部２０４は、図２７（５）に示す辞書Ｄｉｃ１を出力する。復号部２０５は、ブロックＢ３に含まれるデータを、図２７（５）に示す辞書で復号する。その結果、復号されたデータは、図２７（６）になる。
【０１５０】
ブロックＢ３の次に、処理対象となるブロックは存在しないため（ステップＳ１０２／ＮＯ）、データ伸長装置２００は、データ伸長処理を終了する。
【０１５１】
以上の説明から明らかなように、本実施例に係るデータ伸長装置２００は、基準ブロックの符号化に使用された辞書と、処理対象ブロックの差分辞書との間に重複する符号が存在する場合、重複する符号に対応する基準ブロックの文字列を、差分辞書の文字列で置換する。その結果、上述したデータ圧縮方法により作成された圧縮データを伸長して、元のデータを復元することができる。
【０１５２】
以上、本件実施例について詳述したが、本件は係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【０１５３】
例えば、本実施例では、連続する２つのブロックにおいて、前方のブロックを基準ブロックとし、後方のブロックを処理対象ブロックとして、順次圧縮処理、伸長処理を行った。しかしながら、基準ブロックを被圧縮データの最初のブロックとし、処理対象ブロックを、最初のブロック以外の、任意のブロックＢｉとしても良い。つまり、データ圧縮装置１００は、処理対象ブロックの圧縮処理において、常に、最初のブロックを基準ブロックとして差分辞書を作成するようにしても良い。連続する２つのブロックを本実施例を用いて圧縮した場合、例えば、ブロックＢｉのデータを伸長するためには、ブロックＢ１〜ブロックＢｉ−１の符号化に用いられた辞書をそれぞれ復元してから、ブロックＢｉの辞書を復元し、データを復号する必要がある。しかしながら、最初のブロックとの差分辞書を作成するようにした場合、最初のブロックの差分辞書と、ブロックＢｉの差分辞書とを使用すれば、ブロックＢｉの符号化に用いられた辞書を復元できるため、ブロックＢ１〜ブロックＢｉ−１において順次辞書を復元する必要がない。従って、指定されたブロックのデータを復号するまでの時間を短縮することができる。また、本実施例における被圧縮データは構造を有するテキストデータであるが、被圧縮データが構造を有しないプレーンなテキスト形式のデータである場合も、同様に実施することができる。さらに、本実施例では、静的辞書式符号化手法として、単純な「値の符号化方式」を採用したが、その他の静的辞書式符号化手法を用いても、同様に実施することが可能である。
【０１５４】
なお、上記のデータ圧縮装置、及びデータ伸長装置が有する機能は、コンピュータによって実現することができる。その場合、データ圧縮装置、及びデータ伸長装置が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。
【０１５５】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ（Digital Versatile Disc）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）などの可搬型記録媒体の形態で販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１５６】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０１５７】
また、本実施例では、データ圧縮装置及びデータ伸長装置を別々の装置として記載したが、図２８に示すように１つの情報処理装置がデータ圧縮装置及びデータ伸長装置としての機能を果すように構成しても良い。また、例えば、インターネット等の通信網に接続されたサーバコンピュータを本件のデータ圧縮装置及びデータ伸長装置の少なくとも一方とし、これに接続されたパーソナルコンピュータ等の通信装置に、データ圧縮及びデータ伸長の少なくとも一つを行うサービスをサーバコンピュータから提供するようにしても良い（ＡＳＰ(Application Service Provider)）。
【０１５８】
また、本実施例ではネットワーク４０を介して、データ圧縮装置１００又はデータ伸長装置２００は、記憶装置１０、センサ装置２０、及びデータ処理装置３０とデータの送受信を行うこととした。しかしながら、データ圧縮装置１００又はデータ伸長装置２００を、記憶装置１０、センサ装置２０、及びデータ処理装置３０のそれぞれと直接接続（ローカル接続）して、データの送受信を行うように構成しても良い。また、本実施例では、地区項目のみを符号化したが、他の項目についても符号化が可能なことはいうまでもない。
【符号の説明】
【０１５９】
１００…データ圧縮装置
１１０…データ取得部
１１１…辞書作成部
１１２…差分辞書作成部
１１３…符号化部
１１４…出力部
２００…データ伸長装置
２０１…ブロック取得部
２０２…データ取得部
２０３…差分辞書取得部
２０４…辞書復元部
２０５…復号部
【特許請求の範囲】
【請求項１】
テキストデータの入力を受け付ける入力部と、
前記テキストデータを所定の規則に基づき複数のブロックに分割する分割部と、
文字列と符号とが対応付けられて格納された辞書データである基準辞書に基づき、処理対象ブロックに出現する文字列のうち、該基準辞書に登録されていない文字列と、該基準辞書において前記処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書を生成する差分辞書生成部と、
前記作成した差分辞書と前記基準辞書とに基づき、辞書データである処理対象辞書を生成する処理対象辞書生成部と、
前記生成した処理対象辞書を参照し、前記処理対象ブロックに出現する文字列を対応する符号に置き換えることで、該処理対象ブロックを圧縮する圧縮部と、
前記圧縮部が圧縮した前記処理対象ブロックのデータと、前記生成した差分辞書とを出力する出力部と、
を備えることを特徴とするデータ圧縮装置。
【請求項２】
前記基準辞書は、処理対象辞書生成部が一つ前の処理対象ブロックに対して生成した処理対象辞書であることを特徴とする請求項１に記載のデータ圧縮装置。
【請求項３】
前記基準辞書は、処理対象辞書生成部が最初の処理対象ブロックに対して生成した処理対象辞書であることを特徴とする請求項１に記載のデータ圧縮装置。
【請求項４】
処理対象ブロック毎に、文字列と符号とが対応付けられて格納された辞書データである基準辞書に基づき、該処理対象ブロックに出現する文字列のうちで該基準辞書に登録されていない文字列と該基準辞書において前記処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書と、符号列である圧縮データとの入力を受け付ける入力部と、
前記圧縮データを所定の規則に基づき複数のブロックに分割する分割部と、
処理対象ブロック毎に、前記受け付けた基準辞書と該処理対象ブロックの差分辞書とに基づき、辞書データである処理対象辞書を生成する処理対象辞書生成部と、
処理対象ブロック毎に、前記生成した処理対象辞書に基づいて、該処理対象ブロックを復号する復号部と、
を備えることを特徴とするデータ伸長装置。
【請求項５】
前記基準辞書は、処理対象辞書生成部が一つ前の処理対象ブロックに対して生成した処理対象辞書であることを特徴とする請求項４に記載のデータ伸長装置。
【請求項６】
前記基準辞書は、処理対象辞書生成部が最初の処理対象ブロックに対して生成した処理対象辞書であることを特徴とする請求項４に記載のデータ伸長装置。
【請求項７】
コンピュータに、
テキストデータの入力を受け付ける入力ステップと、
前記テキストデータを所定の規則に基づき複数のブロックに分割する分割ステップと、
文字列と符号とが対応付けられて格納された辞書データである基準辞書に基づき、処理対象ブロックに出現する文字列のうち、該基準辞書に登録されていない文字列と、該基準辞書において前記処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書を生成する差分辞書生成ステップと、
前記作成した差分辞書と前記基準辞書とに基づき、辞書データである処理対象辞書を生成する処理対象辞書生成ステップと、
前記生成した処理対象辞書を参照し、前記処理対象ブロックに出現する文字列を対応する符号に置き換えることで、該処理対象ブロックを圧縮する圧縮ステップと、
前記圧縮部が圧縮した前記処理対象ブロックのデータと、前記生成した差分辞書とを出力する出力ステップと、
を実行させることを特徴とするデータ圧縮プログラム。
【請求項８】
コンピュータに、
処理対象ブロック毎に、文字列と符号とが対応付けられて格納された辞書データである基準辞書に基づき、該処理対象ブロックに出現する文字列のうちで該基準辞書に登録されていない文字列と該基準辞書において前記処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書と、符号列である圧縮データとの入力を受け付ける入力ステップと、
前記圧縮データを所定の規則に基づき複数のブロックに分割する分割ステップと、
処理対象ブロック毎に、前記受け付けた基準辞書と該処理対象ブロックの差分辞書とに基づき、辞書データである処理対象辞書を生成する処理対象辞書生成ステップと、
処理対象ブロック毎に、前記生成した処理対象辞書に基づいて、該処理対象ブロックを復号する復号ステップと、
を実行させることを特徴とするデータ伸長プログラム。
【請求項１】
テキストデータの入力を受け付ける入力部と、
前記テキストデータを所定の規則に基づき複数のブロックに分割する分割部と、
文字列と符号とが対応付けられて格納された辞書データである基準辞書に基づき、処理対象ブロックに出現する文字列のうち、該基準辞書に登録されていない文字列と、該基準辞書において前記処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書を生成する差分辞書生成部と、
前記作成した差分辞書と前記基準辞書とに基づき、辞書データである処理対象辞書を生成する処理対象辞書生成部と、
前記生成した処理対象辞書を参照し、前記処理対象ブロックに出現する文字列を対応する符号に置き換えることで、該処理対象ブロックを圧縮する圧縮部と、
前記圧縮部が圧縮した前記処理対象ブロックのデータと、前記生成した差分辞書とを出力する出力部と、
を備えることを特徴とするデータ圧縮装置。
【請求項２】
前記基準辞書は、処理対象辞書生成部が一つ前の処理対象ブロックに対して生成した処理対象辞書であることを特徴とする請求項１に記載のデータ圧縮装置。
【請求項３】
前記基準辞書は、処理対象辞書生成部が最初の処理対象ブロックに対して生成した処理対象辞書であることを特徴とする請求項１に記載のデータ圧縮装置。
【請求項４】
処理対象ブロック毎に、文字列と符号とが対応付けられて格納された辞書データである基準辞書に基づき、該処理対象ブロックに出現する文字列のうちで該基準辞書に登録されていない文字列と該基準辞書において前記処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書と、符号列である圧縮データとの入力を受け付ける入力部と、
前記圧縮データを所定の規則に基づき複数のブロックに分割する分割部と、
処理対象ブロック毎に、前記受け付けた基準辞書と該処理対象ブロックの差分辞書とに基づき、辞書データである処理対象辞書を生成する処理対象辞書生成部と、
処理対象ブロック毎に、前記生成した処理対象辞書に基づいて、該処理対象ブロックを復号する復号部と、
を備えることを特徴とするデータ伸長装置。
【請求項５】
前記基準辞書は、処理対象辞書生成部が一つ前の処理対象ブロックに対して生成した処理対象辞書であることを特徴とする請求項４に記載のデータ伸長装置。
【請求項６】
前記基準辞書は、処理対象辞書生成部が最初の処理対象ブロックに対して生成した処理対象辞書であることを特徴とする請求項４に記載のデータ伸長装置。
【請求項７】
コンピュータに、
テキストデータの入力を受け付ける入力ステップと、
前記テキストデータを所定の規則に基づき複数のブロックに分割する分割ステップと、
文字列と符号とが対応付けられて格納された辞書データである基準辞書に基づき、処理対象ブロックに出現する文字列のうち、該基準辞書に登録されていない文字列と、該基準辞書において前記処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書を生成する差分辞書生成ステップと、
前記作成した差分辞書と前記基準辞書とに基づき、辞書データである処理対象辞書を生成する処理対象辞書生成ステップと、
前記生成した処理対象辞書を参照し、前記処理対象ブロックに出現する文字列を対応する符号に置き換えることで、該処理対象ブロックを圧縮する圧縮ステップと、
前記圧縮部が圧縮した前記処理対象ブロックのデータと、前記生成した差分辞書とを出力する出力ステップと、
を実行させることを特徴とするデータ圧縮プログラム。
【請求項８】
コンピュータに、
処理対象ブロック毎に、文字列と符号とが対応付けられて格納された辞書データである基準辞書に基づき、該処理対象ブロックに出現する文字列のうちで該基準辞書に登録されていない文字列と該基準辞書において前記処理対象ブロックに出現しない文字列に対応付けられた符号とを対応付けた辞書データである差分辞書と、符号列である圧縮データとの入力を受け付ける入力ステップと、
前記圧縮データを所定の規則に基づき複数のブロックに分割する分割ステップと、
処理対象ブロック毎に、前記受け付けた基準辞書と該処理対象ブロックの差分辞書とに基づき、辞書データである処理対象辞書を生成する処理対象辞書生成ステップと、
処理対象ブロック毎に、前記生成した処理対象辞書に基づいて、該処理対象ブロックを復号する復号ステップと、
を実行させることを特徴とするデータ伸長プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【公開番号】特開２０１１−１１４５４６（Ｐ２０１１−１１４５４６Ａ）
【公開日】平成２３年６月９日（２０１１．６．９）
【国際特許分類】
【出願番号】特願２００９−２６８６９３（Ｐ２００９−２６８６９３）
【出願日】平成２１年１１月２６日（２００９．１１．２６）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２３年６月９日（２０１１．６．９）
【国際特許分類】
【出願日】平成２１年１１月２６日（２００９．１１．２６）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]