Сравнение алгоритмов распознавания аудио для Second Screen

[megalol]

Вместо полного перебора можно (и нужно) построить структуру данных для ускорения. Я начал было об этом рассуждать, но заглянул в [1] и увидел. что там что-то подбное описывается.

Лучшим вариантом по моему мнению является комбинация методов. Сначала с помощью алгоритма Wong, в котором основное преимущество как раз в быстром поиске по словарю, найти десяток-другой претендентов, затем отфильтровать претендентов более точным методом.

[borges]

Да, конечно, у нас есть и структура данных выше уровнем для ускорения поиска. Но это не словарь, в ней так же допускается нечеткое совпадение. Да, сначала находятся претенденты, а потом они проверяются. Претендентов не десяток-другой, а тысячи (зависит от предметной области, размеров базы и т. д.)

Если же использовать поиск по словарю, то слишком часто среди претендентов не будет находиться правильный ответ. В нашей предметной области false negative rate увеличивается в 2-2.5 раза.

[vikorbit]

На данном этапе исследований мы хотели посмотреть на весь потенциал помехоустойчивости сигнатур Haitsma. Ускорение поиска за счет словарей предполагает ряд допущений (например, что по крайней мере один sub-fingerprints имеет точное соответствие), которые для сильно деградированных сигналов не всегда справедливы.

Для случая когда алгоритм Wang не может распознать запрос он не может использоваться для эффективного отбора претендентов.

[megalol]

Это не обязательно должен быть словарь из той статьи, можно сделать поиск ближайшей точки в многомерном пространстве с помощью каких-либо деревьев, можно предварительно округлять данные, сплющивая биты в один. Меня смутило упоминание обязательности брутфорса в статье — понятно, что o(n) в случае даже тысячи файлов (а значит миллионах проверок) не годится. Если у вас есть структура нечеткого поиска, но не упоминаете ноу-хау, это другой вопрос.

Для случая когда алгоритм Wang не может распознать запрос он не может использоваться для эффективного отбора претендентов.

Обычно несколько отсчетов все-таки ловится. Этого не достаточно для полноценного диагноза, но базу сузить может очень сильно.

[vikorbit]

Спасибо за уместное замечание. Действительно без дополнительных исследований категорично заявлять об обязательности брутфорса преждевременно.

Эксперименты показали, что когда наша реализация алгоритма Wang не может распознать запрос, базу можно уменьшить примерно на 10 % (около 90 % кандидатов имеют score лежащий между score правильного ответа и максимальным для данного запроса).