"検索対象データに関するタグを有するタクソノミにおいて、前記タクソノミにおける各ノードから到達可能な検索対象データの集合を取り出すためのデータ構造であって、前記タクソノミにおいて、前記各ノードの上位ノードである先祖ノードを示す先祖参照用データと、前記各ノードの転置リストを含み、前記各ノードのうち、前記先祖参照用データにおいて前記先祖ノードが登録されているノードの転置リストは、登録された前記先祖ノードに対応する転置リスト中の位置を示す整数値のリストであり、さらに、前記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、前記ブロックにおける整数値と前記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換された転置リスト用データとを備える、データ構造。検索対象データに関するタグを有するタクソノミにおいて、前記タクソノミにおける各ノードから到達可能な検索対象データの集合を取り出すために用いる転置リストを作成するためのインデックス作成装置であって、前記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、前記ブロックにおける整数値と前記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換されており、前記タクソノミにおけるノードごとに、前記ノードの上位ノードである先祖ノードを1つ選択し、選択した前記先祖ノードを示す先祖参照用データを生成するための先祖ノード決定部と、前記先祖参照用データに基づいて、前記タクソノミにおけるタグの1または複数の先祖ノードを示す先祖ノードリストを生成するための先祖ノード探索部と、前記検索対象データの識別子を受けて、前記先祖ノードリストにおける各前記ノードのうち最上位のノードについては、前記識別子を対応の転置リストの要素として追加し、前記最上位ノード以外のノードについては、対応の転置リストの要素として、前記識別子の代わりに、前記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値を追加するための先祖番号変換部とを備える、インデックス作成装置。検索対象データに関するタグを有するタクソノミにおいて、前記タクソノミにおける指定された指定ノードから到達可能な検索対象データの集合を取り出すためのデータ検索装置であって、前記タクソノミにおける各ノードの転置リストを含み、前記各ノードのうち、最上位のノードの転置リストは、前記検索対象データの識別子を示す整数値のリストであり、前記最上位ノード以外のノードの転置リストは、前記識別子の代わりに、前記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値のリストであり、さらに、前記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、前記ブロックにおける整数値と前記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換された転置リスト用データを記憶するための先祖番号転置リスト記憶部と、前記指定ノードを示す情報を受けて、前記転置リスト用データに基づき、前記指定ノードに対応する前記転置リストの整数値が示す前記位置に対応する、前記指定ノードの上位ノードに対応する前記転置リストの整数値を取り出す処理を、前記最上位ノードに対応する前記転置リストの前記識別子を取り出すまで繰り返すことにより、前記指定ノードに対応する前記検索対象データの識別子のリストを作成するための識別子変換部とを備える、データ検索装置。前記データ検索装置は、さらに、前記タクソノミにおける各ノードの、各検索対象データに対応する頻度を示す頻度リストを記憶するための頻度リスト記憶部を備え、前記識別子変換部は、さらに、前記指定ノードに対応する1または複数の前記検索対象データの識別子のリストにおいて、前記頻度リストに基づいて前記識別子をソートする、請求の範囲第3項に記載のデータ検索装置。前記データ検索装置は、前記タクソノミにおける複数のノードが指定された場合には、各前記指定ノードのいずれからも到達可能な検索対象データの集合を取り出し、前記識別子変換部は、前記タクソノミにおける複数のノードが指定された場合には、各前記指定ノードに対応する前記転置リストを前記先祖番号転置リスト記憶部から取得し、前記指定ノードに対応する前記転置リストの整数値が示す前記位置に対応する、前記指定ノードの上位ノードに対応する前記転置リストの整数値を取り出す処理を行なう際に、前記指定ノードの組で共通の前記上位ノードのうち、前記タクソノミにおいて最も下位の上位ノードである共通先祖ノードに対応する前記転置リストにおける整数値を取り出すとき、前記指定ノードの組において共通の前記整数値を取り出し、取り出した前記整数値を用いて、前記複数の指定ノードに対応する前記検索対象データの識別子のリストを作成する、請求の範囲第3項に記載のデータ検索装置。前記データ検索装置は、さらに、前記タクソノミにおける各ノードの下位ノードである子ノードの集合を示す子ノード情報を記憶するための子ノード記憶部と、前記指定ノードに対応する前記検索対象データの識別子のリストを受けて、前記タクソノミにおける各ノードの中から、前記リストが示す前記検索対象データの集合において所定値以上の頻度を持つノードを取り出すためのトップダウン探索部とを備え、前記トップダウン探索部は、前記最上位ノードに対応する前記転置リストにおける前記識別子の位置を検出し、前記子ノード情報に基づいて、検出した前記位置と前記最上位ノードの1つ下位のノードに対応する前記転置リストにおける整数値とを比較し、一致した整数値に基づいて前記ノードの頻度を算出する処理を少なくとも行い、さらに、前記ノードの下位のノードについて、上位ノードに対応する前記転置リストにおいて前記識別子の位置に対応する整数値と、前記上位ノードの1つ下位のノードに対応する前記転置リストにおける整数値とを比較し、一致した整数値に基づいて前記1つ下位のノードの頻度を算出する処理を0回以上行なうことにより、前記検索対象データにおける前記各ノードの頻度を算出する、請求の範囲第3項に記載のデータ検索装置。検索対象データに関するタグを有するタクソノミにおいて、前記タクソノミにおける各ノードから到達可能な検索対象データの集合を取り出すために用いる転置リストを作成するインデックス作成方法であって、前記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、前記ブロックにおける整数値と前記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換されており、前記タクソノミにおけるノードごとに、前記ノードの上位ノードである先祖ノードを1つ選択し、選択した前記先祖ノードを示す先祖参照用データを生成するステップと、前記先祖参照用データに基づいて、前記タクソノミにおけるタグの1または複数の先祖ノードを示す先祖ノードリストを生成するステップと、前記検索対象データの識別子を受けて、前記先祖ノードリストにおける各前記ノードのうち最上位のノードについては、前記識別子を対応の転置リストの要素として追加し、前記最上位ノード以外のノードについては、対応の転置リストの要素として、前記識別子の代わりに、前記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値を追加するステップとを含む、インデックス作成方法。検索対象データに関するタグを有するタクソノミにおいて、前記タクソノミにおける指定された指定ノードから到達可能な検索対象データの集合を取り出すデータ検索方法であって、前記タクソノミにおける各ノードの転置リストを含み、前記各ノードのうち、最上位のノードの転置リストは、前記検索対象データの識別子を示す整数値のリストであり、前記最上位ノード以外のノードの転置リストは、前記識別子の代わりに、前記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値のリストであり、さらに、前記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、前記ブロックにおける整数値と前記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換された転置リスト用データを取得するステップと、前記指定ノードを示す情報を受けて、前記転置リスト用データに基づき、前記指定ノードに対応する前記転置リストの整数値が示す前記位置に対応する、前記指定ノードの上位ノードに対応する前記転置リストの整数値を取り出す処理を、前記最上位ノードに対応する前記転置リストの前記識別子を取り出すまで繰り返すことにより、前記指定ノードに対応する前記検索対象データの識別子のリストを作成するステップとを含む、データ検索方法。検索対象データに関するタグを有するタクソノミにおいて、前記タクソノミにおける各ノードから到達可能な検索対象データの集合を取り出すために用いる転置リストを作成するインデックス作成プログラムを記録した、コンピュータ読み取り可能な記録媒体であって、前記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、前記ブロックにおける整数値と前記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換されており、前記インデックス作成プログラムは、コンピュータに、前記タクソノミにおけるノードごとに、前記ノードの上位ノードである先祖ノードを1つ選択し、選択した前記先祖ノードを示す先祖参照用データを生成するステップと、前記先祖参照用データに基づいて、前記タクソノミにおけるタグの1または複数の先祖ノードを示す先祖ノードリストを生成するステップと、前記検索対象データの識別子を受けて、前記先祖ノードリストにおける各前記ノードのうち最上位のノードについては、前記識別子を対応の転置リストの要素として追加し、前記最上位ノード以外のノードについては、対応の転置リストの要素として、前記識別子の代わりに、前記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値を追加するステップとを実行させるためのプログラムである、コンピュータ読み取り可能な記録媒体。検索対象データに関するタグを有するタクソノミにおいて、前記タクソノミにおける指定された指定ノードから到達可能な検索対象データの集合を取り出すデータ検索プログラムを記録した、コンピュータ読み取り可能な記録媒体であって、前記データ検索プログラムは、コンピュータに、前記タクソノミにおける各ノードの転置リストを含み、前記各ノードのうち、最上位のノードの転置リストは、前記検索対象データの識別子を示す整数値のリストであり、前記最上位ノード以外のノードの転置リストは、前記識別子の代わりに、前記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値のリストであり、さらに、前記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、前記ブロックにおける整数値と前記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換された転置リスト用データを取得するステップと、前記指定ノードを示す情報を受けて、前記転置リスト用データに基づき、前記指定ノードに対応する前記転置リストの整数値が示す前記位置に対応する、前記指定ノードの上位ノードに対応する前記転置リストの整数値を取り出す処理を、前記最上位ノードに対応する前記転置リストの前記識別子を取り出すまで繰り返すことにより、前記指定ノードに対応する前記検索対象データの識別子のリストを作成するステップとを実行させるためのプログラムである、コンピュータ読み取り可能な記録媒体。ところで、電子文書を検索する際に、複数のタグおよび複数の意味クラスから構成される有向非循環グラフDAG:DirectedAcyclicGraphのデータ集合以下、タクソノミとも称する。が用いることが考えられる。ここでは、まず、タクソノミおよび検索対象データを定義する。図31は、本発明の第1の実施の形態に係るインデックス作成装置およびデータ検索装置におけるタクソノミおよび検索対象データの一例を具体的に示す図である。図31を参照して、前述のように、タクソノミとは、複数のタグおよび複数の意味クラスから構成される有向非循環グラフである。タグとは、グラフ中の葉ノードであり、少なくともラベルを持つ情報である。ラベルとは、タグを表現する文字列である。図31では、タグを長方形で表現し、各タグのラベルをで囲んだ文字列として表現している。また、意味クラスとは、タグをまとめ上げる概念を表現した情報であり、文字列であるラベル、または識別子を持つ。図31では、各意味クラスを楕円で表現し、各意味クラスのラベルを楕円内に記述している。なお、以下では、任意の文字または記号であるXについて、Xというラベルを持つタグまたは意味クラスをXノードと表現することがある。タクソノミ内の意味クラスおよびタグには、意味的な包含関係が存在する。図31では、矢印でこの関係を示している。たとえば、企業ノードは電器メーカーノードの上位の概念であり、電器メーカーノードは山本電気ノードの上位の概念である。また、この包含関係には、同義な関係も含まれる。たとえば、山本電気という企業がyamadenという略称で呼ばれることもあるとする。このとき、山本電気ノードはyamadenノードの上位の概念として捉えることも可能である。検索対象データとは、タクソノミ中のタグと結びついたデータであり、他の検索対象データとの識別を可能とするユニークな識別子を持つ。検索対象データの例としては、たとえば、ニュース記事などがこれにあたり、各記事は、整数で表現された識別子を持ち、また、各記事中に登場する単語をタグとして持つ。図31では、7つの検索対象データ、および各検索対象データに対応する識別子が示されている。たとえば、識別子001の検索対象データは、山本電気というデータを含み、タクソノミ中の山本電気ノードとの関係を持つ。本発明の第1の実施の形態に係るデータ検索装置は、ある意味クラスまたはタグを示す情報が入力されると、当該情報によって指定されたタクソノミ中のノードから到達可能なデータの集合を示す識別子のリストを返す。たとえば、タグyamadenがデータ検索装置へ入力されると、データ検索装置は、003,004の2つの識別子を検索対象として返す。また、意味クラス山陽食品がデータ検索装置へ入力されると、データ検索装置は、004,005,006,007の4つの識別子を検索対象として返す。次に、図31に示すモデルについてもう少し詳しい説明を行なう。図32は、本発明の第1の実施の形態に係るインデックス作成装置およびデータ検索装置におけるタクソノミおよび検索対象データの一例を概念的に示す図である。図32では、タクソノミの例が示されており、楕円が意味クラスを表し、長方形がタグを表している。各タグからつながっているdXは、ノードXから到達可能な検索対象データの識別子の集合を表現している。このとき、意味クラスXに対応するdXは、意味クラスXから到達可能なタグの集合Yにおいて、各タグのdyy⊂YのUnionになる。たとえば、dB=dL∪dM∪dNであり、dA=dL∪dM∪dN∪dOである。このようなタクソノミを用いた電子文書検索では、タクソノミのサイズが大きくなった場合に、タクソノミにおいて上位の意味クラスに対する問い合わせを高速に実現できない、という問題点がある。すなわち、従来の転置インデックスを用いる方法としては、タグのみの転置インデックスを用いる方法A、およびすべてのノードに対応する転置インデックスを用いる方法Bの2種類が考えられる。方法Aを採用した場合、上位の意味クラスに対応する転置リストを参照するためには、到達可能なタグの集合を計算する処理時間と、当該計算結果によって得られるタグの集合に対応する転置リストをそれぞれ参照し、データ集合のUnion和集合を計算する処理時間とが必要である。このため、方法Aを採用すると、タクソノミおよびデータ集合のサイズが大きくなった場合に、これら2つの処理時間が増大してしまう。また、方法Bを採用した場合、検索時に該当する転置リストを読み出すのみで処理を終えることができるものの、記憶しなければならないデータの量が圧倒的に増加する。現在のコンピュータアーキテクチャでは、主記憶装置に収まらないデータがある場合、補助記憶装置へのアクセスが発生するため、方法Bを採用すると問い合わせ速度が低下してしまうことがある。しかしながら、特許文献1~3および非特許文献1には、タクソノミを用いた電子文書検索において、上記のような問題点を解決するための構成は開示されていない。この発明は、上述の課題を解決するためになされたもので、その目的は、検索処理のためのデータ容量の低減および検索処理の高速化を図ることが可能なデータ構造、インデックス作成装置、データ検索装置、インデックス作成方法、データ検索方法およびコンピュータ読み取り可能な記録媒体を提供することである。上記課題を解決するために、この発明のある局面に係わるデータ構造は、検索対象データに関するタグを有するタクソノミにおいて、上記タクソノミにおける各ノードから到達可能な検索対象データの集合を取り出すためのデータ構造であって、上記タクソノミにおいて、上記各ノードの上位ノードである先祖ノードを示す先祖参照用データと、上記各ノードの転置リストを含み、上記各ノードのうち、上記先祖参照用データにおいて上記先祖ノードが登録されているノードの転置リストは、登録された上記先祖ノードに対応する転置リスト中の位置を示す整数値のリストであり、さらに、上記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、上記ブロックにおける整数値と上記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換された転置リスト用データとを備える。上記課題を解決するために、この発明のある局面に係わるインデックス作成装置は、検索対象データに関するタグを有するタクソノミにおいて、上記タクソノミにおける各ノードから到達可能な検索対象データの集合を取り出すために用いる転置リストを作成するためのインデックス作成装置であって、上記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、上記ブロックにおける整数値と上記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換されており、上記タクソノミにおけるノードごとに、上記ノードの上位ノードである先祖ノードを1つ選択し、選択した上記先祖ノードを示す先祖参照用データを生成するための先祖ノード決定部と、上記先祖参照用データに基づいて、上記タクソノミにおけるタグの1または複数の先祖ノードを示す先祖ノードリストを生成するための先祖ノード探索部と、上記検索対象データの識別子を受けて、上記先祖ノードリストにおける各上記ノードのうち最上位のノードについては、上記識別子を対応の転置リストの要素として追加し、上記最上位ノード以外のノードについては、対応の転置リストの要素として、上記識別子の代わりに、上記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値を追加するための先祖番号変換部とを備える。上記課題を解決するために、この発明のある局面に係わるデータ検索装置は、検索対象データに関するタグを有するタクソノミにおいて、上記タクソノミにおける指定された指定ノードから到達可能な検索対象データの集合を取り出すためのデータ検索装置であって、上記タクソノミにおける各ノードの転置リストを含み、上記各ノードのうち、最上位のノードの転置リストは、上記検索対象データの識別子を示す整数値のリストであり、上記最上位ノード以外のノードの転置リストは、上記識別子の代わりに、上記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値のリストであり、さらに、上記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、上記ブロックにおける整数値と上記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換された転置リスト用データを記憶するための先祖番号転置リスト記憶部と、上記指定ノードを示す情報を受けて、上記転置リスト用データに基づき、上記指定ノードに対応する上記転置リストの整数値が示す上記位置に対応する、上記指定ノードの上位ノードに対応する上記転置リストの整数値を取り出す処理を、上記最上位ノードに対応する上記転置リストの上記識別子を取り出すまで繰り返すことにより、上記指定ノードに対応する上記検索対象データの識別子のリストを作成するための識別子変換部とを備える。上記課題を解決するために、この発明のある局面に係わるインデックス作成方法は、検索対象データに関するタグを有するタクソノミにおいて、上記タクソノミにおける各ノードから到達可能な検索対象データの集合を取り出すために用いる転置リストを作成するインデックス作成方法であって、上記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、上記ブロックにおける整数値と上記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換されており、上記タクソノミにおけるノードごとに、上記ノードの上位ノードである先祖ノードを1つ選択し、選択した上記先祖ノードを示す先祖参照用データを生成するステップと、上記先祖参照用データに基づいて、上記タクソノミにおけるタグの1または複数の先祖ノードを示す先祖ノードリストを生成するステップと、上記検索対象データの識別子を受けて、上記先祖ノードリストにおける各上記ノードのうち最上位のノードについては、上記識別子を対応の転置リストの要素として追加し、上記最上位ノード以外のノードについては、対応の転置リストの要素として、上記識別子の代わりに、上記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値を追加するステップとを含む。上記課題を解決するために、この発明のある局面に係わるデータ検索方法は、検索対象データに関するタグを有するタクソノミにおいて、上記タクソノミにおける指定された指定ノードから到達可能な検索対象データの集合を取り出すデータ検索方法であって、上記タクソノミにおける各ノードの転置リストを含み、上記各ノードのうち、最上位のノードの転置リストは、上記検索対象データの識別子を示す整数値のリストであり、上記最上位ノード以外のノードの転置リストは、上記識別子の代わりに、上記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値のリストであり、さらに、上記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、上記ブロックにおける整数値と上記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換された転置リスト用データを取得するステップと、上記指定ノードを示す情報を受けて、上記転置リスト用データに基づき、上記指定ノードに対応する上記転置リストの整数値が示す上記位置に対応する、上記指定ノードの上位ノードに対応する上記転置リストの整数値を取り出す処理を、上記最上位ノードに対応する上記転置リストの上記識別子を取り出すまで繰り返すことにより、上記指定ノードに対応する上記検索対象データの識別子のリストを作成するステップとを含む。上記課題を解決するために、この発明のある局面に係わるコンピュータ読み取り可能な記録媒体は、検索対象データに関するタグを有するタクソノミにおいて、上記タクソノミにおける各ノードから到達可能な検索対象データの集合を取り出すために用いる転置リストを作成するインデックス作成プログラムを記録した、コンピュータ読み取り可能な記録媒体であって、上記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、上記ブロックにおける整数値と上記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換されており、上記インデックス作成プログラムは、コンピュータに、上記タクソノミにおけるノードごとに、上記ノードの上位ノードである先祖ノードを1つ選択し、選択した上記先祖ノードを示す先祖参照用データを生成するステップと、上記先祖参照用データに基づいて、上記タクソノミにおけるタグの1または複数の先祖ノードを示す先祖ノードリストを生成するステップと、上記検索対象データの識別子を受けて、上記先祖ノードリストにおける各上記ノードのうち最上位のノードについては、上記識別子を対応の転置リストの要素として追加し、上記最上位ノード以外のノードについては、対応の転置リストの要素として、上記識別子の代わりに、上記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値を追加するステップとを実行させるためのプログラムである。またこの発明の別の局面に係わるコンピュータ読み取り可能な記録媒体は、検索対象データに関するタグを有するタクソノミにおいて、上記タクソノミにおける指定された指定ノードから到達可能な検索対象データの集合を取り出すデータ検索プログラムを記録した、コンピュータ読み取り可能な記録媒体であって、上記データ検索プログラムは、コンピュータに、上記タクソノミにおける各ノードの転置リストを含み、上記各ノードのうち、最上位のノードの転置リストは、上記検索対象データの識別子を示す整数値のリストであり、上記最上位ノード以外のノードの転置リストは、上記識別子の代わりに、上記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値のリストであり、さらに、上記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、上記ブロックにおける整数値と上記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換された転置リスト用データを取得するステップと、上記指定ノードを示す情報を受けて、上記転置リスト用データに基づき、上記指定ノードに対応する上記転置リストの整数値が示す上記位置に対応する、上記指定ノードの上位ノードに対応する上記転置リストの整数値を取り出す処理を、上記最上位ノードに対応する上記転置リストの上記識別子を取り出すまで繰り返すことにより、上記指定ノードに対応する上記検索対象データの識別子のリストを作成するステップとを実行させるためのプログラムである。本発明によれば、検索処理のためのデータ容量の低減および検索処理の高速化を図ることができる。以下、本発明の実施の形態について図面を用いて説明する。なお、図中同一または相当部分には同一符号を付してその説明は繰り返さない。<第1の実施の形態>本発明の第1の実施の形態に係るデータ検索装置は、タクソノミ中のノードを示すXを入力し、dXを返す機能を提供する。このような機能を実現する方法としては、転置インデックスを用いることが考えられる。図1aは、転置インデックスを用いたデータ構造の一例を示している。図1bは、転置インデックスを用いたデータ構造の他の例を示している。図1aは、タクソノミ中のタグに対して作成した転置インデックスを示している。この転置インデックスでは、各行が各タグの転置リストを表している。たとえば、タグLは、検索対象データ1番、456番および12000番に関連し、タグMは、検索対象データ23番および16333番に関連している。この転置インデックスを用いたデータ検索装置は、タグが入力として与えられた場合、転置インデックスにおける各行のうち、当該タグに対応する行のデータを返す。また、意味クラスが入力として与えられた場合、このデータ検索装置は、タクソノミ中の到達可能なタグの集合を調べ、各タグに対応するdXをそれぞれ取り出し、取り出したdXのUnionを計算して返す。図1bは、タクソノミ中の全ノードに対して作成した転置インデックスを示している。この転置インデックスでは、各行が各ノードの転置リストを表している。たとえば、意味クラスBは、検索対象データ1番、23番、456番、12000番および16333番に関連している。この転置インデックスを用いたデータ検索装置は、タクソノミ中のノードXが指定された場合、転置インデックスにおける各行のうち、ノードXに対応する行のデータを取り出す。次に、本発明の第1の実施の形態に係るインデックス作成装置およびデータ検索装置における転置リストの圧縮技術について説明する。図1に示す転置インデックスは、各キーに対応する整数値のリストである。通常、コンピュータによって整数値を保持するためには、4バイトのデータが必要である。このため、普通にこれらのデータを保持するためには、ノードごとに4バイト×ノードが登場する検索対象データ数のサイズを持つ転置リストを保持しなければならない。通常、このような転置リストのサイズは大きなものになるため、次のような圧縮方法が用いられる。図2は、本発明の第1の実施の形態に係るインデックス作成装置およびデータ検索装置における転置リストの圧縮方法の一例を示す図である。図2は、1,2,5,7,8,11,15,16,18,19という10個の整数値のリストを圧縮する方法の例を示している。この圧縮方法では、まず、整数値のリストをL個置きにブロックに分割する。ここでは、L=5の場合が例示されている。次に、分割されたブロックに対して、先頭の数値はそのままにし、以降の数値を直前の数値との差分に置き換える処理を行なう。次に、可変長整数コードを用いて、これら差分の値を表現する。ここで、可変長整数コードとは、短い整数を短いビット長で表現し、長い整数を長いビット長で表現する整数列の符号化方法である。可変長整数コードの例は、非特許文献1に記載されている。図3は、本発明の第1の実施の形態に係るインデックス作成装置およびデータ検索装置における可変長整数コードの一例を示す図である。図3では、可変長整数コードの例としてγコードの例が示されている。たとえば、整数1は、0で表され、整数2は、100で表される。図2に示すような圧縮方法が有効な理由は、以下の通りである。すなわち、まず、整数値を差分で表現することにより、転置リストの整数値が小さくなる。そして、可変長整数コードを用いることにより、データ長が短くなる。これにより、転置リストの圧縮が可能となる。さらに、L個ごとのブロックを作成することにより、たかだかL回の復号および足し算を行なえば、元の転置リストにおける任意の位置の値を取り出すことができる。[構成および基本動作]本発明の第1の実施の形態に係るインデックス作成装置およびデータ検索装置を備える情報処理装置は、典型的には、汎用的なアーキテクチャを有するコンピュータを基本構造としており、予めインストールされたプログラムを実行することで、後述するような各種機能を提供する。一般的に、このようなプログラムは、フレキシブルディスクFlexibleDiskおよびCD-ROMCompactDiskReadOnlyMemoryなどの記録媒体に格納されて、あるいはネットワークなどを介して流通する。本発明の第1の実施の形態に係るプログラムは、他のプログラムの一部に組み込まれて提供されるものであってもよい。この場合でも、本発明の第1の実施の形態に係るプログラム自体は、上記のような組み込み先の他のプログラムが有するモジュールを含んでおらず、当該他のプログラムと協働して処理が実行される。すなわち、本発明の第1の実施の形態に係るプログラムとしては、このような他のプログラムに組み込まれた形態であってもよい。なお、代替的に、プログラムの実行により提供される機能の一部または全部を専用のハードウェア回路として実装してもよい。図4は、本発明の第1の実施の形態に係る情報処理装置の概略構成図である。図4を参照して、情報処理装置201は、演算処理部であるCPUCentralProcessingUnit101と、メインメモリ102と、ハードディスク103と、入力インターフェイス104と、表示コントローラ105と、データリーダ/ライタ106と、通信インターフェイス107とを備える。これらの各部は、バス121を介して、互いにデータ通信可能に接続される。CPU101は、ハードディスク103に格納されたプログラムコードをメインメモリ102に展開し、これらを所定順序で実行することにより、各種の演算を実施する。メインメモリ102は、典型的には、DRAMDynamicRandomAccessMemoryなどの揮発性の記憶装置であり、ハードディスク103から読み出されたプログラムに加えて、各種の演算処理結果を示すデータなどを保持する。また、ハードディスク103は不揮発性の磁気記憶装置であり、CPU101で実行されるプログラムに加えて、各種設定値などが格納される。このハードディスク103にインストールされるプログラムは、後述するように、記録媒体111に格納された状態で流通する。なお、ハードディスク103に加えて、あるいはハードディスク103に代えて、フラッシュメモリなどの半導体記憶装置を採用してもよい。入力インターフェイス104は、CPU101とキーボード108、マウス109および図示しないタッチパネルなどの入力部との間のデータ伝送を仲介する。すなわち、入力インターフェイス104は、ユーザが入力部を操作することで与えられる操作指令などの外部からの入力を受付ける。表示コントローラ105は、表示部の典型例であるディスプレイ110と接続され、ディスプレイ110での表示を制御する。すなわち、表示コントローラ105は、CPU101による画像処理の結果などをユーザに対して表示する。ディスプレイ110は、たとえばLCDLiquidCrystalDisplayまたはCRTCathodeRayTubeである。データリーダ/ライタ106は、CPU101と記録媒体111の間のデータ伝送を仲介する。すなわち、記録媒体111は、情報処理装置201で実行されるプログラムなどが格納された状態で流通し、データリーダ/ライタ106は、この記録媒体111からプログラムを読み出す。また、データリーダ/ライタ106は、CPU101の内部指令に応答して、情報処理装置201における処理結果などを記録媒体111へ書き込む。なお、記録媒体111は、たとえば、CFCompactFlashおよびSDSecureDigitalなどの汎用的な半導体記憶デバイス、フレキシブルディスクFlexibleDiskなどの磁気記憶媒体、またはCD-ROMCompactDiskReadOnlyMemoryなどの光学記憶媒体である。通信インターフェイス107は、CPU101と他のパーソナルコンピュータおよびサーバ装置などの間のデータ伝送を仲介する。通信インターフェイス107は、典型的には、イーサネット登録商標またはUSBUniversalSerialBusの通信機能を有する。なお、記録媒体111に格納されたプログラムを情報処理装置201にインストールする形態に代えて、通信インターフェイス107を介して配信サーバなどからダウンロードしたプログラムを情報処理装置201にインストールしてもよい。また、情報処理装置201には、必要に応じてプリンタなどの他の出力装置が接続されてもよい。[制御構造]次に、情報処理装置201におけるインデックス作成機能およびデータ検索機能を提供するための制御構造について説明する。図5は、本発明の第1の実施の形態に係る情報処理装置が提供する制御構造を示すブロック図である。図5に示すCPU101における各ブロックは、ハードディスク103に格納されたプログラムコードなどをメインメモリ102に展開して、CPU101に実行させることで提供される。なお、図5に示す情報処理装置201の制御構造の一部または全部を専用ハードウェアおよび/または配線回路によって実現してもよい。図5を参照して、情報処理装置201は、その制御構造として、先祖ノード決定部11と、先祖ノード探索部13と、識別子付与部14と、先祖番号変換部15と、先祖頻度変換部17と、識別子変換部18とを備える。また、情報処理装置201は、先祖ノード記憶部12と、先祖番号転置リスト記憶部16と、頻度リスト記憶部19とを備える。これらの記憶部は、図4に示すメインメモリ102またはハードディスク103に相当する。CPU101は、図5に示す各部の他に、多くのユニットによって構成されるのが一般的であるが、説明を簡単にするために、他のユニットについては図示していない。先祖ノード決定部11は、タクソノミと、タクソノミ中の各ノードの検索対象データ集合における頻度分布を示す頻度情報を受けて、各ノードに対して、先祖ノード記憶部12に登録すべき先祖ノードを決定する。先祖ノード記憶部12は、先祖ノード決定部11によって決定された各ノードの先祖ノードを1つ記憶する。先祖ノード探索部13は、あるタグを受けて、先祖ノード記憶部12を参照し、当該タグの上位ノードである先祖ノードをすべて取り出す。識別子付与部14は、1つ以上のタグと各タグの頻度とから成る検索対象データを受けて、当該検索対象データに識別子を付与して先祖番号変換部15へ出力する。先祖番号転置リスト記憶部16は、タクソノミ中のノードを指すラベルごとの転置リストを保持する。先祖番号変換部15は、識別子が付与された検索対象データを識別子付与部14から受けて、検索対象データ内のタグごとに、先祖ノード探索部13を利用して先祖ノードの集合を取り出す。そして、先祖番号変換部15は、各タグに対応する先祖ノードの集合をトライ構造として整理し、識別子と、トライ構造と、各タグについての頻度とを先祖頻度変換部17へ出力する。また、先祖番号変換部15は、先祖番号転置リスト記憶部16内の先祖ノードの集合のうち最も上位にあたるノードに対応する転置リストに識別子を追加した上で、追加した位置を覚えておき、当該ノードの次に上位にあたるノードについての転置リストに、直前に覚えておいた先祖ノードについての位置を追加する。そして、先祖番号変換部15は、さらに下位ノードの転置リストについてもこのような処理を繰り返す。先祖頻度変換部17は、識別子と、各タグの先祖ノードをまとめたトライ構造と、各タグについての頻度とを先祖番号変換部15から受けて、各先祖ノードに対応する頻度を計算し、頻度リスト記憶部19内の先祖ノードの集合のうち最も上位にあたるノードに対応する転置リストに頻度を追加した上で、追加した頻度を覚えておき、当該ノードの次に上位にあたるノードについての転置リストにおける頻度と、直前に覚えておいた頻度とを比較し、等しければ0を追加し、そうでなければ当該転置リストにおける頻度をそのまま追加する。そして、先祖頻度変換部17は、さらに下位ノードの転置リストについてもこのような処理を繰り返す。識別子変換部18は、タクソノミ中のノードを指すラベルを外部から受けて、先祖ノード探索部13を用いて当該ノードの先祖ノードの集合を取り出した上で、当該ラベルが指すノードに対応する転置リストを先祖番号転置リスト記憶部16から取り出す。そして、識別子変換部18は、転置リスト中の各整数値が示す先祖番号転置リスト記憶部16内の位置と、頻度リスト記憶部19内の位置とを参照しながら識別子および対応の頻度の組を作成し、作成された識別子を頻度順に並べ替えた上で、出力する。次に、先祖ノード記憶部12、先祖番号転置リスト記憶部16、および頻度リスト記憶部19内のデータ構造について説明する。図6は、本発明の第1の実施の形態に係る情報処理装置における先祖ノード記憶部に記憶される先祖参照用データの一例を示す図である。図6を参照して、先祖ノード記憶部12は、タクソノミ中の各ノードの先祖ノードを示す情報を保持する。図6は、図2に示すタクソノミに対応する先祖参照用データの例を示している。この先祖参照用データでは、各行が各ノードに対応しており、各ノードの先祖ノードが示されている。なお、先祖ノードを指定しない場合には、空を示す記号としてφを用いる。たとえば、意味クラスAに対する先祖ノードは無く、意味クラスBに対する先祖ノードはAである。また、先祖参照用データでは、実際にはタクソノミに先祖ノードが存在する場合においても、φを示すことがある。たとえば、図2に示すタクソノミでは、ノードCに対する親ノードとしてノードAが存在するが、図6に示す先祖参照用データでは、先祖ノードが無いφが示されている。各ノードに対して各先祖ノードのうちのどのノードを選ぶか、また、先祖ノードを無しとするかの判断は、先祖ノード決定部11が行なう。この処理については後述する。図7は、本発明の第1の実施の形態に係る情報処理装置における先祖番号転置リスト記憶部に記憶される先祖番号転置リストの一例を示す図である。図7を参照して、先祖番号転置リスト記憶部16は、本質的には、各ノードに対応する検索対象データの識別子の列を示す情報を記憶する。しかしながら、先祖番号転置リスト記憶部16は、すべてのノードに対応する識別子の列をそのまま転置リストとして保持するのではなく、先祖参照用データにおいて先祖ノードが登録されているノードについては、先祖ノードに対応する転置リスト中の位置を保持する。たとえば、ノードBに対応する転置リストdBでは、1,2,3,6,7という5つの整数値が記載されている。これらは、ノードBの先祖ノードAに対応する転置リスト中の位置を意味している。たとえば、転置リストdBにおいて、1はノードAに対応するリスト内の1番目の値である識別子1を、2はAに対応するリスト内の2番目の値である識別子23を、3はノードAに対応するリスト内の3番目の値である識別子識別子456を意味する。なお、図7は、先祖番号転置リスト記憶部16が保持する情報を理解しやすいように示した図であり、実際には、先祖番号転置リスト記憶部16は、図7に示すデータをそのまま保持する訳ではない。実際には、先祖番号転置リスト記憶部16は、各転置リストについて、図2に示す圧縮方法を用いて圧縮したデータと、転置リストの長さとを保持する。図8は、本発明の第1の実施の形態に係る情報処理装置における頻度リスト記憶部に記憶される頻度リストの一例を示す図である。図8を参照して、頻度リスト記憶部19は、先祖番号転置リスト記憶部16に記憶された転置リストにおける各ノードについて検索対象データ番号に対応する頻度を記憶する。たとえば、ノードCに対応する頻度リストは2,3,5という値を持つ。これらの値は、図7に示す先祖番号転置リスト記憶部16内のノードCに対応する転置リスト2451,3443,18921と対応している。すなわち、意味クラスCは、検索対象データ2451番内で頻度2を持ち、検索対象データ3443番内で頻度3を持ち、検索対象データ18921番で頻度5を持つ。なお、図8では0という値が存在しているが、前述のように、これは頻度0を表している訳ではなく、図6で示される先祖ノードの頻度と等しいことを意味する。たとえば、意味クラスBの頻度リストの先頭における頻度の値が0となっているため、意味クラスBの検索対象データ1番における頻度は、先祖ノードAの頻度リストの先頭における値4である。[動作]次に、本発明の第1の実施の形態に係る情報処理装置の動作について図面を用いて説明する。本発明の第1の実施の形態では、情報処理装置を動作させることによって、本発明の第1の実施の形態に係るインデックス作成方法およびデータ検索方法が実施される。よって、本発明の第1の実施の形態に係るインデックス作成方法およびデータ検索方法の説明は、以下の情報処理装置201の動作説明に代える。なお、以下の説明においては、適宜図5を参照する。本発明の第1の実施の形態に係る情報処理装置の処理は大きく、タクソノミ登録処理、データ登録処理およびデータ検索処理の3つから成る。[タクソノミ登録処理]図9は、本発明の第1の実施の形態に係る情報処理装置がタクソノミ登録処理を行なう際の動作手順を示すフローチャートである。図9を参照して、情報処理装置201は、タクソノミおよびデータ分布が先祖ノード決定部11へ入力されると、タクソノミ登録処理を開始する。ここで、データ分布とは、タクソノミ中の各ノードに関連するデータ数の予測値であり、以降の説明では、ノードXに対応するデータ数の予測値をfreqXとする。先祖ノード決定部11は、まず、各ノードに対して次の処理を順に行なう。まず、ノードXに対して、タクソノミを辿ることにより、先祖ノードのリストを収集するRT01。ここで、タクソノミはDAGであるため、先祖ノードの収集処理は、深さ優先探索または幅優先探索によって実現可能である。次に、先祖ノード決定部11は、先祖ノードのリストのうち、先祖ノード記憶部12に登録する先祖ノードの候補を選ぶRT02。この処理では、先祖ノード決定部11は、ノードXの各先祖ノードYに対して以下のような演算を実行する。csompY、X=entopyAll、freqX-entopyfreqY,freqXここで、Allは、ユーザが想定するデータ集合の数を意味する定数である。また、entopym,nは、m個のデータ集合中のn個を取り出す転置リストを作成する場合のデータ長の下限を意味する。なお、entopym,nは、次の式によって算出することが可能である。entopym,n=n×logm/nm-n×logm/m-nこれにより、entopyAll,freqXは、ノードXを通常の転置リストとして表現した場合のデータ長、entopyfreqY,freqXは、ノードXを先祖ノードYの転置リストを参照して表現した場合のデータ長を意味する。よって、compY,Xは、Xの先祖ノードとしてノードYを選んだときに圧縮可能なデータ長を表現している。先祖ノード決定部11は、compY,Xが閾値σより小さい先祖ノードを排除することで、先祖ノードの候補を選ぶ。次に、先祖ノード決定部11は、先祖ノード候補が1つ以上存在していればRT05でYES、先祖ノードのリストをスコアリングし、スコアが最大になる先祖ノードを1つ決定するRT03。このスコアリングでは、より上位の先祖ノードであり、かつ、データ長が小さくなりそうな先祖ノードに高い得点を付ける。ここで、具体的なスコアリングの例として、AncScoreを定義する。ノードXの先祖ノードYに対応するスコアAncScoreは、次の式によって算出される。AncScoreY,X=α×disX,Yβ×1/entopyfreqY,freqXここで、α、βは定数であり、それぞれ、検索速度を重視する度合い、およびデータ量を重視する度合いを意味する。また、disX,Yは、ノードYからノードXに到達するために辿るエッジの数を意味する。すなわち、disX,Yが大きくなればなるほど、より上位の先祖ノードを選ぶことができ、検索時のコストが減る。先祖ノード決定部11は、各先祖ノード候補の中からスコアAncScoreY,Xが最大になるノードYを取り出し、ノードXおよび先祖ノードYのペアを先祖ノード記憶部12に挿入する。一方、先祖ノード決定部11は、先祖ノード候補が1つも存在していなければRT05でNO、先祖ノードは存在しないものとして、ノードXおよびφを先祖ノード記憶部12に保存するRT04。なお、ここでは、データ分布およびAllといった情報が得られる場合に、データ量を計算することで効率良く先祖を選ぶ方法を用いた。しかしながら、データ分布およびAllが得られない場合、各ノードに対して単に親ノードを1つ選ぶといった方法を用いても良い。また、ここでは、検索速度およびデータ量から先祖ノードを選択しているが、各ノードに対するユーザの問い合わせ頻度がわかっている場合には、問い合わせ頻度が高い先祖ノードを選ぶ、といった別の基準に置き換えてもよいし、または、別の基準を追加しても良い。[データ登録処理]次に、データ登録処理を説明する。図10は、本発明の第1の実施の形態に係る情報処理装置がデータ登録処理を行なう際の動作手順を示すフローチャートである。図10を参照して、情報処理装置201は、識別子付与部14へ1つ以上のタグおよび当該タグの頻度を持つデータが入力されると、データ登録処理を開始する。まず、識別子付与部14は、内部にカウンターを持ち、データが入力されるたびにカウンターに1を追加し、その値を識別子としてデータに付与するRD01。そして、識別子付与部14は、識別子と1つ以上のタグと各タグの頻度とを先祖番号変換部15に出力する。先祖番号変換部15は、識別子付与部14から受けた各タグについて次の作業を行なう。すなわち、先祖番号変換部15は、まず、先祖ノード探索部13にタグXを渡し、タグXの先祖ノードの集合を先祖ノード探索部13から取り出すRD02。図11は、先祖ノード探索部が先祖ノード集合の算出処理を行なう際の動作手順を示すフローチャートである。図11を参照して、先祖ノード探索部13は、まず、一時変数nodeにタグXを代入し、出力リストancListを空の状態で初期化するRD021。次に、先祖ノード探索部13は、先祖ノード記憶部12を参照してnodeの先祖ノードを取り出し、node.ancとする。次に、先祖ノード探索部13は、node.anc=φでない場合にはRD022でfalse、nodeをancListに追加し、nodeにnodeの先祖ノードを代入しRD024、再びnode.ancの判定処理を行なうRD022。一方、先祖ノード探索部13は、node.anc=φの場合にはRD022でtrue、nodeをancListに追加し、ancListを出力するRD023。以上の処理により、先祖ノード探索部13は、指定されたタグと当該タグの上位にあるすべての先祖ノードとを取り出すことができる。たとえば、図2に示すタクソノミのタグLが入力として与えられ、図6に示す情報が先祖ノード記憶部12に保持されている場合、先祖ノード探索部13は、{L,B,A}という3つのノードを先祖番号変換部15に返す。再び図10を参照して、次に、先祖番号変換部15は、各タグの先祖ノードのリストをすべて調べ、共通する先祖ノードをまとめたトライ木すなわち前述のトライ構造を構築するRD03。図12は、先祖番号変換部が構築するトライ木の一例を示す図である。図12を参照して、このトライ木は、3つのタグL,N,Oにそれぞれ対応する先祖ノードのリスト{L,B,A},{N,B,A},{O,C}をまとめたトライ木である。このトライ木の要素は、各先祖ノードのラベルであり、3つの先祖ノードリスト中の共通の先祖をまとめた形になっている。このトライ木の構築アルゴリズムを説明するために、再帰的関数insertTrieを定義する。図13は、再帰的関数insertTrieの処理手順を示すフローチャートである。図13を参照して、再帰的関数insertTrieでは、トライ木中の要素tnodeと、1つの先祖ノードリストlistとを入力とし、処理が開始される。insertTrieでは、まず、与えられたlistの中身を調べRD031、listが空であればRD031でtrue、何もせず処理を終了するRD036。一方、listの中身が空で無ければRD031でfalse、listの最後のラベルを取り出し、トライ木中の要素tnodeの子要素のうち、当該ラベルを持つ子要素cnodeを取り出すRD032。次に、ラベルを持つ子要素cnodeが有ればRD033でfalse、cnodeおよびlistを引数として、RD031~RD034に示す処理と同じ処理を行なうRD035。一方、ラベルを持つ子要素が無ければRD033でtrue、当該ラベルを要素としたcnodeを作成し、要素tnodeの子要素としてcnodeを追加しRD034、cnodeおよびlistを引数として、RD031~RD034に示す処理と同じ処理を行なうRD035。図14は、先祖番号変換部がトライ木の構築処理を行なう際の動作手順を示すフローチャートである。図14を参照して、先祖番号変換部15は、まず、トライ木のルート要素rootを作成するRD041。次に、先祖番号変換部15は、ルート要素root、および各タグの先祖ノードリストlistに対して再帰的関数insertTrieを呼び出すRD042。以上の処理により、各先祖ノードリストはルート要素rootの子孫として追加され、図12に示すようなトライ木を構築することができる。再び図10を参照して、次に、先祖番号変換部15は、トライ木および識別子に基づいて、先祖番号転置リスト記憶部16内の転置リストの更新処理を行なうRD04。この処理を説明するために、再帰的関数insertNodenode,intnumberを定義する。図15は、再帰的関数insertの処理手順を示すフローチャートである。図15を参照して、関数insertは、トライ木中の要素を意味するnode、および整数値numberという2つの引数を持つ。再帰的関数insertでは、まず、nodeで指定されるノードに対応する先祖番号転置リスト記憶部16内の転置リストについて、当該転置リストの最後にnumberを追加し、追加した時点における転置リストの長さ、すなわちnumberの追加位置を取り出してposとするRDI01。次に、nodeのトライ木における各子ノードすなわちchildについて、posを追加する関数処理insertchild,posを呼び出す。これにより、各子要素の転置リストに、nodeで指定される現在の要素の追加位置の情報posが追加されるRDI02。再び図10を参照して、先祖番号変換部15は、トライ木におけるrootの各子要素rchildに対して、insertrchild,識別子を呼び出すことにより、先祖番号転置リスト記憶部16内の転置リストの更新処理を行なうRD04。また、先祖番号変換部15は、転置リストの更新処理RD04と並行して、トライ木と、識別子と、各タグの頻度とを先祖頻度変換部17へ出力する。次に、先祖頻度変換部17は、先祖番号変換部15から受けたトライ木および各タグの頻度に基づいて先祖ノードの頻度の計算を行なうRD05。図16は、先祖頻度変換部が行なうトライ木における頻度の計算結果を示す図である。図16を参照して、先祖頻度変換部17は、トライ木の葉ノードから親方向に辿りながら、各ノードの子ノードが持つ頻度の和を計算することにより、先祖ノードの頻度の計算を行なう。たとえば、図12に示すトライ木と、タグLの頻度3、タグNの頻度2およびタグOの頻度1とが得られた場合には、先祖頻度変換部17は、タグBの頻度5、タグAの頻度5およびタグCの頻度1を算出する。再び図10を参照して、次に、先祖頻度変換部17は、頻度リストの更新を行なうRD06。この処理を説明するために、再帰的関数insertFreqを定義する。図17は、再帰的関数insertFreqの処理手順を示すフローチャートである。図17を参照して、再帰的関数insertFreqは、トライ木中のノードを意味するnode、および頻度を示す整数値freqという2つの引数を持つ。再帰的関数insertFreqでは、まず、nodeで指定されるノードおよび当該ノードの頻度freqを頻度リスト記憶部19に追加するRDIF01。さらに、トライ木におけるnodeの各子ノードchildに対して、nodeの頻度freqと、子ノードの頻度child.freqとを比較し、等しい場合、insertFreqchild,0を呼び出すことにより、0を頻度として追加する。一方、頻度が等しく無い場合には、insertFreqchild,child.freqを呼び出すことにより、子ノードの頻度をそのまま追加するRDIF02。先祖頻度変換部17は、トライ木におけるrootの各子ノードrchildに対して、insertrchild,rchild.freqを呼び出すことにより、頻度リストの更新を行なうRD06。[データ検索処理]次に、データ検索処理を説明する。図18は、本発明の第1の実施の形態に係る情報処理装置がデータ検索処理を行なう際の動作手順を示すフローチャートである。図18を参照して、情報処理装置201は、識別子変換部18へタクソノミ中のノードを指すラベルが入力されると、データ検索処理を開始する。まず、識別子変換部18は、ラベルが入力されると、先祖ノード探索部13を用いて、当該ラベルが指す指定ノードに対応する先祖ノードのリストを取得するS01。次に、識別子変換部18は、先祖番号転置リスト記憶部16を参照し、指定ノードに対応する転置リストを整数列として読み出すS02。次に、識別子変換部18は、頻度リスト記憶部19を参照し、指定ノードに対応する頻度リストを整数列として読み出すS03。次に、識別子変換部18は、先祖ノードリスト、転置リストおよび頻度リストに基づいて、識別子および頻度の組のリストを作成する。より詳細には、識別子変換部18は、長さnの転置リスト、および頻度リスト中の各値の組に対して、関数transによる処理を行なうS04。図19は、関数transの処理手順を示すフローチャートである。図19では、ノードXに対応する先祖ノードリストancList、転置リスト中の値inv[i]0<i<=n、頻度リスト中の値hit[i]0<i<=nを引数とする、関数transinv[i],hit[i],ancListの処理手順が示されている。図19を参照して、関数transでは、まず、一時変数posにinv[i]を代入し、一時変数freqにhit[i]を代入するS041。次に、ancList中の先祖ノードを下位のノードから順に参照し、各先祖ノードancに対して、次のような処理を行なう。すなわち、まず、freqの値が0である場合には、関数selectFreqpos,ancによる処理を行なう。ここで、関数selectFreqpos,ancでは、頻度リスト記憶部19中のノードancに対応する頻度リストのうち、pos番目の値を取り出す処理を行なう。頻度リスト記憶部19において、たとえば頻度リストはL個のブロックに分割した上で保存されているため、たかだかL回の復号処理を行なうだけで頻度を取り出すことができる。そして、取り出した値は、変数freqに代入される。次に、関数selectpos,ancによる処理を行なう。関数selectpos、ancでは、先祖番号転置リスト記憶部16内に記憶されているノードancの転置リストのうち、pos番目の値を取り出す処理を行なう。ここで、転置リストは、前述のようにL個ごとのブロックに分割した上で差分圧縮されていることから、転置リストのうち、pos番目の値を取り出すためには、たかだかL回の復号および足し算を行なえば良い。このような処理をすべての先祖ノードに対して行った後、posを識別子すなわちデータ番号とし、freqを頻度として出力するS043。再び図10を参照して、次に、識別子変換部18は、識別子を頻度順に並べ替え、検索結果として出力するS05。なお、本発明の第1の実施の形態に係る情報処理装置では、識別子変換部18は、識別子を頻度順に並べ替えて出力する構成であるとしたが、情報処理装置201は、各識別子に対応する何らかの評価値を外部に持ち、頻度および評価値に基づいて識別子を並べ替える構成であってもよい。次に、本発明の第1の実施の形態に係る情報処理装置によって奏する効果をより具体的に説明する。本発明の第1の実施の形態に係る情報処理装置では、タクソノミ中のノードに対応する転置リストにおいて、識別子の列を記憶するのではなく、当該ノードの上位ノードである先祖ノードの転置リスト中の位置を記憶する。これにより、データ量が小さく、検索も高速となるインデックスを実現している。まず、ここでは、タクソノミ登録処理により、図2に示すタクソノミが登録され、図6に示す先祖ノードが登録されたことを想定する。さらに、データ登録処理により、図1aに示す転置リストで表現されたデータが登録されたとき、先祖番号転置リスト記憶部16には、図7に示す転置リストが、差分圧縮された形で保持される。図7に示す転置リストに注目して見ると、図6に示す先祖ノードリストにおいて先祖ノードがφになっているノードAおよびCでは、これらのノードに対応する識別子がそのまま入っているが、それ以外の転置リストは、図1bに示す転置インデックスに比べ、各要素間の差分が小さくなっており、高い率の圧縮が可能となっている。次に、本発明の第1の実施の形態に係る情報処理装置による検索が高速であることを説明するため、データ検索処理について述べる。識別子変換部18に、ノードBを示すラベルが入力されたとする。このとき、識別子変換部18は、図7に示す転置リストおよび図8に示す頻度リストの中から、それぞれdBに対応する行を取り出す。また、識別子変換部18は、ノードBの先祖ノードに対応する転置リストとして、図7に示す転置リストからノードAに対応する行を取り出す。また、識別子変換部18は、dBに対応する行の各データと先祖ノードAの転置リストとを照合し、1,23,456,12000,16333という識別子の列と、4,1,3,2,5という頻度の列とを取り出すことができる。以上の処理のステップ数は、識別子列の長さに対して定数倍であることから、データ検索を高速に実現することが可能である。さらに、識別子変換部18は、取り出した識別子の列を、16333,1,456,12000,23のように頻度順に並べ替え、指定ノードと関連の強いデータから順番に返すことが可能である。また、図9に示すタクソノミ登録処理におけるパラメータα、β、γを調整することにより、先祖ノードの選択方法を変えることができる。たとえば、γを小さく設定することで、図6に示すノードCに対応する先祖ノードをφではなく、ノードAとして登録することを考える。このとき、先祖番号転置リスト記憶部16に記憶される情報は、以下の図20に示す転置リストになる。図20は、本発明の第1の実施の形態に係る情報処理装置における先祖番号転置リスト記憶部に記憶される先祖番号転置リストの一例を示す図である。図20を参照して、この転置リストにおける整数列は、図7に示す転置リストに対して、ノードCに対応する整数列における各値の差分がさらに小さくなっており、当該差分の圧縮をすることにより、転置リストのデータ量をさらに小さくすることができる。ただし、この設定では、ノードCに対する問い合わせを行なう場合、ノードAの転置リストを参照しなければならない。このため、図7に示す転置リストの場合に比べ、検索処理に時間がかかる。このように、α、β、γを調整することにより、データサイズおよび検索速度のバランスを調整することが可能である。以上のように、本発明の第1の実施の形態に係るデータ構造は、検索対象データに関するタグを有するタクソノミにおいて、タクソノミにおける各ノードから到達可能な検索対象データの集合を取り出すためのデータ構造である。そして、データ構造は、先祖参照用データと、転置リスト用データすなわち先祖番号転置リストとを備える。この先祖参照用データは、タクソノミにおいて、各ノードの上位ノードである先祖ノードを示す。そして、転置リスト用データは、各ノードの転置リストを含み、各ノードのうち、先祖参照用データにおいて先祖ノードが登録されているノードの転置リストは、登録された先祖ノードに対応する転置リスト中の位置を示す整数値のリストである。さらに、転置リスト用データでは、各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、ブロックにおける整数値と整数値の直前の整数値との差分値が可変長整数コードのビット列に変換されている。また、本発明の第1の実施の形態に係るインデックス作成装置は、検索対象データに関するタグを有するタクソノミにおいて、タクソノミにおける各ノードから到達可能な検索対象データの集合を取り出すために用いる転置リストを作成する。そして、インデックス作成装置では、各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、ブロックにおける整数値と整数値の直前の整数値との差分値が可変長整数コードのビット列に変換されている。そして、先祖ノード決定部11は、タクソノミにおけるノードごとに、ノードの上位ノードである先祖ノードを1つ選択し、選択した先祖ノードを示す先祖参照用データを生成する。先祖ノード探索部13は、先祖参照用データに基づいて、タクソノミにおけるタグの1または複数の先祖ノードを示す先祖ノードリストを生成する。そして、先祖番号変換部15は、検索対象データの識別子を受けて、先祖ノードリストにおける各ノードのうち最上位のノードについては、識別子を対応の転置リストの要素として追加し、最上位ノード以外のノードについては、対応の転置リストの要素として、識別子の代わりに、ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値を追加する。また、本発明の第1の実施の形態に係るデータ検索装置は、検索対象データに関するタグを有するタクソノミにおいて、タクソノミにおける指定された指定ノードから到達可能な検索対象データの集合を取り出す。そして、データ検索装置では、先祖番号転置リスト記憶部16は、転置リスト用データを記憶する。この転置リスト用データは、タクソノミにおける各ノードの転置リストを含み、各ノードのうち、最上位のノードの転置リストは、検索対象データの識別子を示す整数値のリストであり、最上位ノード以外のノードの転置リストは、識別子の代わりに、ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値のリストである。さらに、転置リスト用データでは、各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、ブロックにおける整数値と整数値の直前の整数値との差分値が可変長整数コードのビット列に変換されている。そして、識別子変換部18は、指定ノードを示す情報を受けて、転置リスト用データに基づき、指定ノードに対応する転置リストの整数値が示す位置に対応する、指定ノードの上位ノードに対応する転置リストの整数値を取り出す処理を、最上位ノードに対応する転置リストの識別子を取り出すまで繰り返すことにより、指定ノードに対応する検索対象データの識別子のリストを作成する。このように、タクソノミにおける各ノードの転置リストを、先祖ノードの転置リスト中の位置で表現することにより、転置リストにおける整数列の差分を短くすることが可能である。これにより、当該差分を可変長整数コードで表現することでデータ長が小さい転置リストを作成することができる。さらに、検索時においては、あるノードに対応する転置リストを検索対象データの識別子の列に変換するために、たかだかグラフ木構造の高さ個の先祖ノードに対応する転置リストを参照すれば良くなる。この参照処理は、通常、高速であり、指定ノードが上位のノードになればなるほど少ない処理で済む。具体的には、通常、すべてのノードに対して転置インデックスを作成する場合、図1bに示すような識別子の列を保持する必要がある。これに対して、本発明の第1の実施の形態に係るデータ検索装置では、転置インデックスは、図7に示すような識別子の列を保持すれば良い。図7に示す識別子列は、図1bに示す識別子列に比べて、小さい値で構成されているため、これらの値の差分をとって可変長整数コードにより圧縮する処理を加えることで当該転置インデックスを大幅に圧縮することが可能である。また、たかだか識別子列の長さ×先祖ノードの数×L回の参照を行なうだけで、上位ノードに対する問い合わせを行なうことが可能となる。すなわち、本発明の第1の実施の形態に係るデータ検索装置では、タクソノミ中の各ノードに対応する転置インデックスをコンパクトに表現しつつ、タクソノミ中の上位のノードに対する問い合わせを高速に行なうことができる。また、タクソノミ中の上位のノードに対する問い合わせを高速に実現可能なコンパクトなデータ構造を実現することができる。したがって、使用データ量をコンパクトに押さえつつ、タクソノミ中の上位ノードである意味クラスに対する問い合わせを高速に実現可能である。このように、本発明の第1の実施の形態に係るデータ構造における各構成要素のうち、先祖参照用データおよび転置リスト用データからなる最小構成により、検索処理のためのデータ容量の低減および検索処理の高速化を図る、という本発明の目的を達成することが可能となる。また、本発明の第1の実施の形態に係るインデックス作成装置における各構成要素のうち、先祖ノード決定部11、先祖ノード探索部13および先祖番号変換部15からなる最小構成により、検索処理のためのデータ容量の低減および検索処理の高速化を図る、という本発明の目的を達成することが可能となる。また、本発明の第1の実施の形態に係るデータ検索装置における各構成要素のうち、先祖番号転置リスト記憶部16および識別子変換部18からなる最小構成により、検索処理のためのデータ容量の低減および検索処理の高速化を図る、という本発明の目的を達成することが可能となる。なお、特許文献1には、検索語を木構造に変換することにより、検索処理を効率化する構成が開示されているが、本発明の第1の実施の形態に係る情報処理装置では、検索に用いるインデックスを木構造に変換することでインデックス全体を圧縮する構成であり、特許文献1に記載の構成とまったく異なるものである。また、本発明の第1の実施の形態に係るインデックス作成装置では、先祖ノード決定部11は、先祖ノードに対応するデータ分布に基づいて、各ノードに対する先祖ノードを決定する。すなわち、先祖ノード決定部11は、タクソノミにおける各ノードが所定のデータ集合内でどの程度の頻度を持つか、あるいは持ちそうかを示す頻度分布を受けて、タクソノミにおけるノードごとに、ノードの各先祖ノードに対応する頻度に基づいて、各先祖ノードを選んだ場合における対応の転置リストのデータ長を計算し、各先祖ノードのうち、データ長が小さい先祖ノードおよびタクソノミにおいてより上位の先祖ノードを優先して選択する。このような構成により、検索速度およびデータ量のバランスを調整しながら転置インデックスを作成することができる。また、本発明の第1の実施の形態に係るデータ検索装置では、各ノードに対応する転置リストを記憶するだけでなく、頻度リストを記憶する。すなわち、頻度リスト記憶部19は、タクソノミにおける各ノードの、各検索対象データに対応する頻度を示す頻度リストを記憶する。そして、識別子変換部18は、さらに、指定ノードに対応する1または複数の検索対象データの識別子のリストにおいて、頻度リストに基づいて識別子をソートする。このような構成により、検索結果として単に識別子を返すのではなく、頻度に基づいたランキングを返すことが可能である。また、本発明の第1の実施の形態に係るデータ構造は、タクソノミ中のあるノードの頻度リストを表現する際に、当該ノードの頻度リストと当該ノードの先祖ノードの頻度リストとを比較し、同じ頻度を持つ場合に短い符号を与えた頻度データを備える。このような構成により、データ長が小さい頻度リストを作成することができる。次に、本発明の他の実施の形態について図面を用いて説明する。なお、図中同一または相当部分には同一符号を付してその説明は繰り返さない。<第2の実施の形態>本実施の形態は、第1の実施の形態に係る情報処理装置と比べて複数のノードが指定された場合の処理の効率化を図る情報処理装置に関する。以下で説明する内容以外は第1の実施の形態に係る情報処理装置と同様である。図21は、本発明の第2の実施の形態に係る情報処理装置が提供する制御構造を示すブロック図である。図21を参照して、情報処理装置202は、本発明の第1の実施の形態に係る情報処理装置と比べて、識別子変換部18の代わりに複数識別子変換部28を備える。複数識別子変換部28は、タクソノミ中の2つ以上の指定ノードを受けて、指定ノードごとに、先祖ノード探索部13を用いて先祖ノードリストを取り出す。複数識別子変換部28は、各指定ノードについて、共通の先祖ノードをまとめたトライ木を作成する。そして、複数識別子変換部28は、作成したトライ木を深さ優先探索しながら、各指定ノードすべてと関連する検索対象データ集合を示す識別子のリストを作成する。図22は、本発明の第2の実施の形態に係る情報処理装置がデータ検索処理を行なう際の動作手順を示すフローチャートである。図22を参照して、情報処理装置201は、複数識別子変換部28へタクソノミ中の複数のノードを示す情報が入力されると、データ検索処理を開始する。まず、複数識別子変換部28は、入力された複数の指定ノードに対して、先祖ノード探索部13を用いて、それぞれの先祖ノードのリストを取得するJ01。この処理は、本発明の第1の実施の形態における処理S01と同じ処理である。次に、複数識別子変換部18は、各指定ノードの先祖ノードのリストのうち、共通する先祖ノードをまとめたトライ木を構築するJ02。この処理は、本発明の第1の実施の形態における処理RD03と同じ処理である。次に、複数識別子変換部18は、構築したトライ木において、深さ優先探索を行いながらJOIN処理を繰り返すことにより、得られた結果を検索結果として出力するJ03。ここで、処理J03について詳しく述べる。この処理では、トライ木において、深さ優先探索を行いながら、図23および図24に示す2つの処理node-inおよびnode-outを実施する。ここで、トライ木のルートを起点とした深さ優先探索において、処理node-inは、ノードに入るときに実施される処理であり、処理node-outは、ノードを出るときに実施される処理である。図23は、処理node-inの手順を示すフローチャートである。図23を参照して、処理node-inでは、まず、新しく入るノードである対象ノードに対応するバッファリストを作成するJ031。ここで、バッファリストとは、整数列を一時的に保持するためのリストである。次に、対象ノードがトライ木中の葉ノードである場合にはJ032でYES、対象ノードに対応する転置リストを先祖番号転置リスト記憶部16から読み出し、読み出した転置リストの整数列を対象ノードのバッファリストに追加するJ033。一方、対象ノードがトライ木中の葉ノードでない場合にはJ032でNO、当該トライ木中の各子ノードに対して探索処理を続け、すべての子を辿り終えた時点で処理を終了するJ034。図24は、処理node-outの手順を示すフローチャートである。図24を参照して、処理node-outでは、まず、出ようとする対象ノードがトライ木中の葉ノードでない場合には、対象ノードのバッファリストおよび対象ノードに対応する転置リストに基づいて、バッファリスト内の整数列を変換する処理を行なうJ036。この処理は、対象ノードnode、およびバッファリスト内の各値posに対して、前述の関数selectpos,nodeを実施することで行われる。次に、トライ木における対象ノードの親ノードが保持するバッファリストが空かどうかを調べJ037、空である場合にはJ037でYES、親ノードのバッファリストに、対象ノードのバッファリストを追加する処理を行なうJ038。一方、空でない場合にはJ037でNO、親ノードのバッファリストにある整数列と対象ノードのバッファリストにある整数列とを比較し、JOIN処理すなわち両方に含まれる整数値だけを残す処理を行なうJ039。図25は、本発明の第2の実施の形態に係る情報処理装置における深さ優先探索の処理手順の具体例を示す図である。図25を参照して、図2に示すタクソノミに対して、入力ノードとして、L,N,Oという3つのノードが指定された状況を想定する。図25では、これらの入力ノードから作成されるトライ木が示されており、また、P0~P13は、このトライ木に対する探索順を示している。まず、rootのバッファリストが作成されるP0。次に、ノードAが探索され、ノードAのバッファリストが作成されるP1。次に、ノードBが探索され、ノードBのバッファリストが作成されるP2。次に、ノードLが探索され、ノードLの転置リストが読み込まれるP3。次に、ノードBに戻り、ノードLの転置リストがノードBのバッファリストに追加されるP4。次に、ノードNが探索され、ノードNの転置リストが読み込まれるP5。次に、ノードBに戻り、ノードBのバッファリストおよびノードNの転置リストがJOIN処理されるP6。次に、ノードAに戻り、ノードBのバッファリストがノードBの転置リスト中の値に変換され、ノードAのバッファリストに追加されるP7。次に、rootに戻り、ノードAのバッファリストがノードAの転置リスト中の値に変換され、rootのバッファリストに追加されるP8。次に、ノードCが探索され、ノードCのバッファリストが作成されるP9。次に、ノードOが探索され、ノードOの転置リストが読み込まれるP10。次に、ノードCに戻り、ノードOの転置リストがノードCのバッファリストに追加されるP11。次に、rootに戻り、ノードCのバッファリストがノードCの転置リスト中の値に変換され、rootのバッファリストとJOIN処理されるP12。次に、rootのバッファリストが出力されるP13。以上の処理により、ノードL,N,Oのすべてに関連する検索対象データの識別子の列を作成し、出力することができる。以上のように、本発明の第2の実施の形態に係るデータ検索装置は、タクソノミにおける複数のノードが指定された場合には、各指定ノードのいずれからも到達可能な検索対象データの集合を取り出す。そして、データ検索装置では、複数識別子変換部28は、タクソノミにおける複数のノードが指定された場合には、各指定ノードに対応する転置リストを先祖番号転置リスト記憶部16から取得し、指定ノードに対応する転置リストの整数値が示す位置に対応する、指定ノードの上位ノードに対応する転置リストの整数値を取り出す処理を行なう際に、指定ノードの組で共通の上位ノードのうち、タクソノミにおいて最も下位の上位ノードである共通先祖ノードに対応する転置リストにおける整数値を取り出すとき、指定ノードの組において共通の整数値を取り出す。そして、複数識別子変換部28は、取り出した整数値を用いて、複数の指定ノードに対応する検索対象データの識別子のリストを作成する。このような構成により、複数のノードをキーとするAND検索において、JOIN演算を効率的に行なうことが可能となる。すなわち、本発明の第1の実施の形態に係る情報処理装置を用いてAND検索を行なう場合には、入力された複数の指定ノードに対応する転置リストを識別子の列に変換するために、各指定ノードの転置リストが参照する先祖ノードの転置リストをすべて参照した上で、JOIN処理を行なう必要がある。たとえば、L,N,Oという3つの指定ノードを入力とし、各指定ノードが100個の検索対象データと関係を持つ場合、合計300個の整数についてそれぞれすべての先祖ノードにおける転置リストの位置を調べ、識別子へ変換する必要がある。これに対して、本発明の第2の実施の形態に係る情報処理装置では、指定ノードの組の共通の先祖ノードのうち、最下位の先祖ノードに対応する転置リスト中の番号に指定ノードの値を変換した時点でJOIN処理を行なう。これにより、効率の良い参照が可能となる。たとえば、L,N,Oという3つの指定ノードを入力とし、各指定ノードが100個の検索対象データと関係を持つ場合であっても、すべての先祖ノードにおける転置リストの位置を調べる必要がなくなる。この例を具体的に説明するため、ノードLとノードNのJOIN処理のみに注目する。図25に示すように、ノードLとノードNのJOIN処理は、各々の転置リストを識別子に変換せずに、ノードBに対応する転置リスト中の位置について実施する。このため、ノードBより上位のノードに対応する転置リストを参照する処理は、このJOIN処理の結果に対してのみ行なえば良いことから、効率的に処理が可能である。次に、本発明の第2の実施の形態に係る情報処理装置によって奏する効果をより具体的に説明する。ここでは、図6および図7に示すデータが保持されている際に、複数識別子変換部28に、ノードLとノードNが入力されたとする。このとき、図22に示すデータ検索処理におけるステップJ01の処理により、ノードLに対応する先祖ノードリストとして{L,B,A}が得られる。また、ノードNに対応する先祖ノードリストとして{N,B,A}が得られる。次に、これらの先祖ノードリストに基づいて先祖トライを構築すると、図26に示すような先祖トライが構築されるJ02。図26は、本発明の第2の実施の形態に係る情報処理装置における深さ優先探索の処理手順の具体例を示す図である。次に、図22に示すデータ検索処理におけるステップJ03の処理を行なうと、以下のような処理手順でJOIN処理が行われる。すなわち、まず、rootのバッファリストが作成されるQ0。次に、ノードAが探索され、ノードAのバッファリストが作成されるQ1。次に、ノードBが探索され、ノードBのバッファリストが作成されるQ2。次に、ノードLが探索され、ノードLの転置リスト{1,3,4}が読み込まれるQ3。次に、ノードBに戻り、ノードLの転置リストがノードBのバッファリストに追加されるQ4。次に、ノードNが探索され、ノードNの転置リスト{3}が読み込まれるQ5。次に、ノードBに戻り、ノードBのバッファリストおよびノードNの転置リストがJOIN処理されるQ6。次に、ノードAに戻り、ノードBのバッファリストがノードBの転置リスト中の値{3}に変換され、ノードAのバッファリストに追加されるQ7。次に、rootに戻り、ノードAのバッファリストがノードAの転置リスト中の値すなわち識別子{456}に変換され、rootのバッファリストに追加されるQ8。次に、rootのバッファリストが出力されるQ9。図26において、重要なポイントはステップQ7およびQ9における処理である。ステップQ7およびQ9では、ノードBおよびノードAに対応する転置リストの参照がそれぞれ行われる。このデータの参照は、それぞれ1つの値についてのみ行われる。具体的には、ステップQ7では3を3に変換する処理が行われ、ステップQ9では3を456に変換する処理が行われる。これに対して、通常の処理手順では、ノードLに対応する転置リスト{1,3,4}、およびノードNに対応する転置リスト{3}内の値それぞれについて上位ノードの転置リストを参照しなければならず、処理に時間がかかってしまう。その他の構成および動作は第1の実施の形態に係る情報処理装置と同様であるため、ここでは詳細な説明を繰り返さない。次に、本発明の他の実施の形態について図面を用いて説明する。なお、図中同一または相当部分には同一符号を付してその説明は繰り返さない。<第3の実施の形態>本実施の形態は、第1の実施の形態に係る情報処理装置と比べて検索結果に関連するノードの集合を得る情報処理装置に関する。以下で説明する内容以外は第1の実施の形態に係る情報処理装置と同様である。図27は、本発明の第3の実施の形態に係る情報処理装置が提供する制御構造を示すブロック図である。図27を参照して、情報処理装置203は、本発明の第1の実施の形態に係る情報処理装置と比べて、さらに、子ノード記憶部21と、トップダウン探索部22とを備える。子ノード記憶部21は、先祖ノード記憶部12に記載されている先祖ノードをまとめることにより作成された、各ノードおよび各ノードの仮想的な1つのrootについての子ノードの集合を示す情報を記憶する。図28は、子ノード記憶部21に記憶される情報の一例を示す図である。図28は、図6に示す先祖参照用データが得られる場合における子ノード情報の例を示している。図28を参照して、たとえば、2行目には、ノードAについての子ノードのリストが登録されており、ノードAには、ノードBという子ノードが登録されていることがわかる。また、1行目には、仮想的なルートrootに対応する子ノードとしてノードAおよびノードCが登録されている。図6に示す例では、ノードAおよびノードCが、先祖ノードの存在しない最上位のノードとして登録されている。そして、これらのノードが上位に単一のルートrootを仮想的に持ち、ルートrootの下位に、タクソノミ中の最上位ノードA,Cのリストが存在するものとして、図28に示す子ノードのリストが作成されている。また、トップダウン探索部22は、指定された全検索対象データの部分集合を示す識別子のリストと、整数minとを受けて、先祖番号転置リスト記憶部16内の転置リストを参照しながら、指定された検索対象データの集合内で、min回以上登場するノードのリストを返す。次に、本発明の第3の実施の形態に係る情報処理装置のlist処理について説明する。トップダウン探索部22は、検索対象データの集合を示す識別子のリスト、および整数値minが入力されると、list処理を開始する。この処理では、識別子変換部18において検索処理が行われた後、得られた識別子のリストと、予め設定されたminの値とが入力として呼び出される。なお、これらはユーザまたは外部のプログラムによって呼び出されても良い。トップダウン探索部22は、子ノード記憶部21に記憶されているルートノードを起点として、タクソノミ中のノードをトップダウンに辿り、指定された検索対象データ集合内での頻度がmin以上かどうかを調べる。この際に、トップダウン探索部22は、再帰的関数listを実行する。図29は、再帰的関数listの処理手順を示すフローチャートである。図29を参照して、再帰的関数listは、子ノード記憶部21に記憶されているノードのうち特定のノードを示すnode、検索対象データ集合を表現した整数列input、および閾値minという3つの値を入力として呼び出される。再帰的関数listでは、呼び出されると、まず、先祖番号転置リスト記憶部16から、nodeで指定されるノードに対応する転置リストを読み込み、nListとするL01。次に、nListおよび整数列inputに対して、JOIN処理である関数listJoinを実施するL02。図30は、関数listJoinの処理手順を示すフローチャートである。図30を参照して、listJoinは、入力された2つの整数配列aとbを順に調べ、a,b両方に含まれる数値が登場する整数配列a中の位置のリストを返す関数である。より詳細には、2つの整数配列aおよびbが与えられると、まず、配列a中の位置を示す変数apを0に初期化し、配列b中の位置を示す変数bpを0に初期化し、出力する整数列を示す変数outを空の状態で初期化するL021。次に、apが配列aの長さより小さく、かつ、bpが配列bpの長さより小さい場合にはL022でYES、配列aのap番目と配列bのbp番目とを比較するL023。そして、両者が等しい場合にはL023でYES、同じ数値が発見されたとして、outにapを追加した後、apをインクリメントしL024、apと配列aの長さとの比較およびbpと配列bpの長さとの比較を再び行なうL022。一方、両者が等しくなくL023でNO、配列aのap番目の値が配列bのbp番目の値より大きい場合にはL025でYES、bpをインクリメントしL026、apと配列aの長さとの比較およびbpと配列bpの長さとの比較を再び行なうL022。また、両者が等しくなくL023でNO、配列aのap番目の値が配列bのbp番目の値より小さい場合にはL025でNO、apをインクリメントしL027、apと配列aの長さとの比較およびbpと配列bpの長さとの比較を再び行なうL022。また、apが配列aの長さ以上であるか、またはbpが配列bpの長さ以上である場合にはL022でNO、配列aまたはbの最後まで到達したとして、outを出力して、処理を終了するL028。再び図29を参照して、次に、トップダウン探索部22は、関数listJoinを実施した結果得られた整数列をtempとし、tempの長さを調べるL03。トップダウン探索部22は、tempの長さがmin以上である場合にはL03でYES、nodeが示すノードの子孫にあたる下位ノードも探索すべきであると判断する。トップダウン探索部22は、nodeが示すノードの子孫にあたる下位ノードも探索すべきであると判断すると、子ノード記憶部21を参照し、nodeの子ノードのリストを取得するL04。次に、トップダウン探索部22は、各子ノードcnodeと、現時点での検索対象データを示す整数列tempと、minとを引数として、同じ関数listを呼び出すL05。これにより、子孫ノードに対しても同様の探索が行われる。次に、トップダウン探索部22は、nodeで指定されたノードのラベル、およびtempの長さを頻度として出力するL06。一方、トップダウン探索部22は、tempの長さがmin未満である場合にはL03でNO、処理を終了する。なお、トップダウン探索部22は、list処理を開始する際、子ノード記憶部21に記憶されているルートノードroot、入力された識別子のリストdids、および閾値minを引数として、listroot,dids,minを実行する。次に、本発明の第3の実施の形態に係るデータ検索装置のlist処理を具体的に説明する。ここでは、図6に示す先祖ノード参照用データ、図7に示す転置リスト、および図28に示す子ノード参照データが保持されている場合に、検索対象データの識別子の列として{2451,3443}が入力され、閾値minとして1が入力された場合を想定する。このとき、トップダウン探索部22は、図28に示す子ノード参照データにおけるrootの子ノードAおよびCに対して処理を開始する。ノードAに対しては、図7の1行目に示す転置リストが読み込まれ、関数listJoinによる処理が行われ、listJoindA,{2451,3443}の結果として{4,5}が得られる。{4,5}の長さは2であり、minより大きい。このため、トップダウン探索部22は、さらに、ノードAの子ノードBに対して探索処理を行い、listJoindB,{4,5}を実行する。この結果は空集合となるため、トップダウン探索部22は、ノードB以下のノードに対しては探索処理を行なわず、rootの別の子ノードCに対して同様の処理を行なう。すなわち、トップダウン探索部22は、listJoindC,{2451,3443}を実行し、結果として{1,2}を得る。{1,2}の長さは2であり、minより大きい。このため、トップダウン探索部22は、ノードCの子ノードOに対してlistJoindO,{1,2}を実行し、{1}を得る。以上のような探索処理により、トップダウン探索部22は、指定された検索対象データの集合において、ノードAの頻度が2、ノードOの頻度が1、ノードCの頻度が2、という情報を出力する。以上のように、本発明の第3の実施の形態に係るデータ検索装置では、子ノード記憶部21は、タクソノミにおける各ノードの下位ノードである子ノードの集合を示す子ノード情報を記憶する。トップダウン探索部22は、指定ノードに対応する検索対象データの識別子のリストを受けて、タクソノミにおける各ノードの中から、リストが示す検索対象データの集合において所定値以上の頻度を持つノードを取り出す。そして、トップダウン探索部22は、最上位ノードに対応する転置リストにおける識別子の位置を検出し、子ノード情報に基づいて、検出した位置と最上位ノードの1つ下位のノードに対応する転置リストにおける整数値とを比較し、一致した整数値に基づいてノードの頻度を算出する処理を少なくとも行なう。さらに、トップダウン探索部22は、ノードの下位のノードについて、上位ノードに対応する転置リストにおいて識別子の位置に対応する整数値と、上位ノードの1つ下位のノードに対応する転置リストにおける整数値とを比較し、一致した整数値に基づいて1つ下位のノードの頻度を算出する処理を0回以上行なう。これにより、トップダウン探索部22は、検索対象データにおける各ノードの頻度を算出する。このような構成により、指定された検索対象データ集合において高頻度なノードを効率良く探すことができる。検索対象データ集合において高頻度なノードを探す処理は、クエリ拡張およびファセット検索などに役立つ。たとえば、何らかの検索を行なうことにより得られた検索結果の集合に対してこのようなlist処理を行なうことで、検索結果に関連するノードの集合が得られる。このため、これらのノードの集合を用いてクエリ拡張を行なうこと、およびこれらのノードの集合をファセットとして提示することが可能になる。通常、検索結果に関連するノードの集合を得るためには、タクソノミ中の各ノードに対応する転置リストを先祖番号転置リスト記憶部16から読み込み、各転置リストについて先祖ノードを参照し、識別子の列に変換してからJOIN処理を行っていく必要がある。このような方法では、無駄が多くなるため時間がかかる。これに対して、本発明の第3の実施の形態に係るデータ検索装置では、タクソノミ中のノードをトップダウンに調べながら、各ノードにおいて毎回識別子の列に変換することなくJOIN処理を行なうことができるため、処理効率を向上させることができる。その他の構成および動作は第1の実施の形態に係る情報処理装置と同様であるため、ここでは詳細な説明を繰り返さない。上記実施の形態の一部または全部は以下の付記のようにも記載されうるが、本発明の範囲は、以下の付記に限定されるものではない。[付記1]検索対象データに関するタグを有するタクソノミにおいて、前記タクソノミにおける各ノードから到達可能な検索対象データの集合を取り出すためのデータ構造であって、前記タクソノミにおいて、前記各ノードの上位ノードである先祖ノードを示す先祖参照用データと、前記各ノードの転置リストを含み、前記各ノードのうち、前記先祖参照用データにおいて前記先祖ノードが登録されているノードの転置リストは、登録された前記先祖ノードに対応する転置リスト中の位置を示す整数値のリストであり、さらに、前記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、前記ブロックにおける整数値と前記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換された転置リスト用データとを備える、データ構造。[付記2]検索対象データに関するタグを有するタクソノミにおいて、前記タクソノミにおける各ノードから到達可能な検索対象データの集合を取り出すために用いる転置リストを作成するためのインデックス作成装置であって、前記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、前記ブロックにおける整数値と前記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換されており、前記タクソノミにおけるノードごとに、前記ノードの上位ノードである先祖ノードを1つ選択し、選択した前記先祖ノードを示す先祖参照用データを生成するための先祖ノード決定部と、前記先祖参照用データに基づいて、前記タクソノミにおけるタグの1または複数の先祖ノードを示す先祖ノードリストを生成するための先祖ノード探索部と、前記検索対象データの識別子を受けて、前記先祖ノードリストにおける各前記ノードのうち最上位のノードについては、前記識別子を対応の転置リストの要素として追加し、前記最上位ノード以外のノードについては、対応の転置リストの要素として、前記識別子の代わりに、前記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値を追加するための先祖番号変換部とを備える、インデックス作成装置。[付記3]前記先祖ノード決定部は、前記タクソノミにおける各ノードが所定のデータ集合内でどの程度の頻度を持つか、あるいは持ちそうかを示す頻度分布を受けて、前記タクソノミにおけるノードごとに、前記ノードの各先祖ノードに対応する頻度に基づいて、前記各先祖ノードを選んだ場合における対応の転置リストのデータ長を計算し、前記各先祖ノードのうち、前記データ長が小さい前記先祖ノードおよび前記タクソノミにおいてより上位の前記先祖ノードを優先して選択する、付記2に記載のインデックス作成装置。[付記4]検索対象データに関するタグを有するタクソノミにおいて、前記タクソノミにおける指定された指定ノードから到達可能な検索対象データの集合を取り出すためのデータ検索装置であって、前記タクソノミにおける各ノードの転置リストを含み、前記各ノードのうち、最上位のノードの転置リストは、前記検索対象データの識別子を示す整数値のリストであり、前記最上位ノード以外のノードの転置リストは、前記識別子の代わりに、前記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値のリストであり、さらに、前記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、前記ブロックにおける整数値と前記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換された転置リスト用データを記憶するための先祖番号転置リスト記憶部と、前記指定ノードを示す情報を受けて、前記転置リスト用データに基づき、前記指定ノードに対応する前記転置リストの整数値が示す前記位置に対応する、前記指定ノードの上位ノードに対応する前記転置リストの整数値を取り出す処理を、前記最上位ノードに対応する前記転置リストの前記識別子を取り出すまで繰り返すことにより、前記指定ノードに対応する前記検索対象データの識別子のリストを作成するための識別子変換部とを備える、データ検索装置。[付記5]前記データ検索装置は、さらに、前記タクソノミにおける各ノードの、各検索対象データに対応する頻度を示す頻度リストを記憶するための頻度リスト記憶部を備え、前記識別子変換部は、さらに、前記指定ノードに対応する1または複数の前記検索対象データの識別子のリストにおいて、前記頻度リストに基づいて前記識別子をソートする、付記4に記載のデータ検索装置。[付記6]前記データ検索装置は、前記タクソノミにおける複数のノードが指定された場合には、各前記指定ノードのいずれからも到達可能な検索対象データの集合を取り出し、前記識別子変換部は、前記タクソノミにおける複数のノードが指定された場合には、各前記指定ノードに対応する前記転置リストを前記先祖番号転置リスト記憶部から取得し、前記指定ノードに対応する前記転置リストの整数値が示す前記位置に対応する、前記指定ノードの上位ノードに対応する前記転置リストの整数値を取り出す処理を行なう際に、前記指定ノードの組で共通の前記上位ノードのうち、前記タクソノミにおいて最も下位の上位ノードである共通先祖ノードに対応する前記転置リストにおける整数値を取り出すとき、前記指定ノードの組において共通の前記整数値を取り出し、取り出した前記整数値を用いて、前記複数の指定ノードに対応する前記検索対象データの識別子のリストを作成する、付記4に記載のデータ検索装置。[付記7]前記データ検索装置は、さらに、前記タクソノミにおける各ノードの下位ノードである子ノードの集合を示す子ノード情報を記憶するための子ノード記憶部と、前記指定ノードに対応する前記検索対象データの識別子のリストを受けて、前記タクソノミにおける各ノードの中から、前記リストが示す前記検索対象データの集合において所定値以上の頻度を持つノードを取り出すためのトップダウン探索部とを備え、前記トップダウン探索部は、前記最上位ノードに対応する前記転置リストにおける前記識別子の位置を検出し、前記子ノード情報に基づいて、検出した前記位置と前記最上位ノードの1つ下位のノードに対応する前記転置リストにおける整数値とを比較し、一致した整数値に基づいて前記ノードの頻度を算出する処理を少なくとも行い、さらに、前記ノードの下位のノードについて、上位ノードに対応する前記転置リストにおいて前記識別子の位置に対応する整数値と、前記上位ノードの1つ下位のノードに対応する前記転置リストにおける整数値とを比較し、一致した整数値に基づいて前記1つ下位のノードの頻度を算出する処理を0回以上行なうことにより、前記検索対象データにおける前記各ノードの頻度を算出する、付記4に記載のデータ検索装置。[付記8]検索対象データに関するタグを有するタクソノミにおいて、前記タクソノミにおける各ノードから到達可能な検索対象データの集合を取り出すために用いる転置リストを作成するインデックス作成方法であって、前記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、前記ブロックにおける整数値と前記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換されており、前記タクソノミにおけるノードごとに、前記ノードの上位ノードである先祖ノードを1つ選択し、選択した前記先祖ノードを示す先祖参照用データを生成するステップと、前記先祖参照用データに基づいて、前記タクソノミにおけるタグの1または複数の先祖ノードを示す先祖ノードリストを生成するステップと、前記検索対象データの識別子を受けて、前記先祖ノードリストにおける各前記ノードのうち最上位のノードについては、前記識別子を対応の転置リストの要素として追加し、前記最上位ノード以外のノードについては、対応の転置リストの要素として、前記識別子の代わりに、前記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値を追加するステップとを含む、インデックス作成方法。[付記9]前記先祖参照用データを生成するステップにおいては、前記タクソノミにおける各ノードが所定のデータ集合内でどの程度の頻度を持つか、あるいは持ちそうかを示す頻度分布を受けて、前記タクソノミにおけるノードごとに、前記ノードの各先祖ノードに対応する頻度に基づいて、前記各先祖ノードを選んだ場合における対応の転置リストのデータ長を計算し、前記各先祖ノードのうち、前記データ長が小さい前記先祖ノードおよび前記タクソノミにおいてより上位の前記先祖ノードを優先して選択する、付記8に記載のインデックス作成方法。[付記10]検索対象データに関するタグを有するタクソノミにおいて、前記タクソノミにおける指定された指定ノードから到達可能な検索対象データの集合を取り出すデータ検索方法であって、前記タクソノミにおける各ノードの転置リストを含み、前記各ノードのうち、最上位のノードの転置リストは、前記検索対象データの識別子を示す整数値のリストであり、前記最上位ノード以外のノードの転置リストは、前記識別子の代わりに、前記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値のリストであり、さらに、前記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、前記ブロックにおける整数値と前記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換された転置リスト用データを取得するステップと、前記指定ノードを示す情報を受けて、前記転置リスト用データに基づき、前記指定ノードに対応する前記転置リストの整数値が示す前記位置に対応する、前記指定ノードの上位ノードに対応する前記転置リストの整数値を取り出す処理を、前記最上位ノードに対応する前記転置リストの前記識別子を取り出すまで繰り返すことにより、前記指定ノードに対応する前記検索対象データの識別子のリストを作成するステップとを含む、データ検索方法。[付記11]前記データ検索方法は、さらに、前記タクソノミにおける各ノードの、各検索対象データに対応する頻度を示す頻度リストを取得するステップと、前記指定ノードに対応する1または複数の前記検索対象データの識別子のリストにおいて、前記頻度リストに基づいて前記識別子をソートするステップとを含む、付記10に記載のデータ検索方法。[付記12]前記データ検索方法では、前記タクソノミにおける複数のノードが指定された場合には、各前記指定ノードのいずれからも到達可能な検索対象データの集合を取り出し、前記識別子のリストを作成するステップにおいては、前記タクソノミにおける複数のノードが指定された場合には、各前記指定ノードに対応する前記転置リストを取得し、前記指定ノードに対応する前記転置リストの整数値が示す前記位置に対応する、前記指定ノードの上位ノードに対応する前記転置リストの整数値を取り出す処理を行なう際に、前記指定ノードの組で共通の前記上位ノードのうち、前記タクソノミにおいて最も下位の上位ノードである共通先祖ノードに対応する前記転置リストにおける整数値を取り出すとき、前記指定ノードの組において共通の前記整数値を取り出し、取り出した前記整数値を用いて、前記複数の指定ノードに対応する前記検索対象データの識別子のリストを作成する、付記10に記載のデータ検索方法。[付記13]前記データ検索方法は、さらに、前記タクソノミにおける各ノードの下位ノードである子ノードの集合を示す子ノード情報を取得するステップと、前記指定ノードに対応する前記検索対象データの識別子のリストを受けて、前記タクソノミにおける各ノードの中から、前記リストが示す前記検索対象データの集合において所定値以上の頻度を持つノードを取り出すステップとを含み、前記ノードを取り出すステップにおいては、前記最上位ノードに対応する前記転置リストにおける前記識別子の位置を検出し、前記子ノード情報に基づいて、検出した前記位置と前記最上位ノードの1つ下位のノードに対応する前記転置リストにおける整数値とを比較し、一致した整数値に基づいて前記ノードの頻度を算出する処理を少なくとも行い、さらに、前記ノードの下位のノードについて、上位ノードに対応する前記転置リストにおいて前記識別子の位置に対応する整数値と、前記上位ノードの1つ下位のノードに対応する前記転置リストにおける整数値とを比較し、一致した整数値に基づいて前記1つ下位のノードの頻度を算出する処理を0回以上行なうことにより、前記検索対象データにおける前記各ノードの頻度を算出する、付記10に記載のデータ検索方法。[付記14]検索対象データに関するタグを有するタクソノミにおいて、前記タクソノミにおける各ノードから到達可能な検索対象データの集合を取り出すために用いる転置リストを作成するインデックス作成プログラムを記録した、コンピュータ読み取り可能な記録媒体であって、前記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、前記ブロックにおける整数値と前記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換されており、前記インデックス作成プログラムは、コンピュータに、前記タクソノミにおけるノードごとに、前記ノードの上位ノードである先祖ノードを1つ選択し、選択した前記先祖ノードを示す先祖参照用データを生成するステップと、前記先祖参照用データに基づいて、前記タクソノミにおけるタグの1または複数の先祖ノードを示す先祖ノードリストを生成するステップと、前記検索対象データの識別子を受けて、前記先祖ノードリストにおける各前記ノードのうち最上位のノードについては、前記識別子を対応の転置リストの要素として追加し、前記最上位ノード以外のノードについては、対応の転置リストの要素として、前記識別子の代わりに、前記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値を追加するステップとを実行させるためのプログラムである、コンピュータ読み取り可能な記録媒体。[付記15]前記先祖参照用データを生成するステップにおいては、前記タクソノミにおける各ノードが所定のデータ集合内でどの程度の頻度を持つか、あるいは持ちそうかを示す頻度分布を受けて、前記タクソノミにおけるノードごとに、前記ノードの各先祖ノードに対応する頻度に基づいて、前記各先祖ノードを選んだ場合における対応の転置リストのデータ長を計算し、前記各先祖ノードのうち、前記データ長が小さい前記先祖ノードおよび前記タクソノミにおいてより上位の前記先祖ノードを優先して選択する、付記14に記載のコンピュータ読み取り可能な記録媒体。[付記16]検索対象データに関するタグを有するタクソノミにおいて、前記タクソノミにおける指定された指定ノードから到達可能な検索対象データの集合を取り出すデータ検索プログラムを記録した、コンピュータ読み取り可能な記録媒体であって、前記データ検索プログラムは、コンピュータに、前記タクソノミにおける各ノードの転置リストを含み、前記各ノードのうち、最上位のノードの転置リストは、前記検索対象データの識別子を示す整数値のリストであり、前記最上位ノード以外のノードの転置リストは、前記識別子の代わりに、前記ノードの1つ上のノードに対応する転置リストにおける位置を示す整数値のリストであり、さらに、前記各ノードの転置リストにおける整数値のリストが複数のブロックに分割され、前記ブロックにおける整数値と前記整数値の直前の整数値との差分値が可変長整数コードのビット列に変換された転置リスト用データを取得するステップと、前記指定ノードを示す情報を受けて、前記転置リスト用データに基づき、前記指定ノードに対応する前記転置リストの整数値が示す前記位置に対応する、前記指定ノードの上位ノードに対応する前記転置リストの整数値を取り出す処理を、前記最上位ノードに対応する前記転置リストの前記識別子を取り出すまで繰り返すことにより、前記指定ノードに対応する前記検索対象データの識別子のリストを作成するステップとを実行させるためのプログラムである、コンピュータ読み取り可能な記録媒体。[付記17]前記データ検索プログラムは、さらに、コンピュータに、前記タクソノミにおける各ノードの、各検索対象データに対応する頻度を示す頻度リストを取得するステップと、前記指定ノードに対応する1または複数の前記検索対象データの識別子のリストにおいて、前記頻度リストに基づいて前記識別子をソートするステップとを実行させるためのプログラムである、付記16に記載のコンピュータ読み取り可能な記録媒体。[付記18]前記データ検索プログラムでは、前記タクソノミにおける複数のノードが指定された場合には、各前記指定ノードのいずれからも到達可能な検索対象データの集合を取り出し、前記識別子のリストを作成するステップにおいては、前記タクソノミにおける複数のノードが指定された場合には、各前記指定ノードに対応する前記転置リストを取得し、前記指定ノードに対応する前記転置リストの整数値が示す前記位置に対応する、前記指定ノードの上位ノードに対応する前記転置リストの整数値を取り出す処理を行なう際に、前記指定ノードの組で共通の前記上位ノードのうち、前記タクソノミにおいて最も下位の上位ノードである共通先祖ノードに対応する前記転置リストにおける整数値を取り出すとき、前記指定ノードの組において共通の前記整数値を取り出し、取り出した前記整数値を用いて、前記複数の指定ノードに対応する前記検索対象データの識別子のリストを作成する、付記16に記載のコンピュータ読み取り可能な記録媒体。[付記19]前記データ検索プログラムは、さらに、コンピュータに、前記タクソノミにおける各ノードの下位ノードである子ノードの集合を示す子ノード情報を取得するステップと、前記指定ノードに対応する前記検索対象データの識別子のリストを受けて、前記タクソノミにおける各ノードの中から、前記リストが示す前記検索対象データの集合において所定値以上の頻度を持つノードを取り出すステップとを実行させるためのプログラムであり、前記ノードを取り出すステップにおいては、前記最上位ノードに対応する前記転置リストにおける前記識別子の位置を検出し、前記子ノード情報に基づいて、検出した前記位置と前記最上位ノードの1つ下位のノードに対応する前記転置リストにおける整数値とを比較し、一致した整数値に基づいて前記ノードの頻度を算出する処理を少なくとも行い、さらに、前記ノードの下位のノードについて、上位ノードに対応する前記転置リストにおいて前記識別子の位置に対応する整数値と、前記上位ノードの1つ下位のノードに対応する前記転置リストにおける整数値とを比較し、一致した整数値に基づいて前記1つ下位のノードの頻度を算出する処理を0回以上行なうことにより、前記検索対象データにおける前記各ノードの頻度を算出する、付記16に記載のコンピュータ読み取り可能な記録媒体。上記実施の形態は、すべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は、上記説明ではなく請求の範囲によって示され、請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。この出願は、2010年10月15日に出願された日本出願特願2010-232896を基礎とする優先権を主張し、その開示の全てをここに取り込む。"