Есть ли ближайшая карта данных?

Ответ 1

В большинстве структур данных дерева используется некоторый алгоритм сортировки для хранения и поиска ключей. Многие реализации таких могут найти ключ закрытия ключа, с которым вы зондируете (обычно это либо ближайший ниже, либо ближайший выше). Например, Java TreeMap реализует такую ​​структуру данных, и вы можете сказать ей, чтобы получить ближайший ключ под вашим ключом поиска или ближайший ключ над вашим ключом поиска (higherKey и lowerKey).

Если вы можете рассчитать расстояния (не всегда легко - интерфейс Java требует, чтобы вы знали, находится ли какой-либо данный ключ "ниже" или "выше" любого другого заданного ключа), тогда вы можете запросить как ближайшее, так и самое близкое ниже и затем подсчитайте для себя, какой из них ближе.

Ответ 2

Какова размерность ваших данных? Если это всего лишь одно измерение, сортированный массив сделает это - бинарный поиск найдет точное совпадение и/или покажет, между какими двумя ключами находится ваш ключ поиска, и простой тест скажет вам, что ближе.

Если вам нужно найти не только ближайший ключ, но и связанное с ним значение, поддерживайте идентично отсортированный массив значений - индекс возвращаемого ключа в массиве ключей будет тогда индексом значения в массиве значений.

Конечно, существует много альтернативных подходов, которые можно использовать в зависимости от многих других факторов, таких как потребление памяти, нужно ли вводить значения, если вы контролируете порядок вставки, удаления, проблемы с потоками и т.д..

Ответ 3

BK-деревья делают именно то, что вы хотите. Здесь хорошая статья об их реализации.

И вот реализация 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
  }
}

Я соглашусь на определенную грязь и уродство об этом, и быть слишком умным с алгоритмом вставки. Кроме того, он будет работать только на небольшом расстоянии, иначе вы будете многократно искать дерево. Здесь альтернативная реализация, которая лучше справляется с этим:

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
}

Ответ 4

В контейнерах С++ и 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

Предполагается, что a 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 <

Ответ 5

Вы можете реализовать что-то подобное в виде дерева. Простым подходом является назначение каждого node в дереве битовой строки. Каждый уровень дерева хранится как бит. Вся родительская информация кодируется в битовой строке node. Затем вы можете легко найти произвольные узлы и найти родителей и детей. Например, "Заказ Morton" работает. У этого есть дополнительное преимущество, что вы можете рассчитать расстояния между узлами простым двоичным вычитанием.

Если у вас есть несколько связей между значениями данных, ваша структура данных представляет собой график, а не дерево. В этом случае вам потребуется немного более сложная система индексирования. Распределенные хэш-таблицы делают такие вещи. Обычно они имеют способ вычисления расстояния между любыми двумя узлами в индексном пространстве. Например, алгоритм Kademlia (используемый Bittorrent) использует расстояния XOR, применяемые к идентификаторам битстрима. Это позволяет клиентам Bittorrent искать идентификаторы в цепочке, сходящиеся в неизвестном целевом местоположении. Вы можете использовать аналогичный подход, чтобы найти node (s), ближайший к вашей цели node.

Ответ 6

Если ваши клавиши являются строками, а ваша функция подобия расстояние Levenshtein, то вы можете использовать конечные машины:

Ваша карта представляет собой trie, созданный как конечный автомат (путем объединения всех пар ключ/значение и детерминации). Затем составьте свой входной запрос с помощью простого преобразователя с конечным состоянием, который кодирует расстояние Левенштейна и составит его с помощью тви. Затем используйте алгоритм Витерби, чтобы извлечь кратчайший путь.

Вы можете реализовать все это только с помощью нескольких вызовов функций, используя конечный набор инструментов.

Ответ 7

в scala это метод, который я использую, чтобы найти ближайший Int <= к ключу, который вы ищете

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