问题标签 [edit-distance]

我带着另一个冗长的问题回来了。在尝试了许多基于 Python 的 Damerau-Levenshtein 编辑距离实现后，我终于找到了下面列出的editdistance_reference(). 它似乎提供了正确的结果，并且似乎有一个有效的实施。

所以我开始着手将代码转换为 Cython。在我的测试数据中，参考方法能够提供 11,000 次比较的结果（对于 12 个字母长的词对），而 Cythonized 方法每秒进行超过 200,000 次比较。可悲的是，结果不正确：当您查看thisrow 我打印出来进行调试的变量时，无论我向其输入什么数据，我的版本都充满了变量，而参考输出显示了另一张图片。例如，测试'helo'产生'world' 以下输出（ED标记我的函数，EDR是正确工作的参考）：

来自editdistance()：

来自editdistance_reference()：

我一定很愚蠢，因为错误可能是那些非常明显的事情之一。但我似乎找不到它。

还有第二个问题：三个数组、、 和malloc的 i 空间，然后它们以循环方式交换。当我尝试等等时，我得到一条 glibc 抱怨的行。我用谷歌搜索过；会不会是指针交换业务让 glibc 有点头晕，从而无法正确释放内存？twoagooneagothisrowfree( twoago )double free or corruption

下面我首先列出setup.py进行编译所需的内容（/path/to/python3.1 ./setup.py build_ext --inplace），然后是适当的编辑距离代码，因此有兴趣的人会发现它更容易复制。

还有一件事：这是用 Python3.1 运行的；一件有趣的事情是，在*.pyx文件内部我们确实有裸 unicode 字符串，但print它仍然是一个语句，而不是一个函数。

是的，我知道这里有很多代码要粘贴，但问题是，当你把它剪得太多时，代码根本无法运行。我相信除了editdistance()正常工作之外的所有方法，但请随时指出您发现的任何问题。

setup.py：

cython_dameraulevenshtein.pyx（一直滚动到最后，看看有趣的东西）：

编辑我还将此文本发布到pastebin和 Cython 列表。

我有一个数据库，它在同一个表中有非常相似的行。这些行是相似的，因为它们具有几乎相等的列值。我需要将这些相应的行整合到一行中。

例如，应该集成这两个用户（u1 和 u2）：

我正在考虑使用一些编辑距离和词干技术。其他算法和技术建议？有什么有用的库可以使用（最好是 Python 或 Java）？

有没有一种算法可以让你找到两个句子之间的词级编辑距离？例如，“A Big Fat Dog”和“The Big House with the Fat Dog”有 1 个替代品，3 个插入

我将如何显示单词之间的详细距离。例如，程序的输出可能是：

Levenshtein 距离不能满足我的需求（我认为）。

我遇到了这种编辑距离问题的变体：

找到从一个词到另一个词的最短路径，例如storm->power，使用isValidWord()函数验证每个中间词。没有其他对单词字典的访问权限，因此无法构建图形。

我试图弄清楚这一点，但它本身似乎不是与距离相关的问题。也许使用简单的递归？但是，你怎么知道你正朝着正确的方向前进呢？

其他人觉得这很有趣吗？期待一些帮助，谢谢！

我已经阅读了有关计算两个不同单词之间距离的 Levenshtein distance 。

我有一个源字符串，我必须将它与所有 10,000 个目标词匹配。应该返回最接近的单词。

问题是我已经给出了 10,000 个目标词的列表，输入的源词也很庞大......那么在这里应用什么最短和有效的算法。每个组合（蛮力逻辑）的每个 n 的 Levenshtein 距离计算将非常耗时。

任何提示或想法都是最受欢迎的。

My company's cat-herding application tracks a convoy of cats. Periodically, it needs to compare previousOrder to currentOrder (each is an ArrayList<Cat>) and notify the cat-wranglers of any changes.

Each cat is unique and can only appear once in each list (or not at all). Most of the time, the previousOrder and currentOrder lists have the same contents, in the same order, but any of the following can happen (from more frequent to less frequent):

