lign="justify"> У файлах формату 0 позначення темпу і розміру можуть бути розкидані по різних місцях в межах однієї MTrk-записи. У файлах формату 1 перша MTrk-запис повинна складатися лише з подій темпу і розміру. У файлі формату 2 кожна MTrk-запис повинен починатися з подій темпу і розміру. p align="justify"> Зауваження: Якщо в міді-файлі немає подій темпу і розміру, то за замовчуванням мається на увазі значення розміру 4/4 і значення темпу 120 BPM.
Таким чином, ми можемо побайтно вважати MIDI-файл, з його заголовка дізнатися всю необхідну інформацію для аналізу (темп, такт, число тиків, що припадають на один такт), вважати музику в масив байтів і ми безпосередньо перейдемо до проблеми визначення подібності мелодій. Дана задача відноситься до задач нечіткого пошуку. p align="justify"> Алгоритми нечіткого пошуку (також відомого як пошук за подібністю або fuzzy string search ) є основою систем перевірки орфографії і повноцінних пошукових систем ніби Google або Yandex. Наприклад, такі алгоритми використовуються для функцій на кшталт В«Можливо ви мали на увазі ...В» у тих же пошукових системах. Нечіткий пошук в більшості своїй використовується для пошуку рядків у тексті, підрядка в рядку і т.д., але він підходить і для нашої задачі:
Для простоти розглядається порівняння двох мелодій, а не порівняння мелодії з набором мелодій (тобто словник з одного слова), то при порівнянні без урахування розбиття на такти одна мелодія (найменша за кількістю нот) буде словом. Розмір слова дорівнюватиме довжині мелодії, а значенням буде комбінація нот в мелодії. p align="justify"> При порівнянні з урахуванням розбиття на такти розмір слова дорівнюватиме такту, а значенням слова буде шматочок мелодії з MIDI-файла. Словником виступить мелодія, на схожість з якою і визначається наданий зразок. p align="justify"> Для простоти викладу і розуміння будемо розглядати нечіткий пошук стосовно рядках.
Алгоритми нечіткого пошуку характеризуються метрикою - функцією відстані між двома словами, що дозволяє оцінити ступінь їх подібності в даному контексті. Суворе математичне визначення метрики включає в себе необхідність відповідності умові нерівності трикутника (X - безліч слів, p - метрика):
В
Тим часом, в більшості випадків під метрикою мається на увазі більш загальне поняття, яке не потребує виконання такої умови, це поняття можна також назвати відстанню .
У числі найбільш відомих метрик - відстані Хемінга , Левенштейна і Дамерау-Леве...
