(57)【要約】      （修正有）【課題】意味認識におけるエントリとノードの関係強度に要する計算負荷を軽減する。【解決手段】外部から言葉が入力される入力部１と、計算結果を出力する出力部７を備え、さらに、エントリＤＢ２と、エントリＤＢ３と、ノードＤＢ４と、関係強度ＤＢ５をそれぞれＨＤＤやメモリなどによって構成される記憶装置により実現し、さらに関係強度計算部６がＭＰＵ等によって構成される演算装置によりプログラムの実行により実現する。最初に有向パスに沿って関係強度を計算し、他のパスはエントリからの距離を基準に順方向のパスだけ加算する。【選択図】図１
2007072904.tif 000002
【特許請求の範囲】
【請求項１】
予め設定されたノードを記憶するノードＤＢと、
予め設定されたエントリを記憶するエントリＤＢと、
予め設定されたノード同士の関係強度を記憶する関係強度ＤＢと、
ノードとエントリの関係について予め設定された関係強度を記憶するインデクスＤＢと、
エントリに最寄りのノードにインデクスＤＢに記憶された関係強度を付与し、関係強度ＤＢに記憶された関係強度で重み付けされた枝で生成された重み付きグラフ上において、前記ノードを根として到達可能な全ての他のノードを含む有向木を選択し、この有向木に属する枝の重みに基づいてエントリから各ノードへの関係強度を算出する関係強度計算部と、
を備えることを特徴とする関係強度計算装置。
【請求項２】
前記関係強度計算部は、
エントリに近いノードから発する枝を有向木に加える枝として優先して選択し、根から各ノードまでの有向木上の枝の重みの積算値を根の関係強度に乗算し、その結果を各ノードに付与される関係強度とする
ことを特徴とする請求項１に記載の関係強度計算装置。
【請求項３】
前記関係強度計算部は、
有向木に属さず有向閉路を生じない枝について根に近いノードより発している枝を順次に加えた部分グラフを形成し、
加えた枝の出所ノードの関係強度に枝の重みを乗じた値を枝の行き先ノードの関係強度に加算し、その加算結果に比例するように下流の各ノードの関係強度の修正を実行する
ことを特徴とする請求項１または２に記載の関係強度計算装置。
【請求項４】
前記関係強度計算部は、
修正した下流の各ノードの前記関係強度に基づいて最大の関係強度を有するノードを選択することを特徴とする請求項３に記載の関係強度計算装置。
【請求項５】
前記関係強度計算部は、
修正した下流の各ノードの前記関係強度に基づいて最大からあらかじめ指定された上位個数の関係強度を有するノードを選択することを特徴とする請求項３に記載の関係強度計算装置。
【請求項６】
ノードＤＢにおいて、予め設定されたノードを記憶するステップと、
エントリＤＢにおいて、予め設定されたエントリを記憶するステップと、
関係強度ＤＢにおいて、予め設定されたノード同士の関係強度を記憶するステップと、
インデクスＤＢにおいて、ノードとエントリの関係について予め設定された関係強度を記憶するステップと、
関係強度計算部において、エントリに最寄りのノードにインデクスＤＢに記憶された関係強度を付与し、関係強度ＤＢに記憶された関係強度で重み付けされた枝で生成された重み付きグラフ上において、前記ノードを根として到達可能な全ての他のノードを含む有向木を選択し、この有向木に属する枝の重みに基づいてエントリから各ノードへの関係強度を算出するステップと、
を有することを特徴とする関係強度計算方法。
【請求項７】
前記関係強度計算部は、
エントリに近いノードから発する枝を有向木に加える枝として優先して選択し、根から各ノードまでの有向木上の枝の重みの積算値を根の関係強度に乗算し、その結果を各ノードに付与される関係強度とするステップ
を有することを特徴とする請求項６に記載の関係強度計算方法。
【請求項８】
前記関係強度計算部は、
有向木に属さず有向閉路を生じない枝について根に近いノードより発している枝を順次に加えた部分グラフを形成し、
加えた枝の出所ノードの関係強度に枝の重みを乗じた値を枝の行き先ノードの関係強度に加算し、その加算結果に比例するように下流の各ノードの関係強度の修正を実行するステップ
を有することを特徴とする請求項６または７に記載の関係強度計算方法。
【請求項９】
前記関係強度計算部は、
修正した下流の各ノードの前記関係強度に基づいて最大の関係強度を有するノードを選択するステップを有することを特徴とする請求項８に記載の関係強度計算方法。
【請求項１０】
前記関係強度計算部は、
修正した下流の各ノードの前記関係強度に基づいて最大からあらかじめ指定された上位個数の関係強度を有するノードを選択するステップを有することを特徴とする請求項８に記載の関係強度計算方法。
【請求項１１】
互いに表現形式が異なる物品表に含まれる項目名同士を比較して互いが比較対象となり得るか否かを判定するための関係強度計算を用いた比較装置であって、
予め設定された項目名を記憶するノードＤＢと、
予め設定された項目名間の関係強度を記憶する関係強度ＤＢと、
関係強度ＤＢに記憶された関係強度で重み付けされた枝で生成された重み付きグラフ上において、項目名を根として到達可能な全ての他の項目名を含む有向木を選択し、この有向木に属する枝および有向木の根からの距離に基づいて発ノードを優先順位づけし、その順位に従って選択された順方向の枝の重みに基づいて項目名間の関係強度を算出する関係強度計算部と、
関係強度計算部にて算出された関係強度に基づいて項目名同士が互いに比較対象に出来る度合いを判定する比較対象判定部と、
を備えることを特徴とする関係強度計算を用いた比較装置。
【請求項１２】
互いに表現形式が異なる物品表に含まれる項目値同士を比較して物品の一致／不一致を判定するための関係強度計算を用いた比較装置であって、
予め設定された項目値を記憶するノードＤＢと、
予め設定された項目値間の関係強度を記憶する関係強度ＤＢと、
関係強度ＤＢに記憶された関係強度で重み付けされた枝で生成された重み付きグラフ上において、項目値を根として到達可能な全ての他の項目値を含む有向木を選択し、この有向木に属する枝および有向木の根からの距離に基づいて発ノードを優先順位づけし、その順位に従って選択された順方向の枝の重みに基づいて項目値間の関係強度を算出する関係強度計算部と、
関係強度計算部にて算出された関係強度に基づいて項目値同士の一致／不一致を判定し、不一致の場合に代替の物品を提示する代替品提示手段と、
を備えることを特徴とする関係強度計算を用いた比較装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エントリの意味をノードとの関係強度に基づいた計算により意味認識するための技術に関する。
【背景技術】
【０００２】
従来において、言葉を意味認識するための技術として、意味認識の対象となる言葉と意味との間の関係の強さを表す関係強度を用い、その言葉との関係強度が最も強い意味を計算により求めることが行われている。
【０００３】
この技術では、意味認識の対象となる言葉をエントリとしておき、意味をノードとしておく。一つのエントリに対してその意味を表す候補となるノードは複数存在しているので、各ノードごとに重み付けがあらかじめなされている。この重み付けはエントリを基準にして、そのエントリの意味となる可能性が高いものから順に大きな値でもって重み付けがされる。
【０００４】
あるエントリの意味を求めるために、まずエントリとノードとの関係に基づく結びつけ（パスの生成）を行う。この結びつけはノードが複数存在する場合には一つのエントリに対して複数のノードとの間で結び付けが生成され、さらに各ノード同士の間においても相互の関係に基づいた結びつけを行う。
【０００５】
次にエントリからノードまでの全ての有向パスを探索し、探索したパス毎に関係強度の積を求め、その解を該パスの関係強度とする。この計算処理を全てのパスについて実行し、さらに算出された関係強度の和を算出する。そして算出した和の中から最も大きな値を示すノードをエントリの意味として抽出され、該エントリの意味として意味認識がされる。
【特許文献１】特開平９−１５３０６８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述の方法では、計算するパス数が多くなるとそれぞれの関係強度の積算だけでも最大でノード数の３乗の計算が必要となり、多大な計算負荷が生じていた。
【０００７】
また、パスの探索においてパスと複数のノードの組み合わせにおいて閉路が生じた場合に、この閉路を計算対象から除外する処理のために多大な計算負荷が生じていた。
【０００８】
本発明は、上記の課題に鑑みてなされたもので、その目的は、意味認識におけるエントリとノードの関係強度に要する計算負荷を軽減することにある。
【課題を解決するための手段】
【０００９】
課題を解決するために、請求項１に記載の本発明は、予め設定されたノードを記憶するノードＤＢと、予め設定されたエントリを記憶するエントリＤＢと、予め設定されたノード同士の関係強度を記憶する関係強度ＤＢと、ノードとエントリの関係について予め設定された関係強度を記憶するインデクスＤＢと、エントリに最寄りのノードにインデクスＤＢに記憶された関係強度を付与し、関係強度ＤＢに記憶された関係強度で重み付けされた枝で生成された重み付きグラフ上において、前記ノードを根として到達可能な全ての他のノードを含む有向木を選択し、この有向木に属する枝の重みに基づいてエントリから各ノードへの関係強度を算出する関係強度計算部と、を備える。
【００１０】
また、請求項２に記載の本発明は、請求項１において、前記関係強度計算部は、エントリに近いノードから発する枝を有向木に加える枝として優先して選択し、根から各ノードまでの有向木上の枝の重みの積算値を根の関係強度に乗算し、その結果を各ノードに付与される関係強度とする。
【００１１】
また、請求項３に記載の本発明は、請求項１または２において、前記関係強度計算部は、有向木に属さず有向閉路を生じない枝について根に近いノードより発している枝を順次に加えた部分グラフを形成し、加えた枝の出所ノードの関係強度に枝の重みを乗じた値を枝の行き先ノードの関係強度に加算し、その加算結果に比例するように下流の各ノードの関係強度の修正を実行する。
【００１２】
また、請求項４に記載の本発明は、請求項３において、前記関係強度計算部は、修正した下流の各ノードの前記関係強度に基づいて最大の関係強度を有するノードを選択する。
【００１３】
また、請求項５に記載の本発明は、請求項３において、前記関係強度計算部は、修正した下流の各ノードの前記関係強度に基づいて最大からあらかじめ指定された上位個数の関係強度を有するノードを選択する。
【００１４】
また、請求項６に記載の本発明は、ノードＤＢにおいて、予め設定されたノードを記憶するステップと、エントリＤＢにおいて、予め設定されたエントリを記憶するステップと、関係強度ＤＢにおいて、予め設定されたノード同士の関係強度を記憶するステップと、インデクスＤＢにおいて、ノードとエントリの関係について予め設定された関係強度を記憶するステップと、関係強度計算部において、エントリに最寄りのノードにインデクスＤＢに記憶された関係強度を付与し、関係強度ＤＢに記憶された関係強度で重み付けされた枝で生成された重み付きグラフ上において、前記ノードを根として到達可能な全ての他のノードを含む有向木を選択し、この有向木に属する枝の重みに基づいてエントリから各ノードへの関係強度を算出するステップと、を有する。
【００１５】
また、請求項７に記載の本発明は、請求項６において、前記関係強度計算部は、エントリに近いノードから発する枝を有向木に加える枝として優先して選択し、根から各ノードまでの有向木上の枝の重みの積算値を根の関係強度に乗算し、その結果を各ノードに付与される関係強度とするステップを有する。
【００１６】
また、請求項８に記載の本発明は、請求項６または７において、前記関係強度計算部は、有向木に属さず有向閉路を生じない枝について根に近いノードより発している枝を順次に加えた部分グラフを形成し、加えた枝の出所ノードの関係強度に枝の重みを乗じた値を枝の行き先ノードの関係強度に加算し、その加算結果に比例するように下流の各ノードの関係強度の修正を実行するステップを有する。
【００１７】
また、請求項９に記載の本発明は、請求項８において、前記関係強度計算部は、修正した下流の各ノードの前記関係強度に基づいて最大の関係強度を有するノードを選択するステップを有する。
【００１８】
また、請求項１０に記載の本発明は、請求項８において、前記関係強度計算部は、修正した下流の各ノードの前記関係強度に基づいて最大からあらかじめ指定された上位個数の関係強度を有するノードを選択するステップを有する。
【００１９】
また、請求項１１に記載の本発明は、互いに表現形式が異なる物品表に含まれる項目名同士を比較して互いが比較対象となり得るか否かを判定するための関係強度計算を用いた比較装置であって、予め設定された項目名を記憶するノードＤＢと、予め設定された項目名間の関係強度を記憶する関係強度ＤＢと、関係強度ＤＢに記憶された関係強度で重み付けされた枝で生成された重み付きグラフ上において、項目名を根として到達可能な全ての他の項目名を含む有向木を選択し、この有向木に属する枝および有向木の根からの距離に基づいて発ノードを優先順位づけし、その順位に従って選択された順方向の枝の重みに基づいて項目名間の関係強度を算出する関係強度計算部と、関係強度計算部にて算出された関係強度に基づいて項目名同士が互いに比較対象に出来る度合いを判定する比較対象判定部と、を備える。
【００２０】
また、請求項１２に記載の本発明は、互いに表現形式が異なる物品表に含まれる項目値同士を比較して物品の一致／不一致を判定するための関係強度計算を用いた比較装置であって、予め設定された項目値を記憶するノードＤＢと、予め設定された項目値間の関係強度を記憶する関係強度ＤＢと、関係強度ＤＢに記憶された関係強度で重み付けされた枝で生成された重み付きグラフ上において、項目値を根として到達可能な全ての他の項目値を含む有向木を選択し、この有向木に属する枝および有向木の根からの距離に基づいて発ノードを優先順位づけし、その順位に従って選択された順方向の枝の重みに基づいて項目値間の関係強度を算出する関係強度計算部と、関係強度計算部にて算出された関係強度に基づいて項目値同士の一致／不一致を判定し、不一致の場合に代替の物品を提示する代替品提示手段と、を備える。
【発明の効果】
【００２１】
本発明によれば、意味認識におけるエントリとノードの関係強度に要する計算負荷を軽減することができる。
【発明を実施するための最良の形態】
【００２２】
＜第１の実施の形態＞
図１に第１の実施の形態の関係強度計算装置の全体構成図を示す。この図１において関係強度計算装置は、関係強度計算に用いるエントリ、インデクス、ノード、重み付け値等のパラメータ値が入力される入力部１と、関係強度計算の結果を出力する出力部７を備える。さらに関係強度計算装置は、インデクスＤＢ２と、エントリＤＢ３と、ノードＤＢ４と、関係強度ＤＢ５を備え、それぞれ図示しないＨＤＤやメモリなどによって構成される記憶装置により実現されている。また、関係強度計算部６が備わり、図示しないＭＰＵ（Ｍｉｃｒｏ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）等によって構成される演算装置によりプログラムを実行することで実現されている。
【００２３】
関係強度計算装置が計算する関係強度の結果は、ある言葉（エントリ）の意味を認識するための意味認識に用いられる。計算の結果、ある言葉（エントリ）との関係強度が最大値となる意味（ノード）をもって意味認識を行う技術である。
【００２４】
関係強度計算を実行するための準備としてエントリとノードをあらかじめ設定する他に、重み付け値とインデクスもあらかじめパラメータとして設定しておく。重み付け値は設定されたノード同士の関係について重み付け値を設定したデータテーブルであり、関係強度表として関係強度ＤＢ５に記憶される。
【００２５】
図２には、図１に示した関係強度計算装置による関係強度計算方法の概略を説明するための説明図を示す。この図２に示した説明図はノード間の関係強度計算について一般的な計算手法による計算例を示したものであり、後の図３に示す実施の形態による関係強度計算の計算例と対比することにより、その理解を容易にするための説明図である。
【００２６】
この図２において、まずエントリーノードであるＥを基準にして、エントリーノードＥ以外の任意のノードを一つ選ぶ。選んだノードについて、このノードから伸びるパスを全て列挙する。そして、各パス上の重みの積をとり、その総和を選んだノードの重みとする。次に、再び他の任意のノードを選び、同様の処理を繰り返す。この処理の繰り返しは全ノードについて実行され、未処理のノードが無くなった時点で終了する。
【００２７】
こうした一般的な計算手法は、全パスについて積和をとるか、あるいは枝重みを１／電気抵抗に見立てたモデルによる値をとる、といった計算手法であるが、いずれも手数が組み合わせ爆発になり、ノード数が少ないかグラフ構造が特別なとき以外は実用的でない。
【００２８】
そこで、実施の形態の関係強度計算方法では、元々不確実な対象なら、精度を犠牲にして計算量が少ない関係強度の定義を定める。最初に有向木に沿って計算し、他の枝は木に順方向のみ根寄り優先で加算する。こうすることにより相対的な関係強度の大小関係が大きくは狂わないので、随時更新されるノード間の関係強度が与えられるときに、隣接しないノード間の関係強度計算の簡略化を実現することができる。
【００２９】
次の図３に示すのは実施の形態の関係強度計算の計算例を説明するための説明図である。この図３に示す説明図において、その計算手順は、まずエントリノードであるＥを根とする有向木を選択する。すなわち、根（Ｅ）に近いノード発を優先採用する処理を行う。
【００３０】
次に、有向木経由のパスで枝重み積を計算し各ノードの重みとする。そして、根からの距離(ノードラベル)を基準に順方向の枝を順次選択する。枝追加毎に「発ノード重み＊追加枝重み」を行き先ノードに加算し、重みが変化したノードから既選択枝で到達できる隣接ノードの重みを比例修正する。
【００３１】
次に、到達可能な隣接ノードが無くなるまで前述の隣接ノードの重みの比例修正を反復して実行し、追加選択可能な枝が存在する限り順方向の枝を順次選択して本処理を繰り返し実行する。
【００３２】
こうした計算手法により、その計算手数はノ−ド数の３乗となるのでノード数の階乗＊ノード数となる一般的な計算手法（図２に示す）よりも計算手数を減らすことができる。
【００３３】
なお、解の安定性についてはエントリーノードを根とする有向木の選択に自由度があり、根からの距離を基準に順方向の枝を順次選択する際にも自由度があるため、算出される解にもばらつきが生じる。しかしながら、元データに曖昧さがあるランキング等で使用するには、このばらつきは実用上無視し得る。
【００３４】
さらに、この関係強度表の具体的な一例を図４に示す。例えば「危険」というノードに対して「危険」というノードの重み付け値は「０」とされている。一方、「危険」というノードと「救援」というノードの関係の重み付け値は「５０」に設定されている。
【００３５】
また、インデクスとはエントリとノードの一対一の関係においてそれぞれ設定された重み付け値を表記したデータテーブルである。このインデクスの例を図５に示しており、エントリごとに各ノードとの関係における重み付け値が設定されている。例えばエントリ「ぐぇ」について対応する各ノードのうち「危険」や「苦悶」との関係はそれぞれ「０」の重み付けであるのに対し、「怪我」というノードとの関係には「５５」の重み付けがされている。
【００３６】
次の図６は関係強度計算の計算処理のフロー図を示す。
【００３７】
まず、関係強度計算部６にて処理が開始されると、インデクスを外部から指定する（Ｓ１：ステップ１、以下同様に表記する）。このインデクスの指定は入力部１から入力され、インデクスＤＢ２のメモリなどの記憶装置に記憶される。ここで入力されるインデクスの例として、例えば「グエッ」というインデクスについて、初期値として重み付けを「１００」とし、このインデクスに関係するノードは未定なのでノードとの距離は初期値の「０」とされる。
【００３８】
次に、図４に示す関係強度ＤＢ５にあらかじめ記憶された関係強度表を参照し、インデクスに隣接したノードの重みを決定する（Ｓ２）。例えばエントリ「グエッ」にたいしてノードは「苦悶」と「怪我」の２種類が設定される。ノード「苦悶」の重み付けは「５５」に設定され、ノード「怪我」の重み付けは「３０」に設定される。なお、それぞれのノードに設定される距離はそれぞれ「１」である。この距離「１」とは、エントリからノードまでの枝（パス：図６中の矢印線）が１本であることを示す。
【００３９】
次に、重みが与えられたノードに隣接し重みが「０」であるノードに重みを加算する。この加算において、加算原因となるリンクが複数ある時はインデクスに近いリンクを優先して選択する（Ｓ３）。
【００４０】
次に、重み「０」の可到達ノードの有無が判断される（Ｓ４）。この判断で可到達ノードがあると判断されると、再びステップ３を実行する。一方、可到達ノードが無いと判断されると次ステップへ処理が進む。
【００４１】
なお、ステップ４までの処理によって、図６に示すようにエントリ「グエッ」に対する２つのノード「苦悶」と「怪我」に対し、「苦悶」に対するノード「危険」が関連付けされ、「怪我」に対するノード「救援」が関連付けされる。「危険」の重み付けは「１３．７５」と算出され、これは「苦悶」の重み付けが５５であるのに対し、「危険」の重みは２５％であるので、加算されて「１３．７５」が算出されている。
【００４２】
次に、距離の小さいノードから距離の大きいノードへ向かうリンクのうち重み計算未使用のリンクについて、「発側ノードの重み×リンクの重み」を着側ノードの重みに加算する（Ｓ５）。
【００４３】
次に、距離の小さいノードから距離の大きいノードへ向かう未使用のリンクの有無を確認し、リンクが無ければ終了し、リンクが有ればステップ５を再び実行する。
【００４４】
なお、図６に示すようにステップ６まで実行された処理によりノード「苦悶」と「救援」との間のパスが選択され、「苦悶」の重み５５に「救援」との関係の５０％により５５＊５０％＝２７．５が算出され、元の「救援」の重み１５に加算されて重み「４２．５」となる。この例ではエントリ「グエッ」に対する最も重み付け値の大きなノードは「救援」と関係強度計算により算出され、出力部７から外部へ結果として出力する。出力されたこのノードを意味として意味認識に用いる。
【００４５】
なお、極めてノード数が多いときは、有向木の形成において根からの距離が所定値に達したときはさらなる枝の追加を停止し、それまでに到達できなかったノードを除いた部分グラフに対して本計算装置を適用することとすることもできる。
【００４６】
＜第２の実施の形態＞
第２の実施の形態は、第１の実施の形態にて説明した関係強度計算を用いて、互いに異なる項目を有する個別のデータベース同士から、同じ意味を有する部分を用いて比較対象となるデータを抽出している。図７には、例えば履き物のように種目細目毎に仕様項目の組み合わせが異なる物品について、表の同じ意味を有する部分をキーとして比較の対象となる表データを収集する処理の概略を説明するための説明図を示している。
【００４７】
図７に示すように「細分化された変数の形を用いた物品表」（ｆ）と「細分化された変数の型を用いた項目表」（ｈ）を比較するために、「関係強度付きカタログ用語辞典」（ｇ）を用いて「細分化された変数の形を用いた物品表」（ｆ）と「細分化された変数の型を用いた項目表」（ｈ）間で同じ意味を持つ項目同士を抽出している。
【００４８】
「細分化された変数の形を用いた物品表」（ｆ）においてセル型並びをキーとする表付き情報の検索（ａ）が行われる。この検索により「細分化された変数の形を用いた物品表」（ｆ）の中から「自然数型」、「履き物名型」、「ブーツ形式型」、「色型」、「￥型」が表を持つ情報として検索され抽出される。こうして抽出された表付き情報のうち、「細分化された変数の形を用いた物品表」（ｆ）と「細分化された変数の型を用いた項目表」（ｈ）との間で部分共通性をもつ表が抽出される。この抽出は第１の実施の形態で説明した関係強度計算によって意味認識が行われ、その結果を持って抽出が実行され、抽出した表の部分共通性が判断（ｂ）される。
【００４９】
次に、「細分化された変数の形を用いた物品表」（ｆ）と「細分化された変数の型を用いた項目表」（ｈ）にそれぞれ記載されたカタログ用語のそれぞれを網羅し、カタログ用語ごとに関係強度（％表示）を定めた関係強度付きカタログ用語辞典（ｇ）を用意する。この関係強度付きカタログ用語辞典（ｇ）に基づいて、第１の実施の形態の関係強度計算を実行することにより、型の細分化規則が異なる表間の型間関係強度決定（ｃ）がされ、さらに定量的でない仕様項目の値間の距離決定（ｅ）もされる。こうして関係強度の代表値決定（ｄ）がされ、「細分化された変数の形を用いた物品表」（ｆ）と「細分化された変数の型を用いた項目表」（ｈ）とで対応する意味を持つ項目同士の比較が可能になる。
【００５０】
次に、図７に示した処理の概略について具体的な関係強度計算の処理を説明する。
【００５１】
図８は、第２の実施の形態の関係強度計算の処理を説明するためのフロー図を示している。図７の「細分化された変数の形を用いた物品表」（ｆ）と「細分化された変数の型を用いた項目表」（ｈ）を同じ意味を持つ項目同士で比較するために、まずカタログを利用する利用者から細分化された変数の型を用いた要求項目表を取得する（Ｓ１１）。
【００５２】
次に、セル型並びまたはキーワードにより、あらかじめ十分緩く調整された条件にて表付き情報の検索を実行する（Ｓ１２）。
【００５３】
なお、ここでステップ１２において実行される、セル型並びをキーとする表付き情報検索のサブシステムの処理について説明する。
【００５４】
まず、図９にはセル型並びをキーとする表付き情報検索のサブシステムの処理を説明するための説明図を示している。この図９において「表Ａのタイトル行」とは図７に示した「細分化された変数の型を用いた物品表」（ｆ）に示された「セル型並びをキーとする表付き情報の検索」（ａ）により示された破線内の部分に相当する。また「表Ｂのタイトル行」は図７に示した「細分化された変数の型を用いた要求項目表」（ｈ）に相当する。さらに「関係強度付きカタログ用語辞典の一部」とは図７に示した「関係強度付きカタログ用語辞典」（ｇ）の一部である。
【００５５】
図９の説明図において実行される関係強度計算は、表Ａの第ｉ列（ｉは任意の数）のタイトルセル値をエントリＡとする。次に、関係強度計算法［１］（図１０に示す）または関係強度計算法［２］（図１１に示す）を用いて、エントリＡから各ノードへの関係強度を決定する。また表Ｂの第ｊ列（ｊは任意の数）のタイトルセル値の相当ノードの関係強度をタイトルセル間の関係強度とする。なお、相当ノードが無いときは関係強度を「０」とする。
【００５６】
次に、図１０には関係強度計算法［１］を説明するための説明図を示している。
【００５７】
この関係強度計算法［１］においては、まず［ｓｔｅｐ１］においてエントリノードを根とし到達可能な全ノードに向かう有向木を抽出する。木に加える枝の選択は根に近いノードから発するものを優先する。
【００５８】
次に、［ｓｔｅｐ２］において、各ノードへの関係強度を有向木に沿ったパス上の各枝の関係強度の積とする。
【００５９】
この［ｓｔｅｐ２］において、図中の実線は当該エントリからの関係強度計算に寄与する枝を表しており、破線は同じく寄与しない枝を表している。例えば、靴形式型と用途型間の枝は、より根に近いスタイル群型と用途型間の枝が使われるため計算から外されている。
【００６０】
一方で、スタイル群型と筒締め型間の枝は筒形式型と筒締め型間の枝とは同等の優先順位である。同順位の枝について、いずれを寄与させるかは、ランダムに決めるか、枝の数値の大小によるか、結果として得られる関係強度の大小によるか、また、数値によるとき大優先か小優先か中央値優先かという方式選択の余地がある。その決定規則のいずれが適切かはシステムの用途に依存するため、重みデータの設定者によって指定されるものとする。
【００６１】
図１１は関係強度計算法［２］を説明するための説明図を示す。
【００６２】
この関係強度計算法［２］においては、まず［ｓｔｅｐ１］においてエントリノードを根とし到達可能な全ノードに向かう有向木を抽出する。木に加える枝の選択は根に近いノードから発するものを優先する。
【００６３】
次に、［ｓｔｅｐ２］において、各ノードへの関係強度を有向木に沿ったパス上の各枝の関係強度の積とする。
【００６４】
次に、［ｓｔｅｐ３］において、上記有向木に属さない枝のうち、有向閉路を生じない枝を根に近いところから発するものから順に加えた部分グラフを順次生成する。枝を加える毎に枝の行き先のノードの関係強度を「枝の出所のノード関係強度×枝の関係強度」だけ加算し、下流のノードの関係強度も比例して修正する。
【００６５】
次に、図８の処理に戻り、この検索の実行により物品表を発見できない場合は処理が終了し、物品表を１個以上発見した場合は次ステップへ処理が進む（Ｓ１３）。
【００６６】
次に、発見された物品表について関係強度付きカタログ用語辞典を用いて項目タイトル間を関係付けする（Ｓ１４）。そして関係付けした項目タイトル間のうち、関係強度の代表値を決定し、表の共通部分を判定する（Ｓ１５）。
【００６７】
なお、関係強度の代表値を決定する方法としては、図１４に示す４種類の方法がある。
【００６８】
まず、［方法１］は、ベクトルの大きさで定義する方法である。項目名ごとの関係強度を二乗して加算し、その解の平方根を代表値として用いる。
【００６９】
次に［方法２］は、平均値で定義する方法である。項目名と関係強度の関係において、それぞれの関係強度を加算して関係強度数で除算し、その解を代表値とする。
【００７０】
また、［方法３］は、上位Ｋ項目（Ｋは検索条件として指定される任意の数）に関する［方法１］と［方法２］の値を代表値として用いる。
【００７１】
さらに、［方法４］は、関係強度が最も低い項目の値を代表値として用いる。
【００７２】
この判定において、表の共通部分が要求項目表の所定割合をカバーするかしないかの判断がされる（Ｓ１６）。この判断において表の共通部分が要求項目表の所定割合をカバーする場合は、比較対象表リストに表の共通部分を加える（Ｓ１７）。また、要求項目表の所定割合をカバーしない場合は、次に未判定の表がまだ残っているか否かの判断がされる（Ｓ１８）。この判断の結果、全て判定済みの場合は次ステップへ処理が進み、未判定の表がまだ残っている場合はステップ１４へ戻って処理が繰り返される。
【００７３】
次に、比較対象表リストから表を１つ選び表［１］とする。この表選びは比較対象表のうち選択基準などを設けずに片端から行う（Ｓ１９）。選んだ表［１］の物品を１つ選び物品［１］とする。この物品選びも表［１］にあげられた物品のうちから選択基準など設けずに片端から行う（Ｓ２０）。
【００７４】
次に、表［１］の共通部分に属する仕様項目を一つ選び物品［１］の値を値Ｂに代入する。この代入は選択基準など設けずに片端から行う（Ｓ２１）。次に、要求項目表の当該仕様項目を値Ａに代入する（Ｓ２２）。この代入した仕様項目の値について、これが定量的でない仕様項目なのか、あるいは定量的仕様項目であるのかの判断がされる（Ｓ２３）。
【００７５】
この判断で定量的でない仕様項目の場合はＡ、Ｂ間のカタログ用語辞典上の距離を求める（Ｓ２４）。
【００７６】
ステップ２４において実行される処理に係る、定量的でない仕様項目の値間の関係強度／距離決定について、図１２にその説明図を示す。
【００７７】
まず、［ｓｔｅｐ１］において、値Ａからカタログ用語辞典上の各ノードまでの（有向）関係強度を図１０と図１１に示した関係強度計算法［１］、［２］により決定する。
【００７８】
次に［ｓｔｅｐ２］にて、値Ｂに相当するノードの関係強度を仕様項目の値間の関係強度、その逆数を距離とする。相当するノードが無いときは関係強度０、距離は無限大となる。
【００７９】
さらに図１５〜図１８に、カタログ用語辞典における定量的でない仕様項目の値Ａと値Ｂ間の関係強度とその計算処理の例を示す。
【００８０】
図１５には、要求項目において「色」の項が「赤」であるとき、「赤ではないが関連がある色」と他の色との関連度を計算により求めるために、あらかじめ設定された関係強度の設定例を示す。値Ａは「赤」であり、値Ｂは「ピンク」である。「赤」からは「ピンク」に対する関係強度が５０％とされ、「ピンク」から「赤」への関係強度も５０％である。同様に「赤」から「紫」へは５０％、「豹柄」へは１０％、「ゴールド」へは２０％といったように設定される。
【００８１】
次の図１６には、各色同士の間の関係について重み付け値をあらかじめ設定した表を示す。この表には、例えば「赤」について「ピンク」は重み付け値が「５０」とされ、「ゴールド」については「１０」、「豹柄」については「１０」というように設定されている。
【００８２】
次の図１７は、図１５に示した関係強度と図１６に示した重み付け値に基づいて「赤」と「ピンク」から他の色（柄）へ関係を示す枝を追加する順序を示している。「赤」から伸びる枝のうち、＜１＞は、木の根として設定された「赤」から出る枝であり全部が同時に初期値とされている。また、＜２＞が付された枝は未到達のノードに向かう枝を根に近いノード発を優先して木が完成するまで加える。例えば「ゴールド」と「クリア」では、「ゴールド」のほうが根である「赤」に近いので「ゴールド」から「クリア」へ向けて枝が設けられる。同順位の枝はランダムに選択され、例えば「シルバー」から「黒」か、あるいは「白」から「黒」への枝の追加が行われる。そして枝番号の＜３＞以降は有向閉路を生じない枝を根に近いノード発のものを優先で加える。なお、ここで同順位の場合の扱いは＜２＞と同様である。
【００８３】
次の図１８は、エントリ「赤」からの各色に対する関係強度を求める過程について、その段階ごとの数値の推移を示している。
【００８４】
まず（１）では、直接隣接値を決定し、逆行する各枝の使用を禁止する。（２）では、木形成がされ、逆行する各枝の使用を禁止する。（３）では、ピンクから白の枝が追加される。白からピンクへの枝の使用は禁止される。（４）では、紫からピンクへの枝が追加がされる。ピンクからの紫への枝の使用は禁止される。（５）では、豹柄からゴールドへの枝が追加される。ゴールドから豹柄への枝の使用は禁止される。（６）ゴールドからシルバーへの枝が追加される。シルバーからゴールドへの枝の使用は禁止され、黒から豹柄への枝の使用も禁止される。（７）紫からゴールドへの枝が追加される。（８）ゼブラから豹柄への枝が追加される。表柄からゼブラへの枝の使用が禁止され、黒からゼブラへの枝の使用も禁止される。（９）ピンクからシルバーへの枝が追加される。（１０）白からシルバーへの枝が追加される。（１１）シルバーからクリアへの枝が追加される。クリアからシルバーへの枝の使用が禁止され、クリアから白への枝の使用も禁止される。（１２）白から黒への枝が追加される。（１３）黒からクリアへの枝が追加される。
【００８５】
このようにして初期値は「赤（１００）」、「ピンク（５０）」、「紫（５０）」、「ゴールド（２０）」、「シルバー（１０）」、「白（１０）」、「黒（０）」、「クリア（０）」、「豹柄（１０）」、「ゼブラ（１０）」であったものが、関係強度計算の結果「赤（１００）」、「ピンク（７５）」、「紫（５０）」、「ゴールド（２８）」、「シルバー（３６．７５）」、「白（１７．５）」、「黒（８．９２５）」、「クリア（１７．５３５）」、「豹柄（１５）」、「ゼブラ（１０）」となる。
【００８６】
一方、定量仕様項目である場合は（｜Ａ−Ｂ｜／当該項目の標準値）を距離とする（Ｓ２５）。図１３に定量的仕様項目間の関係強度／距離決定の方法を説明するための説明図を示す。
【００８７】
まず［ｓｔｅｐ１］にて、項目型Ａからカタログ用語辞典上の各ノードまでの（有向）関係強度を図１０と図１１に示した関係強度計算法［１］、［２］により決定する。
【００８８】
次に、［ｓｔｅｐ２］にて、項目型Ｂに相当するノードの関係強度を仕様項目の値間の関係強度、その逆数を距離とする。相当するノードがないときは関係強度０、距離は無限大となる。
【００８９】
次に、距離未決定の仕様項目があるか否かの判断がされる（Ｓ２６）。この判断で距離未決定の仕様項目が無い場合は次のステップへ処理が進み、表の共通部分に属し距離未決定の仕様項目がある場合はステップ２１へ処理が戻り繰り返される。
【００９０】
次に、要求項目表の共通部分に属さない仕様項目を一つ選び値を値Ａに代入する（Ｓ２７）。次に、当該仕様項目の標準値を値Ｂに代入する（Ｓ２８）。なお、標準値とは仕様項目にあらかじめ与えられた規定値である。そして、定量的でない仕様項目か、あるいは定量的仕様項目であるかが判断され、定量的でない仕様項目の場合は、Ａ、Ｂ間のカタログ用語辞典上の距離を求める（Ｓ３０）。一方、定量的仕様項目の場合は、（｜Ａ−Ｂ｜／当該項目の標準値）を距離とする（Ｓ３１）。
【００９１】
次に、表の共通部分に属し距離未決定の仕様項目の有無を判定する（Ｓ３２）。この判定で表の共通部分に属し距離未決定の仕様項目がある場合はステップ２７へ処理が戻り繰り返される。一方、距離未決定の仕様項目が無い場合はあらかじめ設定されている［方法１］〜［方法３］のうちのいずれかを実行する（Ｓ３３）。
【００９２】
ここで、［方法１］とは、要求項目表の各仕様項目について求めた距離を要素とするベクトルの長さを求め物品［１］と要求項目表の距離とする方法である。［方法２］とは、要求項目表の各仕様項目について求めた距離の平均を物品［１］と要求項目表の距離とする方法である。［方法３］とは、要求項目表の各仕様項目について求めた距離の最大値を物品［１］と要求項目表の距離とする方法である。
【００９３】
次に、表［１］の物品で要求項目表との距離が決定していないものがあるか否かが判断され、決定していないものがある場合はステップ２０へ処理が戻り繰り返される（Ｓ３４）。一方、距離が決定していないものが無い場合は、次に比較対照リストに所属物品と要求項目表の距離が決定していないものがあるか無いかの判断がされ、決定していないものがある場合はステップ１９へ処理が戻り繰り返される（Ｓ３５）。一方、距離が決定していないものが無い場合は、要求項目表との距離を求めたすべての物品について距離の近い順に並べ、要求項目表の仕様項目を示した表を作成し（Ｓ３６）、一連の処理は終了する。
【００９４】
＜第３の実施の形態＞
図１９には、第３の実施の形態の関係強度計算方法を説明するための説明図を示す。この図１９に示した説明図は、関係強度計算（全パスもしくは主要パス探索）が必要な場合であって、随時にノードの追加や削除あるいは関係強度の増減が行われる場合の計算例であって、関係強度計算を事業者間における相互の信用調査に適用して信用情報システムを構築する場合を計算例として示している。
【００９５】
まず、図１９において、各ノードＡ〜Ｇは各事業者を表し、それぞれの事業者間は一方の信用状態が他方の信用状態に与える度合いとして％表示で関係強度が定義されている。これらの％表示による個別の信用状態の度合いを示す数値を与える式は、信用情報調査機関の企業秘密であり、所属アナリストの見解として結果のみが随時公表される（実在するＳ＆Ｐ（Standard & Poor's, a division of The McGraw-Hill Companies, Inc. の登録商標）等では数値化はしていないが、たとえば信用状態に影響する何等かの事件に際して”影響に注視””影響は軽微”等独特の言い回しで５段階評価的情報を出している）。
【００９６】
本実施の形態における関係強度計算では、複数の信用情報調査機関が発表する信用状態の度合いの数値を随時収集して合成した結果を主に使用し、さらに信用情報システムの運営者独自調査による補足も行う。
【００９７】
この図１９に示す例では、ＢはＡが全額出資する子会社で、借入金と債務保証を全部Ａに依存し、全取引がＡ向けであり、全要員がＡからの出向であると仮定すると、Ａ→Ｂの関係強度は自明に１００％となる。また、Ｃの信用状態変化の９０％がＡの信用状態に反映されるといずれかの信用情報機関が評価したときＣ→Ａの関係強度が９０％となる。他の区間も同様に何者かの評価によって関係強度が与えられ、また随時修正や削除が行われる。
【００９８】
このようにして「ある事業者が破綻したとき影響を受ける主な事業者のリスト」を作ることができる。こうして作成したリストを用いれば、事業者の倒産や経営危機のニュースに際して、当該企業と直接の取引や資本関係がない影響先を察知することができる。
【００９９】
たとえば図１９においては、事業者Ｇの経営破綻に際して大きな影響を受ける事業者のリストとして、事業者Ｃが４６％、事業者Ａが４１．５％、事業者Ｂが４１．５％として算出される。
【０１００】
＜第４の実施の形態＞
図２０は、関係強度計算を用いた比較装置の実施の形態の全体構成図を示している。この図２０には、比較装置５０と、比較装置５０に接続されるインターネット５１と、インターネット５１および比較装置５０を利用するエンドユーザー５２と、が示されている。
【０１０１】
比較装置５０には、インターネット５１と通信するための通信手段５３と、エンドユーザー５２と接続して情報の入出力を行う入出力手段５５と、要求判別手段５４と、関係強度計算部６２と、関係強度ＤＢ（データベース）６４と、ノードＤＢ（データベース）６３と、比較対象提示手段５７と、代替品提示手段５６と、が示されている。なお、比較対象提示手段５７は、比較対象検索手段６０と、比較対象判定手段６１と、を備えている。一方、代替品提示手段５６は、代替品検索手段５８と、代替品順位づけ手段５９と、を備えている。
【０１０２】
エンドユーザー５２が検索要求した情報は入出力手段５５を介して比較装置５０に入力される。入力された検索要求は、要求判別手段５４においてエンドユーザー５２からの通信またはコマンド入力の内容に基づいて、これを比較対象検索と代替品検索とに振り分ける。
【０１０３】
通信またはコマンド入力が比較対象検索である場合は、比較対象提示手段５７に入力される。比較対象提示手段５７には比較対象検索手段６０と比較対象判定手段６１が備わり、比較対象の検索と判定を実行処理する。比較対象提示手段５７が比較対象を提示するための演算は、関係強度計算部６２において実行され、の計算結果に基づいて比較対象提示手段５７が比較対象の提示処理を実行する。関係強度計算部６２にはノードＤＢ６３と関係強度ＤＢ６４とが接続されている。
【０１０４】
一方、通信またはコマンド入力が代替品検索である場合は、代替品提示手段５６に入力される。代替品提示手段５６には代替品検索手段５８と、代替品順位づけ手段５９と、が備わり代替品の検索と提示を実行処理する。代替品提示手段５６が代替品を提示するための演算も関係強度計算部６２において処理される。
【０１０５】
比較対象提示手段５７や代替品提示手段５６からの結果情報（比較対象情報、代替品情報）の出力は入出力手段５５を介してエンドユーザー５２へ返信される。あるいは通信手段５３を介してインターネット５１を経由してエンドユーザー５２へ返信される。インターネット５１を介してエンドユーザー５２と入出力手段５５が接続するには、たとえばインターネット５１上に配置された商品比較サイトやショッピングサイトを介してもよい。この場合は、これらのＷｅｂサイトにおいてエンドユーザー５２がＷｅｂブラウザを操作することにより、その操作を解釈して比較装置５０への指示に当てはめてもよい。
【０１０６】
図２１には、図２０に示した比較装置５０を用いた比較対象提示を説明するための説明図を示す。
【０１０７】
まず、エンドユーザー５２が「赤のピンヒール」を欲して安い店を検索している。この検索にて自分で見つけたカタログに不満が生じている。インターネット５１を介して見つけた店は、たとえばネットショップＡ７２であり、そこのカタログ７３について不満が生じている。
【０１０８】
次に、エンドユーザー５２は満足の行くカタログを探すために比較装置５０に対して似たカタログを探す指示を出す。比較装置５０ではインターネット５１を介して似たカタログの検索代行を実行する。
【０１０９】
この検索代行の結果、たとえば図２１においてはサイズ項目、価格項目が関係強度１００％で、型項目と色項目がデザイン項目に対し各４０％の関係強度であり、ベクトル強度２．３２は十分であると判断する。この判断に基づいてネットショップＢ７０のカタログ７１をエンドユーザー５２へ比較対象となるカタログとして提示する。
【０１１０】
図２２には、図２０に示した比較装置５０を用いた代替品提示を説明するための説明図を示す。
【０１１１】
まず、エンドユーザー５２が比較対象提示により提示されたネットショップＢ７０のカタログ７１について、その中から希望する商品が在庫切れとなっている場合を想定している。
【０１１２】
次に、比較装置５０はこの状態を検出して、カタログの行間を比較し、仕様項目値間の関係強度を計算する。関係強度を計算により求めて、関係強度が強い順に代案を仕様項目表７５にしてエンドユーザー５２へ提示し、ネットショップＢ７０のサイトから立ち去りそうな顧客（エンドユーザー５２）を引き留める。
【０１１３】
このように、以上説明した実施の形態によれば、意味認識におけるエントリとノードの関係強度に要する計算負荷を軽減することができる。
【図面の簡単な説明】
【０１１４】
【図１】関係強度計算装置の第１の実施の形態の構成図を示す。
【図２】関係強度計算装置による関係強度計算方法の概略を説明するための説明図を示す。
【図３】実施の形態の関係強度計算の計算例を説明するための説明図を示す。
【図４】関係強度計算に用いられる関係強度表の例を示す。
【図５】関係強度計算に用いられるインデクスの例を示す。
【図６−１】関係強度計算の第１の実施の形態の計算処理を説明するためのフロー図を示す。
【図６−２】関係強度計算の第１の実施の形態の計算処理を説明するためのフロー図を示す。
【図７】関係強度計算装置の第２の実施の形態の概略を説明するための説明図を示す。
【図８−１】関係強度計算の第２の実施の形態の計算処理を説明するためのフロー図を示す。
【図８−２】関係強度計算の第２の実施の形態の計算処理を説明するためのフロー図を示す。
【図８−３】関係強度計算の第２の実施の形態の計算処理を説明するためのフロー図を示す。
【図８−４】関係強度計算の第２の実施の形態の計算処理を説明するためのフロー図を示す。
【図９】第２の実施の形態の、セル型並びをキーとする表付き情報検索のサブシステムの処理を説明するための説明図を示す。
【図１０】第２の実施の形態の、関係強度計算法［１］を説明するための説明図を示す。
【図１１】第２の実施の形態の、関係強度計算法［２］を説明するための説明図を示す。
【図１２】第２の実施の形態の、定量的でない仕様項目の値間の関係強度／距離決定の説明図を示す。
【図１３】第２の実施の形態の、定量的仕様項目間の関係強度／距離決定の方法を説明するための説明図を示す。
【図１４】第２の実施の形態の、関係強度の代表値を決定する方法として［方法１］〜［方法４］を示す。
【図１５】第２の実施の形態の、定量的でない仕様項目の値の関係強度とその計算処理の例を示す。
【図１６】第２の実施の形態の、定量的でない仕様項目の値の関係強度とその計算処理の例を示す。
【図１７】第２の実施の形態の、定量的でない仕様項目の値の関係強度とその計算処理の例を示す。
【図１８】第２の実施の形態の、定量的でない仕様項目の値の関係強度とその計算処理の例を示す。
【図１９】第３の実施の形態の関係強度計算方法を説明するための説明図を示す。
【図２０】関係強度計算を用いた比較装置の実施の形態の全体構成図を示す。
【図２１】比較装置を用いた比較対象提示を説明するための説明図を示す。
【図２２】比較装置を用いた代替品提示を説明するための説明図を示す。
【符号の説明】
【０１１５】
１  入力部
２  インデクスＤＢ
３  エントリＤＢ
４  ノードＤＢ
５  関係強度ＤＢ
６  関係強度計算部
７  出力部
【図１】
2007072904.tif 000003
【図２】
2007072904.tif 000004
【図３】
2007072904.tif 000005
【図４】
2007072904.tif 000006
【図５】
2007072904.tif 000007
【図６−１】
2007072904.tif 000008
【図６−２】
2007072904.tif 000009
【図７】
2007072904.tif 000010
【図８−１】
2007072904.tif 000011
【図８−２】
2007072904.tif 000012
【図８−３】
2007072904.tif 000013
【図８−４】
2007072904.tif 000014
【図９】
2007072904.tif 000015
【図１０】
2007072904.tif 000016
【図１１】
2007072904.tif 000017
【図１２】
2007072904.tif 000018
【図１３】
2007072904.tif 000019
【図１４】
2007072904.tif 000020
【図１５】
2007072904.tif 000021
【図１６】
2007072904.tif 000022
【図１７】
2007072904.tif 000023
【図１８】
2007072904.tif 000024
【図１９】
2007072904.tif 000025
【図２０】
2007072904.tif 000026
【図２１】
2007072904.tif 000027
【図２２】
2007072904.tif 000028