1
Lời cảm ơn

Trước hết chúng em xin bày tỏ lời cảm ơn chân thành và sâu sắc nhất đến TS. Nguyễn
Hải Châu, người thầy đã hướng dẫn em trong đề tài này. Đây là đề tài mới và nhiều khó khăn
nhưng nhờ sự động viên và hướng dẫn nhiệt tình của thầy em đã có kết quả như hôm nay.
Em xin gửi lời cảm ơn chân thành đến các thầy cô trong khoa CNTT - Trường Đại
học Công Nghệ vì những kiến thứ
c quý báu mà các thầy cô đã truyền dạy trong bốn năm vừa
qua. Những kiến thức này có giá trị đối với chúng em trong quá trình thực hiện luận văn,
cũng như trong quá trình xây dựng sự nghiệp trong tương lại.
Cảm ơn bạn bè đã luôn bên cạnh giúp đỡ hướng dẫn tôi trong quá trình nghiên cứu,
tìm hiểu khóa luận này.
Cuối cùng con xin cảm ơn bố mẹ và các anh chị đã luôn động viên giúp đỡ con vượt
qua những khó khăn
để hoàn thành khóa luận này.
Mặc dù đã rất cố gắng tập trung nghiên cứu khóa luận song sẽ không tránh khỏi
những thiếu sót mong các thầy cô thông cảm.

Chân thành cảm ơn

3
Mục lục

Danh mục hình vẽ
Danh mục các từ viết tắt
QBSH
Query by Singing/Humming
Truy xuất bởi giai điệu và lời hát
MaART
Musical and Audio Retrieval tools
Công cụ tìm kiếm nhạc
MIR
Muscal Information Retrieval
Hệ thống tìm kiếm âm nhạc

5
LỜI MỞ ĐẦU
Ngày nay nhu cầu của con người càng ngày càng lớn hơn. Sự phát triển của
Internet, Google, Yahoo, MSN… là những tên tuổi được biết đến trong lĩnh vực cung
cấp dịch vụ tìm kiếm tài liệu qua mạng. Với những dịch vụ tìm kiếm tài liệu qua
mạng. Với những dịch vụ này người dùng có thể tìm kiếm các tài liệu, hình ảnh, video,
hay những tài nguyên khác có trên Internet qua từ khóa. Cho đến nay, phương pháp
tìm kiếm bằng t
ừ khóa vẫn là phương pháp chủ đạo trong các hệ thống truy vấn thông
tin và tìm kiếm dữ liệu. Tuy nhiên, phương pháp này cũng thể hiện những hạn chế và
khả năng ứng dụng của nó trong loại dữ liệu không phải là văn bản. Với dữ liệu hình
ảnh, việc tìm kiếm phụ thuộc rất nhiều vào việc gán nhãn cho hình ảnh trong dữ liệu.
Phương pháp này xa rời với bản chất của hình
ảnh là màu sắc và đường nét. Trong âm
nhạc, phương pháp này cũng tỏ ra những mặt hạn chế của nó. Bản chất của âm nhạc là
giai điệu, nhưng hầu hết các từ khóa không thể hiện được tính chất này của bản nhạc.
Tìm kiếm dựa vào thông tin nhạc sĩ, ca sĩ và lời bài hát là những ứng dụng chính
trong truy vấn thông tin âm nhạc hiện nay.Tưởng tượng rằng khi bạn đang nghe một
bài hát nào đó và r
ất thích nó và bạn muốn nghe lại nó. Nhưng bạn không biết tên bài

