JP2013186542A - プログラム、情報処理装置およびインデックス生成方法 - Google Patents

Abstract

【課題】伸長したデータに対応するインデックスを効率的に生成する。
【解決手段】記憶部１４は、符号と関連付けて、復号した記号とインデックス１３内において当該記号に対応するフラグ情報を識別するための識別情報とを含む辞書データ１４ａを記憶する。伸長部１５は、辞書データ１４ａから、圧縮データ１１に含まれる符号に関連付けられている記号と識別情報とを取得し、取得した記号を用いて伸長データ１２を生成し、また、取得した識別情報が示すインデックス１３内のフラグ情報を更新する。
【選択図】図１

Description

本発明はプログラム、情報処理装置およびインデックス生成方法に関する。

現在、データをネットワーク上で送信するときや記憶装置に保存するとき、データ量を削減するため、圧縮符号を用いてデータを圧縮することがある。例えば、ＺＩＰと呼ばれるファイルフォーマットでは、圧縮符号としてハフマン符号を用いることができる。ハフマン符号は、元のデータに含まれる記号（例えば、１つの文字や１バイトのビット列）のうち、出現頻度の高い記号にビット数の小さい符号を割り当て、出現頻度の低い記号にビット数の大きい符号を割り当てる。圧縮されたデータを伸長するときは、符号から元の記号（復号した記号）を判定するための辞書データを用意することがある。

また、文書データ群の中から、特定の文字列（文字数が１の場合を含んでもよい）を含む文書データを検索する文書検索技術が用いられている。例えば、複数の電子書籍ファイルの中から、ユーザの指定したキーワードを含む電子書籍ファイルを検索したいことがある。ここで、ターゲットの文字列が指定されてから文書データ群の全文を走査すると、検索時間が長くなるおそれがある。そこで、文書データ群の全文を予め走査して、文字列の有無を判定するためのインデックスを生成しておくことがある。文字列が指定されると、インデックスを参照して所望の文書データを判定することで、検索時間を短縮できる。

なお、複数の文書それぞれから、各文書に含まれる文字である１文字成分と当該文字に隣接する他の文字を示す隣接文字成分とを抽出して、１文字成分表と隣接文字成分表を生成し、生成した２つの表を用いて文書を検索する文書検索方法が提案されている。また、圧縮されたデータを伸長するとき、復号済の文字列を用いて辞書を順次拡張していき、拡張した辞書に基づいて後続の符号を復号する圧縮・伸長アルゴリズム（辞書式アルゴリズム）がある。また、ファイルの圧縮と並行して、複数の文字それぞれが当該ファイルに含まれているか否かを示すマップ群を生成することで、圧縮したファイルを伸長せずにキーワード検索を行えるようにしたデータ圧縮方法が提案されている。

特開平５−３２４７２２号公報 特開平９−２１８８７７号公報 特開２０１１−１００３２０号公報

ところで、圧縮されたデータを取得した情報処理装置は、そのデータにインデックスが付加されていない場合、そのデータを対象として文書検索を行えるように、インデックスを生成しておきたいことがある。例えば、圧縮された電子書籍ファイルを取得した情報端末装置は、複数の電子書籍ファイルの中からユーザの指定したキーワードを含むものを検索できるように、インデックスを生成したいことがある。

インデックスを生成する１つの方法として、例えば、圧縮されたデータを伸長し、伸長が完了した後、伸長されたデータに含まれる記号毎に、インデックスの中からその記号に対応するフラグを探して当該フラグを更新していく方法が考えられる。しかし、この方法は、インデックスを生成する過程でＲＡＭ（Random Access Memory）などの記憶装置にアクセスする回数が多くなることから、生成効率に改善の余地がある。

一側面では、本発明は、伸長したデータに対応するインデックスを、省資源のハードウェア環境においても効率的に生成できるプログラム、情報処理装置およびインデックス生成方法を提供することを目的とする。

一側面では、複数の記号それぞれに対応するフラグ情報を含み、圧縮データを伸長することで得られる伸長データに複数の記号それぞれが含まれているか否かをフラグ情報によって示すインデックスを生成するプログラムが提供される。プログラムを実行するコンピュータは、圧縮に用いられる符号と関連付けて、符号に対応する復号した記号と、インデックス内において復号した記号に対応するフラグ情報を識別するための識別情報とを含む辞書データにアクセスし、辞書データから、圧縮データに含まれる符号に関連付けられている復号した記号と識別情報とを取得する。取得した復号した記号を用いて伸長データを生成し、また、取得した識別情報が示すインデックス内のフラグ情報を更新する。

また、一側面では、複数の記号それぞれに対応するフラグ情報を含み、圧縮データを伸長することで得られる伸長データに複数の記号それぞれが含まれているか否かをフラグ情報によって示すインデックスを生成する情報処理装置が提供される。情報処理装置は、記憶部と伸長部とを有する。記憶部は、圧縮に用いられる符号と関連付けて、符号に対応する復号した記号と、インデックス内において復号した記号に対応するフラグ情報を識別するための識別情報とを含む辞書データを記憶する。伸長部は、辞書データから、圧縮データに含まれる符号に関連付けられている復号した記号と識別情報とを取得し、復号した記号を用いて伸長データを生成し、また、識別情報が示すインデックス内のフラグ情報を更新する。

また、一側面では、複数の記号それぞれに対応するフラグ情報を含み、圧縮データを伸長することで得られる伸長データに複数の記号それぞれが含まれているか否かをフラグ情報によって示すインデックスを生成する、コンピュータが実行するインデックス生成方法が提供される。圧縮に用いられる符号と関連付けて、符号に対応する復号した記号と、インデックス内において復号した記号に対応するフラグ情報を識別するための識別情報とを含む辞書データにアクセスし、辞書データから、圧縮データに含まれる符号に関連付けられている復号した記号と識別情報とを取得する。取得した復号した記号を用いて伸長データを生成し、また、取得した識別情報が示すインデックス内のフラグ情報を更新する。

一側面では、伸長したデータに対応するインデックスを、省資源のハードウェア環境においても効率的に生成できる。

第１の実施の形態の情報処理装置を示す図である。 情報端末装置のハードウェア例を示すブロック図である。 ファイルと項目とブロックの関係を示す図である。 インデックスのデータ構造例を示す図である。 圧縮ファイルのデータ構造例を示す図である。 スライド窓を用いた圧縮ファイルの伸長例を示す図である。 二分ハフマン木の例を示す図である。 情報端末装置で動作するソフトウェア例を示すブロック図である。 ハフマン木を表した構造体データの第１の例を示す図である。 ファイル伸長の第１の手順例を示すフローチャートである。 ファイル伸長の第１の手順例を示すフローチャート（続き）である。 構造体生成の第１の手順例を示すフローチャートである。 ハフマン復号の第１の手順例を示すフローチャートである。 第１のインデックス生成例を示す図である。 第２のインデックス生成例を示す図である。 第３のインデックス生成例を示す図である。 第４のインデックス生成例を示す図である。 変形したハフマン木の例を示す図である。 ハフマン木を表した構造体データの第２の例を示す図である。 構造体生成の第２の手順例を示すフローチャートである。 ハフマン復号の第２の手順例を示すフローチャートである。 ハフマン復号におけるビット演算の例を示す図である。 ファイル伸長の第２の手順例を示すフローチャートである。 ブロック境界におけるインデックス生成例を示す図である。

以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
図１は、第１の実施の形態の情報処理装置を示す図である。

情報処理装置１０は、圧縮データ１１を伸長して伸長データ１２を生成し、また、伸長データ１２に対応するインデックス１３を生成する。圧縮データ１１は、例えば、ハフマン符号を用いて圧縮されたＺＩＰファイルである。伸長データ１２は、例えば、電子化された小説や学術書や辞書などの電子書籍のファイルである。インデックス１３は、例えば、伸長データ１２に対する全文検索に用いられる。情報処理装置１０は、電子書籍リーダや電子辞書や携帯電話機などの情報端末装置であってもよいし、デスクトップコンピュータやサーバコンピュータなどの据え置き型装置であってもよい。

情報処理装置１０は、記憶部１４と伸長部１５を有する。記憶部１４は、圧縮データを伸長するときに参照される辞書データ１４ａを記憶する。記憶部１４は、ＲＡＭなどの揮発性記憶装置でもよいし、フラッシュメモリやＨＤＤ（Hard Disk Drive）などの不揮発性記憶装置でもよい。伸長部１５は、辞書データ１４ａを参照して圧縮データ１１を伸長し、伸長データ１２とインデックス１３を生成する。伸長部１５は、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサを含んでもよく、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field-Programmable Gate Array）などの電子回路を含んでもよい。メモリに格納したプログラムをプロセッサが実行することで以下の処理が実現されるとき、情報処理装置１０はコンピュータと言うことができる。

インデックス１３は、伸長データ１２に含まれ得る複数の記号それぞれに対応するフラグ情報を含み、伸長データ１２に各記号が含まれているか否かをフラグ情報によって示している。各記号に対応するフラグ情報は、例えば、その記号が出現するか否かを示す少なくとも１つのフラグを含む。フラグは、例えば、１ビットで表現され、その記号が出現するときは“１”に設定され出現しないときは“０”に設定される。辞書データ１４ａは、圧縮に用いられる符号と関連付けて、その符号に対応する記号と、インデックス１３内においてその記号に対応するフラグ情報を識別するための識別情報とを含む。辞書データ１４ａは、圧縮データ１１を伸長するときに、伸長部１５が生成するようにしてもよい。

伸長部１５は、圧縮データ１１を伸長するとき、辞書データ１４ａから、圧縮データ１１に含まれる符号に関連付けられている記号（復号した記号）と識別情報とを取得する。そして、伸長部１５は、辞書データ１４ａから取得した記号を用いて伸長データ１２を生成する。例えば、伸長部１５は、伸長結果としての記号列を格納するバッファの末尾に、取得した記号を格納する。また、伸長部１５は、インデックス１３のフラグ情報のうち、辞書データ１４ａから取得した識別情報が示すフラグ情報を更新する。例えば、伸長部１５は、識別情報が示すフラグ情報に含まれるフラグを“１”に設定する。

例えば、辞書データ１４ａに、ある符号に関連付けて、復号した記号ｔと識別情報０ｘ１Ｄ（１０進数で２９）が登録されているとする。圧縮データ１１からその符号を取得すると、伸長部１５は、伸長データ１２としての記号列に記号ｔを追加し、また、識別情報０ｘ１Ｄが指し示すインデックス１３内のフラグ情報を更新する。辞書データ１４ａに識別情報が登録されているため、伸長部１５は、伸長結果を格納するバッファから記号ｔを読み直してインデックス１３の中から記号ｔに対応するフラグ情報を探さなくてよい。

なお、伸長データ１２やインデックス１３における「記号」は、１つの文字でもよいし１バイトのビット列でもよい。１つの文字が２バイト以上で表現されるとき、その文字は複数の「記号」に分割されることがある。また、インデックス１３は、Ｎ個（Ｎは２以上の整数）の記号を含む記号列に対応するフラグ情報を含んでもよい。Ｎ＝２の記号列はバイグラム（bi-gram）、Ｎ＝３の記号列はトライグラム（tri-gram）と呼ぶことがある。その場合、伸長部１５は、例えば、伸長が完了した直近のＮ−１個の記号に対応する識別情報を、メモリなどの記憶装置に一時的に保存しておく。そして、伸長部１５は、次に辞書データ１４ａから取得した識別情報と保存してあるＮ−１個の記号分の識別情報との組み合わせによって、インデックス１３の中から記号列に対応するフラグ情報を特定する。

