0

我有一个到 int 的无序映射字符串，它使用定义为的自定义 equal_to 函数：

bool hashEqual::operator ()(const string &a, const string &b) const
{
    if (a.size() != b.size())
        return false;

    return std::inner_product(
        a.begin(), a.end(), b.begin(),
        0, std::plus<unsigned int>(),
        std::not2(std::equal_to<std::string::value_type>())
        ) <= 8;  
}

基本上，如果两个键的汉明距离等于或小于 8，则它的作用是相同的键。

问题是我希望距离阈值是动态的，以便让用户通过命令行设置它。而不是 8，一个可变阈值或类似的东西。

我不是在寻找像全局变量这样的技巧（除非它是实现这一目标的唯一方法），而是在寻找“好方法”。

4

2 回答 2

1

为什么`unordered_map`不能可靠地工作

一个好的通用哈希函数以可重复但看似随机的方式将键映射到存储桶，我的意思是，如果键变化甚至一位，那么存储桶应该在统计上不相关 - 就好像你在随机的。因此，假设您有一个包含一些现有元素的哈希表：

[ bucket 0 - "abcde fghij" ]
[ bucket 1 - <empty> ]
[ bucket 2 - <empty> ]
[ bucket 3 - "01234 56789", "77777 QQQQQ" ]  (2 colliding values for this bucket)
[ bucket 4 - "XXXXX YYYYY" ]
[ bucket 5 - <empty> ]

如果你来插入说"Abcde fghij"，那么你可以散列到这些桶中的任何一个 - 你应该没有比其他任何桶更多的机会成为桶 0，但如果那个桶不是桶 0，那么你甚至永远不会尝试与“abcde fghij”的汉明距离感知平等比较。

为什么`multimap`不能可靠地工作

想象一下，我们multimap有一些现有的字符串（S1 到 S6 以增加的字典排序顺序 - 每个与其他元素的汉明距离大于 8），实际的平衡二叉树可能看起来有点像：

            S4
          /    \
        S2       S6
       /  \     /  \
      S1   S3  S5

现在，假设 S1 恰好是"Abcde fghij"，S4 是"ZZZZZ ZZZZZ"，我们去插入"abcde fghij"：

  • 即使有汉明距离比较，"ZZZZZ ZZZZZ" < "abcde fghij"（记住'Z' < 'a'按ASCII顺序）所以multimap期望"abcde fghij"存储在树的右侧......

  • "abcde fghij"然后与 S6 进行比较，如果 S5 小于 S5，则会相应地插入，但至关重要的是，从未与 S1 进行任何比较

这让我回到了我之前的评论：

我认为除了蛮力（尝试每种组合）之外，没有任何简单而正确的方法来进行比较。对于相同的数据，结果以另一个顺序变化。

于 2014-06-30T08:15:48.767 回答
0

我想到了。

一切都在类 hashEqual 中完成。我改变了这样的定义：

class hashEqual {
    private:
        int th;
    public:
       hashEqual();
        hashEqual(int th) { this->th = th; }; // This implemetation on the .cpp
        bool operator ()(const string &a, const string &b) const;
};

operator() 实现：

bool hashEqual::operator ()(const string &a, const string &b) const
{
    if (a.size() != b.size())
        return false;

    return std::inner_product(
        a.begin(), a.end(), b.begin(),
        0, std::plus<unsigned int>(),
        std::not2(std::equal_to<std::string::value_type>())
        ) <= this->th;  
}

在 unordered_map 的构造函数中：

boost::unordered_map<string, unsigned int, boost::hash<string>, hashEqual> myMap(size, boost::hash<string>(), hashEqual(threshold));
于 2014-06-27T09:34:49.880 回答