JP5771971B2

JP5771971B2 - 情報処理装置、情報処理方法、及びコンピュータプログラム

Info

Publication number: JP5771971B2
Application number: JP2010278634A
Authority: JP
Inventors: 淑隆林
Original assignee: Canon Marketing Japan Inc; Canon IT Solutions Inc
Current assignee: Canon Marketing Japan Inc; Canon IT Solutions Inc
Priority date: 2010-12-14
Filing date: 2010-12-14
Publication date: 2015-09-02
Anticipated expiration: 2030-12-14
Also published as: JP2012128603A

Description

本発明は、複数の文字列をデータ構造に効率良く格納し、当該データ構造へ文字列を追加して格納し、当該データ構造から文字列を検索するのに好適な技術に関する。

従来から、複数の文字列の集合に指定された文字列が存在するか否かを高速に判定するためのデータ構造として、トライ（ｔｒｉｅ）構造を用いた手法が提案されている。

トライ構造は、複数の文字列集合における共通接頭辞を状態遷移構造として表現することで、重複した記憶領域を削減し、且つ検索処理における無駄な処理も削減する。

このトライ構造を効率的に実装し且つ高速に検索する方法として、ダブル配列法が開示されている（非特許文献１）。ダブル配列法は２つの整数型配列（以下、ＢＡＳＥ配列及びＣＨＥＣＫ配列）にトライ構造を効率的に格納し、トライ構造上における状態遷移を、ＢＡＳＥ配列上の加算演算とＣＨＥＣＫ配列上の比較演算で実現する非常に高速な検索手法を開示している。さらに接尾辞部分について、状態遷移の分岐が発生しない状態遷移を１つの文字列型配列（以下、ＴＡＩＬ配列）に集約して格納することで、状態遷移を表すＢＡＳＥ配列とＣＨＥＣＫ配列の記憶領域を削減し且つ検索速度の向上を図っている。

また、非特許文献２では前記ダブル配列法を改良し、よりコンパクトなダブル配列構造を実装する方法が開示されている。具体的には、前述したＴＡＩＬ配列について、後方一致する共通接尾辞を併合することで、ＴＡＩＬ配列のさらなる圧縮を行っている。

このようにダブル配列法は、トライ構造上の状態遷移において、分岐の発生しない部分をＴＡＩＬ配列として実装することで、空間領域の削減と検索速度の向上を図っている。

一方、トライ構造の空間効率を重視した実装方法として、簡潔木法が開示されている（非特許文献３）。簡潔木法はトライ構造上で幅優先探索を行い、トライ構造をビット列に変換する。このビット列構造とトライ構造上の状態遷移を表す文字集合を合わせて格納することで、非常にコンパクトなトライ構造の実装が実現できる。

しかしながら、簡潔木法は、常にビット列構造を先頭からカウントする関数を用いて状態遷移を行う。具体的には、先頭からのビット１の数を返すrank₁関数、及び先頭からｎ番目の０ビットの位置を返すselect₀関数を利用する。これらの状態遷移関数は算出コストが高く、特にselect₀関数は非常に算出コストが高い。従って、前述したビット列構造に対して、任意の大きさの区画ごとに当該ビット数を予め算出した索引を併用する実装が一般的である。

青江順一、「ダブル配列による高速ディジタル検索アルゴリズム」、電子情報通信学会論文誌、Vol.J71-D、No.4、pp.1592-1600、1988 矢田晋ほか、「ダブル配列におけるキャッシュの効率化」、FIT2006、pp.71-72、2006 G.Jacobson、「Space-efficent static trees and graphs」、In Proc. 30th FOCS、pp.549-554、1989

ダブル配列法は、非常に高速な検索手法が特徴であるが、元になる文字列集合の大きさに対して、同等もしくは大きなサイズのデータ構造になる。また、簡潔木法は元になる文字列集合の大きさに対して、非常にコンパクトなデータ構造になるが、ビット列の探索において検索手法が高速にならない。

本発明は上記の課題を解決するためになされたものであり、指定された文字列を用いて、データ構造として登録された文字列を検索する処理の効率化を図る技術を提供することを目的とする。

上記した目的を達成するために、本発明の情報処理装置は、検索対象となる複数の第１のキーワードをデータとしてダブル配列へ登録する登録手段と、前記登録手段で登録されたダブル配列のデータを用いて幅優先探索を行うための簡潔木構造に登録するためのデータを作成する作成手段と、前記作成手段によって作成したデータを備えた簡潔木構造を記憶する記憶手段と、前記複数の第１のキーワードを検索するための検索キーワードである第２のキーワードの入力を受け付ける受付手段と、前記受付手段で受け付けた第２のキーワードが前記複数の第１のキーワードに含まれるか、を前記記憶手段によって記憶された前記簡潔木構造を用いて検索する検索手段と、を備え、前記作成手段は、前記ダブル配列のトライ構造を構成するノードに対するＴＡＩＬ配列へのリンクを前記簡潔木構造のノードに対する前記ＴＡＩＬ配列へのリンクとしてデータを作成し、前記検索手段は、前記受付手段で受け付けた第２のキーワードの最初の文字を読み込み、前記簡潔木構造のルートノードを第１のノードに設定し、該第１のノードの子ノードに前記読み込んだ文字を示す子ノードがあるかを判定し、前記読み込んだ文字を示す子ノードがあると判定した場合には、当該子ノードを第１のノードに設定し、前記第２のキーワードの次の１文字を読み込み、変更後の第１のノードに該読み込んだ１文字を示す子ノードが存在するかを判定する処理を繰り返し、前記読み込んだ文字を示す子ノードがないと判定した場合には、前記子ノードから前記ＴＡＩＬ配列へのリンクを参照することで前記ＴＡＩＬ配列に遷移し、前記ＴＡＩＬ配列に残りの文字列が登録されているかを判定することにより、前記第２のキーワードが前記複数の第１のキーワードに含まれるかを検索することを備えることを特徴とする。