また、各記号または記号列に対応するフラグ情報は、伸長データ１２を分割した所定の単位毎に、当該単位のデータ内にその記号または記号列が含まれているか否かを示すフラグを含んでもよい。所定の単位は、例えば、ファイル、ファイル内の項目、所定長（例えば、２５６バイト、５１２バイト、１０２４バイトなど）のブロックなどである。伸長部１５は、伸長データ１２の種類（例えば、小説や辞書など）を判定し、判定した種類に応じて、ファイル・項目・ブロックなどの複数の単位の中から、フラグを作成する単位を選択するようにしてもよい。また、ブロック毎にフラグを作成する場合であって、２つのブロックに跨がる記号列が存在するとき、伸長部１５は、２つのブロックの両方がその記号列を含んでいることを示すように、その記号列に対応するフラグ情報を更新してもよい。

第１の実施の形態の情報処理装置１０によれば、復号した記号に対応するフラグ情報の識別情報が辞書データ１４ａに登録されているため、伸長データ１２の生成と並行して、伸長データ１２に対応するインデックス１３を効率的に生成できる。すなわち、圧縮データ１１の伸長が完了してから、伸長結果を格納するバッファから各記号を取得してインデックス１３内の更新するフラグ情報を探す方法では、伸長データ１２やインデックス１３を記憶するＲＡＭなどの記憶装置へのアクセスが多くなってしまう。これに対し、辞書データ１４ａに登録された識別情報を用いて、インデックス１３内の所望のフラグ情報に直接アクセスすることで、記憶装置へのアクセスを減らすことができる。また、圧縮データ１１の伸長が完了した時点で、伸長データ１２に対応するインデックス１３が生成されているため、伸長データ１２に対する検索をすぐに開始することが可能となる。

［第２の実施の形態］
図２は、情報端末装置のハードウェア例を示すブロック図である。
情報端末装置１００は、ユーザの操作に応じて、電子化された小説や学術書や辞書などの電子書籍を表示することができる情報端末装置である。電子書籍は、ハフマン符号を用いて圧縮されたＺＩＰファイルとして配布される。電子書籍のフォーマットとしては、ＩＤＰＦ（International Digital Publishing Forum）が標準化を進めるＥＰＵＢ（Electronic Publication）やＸＭＤＦ（ever-Extending Mobile Document Format）などが挙げられる。電子書籍ファイルは、例えば、本文を記載したＸＨＴＭＬ（Extensible HyperText Markup Language）ファイルや、表示方法を定義したＣＳＳ（Cascading Style Sheets）ファイルや、図形を表したＳＶＧ（Scalable Vector Graphics）ファイルを含む。

情報端末装置１００は、ＣＰＵ１０１、ＲＡＭ１０２、不揮発性メモリ１０３、ディスプレイ１０４、入力部１０５、カードリーダ１０６および無線通信部１０７を有する。なお、情報端末装置１００は、第１の実施の形態の情報処理装置１０の一例である。ＲＡＭ１０２や不揮発性メモリ１０３は第１の実施の形態の記憶部１４の一例であり、ＣＰＵ１０１は第１の実施の形態の伸長部１５の一例である。

ＣＰＵ１０１は、プログラムの命令を実行する演算器を含むプロセッサである。ＣＰＵ１０１は、不揮発性メモリ１０３に記憶されているプログラムやデータの少なくとも一部をＲＡＭ１０２にロードし、プログラムを実行する。なお、ＣＰＵ１０１は複数のプロセッサコアを備えてもよく、情報端末装置１００は複数のプロセッサを備えてもよく、以下で説明する処理を複数のプロセッサまたはプロセッサコアを用いて並列実行してもよい。

ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムや情報処理に用いられるデータを一時的に記憶する揮発性メモリである。なお、情報端末装置１００は、ＲＡＭ以外の種類のメモリを備えてもよく、複数のメモリを備えてもよい。

不揮発性メモリ１０３は、ＯＳ（Operating System）やファームウェアやアプリケーションソフトウェアなどのソフトウェアのプログラム、および、ＺＩＰファイルなどのデータを記憶する記憶装置である。不揮発性メモリ１０３は、例えば、フラッシュメモリである。なお、情報端末装置１００は、ＨＤＤなどの他の種類の不揮発性記憶装置を備えてもよく、複数の不揮発性記憶装置を備えてもよい。

ディスプレイ１０４は、ＣＰＵ１０１からの命令に従って、電子書籍を選択するための操作画面や選択された電子書籍のデータなどを表示する。ディスプレイ１０４としては、例えば、液晶ディスプレイ（ＬＣＤ：Liquid Crystal Display）や有機ＥＬ（Electro-Luminescence）ディスプレイなどを用いることができる。

入力部１０５は、ユーザの入力操作を検知し、押下されたボタンやタッチ位置などを示す入力信号をＣＰＵ１０１に出力する。入力部１０５としては、例えば、１またはそれ以上のボタンを備えるキーパッドや、タッチ位置を検出できるタッチパネルなどを用いることができる。情報端末装置１００は、複数の種類の入力デバイスを備えてもよい。

カードリーダ１０６は、カード型の可搬記録媒体である記録媒体２１に記録されたプログラムやデータを読み取る駆動装置（ドライブ）である。カードリーダ１０６は、ＣＰＵ１０１からの命令に従って、記録媒体２１から読み出したプログラムやデータをＲＡＭ１０２または不揮発性メモリ１０３に格納する。記録媒体２１は、例えば、ｍｉｃｒｏＳＤ（Secure Digital）メモリやフラッシュメモリなどの不揮発性の半導体メモリである。ただし、情報端末装置１００は、ディスク型の可搬記録媒体に記録されたプログラムやデータを読み取るディスクドライブを備えてもよい。その場合、記録媒体２１として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）などの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）などを使用できる。

無線通信部１０７は、携帯電話網や無線ＬＡＮ（Local Area Network）などの無線アクセス網に接続して無線通信を行う通信インタフェースである。無線通信部１０７は、無線アクセス網に属するアクセスポイント２２（基地局と呼ぶこともある）と無線通信する。無線通信部１０７は、アクセスポイント２２を介してサーバコンピュータから、プログラムやデータを受信し、ＲＡＭ１０２または不揮発性メモリ１０３に格納する。なお、情報端末装置１００は、有線の通信インタフェースを備えてもよい。

情報端末装置１００は、電子書籍として、記録媒体２１に記録されて配布されたＺＩＰファイルやネットワーク経由で配布されたＺＩＰファイルを、不揮発性メモリ１０３に格納する。そして、情報端末装置１００は、ユーザが指定したＺＩＰファイルを不揮発性メモリ１０３からＲＡＭ１０２にロードし、ＺＩＰファイルをＲＡＭ１０２上で伸長して、伸長したデータをディスプレイ１０４に表示する。電子書籍としてのＺＩＰファイルは、ＤＲＭ（Digital Rights Management）によって複製が制限されていることがある。情報端末装置１００は、電子書籍のデータをディスプレイ１０４に表示する毎にＺＩＰファイルを伸長し、伸長したデータを不揮発性メモリ１０３に保存しないことが好ましい。

図３は、ファイルと項目とブロックの関係を示す図である。不揮発性メモリ１０３に、圧縮された複数のＺＩＰファイルが格納され得る。各ＺＩＰファイルを伸長して得られるテキストファイル（例えば、ＸＨＴＭＬファイル）には、複数の項目が含まれ得る。項目は、例えば、電子書籍の小説や学術書における１つの章や節、電子辞書における１つの見出し語分の記載に相当する。また、伸長されたテキストファイルは、所定のバイト数（例えば、２５６バイト、５１２バイト、１０２４バイトなど）のブロックに分割され得る。１つの項目（例えば、サイズの大きい項目）は、複数のブロックを含むことがある。

図４は、インデックスのデータ構造例を示す図である。
情報端末装置１００は、ユーザが入力したキーワードを含む可能性のあるファイル、項目またはブロックを検索できるよう、インデックスを生成し、インデックスファイルを不揮発性メモリ１０３に格納する。不揮発性メモリ１０３に格納されたインデックスファイルを用いることで、情報端末装置１００は、各ＺＩＰファイルを伸長する前に、伸長するＺＩＰファイルを絞り込むことができる。１つのインデックスファイルは、ＺＩＰファイル毎に生成されてもよいし、複数のＺＩＰファイル分のインデックスを含んでもよい。

インデックスは、伸長したファイルに出現し得る１グラム（ユニグラム）の記号、２グラム（バイグラム）の記号列および３グラム（トライグラム）の記号列それぞれについてのビットマップを含む。第２の実施の形態では、「記号」として１バイト記号を考える。各記号は、０ｘ００〜０ｘＦＦ（１０進数で０〜２５５）の範囲の値を取る。インデックスは、最大で、１グラムに関する２５６個のビットマップと、２グラムに関する６５５３６個のビットマップと、３グラムに関する１６７７７２１６個のビットマップを含む。

１グラムのビットマップは、ビットマップＩＤによって識別される。例えば、ビットマップＩＤを、１グラムのビットマップを記憶する領域の先頭からのオフセットとして用いることで、そのビットマップの位置を示すアドレスが算出される。２グラムのビットマップは、１グラムに関する２つのビットマップＩＤの組み合わせよって識別される。例えば、記号列０ｘ０００１に対応するビットマップは、記号０ｘ００のビットマップＩＤと記号０ｘ０１のビットマップＩＤの組み合わせによって識別される。例えば、２つのビットマップＩＤを結合して得られる値を、２グラムのビットマップを記憶する領域の先頭からのオフセットとして用いることで、アドレスが算出される。３グラムのビットマップは、１グラムに関する３つのビットマップＩＤの組み合わせによって識別される。

各ビットマップは、複数の単位（ファイル、項目またはブロック）に対応する複数のビットを含む。ビット＝１は記号または記号列が出現することを示し、ビット＝０は記号または記号列が出現しないことを示す。第２の実施の形態のビットマップは、第１の実施の形態で述べたフラグ情報の一例である。図４に示すように、以下の第２の実施の形態の説明では、ビットマップが各ブロックに対応するビットを含んでいる場合を考える。

図５は、圧縮ファイルのデータ構造例を示す図である。第２の実施の形態の圧縮および伸長では、１バイト（８ビット）の記号を最小単位とし、各記号を０ｘ００〜０ｘＦＦの範囲の数値として扱う。２バイト文字や３バイト文字など複数バイトで表される文字は、文字単位で扱わずに複数の１バイト記号の列として扱うこととする。

ＺＩＰファイルの圧縮には、ＬＺ７７アルゴリズムとハフマン符号化とを組み合わせた可逆圧縮アルゴリズムが用いられる。データの圧縮では、６４ｋバイト（または、所定のバイト数）のスライド窓の記号列を利用して、以下の処理を行う。まず、６４ｋバイトの記号列における０ｘ００〜０ｘＦＦの各記号の出現頻度を算出し、ハフマン木を生成して各記号に対応する符号を決定する。そして、６４ｋバイトの記号列の先頭から末尾に向かって圧縮を進める。

