Нахождение ближайшего соседа с использованием оптимизированного алгоритма Левенштейна

Question

Недавно я опубликовал вопрос об оптимизации алгоритма для вычисления расстояния Левенштейна, и ответы привели меня к статье в Википедии о расстоянии Левенштейна.

В статье упоминается, что если на максимальном расстоянии существует граница k, возможный результат может быть получен из данного запроса, тогда время выполнения может быть уменьшено с O(mn) до O (kn), где m и n - длины строки. Я посмотрел алгоритм, но я не мог понять, как его реализовать. Я надеялся получить некоторые подсказки по этому вопросу здесь.

Оптимизация #4 в разделе "Возможные улучшения".

Часть, которая смутила меня, была та, которая сказала, что нам нужно только вычислить диагональную полосу шириной 2k + 1, центрированную по главной диагонали (главная диагональ определяется как координаты (i,i)).

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

Answer 1

Я делал это несколько раз. Я делаю это с помощью рекурсивного блуждания по дереву игрового дерева возможных изменений. Существует бюджет k изменений, который я использую, чтобы обрезать дерево. С этой подпрограммой сначала я запускаю ее с k=0, затем k=1, затем k=2, пока я не получу удар, или я не хочу идти выше.

char* a = /* string 1 */;
char* b = /* string 2 */;
int na = strlen(a);
int nb = strlen(b);
bool walk(int ia, int ib, int k){
  /* if the budget is exhausted, prune the search */
  if (k < 0) return false;
  /* if at end of both strings we have a match */
  if (ia == na && ib == nb) return true;
  /* if the first characters match, continue walking with no reduction in budget */
  if (ia < na && ib < nb && a[ia] == b[ib] && walk(ia+1, ib+1, k)) return true;
  /* if the first characters don't match, assume there is a 1-character replacement */
  if (ia < na && ib < nb && a[ia] != b[ib] && walk(ia+1, ib+1, k-1)) return true;
  /* try assuming there is an extra character in a */
  if (ia < na && walk(ia+1, ib, k-1)) return true;
  /* try assuming there is an extra character in b */
  if (ib < nb && walk(ia, ib+1, k-1)) return true;
  /* if none of those worked, I give up */
  return false;
}

Добавлено, чтобы объяснить три поиска:

// definition of trie-node:
struct TNode {
  TNode* pa[128]; // for each possible character, pointer to subnode
};

// simple trie-walk of a node
// key is the input word, answer is the output word,
// i is the character position, and hdis is the hamming distance.
void walk(TNode* p, char key[], char answer[], int i, int hdis){
  // If this is the end of a word in the trie, it is marked as
  // having something non-null under the '\0' entry of the trie.
  if (p->pa[0] != null){
    if (key[i] == '\0') printf("answer = %s, hdis = %d\n", answer, hdis);
  }
  // for every actual subnode of the trie
  for(char c = 1; c < 128; c++){
    // if it is a real subnode
    if (p->pa[c] != null){
      // keep track of the answer word represented by the trie
      answer[i] = c; answer[i+1] = '\0';
      // and walk that subnode
      // If the answer disagrees with the key, increment the hamming distance
      walk(p->pa[c], key, answer, i+1, (answer[i]==key[i] ? hdis : hdis+1));
    }
  }
}
// Note: you have to edit this to handle short keys.
// Simplest is to just append a lot of '\0' bytes to the key.

Теперь, чтобы ограничить его бюджетом, просто откажитесь от спуска, если hdis слишком велик.