(57)【特許請求の範囲】
【請求項１】
被検索括弧列を示すビット列を複数のブロックに分割する分割手段と、
前記各ブロックの終端ビットの相対超過数を算出する終端相対超過数算出手段と、
前記各ブロックについて、当該ブロックの各ビットの相対超過数のうち最小の相対超過数である相対最小超過数を算出する相対最小超過数算出手段と、
前記各ブロックの終端ビットの相対超過数、及び相対最小超過数に基づき、所与の超過数を有するビットを含む前記ブロックを特定するブロック特定手段と、
特定される前記ブロックにおける前記所与の超過数を有するビットの位置を特定するビット位置特定手段と、を含み、
前記ビット位置特定手段は、特定される前記ブロックに含まれるビット列のうち先頭から所定数のビットに含まれる値１のビットの数と、前記所定数と、前記所与の超過数と、に基づいて、前記所与の超過数を有するビットの位置が前記所定数に対応する位置であるか否かを判定する、
情報処理システム。
【請求項２】
請求項１に記載の情報処理システムにおいて、
前記ビット位置特定手段は、前記値１のビットの数をｎ、前記所定数をｍ、前記所与の超過数をｌとしたときに、２×ｎ−ｍ＝ｌが成立するか否かを判定することにより、前記所与の超過数を有するビットの位置が前記所定数に対応する位置であるか否かを判定する、
情報処理システム。
【請求項３】
請求項１または２に記載の情報処理システムにおいて、
前記ビット位置特定手段は、前記所定数として第１の数を用いる前記判定と、前記所定数として前記第１の数とは異なる第２の数を用いる前記判定と、を並列に実行する、
情報処理システム。
【請求項４】
請求項１から３のいずれかに記載の情報処理システムにおいて、
前記ビット位置特定手段は、
特定される前記ブロックに含まれるビット列のうち、先頭から所定数のビットを元の値のまま残し、残りのビットの値を所定値に変更した仮ビット列を生成する手段と、
前記仮ビット列に含まれる値１のビットの数を示すビット列を取得する手段と、
取得される前記ビットの数を示すビット列を左ビットシフトする手段と、
左ビットシフトされた前記ビット列から、前記所定数を示すビット列を減算して、前記所定数のビットの超過数を示すビット列を取得する手段と、
前記所定数のビットの超過数を示すビット列と、前記所与の超過数と、に基づいて、特定される前記ブロックにおける前記所与の超過数のビットの位置が、前記所定数に対応する位置であると判定する手段と、を含む、
情報処理システム。
【請求項５】
請求項１から４のいずれかに記載の情報処理システムにおいて、
前記相対最小超過数算出手段は、
各ブロックに含まれる、第１サブブロックについて相対最小超過数及び相対終端超過数を算出するとともに、該第１サブブロックの終端に隣接する第２ブロックについて相対最小超過数を算出する手段と、
前記第１サブブロックについて算出される相対最小超過数を示す値と、前記第１サブブロックについて算出される相対終端超過数に前記第２サブブロックについて算出される前記相対最小超過数を示す値とを加算してなる値と、のうち、いずれか小さい方を、前記第１及び第２サブブロックに含まれるビット列を連結してなる連結ビット列の相対最小超過数として取得する手段と、
を含む情報処理システム。
【請求項６】
ビット列のうち先頭から所定数ｍのビットに含まれる値１のビットの数ｎと、前記所定数ｍと、所与の超過数ｌと、に基づいて、前記ビット列における前記所与の超過数を有するビットの位置が前記所定数に対応する位置であるか否かを判定するビット位置特定手段を含む、
情報処理システム。
【請求項７】
被検索括弧列を示すビット列を複数のブロックに分割する分割手段と、
前記各ブロックの終端ビットの相対超過数を算出する終端相対超過数算出手段と、
前記各ブロックについて、当該ブロックの各ビットの相対超過数のうち最小の相対超過数である相対最小超過数を算出する相対最小超過数算出手段と、
前記各ブロックの終端ビットの相対超過数、及び相対最小超過数に基づき、所与の超過数を有するビットを含む前記ブロックを特定するブロック特定手段と、
特定される前記ブロックにおける前記所与の超過数を有するビットの位置を特定するビット位置特定手段と、を含み、
前記ビット位置特定手段は、
特定される前記ブロックに含まれるビット列のうち先頭から所定数のビットを取得し、
前記取得された所定数のビットの終端における相対超過数を算出し、
前記算出された相対超過数と前記所与の超過数とに基づいて、前記所与の超過数を有するビットの位置が前記所定数に対応する位置であるか否かを判定する、
情報処理システム。
【請求項８】
分割手段が、被検索括弧列を示すビット列を複数のブロックに分割するステップと、
終端相対超過数算出手段が、前記各ブロックの終端ビットの相対超過数を算出するステップと、
相対最小超過数算出手段が、前記各ブロックについて、当該ブロックの各ビットの相対超過数のうち最小の相対超過数である相対最小超過数を算出するステップと、
ブロック特定手段が、前記各ブロックの終端ビットの相対超過数、及び相対最小超過数に基づき、所与の超過数を有するビットを含む前記ブロックを特定するステップと、
ビット位置特定手段が、特定される前記ブロックにおける前記所与の超過数を有するビットの位置を特定するステップと、を含み、
前記所与の超過数を有するビットの位置を特定するステップでは、前記ビット位置特定手段が、特定される前記ブロックに含まれるビット列のうち先頭から所定数のビットに含まれる値１のビットの数と、前記所定数と、前記所与の超過数と、に基づいて、前記所与の超過数を有するビットの位置が前記所定数に対応する位置であるか否かを判定する、
情報処理方法。
【請求項９】
分割手段が、被検索括弧列を示すビット列を複数のブロックに分割するステップと、
終端相対超過数算出手段が、前記各ブロックの終端ビットの相対超過数を算出するステップと、
相対最小超過数算出手段が、前記各ブロックについて、当該ブロックの各ビットの相対超過数のうち最小の相対超過数である相対最小超過数を算出するステップと、
ブロック特定手段が、前記各ブロックの終端ビットの相対超過数、及び相対最小超過数に基づき、所与の超過数を有するビットを含む前記ブロックを特定するステップと、
ビット位置特定手段が、特定される前記ブロックにおける前記所与の超過数を有するビットの位置を特定するステップと、を含み、
前記所与の超過数を有するビットの位置を特定するステップでは、前記ビット位置特定手段が、
特定される前記ブロックに含まれるビット列のうち先頭から所定数のビットを取得し、
前記取得された所定数のビットの終端における相対超過数を算出し、
前記算出された相対超過数と前記所与の超過数とに基づいて、前記所与の超過数を有するビットの位置が前記所定数に対応する位置であるか否かを判定する、
情報処理方法。
【請求項１０】
被検索括弧列を示すビット列を複数のブロックに分割する分割手段、
前記各ブロックの終端ビットの相対超過数を算出する終端相対超過数算出手段、
前記各ブロックについて、当該ブロックの各ビットの相対超過数のうち最小の相対超過数である相対最小超過数を算出する相対最小超過数算出手段、
前記各ブロックの終端ビットの相対超過数、及び相対最小超過数に基づき、所与の超過数を有するビットを含む前記ブロックを特定するブロック特定手段、および
特定される前記ブロックにおける前記所与の超過数を有するビットの位置を特定するビット位置特定手段、としてコンピュータを機能させ、
前記ビット位置特定手段は、特定される前記ブロックに含まれるビット列のうち先頭から所定数のビットに含まれる値１のビットの数と、前記所定数と、前記所与の超過数と、に基づいて、前記所与の超過数を有するビットの位置が前記所定数に対応する位置であるか否かを判定する、
プログラム。
【請求項１１】
被検索括弧列を示すビット列を複数のブロックに分割する分割手段、
前記各ブロックの終端ビットの相対超過数を算出する終端相対超過数算出手段、
前記各ブロックについて、当該ブロックの各ビットの相対超過数のうち最小の相対超過数である相対最小超過数を算出する相対最小超過数算出手段、
前記各ブロックの終端ビットの相対超過数、及び相対最小超過数に基づき、所与の超過数を有するビットを含む前記ブロックを特定するブロック特定手段、および、
特定される前記ブロックにおける前記所与の超過数を有するビットの位置を特定するビット位置特定手段、としてコンピュータを機能させ、
前記ビット位置特定手段は、
特定される前記ブロックに含まれるビット列のうち先頭から所定数のビットを取得し、
前記取得された所定数のビットの終端における相対超過数を算出し、
前記算出された相対超過数と前記所与の超過数とに基づいて、前記所与の超過数を有するビットの位置が前記所定数に対応する位置であるか否かを判定する、
プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報処理システム、情報処理方法およびプログラムに関する。
【背景技術】
【０００２】
ＸＭＬ（Extensible Markup Language）、ＪＳＯＮ（JavaScript Object Notation）などの半構造テキストフォーマット（semi-structured textual format）で記載されたデータが利用されている。半構造テキストフォーマットで記載されたデータのインデックスとして、ＢＰ（balanced parentheses）表現のビット列からなる括弧木データを用いる手法が存在する。この手法では、そのビット列内で求める超過数を有するビットの位置を求めることにより、データの適切な位置を検索する。非特許文献１には、半構造テキストデータをＢＰ表現のビット列として扱う手法が開示されている。【０００３】
この手法における検索の際には、ビット列が分割された複数のブロックの最小超過数などを用いてブロックを検索し、その後でブロック内で求める超過数を有するビットの位置を求めている。ブロック内の検索条件を満たすビットの位置を先頭のビットから順にチェックするアルゴリズムでは処理時間がかかる。非特許文献２にはブロックのビット列と超過数との組み合わせを検索キーとして予め生成されているルックアップテーブルを検索することでより高速にビットの位置を特定することが記載されている。
【先行技術文献】
【特許文献】
【０００４】
【非特許文献１】G. Ottaviano, R. Grossi, “Semi-indexing Semi-structured Data in Tiny Space”, Proceedings of the 20th ACM International Conference on Information and Knowledge Management (CIKM 2011), pp. 1485-1494, 2011.
【非特許文献２】G. Ottaviano, R. Grossi, “Fast Compressed Tries through Path Decompositions”, Proceedings of the 14th Meeting on Algorithm Engineering Experiments (ALENEX 2012), pp. 65-74, 2012.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ルックアップテーブルを用いてビットの位置を特定する処理を行うと、ルックアップテーブルのメモリの使用量が多くなってしまう。そのため、例えばプロセッサのキャッシュメモリを有効に利用できないなどの問題が生じやすい。【０００６】
本発明は上記課題を鑑みてなされたものであって、その目的は、複数のブロックを含む括弧木データのビット列から、検索条件を満たすビット位置を検索する際のメモリ使用量を削減することができる情報処理システム、情報処理方法およびプログラムを提供することにある。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、本発明にかかる情報処理システムは、被検索括弧列を示すビット列を複数のブロックに分割する分割手段と、前記各ブロックの終端ビットの相対超過数を算出する終端相対超過数算出手段と、前記各ブロックについて、当該ブロックの各ビットの相対超過数のうち最小の相対超過数である相対最小超過数を算出する相対最小超過数算出手段と、前記各ブロックの終端ビットの相対超過数、及び相対最小超過数に基づき、所与の超過数を有するビットを含む前記ブロックを特定するブロック特定手段と、特定される前記ブロックおける前記所与の超過数を有するビットの位置を特定するビット位置特定手段と、を含み、前記ビット位置特定手段は、特定される前記ブロックに含まれるビット列のうち先頭から所定数のビットに含まれる値１のビットの数と、前記所定数と、前記所与の超過数と、に基づいて、前記所与の超過数を有するビットの位置が前記所定数に対応する位置であるか否かを判定する。【０００８】
また、本発明にかかる情報処理方法は、被検索括弧列を示すビット列を複数のブロックに分割するステップと、前記各ブロックの終端ビットの相対超過数を算出するステップと、前記各ブロックについて、当該ブロックの各ビットの相対超過数のうち最小の相対超過数である相対最小超過数を算出するステップと、前記各ブロックの終端ビットの相対超過数、及び相対最小超過数に基づき、所与の超過数を有するビットを含む前記ブロックを特定するステップと、特定される前記ブロックおける前記所与の超過数を有するビットの位置を特定するステップと、を含み、前記所与の超過数を有するビットの位置を特定するステップでは、特定される前記ブロックに含まれるビット列のうち先頭から所定数のビットに含まれる値１のビットの数と、前記所定数と、前記所与の超過数と、に基づいて、前記所与の超過数を有するビットの位置が前記所定数に対応する位置であるか否かを判定する。【０００９】
また、本発明にかかるプログラムは、被検索括弧列を示すビット列を複数のブロックに分割する分割手段、前記各ブロックの終端ビットの相対超過数を算出する終端相対超過数算出手段、前記各ブロックについて、当該ブロックの各ビットの相対超過数のうち最小の相対超過数である相対最小超過数を算出する相対最小超過数算出手段、前記各ブロックの終端ビットの相対超過数、及び相対最小超過数に基づき、所与の超過数を有するビットを含む前記ブロックを特定するブロック特定手段、および、特定される前記ブロックおける前記所与の超過数を有するビットの位置を特定するビット位置特定手段、としてコンピュータを機能させ、前記ビット位置特定手段は、特定される前記ブロックに含まれるビット列のうち先頭から所定数のビットに含まれる値１のビットの数と、前記所定数と、前記所与の超過数と、に基づいて、前記所与の超過数を有するビットの位置が前記所定数に対応する位置であるか否かを判定する。【００１０】
また、本発明にかかるもう１つの情報処理システムは、被検索括弧列を示すビット列を複数のブロックに分割する分割手段と、前記各ブロックの終端ビットの相対超過数を算出する終端相対超過数算出手段と、前記各ブロックについて、当該ブロックの各ビットの相対超過数のうち最小の相対超過数である相対最小超過数を算出する相対最小超過数算出手段と、前記各ブロックの終端ビットの相対超過数、及び相対最小超過数に基づき、所与の超過数を有するビットを含む前記ブロックを特定するブロック特定手段と、特定される前記ブロックおける前記所与の超過数を有するビットの位置を特定するビット位置特定手段と、を含み、前記ビット位置特定手段は、特定される前記ブロックに含まれるビット列のうち先頭から所定数の上位ビットを取得し、前記取得された所定数のビットの終端における相対超過数を算出し、前記算出された相対超過数と前記所与の超過数とに基づいて、前記所与の超過数を有するビットの位置が前記所定数に対応する位置であるか否かを判定する。【００１１】
また、本発明にかかるもう１つの情報処理方法は、被検索括弧列を示すビット列を複数のブロックに分割するステップと、前記各ブロックの終端ビットの相対超過数を算出するステップと、前記各ブロックについて、当該ブロックの各ビットの相対超過数のうち最小の相対超過数である相対最小超過数を算出するステップと、前記各ブロックの終端ビットの相対超過数、及び相対最小超過数に基づき、所与の超過数を有するビットを含む前記ブロックを特定するステップと、特定される前記ブロックおける前記所与の超過数を有するビットの位置を特定するステップと、を含み、前記所与の超過数を有するビットの位置を特定するステップでは、特定される前記ブロックに含まれるビット列のうち先頭から所定数のビットを取得し、前記取得された所定数のビットの終端における相対超過数を算出し、前記算出された相対超過数と前記所与の超過数とに基づいて、前記所与の超過数を有するビットの位置が前記所定数に対応する位置であるか否かを判定する。【００１２】
また、本発明にかかるもう１つのプログラムは、被検索括弧列を示すビット列を複数のブロックに分割する分割手段、前記各ブロックの終端ビットの相対超過数を算出する終端相対超過数算出手段、前記各ブロックについて、当該ブロックの各ビットの相対超過数のうち最小の相対超過数である相対最小超過数を算出する相対最小超過数算出手段、前記各ブロックの終端ビットの相対超過数、及び相対最小超過数に基づき、所与の超過数を有するビットを含む前記ブロックを特定するブロック特定手段、および、特定される前記ブロックおける前記所与の超過数を有するビットの位置を特定するビット位置特定手段、としてコンピュータを機能させ、前記ビット位置特定手段は、特定される前記ブロックに含まれるビット列のうち先頭から所定数のビットを取得し、前記取得された所定数のビットの終端における相対超過数を算出し、前記算出された相対超過数と前記所与の超過数とに基づいて、前記所与の超過数を有するビットの位置が前記所定数に対応する位置であるか否かを判定する。【００１３】
本発明によれば、複数のブロックを含む括弧木データのビット列から、検索条件を満たすビット位置を検索する際のメモリ使用量を削減することができる。【００１４】
本発明の一態様では、前記ビット位置特定手段は、前記値１のビットの数をｎ、前記所定数をｍ、前記所与の超過数をｌとしたときに、２×ｎ−ｍ＝ｌが成立するか否かを判定することにより、前記所与の超過数を有するビットの位置が前記所定数に対応する位置であるか否かを判定してもよい。【００１５】
本発明の一態様では、前記ビット位置特定手段は、前記所定数として第１の数を用いる前記判定と、前記所定数として前記第１の数とは異なる第２の数を用いる前記判定と、を並列に実行してもよい。【００１６】
本発明の一態様では、前記ビット位置特定手段は、特定される前記ブロックに含まれるビット列のうち、先頭から所定数のビットを元の値のまま残し、残りのビットの値を所定値に変更した仮ビット列を生成する手段と、前記仮ビット列に含まれる値１のビットの数を示すビット列を取得する手段と、取得される前記ビットの数を示すビット列を左ビットシフトする手段と、左ビットシフトされた前記ビット列から、前記所定数を示すビット列を減算して、前記所定数の上位ビットの超過数を示すビット列を取得する手段と、前記所定数の上位ビットの超過数を示すビット列と、前記所与の超過数と、に基づいて、特定される前記ブロックにおける前記所与の超過数のビットの位置が、前記所定数に対応する位置であると判定する手段と、を含んでもよい。【００１７】
本発明の一態様では、前記相対最小超過数算出手段は、各ブロックに含まれる、第１サブブロックについて相対最小超過数及び相対終端超過数を算出するとともに、該第１サブブロックの終端に隣接する第２ブロックについて相対最小超過数を算出する手段と、前記第１サブブロックについて算出される相対最小超過数を示す値と、前記第１サブブロックについて算出される相対終端超過数に前記第２サブブロックについて算出される前記相対最小超過数を示す値とを加算してなる値と、のうち、いずれか小さい方を、前記第１及び第２サブブロックに含まれるビット列を連結してなる連結ビット列の相対最小超過数として取得する手段と、を含んでもよい。
【図面の簡単な説明】
【００１８】
【図１】本発明の実施形態にかかる情報処理システムの一例を示す図である。
【図２】情報処理サーバおよびクライアント装置のハードウェア構成の一例を示す図である。
【図３】情報処理システムが実現する機能を示すブロック図である。
【図４】半構造テキストデータの一例を示す図である。
【図５】半構造テキストデータが示す木構造の一例を示す図である。
【図６】生成されたＢＰ表現のビット列データの一例を示す図である。
【図７】生成されるビット位置関連データの一例を示す図である。次のノードを検索するための超過数の検索の一例を示す図である。
【図８】インデックス生成部の処理において生成されるデータの関連を示す図である。
【図９】インデックス生成部が相対最小超過数を算出する過程の一例を説明する図である。
【図１０】複数のビットグループを加算する加算ユニットの一例を示す回路図である。
【図１１】ブロック特定部の処理において生成されるデータの関連を示す図である。
【図１２】ビット位置特定部の処理において生成されるデータの関連を示す図である。
【図１３】ビット位置特定部がビット位置を検索する過程の一例を説明する図である。
【図１４】情報処理システムの処理の概要を示すフロー図である。
【発明を実施するための形態】
【００１９】
以下では、本発明の実施形態について図面に基づいて説明する。出現する構成要素のうち同一機能を有するものには同じ符号を付し、その説明を省略する。以下では主に、ＸＭＬなどの半構造テキストフォーマットのデータとそのインデックスを配信し、受信側でそのデータを処理するシステムを説明する。
【００２０】
図１は、本発明の実施形態にかかる情報処理システムの一例を示す図である。本発明の実施形態にかかる情報処理システムは、情報処理サーバ１およびクライアント装置２を含む。情報処理サーバ１はサーバコンピュータであり、クライアント装置２は例えばパーソナルコンピュータや携帯情報端末（タブレット、電子書籍端末など）である。
【００２１】
図２は、情報処理サーバ１およびクライアント装置２のハードウェア構成の一例を示す図である。情報処理サーバ１およびクライアント装置２のそれぞれは、プロセッサ１１、記憶部１２、通信部１３、入出力部１４、バス１５を含む。
【００２２】
プロセッサ１１は、記憶部１２に格納されているプログラムに従って動作する。またプロセッサ１１は通信部１３、入出力部１４を制御する。なお、上記プログラムは、インターネット等を介して提供されるものであってもよいし、フラッシュメモリやＤＶＤ−ＲＯＭ等のコンピュータで読み取り可能な記憶媒体に格納されて提供されるものであってもよい。
【００２３】
記憶部１２は、ＲＡＭやフラッシュメモリ等のメモリ素子やハードディスクドライブによって構成されている。記憶部１２は、上記プログラムを格納する。また、記憶部１２は、各部から入力される情報や演算結果を格納する。
【００２４】
通信部１３は、他の装置と通信する機能を実現するものであり、例えば有線ＬＡＮの集積回路やコネクタ端子、無線ＬＡＮの集積回路やアンテナなどにより構成されている。通信部１３は、プロセッサ１１の制御に基づいて、他の装置から受信した情報をプロセッサ１１や記憶部１２に入力し、他の装置に情報を送信する。
【００２５】
入出力部１４は、表示出力手段をコントロールするビデオコントローラや、入力デバイスからのデータを取得するコントローラなどにより構成される。入力デバイスとしては、キーボード、マウス、タッチパネルなどがある。入出力部１４は、プロセッサ１１の制御に基づいて、表示出力デバイスに表示データを出力し、入力デバイスをユーザが操作することにより入力されるデータを取得する。表示出力デバイスは例えば外部に接続されるディスプレイ装置やクライアント装置２に内蔵されるディスプレイパネルである。
【００２６】
バス１５は、プロセッサ１１と記憶部１２と通信部１３と入出力部１４とを接続し、バス１５はそれらの間でデータを含む信号を伝送する。バス１５には、以下で説明する処理を実行する演算ユニットが接続されていてもよい。
【００２７】
図３は、情報処理システムが実現する機能を示すブロック図である。情報処理システムは、機能的に、括弧木データ生成部５１、インデックス生成部５２、データ送信部５３、データ受信部６１、クエリ取得部６２、ブロック特定部６３、ビット位置特定部６４、クエリ結果出力部６５を含む。またインデックス生成部５２は、機能的に、終端超過数算出部５４、最小超過数算出部５５、最大超過数算出部５６を含む。本実施形態では、括弧木データ生成部５１、インデックス生成部５２、データ送信部５３は情報処理サーバ１に含まれるプロセッサ１１が記憶部１２に格納されるプログラムを実行し、通信部１３や入出力部１４を制御することで実現される。データ受信部６１、クエリ取得部６２、ブロック特定部６３、ビット位置特定部６４、クエリ結果出力部６５はクライアント装置２に含まれるプロセッサ１１が記憶部１２に格納されるプログラムを実行し、通信部１３や入出力部１４を制御することで実現される。なお、クエリ取得部６２、ブロック特定部６３、ビット位置特定部６４、クエリ結果出力部６５は、情報処理サーバ１に含まれるプロセッサ１１等より実現されてもよい。また、情報処理サーバ１およびクライアント装置２の少なくとも一方に専用のハードウェアである演算ユニットを装備し、その演算ユニットとプロセッサ１１とが連携することで上記機能の一部または全部を実現してもよい。
【００２８】
図１４は、情報処理システムの処理の概要を示すフロー図である。図１４に示す処理のうち一部は並列的に処理されてもよい。例えばステップＳ９２とステップＳ９３は、実際には並列的に処理されてよい。また例えばステップＳ９７以降の処理は実際には検索条件が与えられるごとに繰返し実行される。
【００２９】
括弧木データ生成部５１は、プロセッサ１１および記憶部１２を中心として実現される。括弧木データ生成部５１は、半構造テキストフォーマットのテキストデータからＢＰ表現のビット列を含む括弧木データと、括弧木データのビット位置とテキストデータの位置との関係を示すビット位置関連データとを生成する（ステップＳ９１）。ここで、括弧木データ生成部５１は括弧木データとして、生成されたビット列が複数のブロックに分割されたデータを記憶部１２に格納する。
【００３０】
図４は、半構造テキストデータの一例を示す図である。図４に示す半構造テキストデータは、ＪＳＯＮ形式のデータであり、ブログのように複数の記事を含むデータである。このデータはある日付において投稿された２つの記事を示している。半構造テキストデータは、一般的に複数のノードを含む木構造と対応することが知られている。半構造テキストデータでは、複数のノードのそれぞれは半構造テキストデータのうちそれぞれの始点から終点までの文字列により表される。例えば、この始点や終点がシンボル（図４の例ではそれぞれ「｛」と「｝」）により表されてもよいし、ほかの何らかの構文上の規則によって始点と終点が示されていてもよい。また、あるノードの文字列の中に、そのノードの子ノードの文字列が入れ子構造で含まれていてもよい。また子ノードの文字列に孫ノードなどのさらに下位のノードの文字列が含まれていてもよい。図４における丸付き数字および破線は半構造テキストデータを説明するための符号および線であり、丸付き数字は破線を介して接続される括弧の位置に対応するノードの番号を示している。
【００３１】
図５は半構造テキストデータが示す木構造の一例を示す図である。図５は、図４に示す半構造テキストデータに対応する木構造を示している。番号０のノードは最上位のノードであり、その子ノードは番号１および４のノードである。また番号１のノードの子ノードは番号２および３のノードである。番号４のノードの子ノードは番号５および７のノードであり、番号５の子ノードは番号６のノードである。
【００３２】
図６は括弧木データ生成部５１が生成した複数のブロックに分割されたＢＰ表現のビット列と、ノード、ブロックとの関係の一例を示す図である。図６のビット列は括弧木データ生成部５１により生成されるデータであり、図６のノード番号、ビット位置、括弧木表現、超過数の記載はそのビット列を説明するためのものである。
【００３３】
図６に示すビット列は、図４に示す半構造テキストデータから生成される。括弧木表現の行の「（」「）」（以下では単に「括弧」と記載した場合、この括弧木表現の括弧を示す）はそれぞれ図４の半構造テキストデータの各ノードの始点と終点を示す。したがって、ビット列の「１」「０」はそれぞれ対応するノードの始点、終点を表す。なお図６ではビット位置は１から始まる番号としている。一方、本実施形態では１ブロックは８ビットとし、ブロック番号は０から始まる番号としている。１ブロックに含まれるビットの数は８でなくてもよいが２のべき乗が好適である。以下では、ブロックのビットの数をブロック長と記載する。また、他のデータにおいてブロックと記載する場合、そのブロック長はビット列におけるブロックと等しいとする。
【００３４】
図６のＢＰ表現における開き括弧とその開き括弧に対応する閉じ括弧とはノードを示している。図６のノード番号はそのビット位置を始点とするするノードの番号を示し、このノード番号は図５の木構造のノード番号に対応する。超過数は、先頭からこのビット位置までの間にあるビット「１」の数からビット「０」の数を引いた数であり、木構造のノードの深さを示す数である。
【００３５】
ここで、図６に示すビット列では左から右にビット位置が大きくなっているが、記憶部１２のメモリやプロセッサ１１のレジスタに格納される物理的なブロックのデータでは、ビット位置の番号が大きくなるにつれてメモリやレジスタの上位の桁のビットに順に配置されるようにビットが配置されている。図６に示すビット列でいえば、右になるほどメモリやレジスタの上位の桁に格納される。
【００３６】
図７は、生成されるビット位置関連データの一例を示す図である。ビット位置関連データは、括弧木データのビット列のビット位置と、そのビット位置に対応するノードの文字列とを関連づけるデータである。図７に示すビット位置関連データは、ビット位置と、半構造テキストデータにおけるノードの開始位置とを含み、ビット位置とノード文字列とを関連づけている。ビット位置関連データは、ビット位置と、ノード文字列そのものとを含んでもよい。
【００３７】
この括弧木データとビット位置関連データとにより、半構造テキストデータから各ノードのデータを特定して取得することが可能となる。例えばいずれかのノード（例えばカレントノード）の始点の開き括弧に対応する閉じ括弧を検索する際には、そのノードの始点の位置の超過数に基づく検索条件を与え、ビット列からその検索条件を満たす超過数のビットを取得することができる。より具体的には、図６においてカレントノードである番号５のノードの始点のビット位置である９と、超過数３とがわかっている場合、そのノードの終点は、以下の条件を満たすビット位置から検索することができる。条件は、ビットの超過数が始点より１小さい２となるビット位置のうち、９より大きい条件を満たす最小のものである。図６の例では、この条件を満たすビット位置１２が終点として検索される。またその次のビット位置は、「（」を示す１であれば同位のノードの開始位置を示し、「）」を示す０であれば上位のノードの終了の位置を示す。このようにして、あるビット位置から指定の超過数を有し最も近いビットのビット位置を検索することで、木構造のノードの関係を追うことが可能となることが知られている。
【００３８】
ここで、括弧木データ生成部５１がＢＰ表現のビット列を生成し、ビット列をブロックに分割する処理やビット位置関連データを生成する具体的なアルゴリズムは周知であり、非特許文献１等にも記載されているので説明を省略する。
【００３９】
次に、この検索条件を満たすビット位置を高速に検索するためのインデックスを求める処理について説明する。
【００４０】
インデックス生成部５２は、プロセッサ１１および記憶部１２を中心として実現される。インデックス生成部５２は、超過数の条件を満たすビット位置を高速に検索する際に用いるインデックスのデータを生成する。このインデックスは、例えば、ブロックごとの絶対終端超過数（global excess at the boundary）、絶対最小超過数（global minimum excess）、絶対最大超過数（global maximum excess）である。インデックス生成部５２に含まれる終端超過数生成部５４は複数のブロックの相対終端超過数（local excess at the boundary）を算出し（ステップＳ９２）、相対終端超過数から絶対終端超過数を算出し記憶部１２に格納する（ステップＳ９４）。インデックス生成部５２に含まれる最小超過数算出部５５は複数のブロックの相対最小超過数（local minimum excess）を算出し（ステップＳ９３）、相対最小超過数から絶対最小超過数を算出して記憶部１２に格納する（ステップＳ９４）。インデックス生成部５２に含まれる最大超過数算出部５６は複数のブロックの相対最大超過数（local maximum excess）を算出し（ステップＳ９３）、相対最大超過数から絶対最大超過数を算出し記憶部１２に格納する（ステップＳ９４）。
【００４１】
ここで、相対終端超過数などにおける「相対」とは、原則としてブロックの開始位置（ブロックの開始ビットの直前）における超過数を基準（０）とした場合の相対的な超過数であることを意味している。従って、相対終端超過数は、ブロックの最終ビットにおける相対的な超過数であり、相対最小超過数は、ブロック内の複数のビットの相対的な超過数のうち最小のものであり、相対最大超過数は、ブロック内の複数のビットの相対的な超過数のうち最大のものである。一方、括弧木データのビット列全体の開始位置を基準とした超過数を絶対超過数と表現する。絶対終端超過数は、ブロックの最終ビットにおける超過数であり、絶対最小超過数は、ブロック内の複数のビットの超過数のうち最小のものであり、絶対最大超過数は、ブロック内の複数のビットの超過数のうち最大の超過数である。
【００４２】
図８は、インデックス生成部５２の処理において生成されるデータの関連を示す図である。インデックス生成部５２は、記憶部１２から所定の数（図８の例では８）のブロックを並べたビットベクトルＩＢを一度に取得し、そのビットベクトルＩＢに含まれるブロックのそれぞれについて同じ演算をすることで相対終端超過数、相対最小超過数、相対最大超過数をまとめて算出し、さらに絶対終端超過数、絶対最小超過数、絶対最大超過数をまとめて算出する。
【００４３】
ビットベクトルＩＢが含むビットの数は、プロセッサ１１のレジスタ長や演算単位のビットの数（以下ではこの数を「処理単位長」と記載する）と同じである。本実施形態ではビットベクトルＩＢのビットの数は６４ビットであり、そのビットベクトルＩＢは８つの８ビットのブロックが並べられたデータである。ビットベクトルＩＢの下位（右側）から順にブロック番号が大きくなるようにブロックが配置される。これは、見方を変えれば、括弧木データのビット列のうち処理単位長に相当する複数のブロックのビット列をビットベクトルＩＢに格納することに相当する。
【００４４】
インデックス生成部５２の処理についてさらに説明する。以下では特に処理単位長が６４、ブロックのビット数が８の場合について説明する。インデックス生成部５２に含まれる終端超過数算出部５４は、ビットベクトルＩＢからデータＮ２を生成する処理１０２と、データＮ２からデータＮ４を生成する処理１０４と、データＮ４からデータＮ８を生成する処理１０６とを行う。
【００４５】
データＮ２，Ｎ４，Ｎ８は、処理単位長（ここでは６４ビット）のデータであり、８つのブロックを含む。データＮ２は３２個（ブロックにつき４個）の２ビットのサブブロックを含み、データＮ４は１６個（ブロックにつき２個）の４ビットのサブブロックを含む。データＮ２，Ｎ４，Ｎ８のそれぞれは、サブブロックに対応するビットベクトルＩＢのうビット列における値が１のビットの数をそのサブブロックに保持する。
【００４６】
終端超過数算出部５４は処理１０２において、ビットベクトルＩＢの隣り合う２つのビットの１のビットの数の値を、データＮ２の対応するサブブロックに格納する。この隣り合う２つのビットのビット位置は、データＮ２の対応するサブブロックのビット位置と同じである。終端超過数算出部５４は処理１０４において、データＮ２の隣り合う２つのサブブロックの１のビットの数の値を加算し、その加算された値を対応するデータＮ４の４ビットのサブブロックに格納する。データＮ２における２つのサブブロックの位置は、データＮ４における対応する４ビットのサブブロックの位置と同じである。また終端超過数算出部５４は処理１０６において、データＮ８のブロックに対応する位置のデータＮ４の隣り合う２つの４ビットのサブブロックの１のビットの数の値を加算し、その加算された値を、データＮ８のブロックのうち、その２つのサブブロックに相当する位置のブロックに格納する。
【００４７】
次に、インデックス生成部５２等が行う具体的な処理を式を用いて説明する。以下では、「＆」、「｜」、「〜」、「＜＜」、「＞＞」、「＊」は、それぞれ論理積のビット演算、論理和のビット演算、ＮＯＴ演算、左シフト演算、右シフト演算、乗算をすることを示す。一般的にプロセッサ１１はこれらの演算と加算、減算、排他的論理和（ＸＯＲ）のビット演算を最小のクロックで実行する。また式において文字に上付き線がある場合、その文字のデータをＮＯＴ演算することを示す。
【００４８】
また「−ｋ」は、ｋビットのサブブロックごとに減算することを示し、「＋ｋ」はｋビットのサブブロックごとに加算をすることを示し、「≦ｋ」はｋビットのサブブロックごとに比較し、その結果を示す１または０の値をサブブロックの最下位ビットに格納することを示す。汎用的なプロセッサ１１がプログラムを実行することで「−ｋ」、「＋ｋ」、「≦ｋ」の演算をする処理は以下の式で表される。
【００４９】
【数１】
0005752337.tif 000002
【００５０】
なお、「Ｈｋ」は、処理単位のビット数のデータに含まれるｋビットのサブブロックのそれぞれについて、最も上位のビットが１となり、他のビットが０となる処理単位のビット列を示している。また、「Ｌｋ」は、処理単位のビット数のデータに含まれるｋビットのサブブロックのそれぞれについて、最も下位のビットが１となり、他のビットが０となる処理単位のビット列を示している。例えばＨ４は２進数で「１０００１０００・・・１０００１０００」であり、Ｌ４は２進数で「０００１０００１・・・０００１０００１」である。
【００５１】
終端超過数算出部５４がプログラムを実行することでデータＮ２，Ｎ４，Ｎ８を生成する処理は以下の式で表される。
【００５２】
【数２】
0005752337.tif 000003
【００５３】
数式（１）は処理１０２を、数式（２）は処理１０４を、数式（３）は処理１０６を表している。式（１）の矢印の右側のｘはビットベクトルＩＢを、左側のｘはデータＮ２を示す。式（２）の矢印の右側のｘはデータＮ２を、左側のｘはデータＮ４を示す。式（３）の矢印の右側のｘはデータＮ４を、左側のｘはデータＮ８を示す。式（１）から（３）のｘの値は計算の際には原則としてプロセッサ１１内のレジスタに格納される。「μｋ」（ｋは０、１、２のいずれか）は以下の式で表される定数を示す。「μｋ」は処理単位長のデータでありパラメータｋに応じた値である。処理の際には予め算出された定数として扱われる。
【００５４】
【数３】
0005752337.tif 000004
【００５５】
ここで「＼」は整数値の割り算を示し、ｗは処理単位のビット数を示す。μ０は２進数で表すと“０１０１０１０１・・・０１０１０１０１”となる。μ１は２進数で表すと“００１１００１１・・・００１１００１１”となり、μ２は２進数で表すと“００００１１１１・・・００００１１１１”となる。
【００５６】
ブロックまたはサブブロックの終端における相対的な超過数である相対終端超過数は、データＮ２、データＮ４、データＮ８から計算することができる。データＮ８のブロックの１のビットの数を２倍したものからそのブロックのビットの総数である８を引くと、相対終端超過数となる。同様に、２または４ビットのサブブロックの１のビットの数の値の２倍から２または４を引いた数は２または４ビットのサブブロックの相対終端超過数となる。このように、１のビットの数は、相対終端超過数との対応がある値でもある。
【００５７】
また終端超過数算出部５４は、データＮ８からデータＧＢ８を生成する処理１０７を行う。終端超過数算出部５４は、データＮ８に含まれる各ブロックの相対終端超過数に前のブロックの絶対終端超過数を加算することでそのブロックの絶対終端超過数を求め、データＧＢ８の対応するブロックに絶対終端超過数を格納する。
【００５８】
インデックス生成部５２に含まれる最小超過数算出部５５は、ビットベクトルＩＢからデータＬＭ２を算出する処理１０１と、データＬＭ２とデータＮ２とからデータＬＭ４を算出する処理１０３と、データＬＭ４とデータＮ４とからデータＬＭ８を生成する処理１０５と、データＬＭ８とデータＧＢ８とからデータＧＭ８を生成する処理１０８とを実行する。
【００５９】
データＬＭ２，ＬＭ４，ＬＭ８，ＧＭ８は処理単位長のデータであり、それぞれ８つのブロックを含む。データＬＭ２は３２個（ブロックにつき４個）の２ビットのサブブロックを含み、データＬＭ４は１６個（ブロックにつき２個）の４ビットのサブブロックを含む。データＬＭ２，ＬＭ４のサブブロックには、そのサブブロックの位置に相当するビットベクトルＩＢのビット列の相対最小超過数の値が格納される。データＬＭ８およびＧＭ８に含まれるブロックには、それぞれ、その位置に対応するビットベクトルＩＢのブロックにおける相対最小超過数の値および絶対最小超過数の値が格納されている。データＬＭ２，ＬＭ４，ＬＭ８，ＧＭ８は処理単位長の記憶部１２のメモリまたはレジスタに格納される。
【００６０】
図９は、インデックス生成部５２が相対最小超過数を算出する過程の一例を説明する図である。図９は、図６に示すビット列を最小超過数算出部５５が処理する過程を示している。図９では、説明を容易にするためにビット列は１６ビットのみ記載しているが、本実施形態の実際の計算では６４ビットの処理単位で演算している。また前述したように括弧木データのビット列はレジスタやメモリの最下位ビットから上位ビットに向かってビット列のビットが配置されている。一方、図９ではビット列が左から右に向かって配置されている。このため、図９のビット列や数値については左側が下位のビットのものとなる。以下では図８に示す処理の詳細とともに図９を説明する。
【００６１】
以下では最小超過数算出部５５がデータＬＭ２，ＬＭ４，ＬＭ８，ＧＭ８を算出する処理について説明する。
【００６２】
最小超過数算出部５５がビットベクトルＩＢからデータＬＭ２（データＺ）を算出する処理１０１は、以下の式（４）により表される。
【００６３】
【数４】
0005752337.tif 000005
【００６４】
式（４）は括弧木データのビット列から２ビットのサブブロックにおける相対最小超過数を算出する処理であり、ｘはビットベクトルＩＢである。図９の例では、算出されたデータＺは、２行目の相対最小超過数に相当する。
【００６５】
また最小超過数算出部５５がデータＬＭ２からデータＬＭ４を算出する処理１０３や、
データＬＭ４からデータＬＭ８を算出する処理１０５は、以下の数式（５）から（８）により表される。
【００６６】
【数５】
0005752337.tif 000006
【００６７】
ここで、ｌはパラメータであり、処理対象となるデータに含まれるサブブロックのビット数である。ｌの値はデータＬＭ２からデータＬＭ４を算出する場合は２、データＬＭ４からデータＬＭ８を算出する場合は４である。データＺは相対超過数を示すものであり、データＬＭ２またはデータＬＭ４のうちパラメータｌにおいて入力されるものである。「ｅｘｔｅｎｄ２ｌ」は、２ｌビットのサブブロックごとに、その下位ｌビットに格納されている値を２ｌビットの値に変換する演算を示す。より具体的には、「ｅｘｔｅｎｄ２ｌ」は、上位ｌビットに、下位からｌビット目の値をコピーする演算を示す。この演算は、負の値を正しく表現するための演算である。また「Ｃｌ」はｌビットの複数のサブブロックを含む処理単位のビットの値であり、データＮ２またはデータＮ４を表す。
【００６８】
式（５）は、最小超過数算出部５５が２ｌビットに相当するデータＺの２ｌビットのうち、下位ｌビットのサブブロックの値を相対最小超過数（下位）のデータＬに含まれる対応する２ｌビットに格納する処理を示している。これは図９において２行目にあり隣り合う２つの相対最小超過数のうち下位側を相対最小超過数（下位）に格納する矢印に相当する。
【００６９】
式（６）は、最小超過数算出部５５が２ｌビットに対応するデータＺの２ｌビットのうち、上位ｌビットのサブブロックの値を相対最小超過数（上位）のデータＬに含まれる対応する２ｌビットに格納する処理を示している。
【００７０】
式（７）は、最小超過数算出部５５が２ｌビットに相当するデータＣｌを２ｌビットごとに分割した場合の下位の（ビット列の先頭側の）ｌビットの終端における相対終端超過数（下位）Ｓを算出する処理を示している。図９には相対終端超過数（下位）Ｓの例が記載されている。
【００７１】
式（８）は、最小超過数算出部５５が、下位ｌビットの先頭を基準とした場合の上位ｌビットの相対最小超過数を示すデータである「Ｓ＋２ｌＵ」を算出し、下位ｌビットの相対最小超過数Ｌと、「Ｓ＋２ｌＵ」とのうち、小さい方の値Ｔを取得する処理を示している。図９の例では、「Ｓ＋２ｌＵ」を算出する処理により、３行目の相対終端超過数（下位）の一番左のサブブロックの２と、２行目の相対最小超過数の左から２番目のサブブロックの０とが加算され、５行目の相対最小超過数（上位）の値として２が格納されている。また、図９の例では、「ｍｉｎ」により、相対最小超過数（上位）と相対最小超過数（下位）のうち、小さい方の値が６行目にある次の段の相対最小超過数の４ビットのサブブロックに格納されている。
【００７２】
小さい方の値を取得する処理「ｍｉｎｋ」も以下の式に示すビット演算を最小超過数算出部５５が行うことにより実現される。
【００７３】
【数６】
0005752337.tif 000007
【００７４】
最小超過数算出部５５は、処理１０８において、終端超過数算出部５４が算出したデータＧＢ８と、各ブロックの相対最小超過数を示すデータＬＭ８とを加算することで絶対最小超過数を示すデータＧＭ８を算出する。
【００７５】
図８には、相対最大超過数や絶対最大超過数を求めるデータフローは明示されていないが、相対最大超過数や絶対最大超過数を求める処理は、最小超過数を求める処理の一部を修正した処理を最大超過数算出部５６が実行することにより実現できる。以下では最小超過数を求める処理との相違点のみ説明する。
【００７６】
最大超過数算出部５６は、２ビットの複数のサブブロックにおける相対最大超過数を以下の式（９）に示される処理を実行することで算出する。式（９）は最小超過数算出部５５の計算における式（４）が示す処理を置き換えるものである。
【００７７】
【数７】
0005752337.tif 000008
【００７８】
また、最大超過数算出部５６は、式（５）から（７）に示される処理（ただしＬやＵに格納されるのは相対最大超過数である）を実行し、式（８）の代わりに、下位ｌビットの相対最大超過数Ｌと、下位ｌビットの相対の基準とした場合の上位ｌビットの相対最大超過数を示すデータである「Ｓ＋２ｌＵ」とのうち、大きい方の値を取得する処理を行う。大きい方の値を取得する「ｍａｘｋ」の処理も以下の式に示すビット演算を最大超過数算出部５６が行うことにより実現される。
【００７９】
【数８】
0005752337.tif 000009
【００８０】
また最大超過数算出部５６は、算出されたブロックごとの相対最大超過数のデータと、絶対終端超過数のデータＧＢ８とを加算することにより、絶対最大超過数のデータを取得する。
【００８１】
相対最大超過数や相対最小超過数を求める処理は、プロセッサ１１がビット演算や加算、乗算などを用い、条件分岐を用いないプログラムを実行することで実現される。これにより、条件分岐に伴うプロセッサ１１のパイプライン制御に伴う速度低下を防ぎ、またこれらの処理を並列で実行することが容易になる。また非特許文献２に記載の技術のように、２５６（２の８乗）のキーをもつルックアップテーブルを設ける必要がないので、必要なメモリが削減される。
【００８２】
ここで、上述の相対最小超過数や相対最大超過数などを求める処理の一部または全部をハードウェアにより実現してもよい。例えば、上述の式に示される演算のうち、処理量が多い「＋ｋ」や「−ｋ」などの演算を、プロセッサ１１がバス１５に接続される専用の演算ユニットにデータを入力しその結果をプロセッサ１１がバス１５経由で取得することで行ってもよい。
【００８３】
図１０は、複数のビットグループを加算する加算ユニットの一例を示す回路図である。図１０に示す加算ユニットは、「＋４」の計算をする演算ユニットである。この加算ユニットは、４ビットのサブブロック単位で入力ＩＮ＿ＡとＩＮ＿Ｂの値の加算をする。加算ユニットは、サブブロックの最下位のビット番号に対応して設けられる半加算器ＨＡと、サブブロックの最下位以外のビット番号に対応して設けられる全加算器ＦＡとを含む。半加算器ＨＡは、入力ＩＮ＿ＡおよびＩＮ＿Ｂの対応するビットを加算し出力ＯＵＴの対応するビットに結果Ｓを出力し、１つ上位の全加算器ＦＡにキャリーＣを出力する。全加算器ＦＡは、１つ下位のキャリーＣと、入力ＩＮ＿ＡおよびＩＮ＿Ｂの対応するビットを加算し、出力ＯＵＴの対応するビットに結果Ｓを出力し、１つ上位の全加算器ＦＡがある場合はその全加算器ＦＡにキャリーＣを出力する。ハードウェアでは、単にサブブロックの境界を超えてキャリーＣを出力しないようにするだけで「＋４」の計算を実現できる。同様にキャリーＣがサブブロックの境界を越えないようにし、演算結果が０であるか、負であるか等を示すビットを生成する演算回路をサブブロックごとに設けることで、「−ｋ」などの他の演算もハードウェアで実現することができる。なお、演算ユニットがプログラムを実行する機能を有していてもよい。この場合にはプロセッサ１１の代わりに式（５）から（８）などの他の演算も演算ユニットが行ってよい。
【００８４】
ここで、これまでの説明ではブロックのビット数は８としているが、１６など別の値であってもよい。ブロックのビット数は２のべき乗であることが望ましい。ビット数が増えた場合には、その増加に応じて式（５）から（８）に示す処理を繰り返す回数を増やせばよい。
【００８５】
なお、インデックス生成部５２は、絶対終端超過数、絶対最小超過数、絶対最大超過数を計算せずに、相対終端超過数、相対最小超過数、相対最大超過数を記憶部１２に格納してもよい。後述するブロック特定部６３がブロックを特定する処理を実行する際に、相対終端超過数、相対最小超過数、相対最大超過数から絶対終端超過数、絶対最小超過数、絶対最大超過数を求めてもよい。また、インデックス生成部５２は、インデックスとして、相対最大超過数や絶対最大超過数を算出しなくてもよい。非特許文献２には相対最大超過数を用いずに検索をする手法が開示されている。
【００８６】
データ送信部５３は、プロセッサ１１、記憶部１２および通信部１３を中心として実現される。データ送信部５３は、半構造テキストデータ、括弧木データ、ビット位置関連データ、括弧木データに含まれる複数のブロックの絶対終端超過数、絶対最小超過数、絶対最大超過数のデータをデータ受信部６１に向けて送信する（ステップＳ９５）。なお、データ送信部５３は、相対終端超過数、相対最小超過数、相対最大超過数を送信してもよい。
【００８７】
データ受信部６１は、プロセッサ１１、記憶部１２および通信部１３を中心として実現される。データ受信部６１は、データ送信部５３から送信される情報を受信し、記憶部１２に格納する（ステップＳ９６）。
【００８８】
クエリ取得部６２は、プロセッサ１１、記憶部１２および入出力部１４を中心として実現される。クエリ取得部６２は、クライアント装置２等で実行されるアプリケーションプログラムとのＡＰＩから取得した検索条件（半構造テキストデータに含まれるデータを検索するための条件）に基づいて、括弧木データのビット列において検索を開始するビット位置と、検索されるビット位置の条件としての絶対超過数とを取得する（ステップＳ９７）。例えば、クエリ取得部６２はビット位置ｉの開き括弧に対応する閉じ括弧のビット位置を見つける命令や、ビット位置ｉの閉じ括弧に対応する開き括弧のビット位置を見つける命令などをＡＰＩから取得し、これらから検索されるビット位置の絶対超過数を演算により取得する。絶対超過数を取得する手法については公知であるので詳細の記載は省略する。なお、クエリ取得部６２は、検索条件として、絶対超過数の代わりにいずれかのビット位置を基準とする相対超過数を取得してもよい。
【００８９】
ブロック特定部６３は、プロセッサ１１および記憶部１２を中心として実現される。ブロック特定部６３は、括弧木データに含まれるブロックのそれぞれの相対終端超過数、及び相対最小超過数に基づいて、検索条件として与えられた超過数を有するビットを含むブロックを特定する（ステップＳ９８）。本実施形態では、ブロック特定部６３は、絶対終端超過数、絶対最小超過数、絶対最大超過数に基づいて、検索条件として与えられた超過数を有するビットを含むブロックを特定する。
【００９０】
図１１は、ブロック特定部６３の処理において生成されるデータの関連を示す図である。ブロック特定部６３は、検索条件として与えられる８ビットの絶対超過数Ｅｘｃ（検索対象超過数）から検索条件データＱＥを生成する処理２０１と、絶対最小超過数のデータＧＭ８に含まれる各ブロックが検索条件データＱＥが示す絶対超過数Ｅｘｃ以下であるか否かを示すデータＳＭを出力する処理２０２と、絶対最大超過数のデータＧＰ８に含まれる各ブロックが検索条件データＱＥが示す絶対超過数Ｅｘｃより大きいかを示すデータＳＰを出力する処理２０３と、データＳＭとデータＳＰとのＡＮＤ演算をし、その結果のデータＳＡを出力する処理２０４とを実行する。
【００９１】
データＳＭ，ＳＰ，ＳＡは処理単位長のデータであり、本実施形態では８つのブロックを含む。データＳＭの各ブロックには、対応するデータＧＭ８のブロックが絶対超過数Ｅｘｃ以下の場合には真（Ｔｒｕｅ）を示す１が、対応するデータＧＭ８のブロックが絶対超過数Ｅｘｃより大きい場合には偽（Ｆａｌｓｅ）を示す０が格納される。データＳＰの各ブロックには、対応するデータＧＰ８のブロックが絶対超過数Ｅｘｃ以上の場合には真を示す１が、対応するデータＧＰ８のブロックが絶対超過数Ｅｘｃより小さい場合には偽を示す０が格納される。したがって、データＳＡの各ブロックには、絶対超過数ＥｘｃがデータＧＭ８の対応するブロックの値以上でデータＧＰ８の対応するブロック以下の場合に真を示す１が格納される。
【００９２】
処理２０１は具体的にはＬ８に絶対超過数Ｅｘｃを掛ける処理により実現され、処理２０２や２０３は「≦ｋ」の演算などによって実現される。処理２０１から２０３は、プロセッサ１１がビット演算や加算、乗算などを用い、条件分岐を用いないプログラムを実行することで実現される。
【００９３】
そして、ブロック特定部６３は処理２０５において、真の値を有する最も早いブロック（図１１において右側のブロック）を検索条件を満たすビットを含むブロックとして特定する。
【００９４】
ここで、前述のように、開き括弧に対応する閉じ括弧のビット位置を求める場合には絶対最大超過数や相対最大超過数を用いなくてもよい。その場合、処理２０３や２０４を行わずにブロックを特定してよい。この手法については非特許文献２に記載されている。
【００９５】
ビット位置特定部６４は、プロセッサ１１および記憶部１２を中心として実現される。ビット位置特定部６４は、ブロック特定部６３により特定されたブロックにおける、検索条件となる超過数を有するビットの位置を特定する（ステップＳ９９）。
【００９６】
図１２は、ビット位置特定部６４の処理において生成されるデータの関連を示す図である。ビット位置特定部６４は、特定されたブロックのビット列ＰＢと検索条件である絶対超過数Ｅｘｃとを取得する。そして、ビット位置特定部６４は、各ブロックがビット列ＰＢを含む処理単位長のデータＷＡを生成する処理３０１と、検索条件となる絶対超過数からブロックの先頭を０とした場合の相対超過数Ｅｘｃ’を求め、各ブロックに相対超過数Ｅｘｃ’が格納されるデータＱＢを生成する処理３０２とを行う。またビット位置特定部６４は、データＷＡからデータＰを生成する処理３０３と、データＰからデータＥを生成する処理３０４と、データＥとデータＱＢとからデータＳＸを生成する処理３０５と、データＳＸから検索条件を満たすビット位置を特定する処理３０６とを行う。
【００９７】
データＷＡ，Ｐ，Ｅ，ＱＢ，ＳＸはそれぞれ処理単位長のデータであり、８つのブロックを含む。
【００９８】
ビット位置特定部６４は処理３０１において、Ｌｋ（ｋはブロック長）とビット列ＰＢとを乗算することでデータＷＡを取得する。また、ビット位置特定部６４は処理３０２において、検索条件となる絶対超過数Ｅｘｃから、このブロックの前のブロックの絶対終端超過数を引くことで、検索条件となる相対超過数Ｅｘｃ’を求め、相対超過数Ｅｘｃ’にＬｋを乗算することでデータＱＢを取得する。
【００９９】
図１３は、ビット位置特定部６４がビット位置を検索する過程の一例を説明する図である。図１３は、図６に示すビット列について検索条件となる絶対超過数が２である場合にブロック特定部６３がブロック番号１を特定した場合の処理の過程を示す。また図１３のビット列や数値については左側が下位のビットのものとなる。以下では図１２に示す処理の詳細とともに図１３の例を説明する。
【０１００】
ビット位置特定部６４は処理３０３において、データＷＡから各ブロックについて、先頭から非マスク数のビットを取得したデータＰを生成する。非マスク数は１からブロック長の間の値であり、その値はブロックの位置により異なる。例えば、データ内のブロックが右から左に進むにつれて１から８の値を取る。
【０１０１】
データＰに含まれる各ブロックは、先頭から非マスク数のビットを元の値のまま残し、残りのビットの値を所定値（０）に変更したデータとなる。処理３０１および３０３は以下の式（１０）で表される。
【０１０２】
【数９】
0005752337.tif 000010
【０１０３】
ｘは特定されたブロックのビット列を示し、Ｕは、各ブロックの非マスク数の先頭側ビットを１とし、他のビットを０とした処理単位長の値である。本実施形態におけるＵを２進数で表すと、「１１１１１１１１０１１１１１１１００１１１１１１０００１１１１１００００１１１１０００００１１１００００００１１０００００００１」となる。図１３の例では展開後の行に示されているのがこのデータＰである。図１３ではビット列の左側ほど下位になるので、Ｕの２進数表記とは左右が反対になっている。処理３０１および処理３０３において、プロセッサ１１は特定されたブロックの値をレジスタに格納し、そのレジスタにＬ８を乗算し、乗算されたレジスタとＵとをＡＮＤ演算する。
【０１０４】
ビット位置特定部６４は処理３０４において、データＰに含まれる各ブロックについて取得された非マスク数のビットの終端ビットの相対超過数が格納されるデータＥを算出する。処理３０４は以下の式で表される。
【０１０５】
【数１０】
0005752337.tif 000011
【０１０６】
ここで、Ｂは処理単位長のデータであり、８つのブロックを含み、各ブロックには対応するＵのブロックの非マスク数が格納されている。
【０１０７】
この処理３０４では、はじめにビット位置特定部６４はデータＵの各ブロックにおける、１のビットの数を示すビット列を単位処理長のデータＷＢの対応するブロックに格納する。データＷＢはビット位置特定部６４が式（１）から（３）に示す演算をすることにより取得される。より具体的には、第１のレジスタＲ１にデータＰが格納されているとして、プロセッサ１１は第２のレジスタＲ２にＲ１の値をコピーし、Ｒ１を１ビット右シフトし、Ｒ１とμ０とをＡＮＤ演算し、Ｒ２からＲ１を減算し、減算された結果のＲ２の値をＲ１にコピーし、Ｒ２を２ビット右シフトし、Ｒ１とμ１とのＡＮＤ演算をし、Ｒ１とＲ２とを加算し、加算された結果のＲ１の値をＲ２にコピーし、Ｒ１を４ビット右シフトし、Ｒ１とＲ２を加算し、加算されたＲ１とμ２とのＡＮＤ演算をした結果をデータＷＢとする。
【０１０８】
ビット位置特定部６４は処理３０４において、次に、データＷＢを１ビット左シフトすることで１のビットの数を２倍にし（図１３の「１の個数」の行から次の行への処理矢印参照）、シフトされたデータＷＢの各ブロックについてそのブロックに応じた非マスク数を減算することで相対超過数を示すビット列のデータＥを取得する（図１３の「相対超過数」への矢印参照）。より具体的には、プロセッサ１１はデータＷＢが格納されるＲ１を１ビット左シフトし、Ｒ１に対してＨ８をＯＲ演算し、Ｒ１からＵを減算し、減算結果のＲ１とＨ８とをＸＯＲ演算することでデータＥを取得する。
【０１０９】
次に、ビット位置特定部６４は処理３０５において、データＥに含まれる各ブロックについて終端ビットの相対超過数と検索相対超過数Ｅｘｃ’とが同じ場合に真を示す値（１）を、異なる場合に偽の値（０）を格納するデータＳＸを生成する（図１３の「比較結果」への矢印参照）。また、ビット位置特定部６４は処理３０６において、データＳＸから、検索条件を満たすビットのブロック内の位置を格納するデータＢＰを生成する。処理３０５および３０６は、それぞれ以下の式（１２）、式（１３）で表される。
【０１１０】
【数１１】
0005752337.tif 000012
【０１１１】
式（１２）に示す「Ｌｋ＊ｄ」は、データＱＢを示し、「Ｔ」はデータＳＸを示す。データＱＢとデータＥとの比較は、より具体的には、データ内の複数のブロック（例えば複数のバイト）をまとめて比較するプロセッサ１１のＳＩＭＤ命令により行われてもよいし、プロセッサ１１がデータＱＢとデータＥとをＸＯＲ演算し、その結果についてＮＯＴ演算と、加算、ＡＮＤ演算とシフト演算とを組み合わせて適用することで行われてもよい。式（１２）に示す処理により、ビット位置特定部６４はブロックのうち非マスク数に対応するビット位置における超過数が、検索条件として与えられた超過数であるかを判定する。言い換えれば、ビット位置特定部６４は非マスク数に対応するビット位置が、検索条件の超過数のビット位置であるかを判定する。また、式（１３）のＬＳＢ（Ｔ）は、データＳＸのうち１または複数のビットが１となっている場合に、そのビットの一番右にあるビットのビット位置を計算することを示す。ＬＳＢ（Ｔ）は、プロセッサ１１の命令により計算されてもよいし、他の公知の高速なアルゴリズムを用いて計算されてもよい。また式（１３）の「＞＞ｊ」は、ビット位置をブロック長（８）で割ることを示す。これにより、ブロック内のビット列のうち検索条件を満たす最も先頭側のビット位置が格納されるデータＢＰが求められる。
【０１１２】
さらに、ビット位置特定部６４はデータＢＰの値（図１３の例では４）に、ブロック長×ブロック番号（図１３の例では１×８）を加算することにより、括弧木データのビット列の開始位置からのビット位置（図１３の例では１２）を求め、検索条件を満たすビット位置として出力する。
【０１１３】
ビット位置特定部６４の処理は、プロセッサ１１がビット演算や加算、乗算などを組み合わせて用い、かつ条件分岐をほとんど用いないプログラムを実行することで実現される。これにより、条件分岐に伴うプロセッサ１１のパイプライン制御に伴う速度低下を防ぎ、またこれらの処理を並列で実行することが容易になる。また非特許文献２に記載されたルックアップテーブルを用いる必要がないので、必要なメモリが削減される。非特許文献２ではこのルックアップテーブルはブロックの値の種類である２５６と検索条件となる相対超過数の種類１７との組み合わせをキーとするので、ルックアップテーブルとしては２５６×１７バイトを節約できる。
【０１１４】
クエリ結果出力部６５はプロセッサ１１および記憶部１２を中心として実現される。クエリ結果出力部６５はビット位置特定部６４により特定されたビット位置に基づいて、半構造テキストデータに含まれ、そのビット位置に対応する文字列のデータを出力する。例えば、ビット位置特定部６４により、開き括弧に対応する閉じ括弧のビット位置がノードの終端として検索された場合、その次のビット位置に兄弟ノードが存在するので、ビット位置関連データを用いてそのビット位置に対応する文字列を取得し、表示出力デバイスなどに出力する。図４や図６に示す例では、次のｓｅｃｔｉｏｎや次のＴＩＴＬＥの情報を表示することに対応する。
【０１１５】
なお、クエリ取得部６２、ブロック特定部６３、ビット位置特定部６４、クエリ結果出力部６５をデータベースエンジンとして利用してもよい。この場合、クエリ取得部６２、ブロック特定部６３、ビット位置特定部６４、クエリ結果出力部６５を情報処理サーバに配置し、それらがインデックス生成部５２や括弧木データ生成部５１が記憶部１２に出力したデータを利用して検索をしてよい。クエリの結果として半構造テキストデータのうち一部のノードおよびその子孫ノードの文字列を必要とするような場合などではこのデータベースエンジンが有効である。
【符号の説明】
【０１１６】
１  情報処理サーバ、２  クライアント装置、３  ネットワーク、１１  プロセッサ、１２  記憶部、１３  通信部、１４  入出力部、１５  バス、５１  括弧木データ生成部、５２  インデックス生成部、５３  データ送信部、５４  終端超過数算出部、５５  最小超過数算出部、５６  最大超過数算出部、６１  データ受信部、６２  クエリ取得部、６３  ブロック特定部、６４  ビット位置特定部、６５  クエリ結果出力部、ＨＡ  半加算器、ＦＡ  全加算器、ＩＢ  ビットベクトル、Ｎ２，Ｎ４，Ｎ８，ＧＢ８  データ、ＬＭ２，ＬＭ４，ＬＭ８，ＧＭ８，ＧＰ８  データ、ＩＮ＿Ａ，ＩＮ＿Ｂ  入力、ＯＵＴ  出力、Ｅｘｃ  絶対超過数、Ｅｘｃ’  相対超過数、ＳＭ，ＳＰ，ＳＡ  データ、ＷＡ，ＱＢ，Ｐ，Ｅ，ＳＸ，ＢＰ  データ、ＱＥ  検索条件データ、ＰＢ  ビット列。
【要約】
複数のブロックを含む括弧木データのビット列から検索条件を満たすビット位置を検索する際のメモリ使用量を削減すること。
情報処理システムは、被検索括弧列を示すビット列を複数のブロックに分割し、前記各ブロックの終端ビットの相対超過数を算出し、前記各ブロックについて相対最小超過数を算出し、前記各ブロックの終端ビットの相対超過数、及び相対最小超過数に基づき、所与の超過数を有するビットを含む前記ブロックを特定し、特定される前記ブロックおける前記所与の超過数を有するビットの位置を特定する。また、ビットの位置を特定する際には、特定される前記ブロックに含まれるビット列のうち先頭から所定数のビットに含まれる値１のビットの数と、前記所定数と、前記所与の超過数と、に基づいて、前記所与の超過数を有するビットの位置が前記所定数に対応する位置であるか否かを判定する。【図１】
0005752337.tif 000013
【図２】
0005752337.tif 000014
【図３】
0005752337.tif 000015
【図４】
0005752337.tif 000016
【図５】
0005752337.tif 000017
【図６】
0005752337.tif 000018
【図７】
0005752337.tif 000019
【図８】
0005752337.tif 000020
【図９】
0005752337.tif 000021
【図１０】
0005752337.tif 000022
【図１１】
0005752337.tif 000023
【図１２】
0005752337.tif 000024
【図１３】
0005752337.tif 000025
【図１４】
0005752337.tif 000026