現在着目している記号を先頭とする記号列であって、長さ３バイト以上の記号列が既出であるとき、その記号列を、一致した記号列の「バイト数」と先に出現した同じ記号列の「先頭アドレス」とに変換する。バイト数は、生成したハフマン木に従ってハフマン符号化される。先頭アドレスは、ＭＳＢ（Most Significant Bit）から数えて最初にビット＝１が現れる桁を示す数値とその桁より後ろにある残りのビット列とに分解され、桁を示す数値がハフマン符号化されて残りのビット列と結合される。一方、現在着目している記号を先頭とする記号列が上記の条件を満たさないとき、現在着目している１バイト記号をハフマン符号化する。なお、圧縮アルゴリズムについては、次の書籍にも記載されている：植松友彦，「文字データ圧縮アルゴリズム入門」，１９９４年。

情報端末装置１００が取得するＺＩＰファイルは、圧縮前の６４ｋバイトの記号列毎に生成された、図５に示すような構造の圧縮データを含む。圧縮データは、ヘッダ部と符号語部とを含む。ヘッダ部は、ハフマン符号化において、０ｘ００〜０ｘＦＦの２５６通りの記号それぞれが何ビットの符号に符号化されているかを示している。各符号の長さは１ビット以上１６ビット以下であり、符号長は４ビットで表現できる。情報端末装置１００は、ヘッダ部に基づいて、圧縮に用いられたハフマン木を再現することができる。

符号語部は、複数の符号語を含む。各符号語の先頭ビットは制御用のビットである。先頭ビット＝０に続く符号語には、ハフマン符号化した１バイト記号が含まれる。ハフマン符号化した１バイト記号の長さは可変長（Ｎａビット）であり、１ビット以上１６ビット以下である。先頭ビット＝０に続く符号語は、ハフマン木に従って抽出し、１バイト記号に変換することで復号できる。先頭ビット＝１に続く符号語には、ハフマン符号化したバイト数と、上記のように変則的な符号化を行った先頭アドレスとが含まれる。ハフマン符号化したバイト数の長さは可変長（Ｎｌビット）であり、符号化した先頭アドレスは可変長である（Ｎｐビット）。先頭ビット＝１に続く符号語からは、ハフマン木に従った復号と伸長済の先の記号列からの複製とによって、３バイト以上の記号列を復号できる。

図６は、スライド窓を用いた圧縮ファイルの伸長例を示す図である。情報端末装置１００は、ＺＩＰファイル内の圧縮データを伸長するとき、符号語部に含まれる符号語の列を格納するバッファと伸長した記号列を格納するバッファを、ＲＡＭ１０２に確保する。情報端末装置１００は、伸長した記号列のうち直近の８ｋバイト（または、２ｋバイトや４ｋバイトなど所定長）の記号列を、スライド窓に含まれる記号列として取り扱う。前述の「先頭アドレス」は、スライド窓内での位置を示すアドレスである。

情報端末装置１００は、符号語の先頭ビット＝１のとき、その先頭ビットに続く「バイト数」を復号し、更にバイト数に続く「先頭アドレス」を復号する。そして、情報端末装置１００は、先頭アドレスとバイト数からスライド窓内の範囲を特定し、伸長した記号列を格納するバッファの末尾に、特定した範囲にある記号列を複製する。例えば、先頭アドレスが示す位置から後方に向かってａｂｃｄｅｆｇｈ・・・という記号列がスライド窓に含まれており、バイト数＝４である場合、記号列ａｂｃｄがバッファの末尾に追加される。一方、情報端末装置１００は、符号語の先頭ビット＝０のとき、その先頭ビットに続く１バイト記号を復号してバッファの末尾に追加する。その後、情報端末装置１００は、バッファに追加した記号の数だけスライド窓を後方にシフトする。

図７は、二分ハフマン木の例を示す図である。情報端末装置１００は、ＺＩＰファイルのヘッダ部に記載された複数の記号それぞれの符号長に基づいて、圧縮に用いられた二分ハフマン木を再現する。図７に示したハフマン木の例では、説明を簡単にするため、元のデータに８通りの記号０ｘ００〜０ｘ０７のみが含まれる場合を考えている。

情報端末装置１００は、記号０ｘ００〜０ｘＦＦ（図７の例では０ｘ００〜０ｘ０７）を、ハフマン符号化したときの符号長の小さい順に並べる。符号長が同じになる複数の記号は、数値の小さい順に並べる。例えば、記号０ｘ０１が符号長＝１、記号０ｘ０２が符号長＝２、記号０ｘ００，０ｘ０４，０ｘ０６が符号長＝４、記号０ｘ０３が符号長＝５、記号０ｘ０５，０ｘ０７が符号長＝６とする。この場合、８個の記号を０ｘ０１，０ｘ０２，０ｘ００，０ｘ０４，０ｘ０６，０ｘ０３，０ｘ０５，０ｘ０７の順に並べる。

また、情報端末装置１００は、符号長から各記号の出現頻度を推定する。出現頻度（出現確率）は、例えば、符号長をＬとすると１／２^Lと算出できる。そして、情報端末装置１００は、上記のように並べた記号の順序を維持して、各記号の出現頻度に基づいてハフマン木を生成する。すなわち、まず各記号に対応する葉ノードを生成し、出現頻度の小さい方から２つのノード（葉ノードまたは中間ノード）を選択して新たな中間ノードを生成することを繰り返す。例えば、図７の例では、出現頻度が１／２⁶である２つの葉ノード（０ｘ０５，０ｘ０７）を結合して出現確率が１／２⁵である中間ノードを生成し、この中間ノードと出現確率が１／２⁵である葉ノード（０ｘ０３）を結合する。

このようにハフマン木を生成すると、左側（図７では上側）の葉ノードほど深さが小さく、右側（図７では下側）の葉ノードほど深さが大きいハフマン木が生成される。情報端末装置１００は、分岐毎に左側の枝に“０”を割り当てて右側の枝に“１”を割り当てる（または、その逆を割り当てる）。そして、情報端末装置１００は、ルートノードから各葉ノードに向かって枝を辿ることで、各記号を符号化したときの符号を判定できる。例えば、記号０ｘ００は符号０と対応付けられ、記号０ｘ０２は符号１０と対応付けられる。以上のように、情報端末装置１００は、複数の記号を符号長の小さい順に並べ、符号長が同じになる記号は数値の小さい順に並べるというルールを、圧縮を行う装置と合意しておくことで、記号毎の符号長からハフマン木を一意に生成することができる。

図８は、情報端末装置で動作するソフトウェア例を示すブロック図である。不揮発性メモリ１０３に、圧縮ファイル１１１とインデックスファイル１１２が格納される。また、情報端末装置１００は、バッファ部１２０、ファイルアクセス部１３１、伸長部１３２、ハフマン木生成部１３３、ハフマン木記憶部１３４、表示制御部１３５および検索部１３６を有する。バッファ部１２０およびハフマン木記憶部１３４は、例えば、ＲＡＭ１０２に確保した記憶領域として実現される。ファイルアクセス部１３１、伸長部１３２、ハフマン木生成部１３３、表示制御部１３５および検索部１３６は、例えば、ＲＡＭ１０２にロードされＣＰＵ１０１により実行されるプログラムのモジュールとして実現される。

圧縮ファイル１１１は、ハフマン符号を用いて圧縮された、電子書籍としてのＺＩＰファイルである。圧縮ファイル１１１は、記録媒体２１から読み込まれ、または、アクセスポイント２２から受信されて、不揮発性メモリ１０３に格納されている。インデックスファイル１１２は、圧縮ファイル１１１を含む１またはそれ以上の圧縮ファイルについてのインデックスを含む。圧縮ファイル１１１についてのインデックスは、圧縮ファイル１１１を最初に伸長するときに生成されて、インデックスファイル１１２に登録される。

バッファ部１２０は、バッファ１２１，１２２、スタック１２３およびインデックス１２４を含む。バッファ１２１は、伸長結果としての記号列を一時的に記憶する６４ｋバイトの記憶領域である。バッファ１２２は、バッファ１２１に記憶された各記号に対応するビットマップＩＤを記憶する記憶領域である。スタック１２３は、バッファ１２２の末尾に記憶されたビットマップＩＤ（１つ前の記号に対応するビットマップＩＤ）と、バッファ１２２の最後から２番目に記憶されたビットマップＩＤ（２つ前の記号に対応するビットマップＩＤ）を記憶する記憶領域である。インデックス１２４は、図４に示した構造のビットマップの集合であり、インデックスファイル１１２に登録される。

ファイルアクセス部１３１は、ユーザの入力操作によって電子書籍が選択されると、選択された電子書籍に対応する圧縮ファイル１１１を不揮発性メモリ１０３から読み込み、伸長部１３２に渡す。なお、圧縮ファイル１１１の伸長は、圧縮ファイル１１１全体をＲＡＭ１０２に読み込んでから開始してもよいし、読み込みが完了する前に読み込み済の部分に対して開始してもよい。また、ファイルアクセス部１３１は、伸長部１３２によって生成されたインデックス１２４を、インデックスファイル１１２に登録する。

伸長部１３２は、圧縮ファイル１１１に含まれる１組のヘッダ部と符号語部を単位として伸長処理を行う。伸長部１３２は、ヘッダ部に記載された各記号の符号長をハフマン木生成部１３３に通知して、ハフマン木の構造体データの生成を指示する。そして、伸長部１３２は、ハフマン木記憶部１３４に記憶されたハフマン木の構造体を参照して、符号語部に含まれる複数の符号語を先頭から順に伸長し、伸長した記号をバッファ１２１に格納していく。また、伸長部１３２は、伸長の進行に合わせてスライド窓の位置を制御する。

また、伸長部１３２は、圧縮ファイル１１１から記号が伸長される毎に、インデックス１２４のビットマップを更新していく。伸長部１３２は、今回伸長した記号に対応するビットマップＩＤを判定し、そのビットマップＩＤによって特定される１グラムのビットマップを更新する。また、伸長部１３２は、今回のビットマップＩＤとスタック１２３に記憶された１つ前のビットマップＩＤとによって特定される２グラムのビットマップを更新する。また、伸長部１３２は、今回のビットマップＩＤとスタック１２３に記憶された１つ前および２つ前のビットマップＩＤとによって特定される３グラムのビットマップを更新する。また、伸長部１３２は、今回のビットマップＩＤをバッファ１２２に格納し、スタック１２３に記憶された１つ前および２つ前のビットマップＩＤを書き換える。

ハフマン木生成部１３３は、伸長部１３２から記号０ｘ００〜０ｘＦＦそれぞれを符号化したときの符号長の情報を取得し、符号長に基づいて複数の記号を並べ替え、図７のような構造のハフマン木を生成する。そして、ハフマン木生成部１３３は、生成したハフマン木を表した構造体データを、ハフマン木記憶部１３４に格納する。

ハフマン木記憶部１３４は、ハフマン木生成部１３３が生成したハフマン木の構造体データを記憶する。ハフマン木の構造体データは、６４ｋバイトの記号列が伸長される毎に更新され得る。構造体データは、後述するように、圧縮に用いられる符号と関連付けて、その符号を復号した記号と、その記号に対応するビットマップＩＤを含む。伸長部１３２は、圧縮ファイル１１１の符号語部からビット列を抽出し、抽出したビット列（符号）に関連付けられている記号とビットマップＩＤを構造体データから取得することになる。

表示制御部１３５は、バッファ１２１から伸長済の６４ｋバイトの記号列を取得する。例えば、表示制御部１３５は、バッファ１２１が満杯になる毎に、バッファ１２１に記憶された記号列をＲＡＭ１０２の他の記憶領域に移動する。そして、表示制御部１３５は、圧縮ファイル１１１の伸長が完了すると、伸長データから電子書籍の表示画面を生成し、ディスプレイ１０４に表示させる。例えば、表示制御部１３５は、伸長データに含まれるＸＨＴＭＬファイルやＳＶＧファイルに基づいて、テキストや図形を含むページをレンダリングし、電子書籍の内容をページ単位でディスプレイ１０４に表示する。

