Levenstein-distance-like metric中的最近邻居搜索

Question

我有一组单词（'词典'），并且我必须从字典中找到最接近的单词，给定一个新单词。 （我使用'word'作为关键字，因为它实际上是一个抽象'字母'的可变长度序列）。

我使用Levenstein距离作为度量的概括 - 我需要概括的原因是我需要交换两个给定字母的特定“成本” - 例如，我需要与'a'交换' b'与'c'交换'a'的成本更低。我想我仍然必须说服自己，我的泛化仍然是一个指标。

目前我正在使用朴素的线性搜索，即迭代字典中的所有单词并跟踪最小距离，我正在寻找更高效的方法。

我开始阅读关于最近邻搜索的方法，但是对于我来说，主要的概念难点是我的'点'（单词）没有嵌入到我可以想象的空间中，并且它们不是具有维度的向量等。

考虑到这一点，我想听听一些关于寻找哪些算法的建议。

Answer 1

让我重新表达你的问题，并给你一个可能的答案。没有看到你的数据集，我不知道哪个对你更好。

您已经有了一个算法，给定两个单词，给出它们之间的距离。它是基于Levenstein距离为这些词汇之间的路径，对成本进行一些修改。而且你希望找到与给定单词最接近的单词，而不必搜索整个字典。

我会尝试的最简单的方法就是从您的单词开始，搜索所有可能的修改集，直到找到字典中最接近的单词为止。你想要一个修改的广度优先搜索。商店(0, your_word)在某种0​​的唯一入口（堆是很容易实现的），抢在距离一个随机字典中的词作为目前最好的解决方案，那么只要优先级队列不为空：

Take the lowest cost element out. 
If it is more expensive than your best solution: 
    stop, return your best. 
For each possible one step modification of that word: 
    if the new word is in the dictionary and is lower cost than your best: 
     improve best estimate 
    else: 
     store (new_cost, new_word) in the priority queue 

这将导致以原始单词开始的指数增长搜索集。但是如果字典中有附近的单词，它应该很快找到。如果你走这条路线，你可能希望在搜索空间上限后放弃。

这可能远非最佳解决方案，但编程和尝试不应太难。