(57)【要約】【課題】ユーザが指定した特徴に注目して類似度の高い過去のレイアウトパターンを検索できる類似度検索装置、類似度検索方法および類似度検索プログラムを提供する。【解決手段】類似度検索装置１０は、生成部４１と、算出部４２とを有する。生成部４１は、レイアウトパターンに含まれるノード毎に、ノードラベルを生成する。ノードラベルは、当該ノードの各特徴が表現された所定長のビット列を重なりなく結合した属性情報と、当該ノードに隣接するノードの前記属性情報の各特徴に基づいて生成されたビット列を重なりなく結合した隣接情報とを、重なりなく結合して生成される。算出部４２は、指定された特徴に関する複数のレイアウトパターンの間の類似度を、ノードラベルを用いて算出する。【選択図】図１
2017191556.tif 000002
【特許請求の範囲】
【請求項１】
レイアウトパターンに含まれるノード毎に、当該ノードの各特徴が表現された所定長のビット列を重なりなく結合した属性情報と、当該ノードに隣接するノードの前記属性情報の各特徴に基づいて生成されたビット列を重なりなく結合した隣接情報とを、重なりなく結合したラベルを生成する生成部と、
指定された特徴に関する複数のレイアウトパターンの間の類似度を、前記ラベルを用いて算出する算出部と
を有することを特徴とする類似度検索装置。
【請求項２】
前記算出部は、指定された特徴が所定の値をもつノードを対象として類似度を算出することを特徴とする請求項１に記載の類似度検索装置。
【請求項３】
前記算出部は、指定された特徴を除外して類似度を算出することを特徴とする請求項１または２に記載の類似度検索装置。
【請求項４】
コンピュータが、
レイアウトパターンに含まれるノード毎に、当該ノードの各特徴が表現された所定長のビット列を重なりなく結合した属性情報と、当該ノードに隣接するノードの前記属性情報の各特徴に基づいて生成されたビット列を重なりなく結合した隣接情報とを、重なりなく結合したラベルを生成し、
指定された特徴に関する複数のレイアウトパターンの間の類似度を、前記ラベルを用いて算出する
処理を実行することを特徴とする類似度検索方法。
【請求項５】
コンピュータに、
レイアウトパターンに含まれるノード毎に、当該ノードの各特徴が表現された所定長のビット列を重なりなく結合した属性情報と、当該ノードに隣接するノードの前記属性情報の各特徴に基づいて生成されたビット列を重なりなく結合した隣接情報とを、重なりなく結合したラベルを生成し、
指定された特徴に関する複数のレイアウトパターンの間の類似度を、前記ラベルを用いて算出する
処理を実行させることを特徴とする類似度検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、類似度検索装置、類似度検索方法および類似度検索プログラムに関する。
【背景技術】
【０００２】
近年ＬＳＩ（Large  Scale  Integration）等の集積回路は、微細化技術の発展により、トランジスタや配線の寸法が光の波長よりも小さくなっている。この影響により、リソグラフィ工程において、設計されたレイアウトパターンどおりに形成されたマスクにより露光を行っても、光近接効果（Optical  Proximity  Effect）により、レイアウトパターンどおりに露光できない箇所が集積回路に生じる場合がある。例えば、レイアウトパターンどおりに形成されたマスクによりウエハ上に配線パターンを露光しても、ウエハ上に形成される配線パターンが細かくなって断線したり、逆に配線パターンが太くなってショートしたり、といった欠陥が発生する場合がある。
【０００３】
また、レイアウトパターンを事前に検証し、リソグラフィ欠陥の有無を判定することにより、ＬＳＩ製造段階から設計段階への手戻りを防止する技術が知られている。このようなレイアウトパターンの設計検証は、リソグラフィシミュレーションを用いることで厳密な検証が可能であるが、これには多大な計算リソースを必要とする。一方、高速に検証を行うにはパターンマッチングと呼ばれる手法が用いられる。パターンマッチングとして、探索対象画像（テンプレート画像）を撮影画像等の非検証画像の全体内で網羅的に探すといった手法を用いることが一般的であるが、テンプレート画像との微小な差異がある場合に欠陥パターンと認識するかどうかの判断が難しい。欠陥の見逃しをゼロにするために、パターン間の微少な差異を許容すると、多数の欠陥ではない箇所が欠陥箇所として識別されることになり、検証工数の増大につながる。
【０００４】
このため、例えば、リソグラフィ工程において欠陥が発生する配線層および配線層に隣接する隣接配線層の欠陥箇所の周辺のレイアウトパターンの特徴を示す特徴情報を抽出し、抽出した特徴情報をもつ過去のレイアウトパターンに基づいて欠陥箇所を識別する技術が提案されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１１−２３３０６９号公報
【特許文献２】特開２０１３−１７５０１６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記の従来技術では、レイアウトパターン間の類似度は、レイアウトパターンに基づくグラフにおいて、予め、例えば、ノード数やエッジ数等の特徴をそれぞれ抽出して定義された特徴ベクトルに基づいて算出される。したがって、類似度を定義付ける特徴項目を変更するためには、特徴ベクトルを定義し直す必要があり、場合に応じて類似度を定義付ける特徴の一部を変更することは困難な場合があった。
【０００７】
一側面では、ユーザが指定した特徴に注目して類似度の高い過去のレイアウトパターンを検索できる類似度検索装置、類似度検索方法および類似度検索プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一側面によれば、類似度検索装置は、生成部と、算出部とを有する。生成部は、レイアウトパターンに含まれるノード毎に、ラベルを生成する。ラベルは、当該ノードの各特徴が表現された所定長のビット列を重なりなく結合した属性情報と、当該ノードに隣接するノードの前記属性情報の各特徴に基づいて生成されたビット列を重なりなく結合した隣接情報とを、重なりなく結合して生成される。算出部は、指定された特徴に関する複数のレイアウトパターンの間の類似度を、ラベルを用いて算出する。
【発明の効果】
【０００９】
ユーザが指定した特徴に注目して類似度の高い過去のレイアウトパターンを検索できる。
【図面の簡単な説明】
【００１０】
【図１】図１は、類似度検索装置の全体構成を示す図である。
【図２】図２は、既知パターンデータに含まれる既知パターンの一例を示す図である。
【図３】図３は、ノードラベルの一例を示す図である。
【図４】図４は、ドロネー三角分割の流れを説明する図である。
【図５】図５は、レイアウトパターンから生成されるグラフの一例を示す図である。
【図６】図６は、自ノードと隣接ノードとの関係を説明する図である。
【図７】図７は、レイアウトパターンの中心からの距離を説明する図である。
【図８】図８は、レイアウトパターンの中心からの方向を説明する図である。
【図９】図９は、レイアウトパターンの正規化を説明する図である。
【図１０】図１０は、類似度算出処理の概要を説明する図である。
【図１１】図１１は、対象ノード抽出処理を説明する図である。
【図１２】図１２は、対象ノード抽出処理を説明する図である。
【図１３】図１３は、指定特徴マスク処理を説明する図である。
【図１４】図１４は、指定特徴マスク処理を説明する図である。
【図１５】図１５は、類似度算出アルゴリズムの一例を示す図である。
【図１６】図１６は、レイアウトパターンの領域の指定を説明する図である。
【図１７】図１７は、レイアウトパターンの領域の指定を説明する図である。
【図１８】図１８は、レイアウトパターンの領域の指定を説明する図である。
【図１９】図１９は、レイアウトパターンの回転・反転を説明する図である。
【図２０】図２０は、レイアウトパターンの回転・反転の指定を説明する図である。
【図２１】図２１は、類似度検索結果の一例を示す図である。
【図２２】図２２は、類似度検索処理手順を示すフローチャートである。
【図２３】図２３は、類似度検索プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１１】
以下に、本発明にかかる類似度検索装置、類似度検索方法および類似度検索プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。そして、各実施例は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【実施例１】
【００１２】
実施例１に係る類似度検索装置１０について説明する。図１は、類似度検索装置１０の全体構成を示す図である。類似度検索装置１０は、欠陥の有無が未知のレイアウトパターンとの類似度が高いレイアウトパターンを、欠陥の有無が既知のレイアウトパターンの中から検索する類似度検索処理を行う装置である。なお、以下の実施例では、欠陥の有無が未知のレイアウトパターンを「未知パターン」、欠陥に係る情報が付与されている、すなわち、欠陥の有無が既知のレイアウトパターンを「既知パターン」と表記する場合がある。
【００１３】
類似度検索装置１０は、例えば、パーソナルコンピュータやサーバコンピュータ等のコンピュータなどである。類似度検索装置１０は、１台のコンピュータとして実装してもよく、また、複数台のコンピュータによるクラウドとして実装することもできる。なお、本実施例１では、類似度検索装置１０を１台のコンピュータとした場合を例として説明する。類似度検索装置１０は、ＣＡＤ（Computer  Aided  Design）装置などの設計者による集積回路の設計を支援する回路設計ソフトウェアが動作する設計装置であってもよい。図１に示すように、類似度検索装置１０は、入力部２０と、表示部２１と、通信Ｉ／Ｆ（インタフェース）部２２と、記憶部２３と、制御部２４とを有する。
【００１４】
入力部２０は、各種の情報を入力する入力デバイスである。入力部２０としては、マウスやキーボードなどの操作の入力を受け付ける入力デバイスが挙げられる。入力部２０は、各種の情報の入力を受付ける。例えば、入力部２０は、類似度検索に関する各種の操作の入力を受け付ける。入力部２０は、ユーザからの操作入力を受け付け、受け付けた操作内容を示す操作情報を制御部２４に入力する。
【００１５】
表示部２１は、各種情報を表示する表示デバイスである。表示部２１としては、ＬＣＤ（Liquid  Crystal  Display）やＣＲＴ（Cathode  Ray  Tube）などの表示デバイスが挙げられる。表示部２１は、各種情報を表示する。例えば、表示部２１は、登録画面や、操作画面、検索結果画面など各種の画面を表示する。
【００１６】
通信Ｉ／Ｆ部２２は、他の装置との間で通信制御を行うインタフェースである。通信Ｉ／Ｆ部２２は、不図示のネットワークを介して他の装置と各種情報を送受信する。例えば、通信Ｉ／Ｆ部２２は、他の装置から後述する既知パターンデータ３０や検索対象の未知パターンデータ３１を受信する。通信Ｉ／Ｆ部２２としては、ＬＡＮカードなどのネットワークインタフェースカードを採用できる。なお、類似度検索装置１０は、メモリカードなどの記憶媒体を介して既知パターンデータ３０や検索対象の未知パターンデータ３１などの情報を取得してもよい。また、既知パターンデータ３０や検索対象の未知パターンデータ３１は、入力部２０から入力されてもよい。
【００１７】
記憶部２３は、ハードディスク、ＳＳＤ（Solid  State  Drive）、光ディスクなどの記憶装置である。なお、記憶部２３は、ＲＡＭ（Random  Access  Memory）、フラッシュメモリ、ＮＶＳＲＡＭ（Non  Volatile  Static  Random  Access  Memory）等のデータを書き換え可能な半導体メモリであってもよい。
【００１８】
記憶部２３は、制御部２４で実行されるＯＳ（Operating  System）や各種プログラムを記憶する。例えば、記憶部２３は、類似度検索に用いる各種のプログラムを記憶する。さらに、記憶部２３は、制御部２４で実行されるプログラムで用いられる各種データを記憶する。例えば、記憶部２３は、既知パターンデータ３０と、未知パターンデータ３１とを記憶する。
【００１９】
既知パターンデータ３０は、既知パターン集合に関する一連の情報を記憶したデータである。そして、以下の実施例では、類似度検索装置１０は、既知パターン集合として既知パターン集合Ｐ１，・・・，Ｐｎの入力を受け付けたものとして説明する。
【００２０】
既知パターンデータ３０は、既知パターン集合Ｐ１，・・・，Ｐｎにおいて、各既知パターンを構成する矩形や多角形の頂点座標リストを含む。例えば、各既知パターンＰｉ（ｉ＝１，・・・，ｎ）を構成する矩形や多角形の集合を、Ｐｉ：｛Ｐ１，Ｐ２，・・・，Ｐｋ，ＰＮ｝と表すことができる。また、多角形Ｐｋの頂点座標を、Ｐｋ=｛（ｘｋ１，ｙｋ１），・・・，（ｘｋｎ，ｙｋｎ），Ｌｋ｝と表すことができる。Ｌｋは、多角形Ｐｋが存在する配線層を識別するための記号である。
【００２１】
図２は、既知パターンデータ３０に含まれる既知パターンの一例を示す図である。図２の例では、既知パターン毎に、既知パターンを構成する各構成部品の頂点座標リストが記録されている。この頂点座標リストには、構成部品を示す図形のそれぞれの頂点座標が１行毎に記録されている。例えば、図２の例では、既知パターンPATTERN1の頂点座標リストとして、矩形RECT1の４つの頂点座標や、多角形POLY2の７つの頂点座標が示されている。頂点座標リストとしては、ＧＤＳ（Graphic  Data  System）、ＯＡＳＩＳ（Open  Artwork  System  Interchange  Standard）等の既存の図形データフォーマットを利用してもよい。
【００２２】
また、既知パターンデータ３０には、各既知パターンにおける欠陥の有無に関する情報（以下の実施例において、「欠陥有無情報」と表記する場合がある）も含まれる。例えば、既知パターンデータ３０には、既知パターン集合Ｐ１，・・・，Ｐｎに対応付けて、欠陥有無情報ｅ１，・・・，ｅｎも含まれる。なお、ここでは、欠陥有無情報として概念的な記号を用いているが、実際には、例えば、欠陥を有するレイアウトパターンには「ＹＥＳ」、欠陥なしのレイアウトパターンには「ＮＯ」が対応付けられることが考えられる。また、欠陥有無情報は、上記の座標等とともに入力されるものである。
【００２３】
また、既知パターンデータ３０には、後述する生成部４１により各既知パターンから生成される配線層毎のドロネー三角形の重心からなるグラフの情報も含まれる。さらに、既知パターンデータ３０には、かかるグラフの各ノードを識別するためのラベルであって、各ノードの属性情報と各ノードに隣接するノード（隣接ノード）の属性情報に基づいた隣接情報とが結合されたラベルも含まれる。ここで、グラフの頂点はノードと呼ばれる。なお、以下の実施例では、ノードのラベルを「ノードラベル」と表記する場合がある。ノードラベルは、後述する生成部４１により生成される。
【００２４】
例えば、既知パターン集合Ｐ１，・・・，Ｐｎから生成されたグラフＧは、Ｇ（Ｖ，Ｅ）（ｉ＝１，・・・，ｎ）のように形式的に定義することができる。Ｖは、ノード集合であり、Ｖ：｛ｖ１，ｖ２，・・・，ｖｎ，ｖｉ＝（ｘｉ，ｙｉ）｝と表すことができる。例えば、ノードｖｉは、座標（ｘｉ，ｙｉ）に位置することを示す。Ｅは、枝集合であり、Ｅ＝｛ｅ１，ｅ２，・・・，ｅｍ，ｅｊ＝（ｖｊ１，ｖｊ２）｝と表すことができる。つまり、各枝ｅｊは、２つのノードｖｊ１とｖｊ２の間の無向枝であることを示す。
【００２５】
なお、上述のドロネー三角形の頂点をノードとするグラフに対しても、以下に説明する処理を同様に適用できる。
【００２６】
また、各ノードに対して、当該ノードの属性情報および隣接ノードの属性情報に基づいてラベルが生成されたグラフＧは、Ｇ＝（Ｖ，Ｅ，ｌ）（ｉ＝１，・・・，ｎ）のように形式的に定義することができる。ＶおよびＥは、上記の通りである。ｌは、各ノードラベルを示し、ｌ：｛ｌ１，ｌ２，・・・，ｌｎ，ｌｉ∈Σ，Σ＝｛０，１｝ｐ｝と表すことができる。つまり、ノードラベルｌは、ｌ１〜ｌｎ要素を含み、長さｐのビット列で表現されることを示す。
【００２７】
図３は、ノードラベルの一例を示す図である。図３に示すように、本実施例におけるノードラベルは、自ノード情報と隣接情報とを含む。ここで、自ノード情報とは、各ノードの属性情報を意味し、当該ノードの各特徴が表現された所定長のビット列が重なりなく結合されている。図３に示す例では、２ビットの特徴１と２ビットの特徴２と３ビットの特徴３とが重なりなく結合され、７ビットの属性情報とされている。特徴については後述する。
【００２８】
また、隣接情報とは、各ノードに隣接するノードの属性情報の各特徴に基づいて生成されたビット列が重なりなく結合されたものである。図３の例では、当該ノードに隣接する各隣接ノードの属性情報の特徴１に基づいて生成された２ビットの特徴１と、同様に各隣接ノードの特徴２から生成された２ビットの特徴２と各隣接ノードの特徴３から生成された３ビットの特徴３とが重なりなく結合される。その結果、隣接情報は７ビットであり、属性情報のビット長に等しい。
【００２９】
なお、後述する算出部４２が、かかる既知パターンデータ３０から、例えば、既知パターン毎にノードラベルの情報を取得し、既知パターンと未知パターンとの類似度を算出する。
【００３０】
未知パターンデータ３１は、例えば、一つの未知パターンＰ０に関する情報を記憶したデータである。未知パターンＰ０は、既知レイアウトパターンとの類似度検索の対象として入力部２０を介して入力される。未知パターンデータ３１は、未知パターンＰ0を構成する矩形や多角形の頂点座標リストを含む。例えば、未知パターンＰ０を構成する矩形や多角形の集合を、Ｐ０：｛Ｐ１，Ｐ２，・・・，Ｐｋ，ＰＮ｝と表すことができる。また、多角形Ｐｋの頂点座標を、Ｐｋ=｛（ｘｋ１，ｙｋ１），・・・，（ｘｋｎ，ｙｋｎ），Ｌｋ｝と表すことができる。Ｌｋは、多角形Ｐｋが存在する配線層を識別するための記号である。ここで、図２は、既知パターンデータ３０に含まれる既知パターンの一例を示す図であるが、未知パターンにも対応するものである。
【００３１】
また、未知パターンデータ３１には、後述する生成部４１により未知パターンＰ０から生成される配線層毎のドロネー三角形の重心をノードとするグラフの情報も含まれる。さらに、未知パターンデータ２４には、かかるグラフのノード毎に、後述する生成部４１により生成される、属性情報および隣接情報が結合されたノードラベルも含まれる（図３参照）。
【００３２】
制御部２４は、類似度検索装置１０を制御するデバイスである。制御部２４としては、ＣＰＵ（Central  Processing  Unit）、ＭＰＵ（Micro  Processing  Unit）等の電子回路や、ＡＳＩＣ（Application  Specific  Integrated  Circuit）、ＦＰＧＡ（Field  Programmable  Gate  Array）等の集積回路を採用できる。制御部２４は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。制御部３１は、各種のプログラムが動作することにより各種の処理部として機能する。例えば、制御部２４は、受付部４０と、生成部４１と、算出部４２と、出力部４３とを有する。
【００３３】
受付部４０は、各種の受付を行う。例えば、受付部４０は、入力部２０を介して入力された既知パターン集合や、各既知パターンにおける欠陥有無情報を受け付ける。そして、受付部４０は、受け付けた既知パターンを既知パターンデータ３０として格納する。また、受付部４０は、類似度検索処理の対象である未知パターンを受け付けて、未知パターンデータ３１として格納する。また、受付部４０は、後述する類似度検索処理において、特徴を指定する情報を受け付ける。なお、受付部４０は、通信Ｉ／Ｆ部２２を介して各種の受付を行うように構成されてもよい。
【００３４】
生成部４１は、レイアウトパターンに含まれるノード毎に、属性情報と隣接情報とを重なりなく結合したラベルを生成する。上述したように、属性情報とは、当該ノードの各特徴が表現された所定長のビット列を重なりなく結合したものである。また、隣接情報とは、当該ノードに隣接するノードの属性情報の各特徴に基づいて生成されたビット列を重なりなく結合したものである。
【００３５】
具体的に、生成部４１は、まず、レイアウトパターンを構成する図形の頂点を結んでドロネー三角分割（Delaunay  triangulation）を配線層毎に行って、図形の頂点を結んで得られる複数の三角形を求める。このような三角形は、ドロネー三角形と呼ばれる。生成部４１は、例えば、既知パターン集合Ｐ１，・・・，Ｐｎそれぞれから生成したドロネー三角形の重心に関する情報（座標等）を既知パターンデータ３０として、既知パターン集合Ｐ１，・・・，Ｐｎのそれぞれに対応付けて格納する。同様に、生成部４１は、未知パターンＰ０から生成したドロネー三角形の重心に関する情報を未知パターンデータ３１として、未知パターンＰ０に対応付けて格納する。
【００３６】
図４は、ドロネー三角分割の流れを説明する図である。図４（Ａ）は、配線パターンの一例を示している。図４（Ｂ）は、図４（Ａ）に示す配線パターンに対し生成されるボロノイ図（Voronoi  diagram）を示している。図４（Ｃ）は、図４（Ａ）に示す配線パターンもしくは図４（Ｂ）に示すボロノイ図に対し生成されるドロネー図（Delaunay  diagram）である。なお、図４において、ドットのパターン部分は、配線部分を示している。
【００３７】
生成部４１は、図４（Ａ）に示すレイアウトパターンの配線部分の頂点座標を求め、求められた頂点座標から図４（Ｂ）に示すボロノイ図を生成する。ボロノイ図は、平面または空間上の点集合の各点について、どの点に最も近いかによって分割して生成される図である。そして、生成部４１は、図４（Ｂ）に示すボロノイ図から、隣接する領域の母点（generatrix）同士を結ぶことにより、図４（Ｃ）に示すドロネー図を生成する。このドロネー図は、各図形間の相対位置関係を表現する。
【００３８】
図５は、レイアウトパターンから生成されるグラフの一例を示す図である。生成部４１は、図５に黒丸で示す各ドロネー三角形の重心をノードとし、ノードとノード間をつなぐエッジにより構成されるグラフを生成する。以下、図にｘで示すノードｖ０を自ノードとして説明する。
【００３９】
また、生成部４１は、既知パターンまたは未知パターンに含まれるノード毎に、自ノードの属性情報および自ノードに隣接する隣接ノードの属性情報に基づいた隣接情報を結合したラベルを生成する。そして、生成部４１は、生成したノードラベルの情報（ビット列）を既知パターンデータ３０あるいは未知パターンデータ３１として、既知パターン集合Ｐ１，・・・，Ｐｎあるいは未知パターンＰ０に対応付けて格納する。
【００４０】
ここで、自ノードに隣接する隣接ノードとは、自ノードとエッジでつながれているノードを意味する。図６は、自ノードと隣接ノードとの関係を説明する図である。図６に示す例において、自ノードｖ０の隣接ノードは、ノードｖ１、ノードｖ２、およびノードｖ３である。
【００４１】
また、上述したように、属性情報は、当該ノードの各特徴が表現された所定長のビット列が重なりなく結合されたものである。属性情報を構成する特徴には、例えば、レイアウトパターンの中心からの距離や方向が例示される。
【００４２】
図７は、レイアウトパターンの中心からの距離を説明する図である。本実施例における特徴の１つに、例えば、図５にｘで示したノードｖ０について、ｏで示したレイアウトパターンの中心からの距離が特徴１として表現される。図７に示す例では、レイアウトパターンの中心ｏからの距離が０〜３の４段階すなわち２ビットのビット列で表現され、例えば、図３に示した特徴１とされる。
【００４３】
また、図８は、レイアウトパターンの中心からの方向を説明する図である。本実施例における他の特徴に、レイアウトパターンの中心ｏからの方向が、特徴２として表現される。図８に示す例では、中心ｏからの方向が０〜３の４段階すなわち２ビットのビット列で表現され、例えば、図３に示した特徴２とされる。
【００４４】
なお、特徴として、グラフを構成する多角形の頂点の凹凸、エッジの長さ、あるいは隣接する多角形との最短距離などが表現されてもよい。また、属性情報を構成する特徴数は２に限定されない。例えば、主成分分析などの既知の統計的手法により、表現する特徴を決定すればよい。また、各特徴のビット長は２ビットに限定されず、表現される段階数に応じて決定される。
【００４５】
図９は、レイアウトパターンの正規化を説明する図である。特徴として、距離や間隔などの長さが表現される場合に、図９に例示するように、レイアウトパターンごとに基準となる寸法すなわち基準寸法で正規化してもよい。これにより、相似形を同一の図形として表現できる。
【００４６】
また、上述したように、隣接情報は、各ノードに隣接するノードの属性情報の各特徴に基づいて生成されたビット列が重なりなく結合されたものである。例えば、図６に示した自ノードｖ０の隣接情報の各特徴は、自ノードｖ０の隣接ノードであるノードｖ１、ノードｖ２、およびノードｖ３の各特徴に基づいて生成される。
【００４７】
すなわち、自ノードｖ０の隣接情報の特徴１として、ノードｖ１の特徴１、ノードｖ２の特徴１およびノードｖ３の特徴１の各ビット列のＸＯＲなどの論理演算結果が設定される。同様に、自ノードｖ０の隣接情報の特徴２として、ノードｖ１の特徴２、ノードｖ２の特徴２およびノードｖ３の特徴２の各ビット列の論理演算結果が設定される。また、自ノードｖ０の隣接情報の特徴３として、ノードｖ１の特徴３、ノードｖ２の特徴３およびノードｖ３の特徴３の各ビット列の論理演算結果が設定される。
【００４８】
これらの各特徴の論理演算結果のビット列を重なりなく結合して、隣接情報のビット列が設定される。図３に示した例では、２ビットの特徴１のビット列と２ビットの特徴２のビット列と３ビットの特徴３のビット列とが重なりなく結合され、７ビットの隣接情報とされている。
【００４９】
なお、論理演算はＸＯＲに限定されないが、論理演算結果のビット長は変更されない。このようにして、本実施例の生成部４１は、図３に示した例において、レイアウトパターンの各ノードについて、７ビットの属性情報と７ビットの隣接情報とを重なりなく結合して、１４ビットのノードラベルを生成する。
【００５０】
また、各ノードの隣接ノードに隣接する近接ノードについて、隣接情報と同様に導出された近接情報がノードラベルに付与されてもよい。
【００５１】
図１に戻る。算出部４２は、指定された特徴に関する複数のレイアウトパターンの間の類似度を、ノードラベルを用いて算出する。具体的に、算出部４２は、受付部４０が受け付けた未知パターンおよび特徴を指定する情報を用いて、指定された特徴に関して、未知パターンと既知パターンデータ３０に格納されている全ての既知パターンとの類似度を算出する類似度算出処理を行う。
【００５２】
図１０は、類似度算出処理の概要を説明する図である。図１０に示すように、算出部４２は、既知パターンＰｉのノードのノードラベル群（以下、ラベル集合とも表記する）Ｌｉ（Ｄ１）と、未知パターンＰ０のラベル集合Ｌ０（Ｄ２）とを対象に類似度算出処理を行って、Ｐ０とＰｉとの類似度を算出する。
【００５３】
ここで、既知パターンＰｉのノード数がｎである場合に、Ｐｉのラベル集合Ｌｉは、Ｌｉ＝｛ｌｉ１，ｌｉ２，・・・，ｌｉｎ｝と表される（Ｄ１）。また、未知パターンＰ０のノード数がｍの場合に、Ｐ０のラベル集合Ｌ０は、Ｌ０＝｛ｌ０１，ｌ０２，・・・，ｌ０ｍ｝と表される（Ｄ２）。
【００５４】
算出部４２は、既知パターンのラベル集合Ｌｉと未知パターンのラベル集合Ｌ０とを対象に、まず、対象ノード抽出処理と指定特徴マスク処理とを行って、ラベル集合Ｌｉ＿ｎｅｗおよびラベル集合Ｌ０＿ｎｅｗを生成する（ステップＳ１）。
【００５５】
ここで、対象ノード抽出処理では、後述するラベルＭ１およびラベルＭ２（Ｄ３）が用いられ、指定された特徴が所定の値をもつノードのラベルが抽出される。また、指定特徴マスク処理では、後述するラベルＭ３（Ｄ３）が用いられ、指定された特徴がラベルから除外される。
【００５６】
このとき、ラベル集合Ｌｉ＿ｎｅｗは、Ｌｉ＿ｎｅｗ＝｛ｌｉ１＿ｎｅｗ，ｌｉ２＿ｎｅｗ，・・・，ｌｉｎ＿ｎｅｗ｝と表される。また、ラベル集合Ｌ０＿ｎｅｗは、Ｌ０＿ｎｅｗ＝｛ｌ０１＿ｎｅｗ，ｌ０２＿ｎｅｗ，・・・，ｌ０ｍ＿ｎｅｗ｝と表される。
【００５７】
次に、算出部４２は、ラベル集合Ｌｉ＿ｎｅｗおよびラベル集合Ｌ０＿ｎｅｗをそれぞれラベルの値でソートして、ラベル集合Ｌｉ＿ｓｏｒｔおよびラベル集合Ｌ０＿ｓｏｒｔを生成する（ステップＳ２）。
【００５８】
ここで、ラベル集合Ｌｉ＿ｓｏｒｔは、Ｌｉ＿ｓｏｒｔ＝｛ｌｉ１＿ｓｏｒｔ，ｌｉ２＿ｓｏｒｔ，・・・，ｌｉｎ＿ｓｏｒｔ｝と表される。また、ラベル集合Ｌ０＿ｓｏｒｔは、Ｌ０＿ｓｏｒｔ＝｛ｌ０１＿ｓｏｒｔ，ｌ０２＿ｓｏｒｔ，・・・，ｌ０ｍ＿ｓｏｒｔ｝と表される。
【００５９】
最後に、算出部４２は、ラベル集合Ｌｉ＿ｓｏｒｔおよびラベル集合Ｌ０＿ｓｏｒｔに所定の類似度算出アルゴリズムを適用して類似度を算出し（ステップＳ３）、記憶部２３の適当な領域に格納する。これにより、未知パターンＰ０と既知パターンＰｉとの類似度（Ｄ４）が算出される。
【００６０】
算出部４２は、未知パターンＰ０と既知パターン集合Ｐ１，・・・，Ｐｎの全ての既知パターンとの類似度を算出する。
【００６１】
次に、図１１および図１２を参照して、対象ノード抽出処理について説明する。図１１および図１２は、対象ノード抽出処理を説明する図である。図１１には、類似度算出の対象として、２ビットの特徴１と３ビットの特徴２と３ビットの特徴３とが左詰めに重なりなく結合された８ビットのノードラベルのうち、特徴１のビット列が「０１」であるノードが抽出される場合が例示されている。
【００６２】
この場合に、算出部４２は、図１１の方法１に例示するように、８ビットのラベルＭ１「０１００００００」と８ビットのラベルＭ２「１１００００００」とを用いて論理演算を行うことにより、対象のノードを抽出する。すなわち、算出部４２は、各グラフの各ノードラベルについて、ラベルＭ１とのＸＯＲを行った後にラベルＭ２とのＡＮＤを行う論理演算により、対象ノードか否かを判定する。算出部４２は、論理演算結果がオール０であった場合は、類似度算出の対象であると判定し、オール０ではなかった場合は、類似度算出の対象外と判定する。
【００６３】
なお、図１１の方法２に例示するように、ラベルＭ１を「１１００００００」、ラベルＭ２を「０１００００００」として、ラベルＭ１とのＡＮＤを行った後にラベルＭ２とのＸＯＲを行う論理演算によっても、方法１と同様に対象のノードを抽出できる。
【００６４】
算出部４２は、上述のように設定されたラベルＭ１およびラベルＭ２を用いて、指定された特徴が所定の値をもつノードのラベルを抽出する。図１２には、グラフＧ１およびグラフＧ２の類似度算出の対象として、自ノード情報の特徴１のビット列が「０１」であるノードが抽出される場合が例示されている。
【００６５】
図１２に示す例では、対象ノード抽出処理により、ノードｖ１、ｖ２、およびｖ３のノードラベルが抽出される。抽出されたノードラベルのうち、ノードｖ１およびｖ２のノードラベルが一致している。この場合に、グラフＧ１とグラフＧ２との類似度は、例えば、（一致したノードラベルの数）／（対象ノード数の和−一致したノードラベルの数）によって算出される。これにより、図１２に示す例では、グラフＧ１とグラフＧ２との類似度は、２／（３＋３−２）＝０．５と算出される。
【００６６】
次に、図１３および図１４を参照して、指定特徴マスク処理について説明する。図１３および図１４は、指定特徴マスク処理を説明する図である。図１３には、類似度算出の対象として、２ビットの特徴１と３ビットの特徴２と３ビットの特徴３とが左詰めに重なりなく結合された８ビットのノードラベルから、特徴２の３ビットが類似度算出の対象から除外される場合が例示されている。
【００６７】
この場合に、算出部４２は、図１３に例示するように、８ビットのラベルＭ３「１１０００１１１」との論理演算を行うことにより、指定された特徴２を対象から除外する。すなわち、算出部４２は、各グラフの各ノードラベルについて、ラベルＭ３とのＡＮＤをとる論理演算により、全ノードラベルの特徴２の３ビットを「０００」として一致させて、特徴２をマスクする。
【００６８】
図１４に示す例において、算出部４２が上述のように設定されたラベルＭ３を用いて、自ノード情報の特徴２および隣接情報の特徴２を類似度算出の対象から除外すれば、グラフＧ１とグラフＧ３との間でノードｖ１、〜ｖ６の全ノードラベルが一致している。この場合に、グラフＧ１とグラフＧ３との類似度は、例えば、（一致したノードラベルの数）／（対象ノード数の和−一致したノードラベルの数）によって算出される。これにより、図１４に示す例では、グラフＧ１とグラフＧ３との類似度は、６／（６＋６−６）＝１．０と算出される。
【００６９】
図１５は、類似度算出アルゴリズムの一例を示す図である。類似度算出アルゴリズムにより、グラフＧ１のラベル集合Ｌ１およびグラフＧ２のラベル集合Ｌ２を入力として、グラフＧ１とグラフＧ２との類似度が算出される。図１５に示すアルゴリズムでは、類似度として、２つのグラフにおいてどれだけのノードラベルが一致しているかを示すマッチング値ｋが算出される。
【００７０】
具体的に、算出部４２は、長さすなわちラベル数がｎ１のソート済みのラベル集合Ｌ１と長さがｎ２のソート済みのラベル集合Ｌ２とのラベルを先頭から順に比較して、ラベルの一致数に応じてｃを算出する。そして、算出部４２は、次式（１）によりマッチング値ｋすなわち類似度を算出する。
【００７１】
ｋ＝ｃ／（ｎ１＋ｎ２−ｃ）  …（１）
【００７２】
例えば、Ｇ１とＧ２とが同一のグラフであれば、ｃ＝ｎ１＝ｎ２となり、類似度ｋ＝１．０と算出される。
【００７３】
なお、図１５において、ｍａｔｃｈ（ｂ１，ｂ２）は、ｂ１とｂ２とが一致した場合に１、それ以外の場合に０を出力する関数である。またｗｅｉｇｈｔ（ｂ１，ｂ２）は、ラベルｂ１，ｂ２の重み関数であり、ｂ１とｂ２とが一致した場合に重みｗ（ｂ１）、それ以外の場合に０が出力される。
【００７４】
ここで、重み関数では、ラベルｂ毎に異なる重みｗ（ｂ）を規定することができる。例えば、以下のように規定することにより、不良パターンにだけ現れるラベルが未知パターンに含まれている場合に、この未知パターンと不良パターンである既知パターンとの類似度の値が大きくなる。これにより、不良パターンの検出が容易になる。
【００７５】
すなわち、不良パターンにだけ現れるラベルについて、ｗ（ｂ）＝１．５と規定する。また、不良でないパターンにだけ現れるラベルについて、ｗ（ｂ）＝０．８と規定する。また、良・不良いずれの既知パターンにも現れるラベルについて、ｗ（ｂ）＝１．０と規定する。また、既知パターンに表れないラベルについて、ｗ（ｂ）＝１．０と規定する。
【００７６】
具体的に、図１５に例示した類似度算出アルゴリズムに対し、以下のラベル集合Ｌ１およびＬ２が入力された場合について説明する。すなわち、Ｌ１＝｛“０００１００１１”，“００１０１１１１”，“０１０００１０１”，“０１１００００１”｝、Ｌ２＝｛“０００１００１１”，“００１０１１１１”，“０１０１０１０１”，“０１１１０００１”｝とする。
【００７７】
重み関数においてｗ（ｂ）＝１の場合、すなわち、ラベル毎の重みを考慮しない場合、Ｌ１とＬ２とのラベルの一致数ｃ＝２であり、上記式（１）により類似度ｋ＝２／（４＋４−２）＝０．３３３・・・と算出される。
【００７８】
一方、ラベル“０００１００１１”およびラベル“００１０１１１１”が不良パターンにだけ現れる場合に、例えば、ｗ（“０００１００１１”）＝１．５、ｗ（“００１０１１１１”）＝１．５と規定される。また、その他のラベルが良・不良いずれの既知パターンにも現れる場合に、例えば、ｗ（“０１０００１０１”）＝１．０、ｗ（“０１１００００１”）＝１．０、ｗ（“０１０１０１０１”）＝１．０、ｗ（“０１１１０００１”）＝１．０と規定される。
【００７９】
この場合に、ｃ＝ｗｅｉｇｈｔ（“０００１００１１”，“０００１００１１”）＋ｗｅｉｇｈｔ（“００１０１１１１”，“００１０１１１１”）＝１．５＋１．５＝３と算出される。また、上記式（１）により、類似度ｋ＝３／（４＋４−３）＝０．６・・・と算出される。
【００８０】
ただし、上記式（１）によれば、ラベル毎の重みを考慮した場合には、グラフが同一の場合にも類似度ｋ＝１．０とはならない。そこで、ラベル毎の重みを考慮した場合の類似度ｋｎｅｗを次式（２）のように定義する。
【００８１】
【数１】
2017191556.tif 000003
【００８２】
上記式（２）によれば、類似度ｋｎｅｗ＝３／（５＋５−３）＝０．４２８・・・と算出される。このように、ラベル毎の重みを考慮することにより、考慮しない場合の類似度ｋ＝０．３３３・・・より値が大きくなるので、不良パターンの検出が容易になることがわかる。
【００８３】
なお、ラベル毎の重みｗ（ｂ）は、予め規定して記憶部２３の適当な領域に格納しておけばよい。また、類似度の算出は、上述したようにラベル集合Ｌ１およびＬ２のノードラベルが完全に一致する数に基づく方式に限定されない。例えば、Ｌ１およびＬ２のノードラベルの上位所定数が一致する場合にノードラベル同士が一致するものとして類似度を算出してもよい。すなわち、例えば、両ノードラベルの上位３ビットが一致している場合にｃを増やして、マッチング値ｋを算出する。また、これらの方式を切り替えて類似度を算出するようにしてもよい。
【００８４】
なお、特徴の指定は、例えば、上述した類似度算出アルゴリズムに、以下に示すように「ＳＩＭ」で始まる１行を記載して行うことができる。ここで、「Ｆ＜特徴ＩＤ＞＜ビット列＞」は、指定された特徴ＩＤのビット列が一致するノードラベルを対象とすることを表す。また、「Ｎ＜特徴ＩＤ＞」は、指定された特徴ＩＤのビット列はノードラベルの一致を判定する際に無視することを表す。
【００８５】
例えば、「ＳＩＭ  Ｆ１“０１”」と記載して、特徴１が“０１”であるラベルを対象とすることを指定できる。また、「ＳＩＭ  Ｆ１“１１”Ｆ２“００”」と記載して、特徴１が“１１”かつ特徴２が“００”であるラベルを対象とすることを指定できる。あるいは、「ＳＩＭ  Ｎ１Ｆ２“００”」と記載して、特徴１を無視し、特徴２が“００”のラベルを対象とすることを指定できる。また、「ＳＩＭ  Ｎ１Ｎ２」と記載して、特徴１および特徴２を無視することを指定できる。
【００８６】
このように、１行に対応する１つの定義について、指定する複数の特徴を列挙してＡＮＤ条件として指定できる。
【００８７】
以上に説明したように、算出部４２は、指定された特徴に関する類似度を算出することにより、ノードラベルの特徴の一部に着目して類似度が高いレイアウトパターンを検索できる。例えば、レイアウトパターンの領域を指定して領域内での類似度を算出することができる。あるいは、レイアウトパターンの回転や反転を許容して類似度を算出することができる。
【００８８】
図１６〜図１８は、レイアウトパターンの領域の指定を説明する図である。図１６に例示するように、レイアウトパターンの各ノードの特徴の１つとして、各ノードが位置する領域を表現することにより、レイアウトパターンの領域を指定して類似度を算出することが可能となる。図１６に示す例では、レイアウトパターンをａ１、ａ２、およびａ３の３つの領域に区分して、各領域を指定するビット列が規定されている。各ノードのノードラベルには、各ノードのレイアウトパターン上の位置に応じたビット列が設定される。
【００８９】
これにより、例えば、図１７に太線枠で示したレイアウトパターンの一部の領域を指定して、当該領域内に位置するノードを類似度算出の対象とすることができる。この場合に、受付部４０は、例えば、図１８に例示する入力画面を表示部２１に表示させることにより、入力部２０を介して領域を指定する入力を受け付ける。
【００９０】
図１９および図２０は、レイアウトパターンの回転・反転を説明する図である。レイアウトパターンの各ノードの特徴の１つとして、図８に例示したように、レイアウトパターンの中心からの方向が表現されている場合に、方向を類似度算出の対象から除外することができる。
【００９１】
これにより、図１９に示すように、回転や反転を許容することができる。すなわち、図１９（ａ）に示すレイアウトパターンと、これを左右に反転させた図１９（ｂ）に示すレイアウトパターンとを同一とみなすことができる。同様に、図１９（ａ）に示すレイアウトパターンと、これを時計回りに９０度回転させた図１９（ｃ）に示すレイアウトパターンとを同一とみなすことができる。この場合に、受付部４０は、例えば、図２０に例示する入力画面を表示部２１に表示させることにより、入力部２０を介して回転・反転を許容する入力を受け付ける。
【００９２】
出力部４３は、算出部４２により算出された類似度に基づいて、入力された未知パターンＰ０と類似度が高い既知パターンＰｉを出力する。例えば、出力部４３は、未知パターンＰ０との類似度の大きさに応じた順位づけを各既知パターンに対して行う。そして、出力部４３は、例えば、各順位に既知パターン名と、パターンの図面と、指定された特徴と、類似度とを対応付け、表示部２１に表示する。
【００９３】
図２１は、類似度検索結果の一例を示す図である。図２１の例は、未知パターンについて、未知パターンとの類似度の高い順に既知パターンを表示している。算出部４２が未知パターン「Ｕ１００」と、既知パターン「Ｐ０２５」、「Ｐ００８」、「Ｐ０２７」それぞれとの類似度を、「０．９９」、「０．９７」、「０．５８」と算出したことを示す。その際、「回転・反転ＯＫ」すなわちレイアウトパターンの回転や反転を許容すると指定された特徴の下で、類似度が算出されたことを示す。さらに、図２１の例は、出力部４３が、未知パターン「Ｕ１００」との類似度の大きさに応じた順位として、「Ｐ０２５：１位」、「Ｐ００８：２位」、「Ｐ０２７：３位」といった順位付けを行ったことを示す。
【００９４】
なお、図２１では、表示部２１に順位１位〜３位までの既知パターンが表示される例を示しているが、この例に限らず、例えば、１〜１０位までであってもよい。すなわち、どの順位まで提示するかは、出力部４３に対し任意に設定されてよい。
【００９５】
次に、図２２を参照して、本実施例に係る類似度検索装置１０が実行する類似度検索処理の流れについて説明する。図２２は、類似度検索処理手順を示すフローチャートである。図２２に例示するフローチャートは、一例として、処理対象の未知パターンデータ３１が入力されたタイミングで起動される。
【００９６】
まず、生成部４１が、既知パターンデータ３０および未知パターンデータ３１に基づくグラフのノード毎に、ノードラベルを生成する（ステップＳ１１）。ここで、ノードラベルは、各ノードの属性情報と隣接情報とが重なりなく結合されたものである。属性情報は、各ノードの特徴が表現された所定長のビット列が重なりなく結合されたものであり、隣接情報は、隣接ノードの属性情報の各特徴に基づいて生成されたビット列が重なりなく結合されたものである。
【００９７】
なお、生成部４１は、既知パターンデータ３０について、予めノードラベルを生成しておいてもよい。
【００９８】
次に、算出部４２が、特徴を指定する入力を待機して（ステップＳ１２，Ｎｏ）、特徴の指定があった場合に（ステップＳ１２，Ｙｅｓ）、指定された特徴に関する未知パターンデータ３１と各既知パターンデータ３０との類似度を算出する（ステップＳ１３）。
【００９９】
なお、特徴の指定は必須でなくてもよい。例えば、ステップＳ１２の処理において、所定時間のタイマが満了した場合に、特徴の指定がないものとみなしてステップＳ１３の処理に移行してもよい。
【０１００】
算出部４２は、未知パターンデータ３１と全ての既知パターンデータ３０との類似度の算出が終わるまで（ステップＳ１４，Ｎｏ）、ステップＳ１３の処理を繰り返す。全ての既知パターンデータ３０との類似度の算出が終了した場合に（ステップＳ１４，Ｙｅｓ）、出力部４３が、未知パターンデータ３１と類似度の高い既知パターンデータ３０とを対応づけて表示部２１に出力する（ステップＳ１５）。これにより、一連の類似度検索処理が終了する。
【０１０１】
上述してきたように、類似度検索装置１０は、生成部４１と算出部４２とを有する。生成部４１は、レイアウトパターンに含まれるノード毎に、属性情報と隣接情報とを重なりなく結合したラベルを生成する。また、算出部４２が、指定された特徴に関する複数のレイアウトパターンの間の類似度を、ノードラベルを用いて算出する。
【０１０２】
ここで、各レイアウトパターンに含まれる平均ノード数をｎ（〜１０００）とすると、Ｎ個のレイアウトパターンについて、ノードラベルを生成する処理にかかる時間は、〜Ｏ（ｎｌｏｇｎ）＊Ｎで表される。また、Ｎ組のレイアウトパターン間の類似度を算出する処理にかかる時間は、〜Ｏ（ｎ）＊Ｎで表される。
【０１０３】
本実施例の類似度検索装置１０では、指定の特徴をもつノードラベルを論理演算で抽出でき、従来のように特徴を指定する度にノードラベルを生成する必要がないため、指定する特徴を変更して類似度を算出する処理にかかる時間が大幅に短縮される。したがって、類似度検索装置１０は、ノードラベルの特徴の一部に着目して類似度が高いレイアウトパターンを検索する処理を容易に行える。
【０１０４】
このように、本実施例の類似度検索装置１０は、ユーザが指定した特徴に注目して類似度の高い過去のレイアウトパターンを検索できる。これにより、例えば、過去の不良のレイアウトパターンと類似度が高いレイアウトパターンを不良と予測することができる。
【０１０５】
また、算出部４２は、指定された特徴が所定の値をもつノードを対象として類似度を算出する。また、算出部４２は、指定された特徴を除外して類似度を算出する。これにより、類似度検索装置１０は、効率よく注目する特徴を指定して過去のレイアウトパターンを検索できる。
【実施例２】
【０１０６】
さて、これまで類似度検索装置１０について、実施例１で説明してきた。しかし、類似度検索装置１０は、かかる実施例以外にも、特許請求の範囲に記載した技術的思想の範囲内において種々の異なる実施例にて実施されてもよいものである。
【０１０７】
実施例１では、類似度検索装置１０は、未知パターンとして、１つの未知パターンＰ０の入力を受け付け、既知パターン集合Ｐ１，・・・，Ｐｎとの類似度を算出する例について説明してきたが、この例に限定されるものではない。例えば、類似度検索装置１０は、複数の未知パターンの入力を受け付けてもよい。そして、類似度検索装置１０は、受け付けた複数の未知パターンの全てを同時に、または、順に処理してもよい。また、類似度検索装置１０は、受け付けた複数の未知パターンのうち所定数を選択させ、それらを同時に、または、順に処理してもよい。
【０１０８】
また、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【０１０９】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示のように構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【０１１０】
さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０１１１】
[類似度検索プログラム]
また、上記の実施例で説明した各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することもできる。そこで、以下では、上記の実施例と同様の機能を有するプログラムを実行するコンピュータシステムの一例を説明する。図２３は、類似度検索プログラムを実行するコンピュータを示す図である。
【０１１２】
図２３に示すように、コンピュータ３００は、ＣＰＵ３１０、ＲＯＭ（Read  Only  Memory）３２０、ＨＤＤ（Hard  Disk  Drive）３３０、ＲＡＭ（Random  Access  Memory）３４０を有する。これら３１０〜３４０の各部は、バス４００を介して接続される。
【０１１３】
ＲＯＭ３２０には上記実施例の各処理部と同様の機能を発揮する類似度検索プログラム３２０ａが予め記憶される。例えば、上記実施例の受付部４０、生成部４１、算出部４２および出力部４３と同様の機能を発揮する類似度検索プログラム３２０ａを記憶させる。なお、類似度検索プログラム３２０ａについては、適宜分離しても良い。
【０１１４】
ＨＤＤ３３０には、各種データを記憶する。例えば、ＨＤＤ３３０は、ＯＳや各種データを記憶する。
【０１１５】
そして、ＣＰＵ３１０が、類似度検索プログラム３２０ａをＲＯＭ３２０から読み出して実行することで、上記実施例の各処理部と同様の動作を実行する。すなわち、類似度検索プログラム３２０ａは、実施例の受付部４０、生成部４１、算出部４２および出力部４３と同様の動作を実行する。
【０１１６】
なお、上記した類似度検索プログラム３２０ａについては、必ずしも最初からＲＯＭ３２０に記憶させることを要しない。類似度検索プログラム３２０ａはＨＤＤ３３０に記憶させてもよい。
【０１１７】
例えば、コンピュータ３００に挿入されるフレキシブルディスク（ＦＤ）、Compact  Disk  Read  Only  Memory（ＣＤ−ＲＯＭ）、Digital  Versatile  Disk（ＤＶＤ）、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」にプログラムを記憶させておく。そして、コンピュータ３００がこれらからプログラムを読み出して実行するようにしてもよい。
【０１１８】
さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ３００に接続される「他のコンピュータ（またはサーバ）」などにプログラムを記憶させておく。そして、コンピュータ３００がこれらからプログラムを読み出して実行するようにしてもよい。
【符号の説明】
【０１１９】
１０    類似度検索装置
２０    入力部
２１    表示部
２２    通信Ｉ／Ｆ部
２３    記憶部
２４    制御部
３０    既知パターンデータ
３１    未知パターンデータ
４０    受付部
４１    生成部
４２    算出部
４３    出力部
【図１】
2017191556.tif 000004
【図２】
2017191556.tif 000005
【図３】
2017191556.tif 000006
【図４】
2017191556.tif 000007
【図５】
2017191556.tif 000008
【図６】
2017191556.tif 000009
【図７】
2017191556.tif 000010
【図８】
2017191556.tif 000011
【図９】
2017191556.tif 000012
【図１０】
2017191556.tif 000013
【図１１】
2017191556.tif 000014
【図１２】
2017191556.tif 000015
【図１３】
2017191556.tif 000016
【図１４】
2017191556.tif 000017
【図１５】
2017191556.tif 000018
【図１６】
2017191556.tif 000019
【図１７】
2017191556.tif 000020
【図１８】
2017191556.tif 000021
【図１９】
2017191556.tif 000022
【図２０】
2017191556.tif 000023
【図２１】
2017191556.tif 000024
【図２２】
2017191556.tif 000025
【図２３】
2017191556.tif 000026