検索部１３６は、入力部１０５を用いてユーザが入力したキーワードを取得し、インデックス１２４を参照して、そのキーワードを含む可能性のあるブロックを検索する。そして、検索部１３６は、検索されたブロックを含むページを表示するよう、表示制御部１３５に指示する。ただし、前述のように、検索する単位は項目やファイルであってもよい。

ここで、１グラム・２グラム・３グラムのビットマップを用いてブロックを検索する方法の一例を説明する。検索部１３６は、入力されたキーワードを、種類が同じである連続する文字の列（１文字の場合も含む）毎に分割する。文字の種類としては、例えば、英数字などの１バイトで表される文字、２バイトで表される文字、３バイトで表される文字、４バイトで表される文字などが挙げられる。検索部１３６は、１バイト文字１つから成る文字列からは１グラムを１個生成し、１バイト文字２つから成る文字列からは２グラムを１個生成し、１バイト文字ｓ個（ｓは３以上の整数）から成る文字列からは３グラムをｓ−２個生成する。また、検索部１３６は、２バイト文字から成る文字列からは文字毎に２グラムを生成し、３バイト文字から成る文字列からは文字毎に３グラムを生成し、４バイト文字から成る文字列からは文字毎に２グラムを２個生成する。

そして、検索部１３６は、キーワードから生成した１グラム・２グラム・３グラムそれぞれに対応するビットマップをインデックス１２４から取得し、複数のビットマップの間で、ビット毎の論理積（ＡＮＤ）を計算する。検索部１３６は、論理積の結果においてビット＝１となっているブロックを、キーワードを含む可能性のあるブロックと判定する。ただし、上記の検索方法は一例であり、インデックス１２４に含まれる１グラム・２グラム・３グラムのビットマップの利用方法は、これに限定されない。

なお、伸長部１３２は、圧縮ファイル１１１を初めて伸長するときに、圧縮ファイル１１１に対応するインデックス１２４を生成してインデックスファイル１１２に登録すればよい。伸長部１３２は、例えば、圧縮ファイル１１１を伸長するとき、圧縮ファイル１１１に対応するインデックスがインデックスファイル１１２に登録済であるか確認し、登録済であればインデックス１２４を生成しなくてもよい。なお、圧縮ファイル１１１は、第１の実施の形態の圧縮データ１１の一例である。インデックス１２４は、第１の実施の形態のインデックス１３の一例である。ハフマン木記憶部１３４に記憶された構造体データは、第１の実施の形態の記憶部１４に記憶された辞書データ１４ａの一例である。

図９は、ハフマン木を表した構造体データの第１の例を示す図である。図９に示すような構造体データが、ハフマン木生成部１３３によって生成されてハフマン木記憶部１３４に格納される。図９に記載した１行は、２バイトの記憶領域に相当する。

ハフマン木の構造体データは、ヘッダ領域および枝・葉領域を含む。ヘッダ領域には、構造体データのサイズや枝・葉領域の先頭アドレスなど、管理用の情報が格納される。枝・葉領域には、ハフマン木のルートノードおよび中間ノードそれぞれに対して、４バイト（２行）の記憶領域が割り当てられる。４バイトのうちの前半２バイト（前半１行）は左子ノードを辿る枝に相当し、４バイトのうちの後半２バイト（後半１行）は右子ノードを辿る枝に相当する。枝・葉領域の先頭４バイトは、ルートノードに割り当てられる。

左子ノードを辿る枝および右子ノードを辿る枝に相当する２バイトの記憶領域それぞれには、生成されたハフマン木に応じて、ポインタと葉データの何れか一方が格納される。ポインタは、子ノードが中間ノードであることを示しており、子ノードに割り当てられた記憶領域の先頭アドレスを含む。葉データは、子ノードが葉ノードであることを示しており、元の記号（伸長記号）と伸長記号に対応するビットマップＩＤとを含む。ポインタの先頭ビットは“０”に設定され、葉データの先頭ビットは“１”に設定されている。

ハフマン符号を復号するとき、伸長部１３２は、圧縮データから１ビットを抽出し、抽出したビットを枝・葉領域の先頭位置からのオフセットとして用いて、ルートノードの左子ノードを辿る枝または右子ノードを辿る枝に相当するデータを選択する。すなわち、伸長部１３２は、圧縮データから抽出したビットが“０”のときは左子ノードを辿り、圧縮データから抽出したビットが“１”のときは右子ノードを辿ることになる。伸長部１３２は、選択したデータの先頭ビットを確認し、先頭ビットが“１”のときは、選択したデータ（すなわち、葉データ）から伸長記号とビットマップＩＤを取得する。

一方、伸長部１３２は、先頭ビットが“０”のときは、選択したデータ（すなわち、ポインタ）からアドレスを取得すると共に、圧縮データから次の１ビットを抽出する。伸長部１３２は、抽出したビットを、取得したアドレスが示す位置からのオフセットとして用いて、中間ノードの左子ノードまたは右子ノードを辿る。伸長部１３２は、何れかの葉データに到達するまでポインタを辿ることを繰り返すことで、符号を復号できる。

図１０は、ファイル伸長の第１の手順例を示すフローチャートである。
（ステップＳ１１）ハフマン木生成部１３３は、圧縮ファイル１１１のヘッダ部に記載された記号０ｘ００〜０ｘＦＦそれぞれの符号長に基づいて、ハフマン木の構造体データをハフマン木記憶部１３４上に生成する。構造体データの生成方法の詳細は後述する。

（ステップＳ１２）伸長部１３２は、次に伸長する符号語の先頭ビットを確認し、先頭ビット＝０であるか判断する。符号語の先頭ビット＝０の場合、処理をステップＳ１３に進める。符号語の先頭ビット＝１の場合、処理をステップＳ１５に進める。

（ステップＳ１３）伸長部１３２は、ハフマン木記憶部１３４に記憶された構造体データを参照して、符号語の先頭ビットの後ろに存在するハフマン符号化された１バイト記号を復号する。また、伸長部１３２は、１バイト記号の復号と併せて、構造体データを参照して、復号された１バイト記号に対応するビットマップを識別するためのビットマップＩＤを特定する。構造体データを用いたハフマン復号の詳細は後述する。

（ステップＳ１４）伸長部１３２は、ステップＳ１３で復号した記号をバッファ１２１の末尾に追加する。また、伸長部１３２は、ステップＳ１３で特定したビットマップＩＤをバッファ１２２の末尾に追加する。そして、処理を後述するステップＳ２１に進める。

（ステップＳ１５）伸長部１３２は、ハフマン木記憶部１３４に記憶された構造体データを参照して、符号語の先頭ビットの後ろに存在するハフマン符号化された「バイト数」を復号する。構造体データを用いたハフマン復号の詳細は後述する。

（ステップＳ１６）伸長部１３２は、ハフマン木記憶部１３４に記憶された構造体データを参照して、ステップＳ１５で復号された符号の後ろに存在するハフマン符号化された「桁数」を復号する。構造体データを用いたハフマン復号の詳細は後述する。

（ステップＳ１７）伸長部１３２は、ステップＳ１６で復号した「桁数」がＭＳＢから数えて最初にビット＝１が現れる桁を意味するように、「先頭アドレス」の上位のビット列を算出する。また、伸長部１３２は、「先頭アドレス」の残りのビット数を算出し、残りのビット数分のビット列を、ステップＳ１６で復号された符号の後ろから抽出する。そして、伸長部１３２は、上位と下位のビット列を結合して「先頭アドレス」を復元する。

（ステップＳ１８）伸長部１３２は、スライド窓に含まれる伸長済の記号列の中から、ステップＳ１５で復号した「バイト数」とステップＳ１７で復元した「先頭アドレス」とによって特定される３バイト以上の記号列を取得する。そして、伸長部１３２は、取得した記号列をバッファ１２１の末尾に複製する。また、伸長部１３２は、記号列に対応するビットマップＩＤの列をバッファ１２２から取得し、バッファ１２２の末尾に複製する。

図１１は、ファイル伸長の第１の手順例を示すフローチャート（続き）である。
（ステップＳ２１）伸長部１３２は、ステップＳ１３またはステップＳ１８で取得した１またはそれ以上のビットマップＩＤから、先頭に近い順に１つビットマップＩＤを選択する。伸長部１３２は、選択したビットマップＩＤを、１グラムの領域の先頭からのオフセットとして用いて、インデックス１２４から１グラムのビットマップを１つ選択する。

また、伸長部１３２は、今回のビットマップＩＤとスタック１２３に記憶された１つ前のビットマップＩＤとを結合したビット列を、２グラムの領域の先頭からのオフセットとして用いて、インデックス１２４から２グラムのビットマップを１つ選択する。また、伸長部１３２は、今回のビットマップＩＤとスタック１２３に記憶された１つ前のビットマップＩＤと２つ前のビットマップＩＤとを結合したビット列を、３グラムの領域の先頭からのオフセットとして用いて、インデックス１２４から３グラムのビットマップを１つ選択する。伸長部１３２は、選択した１グラム・２グラム・３グラムのビットマップに含まれる、現在伸長中のブロックに対応するビットを“１”に設定する。

（ステップＳ２２）伸長部１３２は、スタック１２３に記憶された１つ前のビットマップＩＤと２つ前のビットマップＩＤを更新する。すなわち、伸長部１３２は、１つ前のビットマップＩＤを２つ前のビットマップＩＤに変更し、ステップＳ２１で選択した今回のビットマップＩＤを１つ前のビットマップＩＤとしてスタック１２３に格納する。

（ステップＳ２３）伸長部１３２は、ステップＳ２１で選択したビットマップＩＤに対応する記号が、ブロックの末尾に相当するか（例えば、バッファ１２１における当該記号のアドレスが８ｋバイトの境界を示すか）判断する。記号がブロックの末尾である場合は処理をステップＳ２４に進め、それ以外の場合は処理をステップＳ２５に進める。

（ステップＳ２４）伸長部１３２は、インデックス１２４に含まれる各ビットマップ内の更新対象となるビットの位置を示すブロック番号をインクリメントする。現在のブロック番号は、例えば、伸長部１３２がＲＡＭ１０２上に確保した記憶領域に記憶しておく。

（ステップＳ２５）伸長部１３２は、ステップＳ２１において、ステップＳ１３またはステップＳ１８で取得した１またはそれ以上のビットマップＩＤの全てを選択したか（末尾の記号に対応するビットマップＩＤまで選択したか）判断する。全て選択した場合は処理をステップＳ２６に進め、未選択のものがある場合は処理をステップＳ２１に進める。

（ステップＳ２６）伸長部１３２は、ステップＳ１４またはステップＳ１８でバッファ１２１に追加した記号の数だけ、スライド窓の位置を後方にシフトさせる。
（ステップＳ２７）伸長部１３２は、符号語部に続きの符号語があるか判断する。続きの符号語がある場合は処理をステップＳ１２に進め、無い場合は処理を終了する。

