オーディオレコーディングVKontakteのインデックス作成のアーキテクチャとアルゴリズム

VKontakteのすべてのオーディオレコーディングで類似のトラックの検索がどのように配置されるかについて説明します。

なぜこれがすべて必要なのですか？

本当にたくさんの音楽があります。 大量-これは4億トラック以上で、重量は約4 PBです。 VKontakteから64 GBのiPhoneにすべての音楽をダウンロードし、それらを互いの上に置くと、エッフェル塔の上に塔ができます。 毎日、このパイルにさらに25台のiPhoneを追加する必要があります。つまり、1.5 TBのボリュームを備えた15万件の新しいオーディオレコーディングです。



もちろん、これらのファイルのすべてが一意であるとは限りません。 各オーディオには、アーティストに関する情報と名前（オプションで、テキストとジャンル）があり、ユーザーが曲をサイトにアップロードするときに入力します。 事前調整なし。 その結果、同じ曲の異なる名前、リミックス、コンサート、スタジオ録音で同じ曲を取得し、もちろん、完全に間違った名前のトラックを取得します。



同じ（または非常に類似した）オーディオレコーディングを正確に見つける方法を学べば、たとえば次のような利点があります。

• 異なる名前で1つのトラックを検索で複製しないでください。
• お気に入りの曲をより高品質で聴くことを申し出ます。
• 曲のすべてのバリエーションにカバーと歌詞を追加する
• 推奨のメカニズムを改善します。
• コンテンツ所有者の苦情の処理を改善します。

おそらく最初に頭に浮かぶのは、ID3タグです。 各mp3ファイルにはメタデータのセットがあり、この情報は、ユーザーがトラックのロード時にサイトのインターフェースで指定したものよりも優先順位として考慮することができます。 これが最も簡単なソリューションです。 また、あまり良くありません-タグは手動で編集できますが、必ずしもコンテンツに対応しているとは限りません。



したがって、私たちが持っているファイルに関連するすべての情報は人間に依存しており、信頼できない場合があります。 そのため、ファイル自体を取得する必要があります。



ファイルの内容のみを分析しながら、聴覚と同じまたは非常に似ているトラックを識別するタスクを設定します。

誰かがすでにこれを行っているようです？

同様の音声を検索することは非常に人気のある話です。 すでに古典的なソリューションは、シャザムからハウリング狼を研究している生物学者まで、連続して使用されています。 アコースティックプリントに基づいています。



音響指紋は、物理的特性を説明する一連の値の形式でのオーディオ信号の表現です。



簡単に言えば、指紋には音に関する情報が含まれており、この情報はコンパクトです。そのボリュームは元のファイルのボリュームよりもはるかに小さくなっています。 聴覚に似ている曲は同じプリントを持ち、逆もまた同じです。音が異なるプリントは一致しません。



まず、既製のC ++ソリューションの1つを使用して、音響指紋を生成しようとしました。 彼らはそれを検索し、実際のファイルでテストし、サンプルのかなりの部分で結果が悪いことに気付きました。 同じトラックが、イコライザー、バックグラウンドノイズまたはジングルの追加、別のトラックのフラグメントとの接着によって正常に「マスク」されます。



次のようになります（元のトラックと比較して）。







ライブパフォーマンス







エコー







リミックス



これらのすべての場合において、人はこれが全く同じ構成であることを容易に理解します。 同様の歪みを持つ多くのファイルがあり、それらで良い結果を得ることができることが重要です。 指紋ジェネレーターの独自の実装が必要であることが明らかになりました。

指紋生成

さて、mp3ファイル形式のオーディオ録音があります。 コンパクトな印刷にするにはどうすればいいですか？



このファイルに圧縮されているオーディオ信号をデコードすることから始める必要があります。 MP3は、PCM形式（パルスコード変調）でエンコードされたオーディオデータを含むフレーム（ブロック）のチェーンです。これは、非圧縮のデジタルサウンドです。



MP3からPCMを取得するには、CのlibmadライブラリとGoの独自のラッパーを使用しました。 その後、彼らはffmpegの直接使用を選択しました。



いずれにせよ、結果として、振幅の時間依存性を表す値の配列の形式のオーディオ信号が得られます。 このようなグラフの形で想像できます：



音声信号



これは耳に聞こえる音です。 人は全体としてそれを知覚することができますが、実際には音波は異なる周波数の多くの基本波の組み合わせです。 いくつかの音符で構成される和音のようなもの。



信号に含まれる周波数、特にその中で最も「特徴的な」周波数を知る必要があります。 このようなデータを取得する標準的な方法である高速フーリエ変換（FFT）を使用します。



