问题标签 [edit-distance]

我正在尝试创建或查找 Levenshtein 距离公式的 CoffeeScript 实现，即编辑距离。这是我到目前为止所拥有的，任何帮助都将不胜感激。

顺便说一句：我知道这段代码在很多方面都是错误的，我很高兴收到任何建设性的批评。只是想改进，并找出这个公式！

CodeEdit1：修补了 Trevor 指出的错误，上面的当前代码包括这些更改

更新：我要问的问题是 - 我们如何在 CoffeeScript 中进行 Levenshtein？

这是 Levenshtein 距离算法的“步骤”，可帮助您了解我要完成的工作。

步骤 1
将 n 设置为 s 的长度。将 m 设置为 t 的长度。如果 n = 0，则返回 m 并退出。如果 m = 0，则返回 n 并退出。构造一个包含 0..m 行和 0..n 列的矩阵。

2
将第一行初始化为 0..n。将第一列初始化为 0..m。

3 检查 s 的每个字符（i 从 1 到 n）。

4 检查 t 的每个字符（j 从 1 到 m）。

5 如果 s[i] 等于 t[j]，则成本为 0。如果 s[i] 不等于 t[j]，则成本为 1。

6 设置矩阵的单元格 d[i,j] 等于以下的最小值：正上方的单元格加 1：d[i-1,j] + 1。紧靠左边的单元格加 1：d[i,j-1] + 1。对角线上方和左侧的单元格加上成本：d[i-1,j-1] + 成本。

7 迭代步骤 (3, 4, 5, 6) 完成后，在单元格 d[n,m] 中找到距离。

来源：http://www.merriampark.com/ld.htm

给定两个文件树 A 和 B，是否可以确定将 A 转换为 B 所需的最短操作序列或操作序列？

一个操作可以是：

1. 创建一个新的空文件夹
2. 创建一个包含任何内容的新文件
3. 删除文件
4. 删除一个空文件夹
5. 重命名文件
6. 重命名文件夹
7. 在另一个现有文件夹中移动文件
8. 在另一个现有文件夹中移动文件夹

当 A 和 B 在相同文件夹结构中具有相同内容（或相同大小相同 CRC）和相同名称的相同文件时，它们是相同的。

这个问题让我困惑了一段时间。目前我有以下基本想法：

• 计算一个数据库：
  • 存储文件名及其 CRC
  • 然后，找到所有没有子文件夹的文件夹，并根据它们包含的文件的 CRC 计算 CRC，并根据它们包含的文件的总大小计算大小
  • 提升树为每个父文件夹创建一个 CRC
• 使用具有数据库 A 和数据库 B 的以下循环：
  • 计算 A ∩ B 并从两个数据库中删除此交集。
  • 使用内连接在 A 和 B 中查找匹配的 CRC，首先是文件夹，按大小排序
  • 当有结果时，使用第一个结果移动文件夹或文件（如有必要，可能创建新文件夹），从两个数据库中删除结果的源行。如果有移动，则更新 db A 中新位置父文件夹的 CRC。
  • 然后删除数据库 A 中引用的所有文件和文件夹，并创建数据库 B 中引用的文件和文件夹。

但是，我认为这确实是一种次优的方法。你能给我什么建议？

谢谢！

我需要编写一个脚本，可能是用 Ruby 编写的，它将获取一个文本块，并将该文本的许多转录记录与原始文本进行比较，以检查准确性。如果这完全令人困惑，我会尝试用另一种方式解释......

我有几个不同的人阅读一个只有几句话的脚本的录音。这些录音都被其他人多次转录回文本。我需要获取所有的转录（数百个）并将它们与原始脚本进行比较以确保准确性。

我什至无法概念化伪代码，并且想知道是否有人可以指出我正确的方向。我应该考虑一个既定的算法吗？有人向我建议了Levenshtein 距离，但考虑到标点​​符号选择、空格等方面的差异，这似乎不能很好地处理较长的字符串——即使每隔一个单词丢失第一个单词也会破坏整个算法很完美。我对任何事情都持开放态度——谢谢！