động, sự định tuyến và l
ọc cho các bản nhạc và các truy vấn nhạc, ngôn ngữ
truy vấn, các chuẩn và siêu dữ liệu khác hoặc các giao thức cho việc xử lý và
truy xuất nhạc, các hệ thống đa xử lý và sự phân bổ tìm kiếm
• Phần mềm cho MIR là các trang web có ý nghĩa các chủ đề nhạc số, các
phương thức thông minh, các phần mềm cộng tác liên quan, tìm kiếm cơ bản
trên web và sự truy xuất có ý nghĩa (semantic retrieval), tìm kiếm bởi giai điệu
(QBH), nhận dạ
ng âm thanh (acoustic fingerprinting).
• Sự nhận dạng bản nhạc, sự hiểu biết, sự ảnh hưởng và các cảm xúc – các chuẩn
đo độ tương tự âm nhạc, các tham biến có cú pháp, các tham biến có ý nghĩa,
các mẫu nhạc, cấu trúc, kiểu và thể loại, các phương pháp luận giải thích về âm
nhạc
• Sự phân tích âm nhạc và trình bày các kiến thức tổng kết tự đông, trích dẫn, sự
xuống cấp, sự chuyể
n đổi, các mẫu hình thức của âm nhạc, các khía cạnh về số
hóa và những đặc trưng, chỉ mục âm nhạc và siêu dữ liệu. Phân tích lý thuyết
vo hướng âm nhạc là một sự bổ sung cho sự tìm kiếm âm nhạc MIR với những
từ khóa và quy mô của tín hiệu âm nhạc mù là một sự theo đuổi không bình
thường.

7
Sau đây chúng ta cùng tìm hiểu về phương pháp tìm kiếm âm nhạc dựa vào giai
điệu qua hệ thống QBH dưới đây.
1.2 Cấu trúc của hệ thống Query by humming (QBH)
QBH (Query by humming) là một hệ thống truy vấn dựa trên nền tảng cơ bản
về nội dung của hệ thống tìm kiếm âm nhạc MIR [phần 1.1 ở trên]. Hệ thống truy vấn
thông tin âm nhạc sẽ nhận thông tin giai điệu truy vấn từ người dùng và trích xuất
thông tin đặc trưng cần thiết của giai điệu. Đặc trưng giai điệu sẽ được đem so sánh
với những đặc trưng giai

trong cơ sở dữ liệu để trả về kết quả cho người dùng.
9 Sơ
đồ minh họa như sau :

9Hình 2: Sơ đồ máy tìm kiếm QBH khác

Máy tìm kiếm QBH thực hiện những chức năng sau:
a. Cung cấp âm thanh được “hum” vào dưới dạng MIDI, ví dụ nhận dạng cao
độ và thời gian mà các note được hum vào.
b. Cung cấp sự biểu thị của việc nhận dạng đường viền cao độ trong khi đang
hát trong thời gian thực;
c. Cho phép chơi lại giai điệu nhận dạng, biến đổi trong MIDI, trước khi đưa ra
truy vấn
d. Tạo chỉ mục giai điệu và gửi m
ột truy vấn đến mạng chủ Sloud QBH
e. Cung cấp việc bố trí các đại diện các note tìm kiếm và kết kết quả trả về [5]

10
1.3 Những ảnh hưởng đến việc tìm kiếm chính xác và hiệu quả [6]
1.3.1 Người không thể đưa ra một truy vấn hoàn hảo
Dù là người dùng có trí nhớ hoàn hảo về từng giai điệu khác nhau, người đó có
thể bắt đầu tại một khóa sai hoặc là có thể truy vấn nhiều nốt tắt cao độ ở trên khắp
giai điệu. Thỉnh thoảng có thể bỏ rơi vài nối hoặc thêm vào vài nốt mà nó không tồn
tại trong giai điệu bình thường. Thêm vào đó, không người dùng nào mong đợi có thể
hát hoàn hảo đúng nhịp điệu như bài hát chứa trong cơ sở dữ liệu. Cuối cùng, bởi vậy
không ai chấp nhận các khác một cách qua lại một truy vấn hum vào có thế chứa bất
kỳ một sự kết hợp của các nối này.

