在与大型集合匹配时，选择一组特征以排除基于位掩码的项目的最佳方法是什么？

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! 
    }
}

所以我的问题是，给定一个有限的位掩码大小，大量可能的特征，以及对象集中每个特征的频率 table（加上访问object set if you want to compute correlations between features 等），我可以使用什么算法来选择包含在我的位掩码中的最佳特征集，以最大化早期出局的数量并最小化测试的数量？

如果我只选择前 x 个最常见的特征，那么一个特征同时出现在两个掩膜中的可能性就更高，所以看起来提前出局的次数会减少。但是，如果我选择 x 个最不常见的特征，则 objectMask 可能经常为零，这意味着不可能提前出局。似乎很容易试验并提出一组提供良好性能的中频特征，但我感兴趣的是是否有理论上的最佳方法。

注意：假定每个特征的出现频率在可能的 myObjects 集合中与在 objectSet 中的出现频率相同，尽管我很想知道如果不是，则如何处理。我也很想知道是否有一种算法可以在给定要与集合匹配的大量候选对象样本的情况下找到最佳特征集。

可能的应用：将输入字符串与大量正则表达式进行匹配，使用 "must contain the same letters in the same order, but possibly with extra characters inserted anywhere in the word" 等条件将字符串与大型单词词典进行匹配。示例特征："contains the literal character D"， "contains the character F followed by the character G later in the string" 等。显然，可能的功能集将高度依赖于特定的应用程序。

Answer 1

你可以试试aho-corasick算法。它是最快的多模式匹配器。基本上它是一个有限状态机，其故障链接是通过树的广度优先搜索计算的。

在与大型集合匹配时，选择一组特征以排除基于位掩码的项目的最佳方法是什么？

What is the optimal way to choose a set of features for excluding items based on a bitmask when matching against a large set?

algorithm

optimization

matching

feature-selection

bit-masks