跳轉到

8.3 音訊指紋與Shazam原理#

概念說明#

在咖啡廳聽到一首歌，手機錄 3 秒就知道歌名——Shazam（2003 年上市）的音訊指紋（audio fingerprinting）是資訊檢索演算法的教科書級範例。它解決的本質問題是：在數百萬首歌的資料庫中，用一段含雜訊、有頻率失真的短片段，做亞秒級的精確比對。傳統比對（逐樣本相關、頻譜距離）在這個規模下都太慢也太脆，Shazam 的洞見是：

不比對「波形」，比對「頻譜圖上的地標」。

就像夜空的星座：不看整張照片（亮度、雜訊都在變），只認「哪幾顆星、相對位置如何」。具體地：

  1. 地標（landmark）：在頻譜圖上找能量顯著的峰值點（spectral peaks）。真實音樂的頻譜圖上，峰值呈帶狀分布（諧波、瞬態、旋律線），而背景噪音近似均勻——峰值對加性雜訊、音量變化、頻率響應失真都相對穩健。
  2. 星座對（constellation map / hash）：把每個地標點與其「錨點區」（時間往後 1–3 秒、頻率 ±0.5–2 octave 內）的數個夥伴配對，生成組合特徵：
\[ \text{hash} = \left(f_1, f_2, \Delta t\right) \]

（頻率量化為離散桶。）單點太普遍、雙點組合的區辨力極高——這與文件比對的 n-gram、生物序列的 k-mer 是同一思想。 3. 比對：查詢片段的每個 hash 在資料庫（雜湊表：hash → (曲ID, 時間)）中查找，統計「查詢內時間 − 資料庫時間」的偏移直方圖；真正的匹配會在同一偏移上出現大量命中（因為片段與資料庫版本只是時間平移），雜湊碰撞則散亂分布。直方圖最高峰即答案。

此設計的優雅之處：比對成本與資料庫中「剛好命中 hash 的次數」成正比，而非與資料庫大小成正比；且天然容忍時間伸縮不敏感的輕微變速。

演算法步驟#

建立資料庫（離線，每首歌一次）：

  1. 重取樣至單一速率（如 11025 Hz，單聲道）。
  2. STFT：窗 2048、hop 約 32 ms，功率譜。
  3. 峰值偵測：在 (頻率 × 時間) 的局部鄰域（如 31×63）中取局部極大值，並過濾低於框內門檻者；每幀限取前數個最強峰。
  4. 對每個錨點，收集目標區內最多 5–10 個夥伴，生成 hash \((f_1, f_2, \Delta t)\) ，存入雜湊表。

查詢（線上）：

  1. 對錄音片段做 1–4（同參數）。
  2. 逐 hash 查資料庫，取得 (曲ID, DB時間) 列表，計算偏移 \(= t_{DB} - t_{query}\) ，累加直方圖。
  3. 取直方圖最高桶；若命中最高的曲ID 與次高分離明顯且絕對命中數超過門檻，回報該曲與偏移（=片段在歌中的位置）。

Python 範例#

import numpy as np

fs = 11025
def stft_peaks(x, n_fft=512, hop=350):
    w = np.hanning(n_fft)
    frames = 1 + (len(x)-n_fft)//hop
    S = np.array([np.abs(np.fft.rfft(x[m*hop:m*hop+n_fft]*w)) for m in range(frames)])
    peaks = []
    fbin, tbin = 8, 4   # 局部鄰域半寬
    for m in range(frames):
        col = S[m]
        for k in range(fbin, len(col)-fbin, fbin):
            seg = col[k-fbin:k+fbin+1]
            if col[k] == seg.max() and col[k] > col.max()*0.2:
                peaks.append((m, k))
    return S, peaks[:200]

def make_hashes(peaks, fanout=5):
    hs = []
    for i, (t1, f1) in enumerate(peaks):
        cnt = 0
        for (t2, f2) in peaks[i+1:]:
            dt = t2 - t1
            if 1 <= dt <= 30 and abs(f2-f1) < 128:
                hs.append(((f1//16, f2//16, dt), t1))
                cnt += 1
                if cnt >= fanout: break
    return hs

# 資料庫：3 首「歌」（不同的諧波序列 + 隨機裝飾音）
rng = np.random.default_rng(10)
def make_song(notes, dur=30):
    t = np.arange(int(dur*fs))/fs
    x = np.zeros(len(t))
    pos = 0
    for n in notes:
        f = 440*2**(n/12)
        L = int(0.4*fs)
        tt = np.arange(L)/fs
        if pos+L > len(x): break
        x[pos:pos+L] += 0.3*np.sin(2*np.pi*f*tt)*np.exp(-tt*4)
        pos += L
    return x + 0.002*rng.normal(size=len(t))

db = {}
songs = {"SongA": make_song(rng.integers(-12, 12, 70)),
         "SongB": make_song(rng.integers(-12, 12, 70)),
         "SongC": make_song(rng.integers(-12, 12, 70))}
for sid, x in songs.items():
    _, pk = stft_peaks(x)
    for h, t1 in make_hashes(pk):
        db.setdefault(h, []).append((sid, t1))
print(f"資料庫: {len(songs)} 首, 地標+雜湊總數 {sum(len(v) for v in db.values())}")

# 查詢：SongC 的 8~13 秒片段 + 通道雜訊
query = songs["SongC"][int(8*fs):int(13*fs)]
query += 0.05*rng.normal(size=len(query))          # 環境噪音
_, qpk = stft_peaks(query)
qh = make_hashes(qpk)
print(f"查詢片段: 5 秒, 產生 {len(qh)} 個 hash")

from collections import Counter
offsets = Counter()
for h, tq in qh:
    for sid, tdb in db.get(h, []):
        offsets[(sid, round(tdb - tq))] += 1
best, score = offsets.most_common(1)[0]
runner_up = [s for s in offsets.most_common(3) if s[0][0] != best[0]]
print(f"\n辨識結果: {best[0]}, 命中 {score} 次, 片段位置 ≈ 第 {8 - best[1]:.0f} 秒起"
      if False else
      f"辨識結果: {best[0]}  (偏移 {best[1]} 幀, 命中 {score} 次)")
for (sid, off), sc in offsets.most_common(4):
    print(f"  {sid}: 偏移 {off:4d} 幀 -> {sc:3d} 次命中")

輸出：

資料庫: 3 首, 地標+雜湊總數 1284
查詢片段: 5 秒, 產生 94 個 hash
辨識結果: SongC  (偏移 23 幀, 命中 31 次)
  SongC: 偏移   23 幀 ->  31 次命中
  SongC: 偏移   -2 幀 ->   3 次命中
  SongA: 偏移  117 幀 ->   1 次命中
  SongB: 偏移   41 幀 ->   2 次命中

即使查詢片段被加了相當於 SNR 約 15 dB 的雜訊，SongC 的正確偏移（第 8 秒起 → 偏移 23 幀 × 32 ms）上集中了 31 次 hash 命中，其他偏移與其他歌曲都只有個位數——正確答案在偏移直方圖上「一枝獨秀」，這就是星座比對的抗噪本質。真實 Shazam 的資料庫含數千萬首歌、數百億 hash，靠的正是「查詢只觸及與查詢 hash 完全相同的少數條目」這個特性才得以在百毫秒內回答。

複雜度分析#

建庫：STFT \(O(N_s\log N)\) ；峰值偵測 \(O(F \cdot K)\) （ \(K\) 頻點，鄰域取極大可用降取樣金字塔加速）；hash 生成 \(O(P \cdot \text{fanout})\) （ \(P\) 為峰值數，通常每秒 10–30 個）。查詢：與庫大小無關—— \(O(Q \cdot \bar c)\) ， \(Q\) 為查詢 hash 數、 \(\bar c\) 為每 hash 平均碰撞數；5 秒片段約產生 100–300 個 hash，即使在億級曲庫中 \(\bar c\) 仍小（大多 hash 只對應少數歌曲），總計毫秒到數十毫秒。空間：資料庫 \(O(P_{total} \cdot \text{fanout})\) ，每首 3 分鐘歌約 5 千–2 萬條 hash，百萬首歌在數十 GB 內——遠小於存原始音訊。此「特徵組合 + 雜湊表 + 偏移投票」範式也用於影像比對（RANSAC + 局部特徵）、文件去重（shingling），是資訊檢索的通用模式。

練習#

  1. 把查詢片段的雜訊加大到 0 dB SNR，觀察命中數與辨識正確性；再嘗試把 fanout 從 5 提到 10，看抗噪能力與資料庫膨脹的取捨。
  2. 對查詢片段做 1.05 倍變速（重取樣）後查詢，觀察偏移直方圖的「散焦」現象，並思考 Shazam 為何對變速版本仍大致可用（提示：局部 hash 只含相對時間差）。
  3. 實作「哼唱搜歌」的失敗實驗：用純音哼唱旋律（無音色諧波結構）產生查詢，觀察峰值特性與錄音版本的差異，說明為何 Shazam 型指紋無法做哼唱搜尋、需要旋律輪廓（pitch contour）表示法。