В принципе, распознать мелодию наверное несложно - т.е. они все (все существующие музыкальные треки в мире) настолько уникальны мелодией, ритмом и т.п., что для каждой можно выделить не особо большой шаблон (килобайта 4 хватит?), описывающий некоторые параметры...

Я просто смотрю на moskva.fm - у них там стоит куча FM-ресиверов, всё пишется, а на сайте визуализируется как ось времени с событиями на ней, часть из которых - прозвучавшие мелодии.

Потом все эти шаблоны укладываются в какое-то многомерное дерево... и, как я понимаю, затраты вычислительные ерундовые получаются на узнавание трека? Это же не слово в речи отловить (сложно). Распознаваторы речей и то целыми фразами часто работают, как я понимаю - отдельные слова в целой фразе в звуке вообще не выделимы бывают. А композиция музыкальная такая большая по времени, что под неё хорошо создаются наверное такие "отпечатки", которые быстро находятся в потоке?

maytonОдна и та-же мелодия может иметь несколько версия типа acoustic, radio-edit и т.д., иметь разных исполнителей, разный ритм и даже иметь пародию на саму себя. Тогда вопрос в том, что вы именно собираетесь узнать? Интернет базы-данных типа cddb хранят длины всех треков в альбоме с точностью до секунд. И по noname-треклисту даже без названий довольно точно определяют всю метаинформацию. Это дёшево и сердито. И это реально работает почти во всех медиаплеерах.
Ну в спектрально-временном "отпечатке" акустик, радио-эдит и проч. одной мелодии - это всё разные треки.

Спасибо за инфу о том, как работает cddb!