有没有最近键的地图数据结构？

Question

我有一种情况，我需要找到最接近我请求的密钥的值。它有点像定义键之间距离的最近的地图。例如，如果我在地图中有键{A，C，M，Z}，则对D的请求将返回C的值。

有什么想法？

Answer 1

大多数树数据结构使用某种排序算法来存储和查找密钥。这样的许多实现可以找到您探测的密钥的密钥（通常是最接近的或最接近的密钥）。例如，Java的TreeMap实现了这样一种数据结构，您可以告诉它为您提供查找键下方最近的键或查找键上方最近的键（higherKey和lowerKey）。如果你可以计算距离（它并不总是很容易 - Java的接口只需要你知道给定的键是否在任何其他给定键的“下方”或“上方”），那么你可以要求两个距离最近和最近的距离然后为自己计算哪一个更接近。

Answer 2

什么是你的数据的维度？如果它只是一维的，排序后的数组就可以做到这一点 - 二进制搜索将找到确切的匹配和/或揭示搜索关键所在的两个键之间的关系 - 而一个简单的测试会告诉你哪个更接近。

如果您不仅需要定位最近的键，而且需要定位一个相关联的值，则需要维护一个相同排序的值数组 - 然后，键数组中检索到的键的索引就是值数组中值的索引。

当然，有许多替代方法 - 哪一个使用取决于许多其他因素，如内存消耗，是否需要插入值，如果您控制插入，删除，线程问题的顺序， etc ...

Answer 3

你可以像树一样实现这样的东西。一个简单的方法是为树中的每个节点分配一个位串。树的每个级别都存储一点。所有的父信息都编码在节点的位串中。然后，您可以轻松找到任意节点，并找到父母和孩子。例如，这是Morton ordering的工作方式。它具有额外的优点，您可以通过简单的二进制减法计算节点之间的距离。

如果数据值之间有多个链接，那么你的数据结构就是一个图形而不是一棵树。在这种情况下，你需要一个稍微复杂的索引系统。 Distributed hash tables做这种事情。它们通常有一种计算索引空间中任意两个节点之间距离的方法。例如，Kademlia算法（由Bittorrent使用）使用应用于bitstring ID的XOR距离。这允许Bittorrent客户端在链中查找ID，并聚合到未知的目标位置。您可以使用类似的方法来查找距离目标节点最近的节点。

Answer 4

BK-trees正是你想要的。以下是实施它们的good article。

这里是一个Scala实现：

class BKTree[T](computeDistance: (T, T) => Int, node: T) { 
    val subnodes = scala.collection.mutable.HashMap.empty[Int,BKTree[T]] 

    def query(what: T, distance: Int): List[T] = { 
    val currentDistance = computeDistance(node, what) 
    val minDistance = currentDistance - distance 
    val maxDistance = currentDistance + distance 
    val elegibleNodes = (
     subnodes.keys.toList 
     filter (key => minDistance to maxDistance contains key) 
     map subnodes 
    ) 
    val partialResult = elegibleNodes flatMap (_.query(what, distance)) 
    if (currentDistance <= distance) node :: partialResult else partialResult 
    } 

    def insert(what: T): Boolean = if (node == what) false else (
    subnodes.get(computeDistance(node, what)) 
    map (_.insert(what)) 
    getOrElse { 
     subnodes(computeDistance(node, what)) = new BKTree(computeDistance, what) 
     true 
    } 
) 

    override def toString = node.toString+"("+subnodes.toString+")" 
} 

object Test { 
    def main(args: Array[String]) { 
    val root = new BKTree(distance, 'A') 
    root.insert('C') 
    root.insert('M') 
    root.insert('Z') 
    println(findClosest(root, 'D')) 
    } 
    def charDistance(a: Char, b: Char) = a - b abs 
    def findClosest[T](root: BKTree[T], what: T): List[T] = { 
    var distance = 0 
    var closest = root.query(what, distance) 
    while(closest.isEmpty) { 
     distance += 1 
     closest = root.query(what, distance) 
    } 
    closest 
    } 
} 

我承认在一定污垢& uglyness一番，意思是与插入算法太聪明了。此外，它只适用于小距离，否则你会反复搜索树。这里有一个备用实现，它的一个更好的工作：

class BKTree[T](computeDistance: (T, T) => Int, node: T) { 
    val subnodes = scala.collection.mutable.HashMap.empty[Int,BKTree[T]] 

    def query(what: T, distance: Int): List[T] = { 
    val currentDistance = computeDistance(node, what) 
    val minDistance = currentDistance - distance 
    val maxDistance = currentDistance + distance 
    val elegibleNodes = (
     subnodes.keys.toList 
     filter (key => minDistance to maxDistance contains key) 
     map subnodes 
    ) 
    val partialResult = elegibleNodes flatMap (_.query(what, distance)) 
    if (currentDistance <= distance) node :: partialResult else partialResult 
    } 

