JP6511752B2 - 符号化装置、符号化方法、復号装置、復号方法、及び、プログラム - Google Patents

Description

本発明は、符号化装置、符号化方法、復号装置、復号方法、及び、プログラムに関する。

データ量を削減するために、符号化対象のデータを符号化する（圧縮する）符号化方法、及び、復号対象のデータを符号化前の元データに復号する復号方法が知られている。

例えば、非特許文献１は、符号化対象のデータに繰り返し出現する文字列について、２回目以降に出現する文字列を、最初に出現する文字列のデータ内における位置及び文字列の長さを示すデータ（以下、頻出文字列メタデータと言う。）に変換して符号化対象のデータを符号化するＬＺ符号化方法を開示している。また、非特許文献１は、復号対象のデータ（ＬＺ符号化方法で符号化されたデータ）に含まれる複数の頻出文字列メタデータのそれぞれを、符号化前の元データにおいて繰り返し出現する文字列のうち最初に出現する文字列に置き換えて復号対象のデータを復号する復号方法を開示している。

岡野原大輔著 「高速文字列解析の世界」岩波出版、２０１２年

しかしながら、従来の符号化方法・復号方法では、部分的な復号が必要とされるデータを符号化・復号の対象とした場合、符号化効率が低い。例えば、辞書データの復号では、ユーザが検索対象とした見出し語単位での復号が必要とされるが、このような部分的な復号を従来の符号化方法・復号方法が実現しようとすると、辞書データを見出し語単位で符号化しなければならない。このことを、上述のＬＺ符号化方法を例にとって具体的に説明すると、辞書データ全体がＬＺ符号化方法で符号化されている場合、符号化された辞書データの一部分には、前述の頻出文字列メタデータの置き換えに必要となる、符号化前の元データに繰り返し出現する文字列のうち最初に出現する文字列が含まれない可能性が高い。そのため、辞書データ全体がＬＺ符号化方法で符号化されている場合、辞書データの部分的な復号はほぼ不可能である。従って、見出し語単位での辞書データの復号には、見出し語単位での符号化が必要となる。また、他の符号化方法・復号方法についても同様の理由から、復号対象のデータの部分的な復号には、符号化前の元データについて部分的な符号化が必要となる。そして、このような部分的な符号化は、符号化効率を著しく低下させる。

本発明は、以上のような課題を解決するためのものであり、符号化効率が高い方法を用いて符号化対象のデータを部分的に復号可能なデータに符号化する符号化装置、符号化方法、符号化効率が高い方法を用いて符号化されたデータを部分的に復号する復号装置、復号方法、及び、プログラムを提供することを目的とする。

上記目的を達成するために、本発明の第１の観点に係る符号化装置は、
符号化対象のデータに含まれる文字と、該文字を識別する文字識別番号と、を関連付けて記憶する文字識別番号記憶部と、
前記文字識別番号記憶部を参照して、前記符号化対象のデータに含まれる文字を、該文字に関連付けられた文字識別番号に変換する変換部と、
前記変換部が変換した文字識別番号をバイナリデータに符号化する符号化部と、
前記符号化部が符号化した文字識別番号のバイナリデータに出現する同一のビット列ごとに、該ビット列を識別するビット列識別番号を関連付けてビット列識別番号記憶部に記憶するビット列識別番号関連付部と、
前記ビット列識別番号記憶部を参照して、前記文字識別番号のバイナリデータに出現する同一のビット列を、該ビット列に関連付けられたビット列識別番号に変換するビット列識別番号変換部と、
前記ビット列識別番号変換部が変換したビット列識別番号に、復号時に前記ビット列識別番号記憶部を参照することを示す参照フラグを関連付けて、該ビット列識別番号をバイナリデータに符号化する参照フラグ付き符号化部と、
を備え、
前記文字識別番号は、前記符号化対象のデータにおいて出現頻度の高い文字に関連付けられたものほど小さく、
前記符号化部は、前記文字識別番号が小さいほど該文字識別番号を符号化して得られるバイナリデータのデータ量が小さい符号化方法を用いて、前記文字識別番号をバイナリデータに符号化する。
また、上記目的を達成するために、本発明の他の観点に係る符号化装置は、
符号化対象のデータに含まれる文字と、該文字を識別する文字識別番号と、を関連付けて記憶する文字識別番号記憶部と、
前記文字識別番号記憶部を参照して、前記符号化対象のデータに含まれる文字を、該文字に関連付けられた文字識別番号に変換する変換部と、
前記変換部が変換した文字識別番号をバイナリデータに符号化する符号化部と、
前記符号化部が符号化した文字識別番号のバイナリデータに出現する同一のビット列ごとに、該ビット列を識別するビット列識別番号を関連付けてビット列識別番号記憶部に記憶するビット列識別番号関連付部と、
前記ビット列識別番号記憶部を参照して、前記文字識別番号のバイナリデータに出現する同一のビット列を、該ビット列に関連付けられたビット列識別番号に変換するビット列識別番号変換部と、
前記ビット列識別番号変換部が変換したビット列識別番号に、復号時に前記ビット列識別番号記憶部を参照することを示す参照フラグを関連付けて、該ビット列識別番号をバイナリデータに符号化する参照フラグ付き符号化部と、
前記文字識別番号のバイナリデータに出現するビット列のうち前記ビット列識別番号が関連付けられていないビット列については、該ビット列の先頭から前記ビット列識別番号が関連付けられたビット列が出現するまでのビットの桁数に、復号時に前記ビット列識別番号記憶部を参照しないことを示す非参照フラグを関連付けて、該ビットの桁数をバイナリデータに符号化する非参照フラグ付き符号化部と、
を備える。
また、上記目的を達成するために、本発明の他の観点に係る符号化装置は、
符号化対象のデータに含まれる文字と、該文字を識別する文字識別番号と、を関連付けて記憶する文字識別番号記憶部と、
前記文字識別番号記憶部を参照して、前記符号化対象のデータに含まれる文字を、該文字に関連付けられた文字識別番号に変換する変換部と、
前記変換部が変換した文字識別番号をバイナリデータに符号化する符号化部と、
前記符号化部が符号化した文字識別番号のバイナリデータに出現する同一のビット列ごとに、該ビット列を識別するビット列識別番号を関連付けてビット列識別番号記憶部に記憶するビット列識別番号関連付部と、
前記ビット列識別番号記憶部を参照して、前記文字識別番号のバイナリデータに出現する同一のビット列を、該ビット列に関連付けられたビット列識別番号に変換するビット列識別番号変換部と、
前記ビット列識別番号変換部が変換したビット列識別番号に、復号時に前記ビット列識別番号記憶部を参照することを示す参照フラグを関連付けて、該ビット列識別番号をバイナリデータに符号化する参照フラグ付き符号化部と、
を備え、
前記ビット列識別番号記憶部が記憶する同一のビット列の桁数は、３２桁である。

上記目的を達成するために、本発明の第２の観点に係る復号装置は、
符号化対象のデータに含まれる各文字を識別する各文字識別番号のバイナリデータと、前記各文字識別番号のバイナリデータに出現する同一のビット列を識別するビット列識別番号のバイナリデータと、で構成された圧縮データを記憶する圧縮データ記憶部と、
前記符号化対象のデータに含まれる文字と、該文字を識別する前記文字識別番号と、を関連付けて記憶する文字識別番号記憶部と、
前記各文字識別番号のバイナリデータに出現する前記同一のビット列ごとに、該ビット列を識別する前記ビット列識別番号を関連付けて記憶するビット列識別番号記憶部と、
復号対象のデータを特定するための条件を入力する入力部と、
前記圧縮データ記憶部が記憶する圧縮データのうち前記条件を満たすデータを復号対象のデータとして特定し、特定した復号対象のデータを構成する前記文字識別番号のバイナリデータと前記ビット列識別番号のバイナリデータとのうち、前記ビット列識別番号のバイナリデータを前記ビット列識別番号に復号するビット列識別番号復号部と、
前記ビット列識別番号記憶部を参照して、前記ビット列識別番号復号部が復号した前記ビット列識別番号を、該ビット列識別番号に関連付けられたビット列に変換するビット列識別番号変換部と、
前記復号対象のデータを構成する前記文字識別番号のバイナリデータと前記ビット列識別番号変換部が変換したビット列とを前記文字識別番号に復号する復号部と、
前記文字識別番号記憶部を参照して、前記復号部が復号した前記文字識別番号を、該文字識別番号に関連付けられた文字に変換する変換部と、
を備える。

本発明によれば、符号化効率が高い方法を用いて符号化対象のデータを部分的に復号可能なデータに符号化することができる。また、符号化効率が高い方法を用いて符号化されたデータを部分的に復号することができる。

