Каков оптимальный способ выбора набора функций для исключения элементов на основе битовой маски при сопоставлении с большим набором?

Question

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

Предположим также, что можно идентифицировать большой набор функций, которые могут использоваться для исключения возможных совпадений, что позволяет избежать дорогостоящего теста. Если в объекте, который я тестирую, присутствует функция, я могу исключить любые объекты из набора, которые не имеют этой функции. Другими словами, наличие признака необходимо, но недостаточно для прохождения теста.

В этом случае я могу предкоммутировать битовую маску для каждого объекта в наборе, указывая, присутствует или нет каждая функция в объекте. Я также могу вычислить его для объекта, который я хочу, чтобы проверить, а затем цикл по массиву, как этот (псевдо-код):

objectMask = computeObjectMask(myObject) 
for(each testObject in objectSet) 
{ 
    if((testObject.mask & objectMask) != objectMask) 
    { 
     // early out, some features are in objectMask 
     // but not in testObject.mask, so the test can't pass 
    } 
    else if(doComplicatedTest(testObject, myObject) 
    { 
     // found a match! 
    } 
} 

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

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

Примечание: частота каждой функции считается одинаковой в наборе возможных объектов myObject, как в объекте, хотя мне было бы интересно знать, как обращаться, если это не так. Мне также было бы интересно узнать, существует ли алгоритм поиска наилучшего набора функций, учитывая большой выборку объектов-кандидатов, которые должны быть сопоставлены с множеством.

Возможные применения: сопоставление входной строки с большим количеством регулярных выражений, сопоставление строки с большим словарем слов с использованием таких критериев, как «должны содержать одни и те же буквы в одном порядке», но, возможно, с дополнительными символами, вставленными в любом месте в слове "и т. д. Примеры:« содержит буквенный символ D »,« содержит символ F, за которым следует символ G позже в строке »и т. д. Очевидно, что набор возможных функций будет сильно зависеть от конкретного приложения.

Answer 1

Вы можете попробовать алгоритм aho-corasick. Его самый быстрый набор шаблонов. В основном это конечный автомат с ошибками, рассчитанный с помощью поискового запроса trie.