标签: levenshtein-distance

如果是这样,请解释如何.

Re:什么是距离 - "两个字符串之间的距离定义为将一个字符串转换为另一个字符串所需的最小编辑数."

例如,xyz到XYZ将进行3次编辑,因此字符串xYZ更接近XYZ和xyz.

如果模式是[0-9] {3}或例如123,那么a23将比ab3更接近模式.

如何找到正则表达式与非匹配字符串之间的最短距离？

以上是Damerau-Levenshtein距离算法.

我在C++中编写了Levenshtein算法

如果我输入:
string s:democrat
string t:republican

我得到矩阵D填充,并且可以在D [10] [8] = 8中读取操作数(Levenshtein距离).
在填充矩阵之外,我想构建最优解.怎么看这个解决方案？我没有主意.
请只写我如何看这个例子.

我在Levenstein距离算法上遇到了一些麻烦.

我使用Levensteins距离算法来比较产品名称和产品名称列表,以找到最接近的匹配.但是,我需要稍微调整一下.我正在使用dotnetperls.com的示例.

假设我有一个来自我自己的数据库的2000个产品名称的列表A. 我自己卖掉所有这些产品.

然后我突然从我的一个供应商处获得了一个清单B,其中包含产品名称和每种产品的新价格.这可能每年发生一次以上,所以我想开发软件来手动完成工作.

问题是这个供应商不是很擅长一致性.所以他时不时地对名字做一些小改动,这意味着我不能做一个简单的字符串比较.

我已经实现了距离算法,但它并不真正符合我的需求. - 还是!

在浏览我的供应商列表时,我遇到了一个名为的产品

American Crew Anti Dandruff洗发露250毫升

该产品与我自己的产品成功匹配

美国船员抗头皮屑250毫升.

距离为10.

问题

我还遇到了一个名为的产品

美国船员3合1洗发水450毫升.

这是错误的匹配

American Crew Daily Shampoo 450 ml.

而不是我的

美国船员3合1 450毫升.

我明白为什么!但我不确定如何从这里改变算法.

有任何想法吗？

顺便说一句,我对算法并不是很好,但我相信某种称量可以帮助我在这里.

编辑:

计算时间并不是真正的问题.即使需要十个小时才能完成,它仍然比手动完成要好得多:P

我正在写一个Python聊天机器人.无论技术是什么(Levenshtein,LCS,正则表达式等),我想要一个像My name is [ A ].智能足够的模式来匹配字符串,如:

My name is Tslmy.              #Distance should = 0, and groupdict()['a'] outputs "Tslmy"
My name is Tesla Tahomana.     #Distance should = 0(!), and groupdict()['a'] outputs "Tesla Tahomana"
my  naem ist tslmy .           #With a little typo, the distance = 5, and groupdict()['a'] outputs "tslmy "

请允许我用来groupdict()['a']指代[ A ](实际上(?P<identifier>match))抓住的东西.