    private def find(what: T, bestDistance: Int): (Int,List[T]) = { 
    val currentDistance = computeDistance(node, what) 
    val presentSolution = if (currentDistance <= bestDistance) List(node) else Nil 
    val best = currentDistance min bestDistance 
    subnodes.keys.foldLeft((best, presentSolution))(
     (acc, key) => { 
     val (currentBest, currentSolution) = acc 
     val (possibleBest, possibleSolution) = 
      if (key <= currentDistance + currentBest) 
      subnodes(key).find(what, currentBest) 
      else 
      (0, Nil) 
     (possibleBest, possibleSolution) match { 
      case (_, Nil) => acc 
      case (better, solution) if better < currentBest => (better, solution) 
      case (_, solution) => (currentBest, currentSolution ::: solution) 
     } 
     } 
    ) 
    } 

    def findClosest(what: T): List[T] = find(what, computeDistance(node, what))._2 

    def insert(what: T): Boolean = if (node == what) false else (
    subnodes.get(computeDistance(node, what)) 
    map (_.insert(what)) 
    getOrElse { 
     subnodes(computeDistance(node, what)) = new BKTree(computeDistance, what) 
     true 
    } 
) 

    override def toString = node.toString+"("+subnodes.toString+")" 
} 

object Test { 
    def main(args: Array[String]) { 
    val root = new BKTree(distance, 'A') 
    root.insert('C') 
    root.insert('E') 
    root.insert('M') 
    root.insert('Z') 
    println(root.findClosest('D')) 
    } 
    def charDistance(a: Char, b: Char) = a - b abs 
} 

Answer 5

如果你的键是字符串和你相似的功能是Levenshtein distance，那么你可以使用finite-state machines：

你的地图是建成一个有限的一个trie （通过将所有键/值对组合并确定）。然后，使用编码Levenshtein距离的简单有限状态转换器编写输入查询，然后用您的trie编写。然后，使用Viterbi algorithm来提取最短路径。

只需几个函数调用即可使用finite-state toolkit实现所有这些。

Answer 6

在斯卡拉

这是一种技术，我用它来找到最接近的诠释< =的关键，你正在寻找

val sMap = SortedMap(1 -> "A", 2 -> "B", 3 -> "C") 
sMap.to(4).lastOption.get // Returns 3 
sMap.to(-1) // Returns an empty Map 

Answer 7

用C++和STL容器（std::map），可以使用下面的模板功能：

#include <iostream> 
#include <map> 

//!This function returns nearest by metric specified in "operator -" of type T 
//!If two items in map are equidistant from item_to_find, the earlier occured by key will be returned 

template <class T,class U> typename std::map<T,U>::iterator find_nearest(std::map<T,U> map_for_search,const T& item_to_find) 
{ 
    typename std::map<T,U>::iterator itlow,itprev; 
    itlow=map_for_search.lower_bound(item_to_find); 
    itprev=itlow; 
    itprev--; 
//for cases when we have "item_to_find" element in our map 
//or "item_to_find" occures before the first element of map 
    if ((itlow->first==item_to_find) || (itprev==map_for_search.begin())) 
    return itlow; 
//if "item"to_find" is besides the last element of map 
    if (itlow==map_for_search.end()) 
    return itprev; 

    return (itlow->first-item_to_find < item_to_find-itprev->first)?itlow:itprev; // C will be returned 
//note that "operator -" is used here as a function for distance metric 
} 

int main() 
{ 
    std::map<char,int> mymap; 
    std::map<char,int>::iterator nearest; 
    //fill map with some information 
    mymap['B']=20; 
    mymap['C']=40; 
    mymap['M']=60; 
    mymap['Z']=80; 
    char ch='D'; //C should be returned 
    nearest=find_nearest<char,int>(mymap,ch); 
    std::cout << nearest->first << " => " << nearest->second << '\n'; 
    ch='Z'; //Z should be returned 
    nearest=find_nearest<char,int>(mymap,ch); 
    std::cout << nearest->first << " => " << nearest->second << '\n'; 
    ch='A'; //B should be returned 
    nearest=find_nearest<char,int>(mymap,ch); 
    std::cout << nearest->first << " => " << nearest->second << '\n'; 
    ch='H'; // equidistant to C and M -> C is returned 
    nearest=find_nearest<char,int>(mymap,ch); 
    std::cout << nearest->first << " => " << nearest->second << '\n'; 
    return 0; 
} 

输出：

C => 40 
Z => 80 
B => 20 
C => 40 

它假设operator -被用作评估距离的函数。如果class T是您自己的班级，则应该实施该操作员，其中的对象用作地图中的键。 你也可以修改代码，使用特殊class T静态成员函数（比如，distance），不operator -，而是：

return (T::distance(itlow->first,item_to_find) < T::distance(item_to_find,itprev->first))?itlow:itprev; 

其中distance应该是不便。像

static distance_type some_type::distance()(const some_type& first, const some_type& second){//...} 

和distance_type应支持operator <