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