• 换句话说,我正在寻找一个带有省略/跳过/空白/忽略的"Levenshtein",并挑选出已被跳过的内容.
• 换句话说,我正在寻找一个模糊(也就是近似)正则表达式,它可以对模式不那么严格,仍然提供良好的旧groupdict(),以及"模糊"值(或"编辑距离",需要确定"与字符串"稍后"匹配的最佳模式.
  这是首选解决方案,因为groupdict()如果管理良好,它提供"足够" .
  然而,TRE库和REGEX库被发现是最接近的解决方案,似乎没有提供"模糊"值.如果这可以解决,那就更好了!

那可能吗？感谢您的关注.

更新:

我决定最终使用强大的正则表达式模块,但仍然无法获得"模糊值".

由于 …

核心问题是:

我正在寻找一种算法来计算一组字符串之间的最大简约距离.对于距离,我的意思是类似于Damerau-Levenshtein距离,即字符或相邻字符块的删除,插入,替换和转置的最小数量.但是我不想使用常规字符串来调查带有方向字符的字符串.

因此,字符串可能如下所示:

1. (A,1) (B,1) (C,1) (D,1)

可能的衍生物可能是:

1. (A,1) (C,0) (B,0) (D,1)
2. (A,1) (C,1) (B,1) (D,1)
3. (A,1) (B,0) (C,0) (D,1)

A,B,C,D字符身份在哪里1 = forward和0 = reverse.

这里,导数1.将具有距离2,因为你可以切出块BC并重新粘贴它(1切,1贴).衍生物2.也会有2个,因为你可以剪掉C并重新粘贴在B前面(1个剪切,1个粘贴),而数字3则需要4个操作(2个剪切,2个粘贴)进行转换.类似,删除或插入块将产生距离1.

如果要为所有可能的X 定义(X,0)和(X,1)作为两个不同的非面向字符(X0, X1),示例3.将导致距离为2,因为您可以切出块B1C1并B0C0分两步插入块.

一个现实世界的例子:

细菌基因组中的基因可以被认为是定向特征(A,0),(B,0)......通过确定序列距离,两个相关细菌中同源基因的基因组方向可以用作进化标记迹线.细菌基因组是圆形字符串的事实引入了额外的边界条件ABC等于BCA.

真正的基因组确实具有独特的基因,在伴侣中没有相应的基因,从而产生了一个占位符字符@.这些占位符将比较的信息内容减少到下限,因为例如(A,1)(B,1)@(C,1)可以转换为(A,1)@@@(B,1) @(C,1)通过插入块@@@.然而,方向部分恢复信息内容,因为您可能会发现(A,1)@@@(B,0)@(C,1)表示最小距离为3.更好的是比较多个相关序列的算法(同时,因为你可以在进化历史中找到中间体,从而提高分辨率.

我意识到,在文本字符串比较中已经发布了几个问题.但它们无法轻易扩展以包括方向.此外,存在大量处理生物序列的方法,特别是用于多序列分析.然而,它们仅限于在交替方向上不存在的大分子序列,并且通常为任何特定的字符匹配调用特定的权重.

如果已经有一个python库可以进行必要的自定义来解决这个问题,那就太棒了.但任何合适的方向感知算法都会非常有用.

我需要安装python Levenshtein距离包才能使用这个库.不幸的是,我无法成功安装它.我通常用pip安装库.但是,这次我得到error: [WinError 2] The system cannot find the file specified了之前从未发生过的事情(安装库时).我试图使用它安装它,python setup.py install但我得到完全相同的错误.这是我从控制台获得的输出.

C:\Users\my_user\Anaconda3\Lib\site-packages\python-Levenshtein-0.10.2>python setup.py install
running install
running bdist_egg
running egg_info
writing dependency_links to python_Levenshtein.egg-info\dependency_links.txt
writing namespace_packages to python_Levenshtein.egg-info\namespace_packages.txt
writing entry points to python_Levenshtein.egg-info\entry_points.txt
writing python_Levenshtein.egg-info\PKG-INFO
writing top-level names to python_Levenshtein.egg-info\top_level.txt
writing requirements to python_Levenshtein.egg-info\requires.txt
reading manifest file 'python_Levenshtein.egg-info\SOURCES.txt'
reading manifest template 'MANIFEST.in'
warning: no files found matching '*' under directory 'docs'
warning: no previously-included files matching '*pyc' found anywhere in …

我有两个多行字符串.我正在使用以下代码来确定其中两个之间的相似性.这利用了Levenshtein距离算法.

  public static double similarity(String s1, String s2) {
    String longer = s1, shorter = s2;
    if (s1.length() < s2.length()) { 
      longer = s2; shorter = s1;
    }
    int longerLength = longer.length();
    if (longerLength == 0) { return 1.0; /* both strings are zero length */ }

    return (longerLength - editDistance(longer, shorter)) / (double) longerLength;

  }

  public static int editDistance(String s1, String s2) {
    s1 = s1.toLowerCase();
    s2 = s2.toLowerCase();

    int[] costs = new int[s2.length() + 1];
    for (int i …

假设我有一个大字符串和一个子串数组,当连接时等于大字符串(差异很小).

例如(注意字符串之间的细微差别):

large_str = "hello, this is a long string, that may be made up of multiple
 substrings that approximately match the original string"

sub_strs = ["hello, ths is a lng strin", ", that ay be mad up of multiple",
 "subsrings tat aproimately ", "match the orginal strng"]

如何最好地对齐字符串以从原始字符串生成一组新的子字符串large_str？例如:

["hello, this is a long string", ", that may be made up of multiple",
 "substrings that approximately ", "match the original string"]

附加信息

用例是从PDF文档中提取的文本的现有分页符中查找原始文本的分页符.从PDF中提取的文本是OCR并且与原始文本相比具有较小的错误,但原始文本没有分页符.目标是准确地分页原文,避免PDF文本的OCR错误.

我正在编写一个diff文本工具来比较两个类似的源代码文件.

周围有很多这样的"差异"工具,但是我的工具会有所改进:

如果它发现一组线在两侧都不匹配(即在两个文件中),它不仅要突出显示这些线,还要突出显示这些线中的各个变化(我在这里称之为线间比较).

我有点工作的解决方案的一个例子:

alt text http://files.tempel.org/tmp/diff_example.png

它目前所做的是采取一组不匹配的线条并再次通过差异运行它们的单个字符,产生粉红色突出显示.

然而,包含"原始2"的第二组不匹配需要更多工作:这里,添加了前两条右线("添加线a/b"),而第三条线是左侧的改变版本.我希望我的软件能够检测到可能的更改和可能的新行之间的这种差异.

看一下这个简单的例子,我可以很容易地发现这种情况:

使用像Levenshtein这样的算法,我可以在3到5的集合中找到所有正确的行,5行最好匹配左行3,因此我可以扣除右边的行3和4被添加,并执行inter左线3和右线5的线比较.

到现在为止还挺好.但我仍然坚持如何将此转换为更通用的算法.

在更复杂的情况下,一组不同的线可以在两侧添加线,其间具有一些紧密匹配的线.这变得非常复杂:

我不仅要匹配左边的第一行和右边的最好的一行,反之亦然,依此类推所有其他行.基本上,我必须匹配左边的每一行与右边的每一行.在最坏的情况下,这可能会产生偶数交叉,因此不再容易清楚哪些线路是新插入的,哪些线路只是被改变了(注意:我不想在这样的块中处理可能移动的线路,除非这实际上会简化算法).

当然,这永远不会是完美的,但我试图让它比现在更好.任何建议不是太神论但相当实用(我不是很好理解抽象算法),这是值得赞赏的.

更新

我必须承认,我甚至不了解LCS算法是如何工作的.我只是给它提供了两个字符串数组,然后列出了哪些序列不匹配.我基本上使用的是这里的代码:http://www.incava.org/projects/java/java-diff

查看代码,我找到一个函数equal(),负责告诉算法两行是否匹配.根据帕维尔的建议,我想知道这是否是我做出改变的地方.但是怎么样？此函数仅返回布尔值 - 而不是可以识别匹配质量的相对值.而且我不能简单地使用一个固定的Levenshtein比率来决定一条相似的线是否仍然被认为是相同的 - 我需要一些自我采用的东西来处理整个线路.

所以,我基本上说的是,我仍然不明白我在哪里应用与不完全匹配的线的相对相似性相关的模糊值.

我的adist函数有问题。基本上，我使用的是RDocumentation的示例。

attr(adist(c("kitten", "sitting"), counts = TRUE), "trafos") here

但是，当我尝试运行时，又增加了一个字

attr(adist(c("kitten", "sitting", "hi"), counts = TRUE), "trafos") 

我正在取得这些结果：

     [,1]      [,2]      [,3]     
[1,] "MMMMMM"  "SMMMSMI" "SMDDDDI"

[2,] "SMMMSMD" "MMMMMMM" "SDDDMDD"

[3,] "SMIIIID" "SIIIMII" "MMI" 

在第三列的第三行中，我正在使用MMI，但我无法理解为什么是同一单词“ hi”。因此必须是MM。（匹配，匹配且无插入）

参考：https : //www.rdocumentation.org/packages/utils/versions/3.6.0/topics/adist

我正在使用另一个示例：

test <- c('x','hi', 'y','x')

attr(adist(test, y=NULL , counts = TRUE), "trafos")

我正在取得这些结果。但是至少对角线需要为M，因为同一个单词。

     [,1] [,2] [,3] [,4]
[1,] "M"  "SI" "SI" "MI"

[2,] "SD" "MM" "SD" "SD"

[3,] "SD" "SI" "MI" "SI"

[4,] "MI" "SI" "SI" "MI"

我不明白这是怎么回事。