数学的装置の詳細な説明は、この記事の範囲外です。 この出版物などで、デジタル信号処理の分野でのフーリエ変換の適用について詳しく知ることができます。



実装ではGO-DSP（デジタル信号処理）パッケージ、つまりgithub.com/mjibson/go-dsp/fft （実際にはFFTおよびgithub.com/mjibson/go-dsp/window ）をハンナウィンドウ関数に使用します。



出力では、一連の複素数を取得します。これは、平面に転送されるときにスペクトログラムと呼ばれます。



スペクトログラムは、信号の時間、周波数、および振幅の3つの音響測定値すべてを視覚的に表現したものです。 特定の時点における特定の周波数の振幅の値を表します。



例：



スペクトログラム参照トラック



時間はx軸に沿ってカウントされ、y軸は周波数を表し、振幅値はピクセルの色の強さで示されます。 周波数が均一に増加する「参照」信号のスペクトログラムを図に示します。 通常の曲の場合、スペクトログラムは次のようになります。







通常のトラックスペクトログラム



これは、オーディオトラックのかなり詳細な「ポートレート」であり、元のトラックを（特定の近似値で）復元できます。 リソースの観点から見ると、このような「ポートレート」を維持することは完全に不採算です。 私たちの場合、これには10 PBのメモリが必要になります-オーディオ録音自体の重量の2.5倍です。



このトラックの最も特徴的な値のみを保持するために、スペクトルの強度に基づいてスペクトログラムのキーポイント（ピーク）を選択します。 その結果、データ量は約200倍削減されます。







スペクトログラムのキー値



このデータを便利な形式で収集することは残っています。 各ピークは、周波数と時間の値という2つの数値によって一意に決定されます。 トラックのすべてのピークを1つのアレイに追加すると、目的の音響インプリントが得られます。

指紋の比較

2つの条件付きトラックに対して上記のすべてを実行したと仮定します。これで、指紋が得られました。 元のタスクに戻ります-これらのトラックを指紋の助けを借りて比較し、それらが類似（同一）かどうかを調べます。



各フィンガープリントは値の配列です。 それらを要素ごとに比較してみて、タイムライン上のトラックを互いに対してシフトします（たとえば、トラックの開始時または終了時の無音を考慮するためにシフトが必要です）。 一部のオフセットでは印刷物の偶然が多くなり、その他のオフセットでは少なくなります。 次のようになります。







共通のフラグメントと異なるトラックを持つトラック



真実のように聞こえます。 共通のフラグメントを持つトラックの場合、このフラグメントが見つかり、特定の時間オフセットでの一致数の急増のように見えます。 比較の結果は「類似度係数」であり、バイアスを考慮した一致の数に依存します。



指紋を生成および比較するためのGoライブラリのソフトウェア実装は、 GitHubで入手できます 。 独自の例のグラフと結果を見ることができます。



次に、これらすべてをインフラストラクチャに統合して、何が起こるかを確認する必要があります。

建築

VKアーキテクチャの指紋生成とインデックス作成/検索エンジン



指紋を生成するエンジンは、各サーバーで動作して音声をダウンロードします（現在、約1000個あります）。 入力としてmp3ファイルを受け取り、処理（デコード、FFT、スペクトルのピークの強調表示）し、このオーディオの音響インプリントを生成します。



負荷はファイルレベルで並列化されます。各トラックは個別のゴルーチンで処理されます。 5〜7分の平均オーディオ録音の場合、処理には2〜4秒かかります。 処理時間は、オーディオの継続時間の増加とともに直線的に増加します。



すべてのトラックの音響プリントは、多少の精度の低下はありますが、約20 TBのメモリを占有します。 この大量のデータはどこかに保存され、そこから何かを見つけるためにすばやくアクセスできる必要があります。 この問題は、別個のインデックス作成と検索エンジンによって解決されます。



指紋データを逆（逆）インデックスの形式で保存します：





逆索引



速度を上げてメモリを節約するために、印刷物の構造を活用しています。 指紋は配列であり、その個々の要素（ハッシュ）を考慮することができます。これは、覚えているように、スペクトルのピークに対応しています。



「トラック」→「指紋」という通信を保存する代わりに、各指紋をハッシュに分割し、「ハッシュ」→「指紋があるトラックのリスト」を保存します。 インデックスは間引かれ、インデックス形式の20 TBの指紋は約100 GBを占有します。



実際にはどのように機能しますか？ 検索エンジンは、音声録音のリクエストを受け取ります。 あなたはそれに似たトラックを見つける必要があります。 この音声のフィンガープリントは、リポジトリからダウンロードされます。 このフィンガープリントのハッシュを含む行がインデックスで選択されます。 頻繁に遭遇するトラックは対応する行から選択され、リポジトリから指紋がダウンロードされます。 これらのフィンガープリントは、ソースファイルのフィンガープリントと比較されます。 その結果、対応する一致フラグメントおよびこれらのフラグメントの条件付き「類似度係数」を持つ最も類似したトラックが返されます。



