标签: edit-distance

假设您有一个包含10,000个电子邮件地址的列表,并且您希望找到此列表中一些最接近的"邻居" - 定义为与列表中其他电子邮件地址可疑接近的电子邮件地址.

我知道如何计算两个字符串之间的Levenshtein距离(由于这个问题),这将给我一个将一个字符串转换成另一个字符串需要多少操作的分数.

假设我将"可疑地接近另一个电子邮件地址"定义为Levenshtein得分小于N的两个字符串.

除了将每个可能的字符串与列表中的每个其他可能的字符串进行比较之外,是否有更有效的方法来查找分数低于此阈值的字符串对？换句话说,这种类型的问题可以更快地解决O(n^2)吗？

Levenshtein对这个问题的算法选择是不是很差？

本文讨论了使用后缀树来改善匹配时间的近似子串匹配技术.每个答案都针对不同的算法.

1. 近似子字符串匹配尝试在字符串中查找子字符串(模式)P,以T允许最多k不匹配.
2. 要了解如何创建后缀树,请单击此处.但是,某些算法需要额外的预处理.

我邀请人们添加新算法(即使它不完整)并改进答案.

我们正在开发一个系统,使用UTF-8,UTF-16和UTF-32 Unicode字符标准对50多种国际语言进行模糊匹配.到目前为止,我们已经能够使用Levenshtein距离来检测德语Unicode扩展字符单词的拼写错误.

我们希望扩展这个系统来处理用Unicode表示的普通话中文表意文字.我们如何在相似的汉字之间进行Levenshtein距离计算？

问题:需要两个字符串之间的LCS长度.字符串的大小最多为100个字符.字母表是通常的DNA,4个字符"ACGT".动态方法不够快.

我的问题是我正在处理很多对(我看到的数百万的等级).我相信我已经将LCS_length函数的调用减少到最小可能,因此使程序运行得更快的唯一方法是使用更高效的LCS_Length函数.

我已经开始实施通常的动态编程方法.这给出了正确答案,希望能够正确实施.

#define arrayLengthMacro(a) strlen(a) + 1
#define MAX_STRING 101

static int MaxLength(int lengthA, int lengthB);

/* 
 * Then the two strings are compared following a dynamic computing
 * LCS table algorithm. Since we only require the length of the LCS 
 * we can get this rather easily.
 */