図１２は、構造体生成の第１の手順例を示すフローチャートである。図１２に示す構造体生成処理は、前述のステップＳ１１の中で実行される。
（ステップＳ３１）ハフマン木生成部１３３は、記号０ｘ００〜０ｘＦＦそれぞれの符号長から、前述のように二分ハフマン木を生成する。すなわち、ハフマン木生成部１３３は、符号化したときの符号長の小さい順に２５６通りの記号を並び替え、符号長が同じになる記号間では数値が小さい順に並び替える。また、ハフマン木生成部１３３は、符号長から各記号の出現頻度を推定する。そして、ハフマン木生成部１３３は、記号に対応する葉ノードを生成し、出現頻度に基づいて、葉ノードからルートノードに向かって枝を形成していく。ハフマン木生成部１３３は、生成した二分ハフマン木の枝を、ルートノードから葉ノードに向かって辿ることで、各記号に対応するハフマン符号を判定する。

（ステップＳ３２）ハフマン木生成部１３３は、ステップＳ３１で生成した二分ハフマン木に現れるルートノードおよび中間ノードの数をカウントする。そして、ハフマン木生成部１３３は、ハフマン木記憶部１３４に、カウントしたノード数に比例する大きさ（例えば、ノード数×２行×２バイト）の枝・葉領域を確保し、各ノードに記憶領域を割り当てる。なお、ルートノードには、枝・葉領域の先頭部分を割り当てるようにする。

（ステップＳ３３）ハフマン木生成部１３３は、ステップＳ３１で生成した二分ハフマン木に現れるルートノードおよび中間ノードの中から、１つノードを選択する。そして、ハフマン木生成部１３３は、選択したノードの左子ノードが葉ノードであるか判断する。左子ノードが葉ノードの場合は、処理をステップＳ３４に進める。左子ノードが葉ノードでない（中間ノードである）場合は、処理をステップＳ３５に進める。

（ステップＳ３４）ハフマン木生成部１３３は、葉ノードに対応する伸長記号と、当該伸長記号に対応する１グラムのビットマップのビットマップＩＤとを含む葉データを生成する。ハフマン木生成部１３３は、生成した葉データを、ステップＳ３３で選択したノードに割り当てられている記憶領域の前半（左子ノードに対応する行）に格納する。

（ステップＳ３５）ハフマン木生成部１３３は、左子ノードとしての中間ノードに割り当てられている記憶領域の先頭を示すアドレスを含むポインタを生成する。ハフマン木生成部１３３は、生成したポインタを、ステップＳ３３で選択したノードに割り当てられている記憶領域の前半（左子ノードに対応する行）に格納する。

（ステップＳ３６）ハフマン木生成部１３３は、ステップＳ３３で選択したノードの右子ノードが葉ノードであるか判断する。右子ノードが葉ノードの場合は、処理をステップＳ３７に進める。右子ノードが葉ノードでない場合は、処理をステップＳ３８に進める。

（ステップＳ３７）ハフマン木生成部１３３は、葉ノードに対応する伸長記号と、当該伸長記号に対応する１グラムのビットマップのビットマップＩＤとを含む葉データを生成する。ハフマン木生成部１３３は、生成した葉データを、ステップＳ３３で選択したノードに割り当てられている記憶領域の後半（右子ノードに対応する行）に格納する。

（ステップＳ３８）ハフマン木生成部１３３は、右子ノードとしての中間ノードに割り当てられている記憶領域の先頭を示すアドレスを含むポインタを生成する。ハフマン木生成部１３３は、生成したポインタを、ステップＳ３３で選択したノードに割り当てられている記憶領域の後半（右子ノードに対応する行）に格納する。

（ステップＳ３９）ハフマン木生成部１３３は、ステップＳ３３において、二分ハフマン木に現れるルートノードおよび中間ノードの全てを選択したか判断する。全て選択した場合は処理を終了し、未選択のノードがある場合は処理をステップＳ３３に進める。

図１３は、ハフマン復号の第１の手順例を示すフローチャートである。図１３に示すハフマン復号処理は、前述のステップＳ１３，Ｓ１５，Ｓ１６の中で実行される。
（ステップＳ４１）伸長部１３２は、ハフマン木記憶部１３４に記憶された構造体データのヘッダ領域を参照して、枝・葉領域の先頭アドレスを確認する。そして、伸長部１３２は、構造体データ内の現在参照している位置を、枝・葉領域の先頭に設定する。

（ステップＳ４２）伸長部１３２は、圧縮ファイル１１１に含まれる符号語部のビット列から、伸長が完了していない部分（未抽出の部分）の先頭１ビットを抽出する。
（ステップＳ４３）伸長部１３２は、ステップＳ４２で抽出した１ビットの値を、構造体データ内の現在参照している位置からの相対アドレス（オフセット）として用いて、１行分のデータ（葉データまたはポインタ）を選択する。すなわち、伸長部１３２は、抽出したビットが“０”のときは左子ノードに対応するデータを選択して、抽出したビットが“１”のときは右子ノードに対応するデータを選択する。

（ステップＳ４４）伸長部１３２は、ステップＳ４３で選択したデータの先頭ビットを確認する。先頭ビット＝０である場合、選択したデータはポインタであると判断し、処理をステップＳ４５に進める。先頭ビット＝１である場合、選択したデータは葉データであると判断し、処理をステップＳ４６に進める。

（ステップＳ４５）伸長部１３２は、ステップＳ４３で選択したデータであるポインタからアドレスを抽出し、構造体データ内のアドレスが差し示す位置にジャンプする（現在参照している位置を更新する）。そして、処理をステップＳ４２に進める。

（ステップＳ４６）伸長部１３２は、ステップＳ４３で選択したデータである葉データから、伸長記号とビットマップＩＤを抽出する。ただし、前述のステップＳ１５，Ｓ１６では、葉データに含まれるビットマップＩＤは使用されない。伸長部１３２は、ステップＳ１５，Ｓ１６では、葉データからビットマップＩＤを抽出しなくてもよい。

図１４は、第１のインデックス生成例を示す図である。図１４は、先頭ビット＝０である符号語を伸長したときの動作を示している。伸長部１３２は、符号語の先頭ビットに続くビット列を用いて、ハフマン木の構造体データから葉データを検索し、葉データから伸長記号とビットマップＩＤを抽出する。伸長部１３２は、抽出した伸長記号をバッファ１２１に格納し、抽出したビットマップＩＤをバッファ１２２に格納する。

また、伸長部１３２は、葉データから抽出したビットマップＩＤを識別子として、インデックス１２４の中から１グラムのビットマップを選択し、選択したビットマップ内の１つのビットを“１”に設定する。また、伸長部１３２は、葉データから抽出したビットマップＩＤとスタック１２３に記憶された１つ前のビットマップＩＤを結合した値を識別子として、インデックス１２４の中から２グラムのビットマップを選択し、選択したビットマップ内の１つのビットを“１”に設定する。また、伸長部１３２は、葉データから抽出したビットマップＩＤとスタック１２３に記憶された１つ前および２つ前のビットマップＩＤを結合した値を識別子として、インデックス１２４の中から３グラムのビットマップを選択し、選択したビットマップ内の１つのビットを“１”に設定する。

また、伸長部１３２は、スタック１２３に記憶されていた１つ前のビットマップＩＤを、２つ前のビットマップＩＤに変更する（例えば、２つ前のビットマップＩＤとしてスタック１２３に格納し直す）。また、伸長部１３２は、葉データから抽出したビットマップＩＤを、１つ前のビットマップＩＤとしてスタック１２３に格納する。

図１５は、第２のインデックス生成例を示す図である。図１５は、先頭ビット＝１である符号語を伸長したときの動作を示している。伸長部１３２は、符号語の先頭ビットに続くビット列から、ハフマン木の構造体データを参照して「先頭アドレス」と「バイト数」を復元する。そして、伸長部１３２は、スライド窓内の「先頭アドレス」と「バイト数」によって特定される範囲にある記号列を、バッファ１２１の末尾に複製し、複製した記号列に対応するビットマップＩＤの列をバッファ１２２の末尾に複製する。

また、伸長部１３２は、複製した１番目のビットマップＩＤを識別子として、インデックス１２４の中から１グラムのビットマップを選択し、選択したビットマップ内の１つのビットを“１”に設定する。また、伸長部１３２は、複製した１番目のビットマップＩＤとスタック１２３に記憶された１つ前のビットマップＩＤを結合した値を識別子として、インデックス１２４の中から２グラムのビットマップを選択し、選択したビットマップ内の１つのビットを“１”に設定する。また、伸長部１３２は、複製した１番目のビットマップＩＤとスタック１２３に記憶された１つ前および２つ前のビットマップＩＤを結合した値を識別子として、インデックス１２４の中から３グラムのビットマップを選択し、選択したビットマップ内の１つのビットを“１”に設定する。

また、伸長部１３２は、スタック１２３に記憶されていた１つ前のビットマップＩＤを、２つ前のビットマップＩＤに変更する。また、伸長部１３２は、複製した１番目のビットマップＩＤを、１つ前のビットマップＩＤとしてスタック１２３に格納する。伸長部１３２は、以上に説明したスタック１２３およびインデックス１２４の更新を、複製した２番目以降のビットマップＩＤそれぞれについても実行する。

以上の第２の実施の形態の説明では、ハフマン木の構造体データに、伸長記号とは別にビットマップＩＤを格納しておき、このビットマップＩＤを用いてインデックス１２４の中から伸長記号に対応するビットマップを選択することとした。ただし、伸長記号としての数値がビットマップＩＤを兼ねる場合もある。例えば、インデックス１２４が、２５６個の１グラムのビットマップを含み、これら２５６個のビットマップが、伸長記号としての数値０ｘ００〜０ｘＦＦの順に並んでいる場合が考えられる。その場合、ハフマン木の構造体データに、伸長記号と別にビットマップＩＤを格納しなくてもよい。また、その場合、バッファ部１２０にバッファ１２２を設けなくてもよい。

図１６は、第３のインデックス生成例を示す図である。図１６は、先頭ビット＝０である符号語を伸長したときの動作を示している。伸長部１３２は、符号語の先頭ビットに続くビット列を用いて、ハフマン木の構造体データから葉データを検索し、葉データから伸長記号を抽出する。伸長部１３２は、抽出した伸長記号をバッファ１２１に格納する。

伸長部１３２は、ビットマップＩＤを兼ねる伸長記号を識別子として、インデックス１２４の中から１グラムのビットマップを選択し、選択したビットマップ内の１つのビットを“１”に設定する。また、伸長部１３２は、伸長記号とスタック１２３に記憶された１つ前のビットマップＩＤを結合した値を識別子として、インデックス１２４の中から２グラムのビットマップを選択し、選択したビットマップ内の１つのビットを“１”に設定する。また、伸長部１３２は、伸長記号とスタック１２３に記憶された１つ前および２つ前のビットマップＩＤを結合した値を識別子として、インデックス１２４の中から３グラムのビットマップを選択し、選択したビットマップ内の１つのビットを“１”に設定する。

また、伸長部１３２は、スタック１２３に記憶されていた１つ前のビットマップＩＤを、２つ前のビットマップＩＤに変更する。また、伸長部１３２は、ビットマップＩＤを兼ねる伸長記号を、１つ前のビットマップＩＤとしてスタック１２３に格納する。

図１７は、第４のインデックス生成例を示す図である。図１７は、先頭ビット＝１である符号語を伸長したときの動作を示している。伸長部１３２は、符号語の先頭ビットに続くビット列から、ハフマン木の構造体データを参照して「先頭アドレス」と「バイト数」を復元する。そして、伸長部１３２は、スライド窓内の「先頭アドレス」と「バイト数」によって特定される範囲にある記号列を、バッファ１２１の末尾に複製する。