本発明の実施形態に係る符号化装置の物理構成を示す図である。 本発明の実施形態に係る符号化装置の機能構成を示す図である。 本発明の実施形態に係る符号化処理の流れを示すフローチャートである。 辞書データ（符号化対象のデータ）を示す図である。 各文字の辞書データにおける出現頻度を示す図である。 文字と文字識別番号との関連付けを示す図である。 最終符号化前バイナリデータを示す図である。 各ビット列の最終符号化前バイナリデータにおける出現頻度を示す図である。 ビット列とビット列識別番号との関連付けを示す図である。 本発明の実施形態に係る復号装置の物理構成を示す図である。 本発明の実施形態に係る復号装置の機能構成を示す図である。 本発明の実施形態に係る復号処理の流れを示すフローチャートである。

以下、本発明の実施形態について、図面を参照して説明する。

従来の符号化方法・復号方法によれば、データを部分的に復号したい場合は、符号化前の元データを部分的に符号化しておかなければならない。従って、符号化に手間がかかり、符号化効率は低い。この点に関して、本願発明に係る符号化装置１００、復号装置２００は、符号化前の元データをまとめて符号化してしまっても部分的な復号を可能とする。以下、このような符号化装置１００、復号装置２００の物理構成及び機能構成を説明する。

本実施形態に係る符号化装置１００は、物理的には図１に示すように構成される。即ち、符号化装置１００は、ＲＯＭ（Read Only Memory）１０と、ＲＡＭ（Random Access Memory）１１と、外部記憶装置１２と、入力装置１３と、表示装置１４と、ＣＰＵ（Central Processing Unit）１５と、を備える。

ＲＯＭ１０は、各種初期設定、ハードウェアの検査、プログラムのロード等を行うための初期プログラムを記憶する。ＲＡＭ１１は、ＣＰＵ１５が実行する各種ソフトウェアプログラム、これらのソフトウェアプログラムの実行に必要なデータ等を一時的に記憶する。

外部記憶装置１２は、例えば、ハードディスクであって、各種ソフトウェアプログラム、データ等を記憶する。これらソフトウェアプログラムの中には、アプリケーションソフトウェアプログラム、ＯＳ（Operating System）のような基本ソフトウェアプログラム等が含まれている。

入力装置１３は、キーボード、マウス、トラックパッド等を備え、ユーザからの入力を受け付ける。入力装置１３は、キーボード、マウス、トラックパッド等からの入力に基づいて信号を生成し、ＣＰＵ１５に供給する。

表示装置１４は、液晶ディスプレイ等の画面を備え、ＣＰＵ１５から供給されたテキストデータや画像データを表示する。

ＣＰＵ１５は、外部記憶装置１２が記憶するソフトウェアプログラムをＲＡＭ１１に読み出して、そのソフトウェアプログラムを実行制御することにより、以下の機能構成を実現する。

符号化装置１００は、機能的には図２に示すように構成される。即ち、符号化装置１００は、符号化候補データ記憶部１０１と、表示部１０２と、入力部１０３と、文字出現頻度取得部１０４と、文字識別番号関連付部１０５と、文字識別番号記憶部１０６と、変換部１０７と、符号化部１０８と、開始位置記憶部１０９と、ビット列出現頻度取得部１１０と、ビット列識別番号関連付部１１１と、ビット列識別番号記憶部１１２と、ビット列識別番号変換部１１３と、参照フラグ付き符号化部１１４と、非参照フラグ付き符号化部１１５と、圧縮データ記憶部１１６と、を備える。符号化候補データ記憶部１０１と、文字識別番号記憶部１０６と、開始位置記憶部１０９と、ビット列識別番号記憶部１１２と、圧縮データ記憶部１１６と、は図１に示す外部記憶装置１２に構築されている。

符号化候補データ記憶部１０１は、複数の符号化候補のデータを記憶する。符号化候補のデータは、辞書データ等のテキストデータである。

表示部１０２は、符号化候補のデータを記録したファイルの名称（ファイル名）を表示装置１４に表示する。ユーザは、表示装置１４に表示されたファイル名を参照して、符号化候補のデータのいずれを符号化するか指定する。

入力部１０３は、入力装置１３が生成した信号を受け付ける。この信号は、ユーザが入力装置１３を介して指定したファイル名を示す。入力部１０３は、入力装置１３から受け付けた信号に基づいて、符号化対象のデータを特定する。そして、符号化対象のデータを符号化する旨の指示を文字出現頻度取得部１０４に入力する。

文字出現頻度取得部１０４は、入力部１０３から入力された指示に基づいて、符号化候補データ記憶部１０１が記憶する符号化候補のデータの中から符号化対象のデータを取得する。

文字出現頻度取得部１０４は、符号化対象のデータに含まれる文字ごとに、符号化対象のデータにおける出現頻度を取得する。例えば、符号化対象のデータが図４に示す辞書データ１の場合、各文字の辞書データ１における出現頻度は図５のようになる。
なお、出現頻度の取得は、符号化対象のデータに含まれる全ての文字を対象に行われる。

文字識別番号関連付部１０５は、符号化対象のデータに含まれる文字ごとに、文字を識別する文字識別番号を関連付けて文字識別番号記憶部１０６に記憶する。このとき、文字識別番号関連付部１０５は、符号化対象のデータにおいて出現頻度が高い文字から順に、値が小さい文字識別番号を関連付ける。例えば、符号化対象のデータが図４に示す辞書データ１の場合、図６に示すように、出現頻度が１番目、２番目、３番目・・・に高い文字「ｔ」、「ｈ」、「ｅ」・・・に、それぞれ文字識別番号０、１、２・・・を関連付ける。

以下、出現頻度に基づいて文字に文字識別番号を関連付ける理由と、出現頻度が高い文字に値が小さい文字識別番号を関連付ける理由を説明する。
テキストの圧縮では文字コードの体系が圧縮率低下の原因となることがある。特に、ＵＴＦ−８を採用すると、多言語のテキストを圧縮対象とするため、言語によってはコード長が冗長になり、圧縮率が低下する。そこで、本願発明は、文字を文字コードに符号化するのではなく、文字に文字識別番号を関連付け、文字を文字識別番号のバイナリデータに符号化する。これで圧縮率は文字コードの体系に影響を受けずにすむ。また、頻出文字をコード長が長いバイナリデータに符号化すると圧縮データのサイズが大きくなるので、本願発明はそうならないよう工夫をしている。具体的には、上述したように頻出文字に値が小さい文字識別番号を関連付ける。そして、デルタ符号化方法、Variable Byte Code符号化方法、ハフマン符号化方法といった値が小さいほどコード長が短いバイナリデータに符号化できる符号化方法を用いて、頻出文字をコード長が短いバイナリデータに符号化する。これにより、文字コードに符号化した場合に比べて圧縮データのサイズは大幅に小さくなる。

文字識別番号記憶部１０６は、図６に示すように、符号化対象のデータに含まれる文字と、文字識別番号と、を関連付けて記憶する。

変換部１０７は、文字識別番号記憶部１０６を参照して、符号化対象のデータに含まれる文字を、文字に関連付けられた文字識別番号に変換する。

符号化部１０８は、変換部１０７が変換した文字識別番号をバイナリデータに符号化する。なお、本明細書では符号化部１０８が符号化したバイナリデータを最終符号化前バイナリデータと言う。図７は、図４に示す辞書データ１が変換部１０７により符号化された場合の最終符号化前バイナリデータ２を示す。なお、最終符号化前バイナリデータ２は実際には０又は１を表すビットの集合である。しかし、説明の都合上、８ビットごとに１６進数表記していることに留意されたい。例えば、図７に示すビット列「１２Ａ５Ｂ８ＣＡ」は、「０００１００１０」、「１０１００１０１」、「１０１１１０００」、「１１００１０１０」を、それぞれ「１２」、「Ａ５」、「Ｂ８」、「ＣＡ」というように１６進数表記したものである

開始位置記憶部１０９は、符号化対象のデータに含まれる見出し語の開始位置（本明細書において圧縮境界とも言う。圧縮データを復号する場合の開始地点となる位置を示す。）を記憶する。

ビット列出現頻度取得部１１０は、最終符号化前バイナリデータに含まれる同一のビット列ごとに、最終符号化前バイナリデータにおける出現頻度を取得する。例えば、図７に示す最終符号化前バイナリデータ２においては、各ビット列の出現頻度は図８のようになる。ただし、上述した圧縮境界を跨ぐビット列の出現数はビット列の出現頻度に含めない。
なお、上記ビット列の桁数は符号化方法にもよるが自然言語であれば３２桁程度が適当である。そこで、本実施形態では、上記ビット列の桁数は３２桁とする。ただし、ビット列の桁数は３２桁に限定されず任意の桁数で構わない。

