(57)【要約】  類似データ検索装置２は、検索対象集合の数が設定個数以上になるように、各転置インデックスの検索対象集合のサイズの範囲を決定し、サイズの範囲毎に検索対象集合を分けて、転置インデックスを生成する、転置インデックス生成部２０と、検索条件集合のサイズと集合間類似度に対して設定された閾値とに基づいて、類似度が閾値以上となるために必要な条件を求め、集合のサイズの最小値が条件を満たす転置インデックス以外を、検索不要な転置インデックスとして同定する不要転置インデックス同定部２１と、非同定転置インデックスに対して検索を実行するデータ検索部２２と、を備える。
2014136810.tif 000002
【特許請求の範囲】
【請求項１】
検索対象となるデータ及び検索条件となるデータとして集合を用いて検索を行うための類似データ検索装置であって、
検索に使用する転置インデックスの生成のため、生成予定の各転置インデックスに含まれる検索対象の集合の数が設定個数以上になるように、前記生成予定の転置インデックス毎に、前記検索対象の集合のサイズの範囲を決定し、決定した前記サイズの範囲毎に、前記検索対象の集合を分けて、前記転置インデックスを生成する、転置インデックス生成部と、
検索条件の集合のサイズと、前記検索条件の集合と前記検索対象の集合との類似度に対して設定された閾値と、に基づいて、前記類似度が閾値以上となるために必要な、前記検索対象の集合のサイズの条件を求め、前記転置インデックスのうち、それに含まれる集合のサイズの最小値が前記条件を満たす転置インデックス以外を、検索不要な転置インデックスとして同定する、不要転置インデックス同定部と、
同定された前記検索不要な転置インデックス以外の転置インデックスに対して、前記検索条件の集合を適用して、検索を実行する、データ検索部と、
を備えることを特徴とする類似データ検索装置。
【請求項２】
前記転置インデックス生成部が、前記検索対象の集合の総数を、設定された値で除算することによって、前記設定個数を算出し、算出した前記設定個数に基づいて、前記生成予定の転置インデックス毎に、前記検索対象の集合のサイズの範囲を決定する、請求項１に記載の類似データ検索装置。
【請求項３】
前記転置インデックス生成部が、前記検索条件の集合が複数存在する場合に、前記データ検索部による検索にかかる時間の総和が小さくなるように、前記生成予定の各転置インデックスに含まれる検索対象の集合の最小数を決定する、請求項１または２に記載の類似データ検索装置。
【請求項４】
前記不要転置インデックス同定部は、
前記検索条件の集合から前記検索対象の集合に対する重複度、前記検索対象の集合から前記検索条件の集合に対する重複度、ジャカード係数、ダイス係数、コサイン類似度のうち、いずれかによって規定される数式と、前記閾値とを用いて、前記条件を計算する、
請求項１から３のいずれかに記載の類似データ検索装置。
【請求項５】
前記データ検索部が、同定された前記検索不要な転置インデックス以外の転置インデックスに含まれる集合の中から、前記検索条件の集合の要素を含む集合を特定し、特定した集合と前記検索条件の集合との前記類似度が前記閾値以上となる場合に、特定した集合を検索結果とする、
請求項１〜４のいずれかに記載の類似データ検索装置。
【請求項６】
前記転置インデックス生成部が、更に、前記検索対象の集合に含まれる各要素に対して予め付与されている重要度を用いて、前記検索対象の集合それぞれのサイズを計算する、
請求項１〜５のいずれかに記載の類似データ検索装置。
【請求項７】
前記類似度が、前記検索条件の集合から前記検索対象の集合に対する重複度、前記検索対象の集合から前記検索条件の集合に対する重複度、ジャカード係数、ダイス係数、コサイン類似度のうち、いずれかによって規定される数式を用いて計算されており、
前記データ検索部が、
同定された前記検索不要な転置インデックス以外の転置インデックスに含まれる集合それぞれについて順に、前記検索条件の集合の要素を、重要度の降順に、一つずつ照合し、
照合が未だ行われていない要素の前記重要度の和が、前記条件を満たさなくなった場合は、前記転置インデックスに含まれる集合のうち、その時点までに照合が行われた集合のみを対象として、前記照合が未だ行われていない要素を用いた照合を行い、
前記その時点までに照合が行われた集合についてのみ、前記検索条件の集合の要素と共通する要素の前記重要度の和を計算し、
計算した和の値が、前記類似度が前記閾値以上となる場合と等価になる条件を満たす場合に、計算の対象となった前記集合を検索結果とする、
請求項６に記載の類似データ検索装置。
【請求項８】
前記検索対象の集合及び前記検索条件の集合に含まれる要素のうち、定められた同義要素の集合に属する要素を、前記同義要素の代表要素に変換する、同義要素変換部を、更に備えている、請求項１から７のいずれかに記載の類似データ検索装置。
【請求項９】
検索対象となるデータ及び検索条件となるデータとして集合を用いて検索を行うための方法であって、
（ａ）検索に使用する転置インデックスの生成のため、生成予定の各転置インデックスに含まれる検索対象の集合の数が設定個数以上になるように、前記生成予定の転置インデックス毎に、前記検索対象の集合のサイズの範囲を決定し、決定した前記サイズの範囲毎に、前記検索対象の集合を分けて、前記転置インデックスを生成する、ステップと、
（ｂ）検索条件の集合のサイズと、前記検索条件の集合と前記検索対象の集合との類似度に対して設定された閾値と、に基づいて、前記類似度が閾値以上となるために必要な、前記検索対象の集合のサイズの条件を求め、前記転置インデックスのうち、それに含まれる集合のサイズの最小値が前記条件を満たす転置インデックス以外を、検索不要な転置インデックスとして同定する、ステップと、
（ｃ）前記（ｂ）のステップで同定された前記検索不要な転置インデックス以外の転置インデックスに対して、前記検索条件の集合を適用して、検索を実行する、ステップと、
を有することを特徴とする類似データ検索方法。
【請求項１０】
コンピュータによって、検索対象となるデータ及び検索条件となるデータとして集合を用いて検索を行うためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記コンピュータに、
（ａ）検索に使用する転置インデックスの生成のため、生成予定の各転置インデックスに含まれる検索対象の集合の数が設定個数以上になるように、前記生成予定の転置インデックス毎に、前記検索対象の集合のサイズの範囲を決定し、決定した前記サイズの範囲毎に、前記検索対象の集合を分けて、前記転置インデックスを生成する、ステップと、
（ｂ）検索条件の集合のサイズと、前記検索条件の集合と前記検索対象の集合との類似度に対して設定された閾値と、に基づいて、前記類似度が閾値以上となるために必要な、前記検索対象の集合のサイズの条件を求め、前記転置インデックスのうち、それに含まれる集合のサイズの最小値が前記条件を満たす転置インデックス以外を、検索不要な転置インデックスとして同定する、ステップと、
（ｃ）前記（ｂ）のステップで同定された前記検索不要な転置インデックス以外の転置インデックスに対して、前記検索条件の集合を適用して、検索を実行する、ステップと、
を実行させる命令を含む、プログラムを記録しているコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、類似データ検索装置、特には、文字列から変換された集合の集合間類似度に基づいて検索を行う、類似データ検索装置、及び類似データ検索方法に関し、更には、これらを実現するための類似データ検索用プログラムを記録したコンピュータ読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
類似データ検索は、クラスタリング、重複データ照合、文字列ソフトマッチングなどに幅広く応用可能な、基本的で、且つ重要なデータ処理である。類似データ検索の具体な方法としては、単純に、対象となる全てのデータの間の類似度を計算し、類似度に基づいて検索を行なう方法が挙げられるが、この方法では、データ量が多くなると処理時間も膨大になる。【０００３】
例えば、類似度が一定以上の全てのデータペアをデータベース内から検索する場合、与えられたデータがN個とすると、(N(N-1)/2)回の類似度計算が必要となる。これは、例えば、一回の類似度計算にかかる時間が、0.001ミリ秒とした場合、データの個数Nが100,000個であるならば、約50億回の類似度計算が必要となるため、計算には約14日を要することになる。【０００４】
このため、非特許文献１は、類似度が一定以上の全データペアを高速に検索して処理時間を短縮するシステムを開示している。非特許文献１に開示されたシステムは、まず、文字列をその特徴の集合に変換し、集合のサイズを集合内の要素の個数と定義し、、集合を同じサイズで分けて、同じサイズの集合毎に、転置インデックスを作成する。次に、非特許文献１に開示されたシステムは、検索時に、入力される集合のサイズと類似度閾値とから、検索すべき転置インデックスのサイズの最小値と最大値とを同定し、同定したサイズの範囲にある転置インデックスのみを検索する。【０００５】
具体的には、非特許文献１は、その表１において、検索が要求された集合をXとし、ジャッカード係数（X∩Y|/|X∪Y|）が閾値α以上の場合は、α|X|以上、|X|/α以下のサイズに該当する転置インデックスのみを検索すれば十分であることを開示している。従って、非特許文献１に開示されたシステムは、転置インデックスを集合のサイズ毎に作成し、検索条件（検索要求）から決まるサイズの上限と下限とを用いて、検索すべき転置インデックスを同定する。この結果、無駄な検索が省かれるので、検索処理の高速化が可能となる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】岡崎直観, 辻井潤一「集合間類似度に対する簡潔かつ高速な類似文字列検索アルゴリズム」、自然言語処理、Vol. 18、No. 2、pp. 89-117、2011年.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、非特許文献１に開示されたシステムには、検索対象となるデータ中に同じサイズの集合が少ない場合に、検索効率が悪化するという問題がある。【０００８】
その理由は、同じサイズの集合毎に転置インデックスが作成されているため、同じサイズのデータが少ない場合には、各転置インデックスから検索可能な集合が少なくなり、同じ結果を得るために必要な転置インデックスへの検索回数が増えることにある。【０００９】
平均的には、同じサイズの集合の数と、同じ結果を取得するために必要な転置インデックスに対する検索回数とは反比例の関係となる。そのため、外部の記憶装置へのランダムアクセスが行われる場合など、転置インデックスに対する検索コストが高い場合には、特に検索効率が悪化する。【００１０】
［発明の目的］
本発明の目的の一例は、上記問題を解消し、検索対象となるデータ中に同じサイズの集合が少ない場合であっても、転置インデックスにおける検索回数の増加による検索効率の低下を抑制し得る、類似データ検索装置、類似データ検索方法、及びコンピュータ読み取り可能な記録媒体を提供することにある。
【課題を解決するための手段】
【００１１】
上記目的を達成するため、本発明の一側面における類似データ検索装置は、検索対象となるデータ及び検索条件となるデータとして集合を用いて検索を行うための類似データ検索装置であって、
検索に使用する転置インデックスの生成のため、生成予定の各転置インデックスに含まれる検索対象の集合の数が設定個数以上になるように、前記生成予定の転置インデックス毎に、前記検索対象の集合のサイズの範囲を決定し、決定した前記サイズの範囲毎に、前記検索対象の集合を分けて、前記転置インデックスを生成する、転置インデックス生成部と、
検索条件の集合のサイズと、前記検索条件の集合と前記検索対象の集合との類似度に対して設定された閾値と、に基づいて、前記類似度が閾値以上となるために必要な、前記検索対象の集合のサイズの条件を求め、前記転置インデックスのうち、それに含まれる集合のサイズの最小値が前記条件を満たす転置インデックス以外を、検索不要な転置インデックスとして同定する、不要転置インデックス同定部と、
同定された前記検索不要な転置インデックス以外の転置インデックスに対して、前記検索条件の集合を適用して、検索を実行する、データ検索部と、
を備えることを特徴とする。【００１２】
また、上記目的を達成するため、本発明の一側面における類似データ検索方法は、検索対象となるデータ及び検索条件となるデータとして集合を用いて検索を行うための方法であって、
（ａ）検索に使用する転置インデックスの生成のため、生成予定の各転置インデックスに含まれる検索対象の集合の数が設定個数以上になるように、前記生成予定の転置インデックス毎に、前記検索対象の集合のサイズの範囲を決定し、決定した前記サイズの範囲毎に、前記検索対象の集合を分けて、前記転置インデックスを生成する、ステップと、
（ｂ）検索条件の集合のサイズと、前記検索条件の集合と前記検索対象の集合との類似度に対して設定された閾値と、に基づいて、前記類似度が閾値以上となるために必要な、前記検索対象の集合のサイズの条件を求め、前記転置インデックスのうち、それに含まれる集合のサイズの最小値が前記条件を満たす転置インデックス以外を、検索不要な転置インデックスとして同定する、ステップと、
（ｃ）前記（ｂ）のステップで同定された前記検索不要な転置インデックス以外の転置インデックスに対して、前記検索条件の集合を適用して、検索を実行する、ステップと、
を有することを特徴とする。【００１３】
更に、上記目的を達成するため、本発明の一側面におけるコンピュータ読み取り可能な記録媒体は、コンピュータによって、検索対象となるデータ及び検索条件となるデータとして集合を用いて検索を行うためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記コンピュータに、
（ａ）検索に使用する転置インデックスの生成のため、生成予定の各転置インデックスに含まれる検索対象の集合の数が設定個数以上になるように、前記生成予定の転置インデックス毎に、前記検索対象の集合のサイズの範囲を決定し、決定した前記サイズの範囲毎に、前記検索対象の集合を分けて、前記転置インデックスを生成する、ステップと、
（ｂ）検索条件の集合のサイズと、前記検索条件の集合と前記検索対象の集合との類似度に対して設定された閾値と、に基づいて、前記類似度が閾値以上となるために必要な、前記検索対象の集合のサイズの条件を求め、前記転置インデックスのうち、それに含まれる集合のサイズの最小値が前記条件を満たす転置インデックス以外を、検索不要な転置インデックスとして同定する、ステップと、
（ｃ）前記（ｂ）のステップで同定された前記検索不要な転置インデックス以外の転置インデックスに対して、前記検索条件の集合を適用して、検索を実行する、ステップと、
を実行させる命令を含む、プログラムを記録していることを特徴とする。
【発明の効果】
【００１４】
以上のように本発明によれば、検索対象となるデータ中に同じサイズの集合が少ない場合であっても、転置インデックスにおける検索回数の増加による検索効率の低下を抑制することができる。
【図面の簡単な説明】
【００１５】
【図１】図１は、本発明の実施の形態１における類似データ検索装置の構成を示すブロック図である。
【図２】図２は、本発明の実施の形態１における類似データ検索装置の動作を示すフロー図である。
【図３】図３は、類似度としてジャッカード係数が用いられる場合のステップＡ１の一例を説明する図である。
【図４】図４は、集合のサイズの範囲を求めるための数式の一例を示す図である。
【図５】図５は、類似度が閾値以上となる場合と等価であるとされる条件の一例を示す図である。
【図６】図６は、本発明の実施の形態２における類似データ検索装置の構成を示すブロック図である。
【図７】図７は、本発明の実施の形態２における類似データ検索装置の動作を示すフロー図である。
【図８】図８は、本発明の実施の形態１及び２における類似データ検索装置を実現するコンピュータの一例を示すブロック図である。
【発明を実施するための形態】
【００１６】
（実施の形態１）
以下、本発明の実施の形態１における、類似データ検索装置、類似データ検索方法、及び類似データ検索用プログラムについて、図１〜図５を参照しながら説明する。
【００１７】
［装置構成］
最初に、本実施の形態１における類似データ検索装置の構成について図１を用いて説明する。図１は、本発明の実施の形態１における類似データ検索装置の構成を示すブロック図である。
【００１８】
図１に示す本実施の形態１における類似データ検索装置２は、検索対象となるデータ及び検索条件となるデータとして集合を用いて検索を行う装置である。図１に示すように、類似データ検索装置２は、転置インデックス生成部２０と、不要転置インデックス同定部２１と、データ検索部２２とを備えている。
【００１９】
転置インデックス生成部２０は、検索に使用する転置インデックスを生成する。このため、まず、転置インデックス生成部２０は、生成予定の各転置インデックスに含まれる検索対象の集合の数が設定個数以上になるように、生成予定の転置インデックス毎に、検索対象の集合のサイズの範囲を決定する。そして、転置インデックス生成部２０は、決定したサイズの範囲毎に、検索対象の集合を分けて、転置インデックスを生成する。
【００２０】
不要転置インデックス同定部２１は、まず、検索条件の集合のサイズと、検索条件の集合と検索対象の集合との類似度に対して設定された閾値と、に基づいて、類似度が閾値以上となるために必要な、検索対象の集合のサイズの条件を求める。次に、不要転置インデックス同定部２１は、転置インデックスのうち、それに含まれる集合のサイズの最小値が条件を満たす転置インデックス以外を、検索不要な転置インデックスとして同定する。
【００２１】
データ検索部２２は、不要転置インデックス同定部２１によって同定された検索不要な転置インデックス以外の転置インデックスを特定し、この特定した転置インデックスに対して、検索条件の集合を適用して、検索を実行する。
【００２２】
このように、本実施の形態では、各転置インデックスにおいて、それに含まれる集合のサイズの範囲が決められ、このサイズの範囲に基づいて、検索条件の集合の検索先として不適切な転置インデックスが同定される。そして、同定された転置インデックスを除いて、検索が行なわれる。この結果、検索対象となるデータ中に同じサイズの集合が少ない場合であっても、転置インデックスにおける検索回数の増加による検索効率の低下を抑制することができる。
【００２３】
ここで、本実施の形態１における類似データ検索装置２の構成について更に具体的に説明する。図１に示すように、類似データ検索装置２は、データ記憶装置１と、入力装置３と、出力装置４とに接続され、これらと共に、類似データ検索システム３０を構築している。
【００２４】
データ記憶装置１は、検索対象の集合で構成された検索対象データ１０と、検索対象の集合に含まれる要素に予め付与された重要度を特定する要素重要度データ１１と、を記憶している（後述の図３参照）。
【００２５】
また、入力装置３は、類似データ検索装置２に、検索条件の集合、及び類似度の閾値といったデータを入力する装置である。入力装置３としては、キーボード等の入力機器、類似データ検索装置２にネットワークを介して接続された端末装置、等が挙げられる。
【００２６】
出力装置４は、検索結果の出力先となる装置である。出力措置４としては、表示装置、プリンタ等が挙げられるが、その他に、類似データ検索装置２にネットワークを介して接続された端末装置も挙げられる。なお、入力装置３と出力装置４とは、同一の端末装置であっても良い。
【００２７】
また、本実施の形態１において、「集合」は、１つ以上の要素で構成されていれば良く、各要素には、上述したように、予め重要度が付与されていても良い（後述の図３参照）。なお、非特許文献１に記載されているように、集合は、要素となる文字tri-gramから構成されていても良い。
【００２８】
また、本実施の形態１において、検索条件の集合と検索対象の集合との「類似度」は、例えば、検索対象の集合をD、検索条件（検索要求）の集合をQ、重要度の重みを返す関数をw(.)とすると、これらを用いた数式によって計算される。例えば、集合間の類似度は、Dから見たQの重複度overlap(Q,D)、Qから見たDの重複度overlap(D,Q)、コサイン類似度cosine(Q,D)、ダイス係数dice(Q,D)、及びジャッカード係数jaccard(Q,D)のうちいずれかによって計算される。
【００２９】
具体的には、集合間の類似度は、下記の数１〜数５のいずれかを用いることで計算することができる。但し、本実施の形態において、類似度は、下記の式で計算されるものに限られるわけではない。本実施の形態では、類似度は、集合の大きさによって条件を規定できるものであれば良く、特に限定なく適用することができる。
【００３０】
【数１】
2014136810.tif 000003
【００３１】
【数２】
2014136810.tif 000004
【００３２】
【数３】
2014136810.tif 000005
【００３３】
【数４】
2014136810.tif 000006
【００３４】
【数５】
2014136810.tif 000007
【００３５】
[装置動作]
次に、本発明の実施の形態１における類似データ検索装置２の動作について図２〜図５を用いて説明する。図２は、本発明の実施の形態１における類似データ検索装置の動作を示すフロー図である。以下の説明においては、適宜図１を参酌する。また、本実施の形態１では、類似データ検索装置２を動作させることによって、類似データ検索方法が実施される。よって、本実施の形態１における類似データ検索方法の説明は、以下の類似データ検索装置の動作説明に代える。
【００３６】
［ステップＡ１］
最初に、図２に示すように、転置インデックス作成部２０が、データ記憶装置１から、検索対象の集合で構成された検索対象データ１０と、集合の要素の重要度を示す要素重要度データ１１とを、読み出す。そして、転置インデックス作成部２０は、これらのデータを用いて検索対象の集合それぞれのサイズを計算する。
【００３７】
続いて、転置インデックス作成部２０は、生成予定の各転置インデックスに含まれる検索対象の集合の数が設定個数以上になるように、検索対象の集合のサイズの範囲を決定する。そして、転置インデックスル作成部２０は、決定したサイズの範囲毎に検索対象の集合を分けて、各転置インデックスを生成する（ステップＡ１）。
【００３８】
また、転置インデックス生成部２０は、検索条件の集合が複数存在する場合には、検索条件の集合それぞれで検索を試行し、データ検索部２２で要する検索時間の総和が小さくなるように、生成予定の各転置インデックスに含まれる検索対象の集合の最小数を決定することができる。
【００３９】
ここで、集合のサイズの計算の仕方について具体的に説明する。サイズの計算の対象となる集合をXとすると、類似度として、上述の２種類の重複度、ダイス係数、又はジャッカード係数が用いられる場合は、集合Xのサイズは、下記の数６によって定義される。また、類似度として、コサイン類似度が用いられる場合は、集合Xのサイズは、下記の数７によって定義される。
【００４０】
【数６】
2014136810.tif 000008
【００４１】
【数７】
2014136810.tif 000009
【００４２】
また、ステップＡ１では、転置インデックス生成部２０は、検索対象の集合に含まれる各要素に対して予め付与されている重要度を用いて、検索対象の集合それぞれのサイズを計算することができる。このとき、全ての要素の重要度は１としても良く、この場合、集合のサイズは集合の要素の個数に一致する。
【００４３】
一方、要素の重要度が細かく設定されている程、同じサイズの集合が少なくなる。このため、上述の本実施の形態１で得られる効果は大きくなる。従って、本実施の形態１では、重要度は出来る限り、細かく設定されているのが好ましい。
【００４４】
また、ステップＡ１では、転置インデックス生成部２０は、各転置インデックスが、必ず一定数以上の集合を持つように、サイズの範囲に閾値を定め、検索対象の集合の総数を、設定値で除算することによって設定個数を算出することができる。そして、転置インデックス生成部２０は、算出した設定個数に基づいて、生成予定の転置インデックス毎に、検索対象の集合のサイズの範囲を決定することができる。つまり、転置インデックス生成部２０は、検索対象の集合の総数を、設定個数Nで除算して均等に全体をN個に分割することで、サイズを決定しても良い。
【００４５】
また、サイズの範囲の閾値及び設定個数Nは、検索条件の候補となる集合のサンプルを用いて実際に検索を行うことによって設定できる。この場合、最も計算時間が速くなるように設定するのが好ましい。
【００４６】
更に、各転置インデックスから検索可能な集合の個数の基準を決定できる場合は、検索対象の各集合のサイズを計算し、これらをサイズの昇順に並べ、サイズの小さい集合から各転置インデックスに所定の条件を満たすまで加えていくことで、転置インデックスの生成が可能である。
【００４７】
ここで、図３を用いて、ステップＡ１の具体例について説明する。図３は、類似度としてジャッカード係数が用いられる場合のステップＡ１の一例を説明する図である。また、図３の例では、設定個数Nは、50に設定されている。
【００４８】
図３に示すように、検索対象データとなる各集合には、識別子SIDが付与されている。また、各集合のサイズは、類似度としてジャッカード係数が用いられるので、上記の数６を用いて計算されている。例えば、SID=1の集合のサイズは6.8となる。
【００４９】
また、図３の例では、検索対象データが10000個存在するため、転置インデックスの数に合わせて、検索対象データを50分割する場合は、おおよそ200個の集合が属するように転置インデックスを作成すれば良いことが分かる。
【００５０】
そのため、転置インデックス生成部２０は、検索対象の集合それぞれをサイズの昇順に並べ、各転置インデックスには、200個を超えるまで集合が追加される。このとき、200個目の集合と同じサイズの集合が存在する場合は、転置インデックス生成部２０は、この同じサイズの集合も、２００個目の集合が追加された転置インデックスに追加する。そして、転置インデックス生成部２０は、サイズが異なる集合がでてきて初めて、その集合を新しい転置インデックスに追加する。
【００５１】
続いて、転置インデックス生成部２０は、各転置インデックスから、検索可能な集合のサイズの最小値βを特定する。そして、転置インデックス生成部２０は、特定した各βに、その昇順に、転置インデックスのIDを付与する。このとき、IDをiとし、各IDの転置インデックスに含まれる集合をDiとすると、各転置インデックスのサイズの幅と集合のサイズとの関係は、下記の数８によって表される。
【００５２】
【数８】
2014136810.tif 000010
【００５３】
上記数８より、例えば、図３に示すID=3の転置インデックスが検索対象として用いられるのであれば、サイズが6.0以上、8.0未満の集合が検索可能となる。従って、ID=3の転置インデックスには、サイズが6.8であるSID=1の集合が含まれている。
【００５４】
［ステップＡ２］
次に、ステップＡ１の終了後、不要転置インデックス同定部２１が、検索条件の集合のサイズと、類似度に設定された閾値とを用いて、類似度毎に定められた数式に従って、類似度が閾値以上となるために必要な、検索対象の集合のサイズの条件を求める。
【００５５】
続いて、不要転置インデックス同定部２１は、転置インデックスのうち、それに含まれる集合のサイズの最小値が条件を満たす転置インデックス以外、即ち、類似度が閾値以上になりえない転置インデックスを検索不要と同定する（ステップＡ２）。
【００５６】
ここで、図４を用いて、ステップＡ２について具体的に説明する。図４は、集合のサイズの範囲を求めるための数式の一例を示す図である。つまり、図４には、検索条件の集合Qと、閾値αとが与えられた場合の、各類似度がα以上になる、集合のサイズの範囲を求めるための数式が示されている。
【００５７】
図４に示された各数式の証明については、重複度の場合を除き、非特許文献１に開示された、整数への切り上げ、切り下げを用いない場合と同様であるので、本実施の形態１での説明は省略する。重複度であるOverlap(Q,D)、Overlap(D,Q)の証明は、以下の通りとなる。
【００５８】
まず、Overlap(Q,D)は、α以上になる場合、定義より、下記の数９の通りとなる。
【００５９】
【数９】
2014136810.tif 000011
【００６０】
また、上記の数９を変形すると、下記の数１０の通りとなる。下記の数１０における|D|の最大値は下記の数１１の通りとなる。
【００６１】
【数１０】
2014136810.tif 000012
【００６２】
【数１１】
2014136810.tif 000013
【００６３】
Overlap(D,Q)についてもほぼ同様で、定義より、下記の数１２の通りとなる。
【００６４】
【数１２】
2014136810.tif 000014
【００６５】
上記の数１２を変形すると下記の数１３の通りとなる。下記の数１３における|D|の最小値は下記の数１４の通りとなる。
【００６６】
【数１３】
2014136810.tif 000015
【００６７】
【数１４】
2014136810.tif 000016
【００６８】
例えば、検索条件の集合Q、そのサイズ|Q|、及び閾値αが与えられた時、本例ではジャッカード係数を対象としているため、閾値α以上となるためには、検索対象の集合Dのサイズは、α|Q|以上、且つ|Q|/α以下である必要がある。具体的には、検索条件の集合Qが、要素e、fからなり、閾値αが0.6の場合、|Q|は2.2となるため、サイズの最小値が1.32(=2.2×0.6）となり、最大値が3.667(≒2.2/0.6)となる。
【００６９】
ここで、図３に示した転置インデックスの下限βを参照すると、転置インデックスID１と転置インデックスID2とに含まれる集合のサイズは、β1(=0.5)≦|D|＜β3(=6.0)となり、この時点で最小値と最大値を包含している。このため、ID3以降の転置インデックスは検索不要であることが分かる。このように、不要転置インデックス同定部２１は、各転置インデックスのサイズの最小値を用いることで、検索不要な転置インデックスを同定する。
【００７０】
［ステップＡ３］
最後に、データ検索部２２は、同定された検索不要な転置インデックス以外の転置インデックスについて、検索条件の対象となる集合と、その要素を含む各集合との類似度を計算し、閾値以上の集合を結果として、出力装置４に出力する（ステップＡ３）。
【００７１】
例えば、上述した検索条件の集合Qは、要素e、fを含むため、データ検索部２２は、図３に示したIDが1の転置インデックスからは、SID=3などを検索する。また、データ検索部２２は、IDが2の転置インデックスからは、SID=10000などを検索する。そして、データ検索部２２は、このようにして取得した集合と、検索条件の集合との類似度を計算して、類似度が実際に閾値α以上となるデータを検索結果として出力することができる。
【００７２】
また、ステップＡ３において、データ検索部２２は、非特許文献１と同様に、τオーバラップ問題として検索を行なうことができる。即ち、データ検索部２２は、同定された転置インデックス以外の転置インデックス（以下「非同定転置インデックス」と表記する。）に含まれる集合それぞれ毎に、検索条件の集合の要素と共通する要素を特定し、特定した要素の前記重要度の和を計算する。そして、データ検索部２２は、計算した和の値が、類似度が閾値α以上となる場合と等価になる条件を満たす場合に、計算の対象となった非同定転置インデックスの集合を検索結果とする
【００７３】
具体的には、検索対象の集合のサイズ|D|、検索条件の集合のサイズ|Q|、閾値αが与えられた時に、集合Qと集合Dとで共通している要素の重要度の和が、図５に示す式によって計算されるτ以上になることが、集合Dと集合Qとの各類似度がα以上と等価であるとされる。この場合、各検索対象の集合のサイズ|D|の計算は、転置インデックスの生成時に一度行なわれば良く、更に、検索条件の集合のサイズ|Q|の計算も、一度行なわれれば良いため、毎回類似度を計算する必要がなくなり、計算効率の向上が図られる。図５は、類似度が閾値以上となる場合と等価であるとされる条件の一例を示す図である。
【００７４】
また、本実施の形態では、データ検索部２２は、非同定転置インデックスに含まれる集合それぞれについて順に、検索条件の集合の要素を一つずつ照合することができる。そして、この場合、データ検索部２２は、照合が未だ行われていない要素の重要度の和が、τ以上にならない（τ未満となる）場合は、転置インデックスに含まれる集合のうち、その時点までに照合が行われた集合のみを対象として、照合が未だ行われていない要素を用いた照合を実行する。そして、データ検索部２２は、その時点までに照合が行われた集合についてのみ、共通する要素の重要度の和を計算する。
【００７５】
つまり、本実施の形態１では、非特許文献１に開示されているように、検索条件の集合Qの未検索の要素の和がτ未満になった時点で、それ以降で初めて検索されるSIDの集合と集合Qとの共通要素の重要度の和がτ以上になれないという性質を利用することもできる。
【００７６】
具体的には、データ検索部２２は、各転置インデックスの集合のサイズの最小値βを|D|と見なし、その転置インデックス内の集合について最低限満たすべきτを計算する。次に、データ検索部２２は、検索条件の集合Qの未検索の要素の和がτ未満になったら、その時点までに検索されたSIDのみを候補として、残りの未検索の要素は、転置インデックスから取得したその要素のリストに対して、各SIDの2分探索で存在確認を行う。これによって、各要素を含む集合の数をnとした場合に、線形探索では計算量がO(n)となることに対し、2分探索による存在確認ではO(log n)となるため、効率化が可能となる。
【００７７】
なお、この2分探索に切り替えた後の各集合に対するτには、各SIDの集合のサイズが用いられることに注意する。また、効率よく検索条件の集合Qの未検索の要素の和がτ未満になることを確定させるため、データ検索部２２は、要素を重要度の降順に検索（照合）するのが好ましい。
【００７８】
［実施の形態１における効果］
このように、本実施の形態１では、転置インデックス生成部２０が検索対象の集合の数が少なくならないように各転置インデックスを作成する。また、不要転置インデックス同定部２１が、検索条件と各転置インデックスの集合のサイズの最小値とから、類似度が閾値以上の集合を検索する際に、検索不要な転置インデックスを同定する。そして、データ検索部２２が、検索不要な転置インデックス以外に対して検索を行う。このため、本実施の形態１によれば、検索条件の集合と同じサイズの集合が少ない場合でも、転置インデックスを参照する回数が総合的に少なくなるので、効率よく類似度が閾値以上となる全ての集合を検索できるようになる。
【００７９】
［プログラム］
本実施の形態におけるプログラムは、コンピュータに、図２に示すステップＡ１〜Ａ３を実行させるプログラムであれば良い。このプログラムをコンピュータにインストールし、実行することによって、本実施の形態における類似データ検索装置３０と類似データ検索方法とを実現することができる。この場合、コンピュータのＣＰＵ（Central Processing Unit）は、転置インデックス生成部２０、不要転置インデックス同定部２１、及びデータ検索部２２として機能し、処理を行なう。
【００８０】
（実施の形態２）
次に、本発明の実施の形態２における、類似データ検索装置、類似データ検索方法、及び類似データ検索用プログラムについて、図６〜図７を参照しながら説明する。
【００８１】
［装置構成］
最初に、本実施の形態２における類似データ検索装置の構成について図６を用いて説明する。図６は、本発明の実施の形態２における類似データ検索装置の構成を示すブロック図である。
【００８２】
図６に示すように、本実施の形態２においては、類似データ検索装置５は、以下の点で、実施の形態１において図１に示した類似データ検索装置２と異なっている。まず、本実施の形態２における類似データ検索装置５は、転置インデックス生成部２０、不要転置インデックス同定部２１、データ検索部２２に加えて、同義要素変換部２３を更に備えている。同義要素変換部２３は、検索対象の集合及び検索条件の集合に含まれる要素のうち、定められた同義要素の集合に属する要素を、同義要素の代表要素に変換する。
【００８３】
また、本実施の形態２では、類似データ検索装置５は、検索対象データ１０、要素重要度データ１１に加えて、同義要素データ１２も利用する。同義要素データ１２は、同義と考える要素を定義するデータであり、検索対象データ１０及び要素重要度データ１１と同様に、データ記憶装置１に格納されている。
【００８４】
具体的には、同義要素変換部２３は、検索対象データ１０、要素重要度データ１１、及び同義要素データ１２を読み込み、同義要素の集合を生成する。そして、同義要素変換部２３は、検索対象の集合と検索条件の集合とのそれぞれにおいて、各同義要素集合内に属する要素を、各同義要素集合の代表要素に置換し、置換後の各集合を、転置インデックス作成部２０に出力する。
【００８５】
[装置動作]
次に、本発明の実施の形態２における類似データ検索装置５の動作について図７を用いて説明する。図７は、本発明の実施の形態２における類似データ検索装置の動作を示すフロー図である。以下の説明においては、適宜図６を参酌する。また、本実施の形態２では、類似データ検索装置５を動作させることによって、類似データ検索方法が実施される。よって、本実施の形態２における類似データ検索方法の説明は、以下の類似データ検索装置の動作説明に代える。
【００８６】
［ステップＢ１］
最初に、図７に示すように、同義要素変換部２３は、同義要素データ、要素重要度データを読み出し、検索対象の集合及び検索条件の集合それぞれについて、同義要素の集合を作成する。
【００８７】
続いて、同義要素変換部２３は、各同義要素集合の代表要素を選出し、検索対象の集合及び検索条件の集合それぞれにおける、各同義要素集合に属する要素を、代表要素に置換する（ステップＢ１）。
【００８８】
ステップＢ１において、同義要素集合の作成は、要素をノードとし、同義と見なされる要素のペアに無向辺をひき、この場合に、各要素から連結成分で辿れるノードを同義要素とすることによって行なわれる。
【００８９】
また、代表要素としては、重要度が最大の要素、重要度が最小の要素、重要度が中央値の要素、要素が全順序である場合の最初の要素等のいずれかを用いることができる。なお、代表要素の選択方法は、特に限定されない。
【００９０】
［ステップＢ２〜Ｂ４］
次に、代表要素に変換済の検索対象の集合と、同じく代表要素に変換済の検索条件の集合とが用いられて、ステップＢ２〜Ｂ４が実行される。なお、ステップＢ２〜Ｂ４は、それぞれ、図２に示したステップＡ１〜Ａ３と同様のステップであり、これらと同様に実行され、最終的に検索結果が出力される。
【００９１】
［実施の形態２における効果］
以上のように、本実施の形態２では、同義要素変換部２３が、同義要素を代表要素に置換した上で、検索処理が実行される。このため、互いに異なる要素同士であっても、同義である場合は、同一視の要素とみなされて、類似データ検索が行なわれるので、検索精度が高められることになる。
【００９２】
（コンピュータ）
ここで、実施の形態１及び２におけるプログラムを実行することによって、類似データ検索装置を実現するコンピュータについて図８を用いて説明する。図８は、本発明の実施の形態１及び２における類似データ検索装置を実現するコンピュータの一例を示すブロック図である。
【００９３】
図８に示すように、コンピュータ１１０は、ＣＰＵ１１１と、メインメモリ１１２と、記憶装置１１３と、入力インターフェイス１１４と、表示コントローラ１１５と、データリーダ／ライタ１１６と、通信インターフェイス１１７とを備える。これらの各部は、バス１２１を介して、互いにデータ通信可能に接続される。
【００９４】
ＣＰＵ１１１は、記憶装置１１３に格納された、本実施の形態におけるプログラム（コード）をメインメモリ１１２に展開し、これらを所定順序で実行することにより、各種の演算を実施する。メインメモリ１１２は、典型的には、ＤＲＡＭ（Dynamic Random Access Memory）等の揮発性の記憶装置である。また、本実施の形態におけるプログラムは、コンピュータ読み取り可能な記録媒体１２０に格納された状態で提供される。なお、本実施の形態におけるプログラムは、通信インターフェイス１１７を介して接続されたインターネット上で流通するものであっても良い。
【００９５】
また、記憶装置１１３の具体例としては、ハードディスクドライブの他、フラッシュメモリ等の半導体記憶装置が挙げられる。入力インターフェイス１１４は、ＣＰＵ１１１と、キーボード及びマウスといった入力機器１１８との間のデータ伝送を仲介する。表示コントローラ１１５は、ディスプレイ装置１１９と接続され、ディスプレイ装置１１９での表示を制御する。
【００９６】
データリーダ／ライタ１１６は、ＣＰＵ１１１と記録媒体１２０との間のデータ伝送を仲介し、記録媒体１２０からのプログラムの読み出し、及びコンピュータ１１０における処理結果の記録媒体１２０への書き込みを実行する。通信インターフェイス１１７は、ＣＰＵ１１１と、他のコンピュータとの間のデータ伝送を仲介する。
【００９７】
また、記録媒体１２０の具体例としては、ＣＦ（Compact Flash（登録商標））及びＳＤ（Secure Digital）等の汎用的な半導体記憶デバイス、フレキシブルディスク（Flexible Disk）等の磁気記憶媒体、又はＣＤ−ＲＯＭ（Compact Disk Read Only Memory）などの光学記憶媒体が挙げられる。
【００９８】
上述した実施の形態の一部又は全部は、以下に記載する（付記１）〜（付記３０）によって表現することができるが、以下の記載に限定されるものではない。
【００９９】
（付記１）
検索対象となるデータ及び検索条件となるデータとして集合を用いて検索を行うための類似データ検索装置であって、
検索に使用する転置インデックスの生成のため、生成予定の各転置インデックスに含まれる検索対象の集合の数が設定個数以上になるように、前記生成予定の転置インデックス毎に、前記検索対象の集合のサイズの範囲を決定し、決定した前記サイズの範囲毎に、前記検索対象の集合を分けて、前記転置インデックスを生成する、転置インデックス生成部と、
検索条件の集合のサイズと、前記検索条件の集合と前記検索対象の集合との類似度に対して設定された閾値と、に基づいて、前記類似度が閾値以上となるために必要な、前記検索対象の集合のサイズの条件を求め、前記転置インデックスのうち、それに含まれる集合のサイズの最小値が前記条件を満たす転置インデックス以外を、検索不要な転置インデックスとして同定する、不要転置インデックス同定部と、
同定された前記検索不要な転置インデックス以外の転置インデックスに対して、前記検索条件の集合を適用して、検索を実行する、データ検索部と、
を備えることを特徴とする類似データ検索装置。
【０１００】
（付記２）
前記転置インデックス生成部が、前記検索対象の集合の総数を、設定された値で除算することによって、前記設定個数を算出し、算出した前記設定個数に基づいて、前記生成予定の転置インデックス毎に、前記検索対象の集合のサイズの範囲を決定する、付記１に記載の類似データ検索装置。
【０１０１】
（付記３）
前記転置インデックス生成部が、前記検索条件の集合が複数存在する場合に、前記データ検索部による検索にかかる時間の総和が小さくなるように、前記生成予定の各転置インデックスに含まれる検索対象の集合の最小数を決定する、付記１または２に記載の類似データ検索装置。
【０１０２】
（付記４）
前記不要転置インデックス同定部は、
前記検索条件の集合から前記検索対象の集合に対する重複度、前記検索対象の集合から前記検索条件の集合に対する重複度、ジャカード係数、ダイス係数、コサイン類似度のうち、いずれかによって規定される数式と、前記閾値とを用いて、前記条件を計算する、
付記１から３のいずれかに記載の類似データ検索装置。
【０１０３】
（付記５）
前記データ検索部が、同定された前記検索不要な転置インデックス以外の転置インデックスに含まれる集合の中から、前記検索条件の集合の要素を含む集合を特定し、特定した集合と前記検索条件の集合との前記類似度が前記閾値以上となる場合に、特定した集合を検索結果とする、
付記１〜４のいずれかに記載の類似データ検索装置。
【０１０４】
（付記６）
前記転置インデックス生成部が、更に、前記検索対象の集合に含まれる各要素に対して予め付与されている重要度を用いて、前記検索対象の集合それぞれのサイズを計算する、
付記１〜５のいずれかに記載の類似データ検索装置。
【０１０５】
（付記７）
前記類似度が、前記検索条件の集合から前記検索対象の集合に対する重複度、前記検索対象の集合から前記検索条件の集合に対する重複度、ジャカード係数、ダイス係数、コサイン類似度のうち、いずれかによって規定される数式を用いて計算されており、
前記データ検索部が、同定された前記検索不要な転置インデックス以外の転置インデックスに含まれる集合それぞれ毎に、前記検索条件の集合の要素と共通する要素を特定し、特定した要素の前記重要度の和を計算し、計算した和の値が、前記類似度が前記閾値以上となる場合と等価になる条件を満たす場合に、計算の対象となった前記集合を検索結果とする、
付記６に記載の類似データ検索装置。
【０１０６】
（付記８）
前記データ検索部が、
同定された前記検索不要な転置インデックス以外の転置インデックスに含まれる集合それぞれについて順に、前記検索条件の集合の要素を一つずつ照合し、
照合が未だ行われていない要素の前記重要度の和が、前記条件を満たさなくなった場合は、前記転置インデックスに含まれる集合のうち、その時点までに照合が行われた集合のみを対象として、前記照合が未だ行われていない要素を用いた照合を行い、
前記その時点までに照合が行われた集合についてのみ、前記共通する要素の前記重要度の和を計算する、
付記７に記載の類似データ検索装置。
【０１０７】
（付記９）
前記データ検索部が、重要度の降順に、前記検索条件の集合の要素を照合する、付記８に記載の類似データ検索装置。
【０１０８】
（付記１０）
前記検索対象の集合及び前記検索条件の集合に含まれる要素のうち、定められた同義要素の集合に属する要素を、前記同義要素の代表要素に変換する、同義要素変換部を、更に備えている、付記１から９のいずれかに記載の類似データ検索装置。
【０１０９】
（付記１１）
検索対象となるデータ及び検索条件となるデータとして集合を用いて検索を行うための方法であって、
（ａ）検索に使用する転置インデックスの生成のため、生成予定の各転置インデックスに含まれる検索対象の集合の数が設定個数以上になるように、前記生成予定の転置インデックス毎に、前記検索対象の集合のサイズの範囲を決定し、決定した前記サイズの範囲毎に、前記検索対象の集合を分けて、前記転置インデックスを生成する、ステップと、
（ｂ）検索条件の集合のサイズと、前記検索条件の集合と前記検索対象の集合との類似度に対して設定された閾値と、に基づいて、前記類似度が閾値以上となるために必要な、前記検索対象の集合のサイズの条件を求め、前記転置インデックスのうち、それに含まれる集合のサイズの最小値が前記条件を満たす転置インデックス以外を、検索不要な転置インデックスとして同定する、ステップと、
（ｃ）前記（ｂ）のステップで同定された前記検索不要な転置インデックス以外の転置インデックスに対して、前記検索条件の集合を適用して、検索を実行する、ステップと、
を有することを特徴とする類似データ検索方法。
【０１１０】
（付記１２）
前記（ａ）のステップで、前記検索対象の集合の総数を、設定された値で除算することによって、前記設定個数を算出し、算出した前記設定個数に基づいて、前記生成予定の転置インデックス毎に、前記検索対象の集合のサイズの範囲を決定する、付記１１に記載の類似データ検索方法。
【０１１１】
（付記１３）
前記（ａ）のステップで、前記検索条件の集合が複数存在する場合に、前記（ｃ）のステップによる検索にかかる時間の総和が小さくなるように、前記生成予定の各転置インデックスに含まれる検索対象の集合の最小数を決定する、付記１１または１２に記載の類似データ検索方法。
【０１１２】
（付記１４）
前記（ｂ）のステップで、前記検索条件の集合から前記検索対象の集合に対する重複度、前記検索対象の集合から前記検索条件の集合に対する重複度、ジャカード係数、ダイス係数、コサイン類似度のうち、いずれかによって規定される数式と、前記閾値とを用いて、前記条件を計算する、
付記１１から１３のいずれかに記載の類似データ検索方法。
【０１１３】
（付記１５）
前記（ｃ）のステップで、前記（ｂ）のステップで同定された前記検索不要な転置インデックス以外の転置インデックスに含まれる集合の中から、前記検索条件の集合の要素を含む集合を特定し、特定した集合と前記検索条件の集合との前記類似度が前記閾値以上となる場合に、特定した集合を検索結果とする、
付記１１〜１４のいずれかに記載の類似データ検索方法。
【０１１４】
（付記１６）
前記（ａ）のステップで、更に、前記検索対象の集合に含まれる各要素に対して予め付与されている重要度を用いて、前記検索対象の集合それぞれのサイズを計算する、
付記１１〜１５のいずれかに記載の類似データ検索方法。
【０１１５】
（付記１７）
前記類似度が、前記検索条件の集合から前記検索対象の集合に対する重複度、前記検索対象の集合から前記検索条件の集合に対する重複度、ジャカード係数、ダイス係数、コサイン類似度のうち、いずれかによって規定される数式を用いて計算されており、
前記（ｃ）のステップで、前記（ｂ）のステップで同定された前記検索不要な転置インデックス以外の転置インデックスに含まれる集合それぞれ毎に、前記検索条件の集合の要素と共通する要素を特定し、特定した要素の前記重要度の和を計算し、計算した和の値が、前記類似度が前記閾値以上となる場合と等価になる条件を満たす場合に、計算の対象となった前記集合を検索結果とする、
付記１６に記載の類似データ検索方法。
【０１１６】
（付記１８）
前記（ｃ）のステップで、
同定された前記検索不要な転置インデックス以外の転置インデックスに含まれる集合それぞれについて順に、前記検索条件の集合の要素を一つずつ照合し、
照合が未だ行われていない要素の前記重要度の和が、前記条件を満たさなくなった場合は、前記転置インデックスに含まれる集合のうち、その時点までに照合が行われた集合のみを対象として、前記照合が未だ行われていない要素を用いた照合を行い、
前記その時点までに照合が行われた集合についてのみ、前記共通する要素の前記重要度の和を計算する、
付記１７に記載の類似データ検索方法。
【０１１７】
（付記１９）
前記（ｃ）のステップで、重要度の降順に、前記検索条件の集合の要素を照合する、付記１８に記載の類似データ検索方法。
【０１１８】
（付記２０）
（ｄ）前記検索対象の集合及び前記検索条件の集合に含まれる要素のうち、定められた同義要素の集合に属する要素を、前記同義要素の代表要素に変換する、ステップを更に有する、付記１１から１９のいずれかに記載の類似データ検索方法。
【０１１９】
（付記２１）
コンピュータによって、検索対象となるデータ及び検索条件となるデータとして集合を用いて検索を行うためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記コンピュータに、
（ａ）検索に使用する転置インデックスの生成のため、生成予定の各転置インデックスに含まれる検索対象の集合の数が設定個数以上になるように、前記生成予定の転置インデックス毎に、前記検索対象の集合のサイズの範囲を決定し、決定した前記サイズの範囲毎に、前記検索対象の集合を分けて、前記転置インデックスを生成する、ステップと、
（ｂ）検索条件の集合のサイズと、前記検索条件の集合と前記検索対象の集合との類似度に対して設定された閾値と、に基づいて、前記類似度が閾値以上となるために必要な、前記検索対象の集合のサイズの条件を求め、前記転置インデックスのうち、それに含まれる集合のサイズの最小値が前記条件を満たす転置インデックス以外を、検索不要な転置インデックスとして同定する、ステップと、
（ｃ）前記（ｂ）のステップで同定された前記検索不要な転置インデックス以外の転置インデックスに対して、前記検索条件の集合を適用して、検索を実行する、ステップと、
を実行させる命令を含む、プログラムを記録しているコンピュータ読み取り可能な記録媒体。
【０１２０】
（付記２２）
前記（ａ）のステップで、前記検索対象の集合の総数を、設定された値で除算することによって、前記設定個数を算出し、算出した前記設定個数に基づいて、前記生成予定の転置インデックス毎に、前記検索対象の集合のサイズの範囲を決定する、付記２１に記載のコンピュータ読み取り可能な記録媒体。
【０１２１】
（付記２３）
前記（ａ）のステップで、前記検索条件の集合が複数存在する場合に、前記（ｃ）のステップによる検索にかかる時間の総和が小さくなるように、前記生成予定の各転置インデックスに含まれる検索対象の集合の最小数を決定する、付記２１または２２に記載のコンピュータ読み取り可能な記録媒体。
【０１２２】
（付記２４）
前記（ｂ）のステップで、前記検索条件の集合から前記検索対象の集合に対する重複度、前記検索対象の集合から前記検索条件の集合に対する重複度、ジャカード係数、ダイス係数、コサイン類似度のうち、いずれかによって規定される数式と、前記閾値とを用いて、前記条件を計算する、
付記２１から２３のいずれかに記載のコンピュータ読み取り可能な記録媒体。
【０１２３】
（付記２５）
前記（ｃ）のステップで、前記（ｂ）のステップで同定された前記検索不要な転置インデックス以外の転置インデックスに含まれる集合の中から、前記検索条件の集合の要素を含む集合を特定し、特定した集合と前記検索条件の集合との前記類似度が前記閾値以上となる場合に、特定した集合を検索結果とする、
付記２１〜２４のいずれかに記載のコンピュータ読み取り可能な記録媒体。
【０１２４】
（付記２６）
前記（ａ）のステップで、更に、前記検索対象の集合に含まれる各要素に対して予め付与されている重要度を用いて、前記検索対象の集合それぞれのサイズを計算する、
付記２１〜２５のいずれかに記載のコンピュータ読み取り可能な記録媒体。
【０１２５】
（付記２７）
前記類似度が、前記検索条件の集合から前記検索対象の集合に対する重複度、前記検索対象の集合から前記検索条件の集合に対する重複度、ジャカード係数、ダイス係数、コサイン類似度のうち、いずれかによって規定される数式を用いて計算されており、
前記（ｃ）のステップで、前記（ｂ）のステップで同定された前記検索不要な転置インデックス以外の転置インデックスに含まれる集合それぞれ毎に、前記検索条件の集合の要素と共通する要素を特定し、特定した要素の前記重要度の和を計算し、計算した和の値が、前記類似度が前記閾値以上となる場合と等価になる条件を満たす場合に、計算の対象となった前記集合を検索結果とする、
付記２６に記載のコンピュータ読み取り可能な記録媒体。
【０１２６】
（付記２８）
前記（ｃ）のステップで、
同定された前記検索不要な転置インデックス以外の転置インデックスに含まれる集合それぞれについて順に、前記検索条件の集合の要素を一つずつ照合し、
照合が未だ行われていない要素の前記重要度の和が、前記条件を満たさなくなった場合は、前記転置インデックスに含まれる集合のうち、その時点までに照合が行われた集合のみを対象として、前記照合が未だ行われていない要素を用いた照合を行い、
前記その時点までに照合が行われた集合についてのみ、前記共通する要素の前記重要度の和を計算する、
付記２７に記載のコンピュータ読み取り可能な記録媒体。
【０１２７】
（付記２９）
前記（ｃ）のステップで、重要度の降順に、前記検索条件の集合の要素を照合する、付記２８に記載のコンピュータ読み取り可能な記録媒体。
【０１２８】
（付記３０）
前記プログラムが、更に、前記コンピュータに、
（ｄ）前記検索対象の集合及び前記検索条件の集合に含まれる要素のうち、定められた同義要素の集合に属する要素を、前記同義要素の代表要素に変換する、ステップを実行させる命令を含む、付記２１から２９のいずれかに記載のコンピュータ読み取り可能な記録媒体。
【０１２９】
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記実施の形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１３０】
この出願は、２０１３年３月７日に出願された日本出願特願２０１３−０４５５６６を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１３１】
以上のように本発明によれば、検索対象となるデータ中に同じサイズの集合が少ない場合であっても、転置インデックスにおける検索回数の増加による検索効率の低下を抑制することができる。本発明は、重複データを削除するための重複データの照合処理及び類似データをまとめるための処理を行なうデータクラスタリングシステム、辞書エントリとのソフトマッチングによって辞書ソフト照合を行なうシステム、等に有用である。
【符号の説明】
【０１３２】
１  データ記憶装置
２  類似データ検索装置（実施の形態１）
３  入力装置
４  出力装置
５  類似データ検索装置（実施の形態２）
１０  検索対象データ
１１  要素重要度データ
１２  同義要素データ
２０  転置インデックス生成部
２１  検索不要転置インデックス同定部
２２  データ検索部
２３  同義要素変換部
３０  類似データ検索システム
１１０  コンピュータ
１１１  ＣＰＵ
１１２  メインメモリ
１１３  記憶装置
１１４  入力インターフェイス
１１５  表示コントローラ
１１６  データリーダ／ライタ
１１７  通信インターフェイス
１１８  入力機器
１１９  ディスプレイ装置
１２０  記録媒体
１２１  バス
【図１】
2014136810.tif 000017
【図２】
2014136810.tif 000018
【図３】
2014136810.tif 000019
【図４】
2014136810.tif 000020
【図５】
2014136810.tif 000021
【図６】
2014136810.tif 000022
【図７】
2014136810.tif 000023
【図８】
2014136810.tif 000024
【手続補正書】
【提出日】平成27年9月4日(2015.9.4)
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項７
【補正方法】変更
【補正の内容】
【請求項７】
前記類似度が、前記検索条件の集合から前記検索対象の集合に対する重複度、前記検索対象の集合から前記検索条件の集合に対する重複度、ジャカード係数、ダイス係数、コサイン類似度のうち、いずれかによって規定される数式を用いて計算されており、
前記データ検索部が、
同定された前記検索不要な転置インデックス以外の転置インデックスに含まれる集合それぞれについて順に、前記検索条件の集合の要素を、重要度の降順に、一つずつ照合し、
照合が未だ行われていない要素の前記重要度の和が、前記条件を満たさなくなった場合は、前記転置インデックスに含まれる集合のうち、その時点までに照合が行われた集合のみを対象として、前記照合が未だ行われていない要素を用いた照合を行い、
前記その時点までに照合が行われた集合についてのみ、前記検索条件の集合の要素と共通する要素の前記重要度の和を計算し、
計算した和の値が、前記類似度が前記閾値以上となる場合と等価になる条件を満たす場合に、計算の対象となった前記集合を検索結果とする、
請求項１から６のいずれかに記載の類似データ検索装置。
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】図１
【補正方法】変更
【補正の内容】
【図１】
2014136810.tif 000025
【手続補正４】
【補正対象書類名】図面
【補正対象項目名】図６
【補正方法】変更
【補正の内容】
【図６】
2014136810.tif 000026
【国際調査報告】
2014136810.tif 000027
2014136810.tif 000028
2014136810.tif 000029