标签: edit-distance

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

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

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

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

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

到目前为止我的想法:

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

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

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

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

我试图计算字符串对集合的编辑距离,以找到最接近的匹配.我目前的问题是集合非常大(大约25000个项目),所以我不得不将集合缩小到相似长度的字符串,但仍然只会将其缩小到几千个字符串,这仍然非常慢.是否存在允许快速查找类似字符串的数据结构,还是有另一种方法可以解决此问题？

我正在尝试编写一个拼写检查模块.

它加载一个文本,从16 mb文件创建一个字典,然后检查遇到的单词是否与字典中的单词相似(类似=最多两个字符),如果是,则将其从字典更改为表单.

现在我正在使用Levenshtein距离算法,处理50个字的设置需要3分钟......

我很确定必须有更快的解决方案.Profiler告诉我,我的应用程序花费了超过80%的时间在Levenshtein Distance功能.

有没有更好的解决方案/算法？

这是我使用的算法版本的实现:

def levenshteinDistance(s1, s2):
    l_s1 = len(s1)
    l_s2 = len(s2)
    d = [[a for a in genM(x, l_s2 + 1)] for x in xrange(l_s1 + 1)]
    for i in xrange(1, l_s1 + 1):
        for j in xrange(1, l_s2 + 1):
            d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + decide_of_equality(s1[i - 1],s2[j - 1]))
    return d[l_s1][l_s2]

现在我正在制作一个包含三个观测值的折线图.因此,有三个x轴刻度.

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

我的数据:

structure(list(Period = c("January 1997 - August 2003", "September 2003 - Jun 2005", 
"Jul 2005 - Dec 2009", "January 1997 - August 2003", "September 2003 - Jun 2005", 
"Jul 2005 - Dec 2009"), Time.Period = structure(c(1L, 3L, 2L, 
1L, 3L, 2L), .Label = c("Jan 1997 - Aug 2003", "Jul 2005 - Dec 2009", 
"Sep 2003 - Jun 2005"), class = "factor"), Variable = structure(c(2L, 
2L, 2L, 1L, 1L, 1L), .Label = c("Significant", "Zscore"), class = "factor"), 
Score = …

我正在寻找一种方法来计算任意两个提交内容之间的良好编辑距离。

我发现的最好的方法是从输出中得出一些东西

git diff <commit-ish> <commit-ish> --numstat

...但是我使用这种方法所能想到的任何东西都将是编辑距离的一个非常粗略的代理。

有更好的吗？

在 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 ]。我错了，还是有人提出了创造性的查询来解决此限制？

我正在尝试基于自定义距离函数为字​​符串创建距离矩阵(用于聚类).我在6000字的列表上运行代码,并且自上次90分钟后它仍在运行.我有8 GB RAM和Intel-i5,所以问题只在于代码.这是我的代码:

library(stringdist)
#Calculate distance between two monograms/bigrams
stringdist2 <- function(word1, word2)
{
    #for bigrams - phrases with two words
    if (grepl(" ",word1)==TRUE) {
        #"Hello World" and "World Hello" are not so different for me
        d=min(stringdist(word1, word2),
        stringdist(word1, gsub(word2, 
                          pattern = "(.*) (.*)", 
                          repl="\\2,\\1")))
    }
    #for monograms(words)
    else{
        #add penalty of 5 points if first character is not same
        #brave and crave are more different than brave and bravery
        d=ifelse(substr(word1,1,1)==substr(word2,1,1),
                            stringdist(word1,word2),
                            stringdist(word1,word2)+5)
    }   
    d
}
#create distance matrix
stringdistmat2 …

我正在计算包​​含最多6个值的序列之间的Levenshtein距离。这些值的顺序不应影响距离。

如何将其实现为迭代或递归算法？

例：

# Currently 
>>> LDistance('dog', 'god')
2

# Sorted
>>> LDistance('dgo', 'dgo')
0

# Proposed
>>> newLDistance('dog', 'god')
0

'dog'和'god'具有完全相同的字母，在手之前对字符串进行排序将返回所需的结果。但是，这并非始终有效：

# Currently 
>>> LDistance('doge', 'gold')
3

# Sorted
>>> LDistance('dego', 'dglo')
2

# Proposed
>>> newLDistance('doge', 'gold')
1

“ doge”和“ gold”具有3/4个匹配字母，因此应返回距离1。这是我当前的递归代码：

def mLD(s, t):
    memo = {}
    def ld(s, t):
        if not s: return len(t)
        if not t: return len(s)
        if s[0] == t[0]: return ld(s[1:], t[1:])
        if (s, t) not in memo:
            l1 = ld(s, t[1:]) …

我有一个长度为 1000 的字符串 S 和一个长度为 100 的查询字符串 Q。我想计算查询字符串 Q 与长度为 100 的字符串 S 的每个子字符串的编辑距离。一种简单的方法是动态计算编辑距离每个子串独立，即edDist(q,s[0:100]), edDist(q,s[1:101]), edDist(q,s[2:102])....... edDist(q,s[900:1000])。

def edDist(x, y):
""" Calculate edit distance between sequences x and y using
    matrix dynamic programming.  Return distance. """
D = zeros((len(x)+1, len(y)+1), dtype=int)
D[0, 1:] = range(1, len(y)+1)
D[1:, 0] = range(1, len(x)+1)
for i in range(1, len(x)+1):
    for j in range(1, len(y)+1):
        delt = 1 if x[i-1] != y[j-1] else 0
        D[i, j] = min(D[i-1, j-1]+delt, …

如果两个字符串之间的Levenshtein距离，s并且t由下式给出L(s,t)，

以下两种不同的规范化方案对结果启发式的影响有何不同？

1. L(s,t) / [length(s) + length(t)]

2. L(s,t) / max[length(s), length(t)]

3. (L(s,t)*2) / [length(s) + length(t)]

我注意到Levenshtein距离Wikipedia页面建议使用规范化方法2，但没有提及方法1。这两种方法是否同样有效？只是想知道是否有数学上的理由来使用一种方法。

另外，方法1和方法3有什么区别？

用下面的例子：

s = "Hi, my name is"

t = "Hello, my name is"

L(s,t) = 4

length(s) = 14 （包括空格）

length(t) = 17 （包括空格）

给出以上三种归一化算法的Levenshtein距离为：

1. 4 /（14 + 17）= 0.129

2. 4 /（17）= 0.235

3. （4 * 2）/（14 + 17）= 0.258