标签: similarity

有没有一种方法来计算字符串的一般"相似性得分"？在某种程度上,我不是将两个字符串比较在一起,而是为每个字符串得到一些数字(哈希),以后可以告诉我两个字符串是否相似.两个相似的字符串应该具有相似(近似)的哈希值.

让我们将这些字符串和分数视为一个例子:

Hello world                1000
Hello world!               1010
Hello earth                1125
Foo bar                    3250
FooBarbar                  3750
Foo Bar!                   3300
Foo world!                 2350

你可以看到Hello world!和Hello世界是相似的,他们的分数彼此接近.

这样,通过从其他分数中减去给定的字符串分数然后对其绝对值进行排序,可以找到与给定字符串最相似的字符串.

是否有任何库用于计算一对句子的语义相似度分数？

我知道WordNet的语义数据库,以及我如何生成2个单词的分数,但我正在寻找能够完成所有预处理任务的库,如整个句子和输出中的端口阻塞,停止单词删除等这两个句子的相关程度得分.

我找到了一个正在使用.NET框架编写的工作,该框架使用一系列预处理步骤来计算得分.是否有任何项目在python中执行此操作？

我不是在寻找可以帮助我找到分数的操作顺序(正如 我在这里要求的那样)
我喜欢自己实现每个阶段,或者从不同的库中粘合函数以便它适用于句子对,但我需要这个作为测试数据推断的工具.

编辑:我正在考虑使用NLTK并计算在两个句子上迭代的每对单词的分数,然后从结果的标准偏差中得出推论,但我不知道这是否是相似性的合理估计.另外,对于长琴弦来说,这需要很多时间.
同样,我正在寻找已经智能地实现这一点的项目/库.让我这样做的东西:

import amazing_semsim_package
str1='Birthday party ruined as cake explodes'
str2='Grandma mistakenly bakes cake using gunpowder'

>>similarity(str1,str2)
>>0.889

我想使用字符串相似性函数来查找我的数据库中的损坏数据.

我遇到了其中几个:

• 哈罗,
• 哈罗,温克勒,
• 莱文斯坦,
• 欧几里德和
• Q-克,

我想知道它们之间的区别以及它们最适合的情况？

我在这里看到了一些与确定文件相似性有关的问题,但它们都与特定域(图像,声音,文本等)相关联.作为解决方案提供的技术需要了解所比较文件的基础文件格式.我正在寻找的是一种没有此要求的方法,可以比较任意二进制文件,而无需了解它们包含的数据类型.也就是说,我希望确定两个文件的二进制数据的相似百分比.

为了给你提供更多的细节,即使这可能适用于很多事情,我确实有一个特定的问题,我正在努力.我目前也有一个有效的解决方案,但我不认为它是理想的.在比较方法方面可能存在许多优化,并存储结果.希望这里的一些人能够给我一些新的想法.我可能会在几天之后编辑一些关于我当前方法的信息,但我不想通过告诉你我是如何做的来偏见人们对这个问题的想法.

我正在研究的问题是视频游戏ROM映像的克隆检测.对于那些没有仿真经验的人来说,ROM是游戏卡带上的数据转储.ROM"克隆"通常是同一游戏的修改版本,最常见的类型是翻译版本.例如,NES 的原始最终幻想的日语和英语版本是克隆.游戏几乎分享了他们所有的资产(精灵,音乐等),但文本已被翻译.

目前有几个小组致力于维护各种系统的克隆列表,但据我所知,这一切都是手动完成的.我试图做的是找到一种方法来自动和客观地检测类似的ROM图像,基于数据相似性而不是"这些似乎是相同的游戏".检测克隆有几个原因,但其中一个主要动机是与固体压缩一起使用.这允许将所有游戏克隆压缩到同一档案中,整个压缩克隆集通常只占用比单个ROM中的一个更多的空间.

提出潜在方法时需要考虑的一些问题:

