标签: edit-distance

我有两个长度为n和m的序列.每个都是形式(x,y)的一系列点,并表示图像中的曲线.我需要找到不同(或类似)这些序列给出的事实

1. 一个序列可能比另一个序列长(即,一个序列可以是另一个序列的一半或四分之一,但如果它们跟踪大致相同的曲线,则它们是相同的)

2. 这些序列可能是相反的方向(即序列1从左到右,而序列2从右到左)

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

谢谢.

我正在尝试创建或找到Levenshtein距离公式的CoffeeScript实现,即编辑距离.这是我到目前为止,任何帮助都将非常感激.

levenshtein = (s1,s2) ->
    n = s1.length
    m = s2.length
    if n < m
        return levenshtein(s2, s1) 
    if not s1 
        return s2.length
    previous_row = [s2.length + 1]
    for c1, i in s1
        current_row = [i + 1]
        for c2, j in s2
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] # is this unnescessary?-> (c1 != c2)
            current_row.push(Math.min(insertions,deletions,substitutions))
        previous_row = current_row
    return previous_row[previous_row.length-1]
#End Levenshetein Function

顺便说一句:我知道这个代码在很多层面都是错误的,我很高兴接受任何建设性的批评.只是想改进,并找出这个公式!

CodeEdit1:修补了Trevor指出的错误,上面的当前代码包括这些更改

更新:我问的问题是 - 我们如何在CoffeeScript中使用Levenshtein？

以下是Levenshtein距离算法的"步骤",以帮助您了解我想要完成的任务. …

可能重复:
计算将一个排列转换为另一个排列所需的交换

我正在寻找一种计算某种字符串距离的算法,其中只允许操作是两个相邻字符的转置.例如:
string1:"mother"
string2:"moterh"
距离:2(首先交换"h"与"e"并获得"motehr"然后"h"与"r"导致"moterh")
我知道Damerau -Levenshtein距离这个问题非常相似,但它需要大量的内存(我希望它可以在高达1 000 000个字符的单词上工作得非常快).我已经写过:

int amo = 0;

