最近傍キーマップデータ構造はありますか？

Question

私は、要求したキーに最も近いキーで値を見つける必要がある状況があります。これは、キーの間の距離を定義する最も近いマップのようなものです。

たとえば、マップに{A、C、M、Z}というキーがある場合、DのリクエストはCの値を返します。

Answer 1

ほとんどのツリーデータ構造は、ソートアルゴリズムを使用してキーを格納および検索します。そのような実装の多くは、プローブするキー（通常はそのすぐ下にあるか、それに近いもの）に近いキーを見つけることができます。たとえば、JavaのTreeMapはそのようなデータ構造を実装しており、ルックアップキーの下の最も近いキー、またはルックアップキーの上の最も近いキー（higherKeyおよびlowerKey）を取得するように指示できます。

距離を計算できれば（Javaのインターフェイスでは、指定されたキーが他の指定キーの「下」または「上」であるかどうかを知る必要があります）、次に、どちらが近いか自分で計算してください。

Answer 2

データの次元は何ですか？ 1次元であれば、ソートされた配列がそれを行います。バイナリ検索では、正確に一致するものが見つかるか、検索キーが存在する2つのキーが表示されます。そして、どちらが近いか簡単なテストが表示されます。

最も近いキーだけでなく関連する値を見つける必要がある場合は、値の配列を同じに保ちます。キー配列内の検索されたキーのインデックスは、value配列の値のインデックスになります。

多くの代替方法 - メモリ消費、挿入する必要があるかどうか、挿入の順序を制御するかどうか、削除、スレッドの問題など、他の多くの要因によって決まります。 ...

Answer 3

このようなものをツリーとして実装できます。簡単なアプローチは、ツリー内の各ノードにビット列を割り当てることです。ツリーの各レベルはビットとして格納されます。すべての親情報は、ノードのビット列にエンコードされます。その後、任意のノードを簡単に見つけて、親と子を見つけることができます。これは例えばMorton orderingの動作です。単純なバイナリ減算によってノード間の距離を計算できるという特別な利点があります。

データ値間に複数のリンクがある場合、データ構造はツリーではなくグラフです。その場合、少し洗練されたインデックスシステムが必要です。 Distributed hash tablesこの種のことをしてください。彼らは通常、インデックス空間内の任意の2つのノード間の距離を計算する方法を持っています。たとえば、ビットトレントで使用されるアルゴリズムKademliaは、ビットストリングIDに適用されるXOR距離を使用します。これにより、Bittorrentクライアントはチェーン内のIDを検索し、未知のターゲット位置に収束させることができます。同様のアプローチを使用して、ターゲットノードに最も近いノードを見つけることができます。

Answer 4

BK-treesあなたが望むものを正確に行います。それらの実装にはgood articleがあります。

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に認めるよ：ここ

とは、Scalaの実装です。また、小さな距離でのみ正常に動作します。そうでなければ、ツリーを繰り返し検索します。あなたのキーは文字列であり、あなたの類似度関数がLevenshtein distanceある場合

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

、あなたはfinite-state machinesを使用することができます：ここでのより良い仕事をして別の実装です

あなたのマップが有限として構築trieです（すべてのキー/値の組を結合して決定することによって）状態機械。次に、Levenshtein距離をエンコードする簡単な有限状態トランスデューサで入力クエリを作成し、それをトライで構成します。次に、Viterbi algorithmを使用して最短パスを抽出します。

finite-state toolkitを使用して、わずかな関数呼び出しですべてを実装できます。 Scalaでは

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）を探しているキーに最も近いのInt < =を見つけるために使用テクニックです：

#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 -を使用するようにコードを変更することができます：distanceはなめらかでなければなりません

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

を。

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

とdistance_typeようoperator <