(57)【要約】データベースにおける要素を識別する複数バイト識別子の従来のバイト順序の再順序付け（１３０）に基づいて大きいデータベース（１９０）の検索を効果的に実行する方法及びシステムを提供する。再順序付け（１３０）は、データベースにおける識別子の非常に均一な分布を与えるように選択される。データベースは、データベースにおける要素の識別子を生成する再順序付けされたバイトに基づいて構成及び／又はソーティング（１４０，３４０）される。不均一に分布した識別子の再順序付けされたバイトの順序の検索を効果的に実行する（１５０，３５０）ことにより、より速く検出されるミスマッチの尤度が殆どの場合に増加することが見込まれ、それ故、マッチングを見つける速度が改善され、又はデータベースの検索を実行し尽くすことができる。
2006511894.tif 000002
【特許請求の範囲】
【請求項１】
データベースにおいて要素を識別するために複数のデータユニットの署名を用いる該データベースを検索する方法であって：
複数のデータユニットを有する検索署名を生成する段階であって、複数のデータユニットは最も重要なデータユニットから最も重要でないデータユニットまでの第１順序を有する、段階； 
前記の複数のデータユニットの署名の選択署名を決定する段階；並びに
差が検索されるまで又は前記複数のデータユニットのデータユニット全てが比較されるまで、シーケンシャルなデータユニットの第２順序を用いて、前記検索署名の複数のデータユニットの各々のデータユニットを対応する前記選択署名のデータユニットとシーケンシャルに比較する段階；
を有する方法であり、
前記第２順序は前記第１順序とは異なる；
ことを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、前記データベースは前記第２順序に基づいてソーティングされる、ことを特徴とする方法。
【請求項３】
請求項１に記載の方法であって：
前記第２順序に基づいて前記データベースをソーティングする段階；
を更に有する、ことを特徴とする方法。
【請求項４】
請求項１に記載の方法であって、前記第２順序は前記第１順序の逆に対応する、ことを特徴とする方法。
【請求項５】
請求項１に記載の方法であって、前記検索署名は、コンテンツであって：
音声データベース；及び
映像データベース；
のコンテンツの少なくとも１つに基づいている、ことを特徴とする方法。
【請求項６】
請求項１に記載の方法であって、前記データベースは、前記の複数のデータユニットの署名により識別される前記要素に関連する補助的情報を又、有し、前記補助的情報は：
前記要素のタイトル；
前記要素の作者；
前記要素の実行者；
前記要素の監督；及び
前記要素のプロデューサ；
の少なくとも１つを有する、ことを特徴とする方法。
【請求項７】
データベースにおいて要素を識別するために複数のデータユニットの署名を用いる該データベースを検索する方法であって：
複数のデータユニットを有する検索署名を生成する段階であって、複数のデータユニットは最も重要なデータユニットから最も重要でないデータユニットまでの第１順序を有する、段階；
前記第１順序とは異なる第２順序に基づく前記検索署名を再順序付けする段階；
前記の複数のデータユニットの署名の選択署名を決定する段階；並びに
差が検索されるまで又は前記複数のデータユニットのデータユニット全てが比較されるまで、シーケンシャルなデータユニットの前記第１順序を用いて、前記検索署名の複数のデータユニットの各々のデータユニットを対応する前記選択署名のデータユニットとシーケンシャルに比較する段階；
を有することを特徴とする方法。
【請求項８】
請求項７に記載の方法であって：
前記の複数のデータユニットの署名は前記第２順序に基づいて再順序付けされ；
前記データベースは前記第１順序に基づいてソーティングされる；
ことを特徴とする方法。
【請求項９】
請求項７に記載の方法であって：
前記第２順序に基づいて前記の複数のデータユニットの署名のデータユニットを再順序付けする段階；及び
前記第１順序に基づいて前記データベースをソーティングする段階；
を更に有する、ことを特徴とする方法。
【請求項１０】
請求項７に記載の方法であって、前記第２順序は前記第１順序の逆に対応する、ことを特徴とする方法。
【請求項１１】
請求項７に記載の方法であって、前記検索署名は、コンテンツであって：
音声データベース；及び
映像データベース；
のコンテンツの少なくとも１つに基づいている、ことを特徴とする方法。
【請求項１２】
請求項７に記載の方法であって、前記データベースは、前記の複数のデータユニットの署名により識別される前記要素に関連する補助的情報を又、有し、前記補助的情報は：
前記要素のタイトル；
前記要素の作者；
前記要素の実行者；
前記要素の監督；及び
前記要素のプロデューサ；
の少なくとも１つを有する、ことを特徴とする方法。
【請求項１３】
請求項７に記載の方法であって：
ｆｉｒｓｔ−ｉｎｆｉｒｓｔ−ｏｕｔ法を用いて前記データベースにおいて前記検索署名をソーティングする段階；
を更に有する、ことを特徴とする方法。
【請求項１４】
検索システムであって：
最も重要なデータユニットから最も重要でないデータユニットへの順序に対応するデータユニットの第１順序を有する検索署名を生成する署名生成器；並びに
前記検索署名に対応する選択署名のためのデータベースを検索する検索エンジン；
を有する検索システムであり、
前記検索エンジンは、前記第１順序とは異なるデータユニットの第２順序に基づいて、前記選択署名の対応するデータユニットと前記検索署名の各々のデータユニットをシーケンシャルに比較する；
ことを特徴とする検索システム。
【請求項１５】
請求項１４に記載の検索システムであって、前記データベースは前記第２順序に基づいてソーティングされる、ことを特徴とする検索システム。
【請求項１６】
請求項１４に記載の検索システムであって：
前記第２順序に基づいて前記データベースをソーティングするソータ；
を更に有する、ことを特徴とする検索システム。
【請求項１７】
請求項１４に記載の検索システムであって、前記第２順序は前記第１順序の逆に対応する、ことを特徴とする検索システム。
【請求項１８】
請求項１４に記載の検索システムであって、前記検索署名は、コンテンツであって：
音声データベース；及び
映像データベース；
のコンテンツの少なくとも１つに基づいている、ことを特徴とする検索システム。
【請求項１９】
請求項１４に記載の検索システムであって、前記データベースは、前記の複数のデータユニットの署名により識別される前記要素に関連する補助的情報を又、有し、前記補助的情報は：
前記要素のタイトル；
前記要素の作者；
前記要素の実行者；
前記要素の監督；及び
前記要素のプロデューサ；
の少なくとも１つを有する、ことを特徴とする検索システム。
【請求項２０】
検索システムであって：
最も重要なデータユニットから最も重要でないデータユニットへの順序に対応するデータユニットの第１順序を有する検索署名を生成する署名生成器；
前記第１順序とは異なるデータユニットの第２順序に基づいて、前記選択署名を再順序付けするデータユニット順序付け器；並びに
前記検索署名に対応する選択署名のためのデータベースを検索する検索エンジン；
を有する検索システムであり、
前記検索エンジンは、前記第１順序に基づいて、対応するデータユニットと前記検索署名の各々のデータユニットをシーケンシャルに比較する；
ことを特徴とする検索システム。
【請求項２１】
請求項２０に記載の検索システムであって：
前記選択署名のデータユニットは前記第２順序に基づいて再順序付けされ；
前記データベースは前記第１第２順序に基づいてソーティングされる；
ことを特徴とする検索システム。
【請求項２２】
請求項２０に記載の検索システムであって：
前記データユニットは、前記第２順序に基づいて前記データベースにおける署名のデータユニットを更に再順序付けし；そして
該システムは、前記第１順序に基づいて前記データベースをソーティングするソータを
を更に有する；
ことを特徴とする検索システム。
【請求項２３】
請求項２０に記載の検索システムであって、前記第２順序は前記第１順序の逆に対応する、ことを特徴とする検索システム。
【請求項２４】
請求項２０に記載の検索システムであって、前記検索署名は、コンテンツであって：
音声データベース；及び
映像データベース；
のコンテンツの少なくとも１つに基づいている、ことを特徴とする検索システム。
【請求項２５】
請求項２０に記載の検索システムであって、前記データベースは、前記の複数のデータユニットの署名により識別される前記要素に関連する補助的情報を又、有し、前記補助的情報は：
前記要素のタイトル；
前記要素の作者；
前記要素の実行者；
前記要素の監督；及び
前記要素のプロデューサ；
の少なくとも１つを有する、ことを特徴とする検索システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、消費者向け電子機器の分野に関し、特に、電子指紋の効率的な検索を容易にする方法及びシステムに関する。
【背景技術】
【０００２】
Ｇｅｏｆｆｒｅｙ  Ｂ．Ｒｈｏａｄｓ及びＫｅｎｎｅｔｈ  Ｌ．Ｌｅｖｙにより２００１年５月１４日に出願された、“ＣＯＮＴＥＮＴ  ＩＤＥＮＴＩＦＩＥＲＳ  ＴＲＩＧＧＥＲＩＮＧ  ＣＯＲＲＥＳＰＯＮＤＩＮＧ  ＲＥＳＰＯＮＳＥＳ”と題された、米国特許出願公開第２００２／００３２８６４Ａ１号明細書において、音声又は映像ファイルのようなデータセットのコンテンツに基づいて１つ又はそれ以上の“指紋”を生成するために一般に使用される種々の技術について紹介しており、この文献の援用により本発明の説明を一部代替する。データセットの指紋は、データセットのタイトル、演奏アーチスト、作曲者、監督等の識別のような、データセットに関連する補助的情報にアクセスするために、通常、使用される。更に、データセットの指紋は、そのようなアクセスに関連するデータセットへのアクセス権及び／又はアクセス料金を確認するために使用されることが可能である。データセットのコンテンツに基づく、データセットの識別子の他の使用は、当該技術分野において一般的である。
【０００３】
音声及び映像記録のようなエンターテインメント素材に関連する一般使用の指紋は、記録を一意に識別することが意図されており、それ故、実質的な長さを有する。例えば、専門家向け／一般消費者向け音声記録の署名のための１２８バイトのフォーマットは一般的である。膨大な数のそのような署名のデータベースは、消費者向け音声記録を一意に識別するために用いることが期待されており、大量のデータベースにおける大量の識別子に対する高効率な検索技術が要望されている。
【０００４】
指紋検索のタスクを更に複雑にしていることには、指紋とデータセットとの間の一対一対応が存在しないことがあり得る。指紋は、データセットのいずれかのコンテンツに基づいており、データセットの１つ又はそれ以上の選択されたセグメントに基づいている可能性がある。指紋はデータセットのコンテンツに基づいているため、指紋を得るためのデータセットのサンプリングは、同じデータセットに対する異なる指紋を生成し得る。現在、決定された指紋との適合性を理解するための指紋のデータベースの検索は、データセットの代替のサンプルに基づいて、データベースを通しての複数の検索及び／又は同じデータベースに対して複数の指紋を有するデータベースを通しての検索をしばしば必要とする。
【０００５】
例えば、楽曲のデータベースと、同じ楽曲に対して１０個の異なる指紋の平均を与える署名生成スキームとについて考察する。データベースは、各々の楽曲に対して１０個の最も高頻度で現れる指紋を含むように構成されることができる、又は、そのデータベースは、１つの最も可能性のある指紋を含むように構成されることが可能である。“検索”署名を生成するために、尚も未知のデータベースがサンプリングされるとき、その特定の楽曲がデータベースに含まれているか又は、その楽曲はデータベースに含まれているが、特定の検索署名はその楽曲に対するデータベースにおける署名の１つではないかのどちらかのために、その署名はデータベースにおける署名にマッチングし得、又はマッチングし得ない。マッチングが見つけられたとき、代表的には、新しいサンプルが得られ、新しい検索署名が生成される場合、この新しい署名が、マッチングに対してデータベースを検索するために用いられる。データベースにおいて記憶されている楽曲に対する１０個の最も頻度高く現れる指紋を得ることにより、即座に見つけられるマッチングの尤度は増加するが、又、記憶されている多くの署名のように１０回まで検索署名を比較する必要がある。楽曲当たり１つの署名のみを記憶することにより、各々の検索署名に対して検索時間とデータベースのサイズを減少させることができるが、取得された異なる署名を用いて複数の検索を実行する必要があるという尤度は増加する。
【０００６】
同じ楽曲に対応する複数の署名の尤度のために、高効率の検索技術に対する要請が、比較的小さいサイズのデータベースに対してさえ存在し、大きいサイズのデータベースに対して特に重要である。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明の目的は、データベースにおける要素の大量の識別子を有する大きいサイズのデータベースにおける高効率な検索を容易にする方法及びシステムを提供することである。更に、本発明の目的は、データベースを高効率に検索するためにデータベースにおける要素の大量の識別子を有する大きいサイズのデータベースを構成する方法及びシステムを提供することである。
【課題を解決するための手段】
【０００８】
それらの目的及び他の目的は、データベースにおける要素を識別する複数バイトの識別子の従来のバイトオーダーの記録に基づく、大きいサイズのデータベースの検索の効果を発揮する方法及びシステムを提供することにより達成される。データベースにおける要素の識別子を構成する記録されたバイトに基づいて、データベースは構成及び／又は記憶される。均一に分布されている識別子の記録されたバイトオーダーの検索の効果を発揮することにより、ミスマッチングをより速く検出する尤度を、殆どの状態で増加させることが見込まれ、それ故、マッチングを見つける速度及びデータベースの無駄な検索が改善される。
【発明を実施するための最良の形態】
【０００９】
本発明は、データベースのコンテンツから導き出される典型的な大きい署名は署名のバイト間のデータ値の均一な分布を示さないという観測を前提としている。一般に、例えば、大きい署名の値は“クラスター化”を示し、特定の“タイプ”のデータベースは小さい署名を示し、大きい署名の値は、データベースの各々の“タイプ”の署名値に関してクラスター化される。楽曲のデータベースにおいては、例えば、ロマンチックなバラードは、一般に、ヘビーメタルの演奏とは実質的に異なる、より小さい署名を有し、ヘビーメタルの演奏は、ワルツより小さい署名とは実質的に異なる小さい署名を示す、等等である。更に、データベースにおいて同じ要素に対して複数の署名を与えるシステムにおいては、同じ要素に対する異なる署名は、類似する署名に関して、しばしば緻密にクラスター化される。
【００１０】
データベースにおける要素の比較的小さいサイズを有するデータベースを検索する検索システムにおいては、しかしながら、検索効率は、識別子の値の分布により影響を受ける。下に詳細に説明するように、大きいサイズの識別子を有するデータベースの検索効率は、特に、識別子のクラスター化された分布により、そして、特に、データベースに記憶された順序でそれらのクラスター化された識別子が記憶されている場合に影響を受ける。
【００１１】
データベースにおける要素を識別するために１２８バイトの署名を用いるデータベースの検索について考察することにし、要素の識別子を昇順化又は降順化することにより、データベースにおけるそれらの要素を従来の方式で記憶することを仮定する。従来、１２８バイトの検索署名の最も重要なバイト又はワードは、データベースにおける選択署名の対応する最も重要なバイトと比較される。バイナリサーチにおいて、選択署名は、典型的には、データベースの中央の署名である。
【００１２】
参照を簡略化するために、以下、用語‘バイト’は、‘データユニット’に対するパラダイムとして用いる。当業者は、用語‘バイト’、‘ワード’、‘ダブルワード’等は単に便宜的なことばであり、特定のデータユニットを形成するビット数の同一性がないことが分かっているであろう。１つのコンテキストにおける３２ビットの‘ダブルワード’は、他のコンテキストにおいては、３２ビットの‘ワード’であることは、まさに、１つのコンテキストにおける１６ビットのバイトが他のコンテキストにおける１６ビットのワードと同等であることと同様である。
【００１３】
それらのバイトがマッチング値を有する場合、検索署名の２番目に重要なバイトとデータベースにおける第１署名とが比較され、次いで、３番目に重要なバイト、等、が順次比較される。最も重要なバイト（ＭＳＢ）から最も重要でないバイト（ＬＳＢ）への進行が、下で説明するように、比較のためにデータベースにおいて次に選択される署名を決定するためにＭＳＢからＬＳＢまでの進行における第１ミスマッチが用いられるため、署名が昇順又は降順に記憶されているかどうかに拘らず、実行される。
【００１４】
対応するバイトがマッチングしない場合、バイト値の匹敵する大きさが、検索署名との比較に対して、データベースにおいて次に選択される署名を決定するために用いられる。例えば、昇順のデータベースのバイナリサーチを用いて、ミスマッチ検索のバイト又はワードが選択された署名における対応するバイト又はワードより大きい場合、データベースにおいて次に選択される署名は、現在の選択署名の半分上に位置している署名であり、ここで、“半分”はデータベースにおける有効な選択署名の前の領域の半分として定義している。降順のデータベースにおいては、次に選択された署名は、現在の選択署名の半分下である署名である。
【００１５】
新しい選択署名が与えられる場合、上記のバイト毎の比較が、他のミスマッチが検出されるまで、又は、検索署名のバイト全てが選択署名のバイト全てとマッチングするまで、実行される。ミスマッチが検出される場合、有効な選択署名の領域が０であって、その０のポイントにおいて検索署名に対してデータベースにおいてマッチングが存在しない０に減少されるまで、上記の処理が継続される。
【００１６】
データベースにおける各々の選択署名に対して、検索署名とのバイト毎の比較はが、ミスマッチが検索されるまで、又は、全てのバイトがマッチングするまで、実行される。それ故、各々の選択署名における平均“ドウェル時間”は、
（ミスマッチを検出する平均バイト数）＊（１−Ｐ（マッチング））＋（全バイト数）＊Ｐ（マッチング）
に比例し、ここで、Ｐ（マッチング）は、検索署名が選択署名とマッチングする尤度である。
【００１７】
署名の十分に分布されたポピュレーションにおいて、ミスマッチを検出するための平均バイト数は検索署名の値とは関係していない。しかしながら、クラスター化分布によりパラメータがどのように影響を与えられるかについて考察する。定義によれば、類似する値の署名の“クラスター”は、同様の最も重要なバイト値を有する署名を有する。‘非常に密’なクラスターは、例えば、最も重要でないバイトの値のみだけ異なる署名を有することが可能である。‘広い’クラスターは、比較的少ない、最も重要でないバイトの値のみだけ異なる署名を有することが可能である。代替として考えるに、署名のクラスター化分布においては、最も重要なバイトにおいて異なる署名は異なるクラスターにある。
【００１８】
検索署名がランダムに分布した値である場合、マッチングがクラスター化分布のデータベースに存在するか否かを決定するための時間は、検索署名がクラスターの１つの中にあるかどうかに依存する。
【００１９】
署名がクラスター内にある場合、この検索署名の最も重要なバイトはいずれのクラスターの最も重要なバイトとマッチングする可能性がないため、データベースにおける各々の選択署名とのミスマッチは‘速く’示され、ミスマッチを検出するための平均バイト数は比較的小さい。
【００２０】
他方、署名がクラスター内にある場合、ミスマッチが存在することを決定するための時間は増加することが見込まれ、それは、検索署名が同じクラスターにおいて署名を選択するために比較されるとき、クラスターを検出する、マッチングする最も重要なバイトの数に対応して、ミスマッチを検出するための平均バイト数は比較的大きくなるためである。上記の例の１２８バイトの音声素材の署名において、ロマンチックなバラードが、署名の同じ上位の６０バイトを示し（各々のロマンチックなバラード間を区別するために残り６８バイト、又は２５６６８の異なる値を残す）、検索署名がロマンチックなバラードから導き出される場合、ロマンチックなバラードのクラスターにおける各々の選択署名に対するミスマッチを検出するための平均バイト数は６０バイトより大きくなる。同様の方法で、同じ楽曲に対応する複数の署名が最下位のオーダーの２バイトの値のみだけ異なる場合、ミスマッチを検出するための平均バイト数は１２６バイトより大きい。
【００２１】
従って、検索署名がランダム値である場合、その検索署名は、その値がクラスター内にないとき、ときどき比較的短い検索時間を示し、そして、その値がクラスター内にあるとき、ときどき比較的長い検索時間を示す。しかしながら、殆どの場合、検索署名は、データベースを作成するために用いられる同じポピュレーションから取り出されることに留意されたい。即ち、検索署名は、一般に、データベースにおける署名のクラスター内にある。音声エンターテインメントにおいては、非常に稀な場合を除いて、知られていない楽曲の署名は、楽曲のデータベースにおける他の楽曲全てと非常に異なっている。更に、典型的な環境においては、ユーザは、ユーザが興味をもっている楽曲に基づいて、楽曲のデータベースが増加するように作成することが可能である。そのようなデータベースはクラスター化された署名を有する可能性が非常に高く、そして、ユーザの音楽における趣味が変化し、新しいクラスターが形成されるまで、そのデータベースへのクエリは類似する特徴を示す楽曲に基づく可能性が高い。
【００２２】
本発明に従って、大きいサイズの署名の比較が、署名のクラスターに実質的に依存しない順序で実行される。好適な実施形態においては、大きいサイズの署名のデータベースは、署名の値のより均一な分布を効果的にするバイトオーダーで構成される。例の構造においては、データベースは最も重要でないバイトに基づいて記憶され、次に、２番目に重要でないバイトが記憶され、等等、繰り返される。逆バイトオーダー等に基づく順序付けは、降順の値に基づく順序付けと同等ではない。各々の数字がバイト値に対応している、３つの署名１２３、６５４及び２７１が与えられる場合、逆バイトオーダーの昇順にソートされた順序は、最も重要でない数字の各々は昇順にあるため、２７１、１２３、６５４になる。
【００２３】
この例のデータベースによる検索は、データベースにおける各々の選択署名に対する検索署名の、最も重要でないバイトの最も重要なバイトに対する比較に基づいて効果を発揮する。例えば、検索署名が７２３であり、上記の例から、選択署名が１２３である場合、両方の署名において最も重要でない数字‘３’が第１に比較され、続いて、両方の署名において次に重要でない数字‘２’が第２に比較され、続いて、検索署名において３番目に重要でない数字‘７’が、そして選択署名における‘１’が最後に比較される。‘７’と‘１’との間の非マッチングと、‘７’が‘１’より大きいこと以外に何もないこととを検出するとき、上記の例における比較に対する次の選択署名は６５４であり、検索署名及び選択署名の最も重要でない数字、即ち‘３’及び‘４’から開始する。
【００２４】
大きいサイズの署名の最も重要でないバイトが不均一に分布している場合、ミスマッチを検出するための平均バイト数は検索署名の値に依存せず、データベースにおける署名のいずれの従来通りに規定されたクラスター化にも依存しないことに留意されたい。又、検索署名が、最も重要なバイトに対する最も重要でない署名の順序に関して署名の同じポピュレーションから取り出される場合、従来通りに規定されたクラスターにおける検索署名の位置は、この逆バイト順序のデータベースにおけるミスマッチを検出するために必要な平均バイト数に影響しないことに留意されたい。
【００２５】
最も重要でないバイトから最も重要なバイトまでの順序付けは実行することが最も容易であることが見込まれ、署名の均一な分布を生成する可能性が最も高いようにみえるが、当業者は、従来の、最も重要でないバイトに対する最も重要なバイトの順序付けより均一な分布を与える、いずれの他の順序付けを用いることができることを認識しているであろう。例えば、特定の署名作成スキームが最も重要でないバイトの値の不均一分布を生成することと、署名の中央バイトにおける上位から下位への循環順序付けの開始に基づく順序付けがより均一な分布を生成するために用いられることが可能であることとが分かる。同様に、第３のバイト値全てに基づく順序付け、上位順序のバイトと下位順序のバイトを交互にすることに基づく順序付け等のような、他の従来の順序付けスキームを用いることが可能である。
【００２６】
図１は、コンテンツ素材１１０を識別するための署名生成器１２０により生成される署名の、従来のＭＳＢからＬＳＢへの順序と異なる順序１３０に基づいて、署名の検索の効果を発揮させる検索システム１００の例示としてのブロック図を示している。順序１３０は、データベース１９０における署名をソーティングする１４０ために用いられる。署名１２３、６５４及び２７１と、従来のＭＳＢからＬＳＢへの順序に対するシンボルａ−ｂ−ｃとを用いる場合であって、ここで、ａはＭＳＢである場合、ｃ−ｂ−ａの順序１３０は署名２７１、１２３、６５４のソーティングを与え、ｂ−ｃ−ａの順序１３０は１２３、６５４、２７１のソーティングを与え、等等である。
【００２７】
順序１３０は又、署名生成器１２０により生成される検索署名とのマッチングのための検索の効果を発揮させるために用いられ、検索署名はデータベース１１０のコンテンツに
基づいている。
【００２８】
図２は、署名を生成するバイトの特定の順序に基づいて、署名に対する検索の効果を実行するための例示としてのフロー図を示している。参照番号２１０において、検索署名が受信され、マッチングが見つけられるまで又は検索を実行し尽くすまで、ループ２２０乃至２８０が繰り返される。参照番号２３０において、従来の技術を用いて、選択署名が識別される。例えば、バイナリサーチを用いて、現在の検索領域の中央における署名は選択署名である。ループ２２０乃至２８０の開始時において、検索領域は全体のデータベースであり、ループの各々の実行は半分の領域に限定される。順序付け検索においてサンプルを選択するための他の技術は当該技術分野においては一般的である。同様に、バイナリサーチ以外の順序付け検索又はその変形としては、例えば、Ｂツリー検索法等があり、一般的である。それについては、例えば、文献、”Ｔｈｅ  Ａｒｔ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｐｒｏｇｒａｍｍｍｉｎｇ，Ｖｏｌ．３：Ｓｏｒｔｉｎｇ  ａｎｄ  Ｓｅａｒｃｈｉｎｇ”，Ｄ．Ｋｎｕｔｈ，Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ  Ｐｕｂｌｉｓｈｉｎｇ  Ｃｏ．（１９７３）を参照されたい。
【００２９】
参照番号２４０において、マッチングパラメータが、データベースから現在の選択署名を識別するために設定され、ループ２５０乃至２６０が、検索署名のバイト全てが選択署名のバイト全てとマッチングするかどうかの判定を実行する。ループ２５０乃至２６０がミスマッチを伴わずに実行しつくされる場合、そのループは、選択署名の識別子に等しいマッチングパラメータを有することにより終了する。ループ２５０乃至２６０は、所定の順序で、検索署名のバイトと選択署名のバイトとを比較する。参照番号２５５においては、検索署名の現在の識別されたバイトは、所定の順序で、選択署名における対応するバイトと比較される。例えば、上記のａ−ｂ−ｃ表示の順序付けを用いて，その所定の順序が
ｂ−ａ−ｃである場合、その署名の第２の数字（‘ｂ’）が先ず、比較され、次いで、第１の数字（‘ａ’）が比較され、次いで、最後の数字（‘ｃ’）が比較される。対応するバイトが、参照番号２５５においてマッチングしない場合、マッチングパラメータは、参照番号２７０において、０のような、データベースにおける署名の識別子に対応しない値に設定され、そしてループ２５０乃至２６０は終了する。参照番号２８０において、マッチングパラメータが０である場合、データベースの検索が実行しつくされる場合以外、ループ２２０乃至２８０が繰り返される。
【００３０】
参照番号２９０においては、検索署名にマッチングするデータベースにおける選択署名の識別子か又は、上記の例示としての０のような、データベースにおける署名を識別しない値のどちらかとして、マッチングパラメータは戻される。図示していないが、マッチングパラメータが、検索署名に対してマッチングが見つからなかったことを示す場合、ユーさは、データベースに検索署名を付加するオプションを与えられる。好適な実施形態においては、ｆｉｒｓｔ−ｉｎ−ｆｉｒｓｔ−ｏｕｔ（ＦＩＦＯ）方法が、検索署名及び補助的情報を付加するために、必要に応じて、データベースに空間を与えるために用いられる。
【００３１】
上記のように、所定の順序が、従来のＭＳＢからＬＳＢへの順序と比べて、データベースにおける署名のより均一な分布をもたらす場合、参照番号２５５においてミスマッチがみつけられる前に、ループ２５０乃至２６０において比較される平均バイト数が従来のＭＳＢからＬＳＢへの検索より小さいことが、特に、署名が従来のクラスター化分布を表す場合に、見込まれる。
【００３２】
上記のアルゴリズムは、上記の非従来型のバイト順序付け法を用いて、従来のデータベースにおけるマルチバイト署名を記憶することにより効果を発揮することができることに留意されたい。図３は、代替としての検索システム３００の例示としてのブロック図を示しており、ここでは、各々の署名のバイトは所定の順序１３０に基づいて再順序化される。例えば、その所定の順序がｃ−ｂ−ａである場合、例示としての署名１２３、６５４、２７１は、各々の署名の数字の順序を逆にすることにより、再順序付け署名３２１，４５６、１７２に再構成される。データベース３９０における署名のバイトを再順序付けする３６０ことにより、従来のＭＳＢからＬＳＢへのソーティング３４０及び検索３５０は、検索署名は又、再順序付け処理３６０により同様に再順序付けされる条件で、効率的な検索を効果的に実行するために用いられる。
【００３３】
この例３００における従来のＭＳＢからＬＳＢへのソータ３４０は、再順序付けされたバイトの順序に対して、昇順（又は、降順）で再順序付けバイト署名を位置付ける。例示としての上記のｃ−ｂ−ａ順序付けにおいては、オリジナルの１２３、６５４、２７１の署名は、データベースにおいて、１７２、３２１、４５６として記憶される。検索署名（上記の例における７２３）は又、バイト再順序付けされた検索署名３２７を生成するために、ｃ−ｂ−ａとバイト再順序付けされる。記憶されたバイト再順序付け署名に対するバイト再順序付け検索署名についての従来のバイナリサーチは、３２７の３２１との従来のＭＳＢからＬＳＢへの比較を、次いで、ＬＳＢからＭＳＢへの順序付け及び検索を実行する上記の技術に対応する、３２７の４５６とのＭＳＢからＬＳＢへの比較を、効果的に実行する。
【００３４】
上記内容は、本発明の原理を単に示したものである。従って、当業者は、本発明の趣旨及び範囲から逸脱することなく、本発明の原理を具現化する種々の構成を考案することができることを理解するであろう。尚、それらについては、ここでは、明示的に記述及び図示していない。例えば、コンテンツ素材からの署名の生成は適切ではないため、上記のように、署名の幾つかのビットがマッチングしないときでさえ、検索シナリオを“マッチング”を示すように構造化することができる。当業者は、図２のブロック２５５を、関連マッチング基準に対応するように修正することができることを認識しているであろう。このような関連基準は、例えば、マッチングしないバイトのビット数、マッチングしない署名における累積ビット数又はマッチングしない署名における累積バイト数に基づくことができる。そのような関連基準は、最小ビット数差に基づいてマッチングをみつけるところの実行し尽す検索より速いマッチングの決定に繋がる可能性がある。しかしながら、ソーティング検索における関連基準を用いる非マッチングの決定は必ずしも完結的ではなく、続く、実行し尽す検索が、真の非マッチングを確認するために用いられることが可能である。上記の及び他のシステム構成及び最適化の特徴は、本明細書の観点から当業者には明らかであろう。そして、それらについては、同時提出の特許請求の範囲に記載している。
【図面の簡単な説明】
【００３５】
【図１】本発明に従った署名検索システムの例示としてのブロック図である。
【図２】本発明に従った例示としてのビット再順序付け検索を示す図である。
【図３】本発明に従った代替の署名検索システムの例示としてのブロック図である。
【図１】
2006511894.tif 000003
【図２】
2006511894.tif 000004
【図３】
2006511894.tif 000005
【国際調査報告】
2006511894.tif 000006
2006511894.tif 000007
2006511894.tif 000008