1

假设我有一个大型的静态对象集，并且我有一个对象，我想根据一组复杂的标准与所有这些对象进行匹配，这需要进行昂贵的测试。

还假设可以识别出可用于排除潜在匹配的大量特征，从而避免昂贵的测试。如果我正在测试的对象中存在某个特征，那么我可以排除集合中没有此特征的任何对象。换句话说，该特征的存在是必要的，但不足以使测试通过。

在这种情况下，我可以为集合中的每个对象预先计算一个位掩码，指示对象中是否存在每个特征。我还可以为要测试的对象计算它，然后像这样循环遍历数组（伪代码）：

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”等。显然，可能的特征集将高度依赖于特定的应用程序。

4

1 回答 1

1

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

于 2015-05-11T06:48:28.713 回答