ビット列識別番号関連付部１１１は、最終符号化前バイナリデータに出現する同一のビット列ごとに、ビット列を識別するビット列識別番号を関連付けてビット列識別番号記憶部１１２に記憶する。このとき、ビット列識別番号関連付部１１１は、出現頻度が１から５番目に高いビット列にビット列識別番号を関連付ける。また、出現頻度が高いビット列から順に、値が小さいビット列識別番号を関連付ける。例えば、図７に示す最終符号化前バイナリデータ２であれば、図９に示すように、出現頻度が１番目、２番目、３番目、４番目、５番目に高いビット列「１２Ａ５Ｂ８ＣＡ」、ビット列「ＤＦ４３Ａ６８Ｃ」、ビット列「３８５Ｃ６５Ｆ９」、ビット列「９３５ＡＤ６ＣＤ」、ビット列「Ｂ５８ＣＥＥＡ５」に、それぞれビット列識別番号０、１、２、３、４を関連付ける。

ビット列識別番号記憶部１１２は、図９に示すように、最終符号化前バイナリデータに出現する同一のビット列ごとに、ビット列を識別するビット列識別番号を関連付けて記憶する。

ビット列識別番号変換部１１３は、ビット列識別番号記憶部１１２を参照して、最終符号化前バイナリデータに出現する同一のビット列を、ビット列に関連付けられたビット列識別番号に変換する。ただし、ビット列識別番号変換部１１３は、ビット列が上述した圧縮境界を跨ぐ場合は、ビット列をビット列識別番号に変換しない。これにより、見出し語単位で復号可能なように符号化されたデータ（圧縮データ）を生成することができる。

参照フラグ付き符号化部１１４は、デルタ符号化方法、Variable Byte Code符号化方法、ハフマン符号化方法といった符号化方法を用いて、ビット列識別番号変換部１１３が変換したビット列識別番号をバイナリデータに符号化する。そして、ビット列識別番号のバイナリデータに参照フラグ（復号時にビット列識別番号記憶部１１２を参照することを示すフラグ）を関連付ける。
このように、頻出するビット列をコード長の短いビット列識別番号のバイナリデータに符号化することで、符号化されたデータ（圧縮データ）のサイズを小さくすることができる。

非参照フラグ付き符号化部１１５は、最終符号化前バイナリデータに出現するビット列のうちビット列識別番号が関連付けられていないビット列について、ビット列の先頭からビット列識別番号が関連付けられたビット列が出現するまでのビットの桁数をバイナリデータに符号化する。この際、ビットの桁数のバイナリデータに、非参照フラグ（復号時にビット列識別番号記憶部１１２を参照しないことを示すフラグ）を関連付ける。
また、上記ビット列が圧縮境界を跨ぐ場合は、ビット列の先頭から圧縮境界までのビットの桁数をバイナリデータに符号化し、このバイナリデータに上記非参照フラグを関連付ける。
さらに、ビット列識別番号が関連付けられたビット列のうち圧縮境界を跨ぐためビット列識別番号に変換されなかったビット列についても、圧縮境界を跨ぐ場合と跨がない場合に応じて同様の処理を行う。

圧縮データ記憶部１１６は、符号化対象のデータが符号化されたバイナリデータ（圧縮データ）を記憶する。

以上のような符号化装置１００が実行する符号化処理の流れについて、図３に示すフローチャートを参照して説明する。

［符号化処理］
表示部１０２が、符号化候補のデータを記録したファイルの名称（ファイル名）を表示装置１４に表示しているとする。ユーザは、表示装置１４に表示されたファイル名を参照して、これら符号化候補の中から符号化対象とするもののファイル名を入力装置１３に入力する。入力装置１３は、入力されたファイル名を示す信号を生成し、入力部１０３に供給する。入力部１０３は、入力装置１３から供給された信号を受け付け、ユーザが符号化対象としたファイルを特定する。そして、ユーザが符号化対象としたファイルのデータを符号化する旨の指示を文字出現頻度取得部１０４に供給する。文字出現頻度取得部１０４は、この指示を受け付け、図３に示す符号化処理を開始する。

まず、文字出現頻度取得部１０４は、指示に基づいて、符号化候補データ記憶部１０１が記憶する複数の符号化候補のデータの中から符号化対象のデータを取得する（ステップＳ１０）。以下、理解を容易にするために、符号化対象のデータとして図４に示す辞書データ１が取得されたものとする。

文字出現頻度取得部１０４は、辞書データ１に含まれる文字ごとに、辞書データ１における出現頻度を取得する（ステップＳ１１）。なお、図５に示すように、辞書データ１において文字「ｔ」の出現頻度が９２０４１回で最も高い。続いて、文字「ｈ」、文字「ｅ」、文字「ｓ」、文字「ｒ」・・・の出現頻度がそれぞれ８３８９０回、８０９８４回、７６１８９回、６８６０７回・・・で２番目、３番目、４番目、５番目・・・に高い。

文字識別番号関連付部１０５は、辞書データ１において出現頻度が高い文字から順に、値が小さい文字識別番号を関連付けて文字識別番号記憶部１０６に記憶する（ステップＳ１２）。具体的には、図６に示すように、出現頻度が１番目、２番目、３番目、４番目、５番目・・・に高い文字「ｔ」、文字「ｈ」、文字「ｅ」、文字「ｓ」、文字「ｒ」・・・に、それぞれ文字識別番号０、１、２、３、４・・・を関連付ける。

変換部１０７は、文字識別番号記憶部１０６を参照して、辞書データ１に含まれる文字を、文字に関連付けられた文字識別番号に変換する（ステップＳ１３）。具体的には、辞書データ１に含まれる文字「ｔ」、文字「ｈ」、文字「ｅ」・・・をそれぞれ文字識別番号０、１、２・・・に変換する。

符号化部１０８は、変換部１０７が変換した文字識別番号をバイナリデータに符号化する（ステップＳ１４）。具体的には、辞書データ１が図７に示す最終符号化前バイナリデータ２に符号化される。なお、上述したように、説明の都合上、図７に示す最終符号化前バイナリデータ２を１６進数表記の複数の数値で表していることに留意されたい。実際には、最終符号化前バイナリデータ２は、０又は１を表すビットの集合である。

ビット列出現頻度取得部１１０は、最終符号化前バイナリデータ２に出現する同一のビット列ごとに、最終符号化前バイナリデータ２における出現頻度を取得する（ステップＳ１５）。ただし、辞書データ１に含まれる見出し語の開始位置（圧縮境界）を跨ぐビット列の出現数はビット列の出現頻度に含めない。
なお、図８に示すように、最終符号化前バイナリデータ２において、ビット列「１２Ａ５Ｂ８ＣＡ」の出現頻度が１５０回で最も高い。また、ビット列「ＤＦ４３Ａ６８Ｃ」、ビット列「３８５Ｃ６５Ｆ９」、ビット列「９３５ＡＤ６ＣＤ」、ビット列「Ｄ５８ＣＥＥＡ５」、ビット列「１Ｂ３Ｃ２Ａ０９」・・・の出現頻度がそれぞれ１３０回、１００回、８０回、７０回、４０回・・・で２番目、３番目、４番目、５番目、６番目・・・に高い。

ビット列識別番号関連付部１１１は、出現頻度が１から５番目に高いビット列に対して、出現頻度が高いビット列から順に、値が小さいビット列識別番号を関連付けてビット列識別番号記憶部１１２に記憶する（ステップＳ１６）。具体的には、図９に示すように、出現頻度が１番目、２番目、３番目、４番目、５番目に高いビット列「１２Ａ５Ｂ８ＣＡ」、ビット列「ＤＦ４３Ａ６８Ｃ」、ビット列「３８５Ｃ６５Ｆ９」、ビット列「９３５ＡＤ６ＣＤ」、ビット列「Ｂ５８ＣＥＥＡ５」に、それぞれビット列識別番号０、１、２、３、４を関連付ける。

ビット列識別番号変換部１１３は、ビット列識別番号記憶部１１２を参照して、最終符号化前バイナリデータ２に出現する同一のビット列を、ビット列に関連付けられたビット列識別番号に変換する（ステップＳ１７）。具体的には、ビット列「１２Ａ５Ｂ８ＣＡ」、ビット列「ＤＦ４３Ａ６８Ｃ」、ビット列「３８５Ｃ６５Ｆ９」・・・を、それぞれビット列識別番号０、１、２・・・に変換する。ただし、ビット列識別番号変換部１１３は、圧縮境界を跨ぐビット列については、ビット列識別番号への変換を行わない。

