ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Bùi Thanh Xuân

CHUỖI ĐẶC TRƯNG ÂM THANH VÀ ỨNG DỤNG
TRONG TÌM KIẾM NHẠC SỐ

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin

HÀ NỘI – 2009


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Bùi Thanh Xuân

CHUỖI ĐẶC TRƯNG ÂM THANH VÀ ỨNG DỤNG
TRONG TÌM KIẾM NHẠC SỐ

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hướng dẫn: TS. Nguyễn Hải Châu

HÀ NỘI – 2009


LỜI CẢM ƠN




MỤC LỤC
LỜI MỞ ĐẦU...........................................................................................................1
CHƯƠNG 1: TỔNG QUAN VỀ CHUỖI ĐẶC TRƯNG ÂM THANH VÀ CÁC
ỨNG DỤNG .............................................................................................................3
1.1 Giới thiệu.........................................................................................................3
1.2 Các khái niệm chuỗi đặc trưng âm thanh........................................................3
1.2.1 . Định nghĩa chuỗi đặc trưng âm thanh ...................................................3
1.2.2 . Các tham số của hệ thống chuỗi đặc trưng âm thanh.............................5
1.3 Các ứng dụng ..................................................................................................6
1.3.1 . Broadcast Monitoring (BM) ...................................................................6
1.3.2 . Ứng dụng liên thông âm thanh ...............................................................6
1.3.3 . Công nghệ lọc chia sẻ file ......................................................................7
1.3.4 . Tổ chức thư viện âm nhạc tự động .........................................................8
CHƯƠNG 2: CÁC PHƯƠNG PHÁP XÂY DỰNG VÀ TÌM KIẾM CHUỖI ĐẶC
TRƯNG ÂM THANH ..............................................................................................9
2.1. Nguyên tắc cơ bản xây dựng hệ thống chuỗi đặc trưng âm thanh.................9
2.2. Các phương pháp xây dựng và tìm kiếm chuỗi đặc trưng trong ứng dụng nhận
dạng nhạc.............................................................................................................10
2.2.1. Phương pháp xây dựng hệ thống chuỗi đặc trưng mạnh.......................10
2.2.1.1. Trích rút chuỗi đặc trưng ................................................................10
2.2.1.2. Tìm kiếm chuỗi đặc trưng trong cơ sở dữ liệu ...............................16
2.2.2. Phương pháp xây dựng và tìm kiếm chuỗi đặc trưng dựa trên waveprint
..........................................................................................................21
2.2.2.1. Trích rút chuỗi đặc trưng ................................................................21
2.2.2.2. Tìm kiếm chuỗi đặc trưng...............................................................25
CHƯƠNG 3: ỨNG DỤNG THỬ NGHIỆM .........................................................27
3.1. Phát biểu bài toán.........................................................................................27
3.2. Tổng quan hệ thống .....................................................................................27

chuỗi đặc trưng của một thư viện rất nhiều bài hát, và khi đó đoạn âm thanh có thể
được xác định. Điểm cốt lõi của vấn đề được trình bày là phương pháp trích rút chuỗi
đặc trưng và chiến lược tìm kiếm chuỗi đặc trưng rất hiệu quả, nó cho phép tìm kiếm
một cơ sở dữ liệu chuỗi đặc trưng lớn chỉ với những tài nguyên tính toán gới hạn.
Khóa luận gồm ba chương:
Chương 1: Tổng quan về chuỗi đặc trưng âm thanh và các ứng dụng. Chương
này trình bày một cách tổng quan nhất những khái niệm cơ bản liên quan đến chuỗi
đặc trưng âm thanh và những ứng dụng phổ biến của chuỗi đặc trưng âm thanh.
Chương 2: Các phương pháp xây dựng và tìm kiếm chuỗi đặc trưng âm thanh.
Trình bày hai phương phát trích rút và tìm kiếm chuỗi đặc trưng âm thanh phổ biến
hiện nay trong các ứng dụng nhận dạng nhạc là phương pháp xây dựng chuôi đặc
trưng mạnh và phương pháp xây dựng chuỗi đặc trưng dựa trên wavelet

1


