Shazam thực ra hoạt động như thế nào?
(perthirtysix.com/how-the-heck-does-shazam-work)- Nhận diện nhạc diễn ra bằng cách biến dao động không khí mà micro thu được thành dạng sóng, rồi nén nó thành phổ tần thời gian cùng một số đỉnh tần số mạnh để tạo ra dấu vân tay của bài hát
- Dạng sóng thô rất dễ thay đổi theo âm lượng và môi trường phát, nên khó dùng làm tiêu chuẩn nhận dạng; cần áp dụng FFT cho từng đoạn ngắn để làm lộ ra cấu trúc tần số theo thời gian thì mới có thể so sánh ổn định
- Các đỉnh còn lại không được dùng như những điểm đơn lẻ mà được ghép thành cặp anchor và target zone để tạo hash; những tổ hợp này hoạt động như fingerprint hash đủ cụ thể để phân biệt một bản ghi âm nhất định
- Việc tìm kiếm không so khớp từng bài hát một mà dùng cấu trúc hash-first để tra cứu trực tiếp bằng khóa hash; ở bước cuối còn kiểm tra xem khoảng cách thời gian giữa các hash khớp nhau có trùng hay không để tăng độ tin cậy
- Cơ sở dữ liệu quy mô lớn trên máy chủ và cách làm on-device có khác nhau về quy mô lẫn ràng buộc, nhưng cốt lõi vẫn là loại bỏ phần lớn thông tin và chỉ giữ lại các đỉnh mốc để tìm bài hát nhanh ngay cả từ những đoạn clip ngắn và nhiều tạp âm
Quá trình diễn giải âm thanh theo chiều ngược lại
- Micro điện thoại đo dao động không khí bằng một màng rung rất mỏng, rồi chuyển nó thành dạng sóng — một chuỗi số biểu diễn áp suất không khí theo thời gian — để lưu lại
- Màng nhĩ của tai người cũng nhận cùng những sóng áp suất đó, nhưng điện thoại xử lý chúng không phải như âm thanh tự thân mà như một chuỗi số
- Âm thanh đi vào được lấy mẫu hàng chục nghìn lần mỗi giây, thường là 44,100 Hz
- Chỉ với dạng sóng thô thì rất khó nhận diện bài hát; cùng một bài nhưng nếu phát to hơn sẽ thành một dạng sóng hoàn toàn khác, và các bài khác nhau đôi khi cũng có thể tạo ra dạng sóng giống nhau
- Ngay cả khi bài hát giống nhau, môi trường phát khác nhau cũng làm dạng sóng thay đổi, nên bản thân dạng sóng không phù hợp làm tiêu chuẩn nhận dạng
- Để giảm vấn đề này, cần chia dạng sóng thành các mảnh nhỏ rồi áp dụng FFT để phân rã xem ở mỗi thời điểm có những tần số nào xuất hiện
- Nếu đổi thành câu hỏi thì nó tương đương với: "để tạo lại mẩu âm thanh ngắn này thì cần cộng những âm thuần nào lại với nhau?"
- Khi xếp kết quả của từng mảnh cạnh nhau, ta sẽ có phổ tần thời gian với trục thời gian, trục tần số và trục độ sáng
- FFT tận dụng thực tế rằng dù dạng sóng có phức tạp đến đâu, nó vẫn có thể được biểu diễn như tổng của các sóng sin với tần số, biên độ và pha khác nhau
- Ví dụ, nếu đưa vào 1,024 mẫu, nó sẽ trả về một phổ cho biết mỗi tần số chứa bao nhiêu năng lượng
- Với mỗi bin tần số, nó nhân toàn bộ mẫu với sóng sin ở tần số đó rồi cộng lại; nếu tần số đó thực sự có trong tín hiệu thì tổng sẽ lớn, còn không thì sẽ bị triệt tiêu
- Điểm cốt lõi của FFT là tốc độ; cách phân rã ngây thơ cần hàng triệu phép tính cho mỗi mảnh, còn FFT dùng tính đối xứng toán học để giảm xuống cỡ n log n
- Tốc độ này đủ nhanh để điện thoại cũng có thể chạy hàng trăm lần mỗi giây
- Thiết bị liên tục trượt cửa sổ này trên luồng audio, áp dụng FFT cho từng mảnh và chồng kết quả lên nhau để tạo phổ tần thời gian
- Ví dụ đơn giản thường dùng âm tổng hợp chỉ gồm một tần số thuần, giúp dễ hiểu, nhưng âm nhạc thực tế thì phức tạp hơn nhiều
- Khi đưa nhạc thật hoặc tiếng ngân nga vào micro, phổ tần thời gian sẽ trông rối hơn rất nhiều, nhưng FFT vẫn làm lộ cấu trúc trong đó theo thời gian thực
- Trong ví dụ trên trình duyệt, mọi audio đều được xử lý bên trong trình duyệt, không ghi âm lại cũng không gửi ra bên ngoài
Dấu vân tay càng ít càng mạnh
- Hệ thống không lưu toàn bộ phổ tần thời gian mà chỉ giữ lại những đỉnh lớn nhất, nén thành một tập điểm thưa
- Khi bỏ đi tín hiệu yếu và chỉ giữ những điểm mạnh nhất, ta chỉ còn lại các mốc âm học quan trọng nhất
- Lý do phải vứt bỏ phần lớn như vậy là vì việc lưu và tìm kiếm trên toàn bộ phổ tần thời gian quá chậm ngay cả với máy tính
- Ngưỡng càng cao thì các tín hiệu mờ càng biến mất, chỉ còn những đỉnh lớn tồn tại
- Cách làm này giúp tăng khả năng chống nhiễu
- Tạp âm nền sẽ thêm năng lượng thấp lên khắp phổ tần thời gian, nhưng thường không thể tạo ra các đỉnh mạnh nhất ở những vùng cụ thể
- Các mốc còn lại chính là những tần số chi phối nổi lên xuyên qua nhiễu
- Đổi lại, kiểu dấu vân tay này thường cho hiệu năng kém hơn khi người dùng tự hát lại bài hát
- Ngay cả khi hát rất đúng, hash tạo ra vẫn có khả năng khác với bản gốc
- Vì vậy các hệ thống dựa trên machine learning mới hơn xử lý tiếng ngân nga và giọng hát theo giai điệu thay vì theo tần số chính xác
Nối các điểm để tạo hash
- Một điểm đơn lẻ có khả năng phân biệt không cao, nhưng tổ hợp của hai điểm thì ít mang tính ngẫu nhiên hơn nhiều, nên phù hợp để dùng làm fingerprint hash
- Ví dụ, một 1,200 Hz ở một thời điểm nào đó có thể xuất hiện trong hàng nghìn bài hát, nhưng tổ hợp trong đó 2,400 Hz xuất hiện sau 0.3 giây kể từ 1,200 Hz thì cụ thể hơn rất nhiều
- Thuật toán lần lượt chọn từng đỉnh làm anchor, rồi xác định một target zone ở bên phải với phạm vi thời gian và tần số nhất định để ghép với mọi đỉnh nằm trong vùng đó
- Mỗi cặp tạo ra một hash ngắn từ ba con số: hai tần số và độ lệch thời gian
- Hash hoạt động như một đoạn mã ngắn luôn cho ra cùng một kết quả từ cùng một đầu vào, nhưng chỉ cần đầu vào thay đổi rất ít thì giá trị cũng đổi hoàn toàn
- Các hệ thống kiểu Shazam có cơ chế xử lý các dao động nhỏ, nhưng về cơ bản hash vẫn được tạo từ tần số và thời điểm chính xác
- Kết quả là những hash này hoạt động giống dấu vân tay của một bản ghi âm cụ thể hơn là của chính bài hát đó
- Vì vậy các bản cover hay remix sẽ khó nhận diện hơn
- Chỉ một bài hát dài 3 phút cũng có thể tạo ra hàng nghìn fingerprint hash như vậy, và cơ sở dữ liệu sẽ lưu tất cả chúng
- Điện thoại mang theo một số ít hash lấy từ clip 5 giây, còn cơ sở dữ liệu thì có hàng triệu hash rút ra từ số lượng bài hát khổng lồ trước khi bước vào giai đoạn so khớp
Tìm ra bản khớp chính xác
- Mỗi hash được dùng như một dạng địa chỉ; với từng hash lấy từ clip, hệ thống tra trực tiếp một bảng khổng lồ để tìm những bài hát có chứa hash đó
- Thay vì quét từng bài một, nó dùng chính hash làm khóa truy cập
- Cách trực quan kiểu song-first phải kiểm tra từng bài hát rồi xem các hash có chồng lên nhau không, nên càng nhiều bài thì càng chậm
- Bài viết biểu diễn điều này bằng thời gian O(N)
- Cơ sở dữ liệu ví dụ và danh sách hash của clip 5 giây được dùng để trực quan hóa sự kém hiệu quả này
- Máy tính có thể đảo ngược cách làm đó bằng phương thức hash-first
- Với mỗi hash, nó hỏi ngay: "những bài hát nào chứa hash này?"
- Có thể hình dung như mục lục tra cứu ở cuối sách: thay vì đọc lại mọi trang, ta đi thẳng đến mục của từ cần tìm
- Cách tiếp cận này khiến việc tra cứu gần với O(1)
- Dù có 100 bài hay 100 triệu bài thì thời gian xử lý nhìn chung vẫn tương tự nhau
- Số lượng hash khả dĩ là cực lớn, nên ngay cả khi có hàng triệu bài, mỗi địa chỉ thường cũng chỉ chứa một số ít mục
- Việc chia sẻ cùng một hash vẫn chưa đủ; bước xác minh cuối cùng diễn ra ở khoảng cách thời gian
- Ví dụ, nếu trong clip khoảng cách giữa 17403C và 19A998 là 1.2 giây, thì ở bài hát ứng viên khớp, hai hash tương ứng cũng phải cách nhau 1.2 giây
- Chỉ khi độ lệch thời gian của các hash trùng khớp với nhau và số lượng đủ nhiều thì mới trở thành một kết quả có độ tin cậy cao
- Toàn bộ hệ thống được thiết kế để phù hợp với những việc máy tính đặc biệt làm tốt
- Nó xoay quanh so sánh số và tra cứu địa chỉ
- Nhờ vậy, ngay cả khi đối chiếu với hàng triệu bài hát, toàn bộ truy vấn vẫn kết thúc trong thời gian ngắn hơn rất nhiều so với 1 giây
Cách tiếp cận hiện đại hơn
- Nhiều dịch vụ nhận diện bài hát kiểu Shazam gửi clip audio lên máy chủ và thực hiện so khớp trong một cơ sở dữ liệu dấu vân tay khổng lồ trên server
- Họ dùng cấu trúc này vì cơ sở dữ liệu rất lớn, liên tục thay đổi và việc tìm kiếm đòi hỏi lượng tính toán đáng kể
- Ngược lại, nhận diện on-device của Apple và Now Playing trên Google Pixel chạy toàn bộ cục bộ ngay trên điện thoại
- Chúng dùng cơ sở dữ liệu nhỏ hơn, được tuyển chọn kỹ hơn cùng các mô hình tối ưu hóa
- Đổi lại tính bao quát tuyệt đối để lấy tốc độ, đồng thời còn có các hướng tiếp cận machine learning tinh vi hơn, bền vững hơn trước nhiễu và biến dạng audio
- Cách làm on-device nhanh hơn và hoạt động được cả khi không có Internet, nhưng bị giới hạn ở cơ sở dữ liệu bài hát có thể so khớp nhỏ hơn rất nhiều
- Việc cập nhật bài hát mới cũng thường chậm hơn
- Khi phát hiện thay đổi vị trí, thiết bị có thể phải tải lại dữ liệu mới
- Sự khác biệt về các bài hát phổ biến theo từng khu vực cũng ảnh hưởng đến cách xây dựng dữ liệu on-device
- Bài hit ở Nhật Bản có thể khác với bài hit ở Mỹ
- Dù việc so khớp diễn ra trên server hay ngay trong thiết bị, kỹ thuật cốt lõi vẫn giống nhau
- Khi loại bỏ phần lớn thông tin và chỉ giữ lại một số đỉnh mốc ít ỏi, ngay cả một clip 5 giây thu trong quán cà phê ồn ào cũng biến thành một tập tọa độ đủ chính xác để chỉ ra một bài hát trong hàng triệu bài
- Cốt lõi của nhận diện không hẳn là nghe được thật nhiều, mà gần hơn với việc loại bỏ thật chính xác những gì cần bỏ qua
Bài báo nền tảng
- Phần lớn nội dung bài viết dựa trên bài báo năm 2003 của Avery Wang, An Industrial-Strength Audio Search Algorithm
- Nếu muốn đào sâu hơn về xử lý tín hiệu và thiết kế hệ thống, đây là điểm khởi đầu trực tiếp phù hợp nhất
- Toàn bộ luồng xử lý đi từ biến đổi dạng sóng, chọn đỉnh, hash cặp đỉnh, tra cứu chỉ mục đảo ngược, đến xác minh căn chỉnh thời gian
- Những bước này kết hợp lại để cho phép nhận diện bài hát nhanh ngay cả với các đoạn clip ngắn và nhiều tạp âm
1 bình luận
Ý kiến trên Hacker News
Nên xem kèm các tài liệu về Shazam Có bài báo gốc https://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf, và nếu thực sự hứng thú thì cũng đáng tìm xem bài thuyết trình YouTube của tác giả https://news.ycombinator.com/item?id=18069968 có bài viết của một nhân viên Shazam, https://news.ycombinator.com/item?id=38538996 có phần giải thích được đồng sáng lập xác nhận, và https://news.ycombinator.com/item?id=41127726 có bản tái hiện thuật toán bằng Go Cuối cùng thì với ML, nhiều trường hợp dữ liệu còn có giá trị hơn cả bản thân mã nguồn
Phỏng đoán gần đây của tôi là có khi hoàn toàn không phải vậy Với nhạc đại chúng thì nó thường nhận khá chuẩn, nhưng tôi đã thử Shazam nhiều lần với vài bản nhạc synth khá hay phát trong giờ nghỉ ở một giải trượt băng, và nó không tìm đúng được bài nào cả Có thể đó là các bài chưa phát hành hoặc quá ngách, nhưng cũng có vẻ đơn giản là Shazam đã thất bại khá nặng
Đây hiển nhiên là cùng họ công nghệ cũng được dùng cho ACR của TV Nhưng có lẽ việc Shazam có danh tiếng trực tuyến tốt hơn nhiều là vì nó tôn trọng ý định và sự đồng ý của người dùng Nếu TV cũng triển khai tương tự mà dữ liệu không chỉ bị đẩy sang mục đích bán quảng cáo, thì biết đâu có thể tạo ra thứ thực sự có lợi cho người tiêu dùng
Bài này có lẽ là một trong những phần giải thích trực quan hay nhất về thuật toán audio fingerprinting gốc trong bài báo Shazam năm 2003 Dù vậy, tôi cũng đoán rằng tới giờ họ đã chuyển sang mô hình ML ở một thời điểm nào đó
Có một thuật toán tên là DTW(dynamic time warping), nhưng hay bị bỏ qua Theo cảm giác của tôi, Shazam chắc cũng dùng nó ở mức độ nào đó
Nhận diện đúng cùng một bản ghi âm thì không khó lắm Nếu là cùng một bản ghi, tiến trình hợp âm và nhịp thời gian có thể lặp lại chính xác, nên kiểu công nghệ nhận diện này đã tồn tại từ hơn 10 năm trước rất lâu rồi Ngược lại, nhận ra cùng một bài hát qua các bản cover tức là những bản ghi khác nhau, thì khó hơn nhiều Audible Magic tuyên bố tại https://www.audiblemagic.com/2024/02/07/identifying-cover-songs-live-performances-ai-clones-and-more/ rằng họ có thể nhận ra nhiều bản biểu diễn khác nhau của cùng một bài, thậm chí cả parody, nhưng dĩ nhiên đó là cách làm dùng AI và nhiều tính toán hơn
Ban đầu tôi nghĩ lại là chủ đề này nữa à, nhưng rồi thấy đó là SCP Tên miền này trông hơi đáng ngờ Một phân tích đầy đủ hơn bài viết năm 2022 của CameronMacLeod là https://news.ycombinator.com/item?id=38531428, còn bài của Slate năm 2009 là https://news.ycombinator.com/item?id=893353
Phải thêm cái này vào danh sách dự án của tôi Một bản Dinosaur game mà nhảy không bằng phím bấm mà bằng tiếng gà gáy chắc sẽ vui lắm
Tôi tò mò liệu có cách nào để ngăn các ứng dụng kiểu Shazam phát hiện được không Ví dụ như trộn thêm nhiễu hay dùng kỹ thuật nào khác
Năm 1986 tôi đã thử làm cái này như một dự án khoa học trên Apple ][c