参照メディアコンテンツとの比較によってソース信号からソースメディアコンテンツを自動認識することを可能にするための装置であって、前記ソース信号にフーリエ変換を適用することによって前記ソース信号からスペクトログラムを生成するように動作可能なスペクトログラムジェネレータであり、前記スペクトログラムが複数のカラムcolumnを含み、各カラムcolumnがタイムスライスを表し複数の周波数ビンを含み、各周波数ビンが前記ソース信号の前記タイムスライスについての周波数成分のそれぞれの範囲を表す、スペクトログラムジェネレータと、前記タイムスライスの前記カラムcolumnからの選択された周波数ビンの大きさの比率を計算し、前記比率を量子化してソースベクトルの数字を生成することによって、前記ソース信号のタイムスライスに対して少なくとも1つのソースベクトルを生成するように動作可能なベクトルジェネレータと、ルックアップテーブル中のエントリに対して第1のベクトルの数字の完全一致を実施することによって1次評価を実施するように動作可能な1次エバリュエータであり、前記ルックアップテーブル中の各エントリが第2のベクトルのグループに関連し、前記完全一致を実施するのに使用される前記第1のベクトルの数字の数が前記ルックアップテーブル中のエントリ間で異なる、1次エバリュエータと、前記第1のベクトルと、第2のベクトルの前記グループのそれぞれとの類似度を決定して、前記ソースメディアコンテンツを前記参照メディアコンテンツと照合するための候補であるいずれかの第2のベクトルを識別するための、2次評価を実施するように動作可能な、2次エバリュエータと、前記ルックアップテーブル及び前記第2のベクトルを含むデータベースとを備え、前記第1のベクトルがソースベクトルと参照ベクトルとのいずれかであり、前記第2のベクトルが前記ソースベクトルと前記参照ベクトルとのうちの他方であり、各参照ベクトルが前記参照メディアコンテンツのタイムスライスを表す、装置。タイムスライスに対して少なくとも1つのベクトルを生成するために、前記ベクトルジェネレータが、タイムスライスの少なくとも1つの選択された周波数ビンについて、前記ビンと、前記タイムスライスの前記カラムcolumnからの、隣接するか又はほぼ隣接する周波数ビンとの比率を計算し、前記比率を範囲に分けて、各比率につき少なくとも1つの選択された数字を生成するように動作可能である、請求項1に記載の装置。タイムスライスに対して少なくとも1つのベクトルを生成するために、前記ベクトルジェネレータが、タイムスライスの少なくとも1つの選択された周波数ビンについて、前記ビンと、前記タイムスライスの前記カラムcolumnからの、隣接するか又はほぼ隣接する周波数ビンとの比率を計算し、前記比率を範囲に分けて、各比率につき2進数を生成するように動作可能である、請求項2に記載の装置。前記範囲が、選択された比率間で異なり、したがって範囲間で比率値のほぼ等しい分布をもたらす、請求項2又は3に記載の装置。前記ベクトルジェネレータが、400Hz~1100Hzの周波数帯域から選択された周波数ビンを使用して第1のソースベクトルを生成し、1100Hz~3000Hzの周波数帯域から選択された周波数ビンを使用して第2のソースベクトルを生成するように動作可能である、請求項2~4のいずれか一項に記載の装置。タイムスライスに対してさらに他のソースベクトルを生成するために、前記スペクトログラムジェネレータが、前記ソース信号にフーリエ変換を適用することによってさらに他のスペクトログラムを生成するように動作可能であり、前記さらに他のスペクトログラムが複数のカラムcolumnを含み、各カラムcolumnがタイムスライスを表し複数の周波数ビンを含み、各周波数ビンが前記ソース信号の前記タイムスライスについての周波数成分のそれぞれの範囲を表し、前記スペクトログラムジェネレータが、前記タイムスライスの前記カラムcolumnからの前記それぞれの周波数ビンにフーリエ変換をさらに適用してそれぞれの係数セットを生成するように動作可能であり、前記ベクトルジェネレータが、前記さらに他のソースベクトルを生成するように動作可能であり、それにより、タイムスライスのカラムcolumn中のN個の係数のセットに対して、前記さらに他のソースベクトルの要素2からN-1までのそれぞれにつき、n番目の係数の2乗をn-1番目の係数とn1番目の係数との積で割った値によってn番目の要素が形成され、前記ベクトルジェネレータが、得られた前記ベクトルの前記要素を量子化して、各要素につき少なくとも1つの数字を生成するように動作可能である、前記請求項のいずれか一項に記載の装置。前記ソース信号がオーディオ信号であり、前記スペクトログラムビンの前記周波数が対数目盛りに従って割り振られる、前記請求項のいずれか一項に記載の装置。前記ルックアップテーブルが、葉に至る可変深度の木として編成され、前記テーブルが第1のベクトルによって索引付けされ、各葉が、第2のベクトルのそれぞれのグループに関連する前記ルックアップテーブル中のエントリを形成し、各葉に至る数字の数が、各葉につきほぼ等しいサイズの第2のベクトルのグループを提供するように決定される、前記請求項のいずれか一項に記載の装置。各葉に至る数字の数が、所与の葉について前記完全一致を実施するのに使用される前記第1のベクトルの数字の数を形成する、請求項8に記載の装置。前記ルックアップテーブルの各葉が、d個の一致する数字を有する第2のベクトルのグループを識別し、dが前記葉までの前記木の深度に対応する、請求項8又は9に記載の装置。前記2次エバリュエータが、距離メトリックを使用して前記2次評価を実施して、前記第1のベクトルと第2のベクトルの前記グループのそれぞれとの前記類似度を決定するように動作可能である、前記請求項のいずれか一項に記載の装置。候補として識別されたいずれかの第2のベクトルに対して3次評価を実施するための3次エバリュエータをさらに備え、前記3次エバリュエータが、1つ又は複数のさらに他の第1のベクトルと、前記2次評価で識別された前記候補第2のベクトルに対応する1つ又は複数のさらに他の第2のベクトルとの類似度を決定するように動作可能である、前記請求項のいずれか一項に記載の装置。前記さらに他の第1のベクトル及び前記さらに他の第2のベクトルが、前記第1のベクトル及び前記候補第2のベクトルからそれぞれ時間的な隔たりがある、請求項12に記載の装置。前記ソース信号が、受信されたプログラム信号である、前記請求項のいずれか一項に記載の装置。前記プログラム信号の前記一致するメディアコンテンツのレコードを生成するように動作可能なレコードジェネレータを備える、請求項14に記載の装置。前記一致するメディアコンテンツを識別するキューシートを生成するように動作可能なキューシートジェネレータを備える、請求項15に記載の装置。前記第2のベクトルが前記ソースベクトルであり、前記装置が前記ソースベクトルから前記データベースを生成するように構成された、前記請求項のいずれか一項に記載の装置。前記スペクトログラムジェネレータ及び前記ハッシュベクトルジェネレータ及び前記エバリュエータを実装するように動作可能な、少なくとも1つのプロセッサと記憶装置とコンピュータソフトウェアとを備える、前記請求項のいずれか一項に記載の装置。参照メディアコンテンツとの比較によってソース信号からソースメディアコンテンツを自動認識するための自動認識方法であって、前記ソース信号にフーリエ変換を適用することによって前記ソース信号からスペクトログラムを生成するステップであり、前記スペクトログラムが複数のカラムcolumnを含み、各カラムcolumnがタイムスライスを表し複数の周波数ビンを含み、各周波数ビンが前記ソース信号の前記タイムスライスについての周波数成分のそれぞれの範囲を表す、ステップと、前記ソース信号のタイムスライスの前記カラムcolumnからの選択された周波数ビンの大きさの比率を計算し、前記比率を量子化してソースベクトルの数字を生成することによって、前記タイムスライスに対して少なくとも1つのソースベクトルを生成するステップと、ルックアップテーブル中のエントリに対して第1のベクトルの数字の完全一致を行うことによって1次評価を実施するステップであり、前記ルックアップテーブル中の各エントリが第2のベクトルのグループに関連し、前記完全一致を実施するのに使用される前記第1のベクトルの数字の数が前記ルックアップテーブル中のエントリ間で異なる、ステップと、前記第1のベクトルと、第2のベクトルの前記グループのそれぞれとの類似度を決定して、前記ソースメディアコンテンツを前記参照メディアコンテンツと照合するための候補であるいずれかの第2のベクトルを識別するための、2次評価を実施するステップとを含み、データベースが前記ルックアップテーブル及び前記第2のベクトルを含み、前記第1のベクトルがソースベクトルと参照ベクトルとのいずれかであり、前記第2のベクトルが前記ソースベクトルと前記参照ベクトルとのうちの他方であり、各参照ベクトルが前記参照メディアコンテンツのタイムスライスを表す、方法。タイムスライスに対して少なくとも1つのベクトルを生成するステップが、タイムスライスの少なくとも1つの選択された周波数ビンについて、前記ビンと、前記タイムスライスの前記カラムcolumnからの、隣接するか又はほぼ隣接する周波数ビンとの比率を計算するサブステップと、前記比率を範囲に分けて、各比率につき少なくとも1つの選択された数字を生成するサブステップとを含む、請求項19に記載の方法。タイムスライスに対して少なくとも1つのベクトルを生成するステップが、タイムスライスの少なくとも1つの選択された周波数ビンについて、前記ビンと、前記タイムスライスの前記カラムcolumnからの、隣接するか又はほぼ隣接する周波数ビンとの比率を計算するサブステップと、前記比率を範囲に分けて、各比率につき2進数を生成するサブステップとを含む、請求項20に記載の方法。前記範囲が、選択された比率ビン間で異なり、したがって範囲間で比率値のほぼ等しい分布をもたらす、請求項20又は21に記載の方法。400Hz~1100Hzの周波数帯域から選択された周波数ビンを使用して第1のソースベクトルを生成し、1100Hz~3000Hzの周波数帯域から選択された周波数ビンを使用して第2のソースベクトルを生成するステップを含む、請求項20~22のいずれか一項に記載の方法。タイムスライスに対してさらに他のソースベクトルを生成するステップを含み、前記さらに他のソースベクトルが、前記ソース信号にフーリエ変換を適用することによって前記第1の信号からさらに他のスペクトログラムを生成するサブステップであって、前記さらに他のスペクトログラムが複数のカラムcolumnを含み、各カラムcolumnがタイムスライスを表し複数の周波数ビンを含み、各周波数ビンが前記第1の信号の前記タイムスライスについての周波数成分のそれぞれの範囲を表す、サブステップと、前記タイムスライスの前記カラムcolumnからの前記それぞれの周波数ビンにフーリエ変換をさらに適用して、それぞれの係数セットを生成するサブステップと、前記さらに他のソースベクトルを生成するサブステップであって、それにより、タイムスライスのカラムcolumn中のN個の係数のセットに対して、前記さらに他のソースベクトルの要素2からN-1までのそれぞれにつき、n番目の係数の2乗をn-1番目の係数とn1番目の係数との積で割った値によってn番目の要素が形成され、得られた前記ベクトルの前記要素を量子化して各要素につき少なくとも1つの数字を生成する、サブステップとによって生成される、請求項19~23のいずれか一項に記載の方法。前記ソース信号がオーディオ信号であり、前記スペクトログラムビンの前記周波数が対数目盛りに従って割り振られる、請求項19~24のいずれか一項に記載の方法。前記ルックアップテーブルが、葉に至る可変深度の木として編成され、前記テーブルが前記第1のベクトルによって索引付けされ、各葉が、第2のベクトルのそれぞれのグループに関連する前記ルックアップテーブル中のエントリを形成し、各葉に至る数字の数が、各葉につきほぼ等しいサイズの第2のベクトルのグループを提供するように決定される、請求項19~25のいずれか一項に記載の方法。各葉に至る数字の数が、所与の葉について前記完全一致を実施するのに使用される前記第1のベクトルの数字の数を形成する、請求項26に記載の方法。前記ルックアップテーブルの各葉が、d個の一致する数字を有する第2のベクトルのグループを識別し、dが前記葉までの前記木の深度に対応する、請求項26又は27に記載の方法。距離メトリックを使用して前記2次評価を実施して、前記第1のベクトルと第2のベクトルの前記グループのそれぞれとの前記類似度を決定するステップを含む、請求項19~28のいずれか一項に記載の方法。候補として識別されたいずれかの第2のベクトルに対して3次評価を実施するステップを含み、前記3次評価が、1つ又は複数のさらに他の第1のベクトルと、前記2次評価で識別された前記候補第2のベクトルに対応する1つ又は複数のさらに他の第2のベクトルとの類似度を決定するサブステップを含む、請求項19~29のいずれか一項に記載の方法。前記さらに他の第1のベクトル及び前記さらに他の第2のベクトルが、前記第1のベクトル及び前記候補第2のベクトルからそれぞれ時間的な隔たりがある、請求項30に記載の方法。前記ソース信号が、受信されたプログラム信号である、請求項19~31のいずれか一項に記載の方法。前記プログラム信号の前記一致するメディアコンテンツのレコードを生成するステップを含む、請求項32に記載の方法。前記一致するメディアコンテンツを識別するキューシートを生成するステップを含む、請求項33に記載の方法。前記第2のベクトルが前記ソースベクトルであり、前記装置が前記ソースベクトルから前記データベースを生成するように構成された、請求項19~34のいずれか一項に記載の方法。請求項19~35のいずれか一項に記載の方法を実施するように動作可能なプログラム命令を含む、コンピュータプログラム製品。0006しかし、オーディオメディアコンテンツをより効率的且つより確実に識別するための装置、システム、及び方法が、依然として必要とされている。概要0007本発明の態様は、特許請求の範囲において定義される。0008例示的な一実施形態では、サンプルメディアコンテンツの自動認識がもたらされる。オーディオ信号の連続的なタイムスライスについて、スペクトログラムが生成される。タイムスライスのカラムcolumnからのそれぞれの周波数ビンの大きさの比率を計算することによって、タイムスライスに対して1つ又は複数のサンプルベクトルが生成される。1次評価段階1次テスト段階では、ハッシュテーブル中のエントリに対してサンプルベクトルのビットの完全一致が実施されて、1つ又は複数の参照ベクトルのグループが識別される。2次評価段階2次テスト段階では、サンプルベクトルと参照ベクトルのグループのそれぞれとの類似度が実施されて、サンプルメディアコンテンツを照合するための候補であるいずれかの参照ベクトルが識別され、各参照ベクトルは、参照メディアコンテンツのタイムスライスを表す。ベクトルはまた、ハッシュ、ハッシュベクトル、シグネチャ、又はフィンガプリントとして、様々に記述することができる。0009本発明の一実施形態は、動作のスケーラビリティ及び効率をもたらすことができる。本発明の一実施形態は、参照トラックの非常に大きなデータベースを効率的且つ確実に扱うことができる。0010本発明の一実施形態は、プログラムオーディオから生成されたハッシュがデータベース中の多すぎるハッシュと一致することがない傾向にあるように、良い識別力多くのエントロピーを有するハッシュを採用することができる。本発明の一実施形態は、オーディオ信号のスペクトルからの多数の測定値を採用することができる。各測定値は、例えば、歪みに対して比較的頑強な、2ビットの2進数の形とすることができる。これらの測定値から、スペクトルの限定された部分に依存するスペクトルハッシュのセットを生成することができる。0011本発明の一実施形態は、1次ステップでの完全一致データベース探索を、可変深度の木構造に記憶された追加の情報を使用する精緻化ステップと組み合わせる方法を用いる。これは、近傍探索の効果と同様の効果をもたらすが、従来の近傍探索に桁違いに勝る処理速度の向上を達成する。完全一致探索は、コンピュータ中で効率的に行うことができ、より高速な認識の実施を可能にすることができる。一実施形態は、非常に大きなソースフィンガプリントデータベースを使用するとき、従来の手法と比較して低減された処理要件で、歪みのある環境で正確な認識を可能にする。一実施形態は、単純な完全一致に関与するシグネチャ部分のエントロピーが慎重に制御されるようにしてそのようにシグネチャのエントロピーを慎重に制御することなしにおおよその一致を使用するのではなく、ある瞬間に対応するシグネチャ又はフィンガプリントが生み出されることを可能にする。これにより、はるかに削減されたプロセッサコストで、正確さ及びスケーラビリティを可能にすることができる。0012スペクトログラムから多数の測定値をとるのではなく、例示的な一実施形態は、完全一致させることが必要とされるハッシュからのビットの数を変動させることによって、様々なハッシュの種々の強度を考慮に入れる。例えば、強いハッシュの最初の27個のビットのみを完全一致させればよく、より弱いハッシュの場合は、より多数の、例えば最初の34ビットを一致させればよい。本発明の一実施形態は、可変深度の木構造を使用して、これらの一致動作の効率的な実施を可能にすることができる。0013例示的な一実施形態は、雑音のある環境で正確な認識を可能にすることができ、また、認識すべきオーディオの継続時間が非常に短い場合例えば3秒未満、又は2秒未満、又は1秒未満であっても、そのようにすることができる。例示的な一実施形態は、フィンガプリント付きコンテンツの非常に大きなデータベースソース例えば百万曲を超える楽曲のに対する認識をもたらすことができる。例示的な一実施形態は、従来のスタンドアロンコンピュータ上で、又はネットワーク化されたコンピュータシステム上で実装することができる。例示的な一実施形態は、既存の認識システムの結果の品質を大きく改善することができ、このようなシステムの大規模実装のコストを改善することができる。0014以下、添付の図面を参照しながら、単なる例として、実施形態について述べる。詳細な説明0021本発明の例示的な一実施形態は、流入incomingオーディオストリームプログラムを処理し、音楽及び音響効果トラックの内部データベースを探索して、プログラム内でのこれらのトラックの使用を識別する、オーディオ認識システムを提供する。例示的な一実施形態の出力の一例は、使用されるトラックのセクションと、それらがプログラム中のどこで発生するかとをリストするキューシートcuesheetの形とすることができる。0022例示的な一実施形態は、例えば1千万秒の音楽のデータベースを扱うことができる。しかし、他の実施形態は、はるかに大きいデータベース、例えば10億秒の音楽のデータベースを扱うようにスケーラブルであり、およそ例えば3秒以下、例えば1秒の継続時間のクリップを認識することができ、通常の音楽ラジオ局からのオーディオを処理する際に、従来のサーバコンピュータ上でリアルタイムの10倍前後のレートで動作することができる。0023以下は、本文書で使用される用語のいくつかの定義である。0024トラックは、後の何らかの時点で認識されることになるオーディオのクリップである。利用可能な全てのトラックは、処理されてデータベースに結合される。0025プログラムは、認識されることになる1つのオーディオである。プログラムは、他の材料がちりばめられた、接合され様々な歪みを受けたいくつかのトラックを含むものと想定される。0026歪みは、プログラムを構成するトラックに対して起こる何らかである。歪みの例は以下のとおりである:-雑音:トラックに対するランダム雑音の混合-ボイスオーバ:トラックに対する音声の混合-ピッチ:基礎をなすタイミングが維持される一方での、ピッチの変化-テンポ:ピッチが維持される一方での、タイミングの変化-速度:ピッチとテンポの両方の変化例えば、テープをより速く再生することによる。0027ピッチ、テンポ、及び速度は関係していること、また、いずれか2つを組み合わせて3つ目を生成できることに留意されたい。0028ハッシュは、トラック又はプログラムの特定部分タイムスライスから得られる1つの小さい情報であり、この情報は、歪みによって変化しないのが理想的である。0029図1は、本発明の一実施形態を形成する装置110の例の概略ブロック図である。0030信号ソース102は、例えば、メディアプログラム例えばオーディオプログラムを受信してソース信号104を提供するための、マイクロホン、ラジオ番組又はインターネット番組受信機などの形とすることができる。0031スペクトログラムジェネレータ112は、ソース信号104にフーリエ変換を適用することによってソース信号からスペクトログラムを生成するように動作可能とすることができる。スペクトログラムは複数のカラムcolumnを含み、各カラムcolumnはタイムスライスを表し複数の周波数ビンを含み、各周波数ビンは、ソース信号のそのタイムスライスについての周波数成分のそれぞれの範囲を表す。0032ベクトルジェネレータ114は、タイムスライスのカラムcolumnからのそれぞれの周波数ビンの大きさの比率を計算し、この比率を量子化してソースベクトルの数字を生成することによって、ソース信号のタイムスライスに対して少なくとも1つのソースベクトルを生成するように動作可能とすることができる。0033データベース46は参照ベクトルを含み、各参照ベクトルは、参照メディアコンテンツのタイムスライスを表す。0034コンテンツエバリュエータ116は、1次、2次、及び3次エバリュエータ、それぞれ118、120、及び122を備えることができる。00351次エバリュエータ118は、データベース46のルックアップテーブル66中のエントリに対してソースベクトルの数字の完全一致を実施することによって、1次評価を実施するように動作可能とすることができる。ルックアップテーブル中の各エントリは参照ベクトルのグループに関連し、完全一致を実施するのに使用されるソースベクトルの数字の数は、ルックアップテーブル66中のエントリ間で異なってもよい。ルックアップテーブル66は、葉に至る可変深度の木として編成することができ、各葉は、参照ベクトルのそれぞれのグループに関連する、ルックアップテーブル中のエントリを形成する。各葉に至る数字の数は、各葉につきほぼ等しいサイズの参照ベクトルグループを提供するように決定することができる。各葉に至る数字の数は、所与の葉について完全一致を実施するのに使用されるソースベクトルの数字の数を形成することができる。ルックアップテーブル66の各葉は、d個の同一の数字を有する参照ベクトルのグループを識別することができ、dは、その葉までの木の深度に対応する。00362次エバリュエータ120は、ソースベクトルと、データベース46中の参照ベクトルのグループのそれぞれとの類似度を決定して、ソースメディアコンテンツを参照メディアコンテンツと照合するための候補であるいずれかの参照ベクトルを識別するための、2次評価を実施するように動作可能とすることができる。2次エバリュエータ120は、距離メトリックを使用して2次評価を実施して、ソースベクトルと参照ベクトルのグループ中の各参照ベクトルとの類似度を決定するように動作可能とすることができる。00373次エバリュエータ122は、候補として識別されたいずれかの参照ベクトルについて3次評価を実施するように動作可能とすることができる。3次エバリュエータ122は、1つ又は複数のさらに他のソースベクトルと、2次評価で識別された候補参照ベクトルに対応する1つ又は複数のさらに他の参照ベクトルとの類似度を決定するように動作可能とすることができる。さらに他のソースベクトル及びさらに他の参照ベクトルはそれぞれ、ソースベクトル及び識別された候補参照ベクトルから時間的な隔たりがあるものとすることができる。0038出力ジェネレータ124は、ソース信号の一致メディアコンテンツを識別する出力レコードrecord、例えばキューシートを生成するように動作可能とすることができる。0039図2は、本発明の例示的な一実施形態の方法のステップの概観を提供する流れ図10である。図1の装置及び図2の方法は、1つ又は複数のコンピュータシステムと、1つ又は複数のコンピュータシステム上で動作する1つ又は複数のコンピュータプログラム製品とによって実装することができる。コンピュータプログラム製品複数可は、任意の適切なコンピュータ可読媒体、例えばコンピュータディスク、テープ、固体記憶装置などに記憶することができる。様々な例で、プロセスの様々な段階を、別々のコンピュータプログラム及び/又は別々のコンピュータシステムによって実施することができる。例えば、後述するスペクトログラムの生成は、ハッシュ生成及び/又はデータベーステスト及び/又はキューシート生成に使用される1つ又は複数のコンピュータプログラム及び/又はコンピュータシステムとは別個の、コンピュータプログラム及び/又はコンピュータシステムによって実施することができる。さらに、図1の装置又は図2のプロセスの1つ又は複数の部分は、専用ハードウェア、例えば後続の記述でより詳細に述べる機能を提供するように構成された専用集積回路を使用して、実装することができる。0040しかし、説明を容易にするために過ぎないが、図2を参照しながら後述するプロセスは、スペクトル生成12、ベクトル生成14、信号評価161次、2次、及び3次段階18、20、及び22を含む、並びに出力生成24を含むが、これらのプロセスは、1つ又は複数のプロセッサと記憶装置とを備え1つ又は複数のプログラムによって制御されるコンピュータサーバシステムを構成する装置によって実施されると仮定する。スペクトル生成12、ベクトル生成14、信号評価161次、2次、及び3次段階18、20、及び22を含む、並びに出力生成24を含む、後述するプロセスステップはまた、図1のスペクトルジェネレータ112、ベクトルジェネレータ114、コンテンツエバリュエータ1161次、2次、及び3次エバリュエータ118、120、及び122の機能を含む、並びに出力ジェネレータ124によって実施される機能にそれぞれ対応する。スペクトル生成120041この例では、例えば高速フーリエ変換FFTをオーディオ信号に適用することによって、オーディオ信号の形のソース信号が処理されてスペクトログラムが生成される。0042例示的な一実施形態では、オーディオ信号は、オーディオ信号が比較される対象となるデータベースを生成する方法と一貫性があるようにして、フォーマットされるべきである。例示的な一実施形態では、オーディオ信号は、例えば1サンプル当たり16ビットで、可能ならステレオで、不可能ならモノラルで、例えば12kHzでサンプリングされた、プレーン.WAVフォーマットに変換することができる。例示的な一実施形態では、ボイスオーバ及び類似の歪みに対するより大きな回復力をもたらすために、左チャネルと右チャネルとを含むステレオオーディオが、合計左右チャネル及び差分左-右チャネルとして表される。次いで、オーディオファイルは処理されて、スペクトログラムが生成される。0043スペクトログラムに適用されるパラメータは、人間の耳による音の知覚に大まかに基づく。その理由は、音が被る可能性の高い種類の歪みは、人間の知覚を保存する種類の歪みだからである。スペクトログラムは、連続的なサンプル間隔タイムスライスについての、情報の一連のカラムcolumnを含む。各タイムスライスは、例えば1~50ミリ秒例えば約20ミリ秒に対応する。連続的なセグメントは、それらの長さのかなりの割合で、例えばそれらの長さの90~99、例えば約97で、重なり得る。この結果、音の特性は、セグメントからセグメントへゆっくりとしか変化しない傾向がある。1つのタイムスライスについてのカラムcolumnは、対数目盛り上に構成された複数の周波数ビンを含むことができ、各ビンは、例えば、およそ半音1つの幅である。0044スペクトルの各タイムスライス又はカラムcolumnにつき、かなりの数の周波数ビンを設けることができる。例えば、約40~100個又はより多くの周波数ビンを生成することができる。特定の一例では、92個の周波数ビンが設けられる。ベクトル生成140045第2のステップ14は、1つ又は複数のハッシュベクトル又はハッシュの生成である。例示的な一実施形態では、いくつかの異なるタイプのハッシュが生成される。ハッシュ又はフィンガプリント、シグネチャを形成する低次元ベクトルの1つ又は複数のシーケンスは、遭遇する可能性のある様々なタイプの歪みに対して頑強であるように設計される。0046例示的な一実施形態では、追加の雑音及び類似の信号に対する回復力を与えるために、ハッシュを生成する前に測定値を粗く量子化することができる。粗く量子化したいという望みと、ソースオーディオから十分なエントロピーを導出する必要性との間で、対立がある。得られるエントロピーを高めるために、どんな所与の測定値に対しても量子化値が等しく見込みがある傾向にあるように量子化を非線形に実施することができ、これにより、図3に示すように、ハッシュの分布はより均一になる。各周波数で量子化しきい値を独立して選択して、ハッシュの分布をより均一にすることができる。頑強性を最大限にするために、各測定値は、スペクトログラム中の2つの点のみに依存するように選択することができる。0047例示的な一実施形態では、基本的なハッシュは、隣接するか又はほぼ隣接する周波数ビンの大きさの比率を計算することによって、スペクトログラムの単一のカラムcolumnから導出される。一例では、カラムcolumn中の隣接する周波数ビンの内容の比率を決定し、この比率を4つの範囲のうちの1つに分けることによって、ベクトルを生成することができる。0048例えば、ビン0~91のそれぞれにつき、以下のように比率を決定する:-ビンiの値/ビンi1の値-そして、この比率が、4つの範囲00、01、10、及び11のうちのどの範囲内に入るかを決定する。0049極端な単純化で表して、範囲00が、0と0.5との間の比率に対応し、範囲01が、0.5と1との間の比率に対応し、範囲10が、1と5との間の割合に対応し、範囲11が、5と無限との間の比率に対応すると考えてみる。したがって、比較されるビンの対それぞれにつき2ビットの数を生成できることがわかる。別の例では、異なる数範囲を使用して、異なる基数に従って異なる数のビット又は1つ若しくは複数の数字を生成することができる。0050このようなベクトルは、元の信号中の全体的な振幅変化に対してほぼ不変とすることができ、等化高い又は低い周波数のブースト又はカットに対して頑強とすることができる。範囲00、01、10、及び11は、ビンごとに異なってよく、オーディオのテストセットから比率の値を収集して、その結果得られた分布を4つの等しい部分に分けることによって、経験的に得ることができる。0051例示的な一実施形態では、次いで、2つのハッシュが生成される。一方のハッシュは、約400Hz~約1100Hzの周波数帯域を使用して生成されタイプ0ハッシュ、他方のハッシュは、約1100Hz~約3000Hzの周波数帯域を使用して生成されるタイプ1ハッシュ。これらの比較的高い周波数帯域は、トラックにボイスオーバを加えることによって引き起こされる歪みに対してより頑強である。0052例示的な一実施形態では、ピッチ変動オーディオサンプルのシーケンスが通常のサンプルレートよりも速く又は遅く再生されるときに起こるものなどに対して頑強であるように設計された、さらに他のハッシュタイプタイプ2ハッシュが生成される。基本的なハッシュと同様の、対数周波数スペクトログラムビンのセットが生成される。次いで、各スペクトログラムビンの振幅をとって、第2のフーリエ変換が適用される。この手法は、対数周波数ケプストラムに似た係数のセットを生成する。元のオーディオ中のピッチシフトが、対数周波数スペクトログラムのカラムcolumnにおける平行移動に対応することになり、したがって、エッジ効果を無視して、得られた係数中の位相シフトに対応することになる。次いで、得られた係数が処理されて、新しいベクトルが形成される。この新しいベクトルのn番目の要素は、n番目の係数の2乗をn-1番目の係数とn1番目の係数との積で割った値をとることによって得られる。この量は、係数中の位相シフトに対して不変であり、したがって、元の信号中のピッチシフトに対しても不変である。また、元の信号中のボリュームの変化の下でも不変である。0053連続的なセグメントはそれらの長さのかなりの割合で重なるので、音の特性は、セグメントからセグメントへゆっくりとしか変化しない傾向があり、それにより、ハッシュは、セグメントからセグメントへ1又は2ビット又は桁でしか変化しない傾向がある。0054これらのハッシュは全て、スペクトログラムの1つのカラムcolumnを調べるだけなので、これらのハッシュは原則的に、テンポ変動ピッチシフトなしの時間伸張又は圧縮に対して不変である。いくつかのテンポ変動アルゴリズムはより低周波数のオーディオ成分のいくらかの歪みを引き起こすことがわかる可能性があるので、前述のようなより高周波数の成分に基づくハッシュは、より頑強である。0055例示的な一実施形態は、プログラムオーディオ中のボイスオーバに関する頑強性をもたらすことができる。トラックにボイスオーバを加えることの一般的な影響は、時間と周波数とにおいて局所化される傾向のあるエリアでスペクトログラムを変化させることである。スペクトログラムの単一のカラムcolumnオーディオの非常に短いセクションに対応するのみに依存するハッシュを使用することは、ボイスオーバに関する頑強性をもたらす。これにより、ボイスオーバが短い間でもおそらく言葉の途中でも一時停止する場合にトラックを認識する良い機会が与えられる。周波数において少なくとも部分的に局所化されるハッシュを使用することはまた、ボイスオーバ並びにいくつかの他の種類の歪みに対する回復力を改善するのにも役立つ。0056さらに、各ハッシュがオーディオの非常に短いセクションに依存することは、トラックの非常に短いセクションを認識する可能性をもたらす。0057ピッチの転位付随するテンポ変化あり又はなしに対する回復力は、修正されたケプストラム計算に基づいてハッシュを生成することによって達成することができる。テスト段階コンテンツ評価160058例示的な一実施形態では、次いで、ハッシュをデータベース中のトラックの事前計算済みハッシュと比較することによって、プログラムオーディオが認識される。このルックアッププロセスの目標は、スペクトログラムの1つのカラムcolumnから得られたベクトルを例えば使用して、音楽データベース全体にわたり近似ルックアップ又は最近傍探索を実施することである。これは、可能性のある多数のターゲットオブジェクトが音楽データベースから導出される、高次元探索である。0059例示的な一実施形態では、これは多段階テストプロセス16として行われる。1次テスト段階1次評価180060完全一致ルックアップを使用して、1次テスト段階18が実施される。例示的な一実施形態では、これは、ハッシュテーブル中でルックアップを実施するための少数のビットを含む単純な2値ベクトルとしてハッシュを使用して行われる。少数のビットを使用する結果として、各ルックアップは通常、データベース中の多数のヒットを返す。後でより明確になる理由で、所与のキーに対する1次ルックアップに応答して取り出されるデータベース中のヒットのセットは、葉と呼ばれる。0061実際上は、キーを構築するためにスペクトログラムから抽出されるビットは、独立しておらず、0又は1である可能性が等しく高いわけではない。言い換えれば、ベクトルの1ビット当たりのエントロピー音楽の所与のサンプルに関しては、1未満である。0062いくつかの種類のベクトルの、1ビット当たりのエントロピーは、他の種類のベクトルよりも大きい。このことを別の言い方で言うと、いくつかのキーは、他のキーよりもずっと一般的である。したがって、固定サイズのキーを使用してデータベースにアクセスする場合、多数のヒットが見つかることもあれば少数のヒットが見つかることもあることになる。キーがランダムに選ばれる場合、キーが所与の葉に含まれる確率は、この葉の中のエントリの数に比例し、また、これが良好な一致であるかどうか判定するためにこれらの各エントリをチェックするのに必要とされる追加の作業の量も、この葉の中のエントリの数に比例する。結果として、このキーについて行われるべき作業の予想総量は、この場合、葉のサイズの2乗の平均に比例する。このことに鑑みて、一実施形態では、葉のサイズをできるだけ等しくすることによって、この値が最小限に抑えられるすなわちシステム性能が最大限になる。0063一実施形態では、したがって、葉のサイズを均等にすることを目標としたデータベース構造が選ばれる。0064望むなら、スペクトログラムの連続関数からハッシュのビットを導出することができる。例えば、連続的な量を8つの異なる値のうちの1つに量子化し、結果を3ビットとしてハッシュ中で符号化することができる。このような場合、一様量子化方式を使用するのではなく、その代わりに、可能性のある各量子化値が発生する可能性が等しく高い傾向があるように、量子化しきい値を選ぶ例えば大きな音楽サンプルの分析に基づいてことが有利である。データベースを作成するときに使用される量子化レベルは、データベース中でルックアップされることになるプログラムからハッシュを作成するときに使用される量子化レベルと同じである。0065ハッシュ中のビットはまた、頑強である可能性がより高いビット例えば、量子化された連続的な量のより上位のビットがハッシュの最上位端に向かって配置され、頑強性のより低いビットがハッシュの最下位端に向かって配置されるように、構成することができる。0066一実施形態では、データベースは、2分木の形で構成される。木の深度は、ハッシュ中のビットの位置に対応する。木は、キーハッシュからの1ビットを消費しながら最上位すなわち最も頑強なものから先に下から上に横断されて、終端ノード又は葉が例えば深度dで見つかるまで、各点で、左の子が選択されるか右の子が選択されるかが判定される。葉は、d個の最上位ビットがキーハッシュのd個の最上位ビットと一致するようなハッシュを含むデータベース中のトラックに関する情報を含む。0067葉は様々な深度にあり、これらの深度は、木の各葉がおよそ同程度の数のエントリ、例えばほぼ同数のエントリを含むように選ばれる。他の例では、木は2分木とは別の基数に基づいてもよいことに留意されたい例えば3分木。0068したがって、1次テスト段階では、プログラムオーディオからのハッシュの選択されたビットと、参照トラックの記憶済みハッシュとの間で、完全一致が探られる。照合される数字の数は、データベースのサイズと、そのハッシュがトラックの中で概してどれくらい一般的であるかとに依存し、したがって、より少ないビットがより珍しいハッシュと照合される。照合される数字の数は、トラックデータベースのサイズに応じて、例えば2分木の場合に10~約30ビットの間で、変動する可能性がある。0069さらに、同じタイプの連続的なハッシュは通常、1又は2ビットのみしか変化しないので、ハッシュが生成されるプログラム中の時点が、参照トラックデータベースについてハッシュが生成された時点と厳密に同期しなくても、照合されるビットについて完全一致が一般にまた得られる。2次テスト段階2次評価200070一実施形態では、2次テスト段階20は、ランダムファイルアクセスによってデータベース中のプログラムハッシュをルックアップすることを含む。これにより、多数の、典型的には数百個の、例えば約200個のハッシュ一致を含む、単一の葉の内容がフェッチされる。各一致は、プログラムハッシュに表面上類似する、元のトラックのうちの1つの中の点に対応する。0071これらのエントリにはそれぞれ、2次テスト情報、すなわち、スペクトログラムから導出されたさらに他の情報を含むデータが付随する。タイプ0及びタイプ1ハッシュには、元のハッシュの作成に関係しないスペクトログラム部分からの量子化済みスペクトログラム情報が付随する。タイプ2ハッシュには、ケプストラム型係数から導出されたさらに他のビットが付随する。エントリはまた、ハッシュに対応する元のトラックと、そのトラック中での位置とを突き止めることを可能にする情報も含む。00722次テストの目的は、プロセスのこの段階がもはや完全一致探索に制約されないことを利用して、プログラムサンプルとデータベースエントリとが一致するかどうかに関する統計的により強力な知識を得ることである。例示的な一実施形態では、マンハッタン距離メトリック又は他の何らかの距離メトリックを使用して、2次テスト情報の2つのベクトル間の類似度を決定することができる。0073例示的な一実施形態では、通過する各2次テストは、データベースに対してさらにランダムファイルアクセスを行って、後述する3次テストのための情報を得ることを伴う。このことを念頭に置くと、例示的な一実施形態では、葉の中のデータベースエントリのうち、平均して約1つが2次テストに合格するように、2次テストに合格するためのしきい値が構成される。言い換えれば、2次テストに合格する確率は、葉のサイズのおおよそ逆数であるべきである。0074図4に、大きい音楽データベースからランダムに選択された2つの2次テストベクトル間の距離の例示的な分布を示す。3つのハッシュタイプのそれぞれにつき1つの曲線がある。これにより、所与のタイプの2次テストに対するしきい値は、適切な曲線上の点を選ぶことによって選ばれるが、この点は、曲線の下の総エリアの一部であるこの点の左側の裾の下のエリアが、葉のサイズの逆数とほぼ等しくなるような点である。0075このように、2次テスト段階では、各1次ヒットが2次テストを受けるが、この2次テストは、同じオーディオセグメントから生成されたハッシュ情報を、一致点における候補トラックと比較することを含む。3次テスト段階3次評価220076上に示したように、葉に記憶された情報は、ハッシュに対応する元のトラックと、そのトラック中での位置とを突き止めることを可能にする。2次テストに合格すると、一致点の周りの短いトラックセクションに対応する3次テストデータがフェッチされる。3次テスト情報は、元のトラックの一連のハッシュを含む。次いで、プログラムハッシュが3次テストデータと比較される。このプロセスは、完全一致探索に制約されず、したがって、距離メトリック、例えばマンハッタン距離メトリックを使用して、プログラムハッシュがどれくらい3次テストデータに類似するかを決定することができる。例示的な一実施形態では、メトリックは、プログラムハッシュと3次テストデータとの類似度を決定するための、経験的に決定された確率テーブルに基づく完全確率的計算を伴う。0077プログラムハッシュのシーケンスと3次テストデータのシーケンスとの両方に、タイムスタンプ情報が付随する。通常、これらは整合すべきである。言い換えれば、プログラムハッシュのタイムスタンプは、一致する3次テストタイムスタンプから一定オフセットを有するべきである。しかし、プログラムが時間伸張された場合はテンポ歪み、このオフセットは徐々にドリフトすることになる。テンポ歪みが大きいほど、ドリフトは速い。このドリフトを検出するために、いくつかの異なる試行テンポで3次テストを実施することができ、最良の結果を、一致のためのテンポ推定値として選択することができる。テンポ歪みは比較的稀なので、例示的な一実施形態では、この選択プロセスは、テンポ歪みが発生しなかったと信じる方に偏向される。00783次テストでは、一致点から後方と前方への走査を実施して、プログラムハッシュと3次テストハッシュとの類似度が評価され、また、テンポ推定値を使用して、プログラム中及び3次テストデータ中で走査が実施される相対速度が決定される。あるレートよりも高いレートで良好な一致が発生し続ける限り、このことは、プログラムがその期間にわたってトラックを含むことの証拠とされる。良好な一致がもはや見られないとき、このことは、トラックの使用の開始又は終了が見つかったことの証拠とされる。0079初期のテンポ推定値が正確である可能性は低い。したがって、走査中に、計算された公称位置のやや前及びやや後のプログラムハッシュがテストされる。これらのハッシュが公称位置のハッシュよりも3次テスト情報とよく一致する場合は、推定されたテンポに対して補正が適用される。このように、テンポにおける少量のドリフトの追跡に対応する。0080例示的な一実施形態で使用されるハッシュはスペクトログラムの単一のカラムcolumnに依存するので、これらのハッシュはテンポの変化に対して本質的に回復力がある。テンポ変化に関する分析又は探索が3次テスト段階まで延期され、3次テスト段階では調べるべき候補がわずかしかなく、そのため、可能性のあるテンポオフセットにわたる網羅的な探索が計算的に実行可能である、という点で、効率が高まる。0081したがって、3次テスト段階では、元のトラックのスペクトログラムの高圧縮バージョンを含み得る第2のデータベースが使用される。例示的な一実施形態では、このデータベースは、1次データベースと同様のハッシュに基づき、いくらかの追加の副次情報が加わる。これらのデータは、トラックによって、且つそのトラック内での位置によって、素早くアクセス可能であるように構成される。インデックスがコンピュータのRAM内に納まるように、システムを構成することができる。3次テストの間、2次テストに合格した候補一致のいずれかの側のプログラムオーディオが、完全確率的計算を使用してデータベースと比較される。このテストは、2次テストに合格した偽陽性を拒否することができると同時に、プログラム内の、トラック材料が使用される開始点と終了点を見つける。0082要約すると、2次テストに合格した各ハッシュは、プログラム材料と2次テスト段階によって暗示されるトラック材料との整合に基づく3次テストを受ける。3次テストでは、ハッシュ並びに他の情報を含むデータベースを使用してプログラムと候補トラックとを比較することによって、1次ヒットが発生した点から時間の後方と前方とにこの整合を拡張して、正確な比較の実施を可能にする。一致をいずれかの方向に十分に拡張できない場合は、一致は廃棄される。そうでない場合は、十分な一致が見つかったプログラム時間の範囲が入ポイント及び出ポイントとして、一致トラックの識別と、一致したトラック時間の範囲と共に、報告される。例示的な一実施形態では、これは、出力キューシート上の1つの候補エントリを形成する。出力段階220083先に言及したように、オーディオ認識プロセスの一適用例は、キューシートの生成である。3次テストの結果は、元のデータベース中のトラックに対する、プログラム材料の一連の候補一致である。各一致は、プログラム開始点及び終了点と、トラックの識別番号と、トラック内の開始点及び終了点と、一致の品質の全体的な程度とを含む。一致の品質が十分に高い場合は、この一致は、キューシート中へのエントリの候補である。0084新しい候補キューシートエントリが見つかったとき、このエントリは、すでにキューシート中にあるエントリと比較される。プログラム時間において既存のエントリと著しい重複がない場合は、キューシートに追加される。別のエントリと著しい重複がある場合は、その一致品質がより高ければ別のエントリは置き換えられ、そうでなければ候補は廃棄される。0085全てのプログラムハッシュが処理されると、完成したキューシートを出力することができる。0086先に示したように、述べたプロセスは、1つ又は複数のコンピュータシステム上で動作する1つ又は複数のコンピュータプログラムによって自動的に実施されるが、リアルタイムで実施される単一のプロセスに統合されてもよく、或いは1つ又は複数の異なるコンピュータシステム上で動作する1つ又は複数のコンピュータプログラムによって種々の時点で実施される1つ又は複数の別々のプロセスに分離されてもよい。以下の各節で、システム動作についてさらに詳細に述べる。0087本例では、図5に示すシステムは、オーディオプログラム32を入力として受け取ってキューシート34を出力するコンピュータサーバシステム30であると仮定する。コンピュータシステムは、1つ又は複数のプロセッサ42、プログラム及びデータのためのランダムアクセスメモリRAM44、データベース46、並びに、図5に示されていない、入出力インタフェースや電源など他の従来のコンピュータシステム機構を備える。参照データベース460088データベース46は、いくつかの段階でソース音楽ファイルの集まりから構築される。0089例示的な一実施形態では、データベースは、以下のプロセスによって生成される:1.各ソース音楽ファイルが、例えば1サンプル当たり16ビットで、可能ならステレオで、不可能ならモノラルで、例えば12kHzでサンプリングされた、プレーン.WAVフォーマットに変換される。左チャネルと右チャネルとを含むステレオオーディオが、合計左右チャネル及び差分左-右チャネルに変換される2.ソースファイル名の番号付きリストを含むファイル例えばsrclistと呼ばれるが作成される。ファイルの各行は、一意の識別番号トラックID又はセグメントIDと、それに続くスペースと、それに続くファイル名とを含むことができる3.ソース音楽トラックからハッシュが生成されて、ソーストラックのハッシュを含むファイル例えばrawseginfoと呼ばれるが作成される。srclistからのトラック名情報を含む補助ファイル例えばrawseginfo.auxと呼ばれるが生成される4.ハッシュが、トラックID及び時間順にソートされる5.3次テストデータが生成され、3次テストデータ中へのインデックスが作成されて、マッピングされたrawseginfoファイルが形成される6.マッピングされたrawseginfoファイルが、ハッシュ値の小さい順にソートされる7.第1のクラスタインデックス以下のフォーマット記述参照が生成される8.補助データファイル例えばauxdataと呼ばれるが生成される。補助データファイルは、キューシート出力の中でファイル名を表示するのに使用される9.次いで、様々なファイルがデータベースに組み立てられる1千万秒のオーディオのデータベースを扱うように設計されたシステムの例示的な一実施形態の場合、後で論じる様々なシステムパラメータが、以下のように設定される:-最大葉サイズ=400-第1のクラスタ深度=20。0090しかし、これらがシステムパラメータの例に過ぎず、異なる実施形態が異なるパラメータを採用することになることに留意されたい。例えば、より大きいデータベースの場合、1億秒のオーディオに対しては第1のクラスタ深度を例えば約23又は24ビットに増加させ、10億秒のオーディオに対しては約26又は27ビットに増加させることができる。後でより詳細に述べる例では、24ビットの第1のクラスタ深度が仮定される。0091例示的な一実施形態では、ファイルサイズを管理可能に維持するために、使用される様々なデータ構造が、データベースの一部として記憶されるようにバイト及びビットにパックされる。生ハッシュ0092例示的な一実施形態では、生ハッシュが、6バイト又は48ビットとして記憶される。最上位ビットは、1次データベースルックアップに使用されるビットである。データベースの葉及びrawseginfo0093データベース中の各葉は、rawseginfo構造のシーケンスを含む。分析されることになるプログラムもまた、データベース中でルックアップが行われる前にrawseginfo構造のシーケンスに変換される。0094各rawseginfo構造は、生ハッシュを保持し、それと共に、どこから来たかについての情報そのトラックID、及びトラック内でのその位置。それぞれ4バイトとして記憶されると、2次テスト情報の16バイトフィールドとを保持する。0095最初の生成時は、位置情報は、約20ミリ秒の単位で測定された、トラックの開始に対して相対的なハッシュの時間を示すように設定される。データベース構築手順の間に、この値は、3次テストデータマッピングされたrawseginfo中への直接オフセットで置き換えられる。0096rawseginfoデータ構造は、BFFbigflatfileと呼ばれるフラットファイル構造でハッシュの順に順次記憶される。各葉は、ハッシュの最初のddepth個のビットが等しいrawseginfoデータ構造で正確に構成されたBFFの連続的な下位セクションであり、dは、各ケースで、葉の中のrawseginfoデータ構造の数が適切な最大葉サイズシステムパラメータ未満であるように選ばれる。深度値の選択は、まずBFFを、第1のクラスタ深度システムパラメータの値に設定された深度値をそれぞれ有する葉に分割することによって実施することができる。次いで、最大葉サイズシステムパラメータを超えるサイズを有する深度値dの葉があれば、その葉を、深度値がそれぞれd1である2つの葉に分割することができる。この分割手順が、最大葉サイズシステムパラメータを超えるサイズの葉がなくなるまで繰り返される。0097図6は、データベース46の構造と、プログラムオーディオから導出された各ハッシュに関連するルックアップとの概観を提供する概略図である。0098データベースの葉へのインデックスには、2つのレベルのインデックスがある。0099上に論じたように、データベース46は、非一様な深度の2分木の形をとる。0100データベースの索引付けを単純化するために、各葉は、少なくとも第1のクラスタ深度パラメータ62の深度、例えば24ビットの深度を有する。木の、第1のクラスタ深度のノードよりも上の部分は、クラスタと呼ばれる。2F個のクラスタがあり、F=第1のクラスタ深度であり、これらの各クラスタはBFF74の連続的なセクションに対応し、BFF74はいくつかの葉72を含む。0101図6の左上に、プログラムハッシュ60を示す。いくつかの最上位ビットパラメータ第1のクラスタ深度62によって設定されるが、可変深度の木の形状に関する情報を含むRAMベースのインデックス66第1のクラスタインデックス中へのオフセットとして使用される。データベースインデックス66の最上レベル68は、1クラスタ当たり1つのエントリを含む。このエントリは単純に、第2のインデックス中の可変長レコード70をポイントし、レコード70は、そのクラスタに関する情報を含む。プログラムハッシュからのさらに他のビットを使用して、第2のインデックスによって形成される木の最後の少数のノードが横断される。図示の例では、さらに3ビット101がとられる。図6に示す木構造に従えば、これらのビットのうちの第1のビットが0であったとすると、総計2ビットしかとられなかったことになる。RAMベースの第1のクラスタインデックスに記憶された情報は、葉72についての対応するデータベースレコードを直接見つけるのに十分である。0102このように、第2レベルのインデックスは、クラスタ中の2分木の形状と、2分木内の葉のサイズとを記述する。エントリは、以下によって構成される:iこのクラスタのデータが開始するBFF74中へのオフセットiiクラスタ中の2分木の形状の符号化。これは、木の深度優先横断で遭遇する順序で考えた場合の、木の各ノード内側及び葉につき1ビットの、ビットストリームである。ノードが内側である場合は、ビットは0であり、ノードが葉である場合は、ビットは1である。ビットストリームは、必要なら、最後のバイトの終わりまで0ビットでパディングされるiiiほとんどのサイズが単一バイトで表現されるような圧縮形で符号化された、木の深度優先横断で遭遇する順序の、クラスタ中の各葉72のサイズ。0103エントロピーのほとんどないハッシュのみをクラスタが含むすなわちクラスタが比較的大きいような少数のケースでは、特別なフラグ値が、上記ii及びiiiに取って代わることができ、対応するBFFエントリは索引付けされない。0104例示的な一実施形態では、両方のレベルのインデックス66/70は、サーバシステム中のRAMに納まるように設計され、それにより、どんなデータベース葉の内容も、BFFへの単一のランダムアクセスでフェッチすることができる。0105BFF中では、各一致ハッシュと共に、スペクトログラムから導出されたさらに他の情報が、プログラムハッシュに関して前に述べたのと同様にして記憶される。2次テスト段階では数百個の一致しか考慮されないことになるので、距離メトリックを使用して、プログラムと、1次テスト段階で識別された参照トラックとの間に良好な一致が実際にあるかどうか判定することができる。このようなメトリックをデータベース全体にわたって評価したとすれば、計算時間的に法外に高くついたであろう。前に示したように、このテストに対するしきい値は、ごく少数、おそらくはわずか1つか2つの潜在的一致しか合格しないように設定される。0106単一のランダムデータベースディスクアクセスから抽出される値をさらに増大させるために、適切な圧縮アルゴリズムを使用して2次テスト情報を圧縮することができる。01073次テスト情報は、トラックID順の3次テストデータ76構造のシーケンスと、そのトラック内の時間オフセットとからなる。これらはそれぞれ、単一バイトとして記憶された、前のエントリからの時間オフセット約20ミリ秒単位と、生ハッシュとを含む。0108データベース46は、各トラックの開始点を提供する、3次テストデータ76中へのインデックス78を含む。このインデックスは、RAMに収まるように十分に小さく設計され、したがって、3次テストデータのどんな所望のアイテムも、データベースファイルへの単一のランダムアクセスでフェッチすることができる。3次テストデータインデックス76中へのエントリを定義するデータ80には、BFF74中の2次テストデータ82が提供される。0109データベースアクセス時間を短縮するために、データベースは、従来のハードディスクよりも固体ディスク上で保持されるのが有利である。その理由は、ソリッドステージディスクのランダムアクセス又はシーク時間は通常、従来のハードディスクよりもおよそ百倍速いからである。データベースサイズが許容する場合、全ての情報をコンピュータのRAMに記憶することができる。さらに、示したように、可変深度の木構造では、ハッシュのビットを必要なだけとって、実施される2次テストの回数を設定しきい値例えば数百未満に低減することができる。0110特定の例示的な実施形態について上述したが、他の実施形態では、修正及び追加も想定される。ハッシュ関数0111例えば、様々な頑強性の程度をもたらすようにハッシュ関数を構成することができ、例えばそれにより、ハッシュの頑強性を完全一致データベースルックアップに関して最大限にするように、ハッシュ内のビットの順序を選ぶことができる。ケプストラム型ハッシュ係数に加えて、他のピッチシフト不変のエントロピーソースを、本格規模のデータベースと共に使用することもできる。データベース木0112上の例では、データベース木構造70は、2進ベースで編成される。しかし、他の例では、ノードの子の数は、2以外であってもよく、実際、木全体にわたって変動してもよい。この手法を使用して、葉のサイズの均等化をさらに容易にすることができる。別法として又は追加で、ノードの子ごとに、例えば2分木中のノードの左右両方の子ごとにハッシュを記憶することができる木構造を使用してもよいスピルツリーspilltreeと呼ばれる。重複トラックの識別0113任意選択で、重複した音楽セクションがないかどうかトラックデータベースを探索することができる。次いで、一意のセクションセグメントと呼ぶことにするが、前述のようにデータベースに記憶されて識別されることになる。後続の処理段階で、認識されたセグメントのリストをトラックのリストに変換することになる。このような手法は、さらに前処理を必要とするであろうが、データベースの記憶要件を低減することになり、リアルタイム処理を加速することができる。絶対時間情報0114前述の実施形態では、3次テストデータエントリについての絶対時間が、そのセグメントの開始からエントリまで前方に走査して時間デルタを累算することによって決定される。任意選択で、絶対時間マーカを3次テストデータエントリのシーケンスに含めることができる。データベースの間引き01152次テストデータベースのサイズを縮小するために、データベースの間引きを使用することができる。これは、ハッシュのハッシュを計算して、決定性方式でハッシュの固定部分を廃棄することを伴う。例えば、データベースを3分の1に間引くには、以下の修正を採用することができる。生成された各ハッシュにつき、データベース中で完全一致させることが必要になるビットが、整数として考慮される。この整数が3でちょうど割り切れない場合は、このハッシュは廃棄される。すなわち、ソーストラック材料から構築されたデータベースに含められない。同様に、プログラム材料を処理する際にこの基準を満たさないハッシュに遭遇した場合は、このハッシュがデータベース中にないであろうことがすぐにわかり、したがってルックアップは実施されないことになる。ハッシュを受容又は拒否するための完全一致に必要とされるビットに応じた決定性基準が使用されるのであり、単純に固定確率でランダムに受容又は拒否するのではない。その理由は、後者の手法は、より大きい間引き率では特に、ハッシュヒット率に対して、よりずっと大きい悪影響を有することになるからである。代替実施形態0116前述の実施形態は、例に過ぎにない。特許請求の範囲の趣旨及び範囲内で、代替実施形態を想定することができる。0117例えば、各図に関して述べた例示的な実施形態では、1次評価は、ルックアップテーブル中のエントリに対してソースベクトルの数字の完全一致を実施することを含み、ルックアップテーブル中の各エントリは、参照ベクトルのグループに関係する。次いで、2次評価は、ソースベクトルと参照ベクトルのグループのそれぞれとの類似度を決定して、ソースメディアコンテンツを参照メディアコンテンツと照合するための候補であるいずれかの参照ベクトルを識別することを含む。次いで、3次評価は、1つ又は複数のさらに他のソースベクトルと1つ又は複数のさらに他の参照ベクトルとの類似度を決定することを伴い、さらに他のソースベクトル及びさらに他の参照ベクトルのそれぞれは、ソースベクトル及び候補参照ベクトルからそれぞれ時間的な隔たりがある。2次及び3次評価は、参照ベクトルのデータベースを保持する記憶装置へのランダムアクセスを必要とする。参照ベクトルのデータベースは、かなりのサイズ、例えば約10テラバイトよりも大きいサイズとすることができることに留意されたい。0118スタンドアロンの又はネットワーク化されたコンピュータシステム、例えば1つ又は複数のプロセッサと共有記憶装置とを備えるコンピュータシステムによって形成された装置を使用して処理が実施される場合、データベースを固体メモリデバイスSSDに保持して処理速度を上げ、それにより2次及び3次処理段階を加速することが有利である。しかし、このような記憶装置は、現在は高価である。ディスク記憶装置など、より低速且つ低コストのデバイスを使用して、処理をこのようにして実施することができるが、こうすると、参照データベースが大きい場合には特に、認識プロセスが遅くなる可能性がある。0119別の代替方法は、処理にアレイ手法又はクラウド手法を採用する装置を使用することであり、この場合、処理タスクは、複数のコンピュータシステムに分散されて例えばバックグラウンドタスクとして動作し、クラウド処理の結果はホストコンピュータシステム中で協調がとられる。0120さらに他の手法も想定することができ、この手法では、ソースプログラムからソースベクトルのソースデータベースが生成され、次いで、線形又はストリーミング方式で、参照データベースの参照メディアがソースデータベースと照合される。これは以下の利点を有する。すなわち、例えばラジオ局からの1日の番組の、ソースベクトルのソースデータベースを、ランダムアクセスメモリの数ギガバイトに保持し、次いで、参照データベースを、低コストの記憶装置、例えばディスクやテープからストリーミングし、比較プロセスを低コストのバッチ方式で実施することができる。したがって、このような手法を使用して、ソースプログラム材料例えば1つのラジオ番組からの、又は適切な期間例えば1時間、1日のうちの一部若しくは全部などの番組からのについてのソースベクトルのソースメディアデータベースを、図6の参照ベクトルの参照メディアデータベースについて述べたようにして生成することができる。ソースベクトルは、ハッシュ値の小さい順にソートされて、ハッシュテーブル中で、又は図6の参照ベクトルの参照メディアデータベースについて述べたのと同様のデータベース構造で、ランダムアクセスメモリに記憶することができる。次いで、参照メディアデータベースから参照ベクトルを順次ストリーミングすることによってこれは、ディスクやテープなどの低コスト記憶装置の場合、ランダムアクセスよりもずっと速い、参照ベクトルをソースメディアデータベースと比較することができる。このプロセスは、ソースデータベーステーブル中のエントリに対して各参照ベクトルの数字の完全一致を実施する1次評価を含むことができ、ソースデータベーステーブル中の各エントリは、ソースベクトルのグループに関連する。次いで、2次評価は、現在の参照ベクトルとソースベクトルのグループのそれぞれとの類似度を決定して、ソースメディアコンテンツを参照メディアコンテンツと照合するための候補であるいずれかのソースベクトルを識別することを含むことができる。次いで、3次評価は、1つ又は複数のさらに他のソースベクトルと1つ又は複数のさらに他の参照ベクトルとの類似度を決定することを伴うことができ、さらに他のソースベクトル及びさらに他の参照ベクトルのそれぞれは、ソースベクトル及び候補参照ベクトルからそれぞれ時間的な隔たりがある。2次評価は、ソースベクトルのデータベースを保持する記憶装置へのランダムアクセスを必要とすることになるが、このデータベースは比較的小さいので、ランダムアクセスメモリに保持することができる。3次評価は、ソースベクトルのデータベース及び参照ベクトルのデータベースを保持する記憶装置へのアクセスを必要とすることになる。一実施形態では、参照ベクトルのデータベースは、自然な順序で、すなわちトラックごとに記憶され、各トラック内では、ベクトルは時間順に記憶される。この実施形態では、3次評価に含まれるルックアップは、データベース中の隣接エントリに関係することになり、したがって、記憶装置への順次アクセスを使用してアクセス時間を短縮することができる。代替の一実施形態では、参照ベクトルのデータベースは、2次テストを実施する目的でハッシュ値の小さい順に記憶され、3次評価のための候補のセットは、3次テストを実施する目的で、収集されてトラック番号によって記憶され、それにより記憶装置への順次アクセスを使用することが可能になる。