Chương 3: Ứng dụng thử nghiệm. Chương này trình bày một ứng dụng cụ thể
của chuỗi đặc trưng âm thanh trong một lĩnh vực đang rất được quan tâm hiện nay đó
là nhận dạng nhạc số. Trong này sẽ mô tả khái quát về chương trình thử nghiệm của
ứng dụng nhận dạng nhạc và những kết quả đạt được

2


CHƯƠNG 1: TỔNG QUAN VỀ CHUỖI ĐẶC TRƯNG ÂM
THANH VÀ CÁC ỨNG DỤNG
1.1 Giới thiệu
Chuỗi đặc trưng âm thanh là một tập các thuộc tính của âm thanh được dùng để
xác định các dạng khác nhau của âm thanh bao gồm âm nhạc, phát thanh radio và các
tác động khác tới âm thanh. Mục tiêu đầu tiên của chuỗi đặc trưng âm thanh là thiết

bằng nhau chính xác về mặt toán học của cặp H(X), H(Y) đưa đến sự bằng nhau của
cặp X và Y với xác xuất xẩy ra lỗi rất thấp. Đối với hàm băm mật mã được xây dựng
hợp lệ thì xác xuất này là 2-n, trong đó n bằng số bit của giá trị băm. Sử dụng các
hàm băm mật mã là một phương pháp hiệu quả hiện có để kiểm tra các dữ liệu cụ thể
của mục X có chứa trong tập dữ liệu lớn được đưa ra là Y = {

i

} hay không. Thay

vì lưu trữ và so sánh với tất cả dữ liệu trong Y thì chỉ cần lưu trữ thành tập các giá trị
băm { hi = H (Yi ) } và so sánh H(X) với tập các giá trị băm.
Nếu như thế có thể ta nghĩ rằng các hàm băm mật mã là một ứng cử tốt cho các
hàm chuỗi đặc trưng. Tuy nhiên với độ hồi tưởng được giới thiệu bên trên, thay vì sự
bằng nhau chính xác về mặt toán học, chúng ta quan tâm đến đặc điểm tương tự nhau.
Ví dụ, chất lượng của bản CD gốc của Rolling Stones-Angie và bản MP3 ở tốc độ
128Kb/s giống nhau với cơ quan thính giác của con người nhưng sóng của chúng có
thể khá là khác nhau. Mặc dù hai bản nhạc đó có cảm giác là giống nhau nhưng về
mặt toán học chúng khác nhau. Vì thế các hàm băm mật mã không thể đưa ra quyết
định dựa trên sự bằng nhau trực giác của hai bản đó.
Một câu hỏi khác được đặt ra là: “Có thể tạo ra một hàm chuỗi đặc trưng mà
cung cấp các chuỗi đặc trưng bằng nhau cho những đối tượng giống nhau về mặt
cảm giác không?” Câu hỏi là rất hợp lý nhưng câu trả lời là mô hình cho sự giống
nhau cảm giác về cơ bản là không thực hiện được. Sự giống nhau cảm giác của cặp
đối tượng X và Y và cặp đối tượng khác Y và Z không nhất thiết bao hàm sự giống
nhau của cặp đối tượng X và Z.
Việc đưa ra những lý lẽ trên mục đích là đề xuất cách xây dựng một hàm chuỗi
đặc trưng theo cách mà các đối tượng âm thanh giống nhau về mặt cảm giác đưa đến
kết quả là những chuỗi đặc trưng giống nhau. Hơn nữa, để có thể phân biệt giữa
những đối tượng âm thanh khác nhau, phải có xác xuất mà các đối tượng âm thanh

dùng để xác định.
• Tốc độ tìm kiếm và khả năng mở rộng (Search speed and scalability):
Mất bao lâu để tìm ra một chuỗi đặc trưng trong cơ sở dữ liệu chuỗi đặc
trưng? Phải làm gì nếu cơ sở dữ liệu chứa hàng trăm nghìn bài hát? Đối với
sự triển khai về mặt thương mại của các hệ thống chuỗi đặc trưng âm thanh,
tốc độ tìm kiếm và khả năng mở rộng của hệ thống là yếu tố then chốt. Tốc
độ tìm kiếm nên là khoảng mili giây cho cơ sở dữ liệu chứa khoảng 100000
bài hát và chỉ sử dụng nguồn tài nguyên tính toán giới hạn
Năm tham số cơ bản này có ảnh hưởng lẫn nhau. Ví dụ, nếu một ứng dụng
muốn granularity thấp hơn thì nó cần trích ra một chuỗi đặc trưng lớn hơn để thu

