1

我需要一个 C++ 内存字典容器，它获取一个键，并以任何方式返回一个值。也就是说，如果键在“键列表”中不存在，它会找到最相似的键，并给出值。

有什么建议么？

编辑：

感谢您的评论。

更多细节：为了简单，让我们从数字键开始。如果钥匙距离钥匙在 200 以内，就拿到它。

4

3 回答 3

2

你需要使用一种叫做locality-sensitive hashing 的东西，并且你需要在它上面写一点代码（我保证只是一点点。一个额外的词）。

首先，您需要使用std::mapand notstd::unordered_map或任何其他哈希表 - 它必须是树或其他有序数据结构。

您的关键是局部敏感散列，它具有散列相似输入以关闭输出的行为。所以 AAA 的哈希值和 AAB 的哈希值会比 AAA 和 CCC 的哈希值更接近。该值将是您想要的任何值。

要检索“最近匹配”，您只需要使用std::map::lower_bound(或std::map::upper_bound) 从地图中获取与任何给定输入最接近的值。

所以你的代码看起来像这样

std::map<unsigned int, some_struct> mymap;
for(;;;)
{
   mymap[locale_sensitive_hash(some_struct(some random value))] = some_struct(some random value)
}

//Now find the object we have that is nearest to some_struct(AAA)
unsigned int this_hash = locale_sensitive_hash(some_struct(AAA));
some_struct nearest_object = mymap.lower_bound(this_hash);

做完了。

一些注意事项：

这是假设一个非数字键。数字本身已经是“区域敏感的哈希”，即如果H(n)是n，则H(n)和之间的差异与输入和H(n')之间的差异成正比。在这种情况下，这是您唯一需要的，并且您不需要额外的散列步骤。nn'lower_bound

你可以很容易地扩展这个方法来做一些事情，比如指定对象之间的最大距离。这将取决于您使用的区域设置敏感哈希以及它如何表示两个给定输入的两个哈希之间的距离，但通常只是在返回(with being ) 之前比较H(n)和。H(n')nearest_structnearest_structn'

于 2012-06-01T16:23:09.000 回答
1

一种方法是使用多图...

T& get(int key)
{
    // use a multimap as storage
    static multimap<int, T> m;

    multimap<int, T>::iterator best;

    // search for key within 200
    for (auto it = m.lower_bound(key-200); it != m.upper_bound(key+200); ++it)
        if (best)
            // if multiple matches use the closest one to the key
            best = (abs(it->first-key) < abs(best->first-key) ? it : best);
        else
            best = it;

    // if none found, insert new entry
    if (!best)
         best = m.insert(key, T());

    return best->second;
}

另一种更快但更混乱的方法是使用 unordered_map 和两级键......

T& get(int key)
{
    struct KeyValue
    {
        int key;
        T value;
    };

    static unordered_map<int, vector<KeyValue>> m;

    vector<KeyValue>::iterator best;

    int b = key/200;
    int a = b - 1;
    int c = b + 1;

    // function to search bucket for a key...
    auto ms = [&](int bucket)
    {
        for (auto it = m[bucket].begin(); it != m[bucket].end(); ++it)
            if (abs(it->key - key) <= 200)
            {
                if (best)
                    best = (abs(it->key - key) < abs(best->key - key));
                else
                    best = it;
            }
    };

    ms(a);
    ms(b);
    ms(c);

    if (!best)
        best = m[key/200].push_back({key, T()});

    return best->value;
}
于 2012-06-01T16:31:34.227 回答
0

std::map解决此问题的一种方法可能是编写您自己的通过组合扩展的容器类。

将 astd::map作为成员并转发任何需要的函数和 typedef。

确保至少使用以下功能实现您的“试错”逻辑：

  • count
  • find
  • operator[]
  • at
于 2012-06-01T13:49:34.117 回答