参照フラグ付き符号化部１１４は、ビット列識別番号変換部１１３が変換したビット列識別番号をバイナリデータに符号化する。そして、ビット列識別番号のバイナリデータに参照フラグ（復号時にビット列識別番号記憶部１１２を参照することを示すフラグ）を関連付ける（ステップＳ１８）。

次に、非参照フラグ付き符号化部１１５は、最終符号化前バイナリデータ２に出現するビット列のうちビット列識別番号が関連付けられていないビット列について、ビット列の先頭からビット列識別番号が関連付けられたビット列が出現するまでのビットの桁数をバイナリデータに符号化する。この際、ビットの桁数のバイナリデータに、非参照フラグ（復号時にビット列識別番号記憶部１１２を参照しないことを示すフラグ）を関連付ける。また、上記ビット列が圧縮境界を跨ぐ場合は、ビット列の先頭から圧縮境界までのビットの桁数をバイナリデータに符号化し、このバイナリデータに上記非参照フラグを関連付ける。（ステップＳ１９）。
さらに、非参照フラグ付き符号化部１１５は、ビット列識別番号が関連付けられたビット列のうち圧縮境界を跨ぐためビット列識別番号に変換されなかったビット列についても、圧縮境界を跨ぐ場合と跨がない場合に応じて同様の処理を行う（ステップＳ２０）。

そして、非参照フラグ付き符号化部１１５は、ステップＳ１０からＳ２０までの処理によって辞書データ１が符号化されたバイナリデータ（圧縮データ）を圧縮データ記憶部１１６に記憶する（ステップＳ２１）。

次に上記符号化処理によって符号化された圧縮データを部分的に復号する復号装置２００の物理構成及び機能構成を説明する。

本実施形態に係る復号装置２００は、物理的には図１０に示すように構成される。即ち、復号装置２００は、ＲＯＭ２０と、ＲＡＭ２１と、外部記憶装置２２と、入力装置２３と、表示装置２４と、ＣＰＵ２５と、を備える。

ＲＯＭ２０は、各種初期設定、ハードウェアの検査、プログラムのロード等を行うための初期プログラムを記憶する。ＲＡＭ２１は、ＣＰＵ２５が実行する各種ソフトウェアプログラム、これらのソフトウェアプログラムの実行に必要なデータ等を一時的に記憶する。

外部記憶装置２２は、例えば、ハードディスクであって、各種ソフトウェアプログラム、データ等を記憶する。これらソフトウェアプログラムの中には、アプリケーションソフトウェアプログラム、ＯＳのような基本ソフトウェアプログラム等が含まれている。

入力装置２３は、キーボード、マウス、トラックパッド等を備え、ユーザからの入力を受け付ける。入力装置２３は、キーボード、マウス、トラックパッド等からの入力に基づいて信号を生成し、ＣＰＵ２５に供給する。

表示装置２４は、液晶ディスプレイ等の画面を備え、ＣＰＵ２５から供給されたテキストデータや画像データを画面に表示する。

ＣＰＵ２５は、外部記憶装置２２に記憶されたソフトウェアプログラムをＲＡＭ２１に読み出して、そのソフトウェアプログラムを実行制御することにより、以下の機能構成を実現する。

復号装置２００は、機能的には図１１に示すように構成される。即ち、復号装置２００は、ビット列識別番号記憶部２０１と、圧縮データ記憶部２０２と、開始位置記憶部２０３と、ビット列識別番号復号方法記憶部２０４と、入力部２０５と、ビット列識別番号復号部２０６と、ビット列識別番号変換部２０７と、文字列識別番号復号方法記憶部２０８と、文字識別番号記憶部２０９と、復号部２１０と、変換部２１１と、表示部２１２と、を備える。なお、ビット列識別番号記憶部２０１、圧縮データ記憶部２０２、開始位置記憶部２０３、文字識別番号記憶部２０９は、それぞれ符号化装置１００が備えるビット列識別番号記憶部１１２、圧縮データ記憶部１１６、開始位置記憶部１０９、文字識別番号記憶部１０６が記憶するデータと同じデータを記憶している。ビット列識別番号記憶部２０１と、圧縮データ記憶部２０２と、開始位置記憶部２０３と、ビット列識別番号復号方法記憶部２０４と、文字識別番号復号方法記憶部２０８と、文字識別番号記憶部２０９と、は図１０に示す外部記憶装置２２に構築されている。

ビット列識別番号記憶部２０１は、最終符号化前バイナリデータに出現する同一のビット列ごとに、ビット列を識別するビット列識別番号を関連付けて記憶する。

圧縮データ記憶部２０２は、符号化対象のデータが上記符号化処理によって符号化されたバイナリデータ（圧縮データ）を記憶する。

開始位置記憶部２０３は、符号化対象のデータに含まれる見出し語の開始位置（圧縮境界）を記憶する。

ビット列識別番号復号方法記憶部２０４は、圧縮データに含まれるビット列識別番号のバイナリデータをビット列識別番号に復号する方法を記憶する。具体例を挙げると、ビット列識別番号のバイナリデータがデルタ符号化方法を用いて符号化されている場合には、ビット列識別番号復号方法記憶部２０４は、デルタ符号化方法で符号化されたバイナリデータを符号化前の元データに戻すロジックをビット列識別番号復号方法として記憶する。

入力部２０５は、入力装置２３が生成した信号を受け付ける。この信号は、ユーザが入力装置２３を介して指定した見出し語を示す。入力部２０５は、ユーザが指定した見出し語及びその見出し語の例文であることを復号対象のデータを特定するための条件に設定する。そして、ビット列識別番号復号部２０６に設定した条件を入力する。

ビット列識別番号復号部２０６は、圧縮データのうち入力部２０５から入力された条件を満たすデータを復号対象のデータとして特定する。例えば、見出し語「ｔｈｅ」とその例文であることが条件であれば、圧縮データに含まれる見出し語「ｔｈｅ」とその例文を復号対象のデータとして特定する。なお、圧縮データにおける見出し語及び例文の位置は、開始位置記憶部２０３が記憶する各見出し語の開始位置に基づいて特定される。

また、ビット列識別番号復号部２０６は、見出し語の開始位置に参照フラグと非参照フラグのどちらが存在するか判別する。参照フラグが存在すると判別した場合、参照フラグに関連付けられているビット列識別番号のバイナリデータをビット列識別番号に復号する。復号方法は、ビット列識別番号復号方法記憶部２０４が記憶する復号方法が採用される。
一方、非参照フラグが存在すると判別した場合、復号部２１０に復号処理の制御を移す。

ビット列識別番号変換部２０７は、ビット列識別番号記憶部２０１を参照し、ビット列識別番号復号部２０６が復号したビット列識別番号を、ビット列識別番号に関連付けられたビット列に変換する。そして、変換したビット列をキューにコピーする。

文字識別番号復号方法記憶部２０８は、圧縮データに含まれる文字識別番号のバイナリデータを文字識別番号に復号する方法を記憶している。具体例を挙げると、文字識別番号のバイナリデータがデルタ符号化方法を用いて符号化されている場合には、文字識別番号復号方法記憶部２０８は、デルタ符号化方法で符号化されたバイナリデータを符号化前の元データに戻すロジックを文字列識別番号復号方法として記憶する。

文字識別番号記憶部２０９は、圧縮データに含まれる文字と、文字を識別する文字識別番号と、を関連付けて記憶している。

復号部２１０は、ビット列識別番号変換部２０７がキューにコピーしたビット列を文字識別番号に復号する。
一方、復号部２１０は、ビット列識別番号復号部２０６から復号処理の制御を移された場合、非参照フラグに関連付けられているビットの桁数を示すデータを読み込む。そして、上記桁数分のバイナリデータをさらに読み込み、キューにコピーする。そして、キューにコピーしたバイナリデータを文字識別番号に復号する。
なお、復号方法は、文字識別番号復号方法記憶部２０８が記憶する復号方法が採用される。

変換部２１１は、文字識別番号記憶部２０９を参照し、復号部２１０が復号した文字識別番号を文字に変換する。

表示部２１２は、圧縮データが復号されたデータ（符号化前の元データ）を表示装置２４に表示する。

以上のような復号装置２００が実行する復号処理の流れについて、図１２に示すフローチャートを参照して説明する。

［復号処理］
ここで、圧縮データ記憶部２０２が記憶する圧縮データは、図４に示す辞書データ１のバイナリデータであるとする。そして、ユーザが、「ｔｈｅ」の定義や「ｔｈｅ」の使用例を調べるにために、入力装置２３に見出し語「ｔｈｅ」を入力したとする。この場合、入力装置２３は、入力された見出し語「ｔｈｅ」を示す信号を生成し、入力部２０５に供給する。入力部２０５は、入力装置２３から供給された信号を受け付け、入力された見出し語が「ｔｈｅ」であることを特定する。そして、見出し語「ｔｈｅ」とその例文であることを復号対象の条件に設定し、ビット列識別番号復号部２０６に設定した条件を入力する。ビット列識別番号復号部２０６は、入力部２０５から上記条件を受け付け、図１２に示す復号処理を開始する。