5


được cùng độ tin cậy. Điều này là vì tỷ lệ khẳng định sai nghịch đảo liên quan đến cỡ
chuỗi đặc trưng. Một ví dụ khác: tốc độ tìm kiếm nói chung sẽ tăng lên khi một ứng
dụng được xây dựng với chuỗi đặc trưng mạnh (robust) hơn. Điều này là vì tìm kiếm
chuỗi đặc trưng là phép tìm kiếm xấp xỉ. Giả sử một chuỗi đặc trưng tương tự vừa
được tìm thấy, nếu các thuộc tính càng mạnh hơn thì độ xấp xỉ càng nhỏ hơn. Vì thế
tốc độ tìm kiếm có thể được tăng lên đáng kể.

1.3 Các ứng dụng
1.3.1 . Broadcast Monitoring (BM)
BM hầu như là ứng dụng nổi tiếng nhất của chuỗi đặc trưng âm thanh. BM là
giải pháp phù hợp để dò tìm, giám sát các bài hát, các quảng cáo và kiểm tra các
chương trình phát thanh. Nó đề cập đến việc tạo ra danh sách (playlist) tự động của
radio, ti vi hoặc truyền hình web, truyền hình vệ tinh, trong số đó mục đích là tập
hợp tiền bản quyền, kiểm tra chương trình, kiểm tra quảng cáo và đo số người sử
dụng. Khi bạn cần giám sát hai đài phát hoặc thậm chí hai nghìn đài phát, hệ thống sẽ
cung cấp những danh sách (playlist) và các bản báo cáo cùng các chỉ dẫn kỹ thuật


1.3.3 . Công nghệ lọc chia sẻ file
Ví dụ điển hình cho công nghệ lọc để chia sẻ file là Napster. Bắt đầu vào tháng
6 năm 1999, người dùng tải về Napster client có thể chia sẻ và tải về được một bộ
sưu tập nhạc miễn phí rất lớn. Sau đó, vì vấn đề pháp lý trong ngành công nghiệp âm
nhạc, người dùng Napster bị cấm tải về những bài hát có bản quyền. Vì thế vào tháng
3 năm 2001 Napster thiết lập một bộ lọc âm thanh trên cơ sở là tên file để ngăn cản
việc tải những bài hát có bản quyền (sử dụng công nghệ lọc dựa trên văn bản để lọc
tên các bài hát). Bộ lọc đó không hiệu quả, bởi vì người dùng bắt đầu cố ý viết sai
chính tả tên file. Vào tháng 5 năm 2001 Napster giới thiệu hệ thống chuỗi đặc trưng
âm thanh bởi Relatable, nó hướng vào việc lọc ra những thành phần có bản quyền
dựa trên nội dung âm thanh vì thế thậm chí nếu chúng có bị viết sai chính tả thì vẫn
bị nhận ra. Napster bị khai tử chỉ hai tháng sau đó.
Trong một dịch vụ chia sẻ file hợp pháp ứng dụng có thể áp dụng lên lịch lọc
chi tiết hơn là việc chỉ lọc được những thành phần có bản quyền.
Mặc dù từ quan điểm của một người tiêu dùng, bộ lọc âm thanh có thể được
xem như một công nghệ không được mong đợi nhưng cũng có một số lợi ích tiềm
năng đối với người tiêu dùng. Đầu tiên nó có thể tổ chức tên của các bài hát trong
các kết quả tìm kiếm theo một cách phù hợp bằng cách sử dụng siêu dữ liệu đáng tin
cậy của cơ sở dữ liệu chuỗi đặc trưng. Thứ hai, chuỗi đặc trưng có thể đảm bảo rằng
những bài hát được tải về thực sự là những bài hát được mong đợi.

7


