在讲算法之前，上一些前人的资料。
http://coding-geek.com/how-shazam-works/
https://laplacian.wordpress.com/2009/01/10/how-shazam-works/
http://royvanrijn.com/blog/2010/06/creating-shazam-in-java/
当然历史也有点久远了，如果你有心去百度一下 shazam 算法，
你会发现这类的博客也是不少的。
当然这显得我现在写这个，好像有点多余。
这里我就快速过一下算法的思路。
假设你有一首歌，换句话说，你有一堆数据。
你可以通过各种各样的方式，对它的内容进行抽象表达。
举个例子，对音乐而言，就是歌名，类型，时长等等。
对于一本书而言就是目录，标题，价位之类的属性。
但是有时候我们会忘记具体内容，
只知道大概的印象，这个时候想要找到对应的那个东西就比较困难了。
举个例子，Beyond 乐队的《喜欢你》这首歌，百度上一堆 问“黑凤梨” blabla的。。
而音乐检索算法就是为了提供比较人性化的方式帮忙 搜索音乐。
而shazam 这家公司就是第一个吃螃蟹的"人"。
上面提供的链接里都提到了shazam 算法的思路，需要细节了解的可以移步上面的链接。
shazam 算法分为以下步骤:
1.进行fft变换
2.切分5个频段，取频段中比较有代表性的信息，一般为该频段中强度最大值。
3.将取到的5个点，拼接起来算个字符串hash作为该段音乐的特征
4.以此类推对整个音频重复1，2，3步骤
最终拿到整个音频的所有hash信息。
后面检索音频也就是简单的建立hash库，然后撞hash数量，评分。
hash命中越多就认为越相似。
上图，感受一下，其实我感觉看图也不是很直观，哈哈哈哈。
整个算法非常简单，
最核心的点是 切分5个频段，
用上了时序信息去算哈希。
对于有时序的数据，肯定要用上时序性维度，不然是有失偏颇的。
之余图片，就要用空间性维度，之余视频，时间和空间都要有。
这个算法简单粗暴，也有效。
严格意义上讲，这个算法的泛化能力有待商榷。
改进的思路和方向也挺多的。
例如:
1.降低精度，下采样
（之于图像就是缩小图片等）
2.还分为5个频段，但是提取更加具有代表性的特征,
可以采用一些图像思路，例如模糊之后增强
（之于图像一般是计算角点等，详情参考sift）
3.加入更多的时序维度，扩展更多的时序关联，例如临近特征关键点的差距
(之于图像，就是采用卷积提取空间特征等)
4.音量归一化，拉伸音频的分贝值
(之于图像就是直方图拉伸，自动增强，白平衡等)
当然还有很多方法可以进一步拓展，其实核心目标就是控制变量因素。
尽可能的让数据处在先验条件的区间内计算。
其实说难也不难，说简单也不简单。
有另一个音频检索算法就是做了控制变量达到更加强大的鲁棒性。
他就是，dejavu
算法细节参见:http://willdrevo.com/fingerprinting-and-audio-recognition-with-python/
不过dejavu其中有一个地方的思路，我认为不妥，就是在最后算hash特征的时候采用sha-1算法。
我认为可以直接采用最后算出的值改为int16 直接拼合起来就可以了，可以降低算法的复杂度。
dejavu用到了一些图像算法，主要就是用于提取更加具有代表性的特征。
具体算法细节这里就不展开了，有兴趣的朋友可以去好好学习一下。
当然除了以上提到的两个算法之外，还有其他的一些实现，不过都是换汤不换药的节奏。
当然，我本人业余时间在研究自己构思的一个音频检索算法，还在开展中，
算法复杂度当然会更高，但是效果和后续检索准确度会大有提升。
上面提到的shazam和dejavu，本人以纯c 原汁原味实现之。
嗯，shazam的算法，开源给大家学习之。
代码来也:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include "fft.h"
//ref:https://raw.githubusercontent.com/cxong/tinydir/master/tinydir.h
#include "tinydir.h"
#include "timing.h"
#define DR_WAV_IMPLEMENTATION
//ref:https://raw.githubusercontent.com/mackron/dr_libs/master/dr_wav.h
#include "dr_wav.h" int16_t *wavRead_int16(char *filename, uint32_t *sampleRate, uint64_t *totalSampleCount) {
unsigned int channels;
int16_t *buffer = drwav_open_and_read_file_s16(filename, &channels, sampleRate, totalSampleCount);
if (buffer == ) {
fprintf(stderr, "ERROR\n");
exit();
}
if (channels == ) {
int16_t *bufferSave = buffer;
for (int i = ; i < *totalSampleCount; i += ) {
*bufferSave++ = (int16_t) ((buffer[i] + buffer[i + ]) >> );
}
*totalSampleCount = *totalSampleCount >> ;
}
return buffer;
} unsigned long hash(unsigned char *str) {
unsigned long hash = ;
int c;
while (c = *str++)
hash = ((hash << ) + hash) + c;
return hash;
} int generateHashes(char *input_file, int **hashtable, int songid, size_t N, int freqbandWidth, int maxElems) {
printf("reading %s \n", input_file);
uint32_t sampleRate = ;
uint64_t samplesize = ;
int16_t *pcmdata = wavRead_int16(input_file, &sampleRate, &samplesize);
float *inputBuffer = (float *) calloc(sizeof(float), N);
fft_complex *outBuffer = (fft_complex *) calloc(sizeof(fft_complex), N);
int sect = ;
int cnt = ;
int numHashes = ;
for (int i = ; i < samplesize; i++) {
if (sect < N) {
inputBuffer[sect] = (float) pcmdata[i];
sect++;
} else {
sect = ;
i -= ;
cnt++;
fft_plan plan = fft_plan_dft_r2c_1d(N, inputBuffer, outBuffer, );
fft_execute(plan);
fft_destroy_plan(plan);
int freq1 = , freq2 = , freq3 = , freq4 = , freq5 = ;
int pt1 = , pt2 = , pt3 = , pt4 = , pt5 = ;
int freqbandWidth2 = freqbandWidth * ;
int freqbandWidth3 = freqbandWidth * ;
int freqbandWidth4 = freqbandWidth * ;
int freqbandWidth5 = freqbandWidth * ;
int freqbandWidth6 = freqbandWidth * ;
for (int k = freqbandWidth; k < freqbandWidth6; k++) {
int freq = (outBuffer[k].real > ) ? (int) outBuffer[k].real : (int) ( - outBuffer[k].real);
int Magnitude = (int) (log10f((freq + )) * );
if (k >= freqbandWidth && k < freqbandWidth2 && Magnitude > freq1) {
freq1 = Magnitude;
pt1 = k;
} else if (k >= freqbandWidth2 && k < freqbandWidth3 && Magnitude > freq2) {
freq2 = Magnitude;
pt2 = k;
} else if (k >= freqbandWidth3 && k < freqbandWidth4 && Magnitude > freq3) {
freq3 = Magnitude;
pt3 = k;
} else if (k >= freqbandWidth4 && k < freqbandWidth5 && Magnitude > freq4) {
freq4 = Magnitude;
pt4 = k;
} else if (k >= freqbandWidth5 && k < freqbandWidth6 && Magnitude > freq5) {
freq5 = Magnitude;
pt5 = k;
}
}
char buffer[];
sprintf(buffer, "%d%d%d%d%d", pt1, pt2, pt3, pt4, pt5);
unsigned long hashresult = hash(buffer) % maxElems;
int key = (int) hashresult;
if (key < )
printf("Invalid key %d\n", key);
hashtable[key][songid]++;
numHashes++;
}
}
free(pcmdata);
free(inputBuffer);
free(outBuffer);
return numHashes;
} int main(int argc, char *argv[]) {
printf("Audio Processing\n");
printf("shazam audio hash\n");
printf("blog: http://cpuimage.cnblogs.com/\n");
int N = ;
int freqbandWidth = ;
int maxSongs = ;
size_t maxElems = ;
int **hashTable;
int i = , n = ;
float count = ;
int numsongs = ;
char filenames[maxSongs + ][_TINYDIR_FILENAME_MAX];
int filesizes[maxSongs + ];
int songScores[maxSongs + ];
float songMatch[maxSongs + ];
printf("running... \n");
if (argc < ) {
printf("no excerpt file to open \n");
exit();
}
double start_total = now();
hashTable = (int **) calloc(maxElems, sizeof(int *));
for (i = ; i < maxElems; i++)
hashTable[i] = (int *) calloc(maxSongs + , sizeof(int));
printf("Generating hashes for original files.. \n");
tinydir_dir dir;
tinydir_open(&dir, "data");
while (dir.has_next) {
tinydir_file file;
tinydir_readfile(&dir, &file);
if (file.is_reg) {
numsongs++;
double startTime = now();
filesizes[numsongs] = generateHashes(file.path, hashTable, numsongs, N, freqbandWidth, maxElems);
size_t time_interval = (size_t) (calcElapsed(startTime, now()) * );
songScores[numsongs] = ;
printf("%d:%d hashes for %s\n", numsongs, filesizes[numsongs], file.path);
printf("Time taken: %d seconds %d milliseconds\n", time_interval / , time_interval % );
strcpy(filenames[numsongs], file.name);
}
tinydir_next(&dir);
}
tinydir_close(&dir);
printf("Generating hashes for recorded file.. \n");
generateHashes(argv[], hashTable, , N, freqbandWidth, maxElems);
printf("Calculating score.. \n");
for (i = ; i < maxElems; i++) {
if (hashTable[i][] > ) {
for (n = ; n <= maxSongs; n++) {
if (hashTable[i][n] >= hashTable[i][])
songScores[n] = songScores[n] + hashTable[i][];
else
songScores[n] = songScores[n] + hashTable[i][n];;
}
}
}
for (i = ; i <= numsongs; i++) {
songMatch[i] = ((float) songScores[i]) / ((float) filesizes[i]);
printf("Score for %s = %f\n", filenames[i], songMatch[i]);
if (songMatch[i] > count) {
count = songMatch[i];
n = i;
}
}
printf("Best Score: %s\n", filenames[n]);
for (i = ; i < maxElems; i++)
free(hashTable[i]);
free(hashTable);
size_t msec = (size_t) (calcElapsed(start_total, now()) * );
printf("Total time taken: %d seconds %d milliseconds\n", msec / , msec % ); return ;
}
项目地址:
https://github.com/cpuimage/shazam
稍微说明一下:
在对应文件下建一个“data”的文件夹，存放需要进行计算hash备档的音频文件。
然后 直接传一个文件名过去，先计算"data"下所有文件的hash,然后计算传的目标文件的hash。
计算hash碰撞，输出相似度得分。
例如：
shazam_demo.exe 有没有.wav
输出：
running...
Generating hashes for original files..
reading data/冯心怡 - 暧昧（Cover 薛之谦）.wav
1:4881 hashes for data/冯心怡 - 暧昧（Cover 薛之谦）.wav
Time taken: 0 seconds 268 milliseconds
reading data/薛之谦 - 别.wav
2:3370 hashes for data/薛之谦 - 别.wav
Time taken: 0 seconds 186 milliseconds
reading data/薛之谦 - 暧昧.wav
3:4879 hashes for data/薛之谦 - 暧昧.wav
Time taken: 0 seconds 271 milliseconds
reading data/薛之谦 - 有没有.wav
4:3938 hashes for data/薛之谦 - 有没有.wav
Time taken: 0 seconds 214 milliseconds
reading data/赵大雄 - 有没有（Cover 薛之谦）.wav
5:3937 hashes for data/赵大雄 - 有没有（Cover 薛之谦）.wav
Time taken: 0 seconds 215 milliseconds
Generating hashes for recorded file..
reading 有没有.wav
Calculating score..
Score for 冯心怡 - 暧昧（Cover 薛之谦）.wav = 0.028478
Score for 薛之谦 - 别.wav = 0.025519
Score for 薛之谦 - 暧昧.wav = 0.026645
Score for 薛之谦 - 有没有.wav = 1.000000
Score for 赵大雄 - 有没有（Cover 薛之谦）.wav = 0.036830
Best Score: 薛之谦 - 有没有.wav
Total time taken: 1 seconds 413 milliseconds
这个工程只是用来练手学习思路，现在它的使命已经结束。
偷偷说一句，扫头像，有打赏，就有猛料。
以上，权当抛砖引玉。
独乐乐，不如众乐乐。
若有其他相关问题或者需求也可以邮件联系俺探讨。
邮箱地址是:
gaozhihan@vip.qq.com