1. The order of cats is scrambled completely
2. Cats individually move up or down in the list
3. New cats join, at a specific point in the convoy
4. Cats leave the convoy

This appears like an edit distance problem to me. Ideally, I am looking for an algorithm that determines the steps required to make previousOrder match currentOrder:

• MOVE Fluffy to position 12
• INSERT Snuggles at position 37
• DELETE Mr. Chubbs
• etc.

The algorithm should also recognize scenario #1, in which case the new order is communicated in its entirety.

What's the best approach for this?

(This post and that post pose similar questions, but they are both dealing with sorted lists. Mine are ordered, but unsorted.)

EDIT

The Levenshtein algorithm is a great suggestion, but I'm concerned about the time/space requirement of creating a matrix. My main goal is to determine and communicate the changes as quickly as possible. Something that is faster than finding the additions and sending message along the lines of "Here are the new cats, and here is the current order."

我正在使用大型企业数据库。

我希望能够比较两个企业名称的相似性，看看它们是否可能是重复的。

以下是应测试为很可能重复的企业名称列表，有什么好的方法可以解决这个问题？

我有两个长度为 n 和 m 的序列。每个点都是 (x,y) 形式的点序列，表示图像中的曲线。我需要找出这些序列有多么不同（或相似）的事实是

1. 一个序列可能比另一个序列长（即，一个序列可以是另一个序列的一半或四分之一，但如果它们追踪大致相同的曲线，它们是相同的）

2. 这些序列可能是相反的方向（即，序列 1 从左到右，而序列 2 从右到左）

   我研究了一些差异估计，如 Levenshtein 以及蛋白质折叠的结构相似性匹配中的编辑距离，但它们似乎都没有奏效。我可以编写自己的蛮力方法，但我想知道是否有更好的方法。

谢谢。

问题：需要两个字符串之间的 LCS 长度。字符串的大小最多为 100 个字符。字母表是通常的 DNA 之一，4 个字符“ACGT”。动态方法不够快。

我的问题是我正在处理很多对（据我所见，数量为数亿）。我相信我已将 LCS_length 函数的调用降至最低，因此使我的程序运行得更快的唯一另一种方法是使用更高效的 LCS_Length 函数。

我开始采用通常的动态编程方法。这给出了正确的答案，并有望正确实施。

那应该是 O(mn)（希望如此）。

然后为了寻找速度，我发现这篇文章Longest Common Subsequence 给出了Myers 的O(ND) 论文 。我尝试了将 LCS 与最短编辑脚本 (SES) 相关联的方法。他们给出的关系是 D = M + N - 2L，其中 D 是 SES 的长度，M 和 N 是两个字符串的长度，L 是 LCS 的长度。但这在我的实现中并不总是正确的。我给出了我的实现（我认为这是正确的）：

主要有例子。例如。“tomato”和“potato”（不要评论），LCS 长度为 4。实现发现它是 5，因为 SES（代码中的 D）出现为 2 而不是我期望的 4（删除“t”，插入“p”，删除“m”，插入“t”）。我倾向于认为 O(ND) 算法也可能计算替换，但我不确定这一点。

欢迎任何可实施的方法（我没有高超的编程技能）。（例如，如果有人知道如何利用小字母表）。

编辑：我认为最重要的是说，我在任何时候都在任何两个字符串之间使用 LCS 函数。因此，与其他几百万相比，它不仅是字符串说 s1。可能是 s200 和 s1000，然后是 s0 和 s10000，然后是 250 和 s100000。也不太可能跟踪最常用的字符串。我要求 LCS 长度不是近似值，因为我正在实现一个近似算法并且我不想添加额外的错误。

编辑：刚刚跑了callgrind。对于 10000 个字符串的输入，对于不同的字符串对，我似乎调用了 lcs 函数大约 50,000,000 次。（10000 个字符串是我想要运行的最低值，最大值是 100 万个（如果可行的话））。