问题标签 [levenshtein-distance]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
java - Levenshtein 到 Damerau-Levenshtein
我坐在这里,为我的 Java 主程序编程一些算法(到目前为止是第一个)。我对 levenshtein 算法进行了很好的编程,这要归功于 wiki 对新手的伪代码非常好,还有一个很好的教程:D
然后我决定升级到 Damerau 并添加了额外的行,但后来我读到它不是 DL 算法,而是 OptimalStringAlignmentDistance。我尝试阅读 actionscript 代码以了解我需要添加哪些内容才能将其添加到 DL 中,但却感到困惑。我去过不同的地方,代码看起来像 Java,但它们也都使用了错误的伪代码。
花了半天时间我放弃了,决定在这里问。有没有人可以帮助我将此代码升级到 Java 中的 Damerau-Levenshtein?
ocr - OCR:加权 Levenshtein 距离
我正在尝试用字典创建一个光学字符识别系统。
事实上我还没有实现字典=)
我听说有基于 Levenstein 距离的简单指标,它考虑了不同符号之间的不同距离。例如,'N' 和 'H' 彼此非常接近,并且 d("THEATRE", "TNEATRE") 应该小于 d("THEATRE", "TOEATRE") 使用基本 Levenstein 距离是不可能的。
你能帮我找到这样的指标吗?
java - 相似度得分 - Levenshtein
我用 Java 实现了 Levenshtein 算法,现在我得到了算法所做的更正,也就是成本。这确实有一点帮助,但没有多大帮助,因为我希望将结果作为百分比。
所以我想知道如何计算那些相似点。
我也想知道你们是怎么做的以及为什么。
javascript - 对于字符串距离,是否有比 Levenshtein 更快(不太精确)的算法?
我想运行 Levenshtein,但要快得多,因为它是我正在构建的实时应用程序。一旦距离大于 10 就可以终止。
sqlite - Jarowinkler 作为 SQLite 的可加载扩展
我想知道是否有人将 Jarowinkler 函数实现为 SQLite 的可加载扩展。
我正在寻找与“ SQLite-Levenshtein”等效的产品。Mateusz Adamowski 作为 SQLite 可加载扩展的 Levenstehein 距离的出色实现
https://github.com/mateusza/SQLite-Levenshtein
提前致谢
java - LevensteinDistance - Commons Lang 3.0 API
使用 Commons Lang api,我可以通过LevensteinDistance计算两个字符串之间的相似度。结果是将一个字符串更改为另一个字符串所需的更改次数。我希望结果在 0 到 1 的范围内,这样更容易识别字符串之间的相似性。结果将更接近于 0 相似度。可能吗?
在我正在使用的示例下方:
谢谢!
coffeescript - CoffeeScript中的Levenshtein距离公式?
我正在尝试创建或查找 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
python - High performance fuzzy string comparison in Python, use Levenshtein or difflib
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?
php - 导入数据库时比较数据的最佳方法是什么?
我有一个 MySQL 数据库表,其中包含大约 1000 家商店的信息。现在我将通过上传 Excel 电子表格来导入更多商店,并且我正在努力避免重复。
- 商店可能有相同的名称,但永远不会有相同的地址。
- 商店可能有相同的地址,但绝不会使用相同的名称
但这是我的问题。
- 商店可能拼写错误
- 地址可能拼写错误
目前我正在将数据导入临时表。现在我想知道将进口商店与现有商店进行比较的最佳方法是什么。
我的计划是遍历每一行并比较商店。
- 首先比较 a.name = b.name AND a.street = b.street。匹配时,商店被删除。
- 然后我将对名称和街道进行 Levenshtein 比较。在这里,我可能必须手动查看结果以确定它是否重复。
有没有人有这种数据比较的经验?
更新
感谢您的好答案。
将用于比较的字段是:
- 姓名
- 街道地址
- 邮政编码
- 城市
- 国家
我在想一些事情:
选择 name = Lavenshtein 和 country = country 的行。
这样我只需要处理一个小列表。
然后我可以开始更彻底地比较姓名和地址。
algorithm - 带有时间戳的编辑/列文斯坦距离 - 具有相似(最小)成本的不同路径
我正在使用Edit/Levenstein 距离来测量单词之间的相似性。与最简单的实现不同,我的信件有时间戳,比如说样本编号 N=0,1,2,...
我面临的问题是我可以沿着成本矩阵获得不同的路径,这些路径以相同的(最小)成本结尾,并且这些不同的路径与不同的目标字符串相关联。例如,如果我测量源字符串aa
和目标字符串之间的距离bab
,并假设源字符串从时间戳 N=0 开始,那么我有 2 条路径,成本相同为 2(一个加法和一个替换):
b
在 N=-1 处添加,保持第一个a
不变,并将第二个替换为a
ab
。- 用 a代替第
a
一个b
,保持第二个不变a
,并b
在 N=2 处添加。
在时间线上对齐,这两个结果是不同的:
我需要知道什么时候会发生这种情况,所以我可以根据一些标准在两个可能的目标之间进行选择。除了沿途跟踪路径并跟踪所有可能导致成本最小的路径之外,还有其他方法吗?
我考虑过使用动态时间扭曲,因为时间线首先是模型的一部分,但似乎由于成本矩阵被初始化为无穷大(除了 [0,0] 条目),第一步将始终将目标的第一帧与源的第一帧进行匹配,从而导致目标与源的时间戳相同。无论如何,使用 DTW,我仍然必须跟踪所有导致相同最小成本的路径。
欢迎任何帮助或见解。