上記した目的を達成するために、本発明の情報処理方法は、データの検索処理を行う情報処理装置によって行われる情報処理方法であって、前記情報処理装置は、検索対象となる複数の第１のキーワードをデータとしてダブル配列へ登録する登録工程と、前記登録工程で登録されたダブル配列のデータを用いて幅優先探索を行うための簡潔木構造に登録するためのデータを作成する作成工程と、前記作成工程によって作成したデータを備えた簡潔木構造を記憶する記憶工程と、前記複数の第１のキーワードを検索するための検索キーワードである第２のキーワードの入力を受け付ける受付工程と、前記受付工程で受け付けた第２のキーワードが前記複数の第１のキーワードに含まれるか、を前記記憶工程によって記憶された前記簡潔木構造を用いて検索する検索工程と、を実行し、前記作成工程は、前記ダブル配列のトライ構造を構成するノードに対するＴＡＩＬ配列へのリンクを前記簡潔木構造のノードに対する前記ＴＡＩＬ配列へのリンクとしてデータを作成し、前記検索工程は、前記受付手段で受け付けた第２のキーワードの最初の文字を読み込み、前記簡潔木構造のルートノードを第１のノードに設定し、該第１のノードの子ノードに前記読み込んだ文字を示す子ノードがあるかを判定し、前記読み込んだ文字を示す子ノードがあると判定した場合には、当該子ノードを第１のノードに設定し、前記第２のキーワードの次の１文字を読み込み、変更後の第１のノードに該読み込んだ１文字を示す子ノードが存在するかを判定する処理を繰り返し、前記読み込んだ文字を示す子ノードがないと判定した場合には、前記子ノードから前記ＴＡＩＬ配列へのリンクを参照することで前記ＴＡＩＬ配列に遷移し、前記ＴＡＩＬ配列に残りの文字列が登録されているかを判定することにより、前記第２のキーワードが前記複数の第１のキーワードに含まれるかを検索することを実行することを特徴とする。

上記した目的を達成するために、本発明のコンピュータプログラムは、データの検索処理を行う情報処理装置において読取り実行可能なコンピュータプログラムであって、前記情報処理装置を、検索対象となる複数の第１のキーワードをデータとしてダブル配列へ登録する登録手段と、前記登録手段で登録されたダブル配列のデータを用いて幅優先探索を行うための簡潔木構造に登録するためのデータを作成する作成手段と、前記作成手段によって作成したデータを備えた簡潔木構造を記憶する記憶手段と、前記複数の第１のキーワードを検索するための検索キーワードである第２のキーワードの入力を受け付ける受付手段と、前記受付手段で受け付けた第２のキーワードが前記複数の第１のキーワードに含まれるか、を前記記憶手段によって記憶された前記簡潔木構造を用いて検索する検索手段と、して機能させ、前記作成手段は、前記ダブル配列のトライ構造を構成するノードに対するＴＡＩＬ配列へのリンクを前記簡潔木構造のノードに対する前記ＴＡＩＬ配列へのリンクとしてデータを作成し、前記検索手段は、前記受付手段で受け付けた第２のキーワードの最初の文字を読み込み、前記簡潔木構造のルートノードを第１のノードに設定し、該第１のノードの子ノードに前記読み込んだ文字を示す子ノードがあるかを判定し、前記読み込んだ文字を示す子ノードがあると判定した場合には、当該子ノードを第１のノードに設定し、前記第２のキーワードの次の１文字を読み込み、変更後の第１のノードに該読み込んだ１文字を示す子ノードが存在するかを判定する処理を繰り返し、前記読み込んだ文字を示す子ノードがないと判定した場合には、前記子ノードから前記ＴＡＩＬ配列へのリンクを参照することで前記ＴＡＩＬ配列に遷移し、前記ＴＡＩＬ配列に残りの文字列が登録されているかを判定することにより、前記第２のキーワードが前記複数の第１のキーワードに含まれるかを検索することとして機能させるためのコンピュータプログラムである。

本発明によれば、巨大な文字列集合を単体の計算機上で実現可能なサイズまでコンパクトに実装した辞書構造ファイルを実行できるシステムを提供でき、さらには、組み込み機器のような限られたリソースを持つ環境では、辞書をよりコンパクトに実装し且つ実用的に検索できる、等の効果を奏する。

本発明の実施形態における文字列登録検索システムの構成を示す図である。本発明の実施形態における各種端末のハードウェア構成を示す図である。本発明の実施形態における文字列登録処理のフローチャートである。本発明の実施形態におけるＴＡＩＬ併合処理のフローチャートである。本発明の実施形態における簡潔木生成処理のフローチャートである。本発明の実施形態における遷移可能集合追加処理のフローチャートである。本発明の実施形態におけるキーワード集合の一例である。本発明の実施形態における併合ＴＡＩＬ配列を用いたダブル配列構造の一例である。本発明の実施形態における併合ＴＡＩＬ配列を用いた簡潔木構造の一例である。本発明の実施形態における簡潔木検索処理のフローチャートである。

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

図１は、本発明の実施形態における文字列登録検索装置の構成を示す図である。

文字列登録検索装置１００は、ダブル配列構築部１０２と、簡潔木構築部１０３と、簡潔木データ１０４と、検索結果表示部１０５と、簡潔木検索部１０６とを備える。尚、簡潔木データ１０４は後述する外部メモリ２１１等の記憶装置に記憶されている。

ダブル配列構築部１０２は、キーワード集合１０１を入力としてダブル配列を構築する。構築されたダブル配列は簡潔木構築部１０３に送られて、簡潔木データ１０４を生成する。簡潔木検索部１０６は、検索キーワード１０７を入力として簡潔木データ１０４を検索し、検索結果を検索結果表示部１０５に表示する。これら一連のデータ登録処理及びデータ検索処理については、詳しく後述する。

