问题标签 [edit-distance]

这个问题并不新鲜，我在这里和这里看到了某种形式的解释。这两种方法都描述了对查询 1 和查询 2 的术语执行 N 克（主要是二元）计算，然后找到余弦相似度。

我希望根据我的理解进行澄清：

我需要获取查询 1 和查询 2 中所有二元组的 TF-IDF 分数，然后使用该分数来计算余弦相似度分数。如果是这样，任何人都可以编写一个简单的python代码以获得更清晰的解释吗？

基于这篇论文： IEEE TRANSACTIONS ON PAITERN ANALYSIS : Computation of Normalized Edit Distance and Applications 在本文中 Normalized Edit Distance如下：

给定有限字母表上的两个字符串 X 和 Y，X 和 Y 之间的归一化编辑距离 d( X , Y ) 定义为 W( P ) / L ( P )w 的最小值，这里 P 是之间的编辑路径X 和 Y ，W ( P ) 是 P 的基本编辑操作的权重之和，L(P) 是这些操作的数量（P 的长度）。

我可以安全地将上面解释的归一化编辑距离算法翻译为：

我试图了解 Wagner–Fischer 算法来查找字符串之间的距离。我正在以下链接中查看它的伪代码：http ://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm

实际上我明白了算法的要点并直观地理解它，因为它对我来说并不明显为什么d[i-1, j] + 1, d[i, j-1] + 1 和 d[i-1, j-1 ] + 1被认为是删除、插入和替换。如果有人以更详细的方式解释实现的细微差别，那就太好了。

我有 2 个查询：

当我使用 python 库 Levenshtein 运行此代码时：

我得到 12 的输出。现在的问题是值 12 是如何得出的？

因为就笔画差异而言，肯定不止12个。

我正在使用 solr 4.6.1 拼写检查组件来提供拼写建议。我将其配置为使用带有默认距离函数和比较器的 DirectSolrSpellChecker，据我了解，这意味着建议按编辑距离（主键）排序，然后是文档频率（次键）。

但是，对于 paper 一词，最重要的建议是papier，它的文档频率远低于paper。两种选择都与paper相距 1 编辑距离。

这是我不理解的编辑距离算法的错误还是怪癖？

我的拼写检查配置：

我想使用 R 来比较很多整数列表，使用编辑距离。例如：list1[231, 3883, 21099, 12, 2]和list2[433, 3883, 12, 919, 2]

我想得到这两个列表之间的距离。前任。使用上面的列表，距离将等于3。因为要做出list2喜欢list1，你会substitute 231为了433，然后add 21099之后3883，然后delete 919。

我想知道需要多少添加和删除才能使 list1 看起来像 list2。我知道 R 具有内置功能：adist(). 然而，这似乎只适用于比较字符串（甚至不是字符串列表）。谷歌一直在推动我adist()去dist()解决这个问题。我宁愿不重新发明轮子，那么是否已经存在功能？我试图重写adist()在这里找到：https://searchcode.com/codesearch/view/13555814/ 但它对我目前的 R 能力来说太复杂了。

我想在插入/删除/编辑单词方面检查两个字符串之间的距离。这类似于 levenshtein 距离，但我只关心单词，而不关心字符。例如：

“猫坐在垫子上”和“狗小心地坐在垫子上”

单词距离为 3。

我正在使用 Rosetta Code C++ 脚本进行 levenshtein 距离，但我不知道该怎么做。

我正在尝试为基于自定义距离函数的字符串创建一个距离矩阵（用于聚类）。我在一个 6000 个单词的列表上运行了代码，并且它自最后 90 分钟以来仍在运行。我有 8 GB RAM 和 Intel-i5，所以问题仅出在代码上。这是我的代码：

我认为问题可能是我使用循环而不是应用 - 但后来我发现在很多地方循环并不是那么低效。更重要的是，我不够熟练，无法使用 apply 因为我的循环是嵌套循环，例如k in 1:nand j in k:n。我想知道是否还有其他可以优化的东西。

我正在尝试找出根据商家名称和金额搜索列表的最佳方法。例如考虑以下事务类或目标：

搜索列表的输入可能是商家的“Acme”和金额的“13.37”。或“Amce”——Acme 拼写错误。天气商人的拼写 100% 正确或略有偏差 我想退回所有“Acme”交易。此外，基于输入金额的“接近度”和拼写与实际交易金额/名称的接近度，为交易提供排名或权重，以便 UI 层可以相应地呈现。

从概念上讲，我了解 SoundEx 和 Edit Distance 类型的算法，但在代码中实现这一点的实践经验为零。希望从这里的社区中汲取经验，您将获得指导。我知道这段代码可能（也许不是）更适合在 SQL 中实现（在我的情况下是 SQL），但现在我想看看这是否可以在应用程序代码中实现——c#。不过对 SQL 建议持开放态度。

谢谢

我最近遇到了这个问题：

解决此问题的一种方法是使用动态编程找到两个字符串之间的编辑距离，并检查它是否为 1。这将花费 O(N2) 时间。有没有办法在线性时间内做到这一点，因为我们只需要检查它们是否在 1 个编辑之外？

我在下面编写的代码适用于大多数情况，但对于 {"m",""} 等情况则失败