ビット列識別番号復号部２０６は、圧縮データのうち上記条件を満たすデータを復号対象のデータとして特定する（ステップＳ３０）。ここで上記条件を満たすのは見出し語「ｔｈｅ」とその例文である。従って、見出し語「ｔｈｅ」とその例文が復号対象のデータとして特定される。

次に、ビット列識別番号復号部２０６は、見出し語「ｔｈｅ」の開始位置に参照フラグと非参照フラグのどちらが存在するか判別する（ステップＳ３１）。参照フラグが存在すると判別した場合、参照フラグに関連付けられているビット列識別番号のバイナリデータを読み込む。そして、ビット列識別番号復号方法記憶部２０４が記憶する復号方法を用いて、ビット列識別番号のバイナリデータをビット列識別番号に復号する（ステップＳ３２）。なお、ここではステップＳ３２において復号されたビット列識別番号を「０」とする。

ビット列識別番号変換部２０７は、ビット列識別番号記憶部２０１を参照して、ビット列識別番号復号部２０６が復号したビット列識別番号を、ビット列識別番号に関連付けられたビット列に変換する（ステップＳ３３）。そして、変換したビット列をキューにコピーする（ステップＳ３４）。具体的には、ステップＳ３２において復号されたビット列識別番号「０」を、ビット列識別番号「０」に関連付けられたビット列「１２Ａ５Ｂ８ＣＡ」（図９参照）に変換し、ビット列「１２Ａ５Ｂ８ＣＡ」をキューにコピーする。

復号部２１０は、キューに存在するビット列を、文字識別番号復号方法記憶部２０８が記憶する復号方法を用いて文字識別番号に復号する（ステップＳ３５）。ここでは、ビット列「１２Ａ５Ｂ８ＣＡ」が文字識別番号「０」、「１」、「２」、「３」に復号されたとする。

変換部２１１は、文字識別番号記憶部２０９を参照し、復号部２１０が復号した文字識別番号を文字に変換する（ステップＳ３６）。具体的には、ステップＳ３５で復号された文字識別番号「０」、「１」、「２」、「３」を、それぞれの文字識別番号に関連付けられた文字「ｔ」、「ｈ」、「ｅ」、「ｓ」（図６参照）に変換する。

文字への変換を終えると、変換部２１１は、全ての復号対象のデータを文字に変換したか否かを判別する（ステップＳ３７）。

変換部２１１は、復号対象のデータに変換されていない部分が存在すると判別した場合（ステップＳ３７；Ｎｏ）、復号処理の制御をビット列識別番号復号部２０６に移す。この場合、ビット列識別番号復号部２０６は、復号済みであるビット列識別番号のバイナリデータの後尾に参照フラグと非参照フラグのどちらが存在するか判別する（ステップＳ３１）。ビット列識別番号復号部２０６は、非参照フラグが存在すると判別した場合、復号処理の制御を復号部２１０に移す。この場合、復号部２１０は、非参照フラグに関連付けられているビットの桁数のバイナリデータを読み込む（ステップＳ３８）。そして、復号済みであるビット列識別番号のバイナリデータの後尾から上記桁数分のバイナリデータを読み込み（ステップＳ３９）、キューにコピーする（ステップＳ４０）。

復号部２１０は、キューに存在するバイナリデータを、文字識別番号復号方法記憶部２０８が記憶する復号方法を用いて文字識別番号に復号する（ステップＳ３５）。

変換部２１１は、文字識別番号記憶部２０９を参照し、復号部２１０が復号した文字識別番号を文字に変換する（ステップＳ３６）。

文字への変換を終えると、変換部２１１は、全ての復号対象のデータを文字に変換したか否かを判別する（ステップＳ３７）。復号対象のデータに変換されていない部分が存在すると判別した場合（ステップＳ３７；Ｎｏ）、復号処理の制御をビット列識別番号復号部２０６に移す。そして、ステップＳ３１からＳ３７までの処理が、全ての復号対象のデータが文字に変換されるまで繰り返し実行される。

ステップＳ３７において、変換部２１１が全ての復号対象のデータを文字に変換したと判別した場合（ステップＳ３７；Ｙｅｓ）、表示部２１２は、変換された文字を表示装置２４に表示する（ステップＳ４１）。具体的には、見出し語「ｔｈｅ」とその例文を表示装置２４に表示する。

このように、上記復号処理では、圧縮データの一部がユーザに指定された見出し語の開始位置から逐次的に復号される。その際、参照フラグと非参照フラグのどちらが存在するかが復号前に判別され、復号しようとしているバイナリデータが文字識別番号のバイナリデータかビット列識別番号のバイナリデータかが特定される。ここで、参照フラグが存在すると判別された場合は、ビット列識別番号のバイナリデータであると特定され、非参照フラグが存在すると判別された場合は、文字識別番号のバイナリデータであると特定される。そして、特定されたバイナリデータの種別に応じた復号方法で、文字識別番号のバイナリデータは文字識別番号に復号され、ビット列識別番号のバイナリデータはビット列に復号される。
ここで注目すべき点は、文字識別番号を文字に変換するために必要となる変換前の元データ、ビット列を文字識別番号に変換するために必要となる変換前の元データを文字識別番号記憶部２０９とビット列識別番号記憶部２０１から自在に取得できることである。これは、圧縮データの一部である復号対象のデータに変換前の元データが存在しなくても、元データに変換可能ということを意味する。従って、従来の符号化方法・復号方法であれば、符号化対象のデータを予め部分的に符号化しておかなければ部分的復号を実行できなかったが、本願発明によればそのようなことをしなくても部分的復号を実行できる。

以上説明したように、本実施形態に係る符号化装置１００は、符号化対象のデータを文字列識別番号及びビット列識別番号のバイナリデータに符号化する。そして、復号装置２００は、文字識別番号記憶部２０９とビット列識別番号記憶部２０１を参照し、符号化装置１００が符号化したバイナリデータ（圧縮データ）を部分的に復号する。これらは、上述したように、符号化対象のデータを部分的に符号化しなくても圧縮データの部分的復号を可能とする。従って、従来の符号化方法・復号方法に比べて符号化に手間がかからず、符号化効率が高い。

（変形例）
以上に本発明の実施形態について説明したが、上記実施形態は一例であり、本発明の適用範囲はこれに限られない。すなわち、本発明の実施形態は種々の応用が可能であり、あらゆる実施の形態が本発明の範囲に含まれる。

例えば、上記実施形態では、出現頻度が１から５番目に高いビット列にビット列識別番号を関連付けたが、ビット列識別番号を関連付ける対象が、出現頻度が１から５番目に高いビット列に限定されるわけではない。例えば、出現頻度が１から１０番目に高いビット列にビット列識別番号を関連付けてもよいし、全てのビット列にビット列識別番号を関連付けてもよい。ただし、出現頻度が低いビット列をコード長が長いビット列識別番号のバイナリデータに符号化するとかえって圧縮率が低下するため、ビット列識別番号を関連付ける対象を出現頻度が高いビット列に限定したほうが好ましい。

また、上記実施形態では、見出し語の開始位置を圧縮境界としたが、見出し語の開始位置と見出し語の例文の開始位置を圧縮境界としてもよい。

また、上記実施形態では、符号化装置１００と復号装置２００とを互いに独立した装置として記載した。しかし、符号化装置１００が、復号装置２００の機能を全て備え、復号装置として動作してもよいし、復号装置２００が、符号化装置１００の機能を全て備え、符号化装置として動作してもよい。

また、復号装置２００は、圧縮データから復号対象のデータを特定する特定部を備えていてもよい。そして、図１２に示す復号処理のステップＳ３０で、特定部が圧縮データから復号対象のデータを特定してもよい。この場合、ビット列識別番号復号部２０６は、特定部が特定した復号対象のデータを復号する。

なお、本発明に係る機能を実現するための構成を予め備えた符号化装置、復号装置として提供できることはもとより、プログラムの適用により、既存のパーソナルコンピュータや情報端末機器等を、本発明に係る符号化装置、復号装置として機能させることもできる。すなわち、上記実施形態で例示した符号化装置、復号装置による各機能構成を実現させるためのプログラムを、既存のパーソナルコンピュータや情報端末機器等を制御するＣＰＵ等が実行できるように適用することで、本発明に係る符号化装置、復号装置として機能させることができる。また、本発明に係る符号化方法、復号方法は、符号化装置、復号装置を用いて実施できる。