次に、図１の文字列登録検索装置１００のハードウェア構成について、図２を用いて説明する。

図中、ＣＰＵ２０１は、システムバス２０４に接続される後述の各デバイスやコントローラを統括的に制御する。また、ＲＯＭ２０３あるいは外部メモリ２１１には、ＣＰＵ２０１の制御プログラムであるＢＩＯＳ（Basic Input / Output System）やオペレーティングシステムプログラム（以下、ＯＳ）や、文字列登録検索装置１００に後述する各種の処理を実行させるために必要な各種プログラムやデータ等が記憶されている。ＲＡＭ２０２は、ＣＰＵ２０１の主メモリ、ワークエリア等として機能する。

ＣＰＵ２０１は、処理の実行に際して必要なプログラム等をＲＡＭ２０２にロードして、プログラムを実行することで後述する各種処理を実現するものである。また、入力コントローラ（入力Ｃ）２０５は、キーボードやポインティングデバイス等で構成される入力装置２０９からの入力を制御する。ビデオコントローラ（ＶＣ）２０６は、ディスプレイ装置２１０等の表示装置への表示を制御する。ディスプレイ装置２１０は、例えばＣＲＴディスプレイや液晶ディスプレイ等で構成される。

メモリコントローラ（ＭＣ）２０７は、ブートプログラム、ブラウザソフトウエア、各種のアプリケーション、フォントデータ、ユーザファイル、編集ファイル、各種データ等を記憶するハードディスク（ＨＤ）やフロッピーディスク（登録商標ＦＤ）或いはＰＣＭＣＩＡカードスロットにアダプタを介して接続されるコンパクトフラッシュメモリ等の外部メモリ２１１へのアクセスを制御する。

通信Ｉ／Ｆコントローラ（通信Ｉ／ＦＣ）２０８は、ネットワークを介して、外部機器と接続・通信するものであり、ネットワークでの通信制御処理を実行する。例えば、ＴＣＰ／ＩＰを用いたインターネット通信等が可能である。

なお、ＣＰＵ２０１は、例えばＲＡＭ２０２内の表示情報用領域へアウトラインフォントの展開（ラスタライズ）処理を実行することにより、ディスプレイ装置２１０上での表示を可能としている。また、ＣＰＵ２０１は、ディスプレイ装置２１０上の不図示のマウスカーソル等でのユーザ指示を可能とする。以上が、文字列登録検索装置１００のハードウェア構成の説明であるが、後述する各種の処理を実行可能であれば、必ずしも図２に記載のハードウェア構成を有していなくとも構わないことは言うまでもない。

次に、文字列登録検索装置１００における文字列登録処理について、図３から図９を用いて、詳しく説明する。

図３は、文字列登録処理の全体フローチャートを示す図である。文字列登録処理では、ＣＰＵ２０１は、キーワード集合１０１を読み込み、ダブル配列構造を構築してから簡潔木データ構造を作成する処理を行う。この文字列登録処理は、ＣＰＵ２０１をダブル配列構築部１０２、簡潔木構築部１０３として機能させるためのプログラムによる制御に従って行われる処理である。文字列登録処理の説明の前に、この処理で扱うキーワード集合の一例を、図７を参照して説明する。

図７は、キーワード集合１０１の一例である。キーワード７０１は、文字列「山形県」に対して数値「１０」が定義されている。同様に、キーワード７０２は文字列「山梨県」に対して数値「２０」が定義され、キーワード７０３は文字列「大阪府大阪市」に数値「３０」が定義されている。キーワード７０４から７０６についても同様である。前記数値は、例えばＩＤ番号を示すものである、等であり、キーワード集合を利用するソフトウェア上において意味を持つ数値である（以下、ＯＵＴＰＵＴ値とする）。

図３に戻って、ステップＳ３０１において、ＣＰＵ２０１は、図７に示すキーワード集合を１行ずつ読み込む。このとき、行情報は所定の書式に従って文字列とＯＵＴＰＵＴ値に分解され、ステップＳ３０２において、ダブル配列に追加される。本実施形態におけるダブル配列は、文字列による検索処理が成功すると、ＯＵＴＰＵＴ値が返される。

続いて、ステップＳ３０３において、ＣＰＵ２０１は、すべてのキーワード集合について登録処理が完了したかどうかを判定し、未処理情報があると判定した場合には処理をステップＳ３０１に進める。すべてのキーワードをダブル配列へ登録完了したと判定した場合（ステップＳ３０３で「ＹＥＳ」の場合）は、ステップＳ３０４に進み、ＴＡＩＬ併合処理を実施する。

ＴＡＩＬ併合処理は、非特許文献２で開示されている共通接尾辞を併合したＴＡＩＬ配列のデータ構造について、ダブル配列への追加処理（ステップＳ３０２）の際に発生するＴＡＩＬ配列内の未使用領域を削減しつつ当該データ構造を作成する処理を示す。この処理の詳細は図４を参照して説明する。

ここで、図４を参照して、図３のステップＳ３０４のＴＡＩＬ併合処理の詳細について説明する。図４はＴＡＩＬ併合処理の詳細を示すフローチャートである。ＴＡＩＬ併合処理では、ＴＡＩＬ配列内の未使用領域を回収するために、ＢＡＳＥ配列からＴＡＩＬ配列へのリンクが定義されているものを探索する。