int LCS_Length(char *a, char *b)
{
    int lengthA = arrayLengthMacro(a),lengthB = arrayLengthMacro(b), 
        LCS = 0, i, j, maxLength, board[MAX_STRING][MAX_STRING];

        maxLength = MaxLength(lengthA, lengthB);

    //printf("%d %d\n", lengthA, lengthB);
    for (i = …

问题: 一些R包用Levenshtein距离实现来计算两个字符串的相似性,例如http://finzi.psych.upenn.edu/R/library/RecordLinkage/html/strcmp.html.计算的距离可以很容易地对于弦长度进行归一化,例如通过将Levenshtein距离除以所涉及的最长弦的长度或者将其除以两个弦的长度的平均值.然而,对于语言学中的一些应用(例如方言学和接受多语言研究),建议将原始Levenshtein距离标准化为最长最小成本比对的长度(Heeringa,2004:130-132).从感性 - 语言学的角度来看,这往往会产生更有意义的距离测量.

示例: 德语字符串"tsYklUs"(Zyklus = cycle)可以7个插槽对齐转换为瑞典同源"sYkEl"(cyckel =(bi)循环),其中包含两个插入(I)和两个替换(S)总转化成本为4.标准化Levenshtein距离:4/7

(一个)

t--s--Y--k--l--U--s
---s--Y--k--E--l---
===================
I-----------S--S--I = 4

也可以将8个插槽对齐的字符串转换为3个插入(I)和1个删除(D),总的对齐成本也是4.标准化的Levenshtein距离:4/8

(B)

t--s--Y--k-----l--U--S
---s--Y--k--E--l------
======================
I-----------D-----I--I = 4

后者对准更有意义语言,因为它对准[1]彼此-phonemes而不是与[E]和[U]元音.

问题: 有没有人知道任何R函数可以让我将Levenshtein距离标准化为最长的最低成本比对而不是正确的字符串长度？感谢您的输入!

参考文献: WJ Heeringa(2004),使用Levenshtein距离测量方言发音差异.博士论文,格罗宁根大学.http://www.let.rug.nl/~heeringa/dialectology/thesis/

编辑 - 解决方案:我想我找到了一个解决方案.该adist函数可以返回对齐,并且似乎默认为最长的低成本对齐.举个例子,这里是与sykel和tsyklus相关的对齐方式:

> attr(adist("sykel", "tsyklus", counts = TRUE), "trafos")
     [,1]      
[1,] "IMMMDMII"

为了计算Heeringa(2004)推荐的长度标准化距离,我们可以编写一个适度的函数:

normLev.fnc <- function(a, b) {
  drop(adist(a, b) / nchar(attr(adist(a, b, counts = TRUE), "trafos")))
}

对于上面的示例,这将返回

> normLev.fnc("sykel", "tsyklus")
[1] 0.5

此函数还返回Heeringa(2004:131)示例的正确标准化距离:

> normLev.fnc("bine", "bEi")
[1] …

给出2个字符串s和t.我需要找到s编辑距离(Levenshtein距离)中的每个子串t.实际上我需要知道每个i位置在s所有从位置开始的子串的最小编辑距离i.

例如:

t = "ab"    
s = "sdabcb"

我需要得到类似的东西:

{2,1,0,2,2}

说明:

1st position:
distance("ab", "sd") = 4 ( 2*subst )
distance("ab", "sda") = 3( 2*delete + insert )
distance("ab", "sdab") = 2 ( 2 * delete)
distance("ab", "sdabc") = 3 ( 3 * delete)
distance("ab", "sdabcb") = 4 ( 4 * delete)
So, minimum is 2

2nd position:
distance("ab", "da") = 2 (delete + insert)
distance("ab", …

有没有办法计算2个字符串之间的%匹配？

我有一种情况,如果有85%,需要计算2个字符串之间的匹配

匹配然后我将结合2个表,我已经编写了组合2个表的代码

我的示例字符串是:

var str1 = 'i love javascript';
var str2 = 'i love javascripttt';

var matchPer = match(str1,str2); // result might be 80% , 85%, 90% ,95% etc

我最近遇到了这个问题:

Given two strings, return true if they are one edit away from each other,else return false.
An edit is insert/replace/delete a character. 
Ex. {"abc","ab"}->true, {"abc","adc"}->true, {"abc","cab"}->false

解决此问题的一种方法是使用动态编程找到两个字符串之间的编辑距离,并检查它是否为1.这将花费O(N2)时间.有没有办法在线性时间内完成此操作,因为我们只检查它们是否为1编辑？

我在下面写的代码适用于大多数情况,但是对于像{"m",""}这样的情况却失败了

public boolean isOneEditDistance(String s1,String s2){
    if(s1==null || s2==null)
        return true;
    if(s1.equals(s2))
        return false;
    if (Math.abs(s1.length() - s2.length()) > 1)
        return false;
    int i = -1;
    int j = -1;
    while (true)
    {
        i++;
        j++;
        if (i == s1.length())
            return true;
        if (s1.charAt(i) == s2.charAt(j))
            continue;
        if (i != j)
            return false; …

我有一个350,000字符串数据库,平均长度约为500.字符串不是由单词组成的,它们是基本上随机的字符组合.

我需要确保没有两个字符串太相似,其中相似性定义为编辑距离除以字符串的平均长度.划分是因为较小的字符串更容易接受较小的编辑距离.如果出于性能原因使用不同的度量标准,则可以正常运行,但编辑距离是首选的基准度量标准.

天真地,我们用运行时计算编辑距离,两个字符串的长度O(a*b)在哪里a,b.我们为所有n^2对执行此操作,这使得整体运行时间O(n^2*a*b)明显过大n=350,000, a,b=500.

数据库采用从csv文件读取的Python列表的形式.如果可能的话,我想以Pythonic的方式处理它.

怎么加速呢？我不确定天真算法需要多长时间才能完成(大约几周)但理想情况下应该花不到一天的时间才能运行.

我把"chunk transposition"放在引号中,因为我不知道技术术语应该是什么或者是什么.只知道该过程是否有技术术语将非常有帮助.

关于编辑距离的维基百科文章给出了一些关于这个概念的好背景.

通过考虑"块转置",我的意思是

Turing, Alan.

应该匹配

Alan Turing

比它更匹配

Turing Machine

即距离计算应检测文本的子串何时在文本中移动.常见的Levenshtein距离公式不是这种情况.

字符串最多只有几百个字符 - 它们是作者姓名或作者姓名列表,可以是各种格式.我没有做DNA测序(虽然我怀疑那些会对这个主题有所了解的人).