标签: edit-distance

我对计算Levenshtein距离的T-SQL算法感兴趣.

我使用PHP levenshtein函数比较字符串有一些成功.

但是,对于包含已交换位置的子串的两个字符串,算法会将这些字符串计为全新的子字符串.

例如:

levenshtein("The quick brown fox", "brown quick The fox"); // 10 differences

被视为没有共同点:

levenshtein("The quick brown fox", "The quiet swine flu"); // 9 differences

我更喜欢一种算法,它看到前两个更相似.

我怎么能想出一个比较函数,它可以识别将位置切换为与编辑不同的子串？

我想到的一种可能的方法是在比较之前将字符串中的所有单词按字母顺序排列.这使得单词的原始顺序完全脱离了比较.然而,这样做的一个缺点是,只更改一个单词的第一个字母可能会造成比单个字母更改所造成的更大的中断.

我想要实现的是比较两个关于自由文本字符串的人的事实,并决定这些事实表明相同事实的可能性.事实可能是有人上学的学校,例如雇主或出版商的名字.两个记录可能有相同的学校拼写不同,单词的顺序不同,额外的单词等,所以如果我们要好好猜测他们指的是同一所学校,那么匹配必须有些模糊.到目前为止,它在拼写错误方面表现得非常好(我使用的是一种类似于metaphone的phoenetic算法),但是如果你改变学校中常见的单词顺序则非常糟糕:"xxx college"vs "xxx学院".

我正在使用大型企业数据库.

我希望能够比较两个商业名称的相似性,看看它们是否可能是重复的.

下面是一个应该测试的企业名称列表,它们很可能是重复的,有什么好办法可以解决这个问题？

George Washington Middle Schl
George Washington School

Santa Fe East Inc
Santa Fe East

Chop't Creative Salad Co
Chop't Creative Salad Company

Manny and Olga's Pizza
Manny's & Olga's Pizza

Ray's Hell Burger Too
Ray's Hell Burgers

El Sol
El Sol de America

Olney Theatre Center for the Arts
Olney Theatre

21 M Lounge
21M Lounge

Holiday Inn Hotel Washington
Holiday Inn Washington-Georgetown

Residence Inn Washington,DC/Dupont Circle
Residence Inn Marriott Dupont Circle

Jimmy John's Gourmet Sandwiches
Jimmy …

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

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

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

对于Data Structures项目,我必须找到两个单词之间的最短路径(例如"cat"和"dog"),一次只能更改一个字母.我们给出了一个拼字游戏单词列表,用于查找我们的路径.例如:

cat -> bat -> bet -> bot -> bog -> dog

我已经使用广度优先搜索解决了这个问题,但我正在寻找更好的东西(我用trie代表字典).

请给我一些更有效的方法(在速度和记忆方面)的想法.有些荒谬和/或挑战是首选.

我问过我的一个朋友(他是一名大三学生),他说这个问题没有有效的解决办法.他说我会学习为什么我参加算法课程.对此有何评论？

我们必须一个接一个地移动.我们不能去cat -> dat -> dag -> dog.我们还必须打印出遍历.

我试图根据2个字符串之间的比较来指定相似度分数.在R中是否有相同的功能.我在SAS中通过SPEDIS的名称了解这样的功能.如果在R中有这样的功能,请告诉我.

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

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

我公司的猫饲养应用程序追踪一队猫.它需要定期previousOrder与currentOrder(每个是ArrayList<Cat>)进行比较,并通知cat-wranglers任何变化.

每只猫都是独一无二的,只能在每个列表中出现一次(或根本不出现).大多数情况下,previousOrder和currentOrder列表具有相同的内容,顺序相同,但可能发生以下任何情况(从更频繁到更不频繁):

1. 猫的顺序完全被扰乱
2. 猫在列表中单独向上或向下移动
3. 新猫加入,在车队的特定点
4. 猫离开了车队

这对我来说似乎是一个编辑距离问题.理想情况下,我正在寻找一种算法来确定进行previousOrder匹配所需的步骤currentOrder:

• 移动Fluffy到位置12
• 插入Snuggles位置37
• 删除 Mr. Chubbs
• 等等

算法还应识别场景#1,在这种情况下,新订单将完整地传达.

对此最好的方法是什么？

(这篇文章和那篇文章提出了类似的问题,但是他们都在处理排序列表.我的订单是订购的,但未分类.)

编辑

该Levenshtein算法是一个很好的建议,但我很担心创建一个矩阵的时间/空间需求.我的主要目标是尽快确定并传达变更.比找到添加和发送消息更快的事情是"这是新猫,这是当前的订单."

是否有算法可以让您找到2个句子之间的单词级编辑距离？例如,"大肥狗"和"肥狗大房子"有1个替代品,3个插入物

给定两个文件树A和B,是否可以确定最短的操作序列或为了将A转换为B所必需的短序列操作？

操作可以是:

1. 创建一个新的空文件夹
2. 使用任何内容创建新文件
3. 删除文件
4. 删除一个空文件夹
5. 重命名文件
6. 重命名文件夹
7. 将文件移动到另一个现有文件夹中
8. 在另一个现有文件夹中移动文件夹

当A和B在相同的文件夹结构中具有相同内容(或相同大小相同CRC)和相同名称的相同文件时,它们是相同的.

这个问题一直困扰着我.目前我有以下基本想法:

• 计算数据库:
  • 存储文件名及其CRC
  • 然后,查找没有子文件夹的所有文件夹,并从它们包含的文件的CRC计算CRC,并从它们包含的文件的总大小计算大小
  • 升级树以为每个父文件夹创建CRC
• 使用具有数据库A和数据库B的以下循环:
  • 计算A∩B并从两个数据库中删除此交集.
  • 使用内部联接在A和B中查找匹配的CRC,首先按文件夹desc排序
  • 当有结果时,使用第一个结果使文件夹或文件移动(如果需要可能创建新文件夹),从两个数据库中删除结果的源行.如果有移动,则更新db A中新位置的父文件夹的CRC.
  • 然后删除数据库A中引用的所有文件和文件夹,并创建数据库B中引用的那些

但是我认为这实际上是一种不理想的方式.你能给我什么建议？

谢谢!