(57)【要約】【課題】複数の要素と、要素間の親子関係を示す親子関係情報と、を含む情報から、要素間の親子関係の特徴が効率よく抽出される情報処理装置及びプログラムを提供する。【解決手段】特徴抽出対象情報取得部４０が特徴抽出対象情報を取得する。組合せ特定部４２が、子標識に関連付けられた子標識対応要素が親標識に関連付けられた親標識対応要素の子孫に該当する、親標識対応要素と子標識対応要素との組合せの数が、予め定められた条件を満足する、標識の組合せを特定する。中間標識特定部４４が、親標識対応要素の子孫に該当し子標識対応要素の先祖に該当する、中間標識に関連付けられた中間標識対応要素の数が、予め定められた条件を満足する、中間標識を特定する。特徴情報生成部４６が、親標識対応要素、子標識対応要素及び中間標識対応要素それぞれの間の親子関係の特徴を示す特徴情報を生成する。【選択図】図４
2010134723.tif 000002
【特許請求の範囲】
【請求項１】
それぞれ複数の標識のうちのいずれかと関連付けられた複数の要素と、前記要素間の親子関係を示す親子関係情報と、を含む特徴抽出対象情報を取得する特徴抽出対象情報取得手段と、
子標識として選択される前記標識に関連付けられた子標識対応要素が親標識として選択される前記標識に関連付けられた親標識対応要素の子孫に該当する、前記特徴抽出対象情報に含まれる前記親標識対応要素と前記子標識対応要素との組合せの数が、予め定められた条件を満足する、前記親標識として選択される前記標識と前記子標識として選択される前記標識との組合せを特定する組合せ特定手段と、
前記親標識対応要素の子孫に該当し前記子標識対応要素の先祖に該当する、中間標識として選択される前記標識に関連付けられた、前記特徴抽出対象情報に含まれる中間標識対応要素の数が、予め定められた条件を満足する、前記中間標識として選択される前記標識を特定する中間標識特定手段と、
前記組合せ特定手段により特定される組合せ、及び、前記中間標識特定手段により特定される標識に基づいて、前記親標識対応要素、前記子標識対応要素及び前記中間標識対応要素それぞれの間の親子関係の特徴を示す特徴情報を生成する特徴情報生成手段と、
を含むことを特徴とする情報処理装置。
【請求項２】
前記組合せ特定手段が、
前記特徴抽出対象情報に含まれる、親標識として選択される前記標識に関連付けられた親標識対応要素の数が予め定められた条件を満足する、前記親標識として選択される前記標識を特定し、
前記特徴抽出対象情報に含まれる、子標識として選択される前記標識に関連付けられた子標識対応要素の数が予め定められた条件を満足する、前記子標識として選択される前記標識を特定し、
前記親標識として選択される前記標識と、前記子標識として選択される前記標識と、に基づいて前記組合せを特定する、
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記組合せ特定手段が、前記親標識対応要素の子孫に該当する前記子標識対応要素の数が予め定められた条件を満足する、前記子標識として選択される前記標識を特定する、
ことを特徴とする請求項２に記載の情報処理装置。
【請求項４】
前記組合せ特定手段が、前記子標識対応要素の先祖に該当する前記親標識対応要素の数が予め定められた条件を満足する前記親標識として選択される前記標識を特定する、
ことを特徴とする請求項２に記載の情報処理装置。
【請求項５】
前記親標識として選択される前記標識の候補又は前記子標識として選択される前記標識の候補の少なくとも一方が予め定められている、
ことを特徴とする請求項１から４のいずれか一項に記載の情報処理装置。
【請求項６】
前記組合せ特定手段が、前記中間標識特定手段により前記中間標識として選択される前記標識が特定された後に、当該特定された標識を親標識又は子標識のうちの一方として選択して、当該標識と、親標識又は子標識のうちの他方として選択される前記標識と、の組合せを特定する、
ことを特徴とする請求項１から５のいずれか一項に記載の情報処理装置。
【請求項７】
前記特徴抽出対象情報取得手段が、複数の特徴抽出対象情報を取得し、
前記組合せ特定手段が、前記親標識対応要素と前記子標識対応要素との組合せが含まれる前記特徴抽出対象情報の数が予め定められた条件を満足する前記組合せを特定し、
前記中間標識特定手段が、前記中間標識対応要素を含む前記特徴抽出対象情報の数が予め定められた条件を満足する前記中間標識として選択される前記標識を特定する、
ことを特徴とする請求項１から６のいずれか一項に記載の情報処理装置。
【請求項８】
それぞれ複数の標識のうちのいずれかと関連付けられた複数の要素と、前記要素間の親子関係を示す親子関係情報と、を含む特徴抽出対象情報を取得する特徴抽出対象情報取得手段、
子標識として選択される前記標識に関連付けられた子標識対応要素が親標識として選択される前記標識に関連付けられた親標識対応要素の子孫に該当する、前記特徴抽出対象情報に含まれる前記親標識対応要素と前記子標識対応要素との組合せの数が、予め定められた条件を満足する、前記親標識として選択される前記標識と前記子標識として選択される前記標識との組合せを特定する組合せ特定手段、
前記親標識対応要素の子孫に該当し前記子標識対応要素の先祖に該当する、中間標識として選択される前記標識に関連付けられた、前記特徴抽出対象情報に含まれる中間標識対応要素の数が、予め定められた条件を満足する、前記中間標識として選択される前記標識を特定する中間標識特定手段、
前記組合せ特定手段により特定される組合せ、及び、前記中間標識特定手段により特定される標識に基づいて、前記親標識対応要素、前記子標識対応要素及び前記中間標識対応要素それぞれの間の親子関係の特徴を示す特徴情報を生成する特徴情報生成手段、
としてコンピュータを機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置及びプログラムに関する。
【背景技術】
【０００２】
複数の要素と、要素間の親子関係を示す情報と、を含む情報（例えば、木構造の情報）から特徴的な要素間の親子関係を抽出する技術が存在する。特許文献１には、複雑な構造を持つデータから、複数段階の構造を持つパターンを抽出する技術が開示されている。特許文献２には順序木において頻出するパターンを効率よく抽出する技術が開示されている。特許文献３には、膨大な文書データから適切に頻出パターンを抽出する技術が開示されている。
【特許文献１】特開２００１−１３４５７５号公報
【特許文献２】特開２００４−３５５４５７号公報
【特許文献３】特開２００１−８４２５０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明は、複数の要素と、要素間の親子関係を示す親子関係情報と、を含む情報から、要素間の親子関係の特徴が効率よく抽出される情報処理装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００４】
請求項１に記載の発明は、情報処理装置であって、それぞれ複数の標識のうちのいずれかと関連付けられた複数の要素と、前記要素間の親子関係を示す親子関係情報と、を含む特徴抽出対象情報を取得する特徴抽出対象情報取得手段と、子標識として選択される前記標識に関連付けられた子標識対応要素が親標識として選択される前記標識に関連付けられた親標識対応要素の子孫に該当する、前記特徴抽出対象情報に含まれる前記親標識対応要素と前記子標識対応要素との組合せの数が、予め定められた条件を満足する、前記親標識として選択される前記標識と前記子標識として選択される前記標識との組合せを特定する組合せ特定手段と、前記親標識対応要素の子孫に該当し前記子標識対応要素の先祖に該当する、中間標識として選択される前記標識に関連付けられた、前記特徴抽出対象情報に含まれる中間標識対応要素の数が、予め定められた条件を満足する、前記中間標識として選択される前記標識を特定する中間標識特定手段と、前記組合せ特定手段により特定される組合せ、及び、前記中間標識特定手段により特定される標識に基づいて、前記親標識対応要素、前記子標識対応要素及び前記中間標識対応要素それぞれの間の親子関係の特徴を示す特徴情報を生成する特徴情報生成手段と、を含むこととしたものである。
【０００５】
請求項２に記載の発明は、請求項１に記載の情報処理装置であって、前記組合せ特定手段が、前記特徴抽出対象情報に含まれる、親標識として選択される前記標識に関連付けられた親標識対応要素の数が予め定められた条件を満足する、前記親標識として選択される前記標識を特定し、前記特徴抽出対象情報に含まれる、子標識として選択される前記標識に関連付けられた子標識対応要素の数が予め定められた条件を満足する、前記子標識として選択される前記標識を特定し、前記親標識として選択される前記標識と、前記子標識として選択される前記標識と、に基づいて前記組合せを特定することとしたものである。
【０００６】
請求項３に記載の発明は、請求項２に記載の情報処理装置であって、前記組合せ特定手段が、前記親標識対応要素の子孫に該当する前記子標識対応要素の数が予め定められた条件を満足する、前記子標識として選択される前記標識を特定することとしたものである。
【０００７】
請求項４に記載の発明は、請求項２に記載の情報処理装置であって、前記組合せ特定手段が、前記子標識対応要素の先祖に該当する前記親標識対応要素の数が予め定められた条件を満足する前記親標識として選択される前記標識を特定することとしたものである。
【０００８】
請求項５に記載の発明は、請求項１から４のいずれか一項に記載の情報処理装置であって、前記親標識として選択される前記標識の候補又は前記子標識として選択される前記標識の候補の少なくとも一方が予め定められていることとしたものである。
【０００９】
請求項６に記載の発明は、請求項１から５のいずれか一項に記載の情報処理装置であって、前記組合せ特定手段が、前記中間標識特定手段により前記中間標識として選択される前記標識が特定された後に、当該特定された標識を親標識又は子標識のうちの一方として選択して、当該標識と、親標識又は子標識のうちの他方として選択される前記標識と、の組合せを特定することとしたものである。
【００１０】
請求項７に記載の発明は、請求項１から６のいずれか一項に記載の情報処理装置であって、前記特徴抽出対象情報取得手段が、複数の特徴抽出対象情報を取得し、前記組合せ特定手段が、前記親標識対応要素と前記子標識対応要素との組合せが含まれる前記特徴抽出対象情報の数が予め定められた条件を満足する前記組合せを特定し、前記中間標識特定手段が、前記中間標識対応要素を含む前記特徴抽出対象情報の数が予め定められた条件を満足する前記中間標識として選択される前記標識を特定することとしたものである。
【００１１】
請求項８に記載の発明は、プログラムであって、それぞれ複数の標識のうちのいずれかと関連付けられた複数の要素と、前記要素間の親子関係を示す親子関係情報と、を含む特徴抽出対象情報を取得する特徴抽出対象情報取得手段、子標識として選択される前記標識に関連付けられた子標識対応要素が親標識として選択される前記標識に関連付けられた親標識対応要素の子孫に該当する、前記特徴抽出対象情報に含まれる前記親標識対応要素と前記子標識対応要素との組合せの数が、予め定められた条件を満足する、前記親標識として選択される前記標識と前記子標識として選択される前記標識との組合せを特定する組合せ特定手段、前記親標識対応要素の子孫に該当し前記子標識対応要素の先祖に該当する、中間標識として選択される前記標識に関連付けられた、前記特徴抽出対象情報に含まれる中間標識対応要素の数が、予め定められた条件を満足する、前記中間標識として選択される前記標識を特定する中間標識特定手段、前記組合せ特定手段により特定される組合せ、及び、前記中間標識特定手段により特定される標識に基づいて、前記親標識対応要素、前記子標識対応要素及び前記中間標識対応要素それぞれの間の親子関係の特徴を示す特徴情報を生成する特徴情報生成手段、としてコンピュータを機能させることとしたものである。
【発明の効果】
【００１２】
請求項１，８に記載の発明によれば、複数の要素と、要素間の親子関係を示す親子関係情報と、を含む情報から、要素間の親子関係の特徴が効率よく抽出される。
【００１３】
請求項２に記載の発明によれば、親標識として選択される標識や子標識として選択される標識を予め定められた条件により絞り込んだ上で、親標識として選択される標識と子標識として選択される標識との組合せが特定される。
【００１４】
請求項３に記載の発明によれば、子標識として選択される標識が、親標識対応要素の子孫に該当する子標識対応要素の数に関する条件により予め絞り込まれる。
【００１５】
請求項４に記載の発明によれば、親標識として選択される標識が、子標識対応要素の先祖に該当する親標識対応要素の数に関する条件により予め絞り込まれる。
【００１６】
請求項５に記載の発明によれば、予め定められている候補のうちの親標識として選択される標識が関連付けられている要素、又は、予め定められている候補のうちの子標識として選択される標識が関連付けられている要素を含む、要素間の親子関係の特徴を示す特徴情報が生成される。
【００１７】
請求項６に記載の発明によれば、要素間の兄弟関係に関する特徴を示す特徴情報が生成される。
【００１８】
請求項７に記載の発明によれば、標識に関連付けられている要素を含む特徴抽出対象情報の数に関する条件に基づいて特徴情報が生成される。
【発明を実施するための最良の形態】
【００１９】
以下、本発明の実施形態について図面に基づき詳細に説明する。
【００２０】
図１は、本実施形態における情報処理装置１０のハードウェア構成の一例を示す図である。図１に例示するように、本実施形態における情報処理装置１０は、制御部１２と、記憶部１４と、ユーザインタフェース（ＵＩ）部１６と、を含んで構成されている。これらの要素は、バス１８を介して接続される。
【００２１】
制御部１２は、ＣＰＵ等のプログラム制御デバイスであり、情報処理装置１０にインストールされるプログラムに従って動作する。
【００２２】
記憶部１４は、ＲＯＭやＲＡＭ等の記憶素子やハードディスクなどである。記憶部１４には、制御部１２によって実行されるプログラムなどが記憶される。また、記憶部１４は、制御部１２のワークメモリとしても動作する。
【００２３】
ＵＩ部１６は、ディスプレイ、マイク、スピーカー、ボタンなどであり、利用者が行った操作の内容や、利用者が入力した音声を制御部１２に出力する。また、このＵＩ部１６は、制御部１２から入力される指示に従って情報を表示出力したり音声出力したりする。
【００２４】
本実施形態では、図２に例示する、複数の木構造の特徴抽出対象情報２０（図２の例では、第１特徴抽出対象情報２０−１〜第６特徴抽出対象情報２０−６）が予め記憶部１４に記憶されている。なお、ＵＩ部１６が利用者により入力される情報を制御部１２に出力して、制御部１２がこの情報に基づいて特徴抽出対象情報２０を生成して、記憶部１４に出力してもよい。そして、本実施形態では、記憶部１４に記憶されている特徴抽出対象情報２０に基づいて、図３に例示する木構造の特徴情報２２が生成される。特徴情報２２は、特徴抽出対象情報２０に含まれるノード２４間の親子関係の特徴的なパターンを示している。
【００２５】
本実施形態における特徴抽出対象情報２０や特徴情報２２は、例えば、ＸＭＬデータである。各特徴抽出対象情報２０及び特徴情報２２はそれぞれ、複数のノード２４と、ノード２４間の親子関係を示すエッジ２６とを、含んでいる。各ノード２４は、具体的には、例えば、ＸＭＬデータにおける、タグの名称、タグの値、属性、属性の値などに対応する。以降、各ノード２４について、そのノード２４とエッジ２６により接続されているノード２４のうち、親にあたるノード２４を親ノードと、子にあたるノード２４を子ノードと呼ぶ。また、そのノード２４からエッジ２６により親ノード方向にたどってたどり着けるノード２４を先祖ノードと、エッジ２６により子ノード方向にたどってたどり着けるノード２４を子孫ノードと呼ぶ。また、そのノード２４と親ノードが共通するノード２４を兄弟ノードと呼ぶ。また、各特徴抽出対象情報２０において、親ノードを有さないノード２４をルートノード２８と呼び、子ノードを有さないノード２４をリーフノード３０と呼ぶ。本実施形態における特徴抽出対象情報２０は、公知の木構造のデータの実装方法によって実装されており、その実装方法は特に問わない。また、特徴抽出対象情報２０や特徴情報２２は木構造である必要はなく、要素（例えば、ノード２４）と、要素間の親子関係を示す親子関係情報（例えば、エッジ２６）を含んでいればよい。
【００２６】
本実施形態では、例えば、図２に例示する特徴抽出対象情報２０に含まれる各ノード２４は、標識（ラベル）３２及びノード識別子３４と関連付けられている。標識３２は複数種類存在し、各ノード２４は、これらの標識３２のうちのいずれか１つが関連付けられている。また、これらの標識３２のうちのいくつか（具体的には、例えば、「Ｖ」、「Ｗ」、「Ｘ」、「Ｙ」、「Ｚ」の標識３２）が、注目標識（フォーカスラベル）３２ａとして予め設定されている。各ノード２４には、そのノード２４が含まれる特徴抽出対象情報２０内で一意のノード識別子３４（例えば、特徴抽出対象情報２０内で深さ優先探索を行った際の順番に対応するノード識別子３４）が関連付けられている。
【００２７】
図４は、本実施形態に係る情報処理装置１０により実現される機能の一例を示す機能ブロック図である。図４に例示するように、本実施形態に係る情報処理装置１０は、機能的には、特徴抽出対象情報取得部４０、組合せ特定部４２、中間標識特定部４４、特徴情報生成部４６、を含むものとして機能する。そして、組合せ特定部４２は、親標識特定部４２ａと、子標識特定部４２ｂと、を含む。これらの要素は制御部１２を主として実現される。これらの要素は、コンピュータである情報処理装置１０にインストールされたプログラムを、情報処理装置１０に含まれる制御部１２で実行することにより実現されている。なお、このプログラムは、例えば、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭなどのコンピュータ可読な情報伝達媒体を介して、あるいは、インターネットなどの通信ネットワークを介して情報処理装置１０に供給される。
【００２８】
特徴抽出対象情報取得部４０は、例えば、図２に例示する特徴抽出対象情報２０（具体的には、例えば、第１特徴抽出対象情報２０−１〜第６特徴抽出対象情報２０−６）を取得する。
【００２９】
組合せ特定部４２は、子標識として選択される標識に関連付けられた子標識対応要素が親標識として選択される標識に関連付けられた親標識対応要素の子孫に該当する、特徴抽出対象情報２０に含まれる親標識対応要素と子標識対応要素との組合せの数が、予め定められた条件を満足する、親標識として選択される標識と子標識として選択される前記標識との組合せを特定する。そして、本実施形態では、組合せ特定部４２は、親標識特定部４２ａと、子標識特定部４２ｂと、を含む。
【００３０】
中間標識特定部４４は、親標識対応要素の子孫に該当し子標識対応要素の先祖に該当する、中間標識として選択される前記標識に関連付けられた、特徴抽出対象情報２０に含まれる中間標識対応要素の数が、予め定められた条件を満足する、中間標識として選択される標識を特定する。
【００３１】
特徴情報生成部４６は、組合せ特定部４２により特定される組合せ、及び、中間標識特定部４４により特定される標識に基づいて、親標識対応要素、子標識対応要素及び中間標識対応要素それぞれの間の親子関係の特徴を示す特徴情報２２を生成する。
【００３２】
［特徴情報生成処理］
本実施形態では、上述の各要素が、図３に例示する特徴情報２２を生成する特徴情報生成処理を実行する。以下、特徴情報生成処理の流れの一例を、図５に例示するフロー図を参照しながら説明する。
【００３３】
まず、特徴抽出対象情報取得部４０が、図２に例示する複数の木構造の特徴抽出対象情報２０を取得する（Ｓ１０１）。
【００３４】
そして、親標識特定部４２ａが、各標識３２について、その標識３２が関連付けられている特徴抽出対象情報２０に含まれるノード２４の数を算出する（Ｓ１０２）。なお、Ｓ１０２に例示する処理で、親標識特定部４２ａが、各標識３２について、その標識３２が関連付けられているノード２４を含む特徴抽出対象情報２０の数を算出してもよい。
【００３５】
そして、親標識特定部４２ａが、予め定められた条件を満足する少なくとも１つの標識３２（例えば、予め定められた閾値以上（又は、その閾値を超える）の数のノード２４と関連付けられている標識３２や、予め定められた閾値以上（又は、その閾値を超える）の数の特徴抽出対象情報２０に、関連付けられているノード２４が含まれている標識３２）それぞれを親標識として特定する（Ｓ１０３）。
【００３６】
そして、特徴情報生成部４６が、Ｓ１０３に例示する処理で特定される親標識のうちの１つ（例えば、「Ａ」の標識３２）を選択して、その親標識に対応する１つのノード２４から構成される特徴情報２２を生成する（Ｓ１０４）。
【００３７】
そして、子標識特定部４２ｂ及び特徴情報生成部４６が、後述する第１特徴情報伸張処理を実行する（Ｓ１０５）。そして、Ｓ１０３に例示する処理で特定された親標識のうちで、１０４に例示する処理において選択されていない親標識が存在する場合は（Ｓ１０６：Ｙ）、その親標識について、特徴情報生成部４６が、Ｓ１０４に例示する処理を実行する。Ｓ１０４に例示する処理において選択されていない親ラベルが存在しない場合は（Ｓ１０６：Ｎ）、処理を終了する。
【００３８】
［第１特徴情報伸張処理］
次に、第１特徴情報伸張処理の流れの一例を図６に例示するフロー図を参照しながら説明する。第１特徴情報伸張処理は、Ｓ１０４に例示する処理において生成される１つのノード２４から構成される特徴情報２２それぞれについて繰り返し実行される。
【００３９】
まず、子標識特定部４２ｂが、上述の各注目標識３２ａ（例えば、「Ｖ」、「Ｗ」、「Ｘ」、「Ｙ」、「Ｚ」）に対応するカウンタ情報を生成し、値を０に設定する（Ｓ２０１）。そして、子標識特定部４２ｂが、処理の対象となる特徴情報２２に含まれるノード２４に対応する標識３２（親標識）に関連付けられた、特徴抽出対象情報２０のうちのいずれかに含まれるノード２４（親標識対応ノード）を１つ特定する（Ｓ２０２）。そして、子標識特定部４２ｂが、Ｓ２０２で特定されたノード２４（親標識対応ノード）の子孫ノードであるノード２４を１つ取得する（Ｓ２０３）。そして、Ｓ２０３で取得したノード２４に関連付けられた標識３２が注目標識３２ａに該当する場合は、子標識特定部４２ｂが、その注目標識３２ａに対応するカウンタ情報の値を１増やす（Ｓ２０４）。このように、子標識として選択される標識３２の候補が予め定められていてもよい。なお、親標識として選択される標識３２の候補が予め定められていてもよい。
【００４０】
そして、Ｓ２０３に例示する処理で取得されていない子孫ノードがまだ存在する場合は（Ｓ２０５：Ｙ）、子標識特定部４２ｂは、そのノード２４についてＳ２０３に例示する処理を実行する。
【００４１】
存在しない場合は（Ｓ２０５：Ｎ）、子標識特定部４２ｂが、Ｓ２０２に例示する処理で特定されていないノード２４（親標識対応ノード）が存在するか否かを確認する（Ｓ２０６）。存在する場合は（Ｓ２０６：Ｙ）、そのノード２４（親標識対応ノード）についてＳ２０２に例示する処理を実行する。
【００４２】
存在しない場合は（Ｓ２０６：Ｎ）、子標識特定部４２ｂが、各注目標識３２ａに対応するカウンタ情報の値に基づいて、予め定められた条件を満足する少なくとも１つの注目標識３２ａ（例えば、予め定められた閾値以上（又は、その閾値を超える）の数のノード２４と関連付けられている標識３２）を子標識として特定する（Ｓ２０７）。
【００４３】
そして、特徴情報生成部４６が、Ｓ２０７に例示する処理で特定される子標識のうちの１つ（例えば、「Ｙ」）を選択して、処理の対象となる特徴情報２２に対応する標識３２（親標識）に対応するノード２４（親標識ノード）と、Ｓ２０７に例示する処理で特定される子標識に対応するノード２４（子標識ノード）と、これらのノード２４間の親子関係を示すエッジ２６と、を含む特徴情報２２（例えば、「Ａ」と「Ｙ」のノード２４を含む特徴情報２２）を生成する（Ｓ２０８）。そして、中間標識特定部４４が、Ｓ２０８に例示する処理で生成される特徴情報２２について、後述する探索境界情報生成処理を実行する（Ｓ２０９）。そして、組合せ特定部４２、中間標識特定部４４及び特徴情報生成部４６が、後述する第２特徴情報伸張処理を実行する（Ｓ２１０）。そして、Ｓ２０８に例示する処理において選択されていない子標識が存在する場合は（Ｓ２１１：Ｙ）、特徴情報生成部４６が、その子標識について、Ｓ２０８に例示する処理を実行する。Ｓ２０８に例示する処理において選択されていない子標識が存在しない場合は（Ｓ２１１：Ｎ）、処理を終了する。
【００４４】
なお、カウンタ情報が、注目標識３２ａに関連付けられている親標識対応ノードの子孫ノードを含む特徴抽出対象情報２０の数を示すようにしてもよい。すなわち、組合せ特定部４２が、親標識対応ノードと子標識対応ノードとの組合せが含まれる特徴抽出対象情報２０の数が予め定められた条件を満足する組合せを特定してもよい。
【００４５】
［探索境界情報生成処理］
次に、Ｓ２０８に例示する処理で生成される特徴情報２２について実行される探索境界情報生成処理（Ｓ２０９参照）の流れの一例を図７に例示するフロー図を参照しながら説明する。探索境界情報生成処理は、Ｓ２０８に例示する処理で生成される特徴情報２２について、各特徴抽出対象情報２０に対して以下の処理が繰り返し実行される。
【００４６】
まず、中間標識特定部４４が、処理の対象となる特徴抽出対象情報２０について、あるノード２４（例えば、ルートノード２８）から、あるノード２４（例えば、リーフノード３０）へと至る、エッジ２６で連結されたパス（以降、エッジパス４８（図８参照）と呼ぶ）を特定する（Ｓ３０１）。図８に、第１特徴抽出対象情報２０−１について特定される６つのエッジパス４８（左から順に第１エッジパス４８−１〜第６エッジパス４８−６）の一例を示す。
【００４７】
そして、中間標識特定部４４が、Ｓ２０８に例示する処理で生成される特徴情報２２に基づいて、初期化された探索境界情報５０（図９参照）を生成する（Ｓ３０２）。図９はＳ３０１〜Ｓ３０４に例示する処理が終了した際の探索境界情報５０の一例を示す図である。探索境界情報５０は、左から順に設定されるエッジパス４８の番号であるエッジパス番号５２と、合流深さ値５４と、子ノード深さ値５６（初期値は−１）と、探索最深値５８（初期値は−１）と、を含む。ここで、合流深さ値５４は、そのエッジパス４８の左に存在するエッジパス４８と合流するノード２４のルートノード２８からの深さを示す。なお、最も左に存在するエッジパス４８（図９の例では、第１エッジパス４８−１）については、合流深さ値５４は０に設定される。なお、子ノード深さ値５６と探索最深値５８の詳細については後述する。
【００４８】
そして、中間標識特定部４４が、各エッジパス４８について、Ｓ２０８に例示する処理で生成される特徴情報２２に子標識ノードとして含まれるノード２４に関連付けられた標識３２と関連付けられている、特徴抽出対象情報２０に含まれるノード２４（子標識対応ノード）のうち、最も深いノード２４の深さを特定し、この深さを示す値に、そのエッジパス４８に対応する探索境界情報５０の子ノード深さ値５６を更新する（Ｓ３０３）。このように、子ノード深さ値５６は、最も深い位置に存在する子標識対応ノードの深さを示す。具体的には、図９の例では、子標識が「Ｙ」である場合には、第１エッジパス４８−１の子ノード深さ値５６は−１のままであり、第２エッジパス４８−２の子ノード深さ値５６は３となる。
【００４９】
そして、中間標識特定部４４が、右のエッジパス４８から順に、探索最深値５８の値を更新する（Ｓ３０４）。中間標識特定部４４は、具体的には、例えば、第６エッジパス４８−６については、子ノード深さ値５６を探索最深値５８に設定する。そして、他のエッジパス４８については、子ノード深さ値５６が−１でない場合は、中間標識特定部４４は、例えば、（（子ノード深さ値５６の値）−１）を探索最深値５８に設定する。具体的には、例えば、中間標識特定部４４は、第５エッジパス４８−５の探索最深値５８を３に、第４エッジパス４８−４の探索最深値５８を２に、第２エッジパス４８−５の探索最深値５８を２に設定する。子ノード深さ値５６が−１である場合は、中間標識特定部４４は、例えば、右隣のエッジパス４８の探索最深値５８が−１である場合はその値を、右隣のエッジパス４８の探索最深値５８が−１でない場合はそのエッジパス４８の合流深さ値５４の値を、探索最深値５８に設定する。中間標識特定部４４は、具体的には、例えば、第３エッジパス４８−５の探索最深値５８を１に、第１エッジパス４８−１の探索最深値５８を２に設定する。
【００５０】
このようにして、中間標識特定部４４は、Ｓ２０８に例示する処理で生成される特徴情報２２について、図９に例示する、各特徴抽出対象情報２０に対応する探索境界情報５０を生成する。
【００５１】
本実施形態では、中間標識特定部４４が、各特徴抽出対象情報２０について、図１０に例示するエッジパス管理情報６０を予め生成する。エッジパス管理情報６０は、各ノード２４に対応するノード識別子３４、ノード２４に関連付けられている標識３２、ルートノード２８からの深さ（このノード２４とルートノード２８との間に存在するエッジ２６の数に対応）を示す深さ値６２、そのノード２４を通るエッジパス４８のエッジパス番号５２のうちの最小値である最小エッジパス番号６４、を含む。中間標識特定部４４は、エッジパス管理情報６０に基づいて、上述の探索境界情報生成処理を実行してもよい。
【００５２】
また、探索境界情報５０が、次のエッジパス４８に含まれるノード２４のノード識別子３４を含んでいてもよい。
【００５３】
［第２特徴情報伸張処理］
次に、第２特徴情報伸張処理（Ｓ２１０参照）の流れの一例を説明する。第２特徴情報伸張処理は、中間標識特定処理と特徴情報分岐処理とを含む。第２特徴情報伸張処理は、Ｓ２０８に例示する処理で生成される特徴情報２２に対して実行される。なお、中間標識特定処理と特徴情報分岐処理とは並行して実行されてもよく、順次実行されてもよい。また、このとき、どちらの処理が先に実行されてもよい。
【００５４】
［中間標識特定処理］
中間標識特定処理の流れの一例を図１１に例示するフロー図を参照しながら説明する。中間標識特定処理は、図６に例示する第１特徴情報伸張処理（Ｓ２０１〜Ｓ２１１）とほぼ同様の処理である。以下、中間標識特定処理が、第１特徴情報伸張処理と異なる点を中心に説明する。
【００５５】
Ｓ４０１に例示する処理では、中間標識特定部４４が、上述の各標識３２に対応するカウンタ情報を生成し、値を０に設定する。
【００５６】
Ｓ４０４に例示する処理では、中間標識特定部４４が、Ｓ４０３に例示する処理で特定される子孫ノードが探索境界情報５０に基づいて特定される探索範囲内である（例えば、探索最深値５８以下の深さの値を持つノード２４である）か否かを判断する。
【００５７】
具体的には、中間標識特定部４４は、例えば、図１０に例示するエッジパス管理情報６０の深さ値６２に基づいて、第１特徴抽出対象情報２０−１のノード識別子３４がｖ１であるノード２４の深さが１であり、最小エッジパス番号６４が１であると特定する。そして、中間標識特定部４４が、図９に例示する探索境界情報５０に基づいて、第１エッジパス４８−１の探索最深値５８が２であり、深さ値６２の値１よりも大きいので、このノード２４が探索範囲内であると判断する。同様にして、中間標識特定部４４は、ノード識別子３４がｖ２であるノード２４は探索範囲内であると判断し、ノード識別子３４がｖ３であるノード２４は探索範囲外であると判断する。
【００５８】
そして、探索範囲内である場合には、この子孫ノードは、親ラベルに対応するノード２４の子孫ノードであり子ラベルに対応するノード２４の先祖ノードであるので、中間標識特定部４４が、そのノード２４に関連付けられている標識３２に関連付けられるカウンタ情報の値を１増やす。
【００５９】
Ｓ４０７に例示する処理では、中間標識特定部４４が、各標識３２に対応するカウンタ情報の値に基づいて、予め定められた条件を満足する少なくとも１つの標識３２（例えば、予め定められた閾値以上（又は、その閾値を超える）の数のノード２４と関連付けられている標識３２）を中間標識として特定する。そして、Ｓ４０８に例示する処理では、Ｓ４０７に例示する処理で特定される中間標識のうちの１つ（例えば、「Ｂ」）を選択して、Ｓ２０８に例示する処理で生成される特徴情報２２の親標識ノード（例えば、「Ａ」のノード）と、子標識ノード（例えば、「Ｙ」のノード）との間に、中間標識に対応するノード２４（中間標識ノード）（例えば、「Ｂ」のノード）を追加（挿入）する。
【００６０】
中間標識特定処理では、Ｓ２０９及びＳ２１０に例示する処理に対応する処理は実行されない。
【００６１】
そして、Ｓ４０８に例示する処理において選択されていない中間標識が存在する場合は（Ｓ４０９：Ｙ）、中間標識特定部４４が、その中間標識について、Ｓ４０８に例示する処理を実行する。Ｓ４０８に例示する処理において選択されていない中間標識が存在しない場合は（Ｓ４０９：Ｎ）、処理を終了する。
【００６２】
このようにして、例えば、「Ａ」と「Ｙ」のノード２４を含む特徴情報２２に基づいて、例えば、「Ａ」と「Ｂ」と「Ｙ」のノード２４を含む特徴情報２２が生成される。
【００６３】
そして、中間標識特定部４４は、Ｓ４０９に例示する処理で特徴情報２２に追加されたノード２４（中間標識ノード）に対応する、特徴抽出対象情報２０に含まれるノード２４（中間標識対応ノード）を、Ｓ４０２に例示する処理における親標識対応ノードとして選択するようにして、上述のＳ４０１〜Ｓ４０９に例示する処理を再帰的に実行する。このようにして、例えば、「Ａ」と「Ｂ」と「Ｙ」のノード２４を含む特徴情報２２に基づいて、「Ａ」と「Ｂ」と「Ｃ」と「Ｙ」のノード２４を含む特徴情報２２が生成される。
【００６４】
なお、中間標識特定部４４が、中間標識対応要素を含む特徴抽出対象情報２０の数が予め定められた条件を満足する中間標識を特定してもよい。
【００６５】
［特徴情報分岐処理］
次に、特徴情報分岐処理の流れの一例を説明する。特徴情報分岐処理は、各特徴情報２２について、その特徴情報２２に含まれる、リーフノード３０であるノード２４とは異なる各ノード２４（分岐点ノード）について実行される。特徴情報分岐処理は、Ｓ２０２に例示する処理において、子標識特定部４２ｂが、分岐点ノードに対応する標識３２を親標識として、この標識３２に関連付けられたノード２４を特徴抽出対象情報２０のうちから１つ特定する点、及び、Ｓ２０３に例示する処理において、子標識特定部４２ｂが、既に特徴情報２２に分岐点ノードの子孫ノードとして追加されているノード２４に対応する、特徴抽出対象情報２０に含まれるノード２４及びその子孫ノード以外の子孫ノードを１つ取得する点、を除いては、上述のＳ２０１〜Ｓ２１１に例示する処理と同様の処理である。このように、組合せ特定部４２が、中間標識が選択された後に、特定された標識３２を親標識（又は子標識）として選択して、この標識３２と子標識（又は親標識）との組合せを特定してもよい。
【００６６】
上述の第２特徴情報伸張処理を再帰的に繰り返すことで、最終的には、図３に例示する特徴情報２２が生成される。なお、制御部１２が、特徴情報２２を表す画像を生成して、ディスプレイなどのＵＩ部１６に出力してもよい。また、制御部１２が、特徴情報２２を記憶部１４に記憶してもよい。
【００６７】
図１２に、上述の方法（Ｔｈｉｓ  Ｍｅｔｈｏｄ）と、従来の方法（Ｍｅｔｈｏｄ１、Ｍｅｔｈｏｄ２）とによる、ＸＭＬデータに対する特徴情報生成処理の処理時間を示す。横軸は、最低いくつの特徴抽出対象情報２０で出現したパターンを特徴情報２２として抽出するかを、縦軸は処理時間を示している。
【００６８】
なお、本発明は上記実施形態に限定されるものではない。
【００６９】
例えば、組合せ特定部４２が、標識３２毎に異なる閾値を設定して、その閾値以上（又は、その閾値を超える）の数のノード２４と関連付けられている標識３２を親標識や子標識として特定してもよい。また、組合せ特定部４２が、ノード２４に関連付けられている情報や特徴情報２２に基づいて、親標識や子標識を特定してもよい。なお、組合せ特定部４２が、特徴抽出対象情報取得部４０が特徴抽出対象情報２０を取得する際や、ＵＩ部１６から出力される情報に基づいて制御部１２が特徴抽出対象情報２０を生成する際などに、親標識や子標識を特定してもよい。また、組合せ特定部４２が、親標識や子標識として特定される標識３２に関連付けられたノード２４の所在を示す情報を親標識や子標識に関連付けた頻出ラベル情報を生成してもよい。
【００７０】
なお、各ノード２４が、そのノード２４又は子孫ノードに関連付けられたノード識別子３４が示す番号のうちの最小値と最大値の組合せであるＳＣＯＰＥ情報や子孫ノードのノード識別子３４の配列である子孫ノードリストと関連付けて記憶部１４に記憶されていてもよい。そして、子標識特定部４２ｂが、上述のＳ２０３に例示する処理において、ＳＣＯＰＥ情報や子孫ノードリストに基づいて、子孫ノードを取得してもよい。また、中間標識特定部４４が、上述のＳ４０３に例示する処理において、ＳＣＯＰＥ情報や子孫ノードリストに基づいて、子孫ノードを特定してもよい。
【００７１】
また、特徴抽出対象情報２０に含まれる各ノード２４を示す情報が深さ優先の順で記憶部１４に記憶されていてもよい。そして、子標識特定部４２ｂが、Ｓ２０３に例示する処理で、各ノード２４を深さ優先の順で取得してもよい。
【００７２】
また、子標識特定部４２ｂが、特徴情報２２に含まれる子標識に対応するノード２４（子ノード）を特定した後で、親標識特定部４２ａが、特徴情報２２に含まれる親標識に対応するノード２４（親ノード）を特定するようにしてもよい。
【００７３】
また、情報処理装置１２は、一つの筐体により構成されていても、複数の筐体により構成されていてもよい。
【００７４】
なお、本明細書中に記載された具体的な数値や、具体的な文字列は例示であり、これらの数値や文字列に限定されない。
【図面の簡単な説明】
【００７５】
【図１】本発明の一実施形態に係る情報処理装置のハードウェア構成の一例を示す図である。
【図２】特徴抽出対象情報の一例を示す図である。
【図３】特徴情報の一例を示す図である。
【図４】本発明の一実施形態に係る情報処理装置により実現される機能の一例を示す機能ブロック図である。
【図５】本実施形態に係る情報処理装置で行われる特徴情報生成処理の流れの一例を示すフロー図である。
【図６】本実施形態に係る情報処理装置で行われる第１特徴情報伸張処理の流れの一例を示すフロー図である。
【図７】本実施形態に係る情報処理装置で行われる探索境界情報生成処理の流れの一例を示すフロー図である。
【図８】エッジパスの一例を示す図である。
【図９】探索境界情報の一例を示す図である。
【図１０】エッジパス管理情報の一例を示す図である。
【図１１】本実施形態に係る情報処理装置で行われる中間標識特定処理の流れの一例を示すフロー図である。
【図１２】本実施形態に係る情報処理装置で行われる特徴情報生成処理と従来の特徴情報生成処理との処理時間の比較の一例を示す図である。
【符号の説明】
【００７６】
１０  情報処理装置、１２  制御部、１４  記憶部、１６  ユーザインタフェース（ＵＩ）部、１８  バス、２０  特徴抽出対象情報、２２  特徴情報、２４  ノード、２６  エッジ、２８  ルートノード、３０  リーフノード、３２  標識（ラベル）、３２ａ  注目標識（フォーカスラベル）、３４  ノード識別子、４０  特徴抽出対象情報取得部、４２  組合せ特定部、４２ａ  親標識特定部、４２ｂ  子標識特定部、４４  中間標識特定部、４６  特徴情報生成部、４８  エッジパス、５０  探索境界情報、５２  エッジパス番号、５４  合流深さ値、５６  子ノード深さ値、５８  探索最深値、６０  エッジパス管理情報、６２  深さ値、６４  最小エッジパス番号。
【図１】
2010134723.tif 000003
【図２】
2010134723.tif 000004
【図３】
2010134723.tif 000005
【図４】
2010134723.tif 000006
【図５】
2010134723.tif 000007
【図６】
2010134723.tif 000008
【図７】
2010134723.tif 000009
【図８】
2010134723.tif 000010
【図９】
2010134723.tif 000011
【図１０】
2010134723.tif 000012
【図１１】
2010134723.tif 000013
【図１２】
2010134723.tif 000014