假设我有一个庞大的静态对象集，并且我想根据一组复杂的标准（需要进行昂贵的测试）将它们与所有对象进行匹配。
还假设可以识别出大量可用于排除潜在匹配项的功能，从而避免进行昂贵的测试。如果我要测试的对象中存在某个功能，则可以排除集合中不具有此功能的任何对象。换句话说，功能的存在是必需的，但不足以使测试通过。
在那种情况下，我可以为集合中的每个对象预先计算一个位掩码，以指示对象中是否存在每个功能。我还可以为要测试的对象计算它，然后像这样（伪代码）遍历数组：
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项功能，则两个遮罩中都包含该功能的机会会更高，因此似乎可以减少早期淘汰的次数。但是，如果我选择了x个最不常用的特征，则objectMask可能经常为零，这意味着不可能提前淘汰。进行实验似乎很容易，并且提出了一组具有良好性能的中频功能，但是我对是否有理论上最好的方法感兴趣。
注意：在可能的myObjects集合中，假定每个功能的频率与objectSet中的频率相同，尽管我很想知道如何处理（如果不是）。我也想知道是否有一种算法，可以根据给定的大量候选对象样本来找到最佳特征集。
可能的应用：将输入字符串与大量正则表达式进行匹配，使用诸如“必须以相同顺序包含相同字母，但可能在单词中的任意位置插入额外的字符”等条件，将字符串与大型单词词典进行匹配等等。示例功能：“包含文字字符D”，“在字符串中包含字符F，后跟字符G”等。显然，可能的功能集将高度依赖于特定的应用程序。
您可以尝试使用aho-corasick算法。它是最快的多模式匹配器。基本上，它是具有故障链接的有限状态机，该故障链接通过trie的广度优先搜索计算得出。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句