インデックス作成および検索エンジンは、純粋なGoで記述された32台のマシンで実行されます。 ここでは、goroutines、内部ワーカーのプールが最大限に使用され、ネットワークで動作し、グローバルインデックスが並列化されます。



これで、すべてのロジックの準備が整いました。 すべての音楽のフィンガープリントを収集し、インデックスを作成して作業を始めましょう。 ところで、どれくらい時間がかかりますか？



インデックス作成を開始し、数日待って、期限を推定しました。 判明したように、結果は約1年になります。 この期間は受け入れられません-何かを変更する必要があります。



可能な限りsync.Poolを実装し、2か月間刻みました。 新しい期間：10か月。 まだ長すぎます。 より良いです



データ型を最適化します-インデックスによるトラックの選択は、配列をマージすることにより実装されました。 配列の代わりにコンテナ/ヒープを使用すると、半分の時間を節約できます。 6か月の修了があります。 たぶんそれはさらに良くなるでしょうか？



標準インターフェイスの代わりにデータ型を使用するためにコンテナ/ヒープをシャープにし、さらに1か月間勝ちます。 しかし、これは私たちには十分ではありません（つまり、たくさん）。



コンテナ/ヒープの独自の実装を作成して、stdlibを修正します-マイナス2か月、合計3。最初の見積もりよりも4倍少ない！



最後に、Goバージョンを1.5から1.6.2に更新すると、最終結果が得られました。 インデックスの作成には2.5か月かかりました。

どうしたの？

実稼働テストでは、最初は考慮しなかったいくつかのケースが明らかになりました。 たとえば、再生速度がわずかに変更されたトラックのコピー：







加速トラック



リスナーにとって、これはほぼ同じことであり、わずかな加速は大きな違いとしては認識されません。 残念ながら、指紋比較アルゴリズムでは、このようなトラックは完全に異なると見なされていました。



これを修正するために、処理を少し追加しました。 これは、2つのプリントで最大共通サブシーケンス（最長共通サブシーケンス）を検索することで構成されます。 結局、振幅と周波数は変化せず、この場合、対応する時間の値のみが変化し、互いに続く点の一般的な順序が保持されます。





LCS



LCSを見つけることで、時間スケールでの信号の「圧縮」または「ストレッチ」の係数を決定できます。 その後、小さいので、通常どおり印刷物を比較し、見つかった係数をそれらの1つに適用します。



LCS検索アルゴリズムを使用すると、結果が大幅に改善されました。これまで指紋で検出されなかった多くのトラックが正常に処理されました。



別の興味深いケースは、フラグメントの一致です。 たとえば、その上にアマチュアボーカルが録音されたいくつかのポピュラーソングを除外します。







一致するトラックフラグメント



時間の比較結果をレイアウトし、トラックの各秒の一致数を調べます。 上の写真は、このマイナスの元のトラックと比較したマイナスを超えるアマチュア録音の例です。 一致しない間隔-ボーカル、一致のピーク-静寂（つまり、元のトラックに似たネットマイナス）。 このような状況では、一致するフラグメントの数をカウントし、一致の数自体から条件付きの「類似度係数」を計算します。



同様のトラックをクラスタリングした後、個々のクラスターは他のクラスターよりも大幅に大きくなりました。 何がありますか？ それらを正しく検討する方法があまり明確ではない興味深い状況があります。 たとえば、有名なハッピーバースデートゥユー。 この曲には数十種類のバリエーションがあり、祝福された人の名前だけが異なります。 それらは異なると見なされるべきですか？ 同じことは、異なる言語のトラックのバージョンにも当てはまります。 これらの歪みとその組み合わせは、打ち上げ段階で深刻な問題になりました。



これらの状況や他の一般的ではない状況を考慮して、メカニズムをほとんど変更する必要がありました。 現在、このような複雑なクラスターを含め、システムは適切に機能しており、新しい異常な変換に対応しながら改善を続けています。 架空の名前で、加速された、ジングル付きでボーカルなしの曲を見つけることができます。 このタスクは完了しました。そして、間違いなく、推奨サービス、音楽検索、およびオーディオセクション全体の開発に関する今後の作業で、複数回役に立つでしょう。



PSこれは、VKontakteの技術面についての長い間約束された一連の記事の最初の記事です。



Habrに加えて、ロシア語と英語でブログに公開します。 ここだけでなく、別のVKコミュニティでも記事の著者に質問することができます 。