また、伸長部１３２は、ビットマップＩＤを兼ねる複製した記号の列のうち１番目の記号を識別子として、インデックス１２４の中から１グラムのビットマップを選択し、選択したビットマップ内の１つのビットを“１”に設定する。また、伸長部１３２は、１番目の記号とスタック１２３に記憶された１つ前のビットマップＩＤを結合した値を識別子として、インデックス１２４の中から２グラムのビットマップを選択し、選択したビットマップ内の１つのビットを“１”に設定する。また、伸長部１３２は、１番目の記号とスタック１２３に記憶された１つ前および２つ前のビットマップＩＤを結合した値を識別子として、インデックス１２４の中から３グラムのビットマップを選択し、選択したビットマップ内の１つのビットを“１”に設定する。

また、伸長部１３２は、スタック１２３に記憶されていた１つ前のビットマップＩＤを、２つ前のビットマップＩＤに変更する。また、伸長部１３２は、ビットマップＩＤを兼ねる１番目の記号を、１つ前のビットマップＩＤとしてスタック１２３に格納する。伸長部１３２は、以上に説明したスタック１２３およびインデックス１２４の更新を、ビットマップＩＤを兼ねる複製した２番目以降の記号それぞれについても実行する。

なお、以上の第２の実施の形態の説明では、インデックス１２４における「１グラム」を、文字コード非依存の１バイト記号（０ｘ００〜０ｘＦＦ）とした。ただし、「１グラム」を、文字コード依存の１文字としてもよい。例えば、１文字が２バイトで表される文字コード体系の場合、「１グラム」は２バイトの文字に相当し、「２グラム」は４バイトで表される文字列に相当し、「３グラム」は６バイトで表される文字列に相当する。インデックス１２４では、１文字当たりのバイト数が異なる複数の文字（例えば、１バイト文字と２バイト文字）が「１グラム」として混在していてもよい。

第２の実施の形態の情報端末装置１００によれば、伸長記号に対応するビットマップＩＤがハフマン木の構造体データに登録されているため、圧縮ファイル１１１の伸長と並行して、伸長データに対応するインデックス１２４を効率的に生成できる。すなわち、構造体データに登録されたビットマップＩＤを用いて、インデックス１２４内の所望のビットマップが記憶されている領域に直接アクセスすることで、ＲＡＭ１０２へのアクセスを減らすことができる。また、１つ前および２つ前のビットマップＩＤを記憶するスタック１２３を設けることで、バッファ１２２から１つ前および２つ前のビットマップＩＤを検索するよりも、効率的に２グラム・３グラムのビットマップにアクセスできる。また、圧縮ファイル１１１の伸長が完了した時点で、伸長データに対応するインデックス１２４が生成されているため、伸長データに対する検索をすぐに開始することが可能となる。

［第３の実施の形態］
第３の実施の形態を説明する。前述の第２の実施の形態との差異を中心に説明し、第２の実施の形態と同様の事項は説明を省略する。第３の実施の形態は、ハフマン木の構造体データの構造と構造体データを用いてハフマン符号を復号する方法が、第２の実施の形態と異なる。第３の実施の形態の情報端末装置は、第２の実施の形態の情報端末装置１００と同様に、図２に示したようなハードウェア構成によって実現でき、また、図８に示したようなソフトウェア構成によって実現できる。以下では、第２の実施の形態で用いた図２，８の中の符号を用いて、第３の実施の形態を説明することとする。

図１８は、変形したハフマン木の例を示す図である。第３の実施の形態の情報端末装置は、ハフマン木を表した構造体データを参照して圧縮ファイル１１１を伸長するにあたり、伸長処理の効率を向上させるためにハフマン木を変形しておく。

情報端末装置は、ハフマン木によって決定される２５６個の符号の最大符号長を特定し、最大符号長を上位ｎビットと下位ｍビット（ｎ，ｍは１以上の整数）に分ける。閾値である“ｎ”は、固定の所定値であってもよいし、符号長がｎビット未満である記号の出現頻度の合計が所望の頻度になるように符号長の情報から決定してもよい。そして、情報端末装置は、１つの枝に１ビットを対応付けた二分ハフマン木を、１つの枝に複数ビットを対応付けることができ葉ノードの深さが１または２であるハフマン木に変形する。変形されたハフマン木では、１つの記号が複数の葉ノードに対応付けられ得る。

すなわち、情報端末装置は、ｎビット未満の符号の末尾に冗長なビットを付加することで、ｎビット以下の符号の長さをｎビットに揃える。例えば、ｎ＝４の場合、符号０が８個のビット列００００〜０１１１に変換され、符号１０が４個のビット列１０００〜１０１１に変換される。また、情報端末装置は、ｎビットを超える符号から上位ｎビットのビット列を分離し、残りのビット列の長さをｍビットに揃える。例えば、ｎ＝４，ｍ＝２の場合、符号１１１１０がビット列１１１１と下位のビット列００，０１に変換され、符号１１１１１０がビット列１１１１と下位のビット列１０に変換される。

変形されたハフマン木では、上位ｎビットのビット列を用いて、ルートノードから符号長がｎビット以下の記号に対応する葉ノードを辿ることができる。また、上位ｎビットのビット列を用いて中間ノードを辿り、下位ｍビットのビット列を用いて、中間ノードから符号長がｎビットを超える記号に対応する葉ノードを辿ることができる。すなわち、変形されたハフマン木では、出現頻度が高い記号は枝を１回辿ることで符号から検索でき、出現頻度が低い記号は枝を２回辿ることで符号から検索することができる。

変形されたハフマン木を用いて圧縮ファイル１１１を伸長する場合、情報端末装置は、圧縮ファイル１１１からｎ＋ｍビットのビット列を１回に抽出し、上位ｎビット、または、上位ｎビットと下位ｍビットの組み合わせから、伸長記号を取得する。このとき、抽出したｎ＋ｍビットの全体が、伸長記号に対応する符号を構成するわけではない。図１８のハフマン木において、例えば、圧縮ファイル１１１からビット列０００１１０が抽出されたときは、記号０ｘ００が伸長記号として取得される。ただし、記号０ｘ００は１ビットの符号０に符号化されていることから、抽出した残りの５ビットのビット列００１１０は次の符号や符号語を構成する可能性があり、復号済とは扱わないことになる。

図１９は、ハフマン木を表した構造体データの第２の例を示す図である。図１９に示すような構造体データが、ハフマン木生成部１３３によって生成されてハフマン木記憶部１３４に格納される。図１９に記載した「１行」は、２バイトの記憶領域に相当する。ハフマン木の構造体は、ヘッダ領域、上位枝領域、下位枝領域および葉領域を含む。

ヘッダ領域には、構造体データのサイズや領域間の境界を示すアドレスなど、管理用の情報が格納される。上位枝領域には、それぞれが２バイトで表された２のｎ乗個のポインタが格納される。上位枝領域の各ポインタは、下位枝領域にある何れかのポインタ集合の先頭アドレスまたは葉領域にある何れかの葉データの先頭アドレスを含む。上位枝領域のポインタの先頭ビットは、ポインタであることを表すため“０”に設定される。上位枝領域から葉領域へのポインタは、図１８のルートノードから葉ノードへの枝に相当し、複数の上位枝領域のポインタが同一の葉データを指し示すことがある。上位枝領域から下位枝領域へのポインタは、図１８のルートノードから中間ノードへの枝に相当する。

下位枝領域には、それぞれが２バイトで表された２のｍ乗個のポインタがａセット（ａは１以上の整数）格納される。下位枝領域の各ポインタは、葉領域にある何れかの葉データの先頭アドレスを含む。下位枝領域のポインタの先頭ビットは、ポインタであることを表すため“０”に設定される。下位枝領域から葉領域へのポインタは、図１８の中間ノードから葉ノードへの枝に相当し、複数の下位枝領域のポインタが同一の葉データを指し示すことがある。集合数ａは、変形したハフマン木における中間ノードの数に相当する。

葉領域には、２５６個の記号０ｘ００〜０ｘＦＦに対応する葉データが格納される。葉領域では、図７，１８の葉ノードと同様の順序に葉データが整列されている。すなわち、符号長の小さい記号に対応する葉データほどアドレスの小さい位置に格納され、また、符号長の同じ記号の中では数値の小さい記号に対応する葉データほどアドレスの小さい位置に格納される。各記号の葉データは、伸長記号、その記号を符号化したときのハフマン符号、符号長の情報およびビットマップＩＤを含む。葉データの先頭ビットは、葉データであることを表すため“１”に設定される。葉データは、例えば、６バイトで表される。ただし、葉データのサイズは、構造体データを生成する時点で所定値に決めておけばよく、葉データにどの様な情報を含めるかに応じて調整できる。例えば、葉データにハフマン符号を含めなくてもよく、その場合は４バイトで表現できる。

前述のようにｎ＋ｍビットのビット列が抽出されると、上位ｎビットのビット列が、上位枝領域の先頭を基準とした相対アドレス（オフセット）として用いられて、オフセットに応じた位置に格納されている上位枝領域のポインタが選択される。選択したポインタが葉データを指し示していないとき、下位ｍビットのビット列が、上位枝領域のポインタが指し示す位置からのオフセットとして用いられて、オフセットに応じた位置に格納されている下位枝領域のポインタが選択される。このように、上位枝領域からポインタを１回または２回辿ることで、葉領域にある葉データを参照することができる。

図２０は、構造体生成の第２の手順例を示すフローチャートである。図２０に示す構造体生成処理は、第２の実施の形態で述べたステップＳ１１の中で実行される。
（ステップＳ５１）ハフマン木生成部１３３は、記号０ｘ００〜０ｘＦＦそれぞれの符号長から、前述のように二分ハフマン木を生成する。ハフマン木生成部１３３は、生成した二分ハフマン木の枝を辿ることで、各記号に対応するハフマン符号を判定する。

（ステップＳ５２）ハフマン木生成部１３３は、ハフマン木記憶部１３４に、６バイト（または、所定バイト）×２５６の大きさの葉領域を確保する。
（ステップＳ５３）ハフマン木生成部１３３は、ステップＳ５２で確保した葉領域に、ステップＳ５１で並べた記号順に各記号に対応する葉データを書き込む。各記号の葉データは、伸長記号とハフマン符号と符号長を示す情報とビットマップＩＤを含む。

（ステップＳ５４）ハフマン木生成部１３３は、記号０ｘ００〜０ｘＦＦに対応する符号の最長符号長を、前述のように上位ｎビットと下位ｍビットに分割する。
（ステップＳ５５）ハフマン木生成部１３３は、ハフマン木記憶部１３４に、２バイト×２ⁿの上位枝領域を確保する。また、ハフマン木生成部１３３は、２ⁿ通りのｎビットのビット列のうち、ビット数がｎを超える符号のプレフィックスになっているものの数ａ（変形したハフマン木の中間ノードの数）を算出する。そして、ハフマン木生成部１３３は、ハフマン木記憶部１３４に、２バイト×ａ×２^mの下位枝領域を確保する。

（ステップＳ５６）ハフマン木生成部１３３は、葉領域にある１つの記号分の葉データを、アドレスの小さい方から選択する。そして、ハフマン木生成部１３３は、選択した葉データの示す符号長が閾値ｎより大きいか判断する。符号長がｎより大きい場合は処理をステップＳ５８に進め、符号長がｎ以下の場合は処理をステップＳ５７に進める。