• Hát với giai điệu thay vì những nốt thuần túy
• Hát với âm thanh thay đổ
i
• Hát quá nhanh
• Âm lượng ghi thấp
• Việc thu phức điệu (như là sự chơi trên piano hoặc guitar )
• Các nốt được hát , chơi với âm lượng khác nhau khá lớn
• Sự xen kẽ giữa việc hát, huýt sáo, giữa việc hát và humming…
Rất nhiều vấn đề nghe được trong quá trình ghi vì vậy việc xử lý âm thanh đầu vào rất
phức tạp.
1.4.3 Việc ghép nối giai điệu truy vấn với cơ s
ở dữ liệu:
Đầu tiên chúng ta định nghĩa vài thuật ngữ. Chúng ta định nghĩa một điệu hát
bao gồm có giai điệu và nhịp điệu với một chuỗi các note ví dụ như một đoạn giai
điệu thì là một cặp của các chuỗi có độ dài bằng nhau, một chuỗi biểu thị cao độ của
mỗi nốt và trường độ của mỗi nốt.Giai điệ
u mà người dùng đưa vào được gọi là truy
vấn và một điệu nhạc đưa ra trong tập dữ liệu âm nhạc được gọi là điệu nhạc kết quả.
Việc xử lý của việc tìm kiếm một giai điệu kết quả mà giống nhất với giai điệu truy
vấn được gọi là thuật toán tìm kiếm và ghép nối xấp xỉ hoặc ghép chính xác, trong các
trường hợp mà các lỗi
được hoặc ko được giải thích, một cách tương ứng. Phần trung
tâm của hệ thống là thuật toán ghép nối. Nó thì khó bởi nó cần được giải thích các lỗi
và xử lý chúng.
Xử lý việc sao chép từ âm thanh ghi lại thành một chuỗi các nốt:

12
• Các nốt bị sai (Các nốt biểu thị trong bản ghi nhưng không tìm ra bởi
thuật toán sao chép)
• Sai vị trí (các nốt trong bản ghi được định dạng sai)