• ROM的大小各不相同,具体取决于系统.有些很小,但现代系统可能有大型,256MB或更多.一些(所有？)系统只有2个可能的大小的功能,其中一个系统上的130MB游戏将具有256MB的rom,基本上是空的.请注意,因此,如果游戏版本超过阈值并且必须使用两倍大小的盒式磁带,则某些克隆可能具有完全不同的大小.
• 目前在许多系统上有数千种已知的ROM,大多数系统仍然不断发布新的系统.即使对于较旧的系统,也有一个主要的ROM黑客社区经常生产修改后的ROM.
• 为每个可能的ROM对存储相似性数据将导致数百万行数据用于任何更流行的系统.具有5000个ROM的系统将需要2500万行相似性数据,其中一个新游戏添加另外5000行.
• 处理状态必须是可恢复的,因此如果它被中断,它可以从中断的地方继续.使用任何方法,将需要大量处理,并假设整个事件将在一个批次中运行是不安全的.
• 可以随时添加新的ROM,因此该方法不应该假设它已经具有"完整"集.也就是说,即使您已经找出所有现有ROM的相似性,如果添加了一个新的(并且这也可能在之前的处理完全完成之前发生),必须有一种方法将其与之前的所有ROM进行比较,以确定哪个(如果有的话)它是克隆的.
• 较高的处理速度应优先于准确性(至某一点).知道两个ROM是94%还是96%相似并不是特别重要,但如果需要一天的处理时间来比较新的ROM与之前的所有ROM,那么该程序可能永远不会真正完成.

这是一个有趣的问题,我期待看到其他人能想到的东西.如果您想了解更多细节,请在评论中告诉我,我会尽力提供.

如果我在mysql中有两个字符串:

@a="Welcome to Stack Overflow"
@b=" Hello to stack overflow";

有没有办法使用MYSQL获得这两个字符串之间的相似性百分比？这里例如3个单词是相似的,因此相似性应该是这样的:
count(@a和@b之间相似的单词)/(count(@a)+ count(@b) - count(intersection))
因此结果是3 /(4 + 4 - 3)= 0.6
任何想法都非常感谢!

我使用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 …

如何计算RGBA色彩空间中两种颜色之间的相似度？(当然背景颜色未知)

我需要通过为图像中的每个像素找到最佳调色板条目,将RGBA图像重新映射到RGBA颜色的调色板.

在RGB颜色空间中,可以假设最相似的颜色是具有最小欧氏距离的颜色.然而,这种方法不RGBA,例如工作,从欧氏距离rgba(0,0,0,0),以rgba(0,0,0,50%)比较小rgba(100%,100%,100%,1%),但后者看起来要好得多.

我正在使用预乘的RGBA色彩空间:

r = r×a
g = g×a
b = b×a

我尝试过这个公式(编辑: 请参阅下面的答案以获得更好的公式):

?r² + ?g² + ?b² + 3 × ?a²

但它看起来不是最佳的 - 在具有半透明渐变的图像中,它会找到错误的颜色,导致不连续/锐边.不透明颜色和alpha之间的线性比例看似腥.

什么是最佳配方？

*)为了简化这个问题,我忽略了误差扩散,伽玛和心理视觉色彩空间.

略有关联:如果你想在这个非Euclidean RGBA空间中找到最接近的颜色,vp-tree是最好的.

我需要在表中创建类似字符串的排名.

我有下表

create table names (
name character varying(255)
);

目前,我正在使用提供该功能的pg_trgm模块similarity,但我遇到了效率问题.我创建了一个像Postgres手册建议的索引:

CREATE INDEX trgm_idx ON names USING gist (name gist_trgm_ops);

我正在执行以下查询:

select (similarity(n1.name, n2.name)) as sim, n1.name, n2.name
from names n1, names n2
where n1.name != n2.name and similarity(n1.name, n2.name) > .8
order by sim desc;

查询有效,但是当你有数百个名字时,它确实很慢.此外,也许我忘了一点SQL,但我不明白为什么我不能使用条件and sim > .8没有得到"列sim不存在"错误.

我想要任何提示使查询更快.

我正在使用Levenshtein算法来找到两个字符串之间的相似性.这是我正在制作的计划中非常重要的一部分,因此它需要有效.问题是该算法没有找到类似的以下示例:

CONAIR
AIRCON

该算法将给出6的距离.因此,对于6个字母的单词(您查看具有最高字母数量的单词),差异为100%=>相似度为0%.

我需要找到一种方法来找到两个字符串之间的相似之处,同时还要考虑像我之前提到的那样的情况.

我可以使用更好的算法吗？或者你们推荐我什么？

编辑:我也研究了"Damerau-Levenshtein"算法,它增加了换位.问题是这个转置仅适用于相邻字符(而不适用于多个字符).