(57)【要約】【課題】ユーザの探索にかかる負担を削減し、ユーザの平均探索時間を減少させる。【解決手段】部分木併合装置１であって、複数の部分木のノード情報２を入力し、部分木記憶手段０２０に記憶する入力手段０３１と、部分木記憶手段０２０から２つの部分木のノード情報を取得し、第１の部分木の根ノードを第２の部分木の葉ノード以外の各ノードの子ノードとなるように配置して併合した場合の損失コストをそれぞれ算出し、損失コスト記憶手段０４０に格納する損失コスト算出手段０３２と、損失コストが最小となる配置を特定し、第１の部分木および第２の部分木を特定した配置で併合した併合後の部分木のノード情報を生成し、部分木記憶手段０２０に登録するとともに、部分木記憶手段０２０から併合前の第１の部分木のノード情報および第２の部分木のノード情報を削除する併合手段０３３と、を備える。【選択図】図１
2014203431.tif 000002
【特許請求の範囲】
【請求項１】
複数の部分木を併合する部分木併合装置であって、
複数の部分木のノード情報を入力し、部分木記憶手段に記憶する入力手段と、
前記部分木記憶手段から２つの部分木のノード情報を取得し、第１の部分木の根ノードを、第２の部分木の葉ノード以外の各ノードの子ノードとなるように配置して併合した場合の損失コストをそれぞれ算出し、損失コスト記憶手段に格納する損失コスト算出手段と、
前記損失コスト記憶手段から損失コストが最小となる配置を特定し、第１の部分木および第２の部分木を前記特定した配置で併合した併合後の部分木のノード情報を生成し、前記部分木記憶手段に登録するとともに、前記部分木記憶手段から併合前の第１の部分木のノード情報および第２の部分木のノード情報を削除する併合手段と、を備え、
前記損失コストは、併合後の部分木の探索コストと、併合前の第１の部分木の探索コストと第２の部分木の探索コストの和との差であること
を特徴とする部分木併合装置。
【請求項２】
請求項１記載の部分木併合装置であって、
前記損失コスト算出手段および前記併合手段は、前記部分木記憶手段に記憶された部分木のノード情報が１つになるまで損失コストの算出および併合を行い、
前記併合手段は、前記部分木記憶手段に記憶された部分木のノード情報が１つになった場合、当該部分木のノード情報をカテゴリ階層として出力すること
を特徴とする部分木併合装置。
【請求項３】
請求項１または２記載の部分木併合装置であって、
損失コスト算出手段は、ノード間の親子関係の強さを示す親子スコアおよびノード間の兄弟関係の強さを示す兄弟スコアが設定されたペア関係スコア記憶手段を参照して前記探索コストを算出すること
を特徴とする部分木併合装置。
【請求項４】
コンピュータが行う複数の部分木を併合する部分木併合方法であって、
複数の部分木のノード情報を入力し、部分木記憶部に記憶する入力ステップと、
前記部分木記憶部から２つの部分木のノード情報を取得し、第１の部分木の根ノードを、第２の部分木の葉ノード以外の各ノードの子ノードとなるように配置して併合した場合の損失コストをそれぞれ算出し、損失コスト記憶部に格納する損失コスト算出ステップと、
前記損失コスト記憶部から損失コストが最小となる配置を特定し、第１の部分木および第２の部分木を前記特定した配置で併合した併合後の部分木のノード情報を生成し、前記部分木記憶部に登録するとともに、前記部分木記憶部から併合前の第１の部分木のノード情報および第２の部分木のノード情報を削除する併合ステップと、を行い、
前記損失コストは、併合後の部分木の探索コストと、併合前の第１の部分木の探索コストと第２の部分木の探索コストの和との差であること
を特徴とする部分木併合方法。
【請求項５】
請求項４記載の部分木併合方法であって、
前記損失コスト算出ステップおよび前記併合ステップを、前記部分木記憶部に記憶された部分木のノード情報が１つになるまで行い、
前記部分木記憶部に記憶された部分木のノード情報が１つになった場合、当該部分木のノード情報をカテゴリ階層として出力する出力ステップを、さらに行うこと
を特徴とする部分木併合方法。
【請求項６】
請求項４または５記載の部分木併合方法であって、
損失コスト算出ステップは、ノード間の親子関係の強さを示す親子スコアおよびノード間の兄弟関係の強さを示す兄弟スコアが設定されたペア関係スコア記憶部を参照して前記探索コストを算出すること
を特徴とする部分木併合方法。
【請求項７】
請求項１から３のいずれか一項に記載の部分木併合装置としてコンピュータを機能させるための部分木併合プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の部分木を併合する部分木併合装置、部分木併合方法および部分木併合プログラムに関する。
【背景技術】
【０００２】
ユーザによる検索を支援するひとつの方法として、ユーザがシステムから提示されたカテゴリを選択して、検索対象を絞り込みながら検索を行うディレクトリ型検索サービスとして、例えば、非特許文献１がある。ユーザは検索クエリを入力する必要がなく、ユーザが検索クエリとして表現しにくい、または具体的な検索クエリとして思い出せない曖昧な検索要求を持つ場合にも、システムから提示されたカテゴリを選択することで検索対象を絞り込むことができる。
【０００３】
また、カテゴリをノードとみなしたカテゴリ階層を併合する方法として、例えば非特許文献２に示す手法がある。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】「gooカテゴリ検索」、＜URL: http://category.goo.ne.jp/＞
【非特許文献２】奥村学、「言語処理のための機械学習入門」、コロナ社、2011年
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ディレクトリ検索サービスで用いられているカテゴリ階層は、サービスごとに人手によって構築されているため、サービスごとにカテゴリ階層が異なる。そのため、ユーザはサービスごとに異なるカテゴリ階層をたどらなければならず検索しにくく、ユーザの検索の利便性は低下する。このような状況において、ある１つのサービスにおいて構築された複数のカテゴリ階層、または複数のサービスで個々に構築されたカテゴリ階層を併合して、ユーザにとってたどり易いカテゴリ階層の構築が求められている。
【０００６】
しかしながら、非特許文献２に示す併合時の２つのノード間の関係性のみに基づく最短距離法によるクラスタリング手法では、例えば階層の平均深さが大きいカテゴリ階層や各ノードの平均子カテゴリ数が大きいカテゴリ階層など、ユーザの探索にかかる探索コストが大きいカテゴリ階層が構築されてしまう可能性があり、この場合、カテゴリ階層を利用するユーザの平均探索時間が増加するという課題がある。
【０００７】
本発明は、上記事情に鑑みてなされたものであり、本発明の目的は、ユーザの探索にかかる負担を削減し、ユーザの平均探索時間を減少させる部分木併合装置、部分木併合方法および部分木併合プログラムを提供することにある。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、請求項１記載の本発明は、複数の部分木を併合する部分木併合装置であって、複数の部分木のノード情報を入力し、部分木記憶手段に記憶する入力手段と、前記部分木記憶手段から２つの部分木のノード情報を取得し、第１の部分木の根ノードを、第２の部分木の葉ノード以外の各ノードの子ノードとなるように配置して併合した場合の損失コストをそれぞれ算出し、損失コスト記憶手段に格納する損失コスト算出手段と、前記損失コスト記憶手段から損失コストが最小となる配置を特定し、第１の部分木および第２の部分木を前記特定した配置で併合した併合後の部分木のノード情報を生成し、前記部分木記憶手段に登録するとともに、前記部分木記憶手段から併合前の第１の部分木のノード情報および第２の部分木のノード情報を削除する併合手段と、を備え、前記損失コストは、併合後の部分木の探索コストと、併合前の第１の部分木の探索コストと第２の部分木の探索コストの和との差であることを要旨とする。
【０００９】
請求項２記載の本発明は、部分木併合装置であって、前記損失コスト算出手段および前記併合手段は、前記部分木記憶手段に記憶された部分木のノード情報が１つになるまで損失コストの算出および併合を行い、前記併合手段は、前記部分木記憶手段に記憶された部分木のノード情報が１つになった場合、当該部分木のノード情報をカテゴリ階層として出力することを要旨とする。
【００１０】
請求項３記載の本発明は、部分木併合装置であって、損失コスト算出手段は、ノード間の親子関係の強さを示す親子スコアおよびノード間の兄弟関係の強さを示す兄弟スコアが設定されたペア関係スコア記憶手段を参照して前記探索コストを算出することを要旨とする。
【００１１】
請求項４記載の本発明は、コンピュータが行う複数の部分木を併合する部分木併合方法であって、複数の部分木のノード情報を入力し、部分木記憶部に記憶する入力ステップと、前記部分木記憶部から２つの部分木のノード情報を取得し、第１の部分木の根ノードを、第２の部分木の葉ノード以外の各ノードの子ノードとなるように配置して併合した場合の損失コストをそれぞれ算出し、損失コスト記憶部に格納する損失コスト算出ステップと、前記損失コスト記憶部から損失コストが最小となる配置を特定し、第１の部分木および第２の部分木を前記特定した配置で併合した併合後の部分木のノード情報を生成し、前記部分木記憶部に登録するとともに、前記部分木記憶部から併合前の第１の部分木のノード情報および第２の部分木のノード情報を削除する併合ステップと、を行い、前記損失コストは、併合後の部分木の探索コストと、併合前の第１の部分木の探索コストと第２の部分木の探索コストの和との差であることを要旨とする。
【００１２】
請求項５記載の本発明は、部分木併合方法であって、前記損失コスト算出ステップおよび前記併合ステップを、前記部分木記憶部に記憶された部分木のノード情報が１つになるまで行い、前記部分木記憶部に記憶された部分木のノード情報が１つになった場合、当該部分木のノード情報をカテゴリ階層として出力する出力ステップを、さらに行うことを要旨とする。
【００１３】
請求項６記載の本発明は、部分木併合方法であって、損失コスト算出ステップは、ノード間の親子関係の強さを示す親子スコアおよびノード間の兄弟関係の強さを示す兄弟スコアが設定されたペア関係スコア記憶部を参照して前記探索コストを算出することを要旨とする。
【００１４】
請求項７記載の本発明は、前記部分木併合装置としてコンピュータを機能させるための部分木併合プログラムである。
【発明の効果】
【００１５】
本発明によれば、ユーザの探索にかかる負担を削減し、ユーザの平均探索時間を減少させる部分木併合装置、部分木併合方法および部分木併合プログラムを提供することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施形態に係る部分木併合装置の構成図である。
【図２】カテゴリペア関係スコアＤＢのデータ例を示す図である。
【図３】部分木ＤＢのデータ例を示す図である。
【図４】損失コストＤＢのデータ例を示す図である。
【図５】本実施形態の処理を示すフローチャートである。
【図６】部分木の併合の一例を示すものである。
【図７】併合前の部分木の探索コストと、併合後の部分木の探索コストとを模式的に示す図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施の形態について、図面を参照して説明する。
【００１８】
図１は、本実施形態における部分木併合装置１の構成を示す構成図である。本実施形態の部分木併合装置１は、ユーザがシステムから提示されたカテゴリを選択して、検索対象を絞り込みながら検索を行うディレクトリ型検索サービスなどにおいて、ユーザの検索のしにくさをユーザの探索にかかるコスト（以下、「探索コスト」と呼ぶ） として数値で表現し、複数のカテゴリ階層を併合して探索コストが小さいカテゴリ階層を構築する。具体的には、部分木併合装置１は、カテゴリペア関係スコアＤＢ２と、部分木ＤＢ３を入力として受け付け、カテゴリ階層ＤＢ０５０を出力する。
【００１９】
図示する部分木併合装置１は、カテゴリペア関係スコアＤＢ０１０と、部分木ＤＢ０２０と、制御部０３０と、損失コストＤＢ０４０と、カテゴリ階層ＤＢ０５０とを備える。そして、制御部０３０は、入力部０３１と、損失コスト算出部０３２と、部分木併合部０３３とを備える。
【００２０】
入力部０３１は、カテゴリペア関係スコアＤＢ２および部分木ＤＢ３を入力し、作業用のカテゴリペア関係スコアＤＢ０１０および部分木ＤＢ０２０に格納する。なお、カテゴリペア関係スコアＤＢ２および部分木ＤＢ３は、１つのディレクトリ検索サービスで作成された複数のカテゴリ階層（以下、「部分木」と呼ぶ）に基づいて生成されるＤＢであってもよく、また、複数のディレクトリ検索サービスで個々に作成された複数のカテゴリ階層（以下、「部分木」と呼ぶ）に基づいて生成されるＤＢであってもよい。
【００２１】
損失コスト算出部０３２は、部分木ＤＢ０２０から任意の未処理の２つの部分木のノード集合（ノード情報）を取得し、第１の部分木の根ノードを、第２の部分木の葉ノード以外の各ノードの子ノードとなるように配置して併合した場合の損失コストをそれぞれ算出し、損失コストＤＢ０４０に格納する。損失コストは、併合後の部分木の探索コストと、併合前の第１の部分木の探索コストと第２の部分木の探索コストの和との差である。
【００２２】
部分木併合部０３３は、損失コストＤＢ０４０から損失コストが最小となる配置を特定し、第１の部分木および第２の部分木を特定した配置で併合した併合後の部分木のノード集合を生成し、部分木ＤＢ０２０に登録するとともに、部分木ＤＢ０２０から併合前の第１の部分木のノード集合および第２の部分木のノード集合を削除する。
【００２３】
また、損失コスト算出部０３２および部分木併合部０３３は、部分木ＤＢ０２０に記憶された部分木のノード集合が１つになるまで損失コストの算出および併合を行い、部分木併合部０３３は、部分木ＤＢ０２０に記憶された部分木のノード集合が１つになった場合、当該部分木のノード集合をカテゴリ階層としてカテゴリ階層ＤＢ０５０に出力する。
【００２４】
図２は、カテゴリペア関係スコアＤＢ０１０（または、カテゴリペア関係スコアＤＢ２）のデータ例を示す。カテゴリペア関係スコアＤＢ０１０は、１つのレコードが２つのノードの関係性の情報を保持しており、本実施形態では、ノード間の親子関係の強さを示す親子スコアおよびノード間の兄弟関係の強さを示す兄弟スコアを保持するものとする。図示するカテゴリペア関係スコアＤＢ０１０は、カテゴリ１カラムと、カテゴリ２カラムと、親子スコアカラムと、兄弟スコアカラムとを有する。
【００２５】
カテゴリ１カラムのカテゴリkw1と、カテゴリ２カラムのカテゴリkw2をラベルとする２つのノードに対して、親子スコアoyako score(kw1,kw2)は、kw1がkw2の親ノードである可能性を表す推定値とする。また、兄弟スコアkyodai score(kw1,kw2)は、２つのノードが兄弟関係である可能性を表す推定値とする。
【００２６】
なお、部分木ＤＢ０２０に格納されている全ノードの任意の２つのノード（カテゴリ）の組み合わせは、すべてカテゴリペア関係スコアＤＢ０１０に格納されているものとする。すなわち、カテゴリペア関係スコアＤＢ０１０のカテゴリ１カラムおよびカテゴリ２カラムに格納されているカテゴリは、部分木ＤＢ０２０のノード集合カラムに格納されている全ノード（カテゴリ）の任意の２つのノードの組み合わせであって、１つの組み合わせに対して１レコード有する。
【００２７】
非特許文献１のgooカテゴリ検索のような既存のディレクトリ検索サービスにおいて、当該検索サービスシステムが持つカテゴリ階層におけるkw1とkw2をラベルにもつノードの配置関係に基づいて、これらのスコアは容易に算出できるものとする。
【００２８】
例えば、一方のノードが他方のノードの上位に配置されており、２つのノードの階層の深さの差が小さいほど高くなるようなスコアを算出して親子スコアとする。また、２つのノードが同一の親ノードをもつ場合は高く、そうでない場合は低くなるようなスコアを算出して兄弟スコアとする。
【００２９】
図３に、部分木ＤＢ０２０（または、部分木ＤＢ３）のデータ例を示す。部分木ＤＢ０２０は、１つのレコードが１つの部分木の情報を保持している。また、各レコード（部分木）毎に、部分木ＩＤカラムとノード集合カラムとを有する。部分木は、カテゴリをノードとみなした木構造である。
【００３０】
ノード集合カラムには、当該部分木に含まれる複数のノードの情報が保持され、ノード毎に、当該ノードのラベル名、当該ノードの親ノードのラベル名、当該ノードの子ノード集合のラベル名が保持される。ただし、ノードが根ノードであるときは、親ノードのラベル名はNoneとする。また、ノードが葉ノードであるときは、子ノード集合のラベル名はNone とする。
【００３１】
図４に、損失コストＤＢ０４０のデータ例を示す。損失コストＤＢ０４０は、部分木ＩＤ１カラム、部分木ＩＤ２カラム、カテゴリ１カラム、カテゴリ２カラム、損失コストカラムを有する。カテゴリ１カラムおよびカテゴリ２カラムに格納されているカテゴリは、部分木ＤＢ０２０のノード集合カラムに格納されているカテゴリ（ノード）であるとする。
【００３２】
カテゴリ階層ＤＢ０５０には、部分木ＤＢ０２０の部分木を１つに併合した結果のカテゴリ階層が格納される。カテゴリ階層ＤＢ０５０には、カテゴリ階層として、部分木ＤＢ０２０のノード集合カラムと同様のノード集合カラムが１つ格納される。
【００３３】
上記説明した部分木併合装置１は、例えば、ＣＰＵと、メモリと、ＨＤＤ等の外部記憶装置などを備えた汎用的なコンピュータシステムを用いることができる。このコンピュータシステムにおいて、ＣＰＵがメモリ上にロードされた部分木併合装置１用のプログラムを実行することにより、部分木併合装置１の各機能が実現される。また、部分木併合装置１用のプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ−ＲＯＭなどのコンピュータ読取り可能な記録媒体に記憶することも、ネットワークを介して配信することもできる。
【００３４】
次に、本実施形態の部分木併合装置１の処理について説明する。
【００３５】
図５は、制御部０３０の処理の流れを示すフローチャートである。
【００３６】
Ｓ１００：入力部０３１は、カテゴリペア関係スコアＤＢ２および部分木ＤＢ３を入力し、作業用のカテゴリペア関係スコアＤＢ０１０および部分木ＤＢ０２０に格納する。
【００３７】
Ｓ１１０：損失コスト算出部０３２は、損失コストＤＢ０４０を空にする。
【００３８】
Ｓ１２０：損失コスト算出部０３２は、部分木ＤＢ０２０から未処理の任意の２つの部分木のレコードを取得する。ここで、取得した２つの部分木の部分木ＩＤを、t1、t2とする。
【００３９】
Ｓ１３０：損失コスト算出部０３２は、部分木ＤＢ０２０の部分木ＩＤがt2のレコードのノード集合カラムの全ノードの中から子ノード集合のラベル名がNone 以外であるノード（すなわち、葉ノード以外のノード）を取得して、t2の葉ノード以外のすべてのノードの集合をXとする。t1の根ノードn1と、t2の集合Xの要素の各ノードn2に対して、n1をn2の子ノードになるように配置し、部分木t1とt2とを併合したときの損失コストcost(n1,n2)を算出する。
【００４０】
図６は、併合前の部分木t1とt2について、t1の根ノードn1がt2のn2の子ノードになるように配置して２つの部分木t1、t2を併合した部分木を示すものである。ここで、併合後の部分木の部分木ID をt3とする。
【００４１】
損失コストcost(n1,n2)は、t1の根ノードn1がt2のn2の子ノードになるように配置してt1とt2を併合したことによる、併合前の探索コストの和と、併合後の探索コストとの差を表す。すなわち、損失コストcost(n1,n2)は、探索コストsearch cost(t1)、search cost(t2)、search cost(t3)を用いて、以下の式により算出することができる。
【数１】
2014203431.tif 000003
【００４２】
図７は、図６に示す併合前の部分木t1とt2の探索コストと、併合後の部分木t3の探索コストとを模式的に示す図である。
【００４３】
部分木Tの探索コストsearch cost(T)は、部分木T を高さ1の部分木で分割したときのそれぞれの高さ1の部分木に対して算出される部分木スコアdivision score(p,Cp)の逆数の和である。つまり、探索コストsearch cost(T)は、部分木スコアdivision score(p,Cp)を用いて、以下の式により算出することができる。
【数２】
2014203431.tif 000004
【００４４】
ここで、Tに含まれる葉ノード以外のノードを要素とする集合をPとし、Pの要素pにおける子ノード集合をCp とする。部分木スコアdivision score(p,Cp)は、親ノードをp、pの子ノード集合をCpとする高さ1の部分木における親子関係の強さと兄弟関係の強さを示す推定値である。部分木スコアdivision score(p,Cp)は、例えば、以下の式により算出することができる。
【数３】
2014203431.tif 000005
【００４５】
ここで、上記式の親子スコアoyako score(p,c)および兄弟スコアkyodai score(c1,c2)については、カテゴリペア関係スコアＤＢ０１０を参照し、対応する親子スコアまたは兄弟スコアを取得する。
【００４６】
｜Cp｜は、集合Cpの要素数を表す。また、γは集合Cpの任意の２つの要素の組合せ数であり、以下の式のよう表される。また、αは2つのスコアの寄与率を表し、0≦α≦1とする。
【数４】
2014203431.tif 000006
【００４７】
部分木スコアdivision score(p,Cp)は、pと集合Cpの親子スコアの平均が高いほど高く、また、子ノード集合の兄弟スコアの平均が高いほど高い。それぞれの高さ1の部分木のdivision score(p,Cp)が高いと、Tにおける親ノードと子ノード集合の親子関係と兄弟関係は強く、探索コストは小さい。
【００４８】
損失コスト算出部０３２は、t2の集合Xの要素の各ノードn2について、t1の根ノードn1を各n2の子ノードになるように配置したときの損失コストcost(n1,n2)を、それぞれ算出し、損失コストＤＢ０４０に記憶する。具体的には、（t1,t2,n1,n2,cost(n1,n2)）の各レコードをそれぞれ生成し、損失コストＤＢ０４０に格納する。
【００４９】
Ｓ１４０：損失コスト算出部０３２は、部分木ＤＢ０２０の部分木ＩＤがt1のレコードのノード集合カラムの全ノードの中から子ノード集合のラベル名がNone 以外であるノード（すなわち、葉ノード以外のノード）を取得して、t1の葉ノード以外のすべてのノードの集合をYとする。t2の根ノードn2と、t1の集合Yの要素の各ノードn1に対して、n2をn1の子ノードになるように配置し、部分木t1とt2とを併合したときの損失コストcost(n2,n1)を、Ｓ１３０と同様に算出し、損失コストＤＢ０４０に記憶する。具体的には、（t2,t1,n2,n1,cost(n2,n1)）の各レコードを生成し、損失コストＤＢ０４０に格納する。
【００５０】
Ｓ１５０：損失コスト算出部０３２は、未処理の２つの部分木の組み合わせがある場合は（Ｓ１５０：ＹＥＳ）、Ｓ１２０に戻り、未処理の２つの部分木についてＳ１３０およびＳ１４０を行う。一方、未処理の２つの部分木の組み合わせがない場合、すなわち、全て組み合わせでのＳ１３０およびＳ１４０の処理を行った場合（Ｓ１５０：ＮＯ）、Ｓ１６０に進む。
【００５１】
Ｓ１６０：部分木併合部０３３は、損失コストＤＢ０４０に格納されたレコードの中で、損失コストcost(n1,n2)（またはcost(n2,n1)）が最小となる（t1,t2,n1,n2,cost(n1,n2)）（または（t2,t1,n2,n1,cost(n2,n1)））のレコードを特定し、n1がn2の子ノード（またはn2がn1の子ノード）になるように部分木t1とt2とを配置して併合する。具体的には、部分木併合部０３３は、部分木ＤＢ０２０の部分木ＩＤとして未使用の部分木ＩＤを、併合後の部分木の部分木ＩＤとし、また、特定したレコードの配置で部分木t1とt2とを併合したノード集合を生成し、併合後の部分木を１つの部分木のレコードとして部分木ＤＢ０２０に登録する。
【００５２】
また、部分木併合部０３３は、併合前の部分木t1とt2に該当するレコードを部分木ＤＢ０２０から削除する。このように、Ｓ１６０の部分木の併合処理が１回実行される毎に、部分木ＤＢ０２０から１レコード削減される。
【００５３】
Ｓ１７０：部分木ＤＢ０２０のレコード数が２以上の場合は（Ｓ１７０：ＹＥＳ）、Ｓ１１０に戻り、以降の処理を繰り返し行う。一方、部分木ＤＢ０２０のレコード数が１の場合は（Ｓ１７０：ＮＯ）、Ｓ１８０に進む。
【００５４】
Ｓ１８０：部分木併合部０３３は、部分木ＤＢ０２０のレコード数が１の場合、当該レコードのノード集合カラムをカテゴリ階層ＤＢ０５０に格納する。部分木ＤＢ０２０のレコード数が１であることは、処理開始時に部分木ＤＢ０２０に格納されていた複数の部分木を全て１つに併合したことを意味する。すなわち、この時点で、部分木ＤＢ０２０に格納されている部分木がカテゴリ階層となる。
【００５５】
以上説明した本実施形態の部分木併合装置１では、ユーザの検索のしにくさをユーザの探索にかかるコストとして数値で表現し、複数のカテゴリ階層を併合して探索コストが小さいカテゴリ階層を構築する。具体的には、併合後の部分木の探索コストと、併合前の部分木の探索コストの和との差である損失コストが小さいものから順次併合してカテゴリ階層を構築する。
【００５６】
これにより、本実施形態では、探索後の探索コストを考慮した部分木の併合が可能となるため、探索コストが小さいカテゴリ階層の構築が可能となり、ユーザにとって検索・探索しやすいディレクトリ型検索サービスを提供することできる。すなわち、ユーザの探索にかかる負担を削減し、ユーザの平均探索時間を減少させることが可能となり、ユーザの利便性を向上することができる。
【００５７】
また、本実施形態では、図５のＳ１３０およびＳ１４０において、葉ノードを除いたノードの集合X、Yを用いて、部分木を併合する。このように、葉ノード以外のノードに他の部分木の根ノードを配置することで、併合後の部分木（またはカテゴリ階層）の階層の深さが大きくなり、探索コストが増加することを抑制することができる。
【００５８】
なお、本発明は上記実施形態に限定されるものではなく、その要旨の範囲内で数々の変形が可能である。
【符号の説明】
【００５９】
１    ：部分木併合装置
２    ：カテゴリペア関係スコアＤＢ
３    ：部分木ＤＢ
０１０：カテゴリペア関係スコアＤＢ
０２０：部分木ＤＢ
０３０：制御部
０３１：入力部
０３２：損失コスト算出部
０３３：部分木併合部
０４０：損失コストＤＢ
０５０：カテゴリ階層ＤＢ
【図１】
2014203431.tif 000007
【図２】
2014203431.tif 000008
【図３】
2014203431.tif 000009
【図４】
2014203431.tif 000010
【図５】
2014203431.tif 000011
【図６】
2014203431.tif 000012
【図７】
2014203431.tif 000013