1.3.4 . Tổ chức thư viện âm nhạc tự động
Ngày nay nhiều người dùng máy tính có một thư viện âm nhạc chứa vài trăm
đôi khi thậm chí là vài nghìn bài hát. Các bản nhạc nói chung được lưu trữ trong định
dạng nén (thường là MP3) trong ổ cứng của họ. Bởi vì những bài hát này thu được từ
nhiều nguồn khác nhau, như xao chép từ đĩa CD hoặc tải về từ các mạng chia sẻ file,

• Các thuộc tính ngữ nghĩa luôn luôn có nghĩa mập mờ và không rõ ràng. Ví
dụ những người có sở thích khác nhau thì có quan điểm khác nhau đối với
việc phân loại. Ngoài ra, trên thực tế ngữ nghĩa có thể thay đổi theo thời
gian. Ví dụ, âm nhạc được phân loại như cách đây 25 năm là hard rock thì
ngày nay được coi là soft listening. Điều này làm cho việc phân tích toán
học trở nên khó khăn.
• Các thuộc tính ngữ nghĩa nói chúng khó tính toán hơn các thuộc tính phi
ngữ nghĩa.
• Các thuộc tính ngữ nghĩa không thích hợp với tất cả. Ví dụ, số nhịp trên
phút không thể áp dụng tiêu biểu cho nhạc cổ điển được.
Câu hỏi thứ hai được đưa ra là sự biểu diễn của các chuỗi đặc trưng. Một dạng
điển hình là ta có thể biểu diễn nó như một vectơ các số thực, trong đó mỗi thành

9


phần biểu thị trọng lượng (weight) của thuộc tính thuộc tri giác cơ bản nào đó. Quan
điểm thứ hai là ngăn cản tiến gần hơn đến các hàm băm mã hóa và biểu diễn các
chuỗi đặc trưng số như những xâu bit. Vì lý do giảm độ phức tạp tìm kiếm chúng ta
quyết định làm việc với quan điểm thứ hai. Theo quan điểm đầu tiên thì việc đo độ
giống nhau có dính dáng đến các phép cộng/trừ các số thực thậm chí có thể là các
phép nhân số thực. Các chuỗi đặc trưng dựa trên cơ sở biểu diễn bởi các bit có thể
được so sánh bằng cách đơn giản là đếm các bit. Khi đưa ra viễn cảnh những ứng
dụng được mong đợi, chúng ta không mong muốn robustness cao cho mỗi ứng dụng
và mỗi bit trong chuỗi đặc trưng nhị phân. Vì thế, trái ngược với các hàm băm mật
mã mà điển hình có tối đa vài trăm bit, chúng ta sẽ cho phép các chuỗi đặc trưng có
vài nghìn bit. Các chuỗi đặc trưng chứa số lượng bit lớn cho phép nhận dạng tin cậy
thậm chí nếu tỷ lệ phần trăm của các bit không phù hợp là khá cao.
Câu hỏi cuối cùng liên quan đến granularity của các chuỗi đặc trưng. Trong các
ứng dụng mà chúng ta vạch ra không đảm bảo rằng các file âm thanh cần nhận dạng

frame chồng nhau (overlapping). Các frame chồng có độ dài 0.37 giây và có trọng
lượng bằng cửa sổ Hamming với một thừa số chồng 31/32. Kết quả của kế hoạch này
trong việc trích rút của một chuỗi đặc trưng con cho mỗi 11.6 mili giây. Trong
trường hợp xấu nhất các ranh giới của frames sử dụng trong việc nhận dạng là 5.8
mili giây với chú ý là các ranh giới được dùng trong cơ sở dữ liệu của các chuỗi đặc
trưng đã được tính toán trước. Sự chồng lấp lớn đảm bảo rằng thậm chí trong trường
hợp xấu nhất các chuỗi đặc trưng con của đoạn âm thanh được nhận dạng vẫn giống
các chuỗi đặc trưng con của những đoạn giống thế trong cơ sở dữ liệu. Vì sự chồng
lấp lớn các chuỗi đặc trưng con tiếp sau có sự giống nhau nhiều và biến đổi rất chậm
theo thời gian. Hình 3a biểu diễn một ví dụ về khối chuỗi đặc trưng được rút ra và
các đặc trưng biến đổi rất chậm theo thời gian.

