标签: levenshtein-distance

我是在回答你自己的问题的精神发表这篇文章的.

我的问题是:如何在Delphi中实现Levenshtein算法来计算两个字符串之间的编辑距离,如此处所述？

只是关于性能的说明:这件事非常快.在我的桌面上(2.33 Ghz双核,2GB内存,WinXP),我可以在不到一秒的时间内完成100K字符串的数组运行.

我需要自动将来自不同来源的产品名称(相机,笔记本电脑,电视等)与数据库中的规范名称相匹配.

例如"Canon PowerShot a20IS","来自佳能的NEW powershot A20 IS"和"数码相机佳能PS A20IS" 都应该与"佳能PowerShot A20 IS"相匹配.我已经使用了levenshtein距离和一些额外的启发式方法(删除了明显的常用词,为数字更改分配了更高的成本等),这在某种程度上起作用,但遗憾的是不够好.

主要问题是即使相关关键字中的单字母更改也会产生巨大差异,但要检测哪些是相关关键字并不容易.例如,考虑三个产品名称:
联想T400
联想R400
新联想T-400,酷睿2双核
任何标准前两个是可笑的类似字符串(好吧,soundex可能有助于在这种情况下消除T和R,但名称可能同样是400T和400R),第一个和第三个是相互远离的字符串,但是是相同的产品.

显然,匹配算法不能100%精确,我的目标是自动匹配大约80%的名字,具有很高的信心.

非常感谢任何想法或参考

我在Java中实现了Levenshtein算法,现在我正在通过算法进行校正,即成本.这确实有点帮助,但不多,因为我希望结果为百分比.

所以我想知道如何计算这些相似点.

我也想知道你们这样做的原因以及原因.

我只是想知道,对于我们在两个字符串之间有Levenshtein距离(或编辑距离)的字符串,是否有类似于图形的东西？

我的意思是,标识了图来变换原子操作(节点和边的插入/缺失)的数目的标量量度G1到的曲线图G2.

假设你有两个长度为100,000的字符串,包含0和1.您可以在大约10 ^ 10次操作中计算其编辑距离.

如果每个字符串只有100个,其余的都是零,那么我可以用100个整数表示每个字符串,说明它们的位置.

使用这种稀疏表示是否有更快的算法来计算编辑距离？更好的是算法也使用100 ^ 2空间而不是10 ^ 10空间.

为了给测试一些东西,考虑这两个字符串,每个字符串10个.整数表示每个字符串中的位置.

[9959, 10271, 12571, 21699, 29220, 39972, 70600, 72783, 81449, 83262]

[9958, 10270, 12570, 29221, 34480, 37952, 39973, 83263, 88129, 94336]

在算法术语中,如果我们有两个长度为n每个由k整数表示的稀疏二进制字符串,那么是否存在O(k^2)时间编辑距离算法？

我在http://code.google.com/p/pylevenshtein/找到了一个实现Levenshtein函数(距离,比率等)的伟大python库,但该项目似乎无效,文档无处可寻.我想知道是否有人比我更了解并且能指出我的文档.

我有一个约20,000个电子邮件地址的列表,其中一些我知道是欺诈性尝试绕过"每个电子邮件1个"限制,例如username1 @ gmail.com,username1a @ gmail.com,username1b @gmail. com等我想找到类似的电子邮件地址进行评估.目前我正在使用Levenshtein算法检查列表中其他电子邮件的每个电子邮件,并报告编辑距离小于2的任何电子邮件.但是,这非常缓慢.有更有效的方法吗？

我现在使用的测试代码是:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading;

namespace LevenshteinAnalyzer
{
    class Program
    {
        const string INPUT_FILE = @"C:\Input.txt";
        const string OUTPUT_FILE = @"C:\Output.txt";

        static void Main(string[] args)
        {
            var inputWords = File.ReadAllLines(INPUT_FILE);
            var outputWords = new SortedSet<string>();

            for (var i = 0; i < inputWords.Length; i++)
            {
                if (i % 100 == 0) 
                    Console.WriteLine("Processing record #" + i);

                var word1 = inputWords[i].ToLower();
                for (var n = i …

我有PHP数组,例如:

$arr = array("hello", "try", "hel", "hey hello");

现在我想重新排列数组,这将基于数组和我的$ search var之间最接近的单词.

我怎样才能做到这一点？

我正在对排名算法进行一些研究,并且想要给出排序列表和该列表的一些排列,计算两个排列之间的一些距离.对于Levenshtein距离的情况,这对应于计算序列与该序列的分类副本之间的距离.例如,还有"反转距离",这里详细描述了线性时间算法,我正在努力实现.

有没有人知道反演距离的现有python实现,和/或Levenshtein距离的优化？我在大约50,000到200,000个元素的序列上计算它,因此O(n ^ 2)太慢,但O(n log(n))或更好应该足够.

还可以理解排列相似性的其他度量.

为未来的人们编辑:

基于Raymond Hettinger的回应 ; 它不是Levenshtein或反转距离,而是"格式塔模式匹配":P

from difflib import SequenceMatcher
import random
ratings = [random.gauss(1200, 200) for i in range(100000)]
SequenceMatcher(None, ratings, sorted(ratings)).ratio()

在可怕的桌面上运行约6秒钟.

编辑2:如果你可以将你的序列强制转换为[1 .. n]的排列,那么曼哈顿度量的变化非常快并且有一些有趣的结果.

manhattan = lambda l: sum(abs(a - i) for i, a in enumerate(l)) / (0.5 * len(l) ** 2)
rankings = list(range(100000))
random.shuffle(rankings)
manhattan(rankings) # ~ 0.6665, < 1 second

归一化因子在技术上是近似值; 它对于偶数大小的列表是正确的,但应该(0.5 * (len(l) ** 2 - 1))用于奇数大小的列表.

Edit3:还有其他几种算法可用于检查列表相似度!的肯德尔头排名系数和斯皮尔曼 …

我有两个字幕文件.我需要一个函数来告诉它们是代表相同的文本还是相似的文本

有时只有一个文件中有"风正在吹......音乐在播放"的评论.但80%的内容都是一样的.该函数必须返回TRUE(文件代表相同的文本).有时会出现像1而不是l(1 - L)这样的拼写错误: 她只能放行李.当然,这意味着函数必须返回TRUE.

我的评论:
该函数应返回文本相似度的百分比 - 同意

"所有人都很开心"和"所有人都不开心" - 这里被认为是拼写错误,因此被视为同一文本.确切地说,函数返回的百分比将更低,但足够高以表示短语是相似的

请考虑是否要在整个文件或搜索字符串上应用Levenshtein - 不确定Levenshtein,但算法必须作为一个整体应用于文件.不过,这将是一个很长的字符串.