标签: edit-distance

我已经看到很多代码要解决这个问题,但我无法理解为什么他们使用矩阵来表示两个单词之间的距离.有人可以向我解释一下吗？

这是我找到的示例代码:

public static int minDistance(String word1, String word2)
{
    int l1 = word1.length(), l2 = word2.length();

    int[][] d = new int[l1 + 1][l2 + 1];

    // the edit distance between an empty string and the prefixes of
    // word2
    for (int i = 0; i < l2 + 1; i++) {
        d[0][i] = i;
    }

    // the edit distance between an empty string and the prefixes of
    // word1
    for (int j = 0; j < l1 + 1; …

我正在使用字符串编辑距离 (Levenshtein-distance) 来比较眼动追踪实验中的扫描路径。（现在我stringdist在 R 中使用这个包）

基本上，字符串的字母指的是 6x4 矩阵中的（凝视）位置。矩阵配置如下：

     [,1] [,2] [,3] [,4]
[1,]  'a'  'g'  'm'  's' 
[2,]  'b'  'h'  'n'  't'
[3,]  'c'  'i'  'o'  'u'
[4,]  'd'  'j'  'p'  'v'
[5,]  'e'  'k'  'q'  'w'
[6,]  'f'  'l'  'r'  'x'

如果我使用的基本Levenshtein距离比较字符串，进行比较a，并g在一个字符串给出了相同的估计为comparicona和x。

例如：

'abc' compared to 'agc' -> 1
'abc' compared to 'axc' -> 1

这意味着字符串同样（不同）相似

我希望能够以在矩阵中包含邻接的方式对字符串比较进行权重。例如之间的距离a和x应该那么之间加权为较大的a和g。

一种方法是计算矩阵中从一个字母到另一个字母的“步行”（水平和垂直步骤），然后除以最大“步行”距离（即从a到 …

我阅读了很多关于计算图形编辑距离(GED)或其他图形相似性度量(例如http://goo.gl/gmDMgA)的理论,但我没有找到完成这种计算的工具.

是否有编程库或软件可以计算图形编辑距离,或者,在两个图形之间再次计算任何其他图形相似性度量？

问题:我知道琐碎的编辑距离DP公式和O(mn)中的2个大小为n和m的字符串的计算.但我最近才知道,如果我们只需要计算编辑距离f的最小值并且它是有界| f | <= s,那么我们可以用O(min(m,n)+ s ^ 2)计算它或者O(s*min(m,n))[维基百科]时间.

如果这是基于DP或解释算法,请解释它背后的dp配方.

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

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

提前致谢.

Levenshtein距离是用于测量两个序列之间差异的字符串度量.Wagner-Fischer算法是一种动态编程算法,用于计算两个字符串之间的编辑距离.

两者都使用矩阵,我没有看到差异？这种差异是回溯还是由于一个是"文学"而另一个是编程这一事实没有进一步的区别？

另外,我只是写一篇论文,我不知道如何划分它 - 我是否应首先首先解释Levenshtein距离,然后再解释Wagner-Fisher算法或两者兼而有之？我在这里有点困惑.

我正在关注 networkx 文档 ( 1 )，我想为成本函数（例如node_del_cost和node_ins_cost）设置不同的惩罚。比方说，我想通过三点惩罚删除/插入节点。

到目前为止，我已经创建了两个无向图，它们因标记节点 C（更新代码）而异。

import networkx as nx

G=nx.Graph()
G.add_nodes_from([("A", {'label':'CDKN1A'}), ("B", {'label':'CUL4A'}), 
    ("C", {'label':'RB1'})])

G.add_edges_from([("A","B"), ("A","C")])

H=nx.Graph()
H.add_nodes_from([("A", {'label':'CDKN1A'}), ("B", {'label':'CUL4A'}),
    ("C", {'label':'AKT'})])
H.add_edges_from([("A","B"), ("A","C")])

# arguments
# node_match – a function that returns True if node n1 in G1 and n2 in G2 should be considered equal during matching.
# ignored if node_subst_cost is specified
def node_match(node1, node2):
    return node1['label']==node2['label']

# node_subst_cost - a function that returns the costs of …

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

实现与这个小python示例相当

def lev(a, b):
    if("" == a):
       return len(b)   # returns if a is an empty string
    if("" == b):
        return len(a)   # returns if b is an empty string
    return min(lev(a[:-1], b[:-1])+(a[-1] != b[-1]), lev(a[:-1], b)+1, lev(a, b[:-1])+1)

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

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

来自我的计算的递归公式

m = length of word1
n = length of word2
T(m,n) = T(m-1,n-1) + 1 + T(m-1,n) + T(m,n-1)
With the base cases:
T(0,n) = n
T(m,0) …

我正在尝试理解用于找到字符串之间距离的Wagner-Fischer算法.我正在通过以下链接查看它的伪代码:http://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm

int EditDistance(char s[1..m], char t[1..n])
   // For all i and j, d[i,j] will hold the Levenshtein distance between
   // the first i characters of s and the first j characters of t.
   // Note that d has (m+1)  x(n+1) values.
   let d be a 2-d array of int with dimensions [0..m, 0..n]

   for i in [0..m]
     d[i, 0] ? i // the distance of any first string to an empty second string
   for j in [0..n] …

我正在尝试比较两个数组之间的编辑距离。我尝试过使用 Text:Levenshtein。

#!/usr/bin/perl -w
use strict;
use Text::Levenshtein qw(distance);

my @words = qw(four foo bar);
my @list = qw(foo fear);
my @distances = distance(@list, @words);

print "@distances\n";
#results: 3 2 0 3

然而，我希望结果如下所示：

2 0 3
2 3 2

通过 @words 数组获取 @list 的第一个元素，并对 @list 的其余元素执行相同的操作。我计划将其升级为更大的阵列。

我有一个在 C++ 中计算字符串编辑距离的函数：

#include <string>
#include <vector>
#include <algorithm>

size_t sed_diff(const std::string & a, const std::string & b) {

    std::vector<size_t> cp(b.length() + 1);
    std::vector<size_t> cc(b.length() + 1);

    // Edit distance on postorder traversal.
    for (int j = 0; j <= b.length(); ++j) {
        cp[j] = j;
    }
    for (int i = 1; i <= a.length(); ++i) {
        cc[0] = i;
        for (int j = 1; j <= b.length(); ++j) {
            unsigned int c1 = a[i - 1];
            unsigned int c2 …