また、このようなプログラムの適用方法は任意である。プログラムを、例えば、コンピュータが読取可能な記録媒体［ＣＤ−ＲＯＭ（Compact Disc Read-Only Memory）、ＤＶＤ（Digital Versatile Disc）、ＭＯ（Magneto Optical disc）等］に格納して適用できる他、インターネット等のネットワーク上のストレージにプログラムを格納しておき、これをダウンロードさせることにより適用することもできる。

以上、本発明の好ましい実施形態について説明したが、本発明は係る特定の実施形態に限定されるものではなく、本発明には、特許請求の範囲に記載された発明とその均等の範囲とが含まれる。以下に、本願出願の当初の特許請求の範囲に記載された発明を付記する。

（付記１）
符号化対象のデータに含まれる文字と、該文字を識別する文字識別番号と、を関連付けて記憶する文字識別番号記憶部と、
前記文字識別番号記憶部を参照して、前記符号化対象のデータに含まれる文字を、該文字に関連付けられた文字識別番号に変換する変換部と、
前記変換部が変換した文字識別番号をバイナリデータに符号化する符号化部と、
前記符号化部が符号化した文字識別番号のバイナリデータに出現する同一のビット列ごとに、該ビット列を識別するビット列識別番号を関連付けてビット列識別番号記憶部に記憶するビット列識別番号関連付部と、
前記ビット列識別番号記憶部を参照して、前記文字識別番号のバイナリデータに出現する同一のビット列を、該ビット列に関連付けられたビット列識別番号に変換するビット列識別番号変換部と、
前記ビット列識別番号変換部が変換したビット列識別番号に、復号時に前記ビット列識別番号記憶部を参照することを示す参照フラグを関連付けて、該ビット列識別番号をバイナリデータに符号化する参照フラグ付き符号化部と、
を備える符号化装置。

（付記２）
前記文字識別番号は、前記符号化対象のデータにおいて出現頻度の高い文字に関連付けられたものほど小さく、
前記符号化部は、前記文字識別番号が小さいほど該文字識別番号を符号化して得られるバイナリデータのデータ量が小さい符号化方法を用いて、前記文字識別番号をバイナリデータに符号化する、
付記１に記載の符号化装置。

（付記３）
前記文字識別番号のバイナリデータに出現するビット列のうち前記ビット列識別番号が関連付けられていないビット列については、該ビット列の先頭から前記ビット列識別番号が関連付けられたビット列が出現するまでのビットの桁数に、復号時に前記ビット列識別番号記憶部を参照しないことを示す非参照フラグを関連付けて、該ビットの桁数をバイナリデータに符号化する非参照フラグ付き符号化部、
を備える付記１又は２に記載の符号化装置。

（付記４）
前記ビット列識別番号は、前記文字識別番号のバイナリデータにおいて出現頻度の高い同一のビット列に関連付けられたものほど小さく、
前記参照フラグ付き符号化部は、前記ビット列識別番号が小さいほど該ビット列識別番号を符号化して得られるバイナリデータのデータ量が小さい符号化方法を用いて、前記ビット列識別番号をバイナリデータに符号化する、
付記１乃至３の何れかに記載の符号化装置。

（付記５）
前記符号化対象のデータは、見出し語を含み、
前記同一のビット列の出現頻度は、前記符号化対象のデータにおける前記見出し語の開始位置を跨ぐ該同一のビット列の出現数を含まない、
付記４に記載の符号化装置。

（付記６）
前記符号化対象のデータは、見出し語を含み、
前記ビット列識別番号変換部は、前記ビット列識別番号が関連付けられたビット列が、前記見出し語の開始位置を跨ぐ場合、該ビット列を前記ビット列識別番号に変換せず、
前記非参照フラグ付き符号化部は、前記ビット列識別番号が関連付けられたビット列のうち前記ビット列識別番号変換部が前記ビット列識別番号に変換しなかったビット列について、該ビット列の先頭から該ビット列が跨ぐ前記見出し語の開始位置までのビットの桁数に、前記非参照フラグを関連付けて、該ビットの桁数をバイナリデータに符号化する、
付記３に記載の符号化装置。

（付記７）
前記非参照フラグ付き符号化部は、前記ビット列識別番号が関連付けられていないビット列が、前記見出し語の開始位置を跨ぐ場合、該ビット列の先頭から該開始位置までのビットの桁数に、前記非参照フラグを関連付けて、該ビットの桁数をバイナリデータに符号化する、
付記６に記載の符号化装置。

（付記８）
前記ビット列識別番号記憶部が記憶する同一のビット列の桁数は、３２桁である、
付記１乃至７の何れかに記載の符号化装置。

（付記９）
符号化対象のデータに含まれる各文字を識別する各文字識別番号のバイナリデータと、前記各文字識別番号のバイナリデータに出現する同一のビット列を識別するビット列識別番号のバイナリデータと、で構成された圧縮データを記憶する圧縮データ記憶部と、
前記符号化対象のデータに含まれる文字と、該文字を識別する前記文字識別番号と、を関連付けて記憶する文字識別番号記憶部と、
前記各文字識別番号のバイナリデータに出現する前記同一のビット列ごとに、該ビット列を識別する前記ビット列識別番号を関連付けて記憶するビット列識別番号記憶部と、
復号対象のデータを特定するための条件を入力する入力部と、
前記圧縮データ記憶部が記憶する圧縮データのうち前記条件を満たすデータを復号対象のデータとして特定し、特定した復号対象のデータを構成する前記文字識別番号のバイナリデータと前記ビット列識別番号のバイナリデータとのうち、前記ビット列識別番号のバイナリデータを前記ビット列識別番号に復号するビット列識別番号復号部と、
前記ビット列識別番号記憶部を参照して、前記ビット列識別番号復号部が復号した前記ビット列識別番号を、該ビット列識別番号に関連付けられたビット列に変換するビット列識別番号変換部と、
前記復号対象のデータを構成する前記文字識別番号のバイナリデータと前記ビット列識別番号変換部が変換したビット列とを前記文字識別番号に復号する復号部と、
前記文字識別番号記憶部を参照して、前記復号部が復号した前記文字識別番号を、該文字識別番号に関連付けられた文字に変換する変換部と、
を備える復号装置。

（付記１０）
符号化対象のデータに含まれる文字と、該文字を識別する文字識別番号と、を関連付けて記憶する文字識別番号記憶部を参照して、前記符号化対象のデータに含まれる文字を、該文字に関連付けられた文字識別番号に変換する変換ステップと、
前記変換ステップで変換した文字識別番号をバイナリデータに符号化する符号化ステップと、
前記符号化ステップで符号化した文字識別番号のバイナリデータに出現する同一のビット列ごとに、該ビット列を識別するビット列識別番号を関連付けてビット列識別番号記憶部に記憶するビット列識別番号関連付ステップと、
前記ビット列識別番号記憶部を参照して、前記文字識別番号のバイナリデータに出現する同一のビット列を、該ビット列に関連付けられたビット列識別番号に変換するビット列識別番号変換ステップと、
前記ビット列識別番号変換ステップで変換したビット列識別番号に、復号時に前記ビット列識別番号記憶部を参照することを示す参照フラグを関連付けて、該ビット列識別番号をバイナリデータに符号化する参照フラグ付き符号化ステップと、
を備える符号化方法。

（付記１１）
復号対象のデータを特定するための条件を入力する入力ステップと、
符号化対象のデータに含まれる各文字を識別する各文字識別番号のバイナリデータと、前記各文字識別番号のバイナリデータに出現する同一のビット列を識別するビット列識別番号のバイナリデータと、で構成された圧縮データのうち、前記条件を満たすデータを復号対象のデータとして特定する特定ステップと、
前記特定ステップで特定した前記復号対象のデータを構成する前記文字識別番号のバイナリデータと前記ビット列識別番号のバイナリデータとのうち、前記ビット列識別番号のバイナリデータを前記ビット列識別番号に復号するビット列識別番号復号ステップと、
前記各文字識別番号のバイナリデータに出現する前記同一のビット列ごとに、該ビット列を識別する前記ビット列識別番号を関連付けて記憶するビット列識別番号記憶部を参照して、前記ビット列識別番号復号ステップで復号した前記ビット列識別番号を、該ビット列識別番号に関連付けられたビット列に変換するビット列識別番号変換ステップと、
前記復号対象のデータを構成する前記文字識別番号のバイナリデータと前記ビット列識別番号変換ステップで変換したビット列とを前記文字識別番号に復号する復号ステップと、
前記符号化対象のデータに含まれる文字と、該文字を識別する前記文字識別番号と、を関連付けて記憶する文字識別番号記憶部を参照して、前記復号ステップで復号した前記文字識別番号を、該文字識別番号に関連付けられた文字に変換する変換ステップと、
を備える復号方法。

