语句倒装和语音图像压缩的科学原理

 

今天吴军老师讲了一道简单谷歌面试题，把语句倒装和语音图像压缩的科学原理结合了起来，很有启发。

 

面试题目是说“如何不使用额外的存储空间完成语句倒装?”,例如要把“London bridge is falling down”倒装成“down falling is bridge London”,这道题的难度在于不使用“额外的存储空间”，而最大思维陷阱在于人会陷入自己固有的思维方式，或者说常人的思维。

这道题最简单的做法如下：

第一步、先将整个句子看成是一个完整的字符串，以字母为单位头尾对调。

第二步、把用空格分割的每一个字串以字母为单位，头尾对调。

 

很多人想不到先要把整个句子变得无意义，才能得到的后面有意义的单词。这种先把看得懂的信息，变成你看不懂，但是没有任何损失的中间信息的做法，是今天语音和图像处理的基础。科学家是怎么设计算法的呢？

第一步、先把语音或者图像从直观的信息，变成人根本看不懂的频率信号。

第二步、根据压缩的比例，把高频的信号过滤掉，只保留低频的即可。当播放语音或者显示图片时，再从频率信息恢复为语音波形，或者图像即可。

 

例如JPEG文件存储的是图像的频率，你可以以为是一大片一大片存储的，因此像蓝天、白云、大海这样变化不是很多的色块，压缩的JPEG文件基本上把它们变成一种颜色。通常JPEG文件压缩和语音压缩10倍，人类感官是感觉不出来的。

 

所以从一道面试题，讲到语音和图像的压缩。它们的共同点在于，计算机在处理信息时，通常要把信息变成另一种形式才好处理，而那种形式，并非是人所熟悉的。