Выравнивание музыкальных нот с использованием алгоритмов сравнения строк или динамического программирования

Question

Мне нужно сравнить 2 набора музыкальных произведений (т. Е. Воспроизведенные в формате MIDI ноты, извлеченные и сохраненные в таблице базы данных, с нотами, переведенными в формат XML). При оценке игры на ноты (т. Е. Примечание - высота, длительность, ритм) необходимо выполнить выравнивание нот - чтобы определить пропущенные / лишние / неправильные / поменянные ноты, исходя из эталонных (ноты) нот.

У меня примерно 1800-2500 нот в одном экземпляре (может даже больше - с полифонией, сейчас я пишу для однотонного). Так нужно ли мне все это помещать в массив? Это будет перегрузка памяти или переполнение стека?

Существуют алгоритмы сопоставления строк, такие как KMP, Boyce-Moore. Но выравнивание нот также можно выполнить с помощью динамического программирования. Как я могу использовать динамическое программирование, чтобы приблизиться к этому? Какие доступны алгоритмы? Это о приблизительном сопоставлении строк?

Какой подход очень продуктивен? Алгоритмы соответствия строк, такие как Бойс-Мур, или динамическое программирование? Как я могу оценить, что является более эффективным?

Очень ценю любые идеи или предложения Заранее спасибо

Answer 1

Интересный вопрос - я думаю, что эта статья охватывает многое из того, что вас интересует. Они решают проблему ошибок и выравнивания музыки и обсуждают их результаты, используя DP в качестве решателя.Они вводят алгоритм под названием «быстрое приближенное сопоставление», который, как они утверждают, лучше, чем подход DP.

Похоже, что ключевыми авторами для поиска являются Mongeau & Sankoff.Похоже, что их оригинальная статья вызвала большую работу в этой области.

Аккуратные вещи.Надеюсь это поможет.