问题标签 [edit-distance]

问题：我知道两个大小分别为 n 和 m 的字符串在 O(mn) 中的微不足道的编辑距离 DP 公式和计算。但是我最近才知道，如果我们只需要计算编辑距离f的最小值并且它是有界的|f|<=s，那么我们可以在O(min(m,n) + s^2)中计算它或 O(s*min(m,n)) [wikipedia] 时间。

如果这是基于 DP 的，请解释其背后的 dp 公式或解释算法。

查看链接improved algorithm部分 ： http ://en.wikipedia.org/wiki/Edit_distance 。

关于改进 UKKONEN 算法的另一个链接http://www.berghel.net/publications/asm/asm.php

提前致谢。

我正在尝试解决编辑距离问题。我一直在使用的代码如下。

这是一种DP方法。问题在于它使用二维数组，我们无法使用上述方法解决大字符串的问题。例如：字符串长度 > 100000。

那么有没有办法修改这个算法来克服这个困难呢？

注意：上面的代码将准确地解决小字符串的编辑距离问题。（长度小于 1000 或接近）

正如您在代码中看到的，它使用 Java 2D 数组 "dp[][]" 。所以我们不能为大的行和列初始化一个二维数组。

例如：如果我需要检查 2 个长度超过 100000 的字符串

以上将是

所以它会给出一个stackOverflow错误。

所以上面的程序只适用于小长度的字符串。我要问的是，有没有办法在java中有效地解决大字符串（长度> 100000）的这个问题。

PS如果增补删减权重不同。比有什么算法可以帮助我。

或者，如果添加/删除和替换的权重不同，Wagner-Fischer 算法需要进行哪些修改以最小化编辑距离？

我正在解决众所周知的编辑距离动态规划问题。实际上，问题是给定两个字符串 string1 和 string2，并给出删除、插入和替换字符的成本，我必须以最低成本将 string1 转换为 string2。对于 DP I必须使用二维数组。对于小字符串（大小<=10000），我的代码可以正常工作，但对于较大的输入（大小>=100000），编译器会说“数组大小太大”。如果必须使用动态编程解决问题（对于输入大小 = 100000），请告诉我应该如何处理此错误。这是我的代码。

我正在开发一个项目，该项目在其数据库中包含大量姓名和地址。名称如“John K Smith”和“Joe Smith”，地址为“20 Theroad avenue”或“1345 Myplace st”。

在这个项目中，一旦用户 X 进入网站，他们将输入姓名和地址以及其他详细信息；输入的姓名和地址与数据库中已有的内容进行核对。如果输入的姓名和地址与用户 X 的数据库中存在的姓名和地址足够相似，则授予访问权限。

我需要执行近似的字符串匹配，而不是精确的字符串匹配，以使登录更方便。（我知道这是一场安全音乐会，但也有完全匹配的用户名/密码）。

我正在寻找一种适用于姓名和地址的字符串匹配算法，此外还要考虑首字母缩略词、缩写形式和类似短语，例如“ave”与“avenue”或“mr”与“mr”。或“街道”与“大道”。

到目前为止，我已经研究了编辑距离、jarowinkler、ngram(qgram)、余弦相似度和语音方法。

我认为也许一种具有自定义规范化功能的混合方法（对缩写/类似术语进行字符串替换）是可行的方法，但我还不确定。

这个项目最终应该可以使用其他语言（西班牙语和法语），这可能意味着更多的自定义文本替换。

在找到最合适的算法以高精度匹配名称和地址（误报数量最少）方面，我们将不胜感激。

所以我知道 Levenshtein 距离算法考虑了将字符串 A 更改为字符串 B 所需的最小删除、插入和替换次数。但是，我想知道如何单独跟踪总编辑中的删除次数需要进行更改。我在看这个算法的实现，

因此，为了跟踪删除，我尝试了：

然后增加计数。但是，这似乎不起作用。我还尝试获取两个字符串的大小差异，但在以下情况下失败

这里显然有 1 个删除，但仅仅获得大小的差异不会检测到这一点。

我想知道是否有人知道如何跟踪将字符串 A 更改为字符串 B 的总编辑中涉及的删除数量。

有谁知道只计算替换和插入的编辑距离算法。所以基本上，这将是没有删除的 Levenshtein 距离算法。

在 PSQL（我相信 Redshift 是基于它的）中，有字符串相似函数，如levenshtein/ levenshtein_less_equal[ http://www.postgresql.org/docs/9.1/static/fuzzystrmatch.html ]。这些功能似乎没有进入 Redshift [ http://docs.aws.amazon.com/redshift/latest/dg/String_functions_header.html ]。我错了，还是有人提出创造性的查询来解决这个限制？

我正在寻找两个不同字符串的子字符串；问题如下：

给定两个字符串 x = X1...Xn 和 y = Y1...Ym，找到最长公共子串的长度，以及在索引 i 和 j 中的最大 k 与 XiXi+1...Xi+k -1 = YjYj+1...Yj+k-1。展示如何在 O(m*n) 时间内做到这一点。

有人可以帮我解决这个问题，我已经研究了太久了？我已经尝试过为这个问题做子空间，但最终弄错了。任何帮助将不胜感激！先感谢您！

给定两个位字符串 x 和 y，其中 x 比 y 长，我想计算它们之间的 Levensthein 距离的一种不对称变体。从 x 开始，我想知道将 x 变为 y 所需的最小删除和替换次数。

我可以为此使用通常的 Levensthein 距离，还是我需要以某种方式修改算法？换句话说，对于通常的删除、替换和添加编辑，删除两个字符串之间的长度差异然后再添加一些位是否有益？我怀疑答案是否定的，但我不确定。如果我错了，我确实需要修改 Levenshtein 距离的定义以禁止删除，我该怎么做？

最后，如果我从 y （较短的字符串）开始并且只允许添加和替换，我会直觉地期望我会得到相同的距离。这是正确的吗？我对这些答案有所了解，但我无法证明它们。