Поиск по midi

Единственное, что пока приходит в голову, это составить индекс по всем последовательностям нот, встречающимся в файле, с учётом возможных пропусков нот (форшлаги, аккомпанимент или другие голоса пользователь вводить не будет, только основную слышимую тему). Но грубый потсчёт показывает, что это будет база размером около 1е8 записей на файл (из расчёта последовательности из 10 нот, пропускать можно до 3 нот и средний размер файла - 400 нот), или около 100 Гб такого индекса на всю коллекцию при размере коллекции на 4-5 порядков меньше. Если автоматически отфильтровывать форшлаги, аккомпанимент, и т.д, что есть отдельная проблема, то удасться сократить, возможно, на один или два порядка. Но это всё равно как-то много.

Есть ли какой-то более оптимальный способ?

Индексировать разности между нотами? Учитывать границы-паузы?

А можно поподробнее? Индекс - это соответствие между интервалом и позицией в файле? Допустим, я проиндексировал все интервалы. Я сыграл 10 нот, и, пользуясь этим индексом, нахожу, что первый интервал встречается в каждой песне, допустим, у 8%. Теперь у меня есть список из позиций, в котором есть этот интервал. Он уже меньше, чем общее количество нот, но что с ним делать дальше? Если просто перебирать все эти варианты, то это всё ещё слишком долго, так как время всё ещё O(N), а хотелось бы O(log N).

Как решают эту проблему поисковики вроде гугла, когда я ввожу какую-нибудь фразу в кавычках? У них есть какой-нибудь индекс по словам, благодаря которому они смогут найти страницы, на которых встречаются все слова из фразы, но ведь фраза в кавычках, а значит слова должны идти последовательно. Неужели они начинают перебирать все найденные страницы одна за одной, проверяя последовательность слов?

то это всё ещё слишком долго, так как время всё ещё O(N), а хотелось бы O(log N).

Если у тебя 100-200 файлов, тебе не нужно париться об O(logN).

Да, но у меня raspberry pi...

100-200 - это если считать файлами. А если нотами, то гораздо больше.

То есть алгоритмическая сложность на таких объёмах, конечно, не так важна, но хочется какой-то эффективности всё равно. Перебирать каждую 10 - это, конечно, значительное ускорение, но хочется большего)

Советую реализовать сначала самый простой алгоритм, который только придумаешь. Если он окажется недостаточно быстрым, придумывать новый. В процессе придумывания у тебя уже будет решение. Медленное, но решение. Хотя бы не вручную искать.

Если ты зациклишься на алгоритмах поиска, не будет ни того, ни другого.

Ну разве что тебе сам поиск не нужен, а интересно именно алгоритм разработать.

А можно поподробнее? Индекс - это соответствие между интервалом и позицией в файле?

Нет. Я имел в виду, что не нужно считать все ноты в файле единой последовательностью. Если есть большие паузы, считать, что последовательность заканчивается на ней, а потом начинается следующая.

Как решают эту проблему поисковики вроде гугла, когда я ввожу какую-нибудь фразу в кавычках? У них есть какой-нибудь индекс по словам, благодаря которому они смогут найти страницы, на которых встречаются все слова из фразы, но ведь фраза в кавычках, а значит слова должны идти последовательно. Неужели они начинают перебирать все найденные страницы одна за одной, проверяя последовательность слов?

Не знаю. Плотно работал только с одной закрытой системой, пользующейся базовыми средствами Оракла, и там поиск последовательностей и подстрок, действительно, гораздо медленнее.

И да, верно советуют, если цель — искать в нескольких сотнях файлов, и набираешь с абсолютным слухом — достаточно написать аналог grep (без регулярных выражений) для midi, и индексы не нужны.

Брать только последовательности длинной 3 или 2. Разбивать ввод на части и искать по ним. Отображать записи по точности совпадения (например, для последовательности длинной 10 и сегменте длинной 2: 5 кусков из 5 или 3 из 5 со сдвигом). Меньше база, дольше поиск.

Задача теоретическая или практическая?

Если теоретическая — см. выше.

Если практическая — берешь любую библиотеку для fingerprinting'а звука, синтезируешь в звуковую дорожку каждый канал каждого файла, собираешь базу. Наигранное на клавиатуре тоже ситезируешь в звук, фингерпринтишь и ищешь по базе. К понедельнику успеешь.