ＣＰＵ２０１は、ステップＳ４０１で、当該リンクを登録するためのリストを初期化し、続くステップＳ４０２からＢＡＳＥ配列の探索を開始する。具体的には、ＢＡＳＥ配列の値が負数になっているものがＴＡＩＬ配列へのリンクを表現しており、その絶対値がＴＡＩＬ配列の添字である。従って、有効なＢＡＳＥ配列の中から負値を持つものについて、そのリンク先となるＴＡＩＬ配列に登録されたＴＡＩＬ文字列を取得し（ステップＳ４０３）、取得したＴＡＩＬ文字列を反転させた反転ＴＡＩＬ文字列とリンク元となるＢＡＳＥ配列の添字をセットにして前記リストに追加する（ステップＳ４０４）。

すべてのＴＡＩＬ文字列を追加した後、続くステップＳ４０５において、反転ＴＡＩＬ文字列をキーとして、前記リストを逆順ソートする。即ち、前記リストを順に辿ることで、反転ＴＡＩＬ文字列を逆辞書順に取得することができる。

続くステップＳ４０６で、ＣＰＵ２０１は新しくＴＡＩＬ配列を格納する領域（以下、併合ＴＡＩＬ配列）を確保し、ステップＳ４０７で前記リストから先頭要素を取得する。続くステップＳ４０８で、ステップＳ４０６で確保した併合ＴＡＩＬ配列に、反転していない元の正ＴＡＩＬ文字列を登録する。元の正ＴＡＩＬ文字列は、反転ＴＡＩＬ文字列を反転させて得ることもできるし、ステップＳ４０４において、別要素にセットして前記リストに追加してもよい。続くステップＳ４０９で、ＢＡＳＥ配列の更新を行う。前記反転ＴＡＩＬ文字列とセットで追加したＢＡＳＥ配列の添字を参照することで、当該ＢＡＳＥ配列の値を併合ＴＡＩＬ配列への添字の負数に更新し、ＢＡＳＥ配列から併合ＴＡＩＬ配列へのリンクを更新する。

具体例をあげて説明する。ＢＡＳＥ［２６］＝−１２であるとき、ＴＡＩＬ［１２］から正ＴＡＩＬ文字列「ＡＢＣ」が取得できたとする。このとき、ステップＳ４０４で前記リストに登録するセットは、（２６、「ＣＢＡ」）である。また、併合ＴＡＩＬ配列に登録した先がＴＡＩＬ［１］の場合、ステップＳ４０９で、ＢＡＳＥ［２６］＝−１に更新する。

その後、ＣＰＵ２０１はステップＳ４１０で、ＢＡＳＥ配列をすべて探索したかを判定し、すべての探索が終了したと判定した場合すれば（ステップＳ４１０で「ＹＥＳ」の場合）、ＴＡＩＬ併合処理を終了する。探索が終了していないと判定した場合には（ステップＳ４１０で「ＮＯ」の場合）、ステップＳ４１１に進める。

ＣＰＵ２０１は、ステップＳ４１１において、前記リストから次の要素セットを取得し、続くステップＳ４１２で、取得したセットの反転ＴＡＩＬ文字列と、前記ステップＳ４０７で取得したセットの反転ＴＡＩＬ文字列を比較する。このとき、ステップＳ４１１で取得した反転ＴＡＩＬ文字列がステップＳ４０７で取得した反転ＴＡＩＬ文字列に含まれていると判定した場合（共通接頭辞になっている場合、即ち、ステップＳ４１２で「ＹＥＳ」の場合）、ステップＳ４０９に戻り、ＢＡＳＥ配列の更新のみを実施する。ステップＳ４１２で「ＮＯ」の場合、ステップＳ４０８に戻り、併合ＴＡＩＬ配列に正ＴＡＩＬ文字列に登録して、続くステップＳ４０９でＢＡＳＥ配列の更新を実施する。

前述の具体例で説明する。先頭要素の反転ＴＡＩＬ文字列「ＣＢＡ」である場合に、次要素のセットが（７、「ＣＢ」）である場合、ステップＳ４１２において、共通接頭辞であると判断し（「ＹＥＳ」の場合）、ＢＡＳＥ［７］＝−２とする。即ち、ＴＡＩＬ［１］で正ＴＡＩＬ文字列「ＡＢＣ」を得ることができ、ＴＡＩＬ［２］で正ＴＡＩＬ文字列「ＢＣ」を得ることができる。また、次要素のセットが（７、「ＤＡ」）である場合は、ステップＳ４１２において「ＮＯ」となり、ＴＡＩＬ［５］＝ＡＤを登録し（ステップＳ４０８）、ＢＡＳＥ［７］＝−５となる（ステップＳ４０９）。

このように、前記リストに追加したすべての要素セットについて、ＢＡＳＥ配列の更新処理と併合ＴＡＩＬ配列への登録処理を実施することで、非特許文献２で開示されているデータ構造を得ることができる。以上が、ＴＡＩＬ併合処理の詳細な説明である。

図８に、図７で示したキーワード集合７００を入力にした、併合ＴＡＩＬ配列を用いたダブル配列構造の一例を示す。ダブル配列構造は、ＢＡＳＥ配列部８０１、ＣＨＥＣＫ配列部８０２、併合ＴＡＩＬ配列部８０３、ＯＵＴＰＵＴ部（索引部８０４及び値部８０５）で構成される。変換表８０６は、ダブル配列構造に登録される文字列に対して、文字を数値に置き換えたものである。通常は文字コードを使用するが、本発明では以降の説明の簡略化のために、便宜的に定義した。

ＯＵＴＰＵＴ索引部８０４は、ＢＡＳＥ配列部８０１において併合ＴＡＩＬ配列部８０３へのリンクが定義されているものについて１を定義し、その他は０となるビット列で表現される。即ち、当該ＯＵＴＰＵＴ値を得るためには、ＯＵＴＰＵＴ索引部８０４においてrank₁関数を用いればよい。例えば、ＢＡＳＥ［４］＝−１であることから、ＢＡＳＥ［４］はＴＡＩＬ［１］へのリンクを意味している。このとき、ＯＵＴＰＵＴ索引部８０４において、ＢＡＳＥ配列の添字４を引数にしてrank₁(4)を求めると２であることから、ＯＵＴＰＵＴ［２］を参照し、ＯＵＴＰＵＴ値「２０」を得る（図７におけるキーワード７０２の検索結果を意味する）。