for (int i = 0; i < n; i++)
{
    if (fromString[i] == toString[i])
        continue;
    char toWhat = toString[i];
    int where = -1;
    for (int j = i; j < n; j++)
    {
        if (fromString[j] == toWhat)
        {
            where = j;
            break;
        }
    }
    while (where != i)
    {
        char temp = fromString[where];
        fromString[where] = fromString[where - 1];
        fromString[where - 1] = temp;
        where--;
        amo++;
    } …

在R中,我有两个字符向量a和b.

a <- c("abcdefg", "hijklmnop", "qrstuvwxyz")
b <- c("abXdeXg", "hiXklXnoX", "Xrstuvwxyz")

我想要一个函数来计算a的每个元素和b的相应元素之间的字符不匹配.使用上面的例子,这样的函数应该返回c(2,3,1).没有必要对齐字符串.我需要逐个字符地比较每对字符串,并计算每对中的匹配和/或不匹配.R中是否存在任何此类功能？

或者,以另一种方式提问,是否有一个函数给我两个字符串之间的编辑距离,其中唯一允许的操作是替换(忽略插入或删除)？

我有一个充满客户数据的SAP Oracle数据库.在我们的自定义CRM中,使用通配符搜索客户是很常见的.除了SAP标准搜索之外,我们还想对一些类似于输入名称的名称进行模糊文本搜索.目前我们正在使用该UTL_MATCH.EDIT_DISTANCE功能搜索相似的名称.唯一的缺点是不可能使用一些通配符模式.

是否有可能将通配符与UTL_MATCH.EDIT_DISTANCE函数结合使用,或者有不同(甚至更好)的方法吗？

比方说,数据库中有以下名称:

PATRICK NOR
ORVILLE ALEX
OWEN TRISTAN
OKEN TRIST

查询可能看起来像OKEN*IST*两个OWEN TRISTAN并且OKEN TRISTAN应该返回.OKEN将是100%匹配,OWEN更少.

我当前的测试查询看起来像:

SELECT gp.partner, gp.bu_sort1, UTL_MATCH.edit_distance(gp.bu_sort1, ?) as edit_distance, 
      FROM but000 gp
      WHERE UTL_MATCH.edit_distance(gp.bu_sort1, ?) < 4

此查询工作正常,除非*在搜索字符串中使用通配符(这很常见).

我的项目中有一个用例，我需要将key-string 与很多字符串进行相似性比较。如果这个值大于某个阈值，我认为这些字符串与我的“相似” key，并根据该列表，我进行一些进一步的计算/处理。

我一直在探索模糊匹配字符串相似性的东西，它使用edit distance基于“levenshtein、jaro 和 jaro-winkler”相似性的算法。

尽管它们工作得很好，但如果一个字符串是另一个字符串的“缩写”，我希望获得更高的相似度分数。有没有我可以使用的算法/实现。

笔记：

language: python3 
packages explored: fuzzywuzzy, jaro-winkler

例子：

using jaro_winkler similarity:

>>> jaro.jaro_winkler_metric("wtw", "willis tower watson")
0.7473684210526316
>>> jaro.jaro_winkler_metric("wtw", "willistowerwatson")
0.7529411764705883

using levenshtein similarity:

>>> fuzz.ratio("wtw", "willis tower watson")
27
>>> fuzz.ratio("wtw", "willistowerwatson")
30
>>> fuzz.partial_ratio("wtw", "willistowerwatson")
67
>>> fuzz.QRatio("wtw", "willistowerwatson")
30

在这种情况下，如果可能的话，我希望分数更高（>90%）。我也可以接受很少的误报，因为它们不会对我的进一步计算造成太多问题。但是，如果我们匹配 s1 和 s2，使得 s1 完全包含在 s2 中（反之亦然），那么它们的相似度得分应该会高得多。

编辑：我的用例的更多示例

对我来说，空格是多余的。这意味着，wtw被视为“willistowerwatson”和“willis tower watson”的缩写。

另外，stove是“STack OVERflow”或“STandardOVErview”的有效缩写

一种简单的算法是从较小字符串的第一个字符开始，看看它是否存在于较大字符串中。然后检查第二个字符，依此类推，直到条件满足第一个字符串完全包含在第二个字符串中。这对我来说是 100% 匹配。

诸如“willistowerwatson”之类的进一步示例wtwx可以给出例如 80% …

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

我的想法是生成一个正则表达式,匹配所有字符串与编辑距离d到字符串s.

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

是这样做的好方法吗？或者你会推荐什么？

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

我发现了一个数据结构,据说可以通过分而治之的方法来帮助加快速度--Burkhard-Keller Trees.问题是我找不到关于这种特定类型树的非常多的信息.

如果我用任意节点填充我的BK树,我有多大可能有平衡问题？

如果我可能或可能与BK-Trees有平衡问题,有没有办法在构建之后平衡这样一棵树？

算法在适当平衡BK树时会是什么样子？

到目前为止我的想法:

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

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

• 从按字母顺序排序的列表开始,然后从中间排队.(我不确定这是一个好主意,因为按字母顺序排序与编辑距离的排序不同).
• 完全洗牌的数据.(这很大程度上依赖于运气来挑选一个"不那么糟糕"的根源.它可能会严重失败并且可能在概率上保证不是最佳的).
• 从列表中的任意单词开始,按照与该项目的编辑距离对其余项目进行排序.然后从中间排队.(我觉得这将是昂贵的,并且仍然做得很差,因为它不会计算所有单词之间的度量空间连接 - 只是每个单词和单个参考单词).
• 使用任何方法构建初始树,将其展平(基本上类似于预订遍历),并从中间排队以获得新树.(这也将是昂贵的,我认为它可能仍然很差,因为它不会提前计算所有单词之间的度量空间连接,并且将简单地获得不同且仍然不均匀的分布).
• 按名称频率排序,插入最受欢迎的第一个,并抛弃平衡树的概念.(这可能是最有意义的,因为我的数据不是均匀分布的,我不会有纯粹的随机单词进来).

仅供参考,我目前还不担心名称 - 同义词问题(Bill vs William).我将单独处理,我认为完全不同的策略将适用.

我有2个查询:

    query1:????
    query2:??

当我使用python库Levenshtein运行此代码时:

from Levenshtein import distance, hamming, median
lev_edit_dist = distance(query1,query2)
print lev_edit_dist

我得到12的输出.现在的问题是12的值是如何得出的？

因为在笔画方面的差异,肯定超过12.

我有一个问题，我们可以用ed值除以两个字符串的长度来归一化levenshtein编辑距离吗？我之所以这样问是因为，如果我们比较两个长度不相等的字符串，那么两个长度之间的差异也将被计算在内。例如：ed（'has a'，'has a ball'）= 4，而ed（'has a'，'has a ball the round'）=15。如果我们增加字符串的长度，则编辑距离即使它们相似，也会增加。因此，我无法设置一个值，好的编辑距离值应该是多少。