鋭意寄り道しながら開発中の音楽再生履歴記録・検索システム(仮)の横道の、gmusicbrowser(GMB)で再生した曲も履歴DBに入れようと四苦八苦準備している中で出たこぼれ話。

そもそもは、GMBで各演奏(録音, 曲)を区別する値「トラックID」は、音響指紋をハッシュ(ダイジェスト)処理で短くしたものを使う方針にした時、有名なハッシュ処理方式のMD5の結果が32文字と長いのが気に入らなくて、何とかしたいと思ったのが発端である。そんな、とても細かい話が書いてあるので、読まれる方はほとんど居ない気はするが、(いつものように)僕の整理のために書く。

まあ、そもそも、トラックIDは曲名などではないので、手で打ち込んだり目で見て何かする(読む)ことはないし、長いとはいっても音響指紋自体ではないので1つが数KBになる訳でもないから、それによってDBのサイズが肥大化することもないので、完全に好みの問題だ(有名な林檎のオジさんがやってそうな話かもw)。

なぜ"CRC48"がないのか?

はじめに目を付けたのはCRCである。ただ、僕が使っているPHPには32ビット(8文字)のCRC32しかなく、どうも心許ない気がした。具体的には、ID(曲数)が増えた時に重複(「衝突」)しそうな気がした。とは言え、僕はこの分野に詳しくないので、本当に32ビットで不十分なのかの確証はない(理論上は、32ビットでは約40億(232-1)通りの表現ができるが、重複(冗長性)を持たせているだろうから、現実的にはもっと少なそうだ。それでも、数万曲だったら完全に余裕だろう。ただ、ハッシュの表現範囲がどうやって決まるのかが分からないので、特定の使い方で範囲が狭くなるのなら安心できないと思った)。まあ、これも全く気分的な問題だ。

探すと、64ビットのCRC64(16文字)はあった。が、それは少し長く、僕としては12文字くらいのが欲しかった。それは"CRC48"というべきものなのだが、いくら探してもほとんど出て来ない。調べると、ハッシュ値を短くする方法が分かったので、それでCRC64を48ビットに短くできた。最初は単純にマスク(≒除算または剰余)して短くすればいいのかとは思ったのだが、詳しくないので、安直なことをしてハッシュの強度が下がる(→ 衝突しやすくなる)のが嫌なので、丹念に調べた。結局は普通にマスクしても問題なさそうだった。念入りにするには、長いハッシュを分割してXORする方法があった。

それにしても、CRC48がないのが不思議だ。Stack overflow(コンピュータ技術者のQ&Aサイト)でも、「結構要る」という意見もあった(UUIDに使うらしい)。全く不便だ。

音響指紋計算プログラムfpcalcの隠れオプション-hashの不思議

CRC48を探したり試行錯誤しているうちに、音響指紋の計算に使っているfpcalcに、探していたものそのものかも知れないオプションがあることが分かった。それが-hashで、検索してもほとんど出て来ないので、知っている人は少なそうだ。

これを指定すると、音響指紋の値に加えて、音響指紋のハッシュ値も出てくる。この値があまりにも妙なので、うなってしまった。この値を使うと、同じ演奏(録音)が分かる可能性がある。ただ、残念ながら、常に分かるとは限らない。

同じ演奏(録音)のハッシュ値は同じか近いことがあるが、全く違うこともある。全く同じファイルなら同じだが、リマスターや単にベスト盤に入っているだけで異なってしまうことがあった。逆に、リマスターでもオリジナル版でもモノラル版でもレコード版でも同じ値になったりもした。同じ演奏で値が違う場合も、最後の桁が1だけ違う場合もあったし、特定の桁が思わせぶりに違う場合もあった。以下にその例を示す。

  • "Bohemian Rhapsody": b04cb826 (リマスターでないベスト盤), 904cb826 (リマスターとそうでないオリジナルアルバム)
  • "Crazy Little Thing Called Love": d434a0ae (リマスターでないオリジナルアルバムと新しいベスト盤), d400a0ae (リマスターでないベスト盤), d42ca02e (リマスターのオリジナルアルバム)

謎の挙動だ。それぞれの桁に意味があるような気がして、それを突き詰めるのもおもしろそうだったが、いつも同じ動きをしないと不便なので(僕としては、同じ演奏ならすべて同じ値になるか、同じファイルでない限り、全部別になって欲しい)、使うのは見送った。そもそも、同じ演奏(録音)かどうかは音響指紋の間の「距離」で確率として表すとのことなので、ハッシュは簡易的に似た演奏を見分けるにはいいだろうが(-hashオプションを紹介しているページには、重複したファイルを減らす使い方が書いてあった)、IDとして使うのは良くなさそうだ。