（付記１２）
コンピュータを、
符号化対象のデータに含まれる文字と、該文字を識別する文字識別番号と、を関連付けて記憶する文字識別番号記憶部を参照して、前記符号化対象のデータに含まれる文字を、該文字に関連付けられた文字識別番号に変換する変換部、
前記変換部が文字識別番号をバイナリデータに符号化する符号化部、
前記符号化部が符号化した文字識別番号のバイナリデータに出現する同一のビット列ごとに、該ビット列を識別するビット列識別番号を関連付けてビット列識別番号記憶部に記憶するビット列識別番号関連付部、
前記ビット列識別番号記憶部を参照して、前記文字識別番号のバイナリデータに出現する同一のビット列を、該ビット列に関連付けられたビット列識別番号に変換するビット列識別番号変換部、
前記ビット列識別番号変換部が変換したビット列識別番号に、復号時に前記ビット列識別番号記憶部を参照することを示す参照フラグを関連付けて、該ビット列識別番号をバイナリデータに符号化する参照フラグ付き符号化部、
として機能させるためのプログラム。

（付記１３）
コンピュータを、
復号対象のデータを特定するための条件を入力する入力部、
符号化対象のデータに含まれる各文字を識別する各文字識別番号のバイナリデータと、前記各文字識別番号のバイナリデータに出現する同一のビット列を識別するビット列識別番号のバイナリデータと、で構成された圧縮データのうち、前記条件を満たすデータを復号対象のデータとして特定する特定部、
前記特定部が特定した前記復号対象のデータを構成する前記文字識別番号のバイナリデータと前記ビット列識別番号のバイナリデータとのうち、前記ビット列識別番号のバイナリデータを前記ビット列識別番号に復号するビット列識別番号復号部、
前記各文字識別番号のバイナリデータに出現する前記同一のビット列ごとに、該ビット列を識別する前記ビット列識別番号を関連付けて記憶するビット列識別番号記憶部を参照して、前記ビット列識別番号復号部が復号した前記ビット列識別番号を、該ビット列識別番号に関連付けられたビット列に変換するビット列識別番号変換部、
前記復号対象のデータを構成する前記文字識別番号のバイナリデータと前記ビット列識別番号変換部が変換したビット列とを前記文字識別番号に復号する復号部、
前記符号化対象のデータに含まれる文字と、該文字を識別する前記文字識別番号と、を関連付けて記憶する文字識別番号記憶部を参照して、前記復号部が復号した前記文字識別番号を、該文字識別番号に関連付けられた文字に変換する変換部、
として機能させるためのプログラム。

１…辞書データ、２…最終符号化前バイナリデータ、１０…ＲＯＭ、１１…ＲＡＭ、１２…外部記憶装置、１３…入力装置、１４…表示装置、１５…ＣＰＵ、１００…符号化装置、１０１…符号化候補データ記憶部、１０２…表示部、１０３…入力部、１０４…文字出現頻度取得部、１０５…文字識別番号関連付部、１０６…文字識別番号記憶部、１０７…変換部、１０８…符号化部、１０９…開始位置記憶部、１１０…ビット列出現頻度取得部、１１１…ビット列識別番号関連付部、１１２…ビット列識別番号記憶部、１１３…ビット列識別番号変換部、１１４…参照フラグ付き符号化部、１１５…非参照フラグ付き符号化部、１１６…圧縮データ記憶部、２００…復号装置、２０…ＲＯＭ、２１…ＲＡＭ、２２…外部記憶装置、２３…入力装置、２４…表示装置、２５…ＣＰＵ、２００…復号装置、２０１…ビット列識別番号記憶部、２０２…圧縮データ記憶部、２０３…開始位置記憶部、２０４…ビット列識別番号復号方法記憶部、２０５…入力部、２０６…ビット列識別番号復号部、２０７…ビット列識別番号変換部、２０８…文字識別番号復号方法記憶部、２０９…文字識別番号記憶部、２１０…復号部、２１１…変換部、２１２…表示部

Claims (12)

1. 符号化対象のデータに含まれる文字と、該文字を識別する文字識別番号と、を関連付けて記憶する文字識別番号記憶部と、
   前記文字識別番号記憶部を参照して、前記符号化対象のデータに含まれる文字を、該文字に関連付けられた文字識別番号に変換する変換部と、
   前記変換部が変換した文字識別番号をバイナリデータに符号化する符号化部と、
   前記符号化部が符号化した文字識別番号のバイナリデータに出現する同一のビット列ごとに、該ビット列を識別するビット列識別番号を関連付けてビット列識別番号記憶部に記憶するビット列識別番号関連付部と、
   前記ビット列識別番号記憶部を参照して、前記文字識別番号のバイナリデータに出現する同一のビット列を、該ビット列に関連付けられたビット列識別番号に変換するビット列識別番号変換部と、
   前記ビット列識別番号変換部が変換したビット列識別番号に、復号時に前記ビット列識別番号記憶部を参照することを示す参照フラグを関連付けて、該ビット列識別番号をバイナリデータに符号化する参照フラグ付き符号化部と、
   を備え、
   前記文字識別番号は、前記符号化対象のデータにおいて出現頻度の高い文字に関連付けられたものほど小さく、
   前記符号化部は、前記文字識別番号が小さいほど該文字識別番号を符号化して得られるバイナリデータのデータ量が小さい符号化方法を用いて、前記文字識別番号をバイナリデータに符号化する、
   符号化装置。
2. 符号化対象のデータに含まれる文字と、該文字を識別する文字識別番号と、を関連付けて記憶する文字識別番号記憶部と、
   前記文字識別番号記憶部を参照して、前記符号化対象のデータに含まれる文字を、該文字に関連付けられた文字識別番号に変換する変換部と、
   前記変換部が変換した文字識別番号をバイナリデータに符号化する符号化部と、
   前記符号化部が符号化した文字識別番号のバイナリデータに出現する同一のビット列ごとに、該ビット列を識別するビット列識別番号を関連付けてビット列識別番号記憶部に記憶するビット列識別番号関連付部と、
   前記ビット列識別番号記憶部を参照して、前記文字識別番号のバイナリデータに出現する同一のビット列を、該ビット列に関連付けられたビット列識別番号に変換するビット列識別番号変換部と、
   前記ビット列識別番号変換部が変換したビット列識別番号に、復号時に前記ビット列識別番号記憶部を参照することを示す参照フラグを関連付けて、該ビット列識別番号をバイナリデータに符号化する参照フラグ付き符号化部と、
   前記文字識別番号のバイナリデータに出現するビット列のうち前記ビット列識別番号が関連付けられていないビット列については、該ビット列の先頭から前記ビット列識別番号が関連付けられたビット列が出現するまでのビットの桁数に、復号時に前記ビット列識別番号記憶部を参照しないことを示す非参照フラグを関連付けて、該ビットの桁数をバイナリデータに符号化する非参照フラグ付き符号化部と、
   を備える符号化装置。
3. 符号化対象のデータに含まれる文字と、該文字を識別する文字識別番号と、を関連付けて記憶する文字識別番号記憶部と、
   前記文字識別番号記憶部を参照して、前記符号化対象のデータに含まれる文字を、該文字に関連付けられた文字識別番号に変換する変換部と、
   前記変換部が変換した文字識別番号をバイナリデータに符号化する符号化部と、
   前記符号化部が符号化した文字識別番号のバイナリデータに出現する同一のビット列ごとに、該ビット列を識別するビット列識別番号を関連付けてビット列識別番号記憶部に記憶するビット列識別番号関連付部と、
   前記ビット列識別番号記憶部を参照して、前記文字識別番号のバイナリデータに出現する同一のビット列を、該ビット列に関連付けられたビット列識別番号に変換するビット列識別番号変換部と、
   前記ビット列識別番号変換部が変換したビット列識別番号に、復号時に前記ビット列識別番号記憶部を参照することを示す参照フラグを関連付けて、該ビット列識別番号をバイナリデータに符号化する参照フラグ付き符号化部と、
   を備え、
   前記ビット列識別番号記憶部が記憶する同一のビット列の桁数は、３２桁である、
   符号化装置。
4. 前記ビット列識別番号は、前記文字識別番号のバイナリデータにおいて出現頻度の高い同一のビット列に関連付けられたものほど小さく、
   前記参照フラグ付き符号化部は、前記ビット列識別番号が小さいほど該ビット列識別番号を符号化して得られるバイナリデータのデータ量が小さい符号化方法を用いて、前記ビット列識別番号をバイナリデータに符号化する、
   請求項１乃至３の何れか一項に記載の符号化装置。
5. 前記符号化対象のデータは、見出し語を含み、
   前記同一のビット列の出現頻度は、前記符号化対象のデータにおける前記見出し語の開始位置を跨ぐ該同一のビット列の出現数を含まない、
   請求項４に記載の符号化装置。
6. 前記符号化対象のデータは、見出し語を含み、
   前記ビット列識別番号変換部は、前記ビット列識別番号が関連付けられたビット列が、前記見出し語の開始位置を跨ぐ場合、該ビット列を前記ビット列識別番号に変換せず、
   前記非参照フラグ付き符号化部は、前記ビット列識別番号が関連付けられたビット列のうち前記ビット列識別番号変換部が前記ビット列識別番号に変換しなかったビット列について、該ビット列の先頭から該ビット列が跨ぐ前記見出し語の開始位置までのビットの桁数に、前記非参照フラグを関連付けて、該ビットの桁数をバイナリデータに符号化する、
   請求項２に記載の符号化装置。
7. 前記非参照フラグ付き符号化部は、前記ビット列識別番号が関連付けられていないビット列が、前記見出し語の開始位置を跨ぐ場合、該ビット列の先頭から該開始位置までのビットの桁数に、前記非参照フラグを関連付けて、該ビットの桁数をバイナリデータに符号化する、
   請求項６に記載の符号化装置。
8. 符号化対象のデータに含まれる各文字を識別する各文字識別番号のバイナリデータと、前記各文字識別番号のバイナリデータに出現する同一のビット列を識別するビット列識別番号のバイナリデータと、で構成された圧縮データを記憶する圧縮データ記憶部と、
   前記符号化対象のデータに含まれる文字と、該文字を識別する前記文字識別番号と、を関連付けて記憶する文字識別番号記憶部と、
   前記各文字識別番号のバイナリデータに出現する前記同一のビット列ごとに、該ビット列を識別する前記ビット列識別番号を関連付けて記憶するビット列識別番号記憶部と、
   復号対象のデータを特定するための条件を入力する入力部と、
   前記圧縮データ記憶部が記憶する圧縮データのうち前記条件を満たすデータを復号対象のデータとして特定し、特定した復号対象のデータを構成する前記文字識別番号のバイナリデータと前記ビット列識別番号のバイナリデータとのうち、前記ビット列識別番号のバイナリデータを前記ビット列識別番号に復号するビット列識別番号復号部と、
   前記ビット列識別番号記憶部を参照して、前記ビット列識別番号復号部が復号した前記ビット列識別番号を、該ビット列識別番号に関連付けられたビット列に変換するビット列識別番号変換部と、
   前記復号対象のデータを構成する前記文字識別番号のバイナリデータと前記ビット列識別番号変換部が変換したビット列とを前記文字識別番号に復号する復号部と、
   前記文字識別番号記憶部を参照して、前記復号部が復号した前記文字識別番号を、該文字識別番号に関連付けられた文字に変換する変換部と、
   を備える復号装置。
9. 符号化対象のデータに含まれる文字と、該文字を識別する文字識別番号と、を関連付けて記憶する文字識別番号記憶部を参照して、前記符号化対象のデータに含まれる文字を、該文字に関連付けられた文字識別番号に変換する変換ステップと、
   前記変換ステップで変換した文字識別番号をバイナリデータに符号化する符号化ステップと、
   前記符号化ステップで符号化した文字識別番号のバイナリデータに出現する同一のビット列ごとに、該ビット列を識別するビット列識別番号を関連付けてビット列識別番号記憶部に記憶するビット列識別番号関連付ステップと、
   前記ビット列識別番号記憶部を参照して、前記文字識別番号のバイナリデータに出現する同一のビット列を、該ビット列に関連付けられたビット列識別番号に変換するビット列識別番号変換ステップと、
   前記ビット列識別番号変換ステップで変換したビット列識別番号に、復号時に前記ビット列識別番号記憶部を参照することを示す参照フラグを関連付けて、該ビット列識別番号をバイナリデータに符号化する参照フラグ付き符号化ステップと、
   を備え、
   前記文字識別番号は、前記符号化対象のデータにおいて出現頻度の高い文字に関連付けられたものほど小さく、
   前記符号化ステップにおいて、前記文字識別番号が小さいほど該文字識別番号を符号化して得られるバイナリデータのデータ量が小さい符号化方法を用いて、前記文字識別番号をバイナリデータに符号化する、
   符号化方法。
10. 復号対象のデータを特定するための条件を入力する入力ステップと、
    符号化対象のデータに含まれる各文字を識別する各文字識別番号のバイナリデータと、前記各文字識別番号のバイナリデータに出現する同一のビット列を識別するビット列識別番号のバイナリデータと、で構成された圧縮データのうち、前記条件を満たすデータを復号対象のデータとして特定する特定ステップと、
    前記特定ステップで特定した前記復号対象のデータを構成する前記文字識別番号のバイナリデータと前記ビット列識別番号のバイナリデータとのうち、前記ビット列識別番号のバイナリデータを前記ビット列識別番号に復号するビット列識別番号復号ステップと、
    前記各文字識別番号のバイナリデータに出現する前記同一のビット列ごとに、該ビット列を識別する前記ビット列識別番号を関連付けて記憶するビット列識別番号記憶部を参照して、前記ビット列識別番号復号ステップで復号した前記ビット列識別番号を、該ビット列識別番号に関連付けられたビット列に変換するビット列識別番号変換ステップと、
    前記復号対象のデータを構成する前記文字識別番号のバイナリデータと前記ビット列識別番号変換ステップで変換したビット列とを前記文字識別番号に復号する復号ステップと、
    前記符号化対象のデータに含まれる文字と、該文字を識別する前記文字識別番号と、を関連付けて記憶する文字識別番号記憶部を参照して、前記復号ステップで復号した前記文字識別番号を、該文字識別番号に関連付けられた文字に変換する変換ステップと、
    を備える復号方法。
11. コンピュータを、
    符号化対象のデータに含まれる文字と、該文字を識別する文字識別番号と、を関連付けて記憶する文字識別番号記憶部を参照して、前記符号化対象のデータに含まれる文字を、該文字に関連付けられた文字識別番号に変換する変換部、
    前記変換部が文字識別番号をバイナリデータに符号化する符号化部、
    前記符号化部が符号化した文字識別番号のバイナリデータに出現する同一のビット列ごとに、該ビット列を識別するビット列識別番号を関連付けてビット列識別番号記憶部に記憶するビット列識別番号関連付部、
    前記ビット列識別番号記憶部を参照して、前記文字識別番号のバイナリデータに出現する同一のビット列を、該ビット列に関連付けられたビット列識別番号に変換するビット列識別番号変換部、
    前記ビット列識別番号変換部が変換したビット列識別番号に、復号時に前記ビット列識別番号記憶部を参照することを示す参照フラグを関連付けて、該ビット列識別番号をバイナリデータに符号化する参照フラグ付き符号化部、
    として機能させ、
    前記文字識別番号は、前記符号化対象のデータにおいて出現頻度の高い文字に関連付けられたものほど小さく、
    前記コンピュータを前記符号化部として機能させる際、前記文字識別番号が小さいほど該文字識別番号を符号化して得られるバイナリデータのデータ量が小さい符号化方法を用いて、前記文字識別番号をバイナリデータに符号化する、
    ためのプログラム。
12. コンピュータを、
    復号対象のデータを特定するための条件を入力する入力部、
    符号化対象のデータに含まれる各文字を識別する各文字識別番号のバイナリデータと、前記各文字識別番号のバイナリデータに出現する同一のビット列を識別するビット列識別番号のバイナリデータと、で構成された圧縮データのうち、前記条件を満たすデータを復号対象のデータとして特定する特定部、
    前記特定部が特定した前記復号対象のデータを構成する前記文字識別番号のバイナリデータと前記ビット列識別番号のバイナリデータとのうち、前記ビット列識別番号のバイナリデータを前記ビット列識別番号に復号するビット列識別番号復号部、
    前記各文字識別番号のバイナリデータに出現する前記同一のビット列ごとに、該ビット列を識別する前記ビット列識別番号を関連付けて記憶するビット列識別番号記憶部を参照して、前記ビット列識別番号復号部が復号した前記ビット列識別番号を、該ビット列識別番号に関連付けられたビット列に変換するビット列識別番号変換部、
    前記復号対象のデータを構成する前記文字識別番号のバイナリデータと前記ビット列識別番号変換部が変換したビット列とを前記文字識別番号に復号する復号部、
    前記符号化対象のデータに含まれる文字と、該文字を識別する前記文字識別番号と、を関連付けて記憶する文字識別番号記憶部を参照して、前記復号部が復号した前記文字識別番号を、該文字識別番号に関連付けられた文字に変換する変換部、
    として機能させるためのプログラム。

Images