问题标签 [edit-distance]

问题： 一些 R 包具有用于计算两个字符串相似度的 Levenshtein 距离实现，例如http://finzi.psych.upenn.edu/R/library/RecordLinkage/html/strcmp.html。计算的距离可以很容易地针对字符串长度进行归一化，例如通过将 Levenshtein 距离除以所涉及的最长字符串的长度或将其除以两个字符串的长度的平均值。然而，对于语言学中的某些应用（例如方言学和接受性多语言研究），建议将原始 Levenshtein 距离标准化为最长最小成本对齐的长度（Heeringa，2004：130-132）。从感知语言的角度来看，这往往会产生更有意义的距离度量。

示例： 德语字符串“tsYklUs”（Zyklus = cycle）可以在 7 槽对齐中转换成它的瑞典同源词“sYkEl”（cyckel = (bi)cycle），其中两个插入 (I) 和两个替换 (S)总转换成本为 4。归一化 Levenshtein 距离：4/7

（一个）

也可以将字符串转换为具有 3 个插入 (I) 和 1 个删除 (D) 的 8 槽对齐方式，总对齐成本也为 4。归一化 Levenshtein 距离：4/8

(乙)

后一种对齐在语言上更有意义，因为它将 [l] 音素彼此对齐，而不是与 [E] 和 [U] 元音对齐。

问题： 有谁知道任何 R 函数可以让我标准化 Levenshtein 距离以获得最长的最低成本对齐，而不是正确的字符串长度？感谢您的输入！

参考： WJ Heeringa (2004)，使用 Levenshtein 距离测量方言发音差异。博士论文，格罗宁根大学。http://www.let.rug.nl/~heeringa/dialectology/thesis/

编辑 - 解决方案：我想我想出了一个解决方案。该adist函数可以返回对齐方式，并且似乎默认为最长的低成本对齐方式。拿上面的例子来说，这里是与sykel到tsyklus相关的对齐：

为了按照 Heeeringa (2004) 的建议计算长度归一化距离，我们可以编写一个适度的函数：

对于上面的示例，这将返回

此函数还返回 Heeeringa (2004: 131) 示例的正确归一化距离：

比较几对字符串：

我正在寻找一种用于计算 Levenshtein 编辑距离的算法，该算法还支持在 C# 中实现的两个相邻字母被转置的情况。

例如单词“animals”和“ainmals”：在字母“n”和“i”之间切换不会被计分为两个替换——这会产生很大的距离——而是会被计为两个字母的转置——距离更小——

到目前为止我在搜索中所达到的

• 计算 Lichtenstein 距离 ，但不包含替换
• 这个问题

我的问题类似于通过有效单词将一个单词转换为另一个单词的算法

但有一个主要区别。我有一个固定的词说“詹姆斯”和不同的字典作为 i/p。当然，我现在不能预处理字典。

所以我必须找到用不同的字典作为输入处理“JAMES”到“JOHNY”的最低成本。

无论如何我可以预处理“JAMES”这个词，以便我需要在运行时执行最少数量的编辑距离计算？你们有什么建议？

我正在尝试根据 2 个字符串之间的比较来分配相似度分数。R中是否有相同的功能。我知道SAS中有这样一个名为SPEDIS的功能。请让我知道R中是否有这样的功能。

编辑距离算法给出了两个字符串之间距离的度量。

问题：这些措施中的哪一个与检测两个实际上相同的不同人名最相关？（由于拼写错误而不同）。诀窍是它应该尽量减少误报。例子：

奥巴马奥巴马 => 可能应该被合并

Obama Ibama => 不应合并。

这只是一个过于简单的例子。他们的程序员和计算机科学家是否更详细地解决了这个问题？

这是一个理论问题，所以我将使用伪代码。

我有一个需要转换为另一个列表的对象列表。

我实现了 Levenshtein 算法，效果很好，但我需要保留对象，而不是创建新对象。我可以暴力破解它，但我宁愿找到一种非 O(n*m) 的方法来做到这一点。

[obj1,obj2,obj3] -> [obj1,obj4,obj5,obj2,obj6,obj3]

obj1,obj2,obj3 必须是同一个对象，其余都是新创建的对象。

有人知道这个的好算法吗？

我们正在开发一个系统，使用 UTF-8、UTF-16 和 UTF-32 Unicode 字符标准对 50 多种国际语言进行模糊匹配。到目前为止，我们已经能够使用 Levenshtein 距离来检测德语 Unicode 扩展字符单词的拼写错误。

我们想扩展这个系统来处理以 Unicode 表示的普通话表意文字。我们将如何在相似的汉字之间进行 Levenshtein 距离计算？

我有两组字母“AGTE”的字符串A和B，我想找到一些比较它们的方法，看看它们在统计上是否相似。第一组 A 是真实世界的观察，B 是预测。每组有 400 人左右

我还想以某种方式将这些可视化，真正用于演示目的。你有什么想法我可以做到这一点吗？

please note that it doesn't require to really calculate Levenshtein edit distance. just check it's 1 or not.

The signature of the method may look like this:

for example: 1. "abc" and "ab" return true 2. "abc" and "aebc" return true 3. "abc" and "a" return false.

I've tried recursive approve, but it it not efficient.

update: got answer from a friend:

我们都在 Google 中看到，如果我们输入查询并打错字，Google 会建议使用更合理的查询版本（这通常是正确的）。现在他们是怎么做到的？我能想到的一种可能方法是找出与给定字符串编辑距离为 1 的所有其他字符串，如果其中任何一个返回具有更高值“搜索”属性的字符串（可能来自后端数据库，每个索引查询词都有一个权重，基于该词在查询中出现的频率）而不是给定的字符串，建议使用该字符串。如果没有找到，则搜索编辑距离为 2 的字符串，依此类推，直到在 5 处，SE 确定该字符串可能是用户正在查找的字符串，并返回相应的搜索结果。

现在有可能在给定字符串的给定编辑距离处找到字符串吗？这个过程的效率如何？有什么很酷的算法可以做到这一点吗？