Hình 1: Tổng quan về quá trình trích chọn chuỗi đặc trưng.
Các thuộc tính âm thanh thuộc tri giác quan trọng nhất nằm trong miền tần số.
Vì thế một sự biểu diễn quang phổ được tính toán bởi hiệu quả biểu diễn của phép
biến đổi Fourier trên mỗi frame. Vì độ nhạy pha của khai triển Fourier khác ranh giới
của frame và sự kiện mà cơ quan thính giác của con người (Human Auditory System
– HAS) không nhạy với pha, chỉ có giá trị tuyệt đối của phổ là được giữ lại, ví dụ
năng lượng mật độ phổ.

11


Để mà rút ra giá trị chuỗi con 32 bit cho mỗi frame thì các dải tần không chồng
chất 33 được chọn. Những dải tần này nằm trong phạm vi từ 300Hz đến 2000Hz
(phạm vi phổ có liên quan nhất đến HAS) và có một khoảng cách logarit. Khoảng
cách logarit được chọn bởi vì nó được biết đến bởi HAS có tác dụng trên những dải
tần xấp xỉ logarit (vì thế được gọi là thang Bark). Bằng thực nghiệm dải tần được
kiểm tra sự khác nhau của tín hiệu năng lượng (đồng thời theo thời gian và tần số) là
thuộc tính rất mạnh của nhiều loại quá trình xử lý. Nếu chúng ta ký hiệu năng lượng

âm thanh được lấy mẫu một frame có độ dài 2048 mẫu. Nếu biến đổi Fourier được
thực thi như một điểm cố định FFT giá trị thực thuật toán chuỗi đặc trưng vừa nói
chạy hiệu quả trên các thiết bị cầm tay như PDA hoặc điện thoại di động.
b)

Phân tích khẳng định sai

Hai tín hiệu âm thanh 3 giây được trình bày giống nhau nếu khoảng cách
Hamming (ví dụ số bit lỗi) giữa hai khối chuỗi đặc trưng được suy ra thấp hơn điểm
bắt đầu T một ít. Giá trị điểm bắt đầu T này xác định trực tiếp tỷ lệ khẳng định sai Pf ,
ví dụ tỷ lệ của tín hiệu âm thanh không được trình bày trực tiếp bằng: T nhỏ hơn, xác
xuất Pf sẽ nhỏ hơn. Mặt khác, giá trị T nhỏ sẽ không ảnh hưởng đến xác xuất phủ
định sai Pn , ví dụ xác xuất mà hai tín hiệu ”bằng nhau” nhưng không được xác định.
Để phân tích sự lựa chọn điểm bắt đầu T, chúng ta giả sử rằng quá trình xử lý
việc rút ra chuỗi đặc trưng mang lại các bit i.i.d ngẫu nhiên (i.i.d = independent and
identically distributed – độc lập và được phân bố tương tự nhau). Số bit lỗi sau đó sẽ
có phân phối nhị thức (n,p), trong đó n bằng số bit được lấy ra và p (=0.5) là xác xuất
mà bit 0 hoặc 1 được rút được lấy ra. Từ đó n (=8192=32*256) lớn trong ứng dụng
của chúng ta, phân phối nhị thức có thể xấp xỉ bằng phân phối thông thường với một
giá trị trung bình μ = np và độ lệch chuẩn σ = (np(1 − p)) . Đưa ra khối chuỗi đặc
trưng F1 , xác xuất mà khối chuỗi đặc trưng F2 được chọn ngẫu nhiên có ít hơn

13


T = αn lỗi với F1 được đưa ra bởi:

Pf (α ) =

1

gian. Sự tương quan này không chỉ là vì sự tương quan thời gian vốn có trong âm
thanh mà còn bởi sự chồng lấp lớn của các frame được dùng trong việc rút ra chuỗi
đặc trưng. Sự tương quan cao hơn kéo theo một độ lệch chuẩn lớn hơn, như biểu diễn
bởi tham số dưới đây.
Giả sử 1 nguồn đối xứng {-1,1} với xác xuất có kí hiệu xi và xi +1 là giống nhau
và bằng q. Sau đó được biểu diễn:
E [xi xi + k ] = a

