你有没有想过沙扎姆是怎么工作的？几年前，我问自己这个问题，我读了沙扎姆的混淆者王立春写的一篇研究文章，以了解沙扎姆背后的魔力。简单的答案是音频指纹，这就引出了另一个问题：什么是音频指纹？
当我还是学生的时候，我从来没有上过信号处理的课程。要真正理解Shazam(而不仅仅是模糊的概念)，我必须从基础开始。这篇文章是我为了解Shazam所做的搜索工作的总结。
我将从音乐理论的基础开始，介绍一些重要的信号处理材料，最后讨论Shazam背后的机制。阅读本文不需要任何知识，但是因为它涉及计算机科学和数学，所以最好有良好的科学背景(特别是后面的部分)。如果你已经知道“八度”、“频率”、“采样”和“频谱泄漏”是什么意思，你可以跳过前几部分。
因为这是一篇很长的技术性文章(11000字)，你可以在不同的时间自由阅读每一部分。
声音是一种通过空气(或水)传播的振动，可以被耳朵破译。例如，当你听mp3播放器时，耳机会产生振动，通过空气传播，直到到达你的耳朵。光也是一种振动，但你听不到它，因为你的耳朵无法破译它(但你的眼睛可以)。
振动可以用正弦波形建模。在这一章中，我们将看到如何从物理/技术上描述音乐。
纯音是指音调波形为正弦波的音调。正弦波的特征是：
它的频率：每秒的周期数。它的单位是赫兹(Hz)，例如100 Hz=每秒100个周期。
这些特征由人耳解密以形成声音。人类可以听到从20赫兹到20000赫兹(最好的耳朵)的纯音，而且这个范围随着年龄的增长而减小。相比之下，你看到的光是由4*10^14 Hz到7.9×10^14 Hz的正弦波组成的。
你可以用YouTube视频检查你的耳朵范围，比如这个视频，它显示了从20 Hz到20k Hz的所有纯音，在我的情况下，我听不到超过15千赫兹的任何声音。
人类对音量的感知取决于纯音的频率。例如，频率为30 Hz的幅度10的纯音将比频率为1000 Hz的幅度10的纯音安静。人类的耳朵遵循心理声学模型，你可以在维基百科上查看这篇文章以了解更多信息。
在此图中，您可以看到频率为20 hz、振幅为1的纯正弦波的表示。
纯音不是自然而然存在的，但世界上的每一个声音都是不同幅度的多个纯音的总和。
在此图中，您可以看到更逼真的声音表示形式，即由多个正弦波组成的声音：
音乐分区是在特定时刻执行的一组音符。这些音符也有持续时间和响度。
音符分为八度。在大多数西方国家，八度是一组8个音符(在大多数英语国家是A、B、C、D、E、F、G，在大多数拉丁西方国家是Do、Re、Mi、Fa、Sol、La、Si)，具有以下属性：
一个八度音符的频率在下一个八度音阶加倍。例如，A4(第四个八度的A)在440 Hz的频率等于A3(第三个八度的A)在220 Hz的频率的2倍，A2(第二个八度的A)在110 Hz的频率的4倍。
许多乐器按八度提供8个以上的音符，这些音符被称为半音或半音。
对于第四个八度(在西方拉丁国家为第三个八度)，音符的频率如下：
虽然可能有些奇怪，但耳朵的频率敏感度是对数的。这意味着：
仅供参考，A4/LA3的频率为440 Hz，是校准声学设备和乐器的标准参考。
同样的音符如果是由吉他、钢琴、小提琴或人类歌手演奏，听起来并不完全相同。原因是每种乐器对于给定的音符都有自己的音色。
对于每种乐器，所产生的声音是听起来像给定音符的多个频率(音符的科学术语是音调)。这种声音有一个基频(最低频率)和多个泛音(高于基频的任何频率)。
大多数乐器都能发出(接近)和谐的声音。对于这些乐器，泛音是称为谐波的基频的倍数。例如，纯音A2(基音)、A4和A6的合成是调和的，而纯音A2、B3、F5的合成是非调和的。
注意：乐器演奏的声音中可能没有音高(感知到的音符)。例如，如果乐器演奏纯音为A4、A6和A8的声音，人脑会将产生的声音解释为A2音符。这个音符/音高将是A2，而声音中的最低频率是A4(这一事实被称为缺失的基频)。
一首乐曲是由多个乐器和歌手演奏的。所有这些乐器都能产生多个频率的正弦波组合，总体来说是一个更大的正弦波组合。
用光谱图可以看到音乐。大多数情况下，谱图是三维图形，其中：
第三个维度用颜色来描述，它表示某一时刻频率的振幅。
例如，这里有一个C4音符的钢琴演奏的声音(其最高基频为261.63 Hz)。
http://coding-geek.com/wp-content/uploads/2015/05/pia60.mp3颜色以分贝为单位表示振幅(我们将在下一章中看到它的含义)。
正如我在前一章中告诉你的，虽然演奏的音符是C4，但在这张唱片中还有261 Hz以外的其他频率：泛音。有趣的是，其他频率是第一个频率的倍数：钢琴是和声乐器的一个例子。
另一个有趣的事实是，频率的强度会随着时间的推移而变化。这是乐器的另一个独特之处。如果你选择同一位艺术家，但你换了钢琴，频率的演变不会有相同的表现，产生的声音也会略有不同，因为每个艺术家/乐器都有自己的风格。从技术上讲，这些频率的演变改变了声音信号的包络(这是音色的一部分)。
为了让您对Shazam音乐指纹算法有一个初步的了解，您可以在这个频谱图中看到一些频率(最低的频率)比其他频率更重要。如果我们只保留最强壮的呢？
除非你是乙烯基盘的爱好者，否则当你听音乐的时候，你使用的是数字文件(mp3，苹果无损，Ogg，音频CD，随便什么)。但当艺术家创作音乐时，它是类比的(不是用比特表示的)。音乐被数字化，以便由电子设备(如计算机、电话、MP3播放器、CD播放器…)存储和播放。。在这一部分中，我们将看到如何从模拟声音过渡到数字声音。了解数字音乐是如何制作的将有助于我们在接下来的部分中分析和处理数字音乐。
模拟信号是连续的信号，这意味着如果你拿一个模拟信号的一秒，你可以把这一秒分成[放你能想到的最大的数字，我希望它是一个大的！]持续零点几秒的部分。但在数字世界里，你负担不起存储无限数量的信息。您需要有一个最小单位，例如1毫秒。在此时间单位内，声音不能改变，因此此单位需要足够短，以便数字歌曲听起来像模拟歌曲，并且足够大，以限制存储音乐所需的空间。
例如，想想你最喜欢的音乐。现在想想看，声音每隔2秒才变一次，听起来没什么。从技术上讲，声音是混叠的。为了确保你的歌曲听起来很棒，你可以选择一个非常小的单位，比如纳米(10^-9)秒。这一次你的音乐听起来很棒，但是你没有足够的磁盘空间来存储它，太糟糕了。
数字音乐的标准时间单位是每秒44到100个单位(或样本)。但是这个44.1 kHz是从哪里来的呢？嗯，有个家伙认为每秒44100个单位会很好，而且所有的…。当然，我是在开玩笑。
在第一章中，我告诉过你，人类可以听到20赫兹到20千赫的声音。Nyquist和Shannon的一个定理指出，如果你想将信号从0 HZ数字化到20 KHz，你至少需要每秒40,000个样本。其主要思想是，频率为F的正弦波信号在每个周期至少需要2个点才能被识别。如果采样频率至少是信号频率的两倍，那么原始信号的每个周期至少会有2个点。
让我们试着用图片来理解，看看这个很好的抽样的例子：
红叉代表采样的声音，这意味着我每1/40秒就用红叉标记蓝色曲线。
虽然它不具有相同的形状和相同的幅度，但采样信号的频率保持不变。
在此图中，20 Hz的声音以30 Hz的采样率进行数字化。这一次，采样信号的频率与原始信号不同：它只有10 Hz。如果仔细观察，可以看到采样信号中的一个周期代表原始信号中的两个周期。这是一个抽样不足的案例。
本例还显示了其他一些情况：如果要数字化0 HZ到20 KHz之间的信号，则需要在采样之前从信号中删除其频率超过20 KHz的信号。否则，这些频率将被转换为0 HZ和20 KHz之间的频率，因此会添加不需要的声音(这称为混叠)。
总而言之，如果你想要一个好的从模拟到数字的音乐转换，你必须每秒至少录制40000次模拟音乐。高保真公司(如索尼)在80年代选择44.1千赫，因为它高于40000赫兹，并与NTSC和PAL视频规范兼容。还有其他音频标准，如48 kHz(Blueray)、96 kHz或192 kHz，但如果你既不是专业人士也不是发烧友，你可能会听44.1 kHz的音乐。
注1：奈奎斯特-香农定理比我所说的要宽泛，如果你想了解更多，可以去维基百科看看。
注2：采样率的频率需要严格高于要数字化的信号频率的2倍，因为在最坏的情况下，您可能最终得到一个恒定的数字化信号。
我们看到了如何将模拟音乐的频率数字化，但是音乐的响度呢？音量是一个相对的量度：对于信号内部相同的音量，如果你增加扬声器的音量，声音会更高。响度衡量的是歌曲内部最低和最高音量之间的差异。
同样的问题也出现在响度上：如何从一个连续的世界(音量无限变化)过渡到一个离散的世界？
想象一下你最喜欢的音乐只有4种响度状态：无声、低音、高音和最大音量。即使是世界上最好的歌也会变得难以忍受，你刚才想象的是4级量化。
此图表示的是8级量化。如您所见，生成的声音(红色)非常不同。真实声音和量化声音之间的差异称为量化误差或量化噪声。这种8级量化也称为3位量化，因为您只需要3位就可以实现8个不同的级别(8=2^3)。
虽然合成的声音仍然是改变的，但它看起来(和听起来)更像原始声音。
谢天谢地，人类没有特别敏感的耳朵。标准量化在16位上编码，这意味着65536级。与16位量化相比，量化噪声对人耳来说足够低。
注：在录音棚中，专业人员使用的量化是24位，这意味着在音轨的最低点和最高点之间有2^24(1600万)个可能的响度变化。
PCM或脉冲编码调制是表示数字信号的标准。它被光盘和大多数电子设备使用。例如，当您在计算机/手机/平板电脑中收听mp3文件时，mp3会自动转换为PCM信号，然后发送到您的耳机。
PCM流是有组织的比特流。它可以由多个声道组成。例如，一个立体声音乐有2个声道。
在流中，信号的振幅范围被分成样本。每秒的样本数目对应于音乐的采样率。例如，44.1 kHz采样的音乐将具有每秒44100个样本。每个样本都给出了相应秒分数的声音的(量化)振幅。
有多种PCM格式，但音频中使用最多的是(线性)PCM 44，1 kHz，16位深度立体声格式。这种格式的音乐每秒有44到100个样本。每个样本需要4个字节：
2字节(16位)表示左侧扬声器的强度(从-32,768到32,767。
2字节(16位)，用于右侧扬声器的强度(从-32,768到32,767。
在PCM44.1 kHz 16位深度立体声格式中，每秒音乐有44100个这样的样本。
现在您知道如何从模拟声音转换为数字声音了。但是，如何才能获得数字信号内部的频率呢？这一部分非常重要，因为Shazam指纹算法仅适用于频率。
对于模拟(因此是连续的)信号，有一种称为连续傅立叶变换的变换。该函数将时间的函数转换为频率的函数。换句话说，如果对声音应用傅立叶变换，它会给出声音内部的频率(及其强度)。
为了更好地了解音乐内部的频率，我们需要对全长音频信号的一小部分应用傅立叶变换，例如0.1秒部分，以便我们知道音轨的每个0.1秒部分的频率是多少)。
谢天谢地，还有另一个数学函数，即离散傅立叶变换(DFT)，它是有一些限制的。
注意：傅立叶变换只能应用于一个声道，这意味着如果您有立体声歌曲，您需要将其转换为单声道歌曲。
DFT(离散傅立叶变换)适用于离散信号，并给出离散频谱(信号内部的频率)。
以下是将数字信号转换为频率的神奇公式(别跑，我会解释的)：
N是窗口的大小：n是组成信号的样本数(我们将在下一部分中大量讨论窗口)。
例如，对于具有4096个采样窗口的音频信号，此公式必须应用4096次：
正如你可能已经注意到的，我说的是频段，而不是频率。原因是DFT给出了一个离散的频谱。频率箱是DFT可以计算的最小频率单位。面元的大小(称为频谱/频谱分辨率或频率分辨率)等于信号的采样率除以窗口的大小(N)。在我们的示例中，使用4096个采样窗口和44.1 kHz的标准音频采样率，频率分辨率为10.77 Hz(特殊的第0个面元除外)：
这意味着DFT不能分离出两个更接近10.77 Hz的频率。例如，27 Hz、32 Hz和37 Hz的音符结束在同一个箱子中。如果37赫兹的音符非常有力，你就会知道第三个音箱是强大的。这对于分离最低八度的音符是有问题的。例如：
A1(或La-1)在55 Hz，B1(或Si-1)在58.27 Hz，G1(或Sol-1)在49 Hz。
一架标准88键钢琴的第一个音符是27.5赫兹的A0，然后是29.14赫兹的A#0。
您可以通过增加窗口大小来提高频率分辨率，但这意味着失去音乐内部的快速频率/音符更改：
增加窗口意味着采集更多的样本，因此增加窗口所需的时间。
对于4096个样本，窗口持续时间为0.1秒，频率分辨率为10.7 Hz：您可以每0.1秒检测到一个变化。
对于16384个样本，窗口持续时间为0.37秒，频率分辨率为2.7HZ：您可以每隔0.37秒检测到一个变化。
音频信号的另一个特殊性是我们只需要DFT计算的一半的箱。在上例中，bin定义为10.7 Hz，这意味着2047个bin代表从21902，9 Hz到21913，6 Hz的频率。但是：
如果你想知道为什么面元分辨率等于“采样率”除以“窗口大小”，或者为什么这个公式如此离奇，你可以在这个非常好的网站(特别是第四部分和第五部分)上阅读一篇关于傅立叶变换的5部分文章，这是我读过的最适合初学者的文章(而且我读了很多关于这件事的文章)。
如果要获得每个0.1秒部分的一秒声音的频率，则必须对第一个0.1秒部分应用傅立叶变换，对第二个0.1秒部分应用傅立叶变换，对第三个0.1秒部分应用傅立叶变换…
对于前0.1秒，您将对完整的1秒信号应用傅里叶变换，再乘以介于0和0.1秒之间的等于1的函数，然后对其余的信号应用0。
对于第二个0.1秒，您将对完整的1秒信号应用傅里叶变换，并在0.1秒和0.2秒之间乘以等于1的函数，对其余的信号应用等于0的函数。
对于第三个0.1秒，您将对完整的1秒信号应用傅里叶变换，乘以0.2到0.3秒之间等于1的函数，其余的应用0。
以下是应用于数字(采样)音频信号以获得第一个0.01秒部分的窗口函数的可视示例：
在此图中，要获得前0.01秒部分的频率，需要将采样的音频信号(蓝色)与窗函数(绿色)相乘。
在此图中，要获得第二个0.01秒部分的频率，需要将采样的音频信号(蓝色)与窗函数(绿色)相乘。
通过对音频信号进行“加窗”，您可以将信号AUDIO(T)乘以窗口函数WINDOW(T)。此窗函数会产生频谱泄漏。频谱泄漏是音频信号中不存在的新频率的幻影。真实频率的功率被泄漏到其他频率。
这里有一个非正式的(非常轻松的)数学解释。让我们假设您想要完整音频信号的一部分。您将使用窗口函数乘以音频信号，该函数仅允许传递所需部分的声音：
当您尝试获取音频部分的频率时，您可以对信号应用傅里叶变换。
根据卷积定理(*表示卷积运算符和。乘法运算符)。
我不会再深入了，因为它需要高等数学。如果您想了解更多，请查看第29页的链接，“截断效应”一章介绍了在信号上应用矩形窗口的数学效果。您需要记住的是，将音频信号分割成小部分来分析每个部分的频率会产生频谱泄漏。
您无法避免频谱泄漏，但您可以通过选择正确的窗口函数来处理泄漏的行为：您可以选择三角形窗口、Parzen窗口、Blackman窗口、Hamming窗口…，而不是使用矩形窗口函数。
矩形窗口是最容易使用的窗口(因为您刚刚。
.