図３の説明に戻る。ＣＰＵ２０１は、ＴＡＩＬ併合処理（ステップＳ３０４）が終了すると、処理をステップＳ３０５に進め、前記併合ＴＡＩＬ配列を用いたダブル配列構造を入力として、簡潔木生成処理を実施する。この処理の詳細は図５を参照して説明する。

ここで、図５を参照して、図３のステップＳ３０５の簡潔木生成処理の詳細について説明する。図５は、簡潔木生成処理の詳細を示すフローチャートである。簡潔木生成処理では、ダブル配列構造を幅優先探索方式で辿ることにより簡潔木を生成する。

まずＣＰＵ２０１は、ステップＳ５０１で簡潔木構造における先頭ビット列「１０」を追加する。そして、続くステップＳ５０２において、状態キューを初期化する。前記状態キューはダブル配列構造において幅優先探索を実現するために使用される。

ステップＳ５０３では、状態ｓを１に初期化し、ステップＳ５０４で遷移可能集合追加処理を実施する。遷移可能集合追加処理では、状態ｓから遷移可能な文字を探索し、前記状態キューに追加する処理を実施する。この遷移可能集合追加処理の詳細については、図６を参照して説明することにする。

ここで、図６を参照して、図５のステップＳ５０４（及びステップＳ５１１）の遷移可能集合追加処理の詳細について説明する。図６は遷移可能集合追加処理の詳細を示すフローチャートである。

まずＣＰＵ２０１はステップＳ６０１で、遷移可能な文字を保持するためのリストを初期化する。続くステップＳ６０２からステップＳ６０３において、状態ｓから遷移可能なすべての文字を探索する。前述したように、ダブル配列構造はＣＨＥＣＫ配列の値が遷移元の状態番号を示すことが開示されているため、有効な文字集合の範囲内で、ＣＨＥＣＫ配列の値がＢＡＳＥ配列添字になるものを探索すればよい。

具体的には、例えば、有効な文字集合をアルファベット２６文字とし且つＡを１、Ｂを２・・・Ｚを２６、と定義した場合において、ＢＡＳＥ［１］＝２のとき、ＢＡＳＥ［１］＋１からＢＡＳＥ［１］＋２６の範囲、即ち、ＣＨＥＣＫ［３］からＣＨＥＣＫ［２８］の範囲において、ＣＨＥＣＫ［ｓ］＝１であるｓを満たす文字を探索する。

その後、ＣＰＵ２０１はステップＳ６０４において、前記条件を満たす文字Ciを前記リストに追加する。

続くステップＳ６０５以降の処理において、前記リストに追加されたすべての文字Ciについて、図５のステップＳ５０２で初期化した前記状態キューに追加する。

ここで、ＢＡＳＥ［ｓ］が正値の場合（ステップＳ６０６で「ＹＥＳ」の場合）、ダブル配列構造において分岐を持った遷移状態を意味しているので、ステップＳ６０７に進み、遷移先の状態番号を示すＢＡＳＥ［ｓ］＋Ciとペアにして、状態（ＢＡＳＥ［ｓ］＋Ci、Ci）を前記状態キューに追加する。ＢＡＳＥ［ｓ］が正値でない場合（ステップＳ６０６で「ＮＯ」の場合）、ＢＡＳＥ［ｓ］はＴＡＩＬ配列へのリンク、或いは後述する終端状態を示しているので、ステップＳ６０８に進み、状態（ＢＡＳＥ［ｓ］、Ci）を前記状態キューに追加する。

以上の遷移可能集合追加処理によって、状態ｓから遷移可能なすべての文字が遷移先の状態番号と共に、前記状態キューに追加されたことになる。続くステップＳ６０９において、状態ｓからの遷移探索が完了したことを意味する終端状態（０、０）を前記状態キューに追加する。以上が、遷移可能集合追加処理の詳細な説明である。

図５の説明に戻る。ステップＳ５０４の遷移可能集合追加処理終了後、ＣＰＵ２０１は、ステップＳ５０５において、前記状態キューが空かどうかを判定する。空でないと判定した場合（ステップＳ５０５で「ＮＯ」の場合）、処理をステップＳ５０６に進め、前記状態キューから状態（ｓ、ｃ）をひとつ取得する。

続くステップＳ５０７の判定処理において、ＣＰＵ２０１が状態ｓを正値であると判定した場合（ステップＳ５０７で「ＹＥＳ」の場合）、ステップＳ５０８に進む。ここでＢＡＳＥ［ｓ］が正数の場合（ステップＳ５０８で「ＮＯ」の場合）、ステップＳ５０６で取得した状態ｓは分岐を持った遷移状態であるので、ステップＳ５１１に進み、前述した遷移可能集合追加処理を再帰的に実施して、ステップＳ５１２に進む。このように前記状態キューを使用することで、ダブル配列構造において幅優先探索を実現している。

また、ステップＳ５０８で「ＹＥＳ」とＣＰＵ２０１が判定した場合、即ち、ＢＡＳＥ［ｓ］が負数の場合は前記併合ＴＡＩＬ配列へのリンクを示す状態であるため、ステップＳ５０９に進み、新たに併合ＴＡＩＬ配列へのリンクを作成する。簡潔木構造では、状態ｓに対応するビット番号に対して併合ＴＡＩＬ配列へのリンクを設定する必要がある。従って、前述した図８におけるＯＵＴＰＵＴ索引部８０４とＯＵＴＰＵＴ値部８０５のように、rank₁関数を用いた索引部とリンク部の構造を持つように併合ＴＡＩＬ配列へのリンクを設定する。当該リンク構造の詳細については、後述する。

