问题标签 [edit-distance]

考虑在此 Wiki 页面上建议的 LD 距离计算算法的C#实现。

如果已经超过某个（预定义的）距离阈值，我想扩展它以中止计算过程的能力。

这个概念优化方法是由 Alex Martelli 在这个线程上提出的。

问题是：如何在建议的 C# 解决方案上实现此解决方案？{ 旁注：函数应该返回找到的最大距离，直到它返回。}

非常感谢。

我有一个问题，我想匹配数据库中与给定字符串具有一定编辑距离的所有字符串。

我的想法是生成一个正则表达式，该表达式将匹配所有具有与 string 编辑距离d的字符串s。

因此，例如，我想为以下形式生成正则r表达式：d = 1等等。但我不确定这是否非常有效，或者是否已经有一些很好的算法来解决这个问题？我想考虑在编辑距离中甚至字符交换。所以也应该是一部分。我想在 PHP 中实现它，然后进行 SQL 查询：.s = 'abc'r = 'abc|.abc|.bc|a.c|ab.|abc.''acb'rSELECT * FROM table WHERE name RLIKE TheRegularExpression

这是一个很好的方法吗？或者你会推荐什么？

我正在编写一个代码来计算两个给定字符串 t 和 s 的编辑距离，其中 m = strlen(t) 和 n = strlen(s)，并且代码应该只使用 O(m) 中的内存。此外，计算两个大约 50 个字符的字符串的时间不应超过 4 秒。我编写的代码满足后者，但我不确定第一个，所以如果你能检查它是否使用不超过 O(m) 的内存，我会很高兴。如果没有，听到一些提示如何做到这一点也很有用。谢谢。

例如，输入可以是["div","table","tr","td","a"]and ["table","tr","td","a","strong"]，对应的输出应该是2。

我的问题是当任一输入列表的大小太大时，例如，列表中有 40 个字符串时，程序会产生can't reserve enough space for object heap错误。JVM 参数是-Xms512m -Xmx512m. 我的代码可能需要这么多堆空间吗？还是由于我的代码中的逻辑错误？

编辑：无论是否克隆列表，这种递归方法似乎都不起作用。有人可以帮助估计为我工作所需的总堆内存吗？我想这会令人震惊。无论如何，我想我必须改用动态编程方法。

我看过很多代码来解决这个问题，但我不明白为什么他们使用矩阵来表示两个单词之间的距离。谁能给我解释一下？

这是我找到的示例代码：

我正在研究使用编辑距离算法在名称数据库中实现模糊搜索。

我发现了一种数据结构，据说可以通过分而治之的方法帮助加快这一进程——Burkhard-Keller Trees。问题是我找不到关于这种特定类型树的太多信息。

如果我用任意节点填充我的 BK-tree，我有多大可能遇到平衡问题？

如果我可能或可能对 BK-Trees 有平衡问题，有没有办法在这种树建成后平衡它？

正确平衡 BK-tree 的算法是什么样的？

到目前为止我的想法：

似乎子节点在距离上是不同的，所以我不能简单地旋转树中的给定节点而不重新校准它下面的整个树。但是，如果我能找到一个最佳的新根节点，这可能正是我应该做的。不过，我不确定如何找到最佳的新根节点。

我还将尝试一些方法，看看是否可以通过从一棵空树开始并插入预分布数据来获得一个相当平衡的树。

• 从按字母顺序排列的列表开始，然后从中间排队。（我不确定这是一个好主意，因为按字母排序与按编辑距离排序不同）。
• 完全洗牌的数据。（这在很大程度上依赖于运气来偶然选择一个“不那么糟糕”的根。它可能会严重失败并且可能在概率上保证是次优的）。
• 从列表中的任意单词开始，然后按照与该项目的编辑距离对其余项目进行排序。然后从中间排队。（我觉得这会很昂贵，并且仍然做得很差，因为它不会计算所有单词之间的度量空间连接 - 只是每个单词和一个参考单词）。
• 使用任何方法构建初始树，将其展平（基本上就像前序遍历），然后从中间排队等待新树。（这也会很昂贵，而且我认为它可能仍然表现不佳，因为它不会提前计算所有单词之间的度量空间连接，并且只会得到不同且仍然不均匀的分布）。
• 按名称频率排序，首先插入最流行的，抛弃平衡树的概念。（这可能是最有意义的，因为我的数据分布不均，而且我不会输入纯随机词）。

仅供参考，我目前并不担心名称同义词问题（Bill vs William）。我会分开处理，我认为完全不同的策略会适用。

我有一个很长（> 1000 项）的单词列表，我想从中删除与其他单词“太相似”的单词，直到其余单词都“显着不同”。例如，没有两个词在编辑距离 D 内。

我不需要一个独特的解决方案，它不必是完全最优的，但它应该相当快（在 Python 中）并且不会丢弃太多条目。

我怎样才能做到这一点？谢谢。

编辑：要清楚，我可以用谷歌搜索一个测量编辑距离的python例程。问题是如何有效地做到这一点，并且也许以某种方式找到 D 的“自然”值。也许通过从所有单词中构造某种 trie 然后修剪？

我整天都在处理一个我似乎无法解决的问题。任务是证明编辑距离的递归实现具有时间复杂度 Ω(2 ^max(n,m) )，其中 n & m 是被测量单词的长度。

该实现类似于这个小的python示例

来自：http ://www.clear.rice.edu/comp130/12spring/editdist/

我尝试为不同的短词绘制递归深度的树，但我找不到树深度和复杂性之间的联系。

我计算的递归公式

但我不知道如何进行，因为每次通话都会导致 3 个新通话，因为长度没有达到 0。

对于如何继续证明下限复杂度为 Ω(2 ^max(n,m) ) 的任何提示，我将不胜感激。

现在我正在制作一个包含三个观察值的折线图。因此，存在三个 x 轴刻度。

我想手动减少 x 轴刻度之间的距离，并基本上强制观察彼此更接近。换句话说，我想减少 x 轴刻度之间的距离。

我的数据：

我的代码：

I need to cluster a large number of strings using ELKI based on the Edit Distance / Levenshtein Distance. Since the data set is too large, I'd like to avoid file based precomputed distance matrices. How can I

(a) load string data in ELKI from a file (only "Labels")?

(b) implement a distance function accessing the labels (extend AbstractDBIDDistanceFunction, but how to get the labels?)

Some code snippets or example input files would be helpful.