13
1.5 Các hệ thống truy vấn thông tin âm nhạc hiện nay
Việc truy vấn thông tin âm nhạc hiện nay đã trở nên ngày càng phổ biến.
Những hệ thống truy vấn thông tin liên quan đến âm nhạc trước đây được
phát triển theo hướng cho những người có hiểu biết về âm nhạc dùng để phân tích
những tác phẩm âm nhạc. Trong khi đó, những hệ thống gần đây lại hướng đến ngƣời
dùng thông thường và mang tính thương mại; nhiều ứng dụng có giao thức Web. Truy
vấn b
ằng giọng hát là một phương pháp gần gũi với người dùng thông thường
trong các phương pháp truy vấn thông tin âm nhạc. Trong những hệ thống này, một
đoạn thu âm của giọng hát hay ngân nga từ người dùng sẽ được biến đổi và bài hát có
thông tin tương ứng với đoạn thu âm sẽ được trả về từ cơ sở dữ liệu. Các kết quả sẽ
được sắp xếp theo thứ tự dựa trên tính gầ
n giống với bản thu âm của mẫu truy
vấn (xem Hình 1). Hệ thống phải xử lý để chấp nhận những lỗi từ việc hát không
chính xác hoặc nhớ không chính xác giai điệu cũng nhận lỗi từ việc rút trích đặc trưng
của mẫu âm thanh truy vấn. Trong phần này, chúng ta sẽ xem xét một vài hệ
thống truy vấn âm nhạc và những đề tài nghiên cứu có liên quan. Xem trong
[Chương 5 của 16]
1.5.1 Shazam
Hiện nay, trong nước chưa có đề
tài nghiên cứu nào về truy vấn thông
tin âm nhạc được công bố rộng rãi.Shazam (http://www.shazam.com.vn/) là một
ứng dụng dùng để nhận dạng bản thu âm thông qua hệ thống mạng điện thoại di
động. Người dùng có điện thoại di động có thể sử dụng dịch vụ này ở khắp mọi nơi có
tiếng nhạc. Đây là dịch vụ thương mại kèm theo việc bán các tác phẩm âm nhạc số
qua mạng đi
ện thoại di động.
1.5.2 Midomi
Đây là một ứng dụng web cho phép người dùng tìm kiếm bài hát từ một đoạn

Một hướng khác để làm tăng hiệu quả của hệ thống là sử dụng càng
lúc càng nhiều lớp melodic contour để so sánh với cơ sở dữ liệu cho đến khi còn ít
hoặc chỉ một bài trong kết quả. Hệ thống sẽ bắt đầu với 3 lớp pitch contour, sau đó sẽ
tăng lên đến 9lớp, và nếu kết quả vẫn còn quá nhi
ều bài hát, số lớp pitch contour sẽ
tăng lên đến 27 lớp.
1.5.5 Query by humming
Ghias et al sử dụng đặc trưng melodic pitch contour, nhưng dùng ký tự
S (Same) thay cho ký tự R (Repetition) để biểu diễn giai điệu và đánh giá độ tưong
đồng của các đặc trưng. Cơ sở dữ liệu bao gồm 183 bài hát. Hệ thống hỗ trợ tìm kiếm
tại bất kỳ vị trí nào trong bản nhạc và hỗ trợ file midi đa âm sắc. Tuy nhiên,

15
phần pitch tracking khá chậm và là phần tốn nhiều thời gian nhất trong toàn hệ
thống. Thời gian tìm kiếm sẽ chậm đáng kể nếu như có nhiều bài hát trong cơ sở dữ
liệu. Cũng do nhược điểm của việc hỗ trợ MIDI đa âm sắc, nhiều thông tin
không cần thiết (không phải thông tin giai điệu như tiếng trống, tiếng nhạc cụ
đệm…) vẫn làm tốn thời gian tìm kiế
m.
1.5.6 Vocal Search
Hệ thống tìm kiếm trực tuyến được phát triển bởi Bryan Pardo et al (Trường
đại học Northwestern, USA). Nhóm nghiên cứu sử dụng đặc trưng Pitch Interval để
biểu diễn và phương pháp Local String Alignment (tham khảo phần 2.3.4.2) để tìm
kiếm giai điệu. Ứng dụng được xây dựng trên nền Java Applet và cơ sở dữ liệu gồm
những bài hát của ban nhạc The Beatles.
Biểu diễn Pitch Interval được phát triển dựa trên biểu diễn pitch
contour và rhythm contour. Trong đ
ó thay vì phân độ sai khác vào các lớp U, D, R,
pitch interval sử dụng hiệu cao độ (đơn vị semitone) giữa hai note liền kề làm
giá trị cho pitch contour. Rhythm contour được sử dụng như khái niệm nguyên thuỷ

thì là một phương pháp không chính xác, nhưng có thể
cải thiện lớn về sự đúng đắn
và tốc độc của hệ thống truy xuất đang dùng phương pháp này. Bởi vậy trung bình
người bình thường nhớ và yêu cầu chủ đề của một đoạn nhỏ của âm nhạc, hệ thống
dùng phương pháp đó thì có thể tìm kiếm cho những phần nhỏ hơn.Tham khảo tại
http://www.cs.cmu.edu/ music/search.
1.5.9 MELDEX
The New Zealand Digital Library’s MELody inDEX (MELDEX) chuyển đổi
trướ
c sang dạng xử lý tín hiệu số, công nghệ biểu diễn âm nhạc và phần cứng máy
tính để chuyển dổi các giai điệu một cách tự dộng từ micro. Nó được tạo ra cho những
người quản lý thư viện người mà thường yêu cầu tìm một phần của âm nhạc dựa trên
một vài note được hát vào. Nó được thiết kế lại để trong các phần mềm ứng dụng thư
viện số. M
ột phân tích cho việc dùng logs đã chỉ ra mà hầu hết nguwofi dùng thì đang
đưa một truy vấn text trên một chủ đề không chắc chắn để thấy tràng các giai điệu
(tunes) kết quả của việc tìm kiếm. Một người có thể cũng tìm kiếm cơ sở dữ liệu bởi
việc chơi truy vấn bởi bàn phím ảo trên một trang web. Thiết kế, tạo và được sử dụng
cho mỗi mục đích riêng, c
ơ sở dữ liệu được làm đầy với 9000 đoạn nhạc và có thể
được tìm kiếm (http://www.nzdl.org/musiclib).

17
Chương 2. CÁC VẤN ĐỀ NGHIÊN CỨU LIÊN QUAN
2.1 Các công cụ hỗ trợ xử lý âm thanh
2.1.1 Praat
Praat là một chương trình dùng để phân tích và tổng hợp lời nói được viết bởi
Paul Boersma och David Weenik tại University của Amsterdam, Department of
Phonetics. Praat phân tích tín hiệu đơn sắc. Praat hỗ trợ khả năng quan sát trực tiếp
các tham số như tần số cơ bản F

được gợi ý, Matlab được thiết kế để thực hiện việc tính toán ma trận một cách có hiệu
quả đặc biệt. Matlab có nhiều bộ dụng cụ cho phép thực thi nhiều nhiệm vụ, bao gồm
cả việc xử lý tín hiệu.
Với khóa luận này bộ công cụ nhóm thứ 3 được sử dụng để truy cập một micro
dùng Matlab và dùng Matlab để đọc file MIDI d
ưới dạng một ma trận. Các bộ công
cụ đó là MIDI dùng cho Matlab bởi Ken Schutte và việc ghi lại và phân tích lời nói.
Xem chi tiết [6]
Matlab có thể đọc trực tiếp các tín hiệu audio do người dùng huýt, thổi hoặc
hát vào qua micro bằng định dạng lệnh :
y = wavrecord(n, fs);
n là số lượng mẫu được ghi lại, fs là tần số lấy mẫu.
Chúng ta cũng có thể ghi files âm thanh “wav”bằng việc dùng Matlab với lệnh
wavwrite như sau:
y = wavwrite(y, fs, nbits, waveFile);
Với y là dữ liệu âm thanh, fs là tầ
n số lấy mẫu, nbits là độ phân giải bít và
wavFile là file dạng wav được ghi vào. Xem chi tiết [25, 26]
Trong Matlab hỗ trợ rất nhiều hàm và công cụ hữu ích cho việc xử lý, phân
tích âm thanh từ micro. Nó cho phép bạn thao tác dễ dàng với các tín hiệu âm thanh
đầu vào thu được.
2.2 Biểu diễn nội dung dữ liệu
Lựa chọn phương pháp biểu diễn dữ liệu là điều rất quan trọng, vì nó ảnh
hưởng đến phương pháp truy vấn, tìm kiếm dữ liệu, và những thuật toán thực thi trên
dữ liệu. Chẳng hạn, văn bản là phương pháp biểu diễn nội dung thích hợp với dữ liệu
là những đoạn thu âm tiếng nói, và với những thuật toán tìm kiếm từ khóa hiện có.
Một vài phương pháp bi
ểu diễn này có thể có được qua việc rút trích đặc trưng từ một
dữ liệu khác, thông thường là ở những mức biểu diễn thấp hơn (chẳng hạn thông qua
những định dạng WAV hay MIDI). Có thể nói, rút trích đặc trưng là một công việc

số trường hợp. Cách biểu diễn này được gọi là đườ
ng biên giai điệu (Melodic pitch
contour).
Đường biên giai điệu thể hiện một chuỗi những biến đổi có tính chất định tính
trong cao độ. Một note trong một bản nhạc được đem so sánh với note trước đó và sự
sai khác được xếp vào một trong ba lớp, được ký hiệu như sau: U (Up - khi cao độ
tăng), D (Down – khi cao độ giảm), và R (Repeat – khi cao độ lặp lại). Như vậy, một
đoạn nhạc đơn giản có thể
được biểu diễn bằng một chuỗi những ký tự (gồm U, D, R).

20
Chẳng hạn như, khúc mở đầu của bản giao hưởng số 5 của Beethoven sẽ được biểu
diễn bằng chuỗi sau: - R R D U R R D. Hình 3 cho ta một ví dụ khác về bản nhạc
quen thuộc “Happy Birthday” được biểu diễn dưới dạng đường biên giai điệu. Hình 3: Ví dụ biểu diễn đường biên giai điệu của bài hát “Happy Birthday”

Đường biên giai điệu thể hiện một chuỗi đặc trưng đường biên của của giai
điệu đã loại bỏ những thông tin không cần thiết, như định lượng sự sai khác
giữa hai note nhạc liền nhau hay thông tin về nhịp điệu, vì vậy làm giảm không gian
và độ phức tạp của việc tìm kiếm. Tuy nhiên, cũng vì thế, thông tin đường biên giai
điệu lại trở nên quá thiếu chi tiết (under-specification).
Có rấ
t nhiều bản nhạc dù giai điệu khác nhau, nhưng vẫn có thể có đường biên
giống nhau do giai điệu cùng lên và xuống theo trật tự giống nhau (nhưng độ lên
xuống khác nhau và thời gian của từng note nhạc cũng khác nhau).
Đặc trưng đường biên giai điệu như mô tả ở trên không đủ phân biệt trong rất
nhiều trường hợp. Một cách khắc phục là phân loại những lớp con trong các lớp
UDR.Theo phương pháp này, mỗi lớ

làm rung động bầu không khí quanh nó, truyền đi trong không gian bao la, rồi đập vào
tai người nghe, làm rung động màng nhĩ, khiến cho người ấy nghe được âm thanh
đó.[27, phụ lục 8]
Để ghi lại, lưu lại một sóng âm thường thì người ta sử dụng kỹ thuật tương tự
(Analog), biến một sóng âm bản chất cơ học thành sóng điện từ, với những định dạng
(format) quen thuộc như .wav, .cda, .mp3 v.v... File âm thanh định dạng wav thường
chi
ếm rất nhiều không gian dĩa, file cda cũng là một loại file wav, được sử dụng cho
các đĩa CD (compact disc) nên cũng chiếm dụng không gian tương đương .Kỹ thuật
nén file ra đời đã hình thành nhạc mp3 với rất nhiều ích lợi (chiếm dụng không gian ít
hơn từ 10 lần đến 20 lần so với file wav, nhờ đó có thể truyền tải được trên mạng
Internet nhiều và nhanh hơn) Nếu một bài hát thông thường lưu ở định dạ
ng wav
chiếm trung bình khoảng 40 Mb , thì file Mp3 tương ứng chỉ cần từ 2Mb cho đến 4
Mb.
Giữa các nhạc cụ điện tử giờ đây có một "ngôn ngữ" chung gọi là "MIDI", để
nói chuyện với nhau. MIDI tuy là một khái niệm mới nhưng đã trở nên rất quen thuộc
trong lĩnh vực âm nhạc điện tử, đến nổi người ta xem nó là một thuật ngữ mà quên
rằng MIDI là từ viết tắt của "Miscical Instrument Digital Interface" (giao di
ện số với
các nhạc cụ). Một cách đơn giản, MIDI là một ngôn ngữ giữa các thiết bị âm nhạc.
Mặc dù có nhiều ngôn ngữ khác nhau trên thế giới (Việt Nam, Anh, Pháp...) nhưng
MIDI chỉ có một ngôn ngữ duy nhất. Do đó, MIDI không phụ thuộc nhà chế tạo nhạc

22
cụ và nơi sản xuất. Hơn nữa nó dùng cho nhiều chủng loại nhạc cụ khác nhau; ví dụ
một piano điện có thể nối với một bộ trống điện tử, khi đó nếu ta bấm một phím trên
piano thì bộ trống sẽ phát ra một tiếng trống tương ứng.
Nhạc Midi không dùng kỹ thuật tương tự (Analog), mà dùng kỹ thuật số (Digital)
để lưu lại âm thanh. Mỗi âm thanh củ

23
Đưa ra một đoạn giai điệu được định nghĩa bởi điểm p
i,
chúng ta có thể tìm các
đoạn tương tự trong chỉ mục bằng các tìm kiếm các hàng xóm gần nhất (NNs) của
điểm ví dụ tất cả các điểm mà khoảng cách nhỏ hơn một ngưỡng cụ thể r nào đó.Điều
này có thể được làm bởi việc đo khoảng cáh đơn gian p
i
đến tất cả các vector trong cơ
sở dữ liệu. Tuy nhiên, các kết quả này trong một thời gian tìm kiếm tùy thuộc vào
kích cỡ tuyến tính của cơ sở dữ liệu. [16, 4]
Để thu được một thời gian tuyến tính dưới một cách phức tạp, chúng ta sử
dụng vị trí của hàm băm miền nhạy cảm LSH là một thuật toán ngẫu nhiên cho việc
tìm kiếm khoảng cách hàng xóm gần nhất trong không gian nhiều chiều.Ý tưởng là
các
điểm mà khoảng cách trong cùng một ngưỡng sẽ được băm vào một thùng giống
nhau với xác suất cao. Người dùng định nghĩa xác suất điều khiển sự thỏa thuận giữa
độ chính xác và tốc độ của LSH. Trong phương pháp của chúng ta, chúng ta thuê LSH
hoàn thiện các gói E2LSH bởi các độc giả http://web.mit.edu/andoni/www/LSH
. Dựa
trên sự thi hành, chúng ta xây dựng một máy chủ cho việc xử lý các đoạn chỉ số the
melodic và một máy khách cho việc truy xuất các đoạn giai điệu giống nhau từ cơ sở
dữ liệu. Gần đây LSH được áp dụng ví dụ trong việc công nhận âm nhạc và trong dấu
tay âm thanh.Ý tưởng của thuật toán LSH như sau. Thuật toán LSH là thuật toán tìm
kiếm K hàng xóm gần nhất hoặc tìm kiếm xấp xỉ K hàng xóm gần nhấ
t.
• Truy vấn lân cận K gần nhất KNN (K- nearest neighbour)
Người dùng đặc tả một đối tượng truy vấn Q và chấp nhận một số lượng K đối
tượng. Hệ thống tìm kiếm K đối tượng tương tự nhất với đối tượng truy vấn từ
MMDBMS (


25
Cho hai vector t = [t1, t2,…, tn] và r = [r1, r2,…,rm]. Thuật toán DTW sẽ giúp
tìm ra một ánh xạ đường đi {(x
i1
, y
j1
), (x
i2
, y
j2
),…, (x
ik
, y
jk
)} với những ràng buộc sau:
i. Điều kiện ràng buộc biên: (i
1
, j
1
) = (1, 1), (i
k
, j
k
) = (m, n). Điều kiện này còn
gọi là "neo điểm đầu" và "neo điểm cuối".
ii. Ràng buộc về đường đi cục bộ: Với mọi node (i, j) trong đường đi, những
node đến được nó chỉ giới hạn trong (i-1, j), (i, j-1), (i-1, j-1). Ràng buộc này giúp
đảm bảo luôn tồn tại một song ánh từ t đến r. Minh họa về ràng buộc đường đi cục bộ
thể hiện trong hình dưới đây.