ステップＳ５０９の処理終了後、処理をステップＳ５１０に進め、状態ｓから分岐できる遷移は存在しないため（併合ＴＡＩＬ配列への分岐なし状態遷移のみ存在する）、前記状態キューに終端状態（０、０）を追加し、ステップＳ５１２に進む。

ステップＳ５０７の判定処理で戻って「ＮＯ」と判定した場合、即ち、状態ｓが正値でない場合には、処理をステップＳ５１２に進める。

ステップＳ５１２では、ステップＳ５０６で取得した文字ｃをエッジ文字として簡潔木に登録する。文字ｃが０でない場合は、簡潔木のビット列に１を追加して、文字ｃをエッジ文字列に追加する。文字ｃが０の場合は（終端状態）、簡潔木のビット列に０を追加する。

ステップＳ５１２での文字ｃの登録処理が終了すると、処理をステップＳ５０５に進め、前記状態キューが空になるまで、前述した処理を繰り返す。

前記状態キューが空になった場合（ステップＳ５０５で「ＹＥＳ」の場合）、ステップＳ５１３に進み、索引生成処理を実施する。索引生成処理は、ビット列におけるrank₁関数やselect₀関数の算出コストを削減するために、任意の大きさの区画ごとに当該ビット数を予め算出した索引を生成する処理である。

以上の処理により、ダブル配列構造において幅優先探索を実施し、簡潔木構造への変換が実現される。

図９に、図８に示したダブル配列構造から生成した簡潔木構造を一例として示す。簡潔木構造は、トライ構造を表すビット配列９０１とエッジ文字列９０２、併合ＴＡＩＬ配列へのリンクを示すＴＡＩＬビット配列９０３とＴＡＩＬリンク配列９０４、ＯＵＴＰＵＴ値を保持するＯＵＴＰＵＴ配列９０５、及び併合ＴＡＩＬ配列９０６から構成される。併合ＴＡＩＬ配列９０６は、図８における前記併合ＴＡＩＬ配列８０３と同等のものである。また、エッジ文字列９０２及び併合ＴＡＩＬ配列９０６内に保持されている文字は、図８の前記変換表８０６を用いて数値に置き換えている。

ビット配列９０１及びＴＡＩＬビット配列９０３はビット列で表現される。従って、前述したように、これらのデータにはrank₁関数やselect₀関数の算出コストを削減するための索引情報が付与されることになる。

図１０に、前期簡潔木構造の検索方法のフローチャートを示す。なお、図９を合わせて用いることで、具体的に検索方法を説明する。

まず、ＣＰＵ２０１は、ステップＳ１００１で検索キーワードから文字ｃを取得する。文字ｃが取得できた場合（ステップＳ１００２で「ＹＥＳ」の場合）、ステップＳ１００３に進み、簡潔木構造における最初の子ノードを探索する。最初の子ノードの探索は、次の関数として非特許文献３に開示されている。

first-child (n) = select₀(rank₁(n))＋１

図９を用いて具体的に説明する。検索開始位置はビット配列９０１の１番目であり、rank₁(1)＝１である。従って、select₀(1)＝２となり、first-child (1)＝３であるから、最初の子ノード番号が３とわかる。ここでビット配列９０１の３番目を見ると１であるため、子ノードが存在することがわかる。０や領域外の場合は、子ノードは存在しない。

続くステップＳ１００４で、子ノードが存在するかどうかを確認する。子ノードが存在する場合（ステップＳ１００４で「ＹＥＳ」の場合）、ステップＳ１００５に進む。ステップＳ１００５で当該子ノードに対応したエッジ文字を取得する。エッジ文字は図９におけるエッジ文字列９０２に登録されており、その算出式は以下のようになる。

e = edge[rank₁(n)−１]

図９の例で説明する。ビット配列９０１の３番目のエッジ文字は、rank₁(3)＝２であるため、edge[1]＝１が選択される。文字コード「１」は、図８における変換表８０６において、文字「山」であることがわかる。従って、ビット配列９０１の３番目のエッジ文字は「山」となる。

図１０のステップＳ１００５ではさらに、取得したエッジ文字ｅとステップＳ１００１で取得した検索キーワードの文字ｃが一致するかを判定する。ＣＰＵ２０１が一致したと判定した場合（ステップＳ１００５で「ＹＥＳ」の場合）、状態遷移が成立したため、ステップＳ１００１に戻り、検索キーワードにおける次の文字を取得し、その文字について、簡潔木構造上での状態遷移を確認する。

ステップＳ１００５の判定処理で、取得したエッジ文字ｅとステップＳ１００１で取得した検索キーワードの文字ｃが一致しないとＣＰＵ２０１が判定した場合（ステップＳ１００５で「ＮＯ」の場合）、ステップＳ１００６に進み、兄弟ノードの探索を実施する。簡潔木構造は幅優先探索を用いて作成されているため、兄弟ノードの探索は、当該ビット列において、隣接するビットが１であれば探索に成功する。図９のビット配列９０１の例では、子ノード番号３に隣接する子ノード番号４のビットが１であることから、子ノード番号４は子ノード番号３の兄弟ノードであるとわかる。

ステップＳ１００７で兄弟ノードが存在しないと判定した場合（ステップＳ１００７で「ＮＯ」の場合）、当該検索キーワードを用いた簡潔木構造において、もはや状態遷移が成立し得ないため、検索失敗として簡潔木検索処理を終了する。