编辑：

感谢您的提示，心理医生。然而，我最大的担忧之一是这样的情况：

原文：

I would've taken that course if I'd known it was available!

转录

I would have taken that course if I'd known it was available!

即使对标记进行逐字比较，这种转录也会被标记为非常错误，即使它几乎是完美的，而且这几乎不是边缘情况！“would've”和“would have”的发音通常极为相似，尤其是在世界的这个地区。有没有办法让你建议的方法足够强大来处理这个问题？我曾考虑过向前和向后进行逐字比较并建立一种综合得分，但这会因这样的转录而崩溃：

I would have taken that course if I had known it was available!

有任何想法吗？

可能重复：
计算将一种排列转换为另一种排列所需的交换次数

我正在寻找一种算法来计算某种字符串距离，其中只允许操作是两个相邻字符的转置。例如：
string1: "mother"
string2: "moterh"
distance: 2 （首先将“h”与“e”交换并得到“motehr”，然后将“h”与“r”交换为“moterh”）
我知道 Damerau –Levenshtein 距离与该问题非常相似，但是它需要大量内存（我希望它在最多 1 000 000 个字符的单词上运行得非常快）。我已经写了这个：

字符串表示为 char[n]，其中 n 是它们的长度。我很确定有一种方法可以更快地做到这一点，如果有人能告诉我如何做到这一点或编写一些源代码（最好是 Java/Python/C++，但任何事情都很棒），我将非常感激。

PS 请原谅我的语言错误，我不是英语，我还没有掌握那种语言。

给定 2 个字符串s和t. 我需要找到s编辑距离（Levenshtein 距离）中的每个子字符串到t. 实际上，我需要知道从ipositions开始的所有子字符串的最小编辑距离是多少i。

例如：

我需要得到类似的东西：

{2,1,0,2,2}

解释：

等等。

当然，我可以使用蛮力算法来解决这个任务。但是有更快的算法吗？

感谢帮助。

编辑距离查找一个字符串到另一个字符串所需的插入、删除或替换次数。我还想在这个算法中包括交换。例如，“apple”和“appel”应该给出 1 的编辑距离。

在线搜索引擎用于为拼写错误的单词提供建议的典型算法是什么。我说的不一定是 Google，而是任何具有搜索功能的网站，例如 Amazon.com。说我搜索这个词"shoo"；该网站会回来说"did you mean: shoe"。

这是Levenshtein 距离算法的一些变体吗？也许如果他们使用的是一些内置的全文搜索框架（例如 lucene）？也许完全定制？

我知道答案千差万别，我只是在寻找有关如何开始使用此功能的指示（在企业环境中）。

我正在尝试根据集合计算字符串的编辑距离以找到最接近的匹配项。我目前的问题是集合非常大（大约 25000 个项目），所以我不得不将集合缩小到只有相似长度的字符串，但这仍然只能将其缩小到几千个字符串，这仍然很慢。是否有允许快速查找类似字符串的数据结构，或者是否有另一种方法可以解决这个问题？

我试图计算 Levenshtein 距离。以下代码适用于小字符串，例如 kit/fit 或 sit/knit。但是，它给了我周日/周六字符串的分段错误。使用 GDB（第一次）后，我认为问题在于 str2 超出了分配的内存空间。但我一直无法弄清楚如何。我在这上面花了很多时间，现在好像我在盯着一堵墙。有人可以指出我在代码中的错误吗？谢谢你。

输出

我正在尝试编写一个拼写检查模块。

它加载文本，从 16 mb 文件创建字典，然后检查遇到的单词是否与字典中的单词相似（相似 = 最多变化两个字符），如果是，则将其更改为字典中的形式。

现在我正在使用 Levenshtein 距离算法，处理 50 个单词集需要 3 分钟......

我很确定必须有一个更快的解决方案。Profiler 告诉我，我的应用程序在 Levenshtein Distance 函数中花费了超过 80% 的时间。

有没有更好的解决方案/算法？

这是我使用的算法版本的实现：