（ステップＳ５７）ハフマン木生成部１３３は、符号長をＬとして、上位枝領域のポインタ数＝２のｎ−Ｌ乗を算出する。そして、ハフマン木生成部１３３は、上位枝領域の中でポインタをまだ書き込んでいない領域のうちアドレスの小さい方から順に、算出したポインタ数だけ、ステップＳ５６で選択した葉データの先頭アドレスを含むポインタを書き込む。例えば、ｎ＝１１の場合、上位枝領域には、１ビットの符号に対応する葉データを指すポインタは１０２４個書き込まれ、２ビットの符号に対応する葉データを指すポインタは５１２個書き込まれ、１０ビットの符号に対応する葉データを指すポインタは２個書き込まれ、１１ビットの符号に対応する葉データを指すポインタは１個書き込まれる。

（ステップＳ５８）ハフマン木生成部１３３は、下位枝領域の中でポインタをまだ書き込んでいない領域の先頭アドレスを確認する。そして、ハフマン木生成部１３３は、上位枝領域の中の、選択した葉データが示すハフマン符号の上位ｎビットによって特定される位置に、確認した下位枝領域のアドレスを含むポインタを書き込む。ただし、上位ｎビットによって特定される位置にポインタを書き込み済のときは、書き込まなくてよい。

（ステップＳ５９）ハフマン木生成部１３３は、下位枝領域のポインタ数＝２のｎ＋ｍ−Ｌ乗を算出する。そして、ハフマン木生成部１３３は、下位枝領域の中でポインタをまだ書き込んでいない領域のうちアドレスの小さい方から順に、算出したポインタ数だけ、選択した葉データの先頭アドレスを含むポインタを書き込む。例えば、ｎ＝１１，ｍ＝３の場合、下位枝領域には、１２ビットの符号に対応する葉データを指すポインタは４個書き込まれ、１４ビットの符号に対応する葉データを指すポインタは１個書き込まれる。

（ステップＳ６０）ハフマン木生成部１３３は、ステップＳ５６で全ての記号に対応する葉データを選択したか判断する。全ての葉データを選択した場合は処理を終了し、未選択の葉データがある場合は処理をステップＳ５６に進める。

図２１は、ハフマン復号の第２の手順例を示すフローチャートである。図２１に示すハフマン復号処理は、前述のステップＳ１３，Ｓ１５，Ｓ１６の中で実行される。
（ステップＳ６１）伸長部１３２は、圧縮ファイル１１１に含まれる符号語部の符号語列から、伸長が完了していないｎ＋ｍビットのビット列を抽出する。

（ステップＳ６２）伸長部１３２は、ハフマン木記憶部１３４に記憶された構造体データのヘッダ領域を参照して、上位枝領域の先頭アドレスを確認する。そして、伸長部１３２は、ステップＳ６１で抽出したビット列の上位ｎビットを、上位枝領域の先頭からの相対アドレス（オフセット）として用いて、上位枝領域にあるポインタを１つ選択する。伸長部１３２は、選択したポインタが指し示す位置（ポインタに含まれるアドレスによって特定される位置）に記憶されているデータを取得する。

（ステップＳ６３）伸長部１３２は、ステップＳ６２で取得したデータの先頭ビットを確認する。先頭ビット＝１の場合、取得したデータは葉データであると判断し、処理をステップＳ６５に進める。先頭ビット＝０の場合、取得したデータは下位枝領域のポインタであると判断し、処理をステップＳ６４に進める。

（ステップＳ６４）伸長部１３２は、ステップＳ６１で抽出したビット列の下位ｍビットを、上位枝領域のポインタが指し示す位置からのオフセットとして用いて、下位枝領域にあるポインタを１つ選択する。そして、伸長部１３２は、選択したポインタが指し示す位置（ポインタに含まれるアドレスによって特定される位置）の葉データを取得する。

（ステップＳ６５）伸長部１３２は、ステップＳ６２またはステップＳ６４で取得した葉データから、伸長記号とビットマップＩＤを抽出する。伸長部１３２は、葉データからビットマップＩＤを抽出する。ただし、前述のステップＳ１５，Ｓ１６では、葉データに含まれるビットマップＩＤは使用されない。伸長部１３２は、ステップＳ１５，Ｓ１６では、葉データからビットマップＩＤを抽出しなくてもよい。

（ステップＳ６６）伸長部１３２は、ステップＳ６２またはステップＳ６４で取得した葉データから符号長の情報を抽出し、符号語列のどの位置まで伸長が完了したかを示すカウンタを符号長だけ進める。カウンタはＲＡＭ１０２に記憶されている。

図２２は、ハフマン復号におけるビット演算の例を示す図である。ここでは、圧縮ファイル１１１に用いられている符号の最長符号長が１４であり、ｎ＝１１であるとする。
情報端末装置は、バッファに格納した符号語列のうち伸長が完了していない部分の先頭位置を管理するため、ＲＡＭ１０２上にバイトカウンタとビットカウンタを保持する。バイトカウンタは、伸長が完了していない部分の先頭が、バッファの先頭から何バイト目に属するかを示している。ビットカウンタは、伸長が完了していない部分の先頭が、バイトの切れ目（８ビット毎の切れ目）から何ビット目にあるかを示している。ビットカウンタは０〜７の範囲の値を取り、一巡するとバイトカウンタがインクリメントされる。

伸長部１３２は、バッファに格納された符号語列から、まず４バイト（３２ビット）単位でビット列を切り出す。すなわち、伸長部１３２は、バイトカウンタが示す位置を先頭とする３２ビットのビット列を、ｌｏｎｇ型変数に代入する。このとき、ｌｏｎｇ型変数の先頭ビットはバイトの切れ目であり、伸長が完了していない部分の先頭とは限らない。

次に、伸長部１３２は、ｌｏｎｇ型変数のビット列に８通りのマスクパターンの何れかを適用することで、伸長が完了していない１４ビットのビット列を抽出する。マスクパターンは、３２ビットのうち連続する１４ビットが“１”で他のビットが“０”に設定されたビット列であり、ＲＡＭ１０２上に記憶されている。マスクパターンには、ＭＳＢから数えて１〜１４ビット目が“１”であるもの、２〜１５ビット目が“１”であるもの、３〜１６ビット目が“１”であるもの、４〜１７ビット目が“１”であるもの、５〜１８ビット目が“１”であるもの、６〜１９ビット目が“１”であるもの、７〜２０ビット目が“１”であるもの、８〜２１ビット目が“１”であるものが存在する。伸長部１３２は、ビットカウンタに応じて何れか１つのマスクパターンを選択し、ｌｏｎｇ型変数のビット列と選択したマスクパターンの間でビット毎の論理積を行う。そして、伸長部１３２は、論理積の結果をシフトして１４ビットのビット列を取得する。

次に、伸長部１３２は、１４ビットのビット列のうち上位１１ビットを、構造体データの上位枝領域からポインタを１つ選択するためのオフセットとして使用する。また、伸長部１３２は、１４ビットのビット列のうち下位３ビットを、構造体データの下位枝領域からポインタを１つ選択するためのオフセットとして使用する。これにより、伸長部１３２は、葉領域から伸長記号とビットマップＩＤと符号長を示す情報とを取得する。ビットマップＩＤは、インデックス１２４の更新のために用いられる。そして、伸長部１３２は、符号長だけビットカウンタの値を増加させる。ビットカウンタが一巡した（ビットカウンタが７から０に戻った）ときは、一巡する毎にバイトカウンタをインクリメントする。

第３の実施の形態の情報端末装置によれば、第２の実施の形態と同様の効果が得られる。また、第３の実施の形態では、ビット数がｎ以下の符号については構造体データのポインタを１回辿れば伸長記号とビットマップＩＤを検索でき、ビット数がｎを超える符号についてはポインタを２回辿れば伸長記号とビットマップＩＤを検索できる。よって、符号語の１ビット毎に、二分ハフマン木の通りにポインタを辿る方法と比べて、ＲＡＭ１０２へのアクセス回数を削減でき、圧縮ファイル１１１の伸長を効率化できる。

また、ビット数がｎを超える符号に対応する記号を２段階のポインタで辿るようにすることで、全ての記号を１段階のポインタで辿る方法と比べて、同じ伸長記号を指し示す冗長なポインタの数を削減でき、構造体データのデータ量を抑制できる。例えば、最大符号長が１４である場合、全ての記号を１段階のポインタで辿れるようにすると、２¹⁴＝１６ｋ（６５５３６）個のポインタが生成される。これに対し、第３の実施の形態の方法では、ｎ＝１１とすると、上位枝領域に２¹¹＝２ｋ（２０４８）個のポインタが生成され、下位枝領域に８個のポインタが複数セット生成される。

なお、第３の実施の形態においても、第２の実施の形態で述べたように、伸長記号としての数値がビットマップＩＤを兼ねる場合がある。その場合、ハフマン木の構造体データに、伸長記号と別にビットマップＩＤを格納しなくてもよい。また、その場合、バッファ部１２０にバッファ１２２を設けなくてもよい。

［第４の実施の形態］
第４の実施の形態を説明する。前述の第２の実施の形態との差異を中心に説明し、第２の実施の形態と同様の事項は説明を省略する。第４の実施の形態は、２つのブロックに跨がる単語を両方のブロックに属しているものとして扱って、インデックスを生成する。これにより、ユーザから指定されたキーワードが２つのブロックに跨がるときに、２つのブロックの何れも検索結果に含まれないことを避けることができる。第４の実施の形態の情報端末装置は、第２の実施の形態の情報端末装置１００と同様に、図２に示したようなハードウェア構成によって実現でき、また、図８に示したようなソフトウェア構成によって実現できる。以下では、図２，８の中の符号を用いて、第４の実施の形態を説明する。

図２３は、ファイル伸長の第２の手順例を示すフローチャートである。図２３のフローチャートの処理は、図１１のフローチャートが示す第２の実施の形態の処理に代えて、図１０のフローチャートの処理に続けて実行される。

（ステップＳ７１）伸長部１３２は、ステップＳ１３またはステップＳ１８で取得した１またはそれ以上のビットマップＩＤから、先頭に近い順に１つビットマップＩＤを選択する。伸長部１３２は、選択したビットマップＩＤと、スタック１２３に記憶された１つ前のビットマップＩＤと、スタック１２３に記憶された２つ前のビットマップＩＤとに基づいて、インデックス１２４から１グラム・２グラム・３グラムのビットマップを選択する。伸長部１３２は、選択した１グラム・２グラム・３グラムのビットマップに含まれる現在伸長中のブロックに対応するビットを“１”に設定する。

（ステップＳ７２）伸長部１３２は、スタック１２３に記憶されていた１つ前のビットマップＩＤを２つ前のビットマップＩＤに変更し、ステップＳ７１で選択した今回のビットマップＩＤを、１つ前のビットマップＩＤとしてスタック１２３に格納する。

（ステップＳ７３）伸長部１３２は、ステップＳ７１で選択したビットマップＩＤに対応する記号が、単語などの所定単位の先頭であるか判断する。例えば、伸長した記号列が英文である場合は、直前のスペース（空白）を検出することで、その記号が単語の先頭であると判断する。また、伸長した記号列が日本語文である場合は、直前の句読点を検出することで、その記号が文や句の先頭であると判断する。記号が所定単位の先頭である場合は処理をステップＳ７４に進め、それ以外の場合は処理をステップＳ７５に進める。