一方、ステップＳ１００７で、兄弟ノードが存在するとＣＰＵ２０１が判定した場合（ステップＳ１００７で「ＹＥＳ」の場合）には、ステップＳ１００５に戻り、当該ビット番号のエッジ文字と当該検索キーワードから取得した文字ｃとの比較を実施する。

このように、当該検索キーワードを１文字ずつ簡潔木構造上で探索していくが、子ノードが存在しない場合（ステップＳ１００４で「ＮＯ」の場合）、或いは、当該検索キーワードすべての文字を探索した場合（ステップＳ１００２で「ＮＯ」の場合）、ステップＳ１００８へ進む。

ステップＳ１００８以降では、ビット配列９０１上における状態遷移が終了し、遷移分岐のない併合ＴＡＩＬ配列９０６を用いた探索を実施する。ステップＳ１００８において、併合ＴＡＩＬ配列９０６へのリンクを取得する。例えば、検索キーワードが「山形県」の場合、ビット配列９０１上を、１⇒３⇒６⇒１３と遷移し bit[13]＝０であることから、ビット番号６までの状態遷移が成立する。ここで、ＴＡＩＬビット配列９０３に対してrank₁(6)を算出すると１であるので、ＴＡＩＬリンク配列９０４を参照して
併合ＴＡＩＬ配列９０６へのリンク値 tail_link [1] ＝１を得る。

続くステップＳ１００９で、前記リンク値が取得できたかどうかを判定する。取得できなかったと判定した場合（ステップＳ１００９で「ＮＯ」の場合）、併合ＴＡＩＬ配列へのリンクが存在しないため、検索失敗として簡潔木検索処理を終了する。取得できたと判定した場合（ステップＳ１００９で「ＹＥＳ」の場合）は、ステップＳ１０１０に進む。

ステップＳ１０１０では、前記検索キーワードの未探索部分である接尾辞部と、併合ＴＡＩＬ配列９０６に格納された文字列が一致するかどうかを調べる。一致しなかった場合（ステップＳ１０１０で「ＮＯ」の場合）、前記検索キーワードが存在しないことから、検索失敗として簡潔木検索処理を終了する。

前述の例では、検索キーワード「山形県」において、「山形」までがビット配列９０１上で確認されており、残りの接尾辞「県」が併合ＴＡＩＬ配列９０６との比較対象となる。前記ＴＡＩＬリンク配列９０４から得たリンク値が１であるため、併合ＴＡＩＬ配列９０６の１番目を先頭に文字列比較を実施する。Tail[1]＝10であることから、変換表８０６を参照すると「県」であり、続くTail[2]＝０で終端となる。従って、前記検索キーワードの接尾辞「県」と併合ＴＡＩＬ配列９０６に登録された文字列「県」が一致することがわかる。

ステップＳ１０１０で「ＹＥＳ」と判定した場合、即ち、文字列比較が一致した場合はステップＳ１０１１に進む。ステップＳ１０１１では、ＯＵＴＰＵＴ値をＯＵＴＰＵＴ配列９０５から取得する。取得する方法は、ＴＡＩＬリンク配列９０４と同様であり、ＴＡＩＬビット配列９０３を用いて取得する。

以上の処理をもって、検索キーワードの検索が成功し、簡潔木検索処理はＯＵＴＰＵＴ値を返すことができる。

以上説明したように、本実施形態によれば、ダブル配列構造を経由させて簡潔木構造を構築することによって、トライ構造をコンパクトに実装できる。また、簡潔木構造の検索において、その計算コストが大きいビット配列を使った状態遷移を最小限に留め、検索速度の向上に寄与している。

以上、実施形態例を詳述したが、本発明は、例えば、システム、装置、方法、プログラムもしくは記憶媒体等としての実施態様をとることが可能であり、具体的には、複数の機器から構成されるシステムに適用しても良いし、また、一つの機器からなる装置に適用しても良い。

なお、上述した各種データの構成及びその内容はこれに限定されるものではなく、用途や目的に応じて、様々な内容で構成されることは言うまでもない。

また、本発明は、システム或いは装置にプログラムを供給することにとって達成される場合にも適用できることは言うまでもない。この場合、本発明を達成するためのソフトウェアによって表されるプログラムを格納した記録媒体を該システム或いは装置に読み出すことによって、そのシステム或いは装置が、本発明の効果を享受することが可能となる。

さらに、本発明を達成するためのソフトウェアによって表されるプログラムをネットワーク上のサーバー、データーベース等から通信プログラムによりダウンロードして読み出すことによって、そのシステム或いは装置が、本発明の効果を享受することが可能となる。

なお、上述した各実施形態及びその変形例を組み合わせた構成もすべて本発明に含まれるものである。

１００文字列登録検索装置
１０１キーワード集合
１０２ダブル配列構築部
１０３簡潔木構築部
１０４簡潔木データ
１０５検索結果表示部
１０６簡潔木検索部
１０７検索キーワード
２０１ＣＰＵ
２０２ＲＡＭ
２０３ＲＯＭ
２０４システムバス
２０５入力コントローラ
２０６ビデオコントローラ
２０７メモリコントローラ
２０８通信Ｉ／Ｆ（インターフェース）コントローラ
２０９キーボード
２１０ディスプレイ装置
２１１外部メモリ

Claims

