c++ - 字典容器，如果键不完全正确也能找到值

Question

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

有什么建议吗？

编辑:

感谢评论。

更多详情:为了简单起见，让我们从数字键开始。如果 key 与 key 的距离在200以内，就拿到它。

Answer 1

你需要使用一个叫做 locality-sensitive hashing 的东西，并且您需要在其上编写一些代码(我保证只是一点点。一个额外的词)。

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

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

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

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

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') 与输入 n 和 n' 之间的差值成正比。在这种情况下，lower_bound 是您唯一需要的东西，您不需要额外的散列步骤。

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