（ステップＳ７４）伸長部１３２は、バッファ１２１における、ステップＳ７１で選択したビットマップＩＤに対応する記号の位置を示すアドレスを保存しておく。
（ステップＳ７５）伸長部１３２は、ステップＳ７１で選択したビットマップＩＤに対応する記号の直前が、単語などの所定単位の末尾であるか判断する。例えば、伸長した記号列が英文の場合は、スペースを検出することで、直前の記号が単語の末尾であると判断する。また、伸長した記号列が日本語文の場合は、句読点を検出することで、直前の記号が文や句の末尾であると判断する。直前の記号が所定単位の末尾である場合は処理をステップＳ７６に進め、それ以外の場合は処理をステップＳ７７に進める。

（ステップＳ７６）伸長部１３２は、単語などの所定単位の記号列がブロックを跨いでいるか、すなわち、ステップＳ７４で保存したアドレスとステップＳ７５で検出した末尾のアドレスとの間に、ブロックの境界が存在するか判断する。ブロックを跨いでいる場合は処理をステップＳ８０に進め、それ以外の場合は処理をステップＳ７７に進める。

（ステップＳ７７）伸長部１３２は、ステップＳ７１において、ステップＳ１３またはステップＳ１８で取得した１またはそれ以上のビットマップＩＤの全てを選択したか（取得したビットマップＩＤの列の末尾まで選択したか）判断する。全て選択した場合は処理をステップＳ７８に進め、未選択のものがある場合は処理をステップＳ７１に進める。

（ステップＳ７８）伸長部１３２は、ステップＳ１４またはステップＳ１８でバッファ１２１に追加した記号の数だけ、スライド窓の位置を後方にシフトさせる。
（ステップＳ７９）伸長部１３２は、符号語部に続きの符号語があるか判断する。続きの符号語がある場合は処理をステップＳ１２に進め、無い場合は処理を終了する。

（ステップＳ８０）伸長部１３２は、バッファ１２１から、ステップＳ７４で保存したアドレス以降にある記号列（例えば、最後の単語）を削除する。また、バッファ１２２から、削除した記号列に対応するビットマップＩＤの列を削除する。

（ステップＳ８１）伸長部１３２は、ステップＳ８０で行った記号列およびビットマップＩＤの削除に合わせて、スライド窓とスタックの状態を、削除した記号列を伸長する前の状態に戻す。すなわち、伸長部１３２は、バッファ１２１から削除した記号の数だけスライド窓を前方にシフトさせる。また、伸長部１３２は、ステップＳ８０の削除を行った後のバッファ１２２の末尾に格納されている２つのビットマップＩＤを、１つ前および２つ前のビットマップＩＤとしてスタック１２３に格納する。

（ステップＳ８２）伸長部１３２は、インデックス１２４に含まれる各ビットマップ内の更新対象となるビットの位置を示すブロック番号をインクリメントする。
（ステップＳ８３）伸長部１３２は、ステップＳ８０で削除した記号列に対応する符号語を、伸長が完了していないものとみなして、処理をステップＳ１２に進める。このように、伸長部１３２は、２つのブロックに跨がる所定単位（例えば、単語）の記号列については、伸長を２回行うことで、両方のブロックに属するものとして扱う。伸長部１３２は、その記号列全体が前のブロックに属するとしてインデックス１２４を更新し、その後、その記号列全体が後のブロックにも属するとしてインデックス１２４を更新する。

図２４は、ブロック境界におけるインデックス生成例を示す図である。図２４に示す例では、英単語“ａｂｏｕｔ”を構成する５文字のうち、前半２文字がブロック＃２に含まれ、後半３文字がブロック＃３に含まれている場合を考える。

前半２文字“ａｂ”が伸長されると、インデックス１２４では、１グラム“ａ”や２グラム“ａｂ”に対応するビットマップ内のブロック＃２に対応するビットが“１”に設定される。続けて、後半３文字“ｏｕｔ”が伸長されると、ブロックがまだ切り替わっていないとみなされ、インデックス１２４では、１グラム“ｏ”や２グラム“ｂｏ”や３グラム“ａｂｏ”に対応するビットマップ内のブロック＃２に対応するビットが“１”に設定される。この時点では、ブロック＃３に対応するビットは更新されない。

英単語“ａｂｏｕｔ”の１回目の伸長が完了すると、その英単語がバッファ１２１から削除され、ブロックがブロック＃２からブロック＃３に切り替わったとみなされる。そして、前半２文字“ａｂ”が再び伸長されると、インデックス１２４では、１グラム“ａ”や２グラム“ａｂ”に対応するビットマップ内のブロック＃３に対応するビットが“１”に設定される。続けて、後半３文字“ｏｕｔ”が再び伸長されると、インデックス１２４では、１グラム“ｏ”や２グラム“ｂｏ”や３グラム“ａｂｏ”に対応するビットマップ内のブロック＃３に対応するビットが“１”に設定される。

このように、ブロック＃２，＃３に跨がる英単語“ａｂｏｕｔ”がブロック＃２，＃３の両方に属するとみなされて、インデックス１２４が生成される。これにより、ユーザが“ａｂｏｕｔ”をキーワードとして指定したときに、ブロック＃２，＃３を検索できる。なお、図２３，２４に示した２つのブロックに跨がる記号列を２回伸長する方法は、その記号列が両方のブロックに属するとみなしてインデックス１２４を生成するための方法の一例であり、他の方法でインデックス１２４を生成することもできる。また、２つのブロックに跨がる記号列を、２つのブロックの何れか一方のみに属するとみなしてもよい。

第４の実施の形態の情報端末装置によれば、第２の実施の形態と同様の効果が得られる。また、第４の実施の形態では、ユーザから指定されたキーワードが２つのブロックに跨がっていても、そのキーワードが現れる箇所を特定でき、検出漏れを抑制できる。

なお、前述のように、第１の実施の形態の情報処理は、情報処理装置１０にプログラムを実行させることで実現できる。また、第２〜第４の実施の形態の情報処理は、情報端末装置１００にプログラムを実行させることで実現できる。プログラムは、コンピュータ読み取り可能な記録媒体（例えば、記録媒体２１）に記録しておくことができる。記録媒体としては、磁気ディスク、光ディスク、光磁気ディスク、半導体メモリなどを使用できる。磁気ディスクには、ＦＤおよびＨＤＤが含まれる。光ディスクには、ＣＤ、ＣＤ−Ｒ（Recordable）／ＲＷ（Rewritable）、ＤＶＤおよびＤＶＤ−Ｒ／ＲＷが含まれる。

プログラムを流通させる場合、例えば、当該プログラムを記録した可搬記録媒体が提供される。また、プログラムを他のコンピュータの記憶装置に格納しておき、ネットワーク経由でプログラムを配布することもできる。コンピュータは、例えば、可搬記録媒体に記録されたプログラムまたは他のコンピュータから受信したプログラムを、記憶装置（例えば、不揮発性メモリ１０３）に格納し、当該記憶装置からプログラムを読み込んで実行する。ただし、可搬記録媒体から読み込んだプログラムを直接実行してもよく、他のコンピュータからネットワークを介して受信したプログラムを直接実行してもよい。

１０ 情報処理装置
１１ 圧縮データ
１２ 伸長データ
１３ インデックス
１４ 記憶部
１４ａ 辞書データ
１５ 伸長部

Claims (7)

1. 複数の記号それぞれに対応するフラグ情報を含み、圧縮データを伸長することで得られる伸長データに前記複数の記号それぞれが含まれているか否かを前記フラグ情報によって示すインデックスを生成するプログラムであって、コンピュータに、
   圧縮に用いられる符号と関連付けて、前記符号に対応する復号した記号と、前記インデックス内において前記復号した記号に対応するフラグ情報を識別するための識別情報とを含む辞書データにアクセスし、前記辞書データから、前記圧縮データに含まれる符号に関連付けられている前記復号した記号と前記識別情報とを取得し、
   取得した前記復号した記号を用いて前記伸長データを生成し、また、取得した前記識別情報が示す前記インデックス内のフラグ情報を更新する、
   処理を実行させるプログラム。
2. 前記インデックスは、Ｎ個（Ｎは２以上の整数）の記号の列である複数の記号列それぞれに対応する他のフラグ情報を更に含み、前記伸長データに各記号列が含まれているか否かを前記他のフラグ情報によって示しており、
   前記コンピュータが備える記憶装置に、前記圧縮データからの伸長が完了している直近のＮ−１個の記号に対応する識別情報を記憶する記憶領域を確保し、
   前記辞書データから１つの符号分の識別情報を取得すると、取得した前記識別情報と前記記憶領域に記憶された前記Ｎ−１個の記号に対応する識別情報との組み合わせによって示される、前記インデックス内の他のフラグ情報を更新する、
   処理を実行させる請求項１記載のプログラム。
3. 各記号列に対応する他のフラグ情報は、前記伸長データを所定長に分割したブロック毎に、当該ブロック内に当該記号列が含まれているか否かを示すフラグを含んでおり、
   一の記号列が第１のブロックと第２のブロックとに跨がるとき、前記第１のブロックと前記第２のブロックの両方が前記一の記号列を含むことを示すように、前記一の記号列に対応する他のフラグ情報を更新する、
   処理を実行させる請求項２記載のプログラム。
4. 前記圧縮データは、一の記号を符号化した符号に代えて当該一の記号より前に出現する記号と同一であることを示すアドレス情報を含む符号語を含んでおり、
   前記コンピュータが備える記憶装置に、前記圧縮データからの伸長が完了している記号と関連付けて当該記号に対応する識別情報を記憶する記憶領域を確保し、
   前記圧縮データから前記アドレス情報を取得したときは、前記アドレス情報が示す記号に関連付けられている識別情報を前記記憶領域から取得し、取得した前記識別情報が示す前記インデックス内のフラグ情報を更新する、
   処理を実行させる請求項１記載のプログラム。
5. 各記号に対応するフラグ情報は、前記伸長データを分割した所定の単位毎に、当該所定の単位のデータ内に当該記号が含まれているか否かを示すフラグを含んでおり、
   伸長する前記圧縮データの種類を判定し、複数の単位の候補の中から、前記圧縮データの種類に応じて前記所定の単位を選択する、
   処理を実行させる請求項１記載のプログラム。
6. 複数の記号それぞれに対応するフラグ情報を含み、圧縮データを伸長することで得られる伸長データに前記複数の記号それぞれが含まれているか否かを前記フラグ情報によって示すインデックスを生成する情報処理装置であって、
   圧縮に用いられる符号と関連付けて、前記符号に対応する復号した記号と、前記インデックス内において前記復号した記号に対応するフラグ情報を識別するための識別情報とを含む辞書データを記憶する記憶部と、
   前記辞書データから、前記圧縮データに含まれる符号に関連付けられている前記復号した記号と前記識別情報とを取得し、前記復号した記号を用いて前記伸長データを生成し、また、前記識別情報が示す前記インデックス内のフラグ情報を更新する伸長部と、
   を有する情報処理装置。
7. 複数の記号それぞれに対応するフラグ情報を含み、圧縮データを伸長することで得られる伸長データに前記複数の記号それぞれが含まれているか否かを前記フラグ情報によって示すインデックスを生成する、コンピュータが実行するインデックス生成方法であって、
   圧縮に用いられる符号と関連付けて、前記符号に対応する復号した記号と、前記インデックス内において前記復号した記号に対応するフラグ情報を識別するための識別情報とを含む辞書データにアクセスし、前記辞書データから、前記圧縮データに含まれる符号に関連付けられている前記復号した記号と前記識別情報とを取得し、
   取得した前記復号した記号を用いて前記伸長データを生成し、また、取得した前記識別情報が示す前記インデックス内のフラグ情報を更新する、
   インデックス生成方法。

Images