¿Existe una estructura de datos de mapa de clave más cercana?

Question

Tengo una situación en la que necesito encontrar el valor con la clave más cercana a la que solicito. Es como el mapa más cercano que define la distancia entre las teclas.

Por ejemplo, si tengo las teclas {A, C, M, Z} en el mapa, una solicitud de D devolvería el valor de C.

¿Alguna idea?

Answer 1

La mayoría de las estructuras de datos en árbol usan algún tipo de algoritmo de clasificación para almacenar y encontrar claves. Muchas implementaciones de este tipo pueden ubicar una tecla de cierre de la tecla con la que indaga (normalmente, es la más cercana a continuación o la más cercana). Por ejemplo, el TreeMap de Java implementa dicha estructura de datos y puede indicarle que obtenga la clave más cercana debajo de su clave de búsqueda, o la clave más cercana sobre su clave de búsqueda (higherKey y lowerKey).

Si puede calcular distancias (no siempre es fácil: la interfaz de Java solo requiere que sepa si una tecla dada está "debajo" o "encima" de cualquier otra tecla dada) puede solicitar tanto la más cercana arriba como la más cercana a continuación y luego calcule cuál está más cerca.

Answer 2

¿Cuál es la dimensionalidad de sus datos? Si solo tiene una dimensión, una matriz ordenada lo hará: una búsqueda binaria ubicará la coincidencia exacta y/o revelará entre qué dos claves se encuentra la clave de búsqueda, y una simple prueba le indicará cuál está más cerca.

Si necesita ubicar no solo la clave más cercana, sino un valor asociado, mantenga una matriz de valores ordenada de manera idéntica: el índice de la clave recuperada en la matriz clave es el índice del valor en la matriz de valores.

Por supuesto, hay muchos enfoques alternativos - cuál utilizar depende de muchos otros factores, tales como el consumo de memoria, si es necesario insertar valores, si se controla el orden de inserción, deleciones, problemas de threads, etc ...

Answer 3

Puede implementar algo así como un árbol. Un enfoque simple es asignar a cada nodo en el árbol una cadena de bits. Cada nivel del árbol se almacena como un bit. Toda la información primaria está codificada en la cadena de bits del nodo. A continuación, puede ubicar fácilmente nodos arbitrarios y buscar padres e hijos. Así es como funciona Morton ordering, por ejemplo. Tiene la ventaja adicional de que puede calcular distancias entre nodos mediante una simple resta binaria.

Si tiene múltiples enlaces entre valores de datos, entonces su estructura de datos es un gráfico en lugar de un árbol. En ese caso, necesita un sistema de indexación un poco más sofisticado. Distributed hash tables hacer este tipo de cosas. Por lo general, tienen una forma de calcular la distancia entre dos nodos cualquiera en el espacio índice. Por ejemplo, el algoritmo Kademlia (utilizado por Bittorrent) usa distancias XOR aplicadas a identificadores de cadena de bits. Esto permite que los clientes de Bittorrent busquen identificadores en una cadena, convergiendo en la ubicación de destino desconocida. Puede usar un enfoque similar para encontrar los nodos más cercanos a su nodo objetivo.

Answer 4

BK-trees haz exactamente lo que quieras. Aquí hay un good article al implementarlos.

Y aquí es una aplicación 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 
    } 
} 

voy a admitir a una cierta suciedad & fealdad de ello, y de ser demasiado inteligente con el algoritmo de inserción. Además, solo funcionará bien para distancias pequeñas, de lo contrario buscará repetidamente en el árbol.Aquí está una implementación alternativa que hace un mejor trabajo de la misma:

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

Si las llaves son cadenas y la función de su similitud es Levenshtein distance, entonces usted puede utilizar finite-state machines:

Su mapa es una trie construido como un finita -establecer la máquina (mediante la unión de todos los pares clave/valor y la determinación). Luego, redacte su consulta de entrada con un transductor de estado finito simple que codifique la distancia de Levenshtein, y componga eso con su trie. Luego, use Viterbi algorithm para extraer la ruta más corta.

Se puede implementar todo esto con sólo unos pocos función de llamadas con un finite-state toolkit.

Answer 6

en Scala Esta es una técnica que utilizo para encontrar el más cercano Int < = a la clave que busca

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

con C++ y contenedores STL (std::map), puede utilizar la siguiente función de plantilla:

#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; 
} 

salida:

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

Se se supone que se usa operator - como una función para evaluar la distancia. Debe implementar ese operador si class T es su propia clase, objetos de los cuales sirven como claves en un mapa. También puede cambiar el código para utilizar class T función miembro estática especial (por ejemplo, distance), no operator -, en su lugar:

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

donde distance debe ser algo bajo. como

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

y distance_type deben apoyar comparación por operator <