SHA-3(というかWikipedia)に騙されたw

CRC48に落ち着き掛けたのだが、厳密に言えば、CRCはハッシュではないし、自分で勝手に短くするのが気に入らず、任意の長さで出せる標準的なハッシュ方式を探した。すると、SHA-3はそれができるとのことだったので、プログラムをダウンロードして48ビットで試してみたら、エラーになった。調べたら、最短ビット数(224ビット)が決まっていた。あと、任意でなく数とおりしか指定できなかった。任意の長さにできるというのは、確かWikipediaで見たのだが、鵜呑みにするのは良くないと実感した。今回はちゃんと確かめたから良かった。もしかしたら、プログラムを変更すればできたのかも知れないが、中身がチンプンカンプンだった。

MD5を短くする。

SHA-3は諦めたものの、「短いハッシュ」で調べているうちに、Stack overflowで目から鱗のアイデアを見付けた。Base64エンコーディングで文字数を減らすのだ。ハッシュ値は普通は、"10f280198c517c830fa302c4e1bcca7b"(MD5の例)のように16進数で書く。これは元々は数値なので、Base64で表せば短くできるのだ。簡単に言うと、16進数は0-9とa-fしか使わないが、Base64はもっと多くの文字を使うから1桁で示せる値が多いので、短く書ける(桁数が減る)。

MD5は128ビットと数が大きいので手こずったが、できた。元は32文字だったのが"EPKAGYxRfIMPowLE4bzKew"のように22文字で表わすことができ、10文字も短くできた。希望は12文字くらいだったが、(今はobsoleteになっているけど)実績あるハッシュ処理を使うことで、衝突の心配が皆無になるだろうから許せると思い、今に至る。これで、いつでもGMBで再生した曲をDBに登録できる(屏風の中から虎を出してくれたらそのプログラムを書きさえすればねw)。

なお、この方法でCRC64も12文字にできる(基本的には、数値なら何でも可)ので、途中まではそれを使おうとしていたが、CRC48を止めたのと同じ理由でMD5の方が良さそうだったので乗り換えた。

(6/11 6:09追記) ちょっと思い付いて調べたら、SpotifyのトラックIDも僕と同じ22文字だった(アルバムIDも同じ)。これもBase64みたいな表記なので(例: 7oYN5pKRoFiVLoDFK6R3O1)、元はMD5のような長さの値なのだろう。偶然の一致だけどおもしろい。ハッシュ値だとしたら、何の情報を元にしているのか興味あるところだ。そして、(これは想像だが、)ID数が数億になるとCRC64では不足するのかも知れない。もちろん、使い切るまで衝突しない訳ではないので、ある程度の余裕が要ると思う。その点で、MD5にしたのは正解だったのではないか。

それに引き換え、(前にも書いたが)マイナンバーは脆弱だ。個人の番号は10進数で12桁なので全く余裕がない。当てずっぽうな値でも有効になるだろうし、(おそらくありえないがw、)長く使われ続けると不足するので、将来は死んだ人の番号を使い回す羽目になると思う。素人でも分かるくらいのしょうもなさだ。そのうち、そういう問題の解消を名目にしてまた新しい仕組みが(利権の確保とともに)生まれるのだろう。役人連中は楽だね。

似たようなことはISRCにも言える。12桁と短いうえに、区分されていて使える数が少ないから、いつかは破綻するし、年を2桁で表記するからとても古い録音は扱えないし(例えば、"19"は1919年なのか2019年なのか? まあ、仕組みができてから録音されたものを登録するスタンスなのだろうが・・・)、2100年以降は使えない。始まったのは2000年以降と推測するが、だとしたら日本の役所並みにお粗末だ。

ちなみに、確認と評価のため、音響指紋のMD5でGMBに入っている全曲(約1.5万曲)のトラックIDを生成してみたところ、90組くらい同じIDが出たが、衝突ではなく、元が同じ演奏(例: 重複したファイル、タグを変えたものとオリジナル、(ごくまれに)収録アルバムが異なる同じ演奏)のためだったので、本来の目的が達成できていることが分かったし、問題なくIDに使えることも分かったので安心した。あと、大量の曲ファイルに重複がほとんどなかったのには、我ながら感心した。なお、音響指紋の計算(fpcalc)が意外に遅く、大量の曲の処理には結構時間が掛かった。

心なしか、ものすご〜く本題から外れている気がするし、ちょっと買い物に行くのにハマーとかモビルスーツに乗るようなくらいやり過ぎな気がしないでもないが、趣味だし、いろいろな知識が得られたので良しとしようw

(6/11 5:41, 6:09 わずかに加筆・修正、追記; 6/11 10:32 わずかに補足)

  •   0
  •   1

コメントを書く

名前    

メール 

URL