问题标签 [levenshtein-distance]

我坐在这里，为我的 Java 主程序编程一些算法（到目前为止是第一个）。我对 levenshtein 算法进行了很好的编程，这要归功于 wiki 对新手的伪代码非常好，还有一个很好的教程：D

然后我决定升级到 Damerau 并添加了额外的行，但后来我读到它不是 DL 算法，而是 OptimalStringAlignmentDistance。我尝试阅读 actionscript 代码以了解我需要添加哪些内容才能将其添加到 DL 中，但却感到困惑。我去过不同的地方，代码看起来像 Java，但它们也都使用了错误的伪代码。

花了半天时间我放弃了，决定在这里问。有没有人可以帮助我将此代码升级到 Java 中的 Damerau-Levenshtein？

这是Damerau–Levenshtein 距离算法的维基百科页面

我正在尝试用字典创建一个光学字符识别系统。

事实上我还没有实现字典=）

我听说有基于 Levenstein 距离的简单指标，它考虑了不同符号之间的不同距离。例如，'N' 和 'H' 彼此非常接近，并且 d("THEATRE", "TNEATRE") 应该小于 d("THEATRE", "TOEATRE") 使用基本 Levenstein 距离是不可能的。

你能帮我找到这样的指标吗？

我用 Java 实现了 Levenshtein 算法，现在我得到了算法所做的更正，也就是成本。这确实有一点帮助，但没有多大帮助，因为我希望将结果作为百分比。

所以我想知道如何计算那些相似点。

我也想知道你们是怎么做的以及为什么。

我想运行 Levenshtein，但要快得多，因为它是我正在构建的实时应用程序。一旦距离大于 10 就可以终止。

我想知道是否有人将 Jarowinkler 函数实现为 SQLite 的可加载扩展。

我正在寻找与“ SQLite-Levenshtein”等效的产品。Mateusz Adamowski 作为 SQLite 可加载扩展的 Levenstehein 距离的出色实现

https://github.com/mateusza/SQLite-Levenshtein

提前致谢

使用 Commons Lang api，我可以通过LevensteinDistance计算两个字符串之间的相似度。结果是将一个字符串更改为另一个字符串所需的更改次数。我希望结果在 0 到 1 的范围内，这样更容易识别字符串之间的相似性。结果将更接近于 0 相似度。可能吗？

在我正在使用的示例下方：

谢谢！

我正在尝试创建或查找 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

I am doing clinical message normalization (spell check) in which I check each given word against 900,000 word medical dictionary. I am more concern about the time complexity/performance.

I want to do fuzzy string comparison, but I'm not sure which library to use.

Option 1:

Option 2:

In this example both give the same answer. Do you think both perform alike in this case?

我有一个 MySQL 数据库表，其中包含大约 1000 家商店的信息。现在我将通过上传 Excel 电子表格来导入更多商店，并且我正在努力避免重复。

• 商店可能有相同的名称，但永远不会有相同的地址。
• 商店可能有相同的地址，但绝不会使用相同的名称

但这是我的问题。

• 商店可能拼写错误
• 地址可能拼写错误

目前我正在将数据导入临时表。现在我想知道将进口商店与现有商店进行比较的最佳方法是什么。

我的计划是遍历每一行并比较商店。

• 首先比较 a.name = b.name AND a.street = b.street。匹配时，商店被删除。
• 然后我将对名称和街道进行 Levenshtein 比较。在这里，我可能必须手动查看结果以确定它是否重复。

有没有人有这种数据比较的经验？

更新
感谢您的好答案。

将用于比较的字段是：

• 姓名
• 街道地址
• 邮政编码
• 城市
• 国家

我在想一些事情：

选择 name = Lavenshtein 和 country = country 的行。
这样我只需要处理一个小列表。

然后我可以开始更彻底地比较姓名和地址。

我正在使用Edit/Levenstein 距离来测量单词之间的相似性。与最简单的实现不同，我的信件有时间戳，比如说样本编号 N=0,1,2,...

我面临的问题是我可以沿着成本矩阵获得不同的路径，这些路径以相同的（最小）成本结尾，并且这些不同的路径与不同的目标字符串相关联。例如，如果我测量源字符串aa和目标字符串之间的距离bab，并假设源字符串从时间戳 N=0 开始，那么我有 2 条路径，成本相同为 2（一个加法和一个替换）：

1. b在 N=-1 处添加，保持第一个a不变，并将第二个替换为aa b。
2. 用 a代替第a一个b，保持第二个不变a，并b在 N=2 处添加。

在时间线上对齐，这两个结果是不同的：

我需要知道什么时候会发生这种情况，所以我可以根据一些标准在两个可能的目标之间进行选择。除了沿途跟踪路径并跟踪所有可能导致成本最小的路径之外，还有其他方法吗？

我考虑过使用动态时间扭曲，因为时间线首先是模型的一部分，但似乎由于成本矩阵被初始化为无穷大（除了 [0,0] 条目），第一步将始终将目标的第一帧与源的第一帧进行匹配，从而导致目标与源的时间戳相同。无论如何，使用 DTW，我仍然必须跟踪所有导致相同最小成本的路径。

欢迎任何帮助或见解。