検索対象となる複数の第１のキーワードをデータとしてダブル配列へ登録する登録手段と、
前記登録手段で登録されたダブル配列のデータを用いて幅優先探索を行うための簡潔木構造に登録するためのデータを作成する作成手段と、
前記作成手段によって作成したデータを備えた簡潔木構造を記憶する記憶手段と、
前記複数の第１のキーワードを検索するための検索キーワードである第２のキーワードの入力を受け付ける受付手段と、
前記受付手段で受け付けた第２のキーワードが前記複数の第１のキーワードに含まれるか、を前記記憶手段によって記憶された前記簡潔木構造を用いて検索する検索手段と、
を備え、
前記作成手段は、前記ダブル配列のトライ構造を構成するノードに対するＴＡＩＬ配列へのリンクを前記簡潔木構造のノードに対する前記ＴＡＩＬ配列へのリンクとしてデータを作成し、
前記検索手段は、前記受付手段で受け付けた第２のキーワードの最初の文字を読み込み、前記簡潔木構造のルートノードを第１のノードに設定し、該第１のノードの子ノードに前記読み込んだ文字を示す子ノードがあるかを判定し、
前記読み込んだ文字を示す子ノードがあると判定した場合には、当該子ノードを第１のノードに設定し、前記第２のキーワードの次の１文字を読み込み、変更後の第１のノードに該読み込んだ１文字を示す子ノードが存在するかを判定する処理を繰り返し、
前記読み込んだ文字を示す子ノードがないと判定した場合には、前記子ノードから前記ＴＡＩＬ配列へのリンクを参照することで前記ＴＡＩＬ配列に遷移し、前記ＴＡＩＬ配列に残りの文字列が登録されているかを判定することにより、前記第２のキーワードが前記複数の第１のキーワードに含まれるかを検索すること
を備えることを特徴とする情報処理装置。
前記作成手段は、前記ダブル配列のトライ構造を構成するノードから遷移可能なノードに対するデータを、前記簡潔木構造のノードに登録することを特徴とする請求項１に記載の情報処理装置。
前記作成手段は、所定ノードから遷移可能なノードは、前記遷移可能なノードに対する前記ダブル配列を構成するＣＨＥＣＫ配列の値から求まる遷移元のノードが前記所定ノードとなることを特徴とする請求項２に記載の情報処理装置。
前記作成手段は、前記複数の第１のキーワード間で共通ではない接尾辞部を併合して前記ＴＡＩＬ配列として、作成することを特徴とする請求項１乃至３の何れか１項に記載の情報処理装置。
データの検索処理を行う情報処理装置によって行われる情報処理方法であって、
前記情報処理装置は、
検索対象となる複数の第１のキーワードをデータとしてダブル配列へ登録する登録工程と、
前記登録工程で登録されたダブル配列のデータを用いて幅優先探索を行うための簡潔木構造に登録するためのデータを作成する作成工程と、
前記作成工程によって作成したデータを備えた簡潔木構造を記憶する記憶工程と、
前記複数の第１のキーワードを検索するための検索キーワードである第２のキーワードの入力を受け付ける受付工程と、
前記受付工程で受け付けた第２のキーワードが前記複数の第１のキーワードに含まれるか、を前記記憶工程によって記憶された前記簡潔木構造を用いて検索する検索工程と、
を実行し、
前記作成工程は、前記ダブル配列のトライ構造を構成するノードに対するＴＡＩＬ配列へのリンクを前記簡潔木構造のノードに対する前記ＴＡＩＬ配列へのリンクとしてデータを作成し、
前記検索工程は、前記受付工程で受け付けた第２のキーワードの最初の文字を読み込み、前記簡潔木構造のルートノードを第１のノードに設定し、該第１のノードの子ノードに前記読み込んだ文字を示す子ノードがあるかを判定し、
前記読み込んだ文字を示す子ノードがあると判定した場合には、当該子ノードを第１のノードに設定し、前記第２のキーワードの次の１文字を読み込み、変更後の第１のノードに該読み込んだ１文字を示す子ノードが存在するかを判定する処理を繰り返し、
前記読み込んだ文字を示す子ノードがないと判定した場合には、前記子ノードから前記ＴＡＩＬ配列へのリンクを参照することで前記ＴＡＩＬ配列に遷移し、前記ＴＡＩＬ配列に残りの文字列が登録されているかを判定することにより、前記第２のキーワードが前記複数の第１のキーワードに含まれるかを検索すること
を実行することを特徴とする情報処理方法。
データの検索処理を行う情報処理装置において読取り実行可能なコンピュータプログラムであって、
前記情報処理装置を、
検索対象となる複数の第１のキーワードをデータとしてダブル配列へ登録する登録手段と、
前記登録手段で登録されたダブル配列のデータを用いて幅優先探索を行うための簡潔木構造に登録するためのデータを作成する作成手段と、
前記作成手段によって作成したデータを備えた簡潔木構造を記憶する記憶手段と、
前記複数の第１のキーワードを検索するための検索キーワードである第２のキーワードの入力を受け付ける受付手段と、
前記受付手段で受け付けた第２のキーワードが前記複数の第１のキーワードに含まれるか、を前記記憶手段によって記憶された前記簡潔木構造を用いて検索する検索手段と、
して機能させ、
前記作成手段は、前記ダブル配列のトライ構造を構成するノードに対するＴＡＩＬ配列へのリンクを前記簡潔木構造のノードに対する前記ＴＡＩＬ配列へのリンクとしてデータを作成し、
前記検索手段は、前記受付手段で受け付けた第２のキーワードの最初の文字を読み込み、前記簡潔木構造のルートノードを第１のノードに設定し、該第１のノードの子ノードに前記読み込んだ文字を示す子ノードがあるかを判定し、
前記読み込んだ文字を示す子ノードがあると判定した場合には、当該子ノードを第１のノードに設定し、前記第２のキーワードの次の１文字を読み込み、変更後の第１のノードに該読み込んだ１文字を示す子ノードが存在するかを判定する処理を繰り返し、
前記読み込んだ文字を示す子ノードがないと判定した場合には、前記子ノードから前記ＴＡＩＬ配列へのリンクを参照することで前記ＴＡＩＬ配列に遷移し、前記ＴＡＩＬ配列に残りの文字列が登録されているかを判定することにより、前記第２のキーワードが前記複数の第１のキーワードに含まれるかを検索すること
として機能させるためのコンピュータプログラム。