k

(2.3)

Trong đó a=2.q-1. Nếu nguồn Z là độc nhất hoặc 2 chuỗi X và Y, sau đó Z là
đối xứng và
E [z i z i + k ] = a

2k

(2.4)

Với N lớn, độ lệch chuẩn trung bình Z N trên N mẫu liên tiếp của Z có thể được
mô tả xấp xỉ bằng phân phối thông thường với giá trị trung bình 0 và độ lệch chuẩn
bằng:
1+ a2
N (1 − a 2 )

(2.5)

Thừa số tương quan a giữa các bit chuỗi đặc trưng nối tiếp bao hàm sự tăng lên
trong độ lệch tiêu chuẩn vì tỉ lệ bit lỗi (BER) bởi thừa số:

2
⎝ 3 2
⎠

(2.7)

Điểm bắt đầu cho tỷ lệ bit lỗi sử dụng trong các thử nghiệm là α = 0.35. Giá trị trung
bình này vượt qua 8192 bits và phải ít hơn 2867 bits lỗi để mà quyết định những khối
chuỗi đặc trưng bắt nguồn từ những bài hát giống nhau. Sử dụng công thức (2.7)
chúng ta đạt tới tỷ lệ khẳng định sai của erfc(6.4)/2=3.6*10-20 rất thấp.

15


2.2.1.2.

Tìm kiếm chuỗi đặc trưng trong cơ sở dữ liệu

Tìm kiếm các chuỗi đặc trưng đã được trích rút trong cơ sở dữ liệu chuỗi đặc
trưng là công việc không đơn giản. Thay vào đó việc tìm kiếm chuỗi đặc trưng dạng
bit dễ dàng hơn, chuỗi đặc trưng gần giống nhất sẽ được tìm ra. Chúng ta trình bày
quá trình tìm kiếm này với các số liệu dựa trên những chuỗi đặc trưng được trích rút
như bên trên. Giả sử cơ sở dữ liệu chuỗi đặc trưng có cỡ vừa phải chứa khoảng
10000 bài hát với độ dài trung bình là 5 phút. Điều này tương đương với xấp xỉ 250
triệu chuỗi đặc trưng con. Để xác định một khối chuỗi đặc trưng có nguồn gốc từ
đoạn âm thanh chưa biết chúng ta phải tìm ra khối chuỗi đặc trưng giống nhất trong
cơ sở dữ liệu. Nói theo cách khác chúng ta phải tìm ra vị trí trong 250 triệu chuỗi đặc
trưng con mà ở đó tỷ lệ bít lỗi là tối thiểu. Đây là quá trình của cách tìm kiếm brute
force. Tuy nhiên phải làm phép so sánh với 250 triệu khối chuỗi đặc trưng. Sử dụng
một máy PC hiện đại thì có thể đạt được tỷ lệ so sánh xấp xỉ 200000 khối chuỗi đặc

tra cứu chứa 232 mục từ thường không khả thi hoặc không thực tế hoặc là cả hai. Hơn
nữa bảng tra cứu sẽ được làm đầy bởi vì chỉ một số giới hạn các bài hát có thể đặt
trong bộ nhớ. Vì thế trong thực tế một bảng băm được dùng thay cho bảng tra cứu.
Chúng ta thực hiện lại tính toán số các phép so sánh khối chuỗi đặc trưng trung
bình trên định dạng đối với 10000 bài hát trong cơ sở dữ liệu. Vì cơ sở dữ liệu chứa
xấp xỉ 250 triệu chuỗi đặc trưng con, số vị trí trung bình trong một danh sách sẽ là
0.0058 (=250*106/1032). Nếu chúng ta giả thiết rằng tất cả các chuỗi đặc trưng con có
khả năng bằng nhau, số phép so sánh chuỗi đặc trưng trung bình trên định dạng chỉ là
15 (=0.058 * 256). Tuy nhiên chúng ta quan sát trong thực tế, vì sự phân phối không
đồng đều của các chuỗi đặc trưng con, số phép so sánh chuỗi đặc trưng tăng lên xấp

17


xỉ 20. Trong 300 phép so sánh trung bình được yêu cầu, thời gian tìm kiếm trung
bình cho mỗi lần là 1.5 mili giây trên một máy PC hiện đại. Bảng tra cứu có thể được
thực thi theo cách mà nó không ảnh hưởng đến thời gian tìm kiếm. Theo giá của
bảng tra cứu, thuật toán tìm kiếm được đề xuất nhanh hơn xấp xỉ 800000 lần phương
pháp brute force.
Một ví dụ về biểu đồ các lỗi bít trên chuỗi đặc trưng đối với một khối chuỗi đặc
trưng mà không chứa bất kỳ chuỗi đặc trưng con không lỗi nào- được thể hiện trong
hình 5.

Hình 5: Bit lỗi trên chuỗi đặc trưng (đường nhạt) và độ tin cậy của bit sai
đáng tin cậy nhất (đường đậm) cho bản MP3@Kbps của “O Fortuna” của Carl
Orff.
Tuy nhiên có những chuỗi đặc trưng con chỉ chứa một lỗi. Vì vậy thay vì chỉ
kiểm tra những vị trí trong cơ sở dữ liệu mà ở đó một trong 256 chuỗi đặc trưng con
xuất hiện, chúng ta có thể kiểm tra toàn bộ các vị trí nơi mà các chuỗi đặc trưng xuất
hiện và có khoảng cách Hamming của một chuỗi với toàn bộ 256 chuỗi đặc trưng

tin cậy nhất và tất cả các bit có thể thay đổi khác. Nếu thông tin về độ tin cậy là
chính xác, giả sử rằng trong trường hợp một chuỗi đặc trưng con có 3 bit lỗi, những
bit với độ tin cậy 1, 2 và 3 là không chính xác. Nếu đây là trường hợp – các khối
chuỗi đặc trưng mà trong đó số bit lỗi trên một chuỗi đặc trưng con tối thiếu là 3 – có
thể được xác định bằng cách tạo ra những vị trí ứng cử với chỉ 8 (=23) chuỗi đặc
trưng con. So sánh với hệ số 5489 đạt được khi sử dụng tất cả các chuỗi đặc trưng
con với một khoảng cách Hamming của 3 để phát ra các vị trí ứng cử, đây là một cải
tiến với hệ số xấp xỉ 686.
Trong thực tế thông tin về độ tin cậy là không chính xác (ví dụ nó xẩy ra khi
một bit với độ tin cậy thấp được thu nhận chính xác và ngược lại) và vì thế sự cải

19


tiến là ít hiệu quả, nhưng vẫn có ý nghĩa. Điều này có thể thấy trong ví dụ ở hình 5.
Số bit lỗi tối thiểu trên chuỗi đặc trưng con là một. Như vừa đề cập trước đó, khối
chuỗi đặc trưng sau đó có thể được xác định bằng cách phát ra 33 nhịp. Hình 5 cũng
có một biểu đồ về độ tin cậy cho bit đáng tin cậy nhất bị thu nhận sai. Những độ tin
cậy được suy ra từ bản MP3@32Kbps sử dụng phương pháp đã đề xuất trên. Chúng
ta thấy rằng chuỗi đặc trưng con đầu tiên chứa 8 lỗi. Tám bit lỗi này không phải là 8
bit kém nhất bởi vì một trong những bit sai có độ tin cậy được chỉ ra là 27. Vì thế,
thông tin về độ tin cậy luôn luôn không đáng tin. Tuy nhiên nếu chúng ta coi như
chuỗi đặc trưng con 130 – chuỗi mà chỉ có một bit lỗi đơn – thì ta thấy rằng độ tin
cậy của bit sai được chỉ ra là 3. Vì thế khối chuỗi đặc trưng này chỉ đến vị trí chính
xác trong cơ sở dữ liệu chuỗi đặc trưng khi chỉ đảo chiều 3 bit kém nhất. Vì vậy bài
hát sẽ được nhận dạng chính xác.

Hình 6: Trình bày cơ sở dữ liệu chuỗi đặc trưng
Chúng ta sẽ kết thúc phần này bằng cách tham khảo hình 6 và đưa ra một ví dụ
về cách làm việc với thuật toán tìm kiếm đã được đề xuất. Chuỗi đặc trưng rút ra