DEIM Forum 2014 F9-4

大規模音声信号データベースに対する超高速部分一致近似検索手法
高田怜†

喜田 拓也†† 北海道大学 大学院情報科学研究科 〒 060–0814 北海道札幌市北区北 14 条西 9 丁目
E-mail: †{takada,kida}@ist.hokudai.ac.jp
あらまし

本稿では，大規模な楽曲信号データベースに対し，音声信号をクエリとして，任意の楽曲の一部分と近似的に一致する箇所を高速に検索する手法について論じる．提案手法では，楽曲の音声信号から抽出された音楽指紋に対して接尾辞配列を適用し，クエリ信号からサンプリングされた多数の小片を厳密一致で検索する．その結果を統合することで高速かつ精度の良い近似検索を実現している．この手法を実現し，歌唱者の異なる同一楽曲を検索する実験を行った．大規模なデータベースに対しての速度評価を行うために，実際の音声信号に加え，およそ 10 万曲分の人
工楽曲データベースを作成し，一般的な PC 上でそのデータベースに対する検索性能を評価した．その結果，84%程度の精度で，1 曲あたり 0.04 秒未満で検索できることを示した．
キーワード

音楽情報処理，楽曲検索，音楽指紋，接尾辞配列

1. は じ め に

音楽指紋は一般的に高次元のビット列である．高次元ビット同士を単純に比較計算しようとすると，計算にかかる時間が次

近年，iTunes [1] や YouTube [2]，ニコニコ動画 [3] などをは元数に対し指数的に増加するため，高速にマッチング検索を行じめとして，個人がデジタル上で扱うことのできる楽曲数がうということが難しい．本稿では，文字列検索で用いられる索非常に膨大になっている．これらのようなインターネット上の引構造である接尾辞配列 [18] を音楽指紋に適用する手法を提サービスでは，楽曲のアーティスト名や作曲者名などのメタ情

案する．また，10 万曲分の擬似データベースに対して歌唱者報が付加されていることが多い．しかし，個人の PC に保存さの異なる楽曲検索実験を行い，高速に楽曲を検索できることをれているような未整理なデータについてはそうとは限らない．

示す．

そのような状況において楽曲の情報が欲しい時，楽曲の音源
データのみを用いて，巨大な楽曲データベースに対しての検索が必要となる．

2. 音 楽 指 紋
音楽指紋とは，楽曲の音響信号データから得られる文字列

そこで，本稿では楽曲の音源のみを用いて，巨大な楽曲デー(ビット列）のことで，その楽曲の特徴を数キロビット程度の比

タベースに対して高速に検索を行うような手法を提案する．高較的小さいデータサイズで表現したものである．本稿では，楽速な検索を行う際に重要となるのは，楽曲の音源データを音楽

曲の同一性を判定するために用いる．音楽指紋から音響信号へ

指紋と呼ばれる小さなデータへ変換することである．音楽指紋の復元はできないが，音楽指紋を用いることで，元の楽曲デー

は，楽曲の音源データから得られるデータで，サイズが元の音

タをそのままデータベースとした時と比べ保持するデータ量が源データと比較して非常に小さいものとなっていることが特徴

小さくなる．

である．この音楽指紋を用いて，楽曲の高速な検索を実現する．

2. 1 音楽指紋の生成

楽曲の検索手法については，楽曲データ同士のマッチングや

本稿では，2002 年に Haitsma と Kalker [17] が提案した音楽

類似検索に関する手法が研究されている [4] [5] [6] [7] [8]．また，指紋をベースとするような音楽指紋を用いる．この音楽指紋は，信号処理分野でよく知られているフーリエ変換 [9] やメル周波

実際の楽曲の差異が，音楽指紋でのビット誤りに反映されるよ

数ケプストラム係数 [10] などのほか，音楽に関する研究としうな設計となっている．

て，特定のワードをクエリとした検索 [11], [12]，検索のために

まず，音響信号を先頭から順に，ある短い長さの区間で区切

音響データを MIDI に変換するもの [13]，ボーカルの声の質のりながら周波数解析を行う．この時の区間をフレームと呼ぶこ類似さに基づく検索 [14]，ユーザの好みをジャンルで学習したとにする．各フレームでの周波数の区切り方は対数スケールで上での検索 [15]，楽曲にタグ付けを行う [16] といったものがあ

行い，ひとつの領域がピアノの鍵盤の音のひとつに対応するよる．このように，楽曲データ同士のマッチング以外においてもうな周波数の区切り方をとる．あるひとつのフレームに着目す

楽曲検索のための様々な研究がなされている．

ると，周波数解析によって得られるデータは，区切られた周波

本稿では，楽曲を音楽指紋に変換した上で，音楽指紋同士の数ごとの音の強さである．フレームの数を N + 1，区切られる

マッチングを行うことで，楽曲同士のマッチングを実現する．こ

周波数の数を M + 1 とおくと，M + 1 次元のベクトルが N + 1

こで，楽曲の検索は，全く同じ音源ではなく歌唱者の異なる楽個並んだデータが得られる．このデータを行列 E とおく．E

曲同士のマッチング検索を行う．本稿では，2002 年に Haitsmaの要素 E(i, j) には，i 番目のフレームの，j 番目の高さの音のと Kalker が提案した音楽指紋 [17] をベースに，議論を行う．

強さが格納されている．i, j はそれぞれ [0, N ], [0, M ] の範囲をἼᙧ䝕䞊䝍

る接尾辞配列について解説する．

㡢ᴦᣦ⣠;‫Ϳܨ‬
ͳ
Ͳ
Ͳ

͙

͙

͙

Ͳ
ͳ

Ͳ
Ͳ

ͳ
ͳ

͙

Ͳ
Ͳ
ͳ

ͳ
Ͳ
ͳ

͙

Ͳ
ͳ
ͳ

͙

Ͳ
ͳ
Ͳ

ͳ
Ͳ

ͳ
ͳ

3. 1 文 字 列
文字列 (String) とは，アルファベット Σ 上の記号の列で‫ܯ‬ある．文字列 T を T = x0 x1 . . . xn−1 と表す (xi ∈ Σ, i =0, 1, ..., n − 1)．この時，文字列 T の長さは n である．また，
文字列 T の i 番目の文字から j 番目の文字を取り出すことでできる部分文字列を，T [i, j] と表す．さらに，終端の文字

ܰ
図1を含まない部分文字列を T [i, j) = T [i, j − 1] と表す．つま波形データの音楽指紋への変換．

り，T = x0 x1 . . . xn−1 のとき，T [1, 5] = x1 x2 x3 x4 x5 であり，

T [1, 5) = x1 x2 x3 x4 である．
とる．

3. 2 接尾辞配列

次に，E の隣接する成分同士の差分を求め，大きさが (M, N )となるような行列 E 0 を計算する．具体的には，

が提案したデータ構造である [18]．接尾辞配列は，文字列検索

E 0 (i, j) = E(i, j) − E(i, j + 1) − (E(i − 1, j) − E(i − 1, j + 1))(1)という計算を行う．この E 0 の値を用いて，次のような行列 Fを生成する．

1
F (i, j) =0E 0 (i, j) > 0 のとき，
E 0 (i, j) <= 0 のとき．

接尾辞配列 (Suffix Array) とは，1990 年に Manber と Myers
を高速に行うためのデータ構造である．
まず，接尾辞配列の生成に使われる接尾辞について述べる．
長さ n の文字列 T について，T の接尾辞 Si (i = 0, 1, . . . , n − 1)は以下のように定義される．

Si = T [i, n)(2)

つまり，ある接尾辞 Si は，文字列 T の i 番目の文字から最後までを取り出した部分文字列である．接尾辞は，長さ n の文字

この行列 F を音楽指紋とよぶ．F は各要素が 0 または 1 であ列に対して n 個存在する．また，接尾辞に対し，ある文字列のり，ビット行列となっていることがわかる (図 1）．

先頭から数文字を取り出したものを接頭辞と呼ぶ．

本稿の実験で使用する音楽指紋は，使用する周波数帯やフ文字列 T に対する接尾辞配列は，T の全ての接尾辞 Si を辞

レームのとり方などにおいて Haitsma と Kalker [17] が提案し書順にソートした時の接尾辞開始位置 i を並べた配列である．

たパラメータとは異なるものとなっている．具体的には，4. 節
で述べる．

3. 3 接尾辞配列上での検索
接尾辞配列の特徴として重要なのが，文字列 T 中に存在する

2. 2 音楽指紋を用いた楽曲のマッチング

任意の部分文字列の先頭の位置を，接尾辞配列の値で表現でき，

上記の手順によって生成された音楽指紋を用いて楽曲検索を

さらにその値が連続するということである．それは，接尾辞を行う方法について概説する．この音楽指紋は，全く同じ音源か

全て辞書順にソートして接尾辞配列を作ったためである．したらは全く同じ音楽指紋が生成されるが，例えばクエリの音源にがって，文字列 T 上に検索したい文字列が含まれているかどう

ノイズがのっているなどすると，同一の楽曲でも生成される音

か，また，T のどの部分に検索したい文字列が含まれているか

楽指紋は若干異なるものとなる．そのような音楽指紋の検索もを，接尾辞配列上で二分探索することで求めることができる．

可能とするためには，厳密に一致する音楽指紋を検索するので任意の部分文字列を元の文字列上を単純に線形探索する時と比はなく，多少の異なりを許容した類似検索を行う必要がある．

べ，高速に検索することができる．

ここで，楽曲同士の類似度を，音楽指紋同士のハミング距離として定義すると，楽曲を検索するという問題は，クエリの音楽

4. 提 案 手 法

指紋と最もハミング距離が小さくなるようなデータベース中の4. 1 手法の概要

音楽指紋をもつ楽曲を見つけ出す問題に帰着する．また，クエ

2. 章で述べたように，音楽指紋の検索とは，先頭の開始位置

リとなる音源が，楽曲のある一部分のみである場合も考慮するが一致しないビット列同士の類似検索である．本論文ではそのためには，音楽指紋同士の比較は，それぞれのデータを先頭部ようなデータの検索方法として，部分的に完全一致する箇所を分から比較するだけでは不十分である．最も単純に音楽指紋を探索し，完全一致する部分が多いものを全体的に類似している

検索する方法としては，クエリとデータベースの比較位置を 1と判断すると考える (図 2)．

フレームずつずらしながら，最もハミング距離の小さくなる場

本論文で使用している音楽指紋は，Haitsma と Kalker ら [17]

所を見つけ，その部分を内包する楽曲を答えとする方法が考えが提案した音楽指紋をベースとしているが，生成する際に使られる．しかし，それでは検索にかかる時間が膨大となるため，用する周波数帯とフレーム長を変更する．まず，使用する周

高速な検索を行うには何かしらの工夫が必要となる．

波数帯は，41.2Hz〜164.8Hz とする．これらは，筆者の先行研

3. 接尾辞配列
本節では，文字列の全文検索のための索引構造のひとつであ究 [19] によって，本稿で行う歌唱者の異なる楽曲の検索に適したものであることがわかっている．また，フレーム長は 0.1 秒とし，各フレームは重複させないものとする．さらに，後に接䜽䜶䝸䛾㡢ᴦᣦ⣠

Ͳ

͙
ͳ

ͳ

ͳ

Ͳ

͙

Ͳ
Ͳ

͙

ͳ

͙

ͳ

Ͳ

͙

Ͳ

ͳ

ͳ

図3

各フレームごとに 8 ビットをひとまとめにする．

Ͳ

ʹ᭤┠䛾
㡢ᴦᣦ⣠

ͳ᭤┠䛾
㡢ᴦᣦ⣠

␒┠䛾᭤䛾㡢ᴦᣦ⣠
݅

Ͳ

͙
͙

݅

െ ͳ␒┠䛾᭤䛾㡢ᴦᣦ⣠

ͳ

ಶ

ͺ

݅

ͳ

͙
͙

᏶඲䛻୍⮴䛧䛶䛔䜛㒊ศ䝕䞊䝍䝧䞊䝇ୖ

ಶ

ͺ

ͳ

͙
͙

ಶ

ͺ

൅ ͳ␒┠䛾᭤䛾㡢ᴦᣦ⣠

͵᭤┠䛾
᭱ᚋ䛾᭤䛾
㡢ᴦᣦ⣠ ͙ 㡢ᴦᣦ⣠᏶඲䛻୍⮴䛧䛶䛔䜛㒊ศ䛜ከ䛔э඲యⓗ䛻㢮ఝ䛩䜛㡢ᴦᣦ⣠
͙
図2

͙

͙

͙

͙

厳密に一致する部分が多い音楽指紋㐃⤖䛩䜛

尾辞配列を生成することを考慮し，ひとつのフレームに含まれるビット数を 24 とする．つまり，2. 節では M とおいていた周

図4

㐃⤖䛩䜛

全ての文字を各曲の境界も含めて横方向に全て連結する．

波数の高さの区切り数は M = 24 とし，各フレームごとに楽曲の波形データから 41.2Hz〜164.8Hz の部分を取り出す．次に，対数領域で 25 分割した後，式 (1)，(2) によって高さ 24 のビット列を生成する．以上のことから，長さ 200 秒の楽曲からは，
縦 24 ビット，横 2000 フレーム分の音楽指紋が生成されることになる．

4. 2 音楽指紋の接尾辞配列
接尾辞配列の生成に関して述べる．前述の音楽指紋は各フ
レームごとに 24 ビットのデータがある．これを，図 3 のように連続する 8 ビットごとに 3 つのセットに分割する．以降，このセットひとつを 1 バイトでコード化された文字とみなす．図

3 の右側のひとつの四角形がひとつの文字に対応する．つまり，各フレームごとに 3 つの文字が得られ，それぞれは周波数の高さで区切られている．この分割を全てのフレームについて行うと，データベース上の各楽曲は縦が 3 文字，横がフレーム数の行列データとなる．そして，全ての文字を横方向に連結し，さらにデータベース上の 1 曲目の最後の 3 つの文字と 2 曲目の最初の 3 つの文字を，同じ高さ同士で連結するといった操作を全ての楽曲の区切れ目で行う (図 4)．図 4 も図 3 と同様にひとつの四角形がひとつの文字に対応する．そうすると，データベー
ス全体が 3 本の長い文字列となる．その長い文字列において，それぞれ接尾辞配列を生成する．したがって，ここでは 3 つの接尾辞配列が生成されることになる．
クエリの音楽指紋において，先頭から j 番目のフレームの上から i 番目の高さの文字を xi,j と表す．クエリの音楽指紋のフレーム数を N とすると，i, j はそれぞれ i = 0, 1, 2，0 <=j<= N −1の範囲をとる．この i と対応するように，データベースの 3 つの接尾辞配列を SA0 , SA1 , SA2 と表すことができる．

4. 3 接尾辞配列上での検索方法
接尾辞配列を用いた音楽指紋の検索は，以下のような手順で行われる．

まず，クエリの音楽指紋からひとつの文字をランダムに取り出す．とり出された文字を xi,j とし，文字列 X を X = xi,j とおく．次に，SAi 上において，X を接頭辞として含む接尾辞を二分探索で見つけ出す．このとき，該当する接尾辞は複数ある
ことが考えられるので，その接尾辞の数 R1 を求める．接尾辞
配列の生成方法から，ここで探索される接尾辞は SAi 上で全て連続している．R1 と，あるしきい値 ∆ を比較する．この時，

R1 >= ∆ であるときは，続いて xi,j+1 を取り出し X の末尾に加え，文字列 X を X = xi,j xi,j+1 とする．そして SAi 上において，X を接頭辞とする接尾辞の数 R2 を新たに求める．この時，一致させる文字列が長くなっているので，R2 <= R1 である．xi,j+2 , xi,j+3 , · · · をひとつずつ X に加えながら以上の操作を繰り返し，Rl , l = 1, 2, · · · が ∆ 以下になったときに探索を終了する (図 5)．この時点で残っている接尾辞の先頭の文字を内包している楽曲に，1 点を加点する．ひとつの楽曲について複数の文字が残っていれば，残っていた分だけ点を加点する．
上述の，ある xi,j を取り出しデータベースの楽曲に加点するという操作を，ある一定数 S 回繰り返す．そして，最終的に最も加点数の多かった上位数曲を，クエリの楽曲と同一の楽曲であるとして出力する．

5. 実

験

本節では，前述の提案手法を用いて楽曲の検索実験を行う．

5. 1 実験に使用するデータ
データベースとして，7849 曲の楽曲データを用いた．この中には，一般的な J-POP 楽曲，ニコニコ動画や YouTube などの動画投稿サイトで公開されている VOCALOID 楽曲 (以下，VOCALOID 曲) などが含まれている．クエリとしては，

J-POP 曲から 78 曲，VOCALOID 曲から 100 曲，オフボー䝕䞊䝍䝧䞊䝇䛾᥋ᑿ㎡㓄ิ

䜽䜶䝸

ܵ‫ܣ‬଴

Ͳ

‫ݔ‬௜ ௝

ͳǡ‫ݔ‬௜ ௝ାଵ ‫ݔ‬௜ ௝ାଶ 䞉䞉䞉
ǡ

ܵ‫ܣ‬ଵ

ǡ

ʹ

ܵ‫ܣ‬ଶ

表1

各クエリの検索の正答率と検索にかかった時間 (7849 曲の DB)．

䝷䞁䝎䝮䛻ϭᩥᏐྲྀ䜚ฟ䛩ܵ‫ ܣ‬䛻ὀ┠䛩䜛

全体

サビのみ

オフボーカル

100%

100%

VOCALOID 曲

95.3%

86%

J-POP 曲

66.0%

57.7%

合計

84.4%

76.5%

ሺ‫ݔ‬௜ ௝ Ϳ
ǡ

௜

ܺൌ‫ݔ‬

௜ ǡ௝

1 曲あたりの検索時間 0.0176 秒 0.00586 秒

䞉䞉䞉ܺ䜢᥋㢌㎡䛸䛧䛶ᣢ䛴᥋ᑿ㎡ܵ‫ܣ‬௜ܴ ൐ ȟ 䞉䞉䞉 ܺ䜢኱䛝䛟䛩䜛ଵܺൌ‫ݔ ݔ‬௜ ǡ௝

音楽指紋の生成の際，音響データの解析には Muller らが公開している chroma toolbox [20] を用いた．また，接尾辞配列の生成には Yuta Mori が公開しているプログラム [21] を用いた．

௜ ǡ௝ାଵ

ܵ‫ܣ‬௜

ランキングの上位数曲を出力すると述べたが，本節では上位 10
曲を出力するとし，その中にクエリと同一の楽曲が含まれていܺൌ‫ݔ ݔ‬௜ ǡ௝௜ ǡ௝ାଵ‫ݔ‬ܴ ൐ ȟ 䞉䞉䞉 ܺ䜢኱䛝䛟䛩䜛

るときに検索は成功したと判断する．検索時間は，クエリの音ଶ௜ ǡ௝ାଶ

楽指紋で接尾辞配列を探索し始めてから答えが出力されるまでとする．実験に使用した計算機は，Intel Core i5 (2.5GHz)，メܵ‫ܣ‬௜

モリサイズ 8GB，OS は Ubuntu12.04 (64bit 版) である．

ܴ ൏ȟଷ䞉䞉䞉 ᥈⣴⤊

図 5 接尾辞配列を用いた音楽指紋の検索方法．

検索実験は，まず検索が間違いなく行われているかどうかの調査を行い，続いて検索精度を調査する．その次に，巨大なデータベースに対しての検索にかかる時間がどの程度であるかを調査する．

カル (伴奏のみ) の曲 22 曲の計 200 曲を用意した．これらのク

5. 2 システムの調査

エリ用楽曲は，J-POP 曲，VOCALOID 曲は，同一の楽曲がまず，検索システムがビット列を間違いなく検索できている

データベースに存在するが，その楽曲とは歌唱者が異なるといかを確認する．データベースとして用意した楽曲から，200 曲

うデータである．また，オフボーカル曲は，データベースに存を複製し，それをクエリとして検索実験を行う．つまり，ここ在する楽曲からボーカルを取り除いたもの (いわゆるカラオケ

ではクエリと全く同じビット列を検索することになる．

バージョン，Instrumental バージョン) となっている．そのた結果としては，全てのクエリにおいて，同一の楽曲をデータ

め，ここでの実験は全く同じ音楽データの照合ではなく，同一ベースから発見することに成功した．検索システムが，類似の楽曲ではあるが，歌唱者の異なる楽曲を検索するということ

ビット列を間違いなく発見できていることを確認した．

を行う．歌唱者が異なるため，歌唱の録音状況なども異なっている．

5. 3 類似楽曲の検索精度
続いて，歌唱者の異なる楽曲を用いた検索実験を行う．ここ

データの収集は，主にニコニコ動画や CD 音源などを用い

で，文字を選び加点するという操作を繰り返す回数 S を 2000，て行った．クエリの J-POP 曲と VOCALOID 曲はニコニコ

接尾辞配列の幅 ∆ を 15 とする．これらのパラメータは，予備

動画から，オフボーカルの楽曲は CD から取得した．この時，実験によって検索時間と精度のバランスを考慮して決定した．

J-POP 曲と VOCALOID 曲は，原曲からキーを変えずに歌唱

また，楽曲全体，サビのみの双方で，検索にかかる時間を測定されているものを選んだ．このうち J-POP 曲については，著した．

作権の問題から，音質が悪い・バンドのアレンジが異なってい各クエリについて 20 回の検索を行った．その時の正答率と計るなど，原曲とはかなり録音状態が異なるものになっている．

算時間の平均を表 1 に載せる．まず，検索精度について，オフ

一方，オフボーカルの楽曲は，データベースにある楽曲と同一ボーカル曲は，クエリの音源が CD から得られているものといの CD から入手したものであるため，クエリとして用いるデー

う事もあり，クエリが楽曲全体，サビのみのどちらでも検索精タの中では最も良い条件のものである．

度はとても良い結果となった．次に VOCALOID 曲と J-POP

さらに，クエリとして用意した楽曲は，楽曲全体のものと他曲については，サビのみとした時の正答率が楽曲全体で検索しに，楽曲のサビ部分を抽出したものの 2 種類を用意した．これた時と比べ下がる結果となった．これは，ボーカルの違いが音

は，イントロや間奏など，歌唱の無い部分が検索精度に影響を楽指紋の違いに影響し，それが検索精度に影響を与えるという

与えてしまう可能性があるということを考慮したためである．

予想を裏付けているといえる．また，特に J-POP 曲での正答データベースの楽曲の長さは平均で 3 分 49 秒，クエリのデー

率が全体，サビのみどちらでも特に低下している．これは，クタは楽曲全体のもので平均 4 分 19 秒，サビ部分を抽出したもエリとして用意した音源の録音状況が悪いなど，音源的な “綺ので平均 27 秒程度であった．データベースとクエリので平均麗さ” が影響してしまったと考えられる．同様に VOCALOID

時間に差があったのは，データベースとして用意した楽曲の中

曲は，J-POP 曲ほどではないが，データベース中の原曲とはに 2 分程度の短い曲が含まれているなどしたためである．

録音状況が異なっているため，正答率の低下にある程度影響が表 2

各クエリの検索の正答率と検索にかかった時間 (107849 曲の

ちやすくなったためだと考えられる．

DB)．
全体

サビのみ

オフボーカル

100%

100%

VOCALOID 曲

94.5%

88%

J-POP 曲

66.3%

56.4%

合計

84.1%

77%

1 曲あたりの検索時間 0.0351 秒 0.0103 秒

6. 結

論

本稿では，楽曲の高速な検索手法について，歌唱者の異なる音源データを用いて議論した．その結果，我々の提案する手法
は，10 万曲分を超える擬似的な楽曲データベース上において，1 曲あたり 0.04 秒未満で検索を可能とすることが確認できた．
今後の課題としては，本稿の実験で用いた J-POP 曲のようあった．これは，クエリと正解データが同じ CD から抽出されたオフボーカル曲の結果が良かったことについてもいえる．検な，汚い音源を用いても正確に検索を行えるように検索手法を改良することが挙げられる．

索精度は，クエリの音源データの音源的な “綺麗さ” の差が，そのまま全体的な結果の差として出ることとなった．
検索時間について，サビのみでの検索が全体での検索よりも時間が小さいのは，サビのみのものはクエリ全体で文字数が2000 未満のものが多く，同じ文字を使用して検索することはな

文

[1]
[2]
[3]
[4]

いため，2000 文字を使用する前に検索が終了してしまったためである．7849 曲のデータベースに対し，楽曲全体での検索にかかる時間が 0.02 秒未満となった．
参考までに，同じく接尾辞配列を用いた楽曲検索手法を提案[5]

している Xiao ら [7] の実験では，Intel Core i7 (1.73GHz)，メ
モリサイズ 4GB の計算機が用いられ，楽曲の検索に要した時間は 8740 曲のデータベースに対し 1 曲あたりおよそ 0.4〜0.6[6]秒程度とのことであった．同じ計算機，実験データを用いた比較が行えなかったのは，[7] の著者から提供を受けた検索システ[7]

ムが，楽曲の解析から検索までを一度に全て行う仕様となっており，検索部分のみの時間計測を行えなかったためである．

5. 4 検 索 速 度[8]続いて，巨大なデータベースに対しての検索速度を調査する．
実際の音楽データを多数集めることが困難であったため，乱数によって音楽指紋を擬似的に生成することで，巨大なデータ[9]

ベースを作成した．ここでは，擬似音楽指紋として 10 万曲分の音楽指紋を生成し，前小節までで使用したデータベースに追加する形で新たなデータベースとした．したがって，実際に使用するデータベースは合計で 107849 曲分のものとなる．デー[10]

タベースの 1 曲あたりの長さは 3 分 49 秒であったため，ここで生成する擬似音楽指紋は 1 曲あたりのフレーム数を 2300 と[11]した．したがって，文字数は 6900 である．
各クエリについて 20 回の検索を行った．その時の正答率と[12]計算時間の平均を表 2 に載せる．
楽曲全体での検索で 1 曲あたり 0.035 秒，サビのみでの検索[13]

で 1 曲あたり 0.011 秒という結果となった．7849 曲のデータ
ベースに対しての検索時間は 0.018 秒であり，およそ 14 倍の大きさのデータベースに対して検索時間は 2 倍程度で抑えられるという結果となった．これは，接尾辞配列上の探索を二分探[14]索することで，検索を対数時間のオーダーで抑えていることが理由として挙げられる．また，精度についても，7849 曲のデー
タベースでの検索と大きな差はないという結果となった．デー
タベースを大きくした上で精度が上昇したものがあったのは，検索の阻害となる誤りのデータがならされ，正解データが目立

[15]

献

Apple.com. iTunes store. http://www.apple.com/jp/itunes/.
YouTube LLC. Youtube. http://www.youtube.com/.
niwango. ニコニコ動画. http://www.niconico.jp/.
Luke Barrington, Antoni Chan, Douglas Turnbull, and Gert
Lanckriet. Audio information retrieval using semantic similarity. In Proceedings of IEEE International Conferenceon Acoustics, Speech and Signal Processing, ICASSP 2007,
pages II–725–II–728, 2007.
Meinard Müller, Frank Kurth, and Michael Clausen. Audio
matching via chroma-based statistical features. In Proceedings of the 6th International Society on Music Information
Retrieval, ISMIR 2006, pages 288–295, 2005.
Frank Kurth and Meinard Müller. Efficient index-based audio matching. IEEE Transactions on Audio, Speech andLanguage Processing, 16(2):382–395, 2008.
Qingmei Xiao, Motoyuki Suzuki, and Kenji Kita. Fast hamming space search for audio fingerprinting systems. In Proceedings of the 12th International Society on Music Information Retrieval, ISMIR 2011, pages 133–138, 2011.
Hidehisa Nagano, Kunio Kashino, and Hiroshi Murase. Fastmusic retrieval using polyphonic binary feature vectors.
In Proceedings of 2002 IEEE International Conference on
Multimedia and Expo, ICME 2002, 2002.
Dimitrios Fragoulis, George Rousopoulos, Thanasis Panagopoulos, Constantin Alexiou, and Constantin Papaodysseus.
On the automated recognition of seriously distorted musical recordings. IEEE Transactions on Signal Processing,49(4):898–908, 2001.
Beth Logan. Mel frequency cepstral coefficients for musicmodeling. In International Symposium on Music Information Retrieval, Electronic Edition, 2000.
辻康博. 曲の局所パターン特徴量を用いた類似曲検索 感性語による検索. 電子情報通信学会技術研究報告. SP, 音声, 96(565):17–
24, 1997.
福村 純也 and 川越 恭二. 特徴空間とメロディ空間を用いた楽曲の類似検索方法. 情報処理学会研究報告. データベース・シス
テム研究会報告, 2003.
Ning Hu, Roger B. Dannenberg, and George Tzanetakis.
Polyphonic audio matching and alignment for music retrieval. In Proceedings of IEEE Workshop on Applicationsof Signal Processing to Audio and Acoustics, WASPAA
2003, pages 185–188, 2003.
藤原 弘将 and 後藤 真孝. Vocalfinder: 声質の類似度に基づ
く楽曲検索システム. 情報処理学会研究報告, 2007(81):27–32,
2007.
Keiichiro Hoashi, Kazunori Matsumoto, and Naomi Inoue.
Personalization of user profiles for content-based music retrieval based on relevance feedback. In Proceedings of theEleventh ACM International Conference on Multimedia,
pages 110–119, 2003.

[16] Matthew D. Hoffman, David M. Blei, and Perry R. Cook.
Easy as cba: A simple probabilistic model for tagging music.
In Proceedings of the 10th International Society on Music
Information Retrieval, ISMIR 2009, pages 369–374, 2009.
[17] Jaap Haitsma and Ton Kalker. A highly robust audio fingerprinting system. In Proceedings of the 3rd International Society on Music Information Retrieval, ISMIR 2002, pages
107–115, 2002.
[18] Udi Manber and Gene Myers. Suffix arrays: A new method
for on-line string searches. In Proceedings of the First
Annual ACM-SIAM Symposium on Discrete Algorithms,
pages 319–327, 1990.
[19] 高田 怜 and 喜田 拓也. 歌唱者の異なる同一楽曲の検索に適した音楽指紋. In 情報処理学会研究報告, 2013.
[20] Meinard Müller and Sebastian Ewert. Chroma toolbox:
Matlab implementations for extracting variants of chromabased audio features. In Proceedings of the 12th International Society on Music Information Retrieval, ISMIR
2011, pages 215–220, 2011.
[21] Yuta Mori. White page. http://homepage3.nifty.com/wpage/.