(57)【要約】【課題】最長一致の文字列探索を用いて文字列を符号化する場合に、圧縮速度および圧縮率の向上を図る。【解決手段】符号化装置１００は、符号化対象のテキストデータを読み込み、符号化対象のテキストデータの文字または単語それぞれを、符号化対象のテキストデータに出現する、符号化済みの文字または単語それぞれについて出現位置をビットマップデータとして対応付けたビットマップ型インデックス１２３を用いて符号化し、符号化と同時に、現に符号化した文字または単語についてビットマップ型インデックス１２３を更新する。【選択図】図５
2018061166.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
符号化対象のテキストデータを読み込み、
前記テキストデータの文字または単語それぞれを、前記テキストデータに出現する、符号化済みの文字または単語それぞれについて出現位置をビットマップデータとして対応付けたインデックス情報を用いて符号化し、
符号化と同時に、現に符号化した文字または単語について前記インデックス情報を更新する
処理を行わせる符号化プログラム。
【請求項２】
前記インデックス情報を用いて符号化する処理は、前記インデックス情報を参照し、前記テキストデータの連続する文字または単語について、符号化済みの文字または単語との最長一致探索を行い、最長一致探索により一致した文字列または単語列を動的辞書に登録して、符号化する
処理を行わせる請求項１に記載の符号化プログラム。
【請求項３】
前記インデックス情報を用いて符号化する処理は、前記テキストデータの連続する文字または単語について、実データである前記テキストデータとの照合を行わず、前記インデックス情報を参照し、最長一致探索により一致した文字列または単語列を前記動的辞書に登録し、登録した前記文字列または単語列に対応付けられた動的符号をもとに符号化する
処理を行わせる請求項２に記載の符号化プログラム。
【請求項４】
符号化対象のテキストデータを読み込む読込部と、
前記テキストデータの文字または単語それぞれを、前記テキストデータに出現する、符号化済みの文字または単語それぞれについて出現位置をビットマップデータとして対応付けたインデックス情報を用いて符号化する符号化部と、
符号化と同時に、現に符号化した文字または単語について前記インデックス情報を更新する更新部と、
を有することを特徴とする符号化装置。
【請求項５】
コンピュータが、
符号化対象のテキストデータを読み込み、
前記テキストデータの文字または単語それぞれを、前記テキストデータに出現する、符号化済みの文字または単語それぞれについて出現位置をビットマップデータとして対応付けたインデックス情報を用いて符号化し、
符号化と同時に、現に符号化した文字または単語について前記インデックス情報を更新する
処理を実行する符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化プログラムなどに関する。
【背景技術】
【０００２】
圧縮アルゴリズムとしては、ＬＺ７７を用いたＺＩＰが主流である。ＺＩＰでは、圧縮対象の文字列に対して、スライド窓を用いて最長一致探索し、圧縮符号を生成する。すなわち、ＺＩＰでは、すでに圧縮符号化された、スライド窓に存在するデータに圧縮対象の文字列と同一の文字列が存在した場合に、スライド窓からの相対アドレスと長さで圧縮符号を表現することにより圧縮を行う。スライド窓を用いた最長一致探索は、バイト単位で行われる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平１０−２８３３６８号公報
【特許文献２】特開平７−６４５８５号公報
【特許文献３】特開平５−１５８６５２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来のスライド窓を用いた、最長一致探索の技術では、圧縮速度および圧縮率が向上し難いという問題がある。
【０００５】
すなわち、スライド窓を用いた最長一致探索では、圧縮符号化と同時に該当する文字または、文字列をスライド窓に格納する必要があり、圧縮速度が低下する。また、最長一致探索の時間や圧縮符号の符号長が長くなりすぎないように、スライド窓のサイズは、一定以下に制限される必要がある。このため、スライド窓から溢れた文字列は最長一致の対象から外されるため、圧縮率が低下する。さらに、最長一致探索の際に、逐次、スライド窓に存在する実データとの照合が必要となり、圧縮速度が低下する。
【０００６】
１つの側面では、最長一致探索を用いて文字列や単語列を符号化する場合に、圧縮速度および圧縮率の向上を図ることを目的とする。
【課題を解決するための手段】
【０００７】
第１の案では、符号化プログラムは、コンピュータに、符号化対象のテキストデータを読み込み、前記テキストデータの文字または単語それぞれを、前記テキストデータに出現する、符号化済みの文字または単語それぞれについて出現位置をビットマップデータとして対応付けたインデックス情報を用いて符号化し、符号化と同時に、現に符号化した文字または単語について前記インデックス情報を更新する、処理を実行させる。
【発明の効果】
【０００８】
１つの態様によれば、最長一致探索を用いて文字列または単語列を符号化する場合に、圧縮速度および圧縮率の向上を図ることができる。
【図面の簡単な説明】
【０００９】
【図１】図１は、実施例に係る符号化処理の流れの一例を示す図（１）である。
【図２】図２は、実施例に係る符号化処理の流れの一例を示す図（２）である。
【図３】図３は、実施例に係る動的辞書の一例を示す図である。
【図４】図４は、実施例に係る符号化ファイルの構成例を示す図である。
【図５】図５は、実施例に係る符号化装置の構成の一例を示す機能ブロック図である。
【図６】図６は、実施例に係る符号化処理のフローチャートの一例を示す図である。
【図７】図７は、実施例に係る単語列の一致探索処理のフローチャートの一例を示す図である。
【図８】図８は、コンピュータのハードウェア構成例を示す図である。
【図９】図９は、コンピュータで動作するプログラムの構成例を示す図である。
【図１０】図１０は、実施形態のシステムにおける装置の構成例を示す図である。
【発明を実施するための形態】
【００１０】
以下に、本願の開示する符号化プログラム、符号化装置および符号化方法の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例】
【００１１】
［実施例に係る符号化処理］
図１および図２は、実施例に係る符号化処理の流れの一例を示す図である。図１および図２に示すように、符号化装置は、符号化対象のテキストデータの文字または単語それぞれを、符号化対象のテキストデータに出現する、符号化済みの文字または単語それぞれについて出現位置をビットマップとして対応付けたインデックス情報を用いて符号化する。すなわち、符号化装置は、繰り返し出現する連続する単語などの成句を、インデックス情報を用いて符号化する。かかるインデックス情報は、「ビットマップ型インデックス」といい、符号ＢＩで表わす。なお、文字には、単語列が含まれる。以降では、単語列を文字の一例として説明する。
【００１２】
ここで、ビットマップ型インデックスＢＩについて説明する。ビットマップ型インデックスＢＩは、符号化対象のテキストデータに含まれる単語または単語列を指定するポインタと単語または単語列のテキストデータ内のオフセット（出現位置）での存否を示すビットを連結したビット列である。すなわち、ビットマップ型インデックスＢＩとは、符号化対象のテキストデータに含まれる単語または単語列について、オフセット（出現位置）ごとの存否をインデックス化したビットマップのことをいう。一例として、単語または単語列がテキストデータ内のある出現位置に存在する場合には、出現位置に対応するオフセット（出現位置）の存否としてＯＮ、すなわち２進数の「１」を示す出現ビットが設定される。単語または単語列がテキストデータ内のある出現位置に存在しない場合には、出現位置に対応するオフセット（出現位置）の存否としてＯＦＦ、すなわち２進数の「０」が設定される。単語または単語列を指定するポインタとしては、例えば、単語または単語列の単語ＩＤが採用される。単語ＩＤは、単語または単語列そのものであっても良いし、単語または単語列の符号であっても良い。単語または単語列の符号は、符号化されたコード（符号化コード）のことをいい、後述する静的コードおよび動的コードに対応する。
【００１３】
例えば、図１に示すように、ビットマップ型インデックスＢＩのＸ軸はオフセット（出現位置）を表し、Ｙ軸は単語ＩＤを表す。つまり、ビットマップ型インデックスＢＩに含まれる各ビットマップは、単語ＩＤが示す単語または単語列の、オフセット（出現位置）ごとの存否を表す。
【００１４】
ここでは、ｎが３９であるとして説明する。符号化対象のテキストデータＦ１の１０番目の位置に単語「ｉｎ」が出現するので、単語「ｉｎ」に対応するビットマップの１０ビット目の出現位置にＯＮ、すなわち２進数の「１」を示す出現ビットが設定される。符号化対象のテキストデータＦ１の１１番目の位置に単語「ｆｒｏｎｔ」が出現するので、単語「ｆｒｏｎｔ」に対応するビットマップの１１ビット目の出現位置にＯＮ、すなわち２進数の「１」を示す出現ビットが設定される。符号化対象のテキストデータＦ１の１２番目の位置に単語「ｏｆ」が出現するので、単語「ｏｆ」に対応するビットマップの１２ビット目の出現位置にＯＮ、すなわち２進数の「１」を示す出現ビットが設定される。符号化対象のテキストデータＦ１の２０番目の位置に単語「ｉｎ」が出現するので、単語「ｉｎ」に対応するビットマップの２０ビット目の出現位置にＯＮ、すなわち２進数の「１」を示す出現ビットが設定される。なお、ビットマップ型インデックスＢＩへの出現ビットは、テキストデータＦ１内の単語が符号化される都度、単語に対応するビットマップの出現位置に設定される。
【００１５】
符号化装置は、このようなビットマップ型インデックスＢＩを参照し、テキストデータＦ１の連続する単語列について、符号化済みの単語または単語列との最長一致単語列の探索処理を実行する。ここでは、テキストデータＦ１内の３０個目に出現する「ｉｎ」から連続する単語列を一例として、最長一致単語列の探索処理について説明する。
【００１６】
例えば、図２に示すように、符号化装置は、テキストデータＦ１内の３０個目に出現する今回の単語「ｉｎ」に対するビットマップを１ビットだけ左シフトする（ｓ１）。ここでは、ビットマップの１１ビット目と２１ビット目に「１」が設定されている。符号化装置は、テキストデータＦ１内の３１個目に出現する次の単語「ｆｒｏｎｔ」に対するビットマップを、ビットマップ型インデックスＢＩから抽出する。符号化装置は、今回の単語「ｉｎ」に対するビットマップと、抽出した次の単語「ｆｒｏｎｔ」に対するビットマップとをＡＮＤ演算する（ｓ２）。そして、符号化装置は、演算の結果、全てのビットが「０」であるか否かを判定する。ここでは、ビットマップの２１ビット目が「０」として算出されたが、１１ビット目が「１」として算出されたので、全てのビットが「０」であるとはいえないと判定される。すなわち、符号化装置は、今回の単語と次の単語とを含む単語列「ｉｎ  ｆｒｏｎｔ」について、符号化済みの単語または単語列と一致すると判定する。
【００１７】
次に、符号化装置は、今回の単語列「ｉｎ  ｆｒｏｎｔ」に対するビットマップを１ビットだけ左シフトする（ｓ３）。ここでは、ビットマップの１２ビット目に「１」が設定されている。符号化装置は、テキストデータＦ１内の３２個目に出現する次の単語「ｏｆ」に対するビットマップを、ビットマップ型インデックスＢＩから抽出する。符号化装置は、今回の単語列「ｉｎ  ｆｒｏｎｔ」に対するビットマップと、抽出した次の単語「ｏｆ」に対するビットマップとをＡＮＤ演算する（ｓ４）。そして、符号化装置は、演算の結果、全てのビットが「０」であるか否かを判定する。ここでは、ビットマップの１２ビット目が「１」として算出されたので、全てのビットが「０」であるとはいえないと判定される。すなわち、符号化装置は、今回の単語列と次の単語とを含む単語列「ｉｎ  ｆｒｏｎｔ  ｏｆ」について、符号化済みの単語または単語列と一致すると判定する。
【００１８】
次に、符号化装置は、今回の単語列「ｉｎ  ｆｒｏｎｔ  ｏｆ」に対するビットマップを１ビットだけ左シフトする（ｓ５）。ここでは、ビットマップの１３ビット目に「１」が設定されている。符号化装置は、テキストデータＦ１内の３３個目に出現する次の単語「ｍｙ」に対するビットマップを、ビットマップ型インデックスＢＩから抽出する。ここでは、ビットマップの２１ビット目に「１」が設定されている。符号化装置は、今回の単語列「ｉｎ  ｆｒｏｎｔ  ｏｆ」に対するビットマップと、抽出した次の単語「ｍｙ」に対するビットマップとをＡＮＤ演算する（ｓ６）。そして、符号化装置は、演算の結果、全てのビットが「０」であるか否かを判定する。ここでは、ビットマップの１３ビット目および２１ビット目がどちらも「０」として算出されたので、全てのビットが「０」であると判定される。すなわち、符号化装置は、今回の単語列と次の単語とを含む単語列「ｉｎ  ｆｒｏｎｔ  ｏｆ  ｍｙ」について、符号化済みの単語または単語列と一致しないと判定する。つまり、今回の単語列である「ｉｎ  ｆｒｏｎｔ  ｏｆ」が最長一致単語列となる。
【００１９】
そして、符号化装置は、今回の単語列「ｉｎ  ｆｒｏｎｔ  ｏｆ」が動的辞書Ｄ０に登録されていなければ、動的辞書Ｄ０に登録し、今回の単語列を動的単語として符号化する（ｓ７）。符号化装置は、符号化された動的コードを符号化コードとして出力する。なお、符号化装置は、今回の単語列が動的辞書Ｄ０に登録されていれば、登録されている動的コードを符号化コードとして出力する。そして、符号化装置は、動的コードを単語ＩＤとして、単語ＩＤに対するビットマップの、当該単語ＩＤが示す単語の出現位置に出現ビットを設定する。すなわち、符号化装置は、単語列「ｉｎ  ｆｒｏｎｔ  ｏｆ」に対するビットマップの出現位置に出現ビットを設定する。
【００２０】
そして、符号化装置は、出力された符号化コードを、符号化ファイルの符号化データに出力する。
【００２１】
ここでいう動的辞書Ｄ０とは、静的辞書に登録されていない単語または単語列と、動的に付された動的コードとを対応付けた辞書である。ここでいう単語列とは、連続して結合される連結単語であり、符号化するテキストデータの中で繰り返し出現する特長がある単語のことをいう。静的辞書に登録されていない単語には、一例として、出現頻度の低い単語（低頻度単語）であっても良い。ここでいう単語（低頻度単語）とは、専門単語、新語、未知語などがある。専門単語とは、ある特定の学問の分野や業界などの間で通用する単語であり、符号化する文書の中で繰り返し出現する特長がある単語のことをいう。新語とは、流行語などの新しく作られた単語であり、符号化する文書の中で繰り返し出現する特長がある単語のことをいう。未知語とは、専門単語でなく、新語でない単語であり、符号化する文書の中で繰り返し出現する特長がある単語のことをいう。なお、動的辞書Ｄ０には、静的辞書に登録されていない単語または単語列の出現順に、動的コードに対応付けられた単語がバッファ部に登録される。動的辞書Ｄ０に関する詳しい説明は後述する。
【００２２】
ここでいう静的辞書とは、一般的な英語辞典、国語辞典や教科書などを基にして、文書中に出現する単語の出現頻度を特定し、出現頻度のより高い単語に対して、より短い符号を割り当てた辞書である。静的辞書には、それぞれの単語に対応する符号である静的コードがあらかじめ登録されている。
【００２３】
［動的辞書の一例］
図３は、実施例に係る動的辞書の一例を示す図である。図３に示される動的辞書Ｄ０は、バッファ部Ｄ１とアドレステーブルＤ２とを含む。バッファ部Ｄ１は、文字列を記憶する。アドレステーブルＤ２は、動的コードと、格納位置と、データ長とを対応付けて保持する。動的コードは、あらかじめ定められた固定長のコードであり、例えば圧縮符号である。そして、動的コードは、単語または単語列の文字列が登録された順に割り当てられる。ここでは、動的コードは、１６進数「Ａ」から始まる固定長２バイトのコードである。格納位置は、バッファ部Ｄ１に格納された文字列の位置を示す。データ長は、バッファ部Ｄ１に格納された文字列の長さ（バイト長）を示す。
【００２４】
例えば、単語列「ｉｎ  ｆｒｏｎｔ  ｏｆ△」に動的コードが割り当てられる場合について説明する。なお、“△”は、空白を意味するものとする。符号化装置は、単語列「ｉｎ  ｆｒｏｎｔ  ｏｆ△」をバッファ部Ｄ１に格納する。符号化装置は、単語列を格納した格納位置および格納したデータ長をアドレステーブルＤ２に登録する。ここでは、符号化装置は、格納位置として「１６」、データ長として「１２」をアドレステーブルＤ２に登録する。符号化装置は、単語列に対応付けられたアドレステーブルＤ２の動的コードを符号化コードとして割り当てる。ここでは、符号化装置は、単語列「ｉｎ  ｆｒｏｎｔ  ｏｆ△」に対応付けられた動的コード「Ａ００２ｈ」を符号化コードとして割り当てる。
【００２５】
［符号化ファイルの構成例］
図４は、実施例に係る符号化ファイルの構成例を示す図である。図４に示すように、符号化ファイルＦ２は、ヘッダ部と、符号化データと、トレーラ部とを有する。符号化データは、テキストファイルＦ１の符号化された符号化コード群を記憶する。トレーラ部は、符号化処理が完了した後の動的辞書Ｄ０の情報やビットマップ型インデックスＢＩなどを記憶する。動的辞書Ｄ０の情報は、図３に示した動的辞書の情報に対応する。ヘッダ部は、例えば、符号化ファイルＦ２の生成に用いられた符号化アルゴリズムを識別する情報や、符号化に用いられたパラメータなどの情報を記憶し、例えば、トレーラ部に格納された動的辞書Ｄ０へのポインタなどが格納される。なお、トレーラ部は、ビットマップ型インデックスＢＩを記憶すると説明したが、記憶しない場合であっても良い。
【００２６】
［実施例に係る符号化装置の構成］
図５は、実施例に係る符号化装置の構成の一例を示す機能ブロック図である。図５に示すように、符号化装置１００は、制御部１１０および記憶部１２０を有する。
【００２７】
制御部１１０は、図１および図２に示した符号化処理を実行する処理部である。制御部１１０は、ファイルリード部１１１、出現位置有無判定部１１２、最長一致単語列探索部１１３、単語列符号化部１１４、単語符号化部１１５、インデックス更新部１１６およびファイルライト部１１７を有する。
【００２８】
記憶部１２０は、例えばフラッシュメモリ（Flash  Memory）やＦＲＡＭ（登録商標）（Ferroelectric  Random  Access  Memory）などの不揮発性の半導体メモリ素子などの記憶装置に対応する。記憶部１２０は、静的辞書１２１、動的辞書１２２およびビットマップ型インデックス１２３を有する。
【００２９】
静的辞書１２１は、一般的な英語辞典、国語辞典や教科書などを基にして、文書中に出現する単語の出現頻度を特定し、出現頻度のより高い単語に対して、より短い符号を割り当てた辞書である。静的辞書１２１には、それぞれの単語に対応する符号である静的コードがあらかじめ登録されている。
【００３０】
動的辞書１２２は、静的辞書１２１に登録されていない単語および単語列と動的に付された動的コードとを対応付けた辞書である。なお、動的辞書１２２は、動的辞書Ｄ０に対応する。動的辞書１２２の説明は、図３と同様であるので、その説明を省略する。
【００３１】
ビットマップ型インデックス１２３は、テキストデータに含まれる単語または単語列について、オフセット（出現位置）ごとの存否をインデックス化したビットマップの集合である。なお、ビットマップ型インデックス１２３は、ビットマップ型インデックスＢＩに対応する。ビットマップ型インデックス１２３の説明は、図１と同様であるので、その説明を省略する。
【００３２】
制御部１１０は、ファイルリード部１１１、単語出現有無判定部１１２、最長一致単語列探索部１１３、単語列符号化部１１４、単語符号化部１１５、インデックス更新部１１６およびファイルライト部１１７を有する。
【００３３】
ファイルリード部１１１は、符号化対象のファイルを記憶領域に読み出す。ファイルリード部１１１は、テキストデータＦ１を記憶領域から読み出し、読み出したテキストデータＦ１に対して字句解析を行う。ファイルリード部１１１は、字句解析した結果の各単語を、順次、単語出現有無判定部１１２に出力する。
【００３４】
単語出現有無判定部１１２は、単語に対するビットマップを用いて、当該単語の出現有無を判定する。例えば、単語出現有無判定部１１２は、単語に対応する単語ＩＤを、静的辞書１２１から取得する。単語出現有無判定部１１２は、取得した単語ＩＤに対するビットマップをビットマップ型インデックス１２３から抽出する。そして、単語出現有無判定部１１２は、抽出したビットマップに出現ビットが設定されているか否かを判定する。
【００３５】
最長一致単語列探索部１１３は、単語に対するビットマップに出現ビットが設定されている場合には、次の単語を含む単語列について、符号化済みの単語または単語列との最長一致探索を行う。例えば、最長一致単語列探索部１１３は、今回処理した単語または単語列に対するビットマップを１ビットだけ左シフトする。最長一致単語列探索部１１３は、次の単語に対するビットマップをビットマップ型インデックス１２３から抽出する。最長一致単語列探索部１１３は、今回処理した単語または単語列に対するビットマップと次の単語に対するビットマップをＡＮＤ演算する。そして、最長一致単語列探索部１１３は、演算した結果、ビットマップの全てのビットが「０」であるか否かを判定する。最長一致単語列探索部１１３は、ビットマップの全てのビットが「０」であるとはいえない場合には、今回処理した単語または単語列と次の単語とを含む単語列について、符号化済みの単語または単語列と一致すると判定する。そして、最長一致単語列探索部１１３は、さらに、次の単語を含む単語列について、符号化済みの単語または単語列との最長一致探索を行う。最長一致単語列探索部１１３は、ビットマップの全てのビットが「０」である場合には、今回処理した単語または単語列と次の単語とを含む単語列について、符号化済みの単語または単語列と一致しないと判定する。この結果、今回処理した単語または単語列が単語列である場合に、当該単語列が最長一致単語列である。
【００３６】
単語列符号化部１１４は、最長一致単語列を符号化する。例えば、単語列符号化部１１４は、最長一致単語列が動的辞書１２２に登録されているか否かを判定する。単語列符号化部１１４は、最長一致単語列が動的辞書１２２に登録されていない場合には、この単語列を動的辞書１２２に登録し、この単語列に動的コードを割り当てる。一例として、単語列符号化部１１４は、最長一致単語列をバッファ部Ｄ１に格納するとともに、アドレステーブルＤ２の新たな動的コードに対応するレコードに、この単語列を格納した格納位置および格納したデータ長を格納する。単語列符号化部１１４は、この単語列を、新たな動的コードに符号化する。なお、単語列符号化部１１４は、最長一致単語列が動的辞書１２２に登録されている場合には、この単語列を、登録されている動的コードに符号化する。そして、単語列符号化部１１４は、符号化された動的コードおよびテキストデータＦ１内の出現位置をインデックス更新部１１６に出力する。
【００３７】
単語符号化部１１５は、単語を符号化する。例えば、単語符号化部１１５は、単語に対するビットマップに出現ビットが出現されていない場合、当該単語を、静的辞書１２１に登録されている静的コードに符号化する。そして、単語符号化部１１５は、符号化された静的コードおよびテキストデータＦ１内の出現位置をインデックス更新部１１６に出力する。
【００３８】
インデックス更新部１１６は、ビットマップ型インデックス１２３を更新する。例えば、インデックス更新部１１６は、単語列符号化部１１４から出力された動的コードおよびテキストデータＦ１内の出現位置を用いて、動的コードに対するビットマップの出現位置に出現ビットを設定する。インデックス更新部１１６は、単語符号化部１１５から出力された静的コードおよびテキストデータＦ１内の出現位置を用いて、静的コードに対するビットマップの出現位置に出現ビットを設定する。
【００３９】
ファイルライト部１１７は、符号化対象のファイルにおけるテキストデータＦ１を全て符号化した後、それぞれの符号化コードを符号化ファイルＦ２の符号化データに格納する。ファイルライト部１１７は、動的辞書１２２の情報およびビットマップ型インデックス１２３を符号化ファイルＦ２のトレーラ部に書き込む。
【００４０】
［実施例に係る符号化処理の処理手順］
次に、図５に示した制御部１１０の処理手順について、図６を参照して説明する。図６は、実施例に係る符号化処理のフローチャートの一例を示す図である。
【００４１】
図６に示すように、制御部１１０は、前処理を実行する（ステップＳ１１）。例えば、制御部１１０は、各種記憶領域を記憶部１２０に確保する。そして、制御部１１０は、符号化対象のファイルを読み出し、読出用の記憶領域にテキストデータＦ１を格納する（ステップＳ１２）。
【００４２】
そして、制御部１１０は、読出用の記憶領域から単語を読み出す（ステップＳ１３）。制御部１１０は、読み出した単語に対するビットマップを一時領域に保持する（ステップＳ１４）。例えば、制御部１１０は、単語に対する静的コードを単語ＩＤとして静的辞書１２１から取得する。制御部１１０は、単語ＩＤに対するビットマップをビットマップ型インデックス１２３から抽出し、抽出したビットマップを一時的な記憶領域に保持する。
【００４３】
制御部１１０は、単語に対するビットマップに出現ビットが設定されているか否かを判定する（ステップＳ１５）。単語に対するビットマップに出現ビットが設定されていないと判定した場合には（ステップＳ１５；Ｎｏ）、制御部１１０は、静的辞書１２１に登録されている静的コードを符号化コードとして出力する（ステップＳ１６）。そして、制御部１１０は、単語の静的コードおよびテキストデータＦ１内の出現位置を用いて、当該単語に対するビットマップの出現位置に「１」（出現ビット）を書き込む（ステップＳ１７）。そして、制御部１１０は、ステップＳ２６に移行する。
【００４４】
一方、単語に対するビットマップに出現ビットが設定されていると判定した場合には（ステップＳ１５；Ｙｅｓ）、制御部１１０は、今回の対象（単語または単語列）と次の単語を含む単語列の一致探索を実行する（ステップＳ１８）。なお、単語列の一致探索処理のフローチャートは、後述する。
【００４５】
一致探索を実行した結果、制御部１１０は、単語列が一致したか否かを判定する（ステップＳ１９）。単語列が一致したと判定した場合には（ステップＳ１９；Ｙｅｓ）、制御部１１０は、次の単語を含む単語列の一致探索を実行すべく、ステップＳ１８に移行する。
【００４６】
一方、単語列が一致しないと判定した場合には（ステップＳ１９；Ｎｏ）、制御部１１０は、今回の対象（単語または単語列）が単語列であるか否かを判定する（ステップＳ２０）。今回の対象が単語列でないと判定した場合には（ステップＳ２０；Ｎｏ）、制御部１１０は、今回の対象を静的コードに符号化すべく、ステップＳ１６に移行する。
【００４７】
一方、今回の対象が単語列であると判定した場合には（ステップＳ２０；Ｙｅｓ）、制御部１１０は、当該単語列が動的辞書１２２に登録されているか否かを判定する（ステップＳ２１）。当該単語列が動的辞書１２２に登録されていないと判定した場合には（ステップＳ２１；Ｎｏ）、制御部１１０は、当該単語列を動的辞書１２２に登録し、この単語列に動的コードを割り当てる（ステップＳ２２）。制御部１１０は、割り当てられた動的コードを符号化コードとして出力する（ステップＳ２３）。そして、制御部１１０は、ステップＳ２５に移行する。
【００４８】
一方、単語列が動的辞書１２２に登録されていると判定した場合には（ステップＳ２１；Ｙｅｓ）、制御部１１０は、動的辞書１２２に登録されている動的コードを符号化コードとして出力する（ステップＳ２４）。そして、制御部１１０は、ステップＳ２５に移行する。
【００４９】
ステップＳ２５において、制御部１１０は、単語列および各単語に対する各ビットマップに「１」を書き込む（ステップＳ２５）。例えば、制御部１１０は、単語列について、動的コードおよびテキストデータＦ１内の出現位置を用いて、当該単語列に対するビットマップの出現位置に「１」（出現ビット）を書き込む。そして、制御部１１０は、最長一致単語列の探索を実行した際に用いた各単語について、静的コードおよびテキストデータＦ１内の出現位置を用いて、当該各単語に対するビットマップの出現位置に「１」（出現ビット）を書き込む。そして、制御部１１０は、ステップＳ２６に移行する。
【００５０】
ステップＳ２６において、制御部１１０は、符号化コードを符号化ファイルＦ２の符号化データに書き込む（ステップＳ２６）。そして、制御部１１０は、ファイルの終点か否かを判定する（ステップＳ２７）。ファイルの終点でないと判定した場合には（ステップＳ２７；Ｎｏ）、制御部１１０は、次の単語を読み出すべく、ステップＳ１３に移行する。
【００５１】
一方、ファイルの終点であると判定した場合には（ステップＳ２７；Ｙｅｓ）、制御部１１０は、符号化処理を終了する。
【００５２】
［実施例に係る単語列の一致探索処理の処理手順］
図７は、実施例に係る単語列の一致探索処理のフローチャートの一例を示す図である。
【００５３】
図７に示すように、制御部１１０は、今回の対象（単語または単語列）に対するビットマップを１ビットだけ左シフトする（ステップＳ３１）。制御部１１０は、次の単語に対するビットマップを一時領域に保持する（ステップＳ３２）。そして、制御部１１０は、今回の対象に対するビットマップと次の単語に対するビットマップとをＡＮＤ演算する（ステップＳ３３）。
【００５４】
制御部１１０は、ＡＮＤ演算した結果を示すビットマップの全てのビットが「０」であるか否かを判定する（ステップＳ３４）。全てのビットが「０」であると判定した場合には（ステップＳ３４；Ｙｅｓ）、制御部１１０は、今回の対象と次の単語とを含む単語列が一致しないと判定する（ステップＳ３５）。すなわち、制御部１１０は、今回の対象と次の単語とを含む単語列について、符号化済みの単語または単語列と一致しないと判定する。そして、制御部１１０は、単語列の一致探索処理を終了する。
【００５５】
一方、全てのビットが「０」であるとはいえないと判定した場合には（ステップＳ３４；Ｎｏ）、制御部１１０は、今回の対象と次の単語とを含む単語列が一致すると判定する（ステップＳ３６）。すなわち、制御部１１０は、今回の対象と次の単語とを含む単語列について、符号化済みの単語または単語列と一致すると判定する。そして、制御部１１０は、単語列の一致探索処理を終了する。
【００５６】
これにより、符号化装置１００は、符号化対象のテキストデータＦ１を読み込み、符号化対象のテキストデータＦ１の文字または単語それぞれを、ビットマップ型インデックス１２３を用いて符号化する。ビットマップ型インデックス１２３は、符号化対象のテキストデータＦ１に出現する、符号化済みの文字または単語それぞれについて出現位置をビットマップデータとして対応付けたインデックス情報である。符号化装置１００は、符号化と同時に、符号化した文字または単語についてビットマップ型インデックスＢＩを更新する。かかる構成によれば、符号化装置１００は、ビットマップ型インデックス１２３を用いることで、ＬＺ７７などのスライド窓を利用した方式のように、限られた範囲との最長一致ではなく、符号化済みの文字または単語に対する最長一致を行うことができる。この結果、符号化装置１００は、スライド窓を利用した方式に比べて、圧縮率を向上させることができる。また、符号化装置１００は、ビットマップ型インデックス１２３を用いることで、最長一致の判定を、実際のテキストデータを参照することなくビットを参照することで行うことができる。この結果、符号化装置１００は、スライド窓を利用した方式に比べて、圧縮速度を向上させることができる。
【００５７】
また、符号化装置１００は、ビットマップ型インデックス１２３を参照し、符号化対象のテキストデータＦ１の連続する文字または単語について、符号化済みの文字または単語との最長一致探索を行う。符号化装置１００は、最長一致探索により一致した文字列または単語列を動的辞書１２２に登録して、符号化する。かかる構成によれば、符号化装置１００は、スライド窓を利用した方式に比べて、圧縮率を向上させることができる。すなわち、符号化装置１００は、ビットマップ型インデックス１２３を用いることで、符号化済みの全てのデータを対象にして最長一致探索を行うことができ、圧縮率を向上させることができる。
【００５８】
また、符号化装置１００は、符号化対象のテキストデータＦ１の連続する文字または単語について、実データである前記テキストデータＦ１との照合を行わず、ビットマップ型インデックス１２３を参照し、符号化済みの文字または単語との最長一致探索を行う。符号化装置１００は、最長一致探索により一致した文字列または単語列を動的辞書１２２に登録し、登録した文字列または単語列に対応付けられた動的符号をもとに符号化する。かかる構成によれば、符号化装置１００は、実データとの照合がないので、スライド窓を利用した方式に比べて、圧縮速度および圧縮率を向上させることができる。
【００５９】
［実施例に関連する他の態様］
以下、上述の実施形態における変形例の一部を説明する。下記の変形例のみでなく、本発明の本旨を逸脱しない範囲の設計変更は適宜行われうる。
【００６０】
また、実施例では、符号化装置１００は、ビットマップ型インデックス１２３を参照し、テキストデータＦ１内の連続する単語列について、符号化済みの単語または単語列との最長一致単語列の探索処理を実行すると説明した。しかしながら、符号化装置１００は、ビットマップ型インデックス１２３の代わりにビットマップ型インデックス１２３をビットマップごとにハッシュ化したハッシュ化インデックスを参照し、テキストデータＦ１内の連続する単語列について、最長一致単語列の探索処理を実行しても良い。かかる場合には、符号化装置１００は、ハッシュ化インデックス内の、対象となる単語または単語列に対応するハッシュ化ビットマップを復元して、復元したビットマップに対して最長一致単語列の探索処理を実行すれば良い。これにより、符号化装置１００は、符号化する際に、使用できる資源が少ない場合であっても、少ない資源で符号化することができる。
【００６１】
また、実施例に示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００６２】
［情報処理装置のハードウェア構成］
下記に、上述の実施形態に用いられるハードウェア及びソフトウェアについて説明する。図８は、コンピュータ１のハードウェア構成例を示す図である。コンピュータ１は、例えば、プロセッサ３０１、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）３０２、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）３０３、ドライブ装置３０４、記憶媒体３０５、入力インターフェース（Ｉ／Ｆ）３０６、入力デバイス３０７、出力インターフェース（Ｉ／Ｆ）３０８、出力デバイス３０９、通信インターフェース（Ｉ／Ｆ）３１０、ＳＡＮ（Ｓｔｏｒａｇｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）インターフェース（Ｉ／Ｆ）３１１およびバス３１２などを含む。それぞれのハードウェアはバス３１２を介して接続されている。
【００６３】
ＲＡＭ３０２は読み書き可能なメモリ装置であって、例えば、ＳＲＡＭ（Ｓｔａｔｉｃ  ＲＡＭ）やＤＲＡＭ（Ｄｙｎａｍｉｃ  ＲＡＭ）などの半導体メモリ、またはＲＡＭでなくてもフラッシュメモリなどが用いられる。ＲＯＭ３０３は、ＰＲＯＭ（Ｐｒｏｇｒａｍｍａｂｌｅ  ＲＯＭ）なども含む。ドライブ装置３０４は、記憶媒体３０５に記録された情報の読み出しか書き込みかの少なくともいずれか一方を行なう装置である。記憶媒体３０５は、ドライブ装置３０４によって書き込まれた情報を記憶する。記憶媒体３０５は、例えば、ハードディスク、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）などのフラッシュメモリ、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）、ブルーレイディスクなどの記憶媒体である。また、例えば、コンピュータ１は、複数種類の記憶媒体それぞれについて、ドライブ装置３０４及び記憶媒体３０５を設ける。
【００６４】
入力インターフェース３０６は、入力デバイス３０７と接続されており、入力デバイス３０７から受信した入力信号をプロセッサ３０１に伝達する回路である。出力インターフェース３０８は、出力デバイス３０９と接続されており、出力デバイス３０９に、プロセッサ３０１の指示に応じた出力を実行させる回路である。通信インターフェース３１０はネットワーク３を介した通信の制御を行なう回路である。通信インターフェース３１０は、例えばネットワークインターフェースカード（ＮＩＣ）などである。ＳＡＮインターフェース３１１は、ストレージエリアネットワークによりコンピュータ１と接続された記憶装置との通信の制御を行なう回路である。ＳＡＮインターフェース３１１は、例えばホストバスアダプタ（ＨＢＡ）などである。
【００６５】
入力デバイス３０７は、操作に応じて入力信号を送信する装置である。入力信号は、例えば、キーボードやコンピュータ１の本体に取り付けられたボタンなどのキー装置や、マウスやタッチパネルなどのポインティングデバイスである。出力デバイス３０９は、コンピュータ１の制御に応じて情報を出力する装置である。出力デバイス３０９は、例えば、ディスプレイなどの画像出力装置（表示デバイス）や、スピーカーなどの音声出力装置などである。また、例えば、タッチスクリーンなどの入出力装置が、入力デバイス３０７及び出力デバイス３０９として用いられる。また、入力デバイス３０７及び出力デバイス３０９は、コンピュータ１と一体になっていても良いし、コンピュータ１に含まれず、例えば、コンピュータ１に外部から接続する装置であっても良い。
【００６６】
例えば、プロセッサ３０１は、ＲＯＭ３０３や記憶媒体３０５に記憶されたプログラムをＲＡＭ３０２に読み出し、読み出されたプログラムの手順に従って制御部１１０の処理を行なう。その際にＲＡＭ３０２はプロセッサ３０１のワークエリアとして用いられる。記憶部１２０の機能は、ＲＯＭ３０３および記憶媒体３０５がプログラムファイル（後述のアプリケーションプログラム２４、ミドルウェア２３およびＯＳ２２など）やデータファイル（例えば、静的辞書１２１、動的辞書１２２、ビットマップ型インデックス１２３など）を記憶し、ＲＡＭ３０２がプロセッサ３０１のワークエリアとして用いられることによって実現される。プロセッサ３０１が読み出すプログラムについては、図９を用いて説明する。
【００６７】
図９は、コンピュータで動作するプログラムの構成例を示す図である。コンピュータ１において、図９に示すハードウェア群（ＨＷ）２１（３０１〜３１２）の制御を行なうＯＳ（オペレーティング・システム）２２が動作する。ＯＳ２２に従った手順でプロセッサ３０１が動作して、ハードウェア群（ＨＷ）２１の制御・管理が行なわれることにより、アプリケーションプログラム（ＡＰ）２４やミドルウェア（ＭＷ）２３に従った処理がハードウェア群２１で実行される。さらに、コンピュータ１において、ミドルウェア（ＭＷ）２３またはアプリケーションプログラム（ＡＰ）２４が、ＲＡＭ３０２に読み出されてプロセッサ３０１により実行される。
【００６８】
プロセッサ３０１が、符号化機能が呼び出された場合に、ミドルウェア２３またはアプリケーションプログラム２４の少なくとも一部に基づく処理を行なうことにより、（それらの処理をＯＳ２２に基づいてハードウェア群２１を制御して）制御部１１０の機能が実現される。符号化機能は、アプリケーションプログラム２４自体に含まれても良いし、アプリケーションプログラム２４に従って呼び出されることで実行されるミドルウェア２３の一部であっても良い。
【００６９】
図１０は、実施形態のシステムにおける装置の構成例を示す。図１０のシステムは、コンピュータ１ａ、コンピュータ１ｂ、基地局２およびネットワーク３を含む。コンピュータ１ａは、無線または有線の少なくとも一方により、コンピュータ１ｂと接続されたネットワーク３に接続している。
【００７０】
図５に示す符号化装置１００と図示しない復号化装置とは、図１０に示すコンピュータ１ａとコンピュータ１ｂとのいずれに含まれても良い。コンピュータ１ｂが符号化装置１００の機能を含み、コンピュータ１ａが復号化装置の機能を含んでも良いし、コンピュータ１ａが符号化装置１００の機能を含み、コンピュータ１ｂが復号化装置の機能を含んでも良い。また、コンピュータ１ａとコンピュータ１ｂとの双方が、符号化装置１００の機能および復号化装置の機能を備えても良い。
【符号の説明】
【００７１】
１００  符号化装置
１１０  制御部
１１１  ファイルリード部
１１２  単語出現有無判定部
１１３  最長一致単語列探索部
１１４  単語列符号化部
１１５  単語符号化部
１１６  インデックス更新部
１１７  ファイルライト部
１２０  記憶部
１２１  静的辞書
１２２  動的辞書
１２３  ビットマップ型インデックス
【図１】
2018061166.tif 000003
【図２】
2018061166.tif 000004
【図３】
2018061166.tif 000005
【図４】
2018061166.tif 000006
【図５】
2018061166.tif 000007
【図６】
2018061166.tif 000008
【図７】
2018061166.tif 000009
【図８】
2018061166.tif 000010
【図９】
2018061166.tif 000011
【図１０】
2018061166.tif 000012