2

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

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

目前我正在使用简单的线性搜索，即遍历字典中的所有单词并跟踪最小距离，我正在寻找一种更有效的方法。

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

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

4

1 回答 1

1

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

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

我会尝试的最简单的事情是从您的单词开始，并搜索所有可能的修改集，直到您在字典中找到最接近的单词。您需要修改后的广度优先搜索。存储(0, your_word)为某种http://en.wikipedia.org/wiki/Priority_queue中的唯一条目（堆很容易实现），获取与随机字典单词的距离作为您当前的最佳解决方案，然后只要优先队列不为空：

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

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

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

于 2011-04-26T16:12:25.657 回答