Bài 23: Shazam nhận ra bài hát trong vài giây như thế nào? Dấu vân tay âm thanh và bảng băm

Bạn đang ở quán cà phê, một bài hát hay vang lên mà không biết tên. Mở Shazam, đưa điện thoại lên – vài giây sau đã có tên bài hát và ca sĩ, dù xung quanh ồn ào tiếng nói chuyện. Làm sao một ứng dụng tìm được đúng một bài trong hàng chục triệu bài nhanh đến vậy?

Bài thứ hai mươi ba của chuyên mục "Thuật toán trong đời sống": dấu vân tay âm thanh, bảng băm và cách Shazam tìm bài hát.

1. Từ số điện thoại 2580 đến 100 tỷ lượt nhận diện

• Shazam ra đời năm 1999, từ ý tưởng của Chris Barton và Philip Inghelbrecht – hai cựu học viên Trường Kinh doanh Haas (ĐH California, Berkeley) – cùng Avery Wang và Dhiraj Mukherjee.
• Năm 2002, dịch vụ ra mắt ở Anh dưới dạng số điện thoại 2580: người dùng gọi số này, đưa điện thoại về phía loa, rồi nhận tin nhắn báo tên bài hát.
• Apple hoàn tất việc mua lại Shazam vào tháng 9/2018.
• Theo Apple (11/2024), Shazam đã vượt 100 tỷ lượt nhận diện bài hát và có hơn 300 triệu người dùng mỗi tháng.

2. Ý tưởng: "dấu vân tay" của âm thanh

Năm 2003, Avery Wang công bố cách Shazam hoạt động trong bài báo "An Industrial-Strength Audio Search Algorithm" tại hội nghị ISMIR. Có ba bước chính:

1. Phổ tần số: dùng biến đổi Fourier (xem Bài 20) để biết ở mỗi thời điểm, tần số nào đang vang mạnh.
2. Bản đồ chòm sao: chỉ giữ lại các đỉnh – những điểm mạnh hơn mọi điểm xung quanh – và bỏ hết phần còn lại. Mỗi bài hát thành một "bầu trời sao" gồm các cặp (thời gian, tần số).
3. Băm từng cặp đỉnh: ghép mỗi đỉnh với vài đỉnh ngay sau nó, tạo thành bộ ba (tần số 1, tần số 2, khoảng cách thời gian). Theo bài báo, mỗi bộ ba được nén vào khoảng 30 bit và lưu trong một bảng băm khổng lồ.

Vì sao phải ghép cặp? Một đỉnh riêng lẻ (chỉ một tần số) xuất hiện trong rất nhiều bài hát. Một cặp đỉnh kèm khoảng cách thời gian thì "hiếm" hơn nhiều, nên tra bảng băm nhanh và chính xác hơn. Theo Wang, cách ghép cặp giúp việc tìm kiếm nhanh hơn khoảng 10.000 lần.

3. Khớp bài hát bằng cách "đếm phiếu"

Khi bạn thu một đoạn nhạc, Shazam tính các dấu vân tay của đoạn đó rồi tra bảng băm. Mỗi lần trùng, ta tính độ lệch thời gian = thời điểm trong bài gốc − thời điểm trong đoạn thu. Nếu đúng là bài đó, rất nhiều cặp trùng sẽ có cùng một độ lệch. Bài nào có nhiều "phiếu" nhất cho cùng một độ lệch thì thắng.

Chương trình mô phỏng dưới đây tạo 3 "bài hát", thu một đoạn 40 khung của bài B bắt đầu từ khung 120, rồi cố tình làm mất và làm nhiễu một số đỉnh:

Mô phỏng Shazam: băm cặp đỉnh và đếm độ lệch

#include <bits/stdc++.h>
using namespace std;
// Bộ sinh số giả ngẫu nhiên đơn giản (cho cùng dữ liệu với bản Python)
struct LCG { long long x; long long next(){ x = (x * 1103515245 + 12345) % 2147483648LL; return x; } };
vector<int> makeSong(long long seed, int n = 200){
    LCG g{seed}; vector<int> p(n);
    for(int i = 0; i < n; i++) p[i] = (g.next() >> 16) % 64;   // tần số "đỉnh" của mỗi khung
    return p;
}
// Dấu vân tay = (tần số 1, tần số 2, khoảng cách) của hai đỉnh gần nhau
vector<pair<array<int,3>,int>> hashes(const vector<int>& p){
    vector<pair<array<int,3>,int>> r;
    for(int i = 0; i < (int)p.size(); i++)
        for(int d = 1; d <= 3; d++)
            if(i + d < (int)p.size() && p[i] >= 0 && p[i+d] >= 0) r.push_back({{p[i], p[i+d], d}, i});
    return r;
}
int main(){
    vector<string> names = {"Bai hat A", "Bai hat B", "Bai hat C"};
    vector<vector<int>> songs = {makeSong(7), makeSong(42), makeSong(2024)};
    map<array<int,3>, vector<pair<int,int>>> db;                // bảng tra: dấu vân tay -> (bài, thời điểm)
    for(int s = 0; s < 3; s++) for(auto& [h, t] : hashes(songs[s])) db[h].push_back({s, t});
    // Đoạn thu âm 40 khung từ khung 120 của bài B, có mất và nhiễu đỉnh
    vector<int> clip(songs[1].begin() + 120, songs[1].begin() + 160);
    LCG g{99};
    for(int i = 0; i < 40; i++){ if(i % 5 == 0) clip[i] = -1; else if(i % 7 == 0) clip[i] = (g.next() >> 16) % 64; }
    map<pair<int,int>, int> votes;
    for(auto& [h, tq] : hashes(clip))
        for(auto& [s, t] : db[h]) votes[{s, t - tq}]++;         // cùng độ lệch thời gian
    for(int s = 0; s < 3; s++){
        int best = 0, off = 0;
        for(auto& [k, c] : votes) if(k.first == s && c > best){ best = c; off = k.second; }
        printf("%s: %2d cap khop (do lech %d)\n", names[s].c_str(), best, off);
    }
}

from collections import defaultdict

def lcg(seed):
    # Bộ sinh số giả ngẫu nhiên đơn giản (để bản C++ và Python cho cùng dữ liệu)
    x = seed
    while True:
        x = (x * 1103515245 + 12345) % 2**31
        yield x

def make_song(seed, n=200):
    g = lcg(seed)
    return [(next(g) >> 16) % 64 for _ in range(n)]      # mỗi khung thời gian: tần số "đỉnh" mạnh nhất

def hashes(peaks):
    # Ghép từng cặp đỉnh gần nhau thành một "dấu vân tay": (tần số 1, tần số 2, khoảng cách)
    for i in range(len(peaks)):
        for d in (1, 2, 3):
            if i + d < len(peaks) and peaks[i] >= 0 and peaks[i + d] >= 0:
                yield (peaks[i], peaks[i + d], d), i

songs = {"Bai hat A": make_song(7), "Bai hat B": make_song(42), "Bai hat C": make_song(2024)}
db = defaultdict(list)                            # bảng băm: dấu vân tay -> (bài hát, thời điểm)
for name, peaks in songs.items():
    for h, t in hashes(peaks):
        db[h].append((name, t))

# Đoạn thu âm 40 khung từ khung thứ 120 của bài B, bị mất và nhiễu một số đỉnh
clip = songs["Bai hat B"][120:160]
g = lcg(99)
clip = [-1 if i % 5 == 0 else ((next(g) >> 16) % 64 if i % 7 == 0 else f) for i, f in enumerate(clip)]

votes = defaultdict(int)
for h, tq in hashes(clip):
    for name, t in db.get(h, []):
        votes[(name, t - tq)] += 1                # cùng độ lệch thời gian => khớp thật
for name in songs:
    best = max(((c, off) for (s, off), c in votes.items() if s == name), default=(0, 0))
    print(f"{name}: {best[0]:2d} cap khop (do lech {best[1]})")

Kết quả chạy (bản Python; bản C++ cũng tìm ra bài B với độ lệch 120):

Bai hat A:  1 cap khop (do lech 88)
Bai hat B: 51 cap khop (do lech 120)
Bai hat C:  1 cap khop (do lech 114)

Dù đoạn thu bị mất 1/5 số đỉnh và nhiễu thêm một số đỉnh khác, bài B vẫn có 51 cặp khớp cùng độ lệch 120 – đúng vị trí bắt đầu của đoạn thu. Các bài khác chỉ trùng ngẫu nhiên 1 cặp.

4. Vì sao Shazam chịu được tiếng ồn?

• Tiếng ồn chỉ làm mất bớt một số đỉnh, nhưng các đỉnh mạnh của bài hát vẫn còn.
• Theo bài báo năm 2003, chỉ cần khoảng 1–2% dấu vân tay còn khớp trong một đoạn thu 15 giây là đã nhận ra bài hát.
• Tra bảng băm gần như tức thì, nên thời gian tìm không phụ thuộc nhiều vào số bài trong kho.

5. Bạn học được gì từ đây?

• Bảng băm (hash table) giúp tra cứu nhanh – trong C++ là unordered_map, trong Python là dict.
• Chọn đặc trưng bền vững (đỉnh tần số) quan trọng hơn lưu toàn bộ dữ liệu.
• "Đếm phiếu" theo độ lệch là cách hay để loại bỏ những lần trùng ngẫu nhiên.

Bài tập luyện tập

• CSES – Sum of Two Values (dùng bảng băm để tìm nhanh)
• CSES – String Matching (tìm một đoạn trong chuỗi dài – có thể dùng hàm băm chuỗi)
• Sửa code: thu đoạn ngắn hơn (20 khung) và nhiễu nhiều hơn. Đến lúc nào chương trình nhận nhầm bài?

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 24: Bàn phím điện thoại đoán chữ bạn định gõ như thế nào? Cây Trie và mô hình n-gram

Đọc tiếp: bàn phím & cây Trie →

← Bài trước: bầu cử & CondorcetXem tất cả 27 bài →

Nguồn tham khảo

• Wang (2003) – An Industrial-Strength Audio Search Algorithm, ISMIR 2003
• Apple Newsroom (20/11/2024) – Shazam hits 100 billion song recognitions
• Berkeley Haas – How two Haas alumni ushered in one of the world's most popular apps
• CNBC (11/12/2017) – Apple confirms Shazam deal
• Macworld (24/09/2018) – Apple completes Shazam acquisition