(57)【要約】      （修正有）【課題】オントロジ上のクラス間の距離を計算する際に、計算量及びメモリの使用量を削減可能なオントロジ探索技術を提供する。【解決手段】取得部１０１は、オントロジデータの組データと始点及び終点の指定とを取得する。符号化部１０２は、取得部１０１が組毎に取得した組データ、目的関数、始点及び終点を符号化する。充足可能性判定部１０３は、オントロジ全体の構造を表すための組データを全て符号化部１０２が符号化した後、オントロジの構造を論理式で表現した制約式と、始点及び終点に関する制約式と、目的関数とをSATソルバに与えてSATソルバを実行し、目的関数の値が最小となるようなブール変数への割り当てを計算する。復号化部１０４は、充足可能性判定部１０３が判定した充足可能性の判定結果を解釈して、始点から終点に至る経路上に存在するクラスの並びと、始点及び終点間の距離とを出力する。【選択図】図３
2010055505.tif 000002
【特許請求の範囲】
【請求項１】
オントロジ上に配置された複数の構成要素と、構成要素間の位置関係とを示す１つ以上のオントロジデータから、２つの構成要素間の距離を計算するオントロジ探索装置であって、
始点及び終点のうち各々一方となる第１構成要素及び第２構成要素の指定を受け付ける受付部と、
前記オントロジに関する前記オントロジデータを全て取得する取得部と、
各前記オントロジデータによって示される各前記構成要素及び前記構成要素間の位置関係が取得される度に、前記構成要素をブール変数に対応付け、ブール変数の論理式に符号化する符号化部と、
前記論理式の充足可能性を判定する充足可能性判定部と、
前記論理式の充足可能性の判定結果を復号化し、前記第１構成要素と前記第２構成要素との間の距離と、前記第１構成要素から前記第２構成要素に至る経路上に存在する前記構成要素を得る復号化部とを備える
ことを特徴とするオントロジ探索装置。
【請求項２】
前記符号化部は、各前記構成要素及び前記構成要素間の位置関係が取得される度に、前記構成要素及び前記構成要素間の位置関係に対してブール変数の制約式を生成する第１生成部を有する
ことを特徴とする請求項１に記載のオントロジ探索装置。
【請求項３】
前記構成要素は、クラスであり、
前記位置関係は、上位下位の階層関係を表すis-a (subClassOf)関係であり、
前記第１生成部は、各前記クラス及び前記クラス間のis-a関係が取得される度に、前記クラス及び前記クラス間のis-a関係に対してブール変数の制約式を生成する
ことを特徴とする請求項２に記載のオントロジ探索装置。
【請求項４】
前記符号化部は、前記第１構成要素である第１クラス及び前記第２構成要素である第２クラスに対してブール変数の制約式を生成する第２生成部を有する
ことを特徴とする請求項３に記載のオントロジ探索装置。
【請求項５】
前記符号化部は、前記第１クラスと前記第２クラスとの間の距離を計算するためのブール変数の目的関数を生成する第３生成部を有する
ことを特徴とする請求項４に記載のオントロジ探索装置。
【請求項６】
前記第３生成部は、前記クラス及び前記クラス間のis-a関係に対して、前記第１クラスと前記第２クラスとの間の距離を計算するためのブール変数の目的関数を生成する
ことを特徴とする請求項５に記載のオントロジ探索装置。
【請求項７】
前記クラス間の位置関係に対して、重み係数が各々設定されており、
前記第３生成部は、前記オントロジに配置された全ての前記クラスについて各前記クラス間の位置関係に対して各々設定されている前記重み係数の和を表す目的関数を生成する
ことを特徴とする請求項６に記載のオントロジ探索装置。
【請求項８】
前記充足可能性判定部は、前記第１生成部が生成した前記制約式、前記第２生成部が生成した前記制約式及び前記目的関数を用いてSAT（Satisfiablity Problem）ソルバを実行する実行部と、
前記制約式が充足可能である場合、SATソルバの実行の結果、前記第１クラスから前記第２クラスに至る経路上に存在する各クラスに対応付けられたブール変数及び当該クラス間のis-a関係に対して対応付けられたブール変数を出力する出力部とを有する
ことを特徴とする請求項７に記載のオントロジ探索装置。
【請求項９】
前記実行部は、SATソルバを実行することにより、前記目的関数の値が最小となるブール変数への割り当てを計算する
ことを特徴とする請求項８に記載のオントロジ探索装置。
【請求項１０】
前記復号化部は、
前記ブール変数が出力された場合、当該ブール変数を、前記第１クラスから前記第２クラスに至る経路上に存在する各クラス及び当該クラス間のis-a関係に復号する変数復号化部と、
前記クラス間のis-a関係に設定された前記重み係数を用いて、前記第１クラスと前記第２クラスとの間の距離を計算する計算部と、
前記第１クラスと前記第２クラスとの間の距離と、前記第１クラスから前記第２クラスに至る経路上に存在する各前記クラスを識別するクラス識別情報とを出力する結果出力部とを有する
ことを特徴とする請求項８又は９に記載のオントロジ探索装置。
【請求項１１】
前記復号化部は、前記制約式が充足不能である場合、前記第１構成要素から前記第２構成要素に至る経路が存在しない旨を出力する
ことを特徴とする請求項１乃至１０のいずれか一項に記載のオントロジ探索装置。
【請求項１２】
前記取得部は、ネットワークを介して接続される情報処理装置にアクセスして、当該情報処理装置に記憶されている前記オントロジデータを取得する
ことを特徴とする請求項１乃至１１のいずれか一項に記載のオントロジ探索装置。
【請求項１３】
前記オントロジデータを記憶する記憶部を更に備え、
前記取得部は、前記オントロジデータを前記記憶部から読み出すことにより、前記オントロジデータを取得する
ことを特徴とする請求項１乃至１２のいずれか一項に記載のオントロジ探索装置。
【請求項１４】
受付部と、取得部と、符号化部と、充足可能性判定部と、復号化部とを備え、オントロジ上に配置された複数の構成要素と、構成要素間の位置関係とを示す１つ以上のオントロジデータから、２つの構成要素間の距離を計算するオントロジ探索装置で実行されるオントロジ探索方法であって、
始点及び終点のうち各々一方となる第１構成要素及び第２構成要素の指定を受け付ける受付ステップと、
前記オントロジに関する前記オントロジデータを全て取得する取得ステップと、
前記符号化部が、各前記オントロジデータによって示される各前記構成要素及び前記構成要素間の位置関係が取得される度に、前記構成要素をブール変数に対応付け、ブール変数の論理式に符号化する符号化ステップと、
前記充足可能性判定部が、前記論理式の充足可能性を判定する充足可能性判定ステップと、
前記論理式の充足可能性の判定結果を復号化し、前記第１構成要素と前記第２構成要素との間の距離と、前記第１構成要素から前記第２構成要素に至る経路上に存在する前記構成要素を得る復号化ステップとを含む
ことを特徴とするオントロジ探索方法。
【請求項１５】
請求項１４に記載のオントロジ探索方法をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オントロジにおけるクラス間の距離を計算するオントロジ探索装置、オントロジ探索方法及びプログラムに関する。
【背景技術】
【０００２】
近年、オントロジ技術を活用した情報処理装置の開発が盛んに行われている。オントロジとは、辞書の一種で、言葉のもつ概念を体系的に整理したものである。オントロジ上に配置された概念の位置関係が、概念間の相対的な意味を表現しており、この意味の情報を利用して、高度な知識処理を行うことが可能となってきている。このオントロジを表現するためのWeb記述言語として、OWL(Web Ontology Language)がある。OWLでは、概念を表すクラスと、その概念の具体的な表現を表すインスタンスとから構成される。概念やその具体的な表現である２つの語彙及びその位置関係を定義した２つ組がOWLにおいて並記されることによって、オントロジ全体が定義される。例えば、２つのクラスと、これらのクラス間の位置関係でありis-aと呼ばれる関係との３つの組は、２つのクラスの間の上位下位の階層関係を表す。クラス及びインスタンスと、クラス及びインスタンスの位置関係でありinstance-ofと呼ばれる関係との３つの組は、クラスに対するインスタンスの従属関係を表す。
【０００３】
ここで、オントロジを活用した応用システムの例を示す。例えば、特許文献１に記載された技術では、インターネット上のブログからクチコミ情報を収集して、商品に関する評判を分析し、肯定的な意見と否定的な意見との比率を求めている。この技術の特徴は、肯定的な意見や否定的な意見を意味する表現語から構成されたオントロジを参照している点にある。この技術では、ブログの文章を自然言語処理する際に、このオントロジ上の表現語を照合することによって、その文章が肯定的意見又は否定的意見のどちらを述べているのかを判定している。
【０００４】
また、特許文献２〜３には、オントロジを利用して、文書間の類似性を判定する技術が記載されている。これらの技術の特徴は、２つの文書から抽出した特徴的な表現語（特徴語）をオントロジと照合し、オントロジ上での位置関係をもとに、特徴語間の距離を計算してこれを類似性として用いている。特に特許文献３には、特徴語間の距離を計算する際に、一方の特徴語を始点とし他方の特徴語を終点としてオントロジ上の経路も求めることが記載されている。
【０００５】
ところで、一般的な語彙を網羅する実用的なオントロジのデータサイズはかなり大きい。このようなオントロジがインターネットなどのネットワークを介して取得される場合、ネットワークへの負荷や通信コストが増大する恐れがあった。このような背景から近年では、例えば特許文献４に記載されているように、オントロジの全体ではなく、ユーザが使用したい部分のみを取得して参照可能にした技術も開発されている。
【０００６】
【特許文献１】特開２００７−１８８３３０号公報
【特許文献２】特開平０５−２６６０８５号広報
【特許文献３】特開平１０−２１２４３号広報
【特許文献４】特開２００６−１１７３９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、特許文献１〜４のいずれの技術であっても、オントロジ上のクラス間の距離を計算する際には、オントロジ全体の構造をメモリ上に構築し、クラス間の位置関係を探索する必要がある。このため、オントロジの規模に対して指数時間の計算量を必要とする。また、オントロジの規模が大きくなる程より多くのメモリの使用量を必要とする。オントロジの規模とは、クラスおよびクラス間の位置関係の総数を意味する。従って、オントロジ上のクラス間の距離を計算する際に、計算量及びメモリの使用量を削減することが望まれていた。
【０００８】
本発明は、上記に鑑みてなされたものであって、オントロジ上のクラス間の距離を計算する際に、計算量及びメモリの使用量を削減可能なオントロジ探索装置、オントロジ探索方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、本発明は、オントロジ上に配置された複数の構成要素と、構成要素間の位置関係とを示す１つ以上のオントロジデータから、２つの構成要素間の距離を計算するオントロジ探索装置であって、始点及び終点のうち各々一方となる第１構成要素及び第２構成要素の指定を受け付ける受付部と、前記オントロジに関する前記オントロジデータを全て取得する取得部と、各前記オントロジデータによって示される各前記構成要素及び前記構成要素間の位置関係が取得される度に、前記構成要素をブール変数に対応付け、ブール変数の論理式に符号化する符号化部と、前記論理式の充足可能性を判定する充足可能性判定部と、前記論理式の充足可能性の判定結果を復号化し、前記第１構成要素と前記第２構成要素との間の距離と、前記第１構成要素から前記第２構成要素に至る経路上に存在する前記構成要素を得る復号化部とを備えることを特徴とする。
【００１０】
また、本発明は、受付部と、取得部と、符号化部と、充足可能性判定部と、復号化部とを備え、オントロジ上に配置された複数の構成要素と、構成要素間の位置関係とを示す１つ以上のオントロジデータから、２つの構成要素間の距離を計算するオントロジ探索装置で実行されるオントロジ探索方法であって、始点及び終点のうち各々一方となる第１構成要素及び第２構成要素の指定を受け付ける受付ステップと、前記オントロジに関する前記オントロジデータを全て取得する取得ステップと、前記符号化部が、各前記オントロジデータによって示される各前記構成要素及び前記構成要素間の位置関係が取得される度に、前記構成要素をブール変数に対応付け、ブール変数の論理式に符号化する符号化ステップと、前記充足可能性判定部が、前記論理式の充足可能性を判定する充足可能性判定ステップと、前記論理式の充足可能性の判定結果を復号化し、前記第１構成要素と前記第２構成要素との間の距離と、前記第１構成要素から前記第２構成要素に至る経路上に存在する前記構成要素を得る復号化ステップとを含むことを特徴とする。
【００１１】
また、本発明は、プログラムであって、上記のオントロジ探索方法をコンピュータに実行させることを特徴とする。
【発明の効果】
【００１２】
本発明によれば、クラス間の距離を計算する際に、オントロジの構造自体をメモリ上に構築する必要がなく、計算量及びメモリの使用量を削減可能になる。また、始点となる構成要素と終点となる構成要素との間の距離に加え、始点となる構成要素から終点となる構成要素に至る経路上に存在する構成要素及びその構成要素間の位置関係も求めることができるため、オントロジの構造の探索を改めて行う必要がない。
【発明を実施するための最良の形態】
【００１３】
以下に添付図面を参照して、この発明にかかるオントロジ探索装置、方法およびプログラムの最良な実施の形態を詳細に説明する。
【００１４】
（１）構成
まず、オントロジについて説明する。オントロジは、上述したように、言葉のもつ概念を体系的に整理したものであり、複数の概念が構成要素としてオントロジ上に各々配置されている。概念を表すクラスは、直感的には、概念の分類名を表し、概念の具体的な表現を表すインスタンスは、概念の実例を表す。例えば、オントロジの対象を商品に限定した商品オントロジの場合、クラスは商品ジャンルを表し、インスタンスは商品名を表す。図１は、商品オントロジを概念的に例示する図である。同図に示されるオントロジでは、６つのクラスと４つのインスタンスとが示されている。６つのクラス「乗用車」,「セダン」,「SUV」,「クーペ」,「クロスオーバーSUV」，「クロカン」はいずれも自動車の車種を表す。４つのインスタンス「car1」,「car2」,「car3」,「car4」はいずれも自動車の製品名を表す。例えば、「クロスーバーSUV」クラスは、SUVでありながらセダンのような上質さと走行性能を兼ね備えた車種であり、「セダン」クラスと「SUV」クラスとの両方の部分クラスとして定義されている。
【００１５】
次に、SAT問題について説明する。ブール変数へ真偽値を割り当てる問題を充足可能性判定問題(Beelean Satisfiablity Problem、略してSAT)と呼ぶ。SAT問題とは、制約式が与えられたときに、それに含まれるブール変数に対して真または偽をうまく割り当てて、制約式を真にできるかどうかを判定する問題である。即ち、ブール変数の集合と、ブール変数の論理式で表現された制約式の集合とが与えられたとき、全ての制約式を真にするような、変数への真または偽の割り当てを見つける、あるいはそのような割り当てが存在しないことを証明する。ある割り当てが制約式を「充足する」とは、その割り当ての元では制約式が真であることをいう。制約式が「充足可能である」とは、ある割り当てが存在し、それが制約式を充足する場合をいう。
【００１６】
SAT問題は、理論上はブール変数の数に対して指数時間の計算量を必要とする問題である。しかし近年では、SAT問題を高速に解くアルゴリズムの研究が進んでおり、その研究成果が様々な分野で応用されている。例えば、形式的検証、FPGAルーティング、電力最適化、AIプランニングで、成果が報告されている。
【００１７】
SAT問題を解くツールをSATソルバと呼ぶ。近年多くのSATソルバが開発され、インターネット上から入手できる。代表的なSATソルバを以下に示す。
* MiniSat
http://minisat.se/
* zChaff
http://www.princeton.edu/~chaff/zchaff.html
* Berkmin
http://eigold.tripod.com/BerkMin.html
【００１８】
SAT問題は一般に、CNF(Conjunctive Normal Form、和積標準形)と呼ばれる形式の論理式で表現される。CNFとは、ブール論理における論理式の正規化の一種であり、１つ以上のリテラルの論理和を１つ以上含む論理積の形式となる。リテラルとは、ブール変数またはブール変数の否定、または定数‘1’又は‘0’を表す。リテラル‘1’は真を表し、リテラル‘0’は偽を表す。また、ブール変数を小文字のアルファベットと数字との組み合わせで表現し、論理否定、論理積、論理和の各演算子を、それぞれ ~、∧、∨で表す。
【００１９】
CNF式の例を式(1)に示す。
φ = (x1∨x2)∧(x1∨~x2)∧(~x1∨~x2)・・・（１）
【００２０】
式φは２つのブール変数及び６つのリテラレルから構成される。ここで、式φの充足可能性を調べてみる。割り当て{x1=1、 x2=1}の元では、式φの3番目の節 ~x1∨~x2 は偽になるために、式φは充足されない。一方、割り当て{x1=1、 x2=0}の元では、式φは充足される。したがって、式φは充足可能である。
【００２１】
CNFは、SAT問題における制約式の表現方法として広く用いられているが、最近では、より表現力の高い PB(Pseudo-Boolean)と呼ばれる形式の論理式が用いられる。PBはブール変数に自然数の係数を付与した線形不等式で、次のような形式で表される。
a1x1 + a2x2 + ・・・ + anxn ≧ b
ここで、ai、bは自然数を表し、xiはブール変数のリテラルを表す。
【００２２】
CNF式からPB式へは容易に変換可能で、例えば、CNF式
a ∨ b ∨ c
は、PB式
1 a + 1 b + 1 c ≧ 1
と表すことができる。
【００２３】
PB問題は、SAT問題を拡張して最適化問題を扱うようにしたものである。即ち、PB問題は、目的関数がブール変数の線形の式で与えられたとき、全ての制約式を真にするような、ブール変数への割り当てのうち、目的関数の値を最大化あるいは最小化するような割り当てを求める問題である。SAT問題が、制約式の充足可能性を求めるのに対し、PB問題は目的関数の元でブール変数への割り当てを決定する問題である。
【００２４】
近年多くのpseudo-Boolean SATソルバが開発され、インターネット上から入手できる。代表的なpseudo-Boolean SATソルバを以下に示す。
* MiniSat+
http://minisat.se/
* PBS4
http://www.aloul.net/Tools/pbs4/
* Pueblo
http://www.eecs.umich.edu/~hsheini/pueblo/
* SAT4J
http://www.sat4j.org/
【００２５】
以上のような技術を利用した本実施の形態に特有の構成について説明する。図２は、本実施の形態にかかる探索システムの構成を例示する図である。探索システムは、オントロジ探索装置１００と、サーバ２００とがネットワークＮＴを介して接続されて構成される。ネットワークとは、例えば、ＬＡＮ（Local Area Network）、イントラネット、イーサネット（登録商標）又はインターネットなどである。サーバ２００は、オントロジ上に配置された複数の構成要素と、構成要素間の位置関係とを示すオントロジデータを保持しており、ネットワークＮＴ上に複数存在し得る。オントロジ探索装置１００もオントロジデータを保持している。即ち、本実施の形態においては、オントロジデータは、あるオントロジ全体の構造の一部を表すものであり、オントロジ全体の構造を表すためのオントロジデータはオントロジ探索装置１００及びサーバ２００の複数の装置に分散されて保持されている。オントロジ探索装置１００は、ネットワークＮＴを介して１つ又は複数のサーバ２００にアクセスして、オントロジ全体の構造を把握するためのオントロジデータを全て取得し、当該オントロジ上の指定されたクラス間の距離を計算する。
【００２６】
尚、本実施の形態のオントロジ探索装置１００は、装置全体を制御するＣＰＵ（Central Processing Unit）等の制御装置と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）等の記憶装置と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶装置と、これらを接続するバスとを備えており、通常のコンピュータを利用したハードウェア構成となっている。また、データ作成装置１００には、情報を表示する表示装置と、ユーザの指示入力を受け付けるキーボードやマウス等の入力装置と、外部装置の通信を制御する通信Ｉ／Ｆ（interface）とが有線又は無線により各々接続される。
【００２７】
次に、このようなハードウェア構成において、オントロジ探索装置１００の有するＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することによりオントロジ探索装置１００において実現される各種機能について説明する。図３は、オントロジ探索装置１００の機能的構成を例示する図である。オントロジ探索装置１００は、取得部１０１と、符号化部１０２と、充足可能性判定部１０３と、復号化部１０４と、オントロジ格納部１０５とを有する。取得部１０１と、符号化部１０２と、充足可能性判定部１０３と、復号化部１０４とは、ＣＰＵのプログラム実行時にＲＡＭなどの記憶装置上に生成されるものである。オントロジ格納部１０５は、例えばＨＤＤなどの外部記憶装置に記憶されるものである。
【００２８】
オントロジ格納部１０５には、オントロジの構造を表すためのオントロジデータが記憶されている。本実施の形態においては、OWL形式のオントロジデータを取り扱う。図４〜５は、OWL形式のオントロジデータのデータ構成を例示する図である。図４は、オントロジ探索装置１００のオントロジ格納部１０５に記憶されたオントロジデータのデータ構成を例示する図である。図５は、サーバ２００に記憶されたオントロジデータのデータ構成を例示する図である。これらの図に示されるように、OWL形式のオントロジデータでは、オントロジを構成する要素である上位のクラス、下位のクラス及びこれらのクラス間のsubClassOf関係との３つが組として下位のクラス毎に示されている。以降、この３つの組のデータを組データという。組データでは、各クラスはクラスIDにより一意に識別される。クラスIDは、例えばURIとする。このURIは、クラスによって、オントロジ探索装置１００を格納場所として表すものもあれば、サーバ２００を格納場所として表すものもある。例えば、「http://ontology.XXXX.or.jp」がオントロジ探索装置１００のURIを表しているものとする。この場合、図４において、オントロジ探索装置１００のURIを引用しているクラス「http://ontology.XXXX.or.jp/#D」,「http://ontology.XXXX.or.jp/#E」,「http://ontology.XXXX.or.jp/#F」については、オントロジ探索装置１００に保持されていることを意味する。一方、「http://ontology.or.jp」が、オントロジ探索装置１００の外部である１つのサーバ２００のURIを表しているものとする。この場合、サーバ２００のURIを引用しているクラス「http://ontology.or.jp/#A」,「http://ontology.or.jp/#B」,「http://ontology.or.jp/#C」については、当該サーバ２００に保持されていることを意味する。尚、説明の便宜上、各URIにおいて「#」以降を用いて各クラスを識別する。図４において、組データＫＭ１は、下位クラス#Dに対して、subClassOf関係の上位クラスとしてクラス#Bが示されている。組データＫＭ２では、下位クラス#Eに対して、subClassOf関係の上位クラスとしてクラス#B,#Cの２つのクラスが示されている。組データＫＭ３では、下位クラス#Fに対して、subClassOf関係の上位クラスとしてクラス#Cが示されている。
【００２９】
また、図５に示されるように、サーバ２００に記憶されたオントロジデータについても、各組データが下位のクラス毎に示されている。組データＫＭ１０では、下位クラス#Bに対して、subClassOf関係の上位クラスとしてクラス#Aが示されている。組データＫＭ１０では、下位クラス#Cに対して、subClassOf関係の上位クラスとしてクラス#Aが示されている。
【００３０】
図６は、図４〜５に示したオントロジデータによって構成されるオントロジの構造をグラフ化して表現した図である。同図に示されるように、図４〜５に示したオントロジデータから、クラス#Aを最上位クラスとし、その直下の下位クラスがクラス#B,#Cであり、クラス#Bの直下の下位クラスがクラス#D,#Eであり、クラス#Cの直下の下位クラスがクラス#E,#Fであることが表されている。また、一点鎖線で囲まれた部分が、図４に示されるオントロジデータに含まれる組データによって表される部分である。また、点線で囲まれた部分が、図５に示されるオントロジデータに含まれる組データによって表される部分である。このように、オントロジを構成する全てのクラスについての組データによって、当該オントロジ全体の構造が把握可能になる。
【００３１】
図３の説明に戻る。取得部１０１は、このようなオントロジデータの組データを組毎に取得する。具体的には、取得部１０１は、オントロジ格納部１０５に記憶されたオントロジデータの読み出しを開始し、組データ毎に読み出しを行う。そして、取得部１０１は、読み出した組データに示されている各クラスについて、クラスIDであるURIによって表される格納場所がオントロジ探索装置１００ではない場合、当該URIによって表される格納場所であるサーバ２００にネットワークＮＴを介してアクセスしてオントロジデータの組データを取得する。図４〜５の例では、取得部１０１は、クラス#D,#E,#Fに関する組データＫＭ１〜ＫＭ３をオントロジ格納部１０５から取得し、クラス#A,#B,#Cに関する組データＫＭ１０，ＫＭ１１をサーバ２００から取得する。
【００３２】
また、取得部１０１には、始点となるクラスと終点となるクラスとを指定する操作入力が操作装置を介して入力される。この２つのクラスの間の距離が計算の対象となる。尚、始点と終点とを区別する必要がないので、２つのクラスのうち一方を始点とし他方を終点とすれば良い。
【００３３】
符号化部１０２は、取得部１０１が組毎に取得した組データ、目的関数、始点及び終点を符号化する。まず、組データの符号化について具体的に説明する。符号化部１０２は、各組データによって示される各クラス及びクラス間の各関係をそれぞれブール変数に対応付けてブール変数の論理式を生成し、クラス間の位置関係に基づいて、オントロジの構造を論理式で表現した制約式を生成することにより、符号化を行う。符号化の際には、クラス変数表、関係変数表及びクラス種類毎に異なる符号化ルールを用いる。クラス変数表は、各クラスと当該各クラスに対応付けられたブール変数との対応関係を表すものであり、符号化の際にＲＡＭなどの記憶装置に一時的に生成され適宜更新される。関係変数表は、クラス間の位置関係と各関係に対応付けられたブール変数との対応関係を表すものであり、符号化の際にＲＡＭなどの記憶装置に一時的に生成され適宜更新される。符号化ルールは予め定義されており例えばＨＤＤなどの外部記憶装置に記憶されている。
【００３４】
図７は、図４〜５に示されるオントロジデータに基づくクラス変数表のデータ構成を例示する図である。図４〜５に示されるオントロジデータでは、６つのクラスと、それらの間の６つのsubClassOf関係とが定義されていた。図７に示されるクラスIDは上述したようにこれらのクラスのURIを表す。クラス変数は、各クラスを表すブール変数を表す。クラスとクラス変数との対応関係は一意である。クラス種類は、オントロジの構造における階層関係を示すものであり、階層関係の種類として、「ルート」、「中間」及び「リーフ」のいずれかのタイプを表すものである。制約式は、当該クラスに関する制約式を表す。オントロジ探索装置１００は、組データの符号化の際、初めて出現したクラスをクラス変数表に登録し、クラス変数を定義する。クラス種類と制約式とは、符号化の実行中に登録したり更新したりする。
【００３５】
図８は、関係変数のデータ構成を例示する図である。同図に示されるように、クラス間の関係は、クラスIDの組、すなわちURIの組を表す。尚、図の簡略化のため、各クラスIDを#A,#B,#C,#D,#E,#Fとして表している。関係変数は、クラス間の位置関係を表すブール変数である。オントロジ探索装置１００は、組データの符号化の際に初めて出現した関係を関係変数表に登録し、関係変数を定義する。
【００３６】
図９は、図７に示したクラス変数及び図８に示した関係変数から構成されるオントロジの構造をグラフ化して表現した図である。同図においては、図６に示した構造を構成する各クラス及びクラス間の位置関係が、クラス変数及び関係変数に変換されて示されている。このように、各クラス及びクラス間の位置関係に対して対応付けられたブール変数によって、オントロジの構造が表現可能になる。ただし，図９は、図７及び図８に示したブール変数が表すオントロジの全体構造を説明するために示したものであり、実際の処理では、図９に示したオントロジ全体のグラフ構造がメモリ上に構築されるわけではない。
【００３７】
図１０〜１２は、クラス種類毎の符号化ルールを概念的に示す図である。図１０は、クラス種類がルートである場合の符号化ルールを示し、図１１は、クラス種類が中間である場合の符号化ルールを示し、図１２は、クラス種類が「リーフ」である場合の符号化ルールを示す図である。オントロジ探索装置１００は、符号化対象のクラスについて、クラス変数によって表されるクラス種類に応じた符号化ルールを適用して、制約式を生成する。このときオントロジ探索装置１００は、クラス変数表におけるクラス種類を適宜更新することにより、更新したクラス種類に応じた符号化ルールを改めて適用して、制約式を再生成するという処理を繰り返す。この結果、オントロジ探索装置１００は、最終的な制約式を生成することにより、組データを符号化する。図１３は、各クラスについて生成された制約式を示すクラス変数表のデータ構成を例示する図である。同図においては、各クラスについて判別されたクラス種類に応じて生成された制約式がクラス毎に表されている。
【００３８】
次に、目的関数の符号化について説明する。符号化部１０２は、SATソルバへ入力するために目的関数の制約式を定義することにより、目的関数を符号化する。目的関数の制約式として、符号化部１０２は、オントロジの構造上のクラス間の位置関係の全ての重みの和を表す制約式を定義する。この制約式は、オントロジの形状や、始点のクラス及び終点のクラスに依存せず、オントロジデータに対して一意に定まる。図１４は目的関数の定義を例示する図である。同図に示されるように、ここではクラス間の位置関係の重みを全て‘1’と仮定して制約式が定義されている。このようにして目的関数が符号化されて生成される。尚、後述するSATソルバではこの目的関数の値が最小となるようなブール変数の割り当てが計算されることにより、始点及び終点間の最小距離が求められることになる。
【００３９】
次に、始点及び終点の符号化について説明する。符号化部１０２は、始点及び終点に関する制約式を定義することにより、始点及び終点を符号化する。始点及び終点は経路上に必ず存在するクラスであるので必ず真になるような制約式を符号化部１０２は定義する。図１５は始点及び終点の符号化を模式的に例示する図である。同図に示されるように、例えば、始点に対するクラス変数が‘ｘ4’である場合、始点は‘（1*×4）=1’と符号化される。終点に対するクラス変数が‘ｘ6’である場合、終点は‘（1*×6）=1’と符号化される。
【００４０】
以上のようにして、符号化部１０２は、組データ、目的関数、始点及び終点を符号化して、SATソルバに入力するための制約式を各々生成する。図１６は、図４〜５に示したオントロジデータに基づいて符号化部１０２が行った符号化の結果を例示する図である。同図において「source node」は、始点が符号化されたものを示す。「destination node」は、終点が符号化されたものを示す。「constraints」は、各クラス及びクラス間の位置関係が符号化されたものを示す。
【００４１】
充足可能性判定部１０３は、オントロジ全体の構造を表すための組データを全て符号化部１０２が符号化した後、オントロジの構造を論理式で表現した制約式と、始点及び終点に関する制約式と、目的関数とをSATソルバに与えてSATソルバを実行し、目的関数の値が最小となるようなブール変数への割り当てを計算する。例えば、クラス#Dが始点として入力され、クラス#Fが終点として入力されたとすると、これらのクラス間の距離の最小値を計算する問題は、即ち、図９に示した変数x4と変数x6とが表す２つの変数間が最短となる最短経路を求める問題となる。そして、充足可能性判定部１０３は、SATソルバの実行における制約式の充足可能性を判定する。図９に示したオントロジの構造においては、制約式が充足可能となる。図１７は、この場合の始点となる変数x4と終点となる変数x6との間の最短経路を概念的に示す図である。同図に示されるように、制約式が充足可能である場合、変数x4から変数x6までの間の距離の最小値は「4」であり、変数x4から変数x6までに至る最短経路に存在する変数x4,X9,x2,x7,x1,x8,x3,x12,x6の並びが得られる。
【００４２】
復号化部１０４は、充足可能性判定部１０３が判定した充足可能性の判定結果を復号化する。具体的には、制約式が充足可能である場合、復号化部１０４は、クラス間の距離、及び始点から終点に至る経路上に存在するクラスのクラスIDの並びを得てこれを出力する。図１８は、図１７に示した変数の並びを復号した例を示す図である。同図においては、復号化部１０４は、変数x4と変数x6との間の最短経路に存在する各変数x4,x9,x2,x7,x1,x8,x3,x12,x6をクラス変数表及び関係変数表からクラスID及びクラス間の位置関係に変換することによりこれらを復号し、始点から終点に至る経路上に存在するクラスのクラスIDの並びを得る。この例では、クラスID#D,#B,#A,#C,#Fが得られる。また、経路上のクラス間の位置関係として、(#D,#B),(#B,#A),(#A,#C),(#C,#F)の４つが得られる。そして、復号化部１０４は、得られたクラス間の位置関係の重みの和を計算することにより、始点及び終点間の距離を計算する。上述した例では、クラス間の位置関係の重みは全て‘1’であるから、４つの関係から、始点及び終点間の距離は‘4’と計算される。そして、復号化部１０４は、得られたクラスの並びと、距離とを出力する。尚、制約式が充足不能である場合、復号化部１０４は、始点から終点に至る経路がオントロジ上に存在しないと解釈してその旨を示す情報を出力する。
【００４３】
以上のような構成によって、オントロジ探索装置１００は、オントロジ上のクラス間の距離を計算する問題を上述した充足可能性判定問題(SAT)として解く。即ち、オントロジ探索装置１００は、OWL形式のオントロジデータによって表されるオントロジをグラフとしてみなすのではなく、オントロジの２つのクラスとこれらのクラス間の位置関係との組（組データ）をSATソルバへ入力するための制約式に変換する。このとき、オントロジ探索装置１００は、OWL形式のオントロジデータについて組データ毎に逐次的に処理して、SAT問題の制約式を付与して、SATソルバへの入力とする。そして、オントロジ探索装置１００は、全ての組データについて制約式を付与した後、当該制約式と、始点及び終点に関する制約式と、目的関数とを用いてSAT問題を解く。そして、オントロジ探索装置１００は、SAT問題の実行結果を解釈することにより、指定された２つのクラス間の距離を計算することができると共に、始点から終点に至る経路上に存在するクラス及びそのクラス間の位置関係も求めることができる。
【００４４】
（２）動作
次に、本実施の形態に係るオントロジ探索装置１００が行う距離計算処理の手順について図１９を参照して説明する。オントロジ探索装置１００には、始点となるクラスと終点となるクラスとを指定する操作入力が操作装置を介して入力される（ステップＳ１）。オントロジ探索装置１００は、外部記憶装置に記憶されているオントロジデータの読み出しを開始し（ステップＳ２）、組データを組毎に読み出す（ステップＳ３）。このときオントロジ探索装置１００は、読み出す対象の組データが、オントロジ探索装置１００自身ではなくサーバ２００が保持するオントロジデータを参照しているか否かを判断する(ステップＳ４)。上述したように、各クラスのクラスIDはURIで表されている。従って、読み出した組データによって示される２つのクラスのうち少なくとも一方が、オントロジ探索装置１００のURIを引用しておらず、サーバ２００に保持されるオントロジデータのURIを引用している場合、サーバ２００が保持するオントロジデータを参照しているとオントロジ探索装置１００は判断する。そして、ステップＳ４の判断結果が肯定的である場合、オントロジ探索装置１００は、参照しているオントロジデータをサーバ２００から取得済みでありＲＡＭなどの記憶装置に記憶しているか否かを判断する（ステップＳ５）。当該判断結果が否定的である場合、オントロジ探索装置１００は、オントロジデータによって参照先として示されるサーバ２００にアクセスして、該当のオントロジデータを取得して記憶装置に記憶させ（ステップＳ６）、ステップＳ７に進む。ステップＳ４の判断結果が否定的である場合及びステップＳ５の判断結果が肯定的である場合も、ステップＳ７に進む。
【００４５】
ステップＳ７では、オントロジ探索装置１００は、組データを符号化する。即ち、オントロジ探索装置１００は、組データによって示される上位のクラス、下位のクラス及びクラス間の各関係をそれぞれブール変数に対応付けてブール変数の論理式を生成し、クラス間の位置関係に基づいて、オントロジの構造を論理式で表現した制約式を生成する。
【００４６】
図２０は、ステップＳ７で組データを符号化する処理の詳細な手順を示すフローチャートである。まず、組データによって示される上位のクラスC1及び下位のクラスC2が入力されると（ステップＳ２０）、オントロジ探索装置１００は、上述した関係変数表（図８参照）を参照して、クラスC1,C2の位置関係が登録されているか否かを判断する（ステップＳ２１）。当該判断結果が否定的である場合、オントロジ探索装置１００はクラスC1,C2の位置関係を関係変数表に登録する（ステップＳ２２）。次に、オントロジ探索装置１００は、クラスC1、C2それぞれについて、上述したクラス変数表（図７参照）に登録済みか否かを判断すべく、まず、クラスC1がクラス変数表に登録済みか否かを判断する（ステップＳ２３）。上位クラスC1が未登録である場合（ステップＳ２３：ＹＥＳ）、オントロジ探索装置１００は、まずクラス変数表にクラスC1を登録する。また、クラスC1が未登録ということはクラス種類は「ルート」となるので、オントロジ探索装置１００は、クラスC1のクラス種類を「ルート」にセットし、クラスC1に対してルートクラス用の符号化ルールを適用し、制約式を生成する（ステップＳ２６）。
【００４７】
一方、上位クラスC1がクラス変数表に登録済みである場合（ステップＳ２３：ＮＯ）、オントロジ探索装置１００は、クラス変数表に表されるクラス種類が「ルート」であるか否かを判断する（ステップＳ２４）。当該判断結果が肯定的である場合、オントロジ探索装置１００は、クラスC1に対してルートクラス用の符号化ルールを適用して制約式を生成する（ステップＳ２７）。尚、ステップＳ２４の判断結果が否定的である場合、オントロジ探索装置１００は、クラス変数表に表されるクラス種類が「中間」であるか否かを判断する（ステップＳ２５）。当該判断結果が肯定的である場合、オントロジ探索装置１００は、クラスC1に対して中間クラス用の符号化ルールを適用して制約式を生成する（ステップＳ２８）。尚、ステップＳ２５の判断結果が否定的である場合、オントロジ探索装置１００は、クラス変数表におけるクラスC1のクラス種類を「中間」に変更することによりクラス変数表を更新し、クラスC1に対してリーフクラス用の符号化ルールを適用して制約式を生成する（ステップＳ２９）。クラス変数表によって表されるクラス種類が「ルート」又は「中間」である場合、クラス種類は変更されない。
【００４８】
また、オントロジ探索装置１００は、下位クラスC2がクラス変数表に登録済みか否かを判断する（ステップＳ３０）。下位クラスC2が未登録である場合（ステップＳ３０：ＹＥＳ）、オントロジ探索装置１００はまずクラス変数表にクラスC2を登録する。また、クラスC2が未登録ということはクラス種類は「リーフ」となるので、オントロジ探索装置１００は、クラスC2のクラス種類を「リーフ」にセットし、クラスC2に対してリーフクラス用の符号化ルールを適用し、制約式を生成する（ステップＳ３３）。一方、下位クラスC2がクラス変数表に登録済みである場合（ステップＳ３０：ＮＯ）、オントロジ探索装置１００は、クラス変数表に表されるクラス種類が「ルート」であるか否かを判断する（ステップＳ３１）。当該判断結果が肯定的である場合、オントロジ探索装置１００は、クラス変数表におけるクラスC2のクラス種類を「中間」に変更することによりクラス変数表を更新し、クラスC2に対してリーフクラス用の符号化ルールを適用して制約式を生成する（ステップＳ３４）。尚、ステップＳ３１の判断結果が否定的である場合、オントロジ探索装置１００は、クラス変数表に表されるクラス種類が「中間」であるか否かを判断する（ステップＳ３２）。当該判断結果が肯定的である場合、オントロジ探索装置１００は、クラスC2に対して中間クラス用の符号化ルールを適用して制約式を生成する（ステップＳ３５）。尚、ステップＳ３２の判断結果が否定的である場合、オントロジ探索装置１００は、クラスC2に対して中間クラス用の符号化ルールを適用して制約式を生成する（ステップＳ３６）。クラス変数表によって表されるクラス種類が「中間」又は「リーフ」である場合、クラス種類は変更されない。
【００４９】
以上のようにして、ステップＳ７で処理の対象となる組データによって表されるクラスC1,C2が初めて入力される際にクラス変数表に登録され、仮の制約式が生成される。その後、ステップＳ８，Ｓ３〜Ｓ５を経て新たに行われるステップＳ７で処理の対象となる新たな組データによってクラスC1又はC2が表されるとき、クラス種類に応じてクラス変数表が適宜更新され、符号ルールが適宜新たに適用されて制約式が再生成される。このような処理が繰り返されて、結果的に、オントロジ上の全ての各クラスの階層関係に応じた制約式が生成されることになる。
【００５０】
図１９に戻り、ステップＳ７で組データを論理式に変換した後、オントロジ探索装置１００は、全ての組データについて符号化を行ったか否かを判断する（ステップＳ８）。当該判断結果が否定的である場合、オントロジ探索装置１００は、新たな組データに対して、ステップＳ３以降の処理を行う。このようにオントロジ探索装置１００は、組データの符号化を組毎に行う。ステップＳ８の判断結果が肯定的である場合、全てのオントロジデータについて符号化を行ったか否かを判断する（ステップＳ９）。当該判断結果が否定的である場合、オントロジ探索装置１００は、ステップＳ７で取得したオントロジデータに対して、ステップＳ２以降の処理を行う。このようにオントロジ探索装置１００は、オントロジ全体の構造を把握するためのオントロジデータの全てを取得して符号化を組毎に行う。
【００５１】
そして、ステップＳ９の判断結果が肯定的となった場合、オントロジ探索装置１００は、SATソルバへ入力するために目的関数の制約式を定義することにより、目的関数を符号化する（ステップＳ１０）。次いで、オントロジ探索装置１００は、始点及び終点に関する制約式を定義する（ステップＳ１１）。その後、オントロジ探索装置１００は、ステップＳ７で生成した制約式、ステップＳ１０で定義した制約式及びステップＳ１１で定義した制約式をSATソルバに入力して、SATソルバを実行する。
【００５２】
そして、オントロジ探索装置１００は、SATソルバの実行における制約式の充足可能性を判定し、判定結果に基づいて、SATソルバの実行結果を復号化する。具体的には、制約式が充足可能である場合、オントロジ探索装置１００は、始点及び終点間の最小の距離を得ると共に、始点から終点に至る経路上に存在するクラス及びそのクラス間の位置関係を求め、当該距離と当該経路上に存在するクラスのクラスIDの並びとを出力する。例えば、SATソルバの実行結果として、図１７に示されるように変数x4,x9,x2,x7,x1,x8,x3,x12,x6の並びが得られた場合、オントロジ探索装置１００は、これらの変数をクラス変数表及び関係変数表からクラスID及びクラス間の位置関係に変換し、始点から終点に至る経路上に存在するクラスのクラスIDの並びを得る。この例では、図１８に示したように、クラスID#D,#B,#A,#C,#Fが得られる。また、経路上のクラス間の位置関係として、(#D,#B),(#B,#A),(#A,#C),(#C,#F)の４つが得られる。そして、オントロジ探索装置１００は、得られたクラス間の位置関係の重みの和を計算することにより、始点及び終点間の距離を計算し（この例では‘4’である）、得られたクラスの並びと、距離とを出力する。尚、制約式が充足不能である場合、オントロジ探索装置１００は、始点から終点に至る経路がオントロジ上に存在しないと解釈してその旨を示す情報を出力する。
【００５３】
以上のようにして、オントロジ全体の構造を把握するために必要なオントロジデータであり複数の装置に分散されているオントロジデータを全て取得することにより、オントロジ全体の構造を正確に把握することができる。そして、このように取得したオントロジデータに示されている上位のクラス、下位のクラス及びこれらの２つのクラス間のsubClassOf関係をSATソルバに入力するための制約式に変換することにより、オントロジ全体の構造をグラフ化してメモリ上に構築する処理が不要となる。このため、メモリの使用量を削減することができる。また、制約式へ変換するという符号化を組毎に逐次行うことにより、変換を高速に行うことができる。また、SAT問題を解くための長年培われた効率化ノウハウを活用することができるため、オントロジ上の構造を探索する問題を短時間で解くことができる。また、クラス間の距離に加え、当該経路上に存在するクラス及びそのクラス間の位置関係も求めることができるため、オントロジの構造の探索を改めて行う必要がない。
【００５４】
また、以上のような構成は、例えば、オントロジ・メトリックスを計算する際に用いて好適である。オントロジ・メトリックスとは、大規模なオントロジが構築される際、そのオントロジが構造的にバランスのとれたものかどうかを評価するための指標である。オントロジ・メトリックスは、オントロジをノードとリンクとから構成されたグラフとみなし、グラフの構造面を指標化したものである。ここでは、ノードはクラスを表し、リンクはクラス間の位置関係を表すものとする。オントロジ・メトリックスの例として、オントロジの高さ（深さ）、幅などがある。これらのオントロジ・メトリックスを計算するためには、グラフを探索し、グラフ上のノード間の位置関係を求める必要がある。例えば、高さは、オントロジ上の最上位に位置するノードと、最深部に位置するノードとの距離である。また、幅であれば、オントロジ上で最も離れた位置に存在する２つのノードの距離である。従って、本実施の形態に係る構成によってノード間の距離を計算することで、オントロジ・メトリックスをより効率的に計算することができる。
【００５５】
[変形例]
なお、本発明は前記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、前記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。また、以下に例示するような種々の変形が可能である。
【００５６】
＜変形例１＞
上述した実施の形態において、オントロジ探索装置１００で実行される各種プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また、当該各種プログラムを、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録して提供するように構成しても良い。この場合には、プログラムは、オントロジ探索装置１００において上記記録媒体から読み出されて実行されることにより例えばＲＡＭなどの記憶装置上にロードされ、上記機能的構成において説明した各部が記憶装置上に生成される。
【００５７】
＜変形例２＞
上述した実施の形態においては、オントロジ全体の構造を表すためのオントロジデータは、あるオントロジ全体の構造の一部を表すものであり、オントロジ探索装置１００及びサーバ２００の複数の装置に分散されて保持されているものとした。しかし、オントロジデータは、オントロジ全体の構造の全部を表すものであっても良い。また、オントロジ全体の構造の一部を表す複数のオントロジデータが全てオントロジ探索装置１００に保持される構成であっても良い。この場合、オントロジ探索システムにおいては、サーバ２００を備えず、オントロジ探索装置１００は、オントロジ全体の構造を表すためのオントロジデータの全てをＨＤＤなどの外部装置に記憶しておき、上述の距離算出処理を行う際に外部記憶装置からオントロジデータを読み出すことによりこれを取得するようにしても良い。
【００５８】
また、上述した実施の形態においては、オントロジデータにおいてクラスを一意に識別するためのクラスIDとして、URIを用いたが、これに限らない。また、クラスの格納場所として、ネットワークＮＴ上のURLや、オントロジ探索装置１００内のローカルファイルのパスが指定されるようにしても良い。
【００５９】
また、上述した実施の形態においては、OWL形式のオントロジデータを取り扱ったが、オントロジデータのデータ形式はこれに限らない。
【００６０】
＜変形例３＞
上述した実施の形態の目的関数では、クラス間の位置関係の重みを全て‘1’と仮定して制約式を定義したが、クラス間の位置関係毎に重みを変えても良い。
【図面の簡単な説明】
【００６１】
【図１】一実施の形態にかかる商品オントロジを概念的に例示する図である。
【図２】同実施の形態にかかる探索システムの構成を例示する図である。
【図３】同実施の形態にかかるオントロジ探索装置１００の機能的構成を例示する図である。
【図４】同実施の形態にかかるオントロジ探索装置１００のオントロジ格納部１０５に記憶されたオントロジデータのデータ構成を例示する図である。
【図５】同実施の形態にかかるサーバ２００に記憶されたオントロジデータのデータ構成を例示する図である。
【図６】図４〜５に示したオントロジデータによって構成されるオントロジの構造をグラフ化して表現した図である。
【図７】図４〜５に示されるオントロジデータに基づくクラス変数表のデータ構成を例示する図である。
【図８】同実施の形態にかかる関係変数のデータ構成を例示する図である。
【図９】図７に示したクラス変数及び図８に示した関係変数から構成されるオントロジの構造をグラフ化して表現した図である。
【図１０】同実施の形態にかかるクラス種類がルートである場合の符号化ルールを示す図である。
【図１１】同実施の形態にかかるクラス種類が中間である場合の符号化ルールを示す図である。
【図１２】同実施の形態にかかるクラス種類が「リーフ」である場合の符号化ルールを示す図である。
【図１３】同実施の形態にかかる各クラスについて生成された制約式を示すクラス変数表のデータ構成を例示する図である。
【図１４】同実施の形態にかかる目的関数の定義を例示する図である。
【図１５】同実施の形態にかかる始点及び終点の符号化を模式的に例示する図である。
【図１６】図４〜５に示したオントロジデータに基づいて符号化部１０２が行った符号化の結果を例示する図である。
【図１７】図９に示したオントロジの構造において制約式が充足可能となる場合の変数x4と変数x6との間の最短経路を概念的に示す図である。
【図１８】図１６に示した変数の並びを復号した例を示す図である。
【図１９】同実施の形態にかかるオントロジ探索装置１００が行う距離計算処理の手順を示すフローチャートである。
【図２０】図１８に示したステップＳ７で組データを符号化する処理の詳細な手順を示すフローチャートである。
【符号の説明】
【００６２】
１００  オントロジ探索装置
１０１  取得部
１０２  符号化部
１０３  充足可能性判定部
１０４  復号化部
１０５  オントロジ格納部
２００  サーバ
ＮＴ  ネットワーク
【図１】
2010055505.tif 000003
【図２】
2010055505.tif 000004
【図３】
2010055505.tif 000005
【図４】
2010055505.tif 000006
【図５】
2010055505.tif 000007
【図６】
2010055505.tif 000008
【図７】
2010055505.tif 000009
【図８】
2010055505.tif 000010
【図９】
2010055505.tif 000011
【図１０】
2010055505.tif 000012
【図１１】
2010055505.tif 000013
【図１２】
2010055505.tif 000014
【図１３】
2010055505.tif 000015
【図１４】
2010055505.tif 000016
【図１５】
2010055505.tif 000017
【図１６】
2010055505.tif 000018
【図１７】
2010055505.tif 000019
【図１８】
2010055505.tif 000020
【図１９】
2010055505.tif 000021
【図２０】
2010055505.tif 000022