标签: string-metric

我想比较两个字符串并获得一些评分看起来有多相似.例如"句子几乎相似"和"句子相似".

我不熟悉Java中的现有方法,但对于PHP我知道levenshtein函数.

Java中有更好的方法吗？

假设我的数据库中有以下两个字符串:

(1) 'Levi Watkins Learning Center - Alabama State University'
(2) 'ETH Library'

我的软件从数据源接收自由文本输入,它应该将这些自由文本与数据库中的预定义字符串(上面的那些)相匹配.

例如,如果软件获得字符串'Alabama University',它应该认识到这与(1)它更相似(2).

起初,我想过使用像Levenshtein-Damerau或Trigrams这样众所周知的字符串度量,但这会导致不必要的结果,如下所示:

http://fuzzy-string.com/Compare/Transform.aspx?r=Levi+Watkins+Learning+Center+-+Alabama+State+University&q=Alabama+University

http://fuzzy-string.com/Compare/Transform.aspx?r=ETH+Library&q=Alabama+University

Difference to (1): 37
Difference to (2): 14

(2)获胜因为它比它短得多(1),即使(1)包含搜索字符串的单词(Alabama和University).

我也尝试过Trigrams(使用Javascript库fuzzySet),但我在那里得到了类似的结果.

是否有一个字符串指标可以识别搜索字符串的相似性(1)？

我有一大堆任意自然语言字符串.对于我分析它们的工具,我需要将每个字符串转换为唯一的颜色值(RGB或其他).我需要颜色对比度来依赖于字符串相似性(字符串与其他字符串不同,它们各自的颜色应该不同).如果我总是为同一个字符串获得相同的颜色值,那将是完美的.

关于如何解决这个问题的任何建议？

更新字符串之间的距离

我可能需要将"相似性"定义为类似Levenstein的距离.不需要自然语言解析.

那是:

"I am going to the store" and 
"We are going to the store"

类似.

"I am going to the store" and 
"I am going to the store today"

类似(但略少).

"I am going to the store" and 
"J bn hpjoh up uif tupsf"

很不相似.

(谢谢,Welbog!)

只有当我看到程序输出时,我才可能确切地知道我需要什么距离函数.所以让我们从简单的事情开始吧.

更新任务简化

我删除了自己的建议,将任务分成两部分 - 绝对距离计算和颜色分布.这不会很好,因为我们首先将尺寸信息减少到一个维度,然后尝试将其合成到三维.

我有一组巨大的(但有限的)自然语言字符串.

我需要一种方法将每个字符串转换为数字值.对于任何给定的字符串,每次的值必须相同.

两个给定字符串越"不同",两个对应的值应该越不同.它们越"相似",值就越少.

我还不知道我需要的字符串之间的区别是什么.无论如何都没有自然语言解析.它可能应该像Levenstein一样(但是Levenstein是相对的,我需要绝对的度量).让我们从简单的事情开始.

尺寸更新

我很乐意满足于多维(3d是最好的)向量而不是单个数值.

更新预期结果的正确性

正如在此处和此处正确指出的那样,从一个字符串到另一个字符串的距离是具有MAX(firstStringLength, secondStringLength)维度的向量.通常,在不丢失信息的情况下不可能减少维数.

但是我不需要绝对的解决方案.我会满足于从N维字符串空间到我的3D空间的任何"足够好"的转换.

另请注意,我有一定数量的有限长度的字符串.(虽然字符串数量相当大,约为8000万(10 GB),所以我最好选择一些单通道无状态算法.)

从扫描参考资料来看,我的印象是希尔伯特空间填充曲线可能对我有所帮助.看起来分析Hilbert空间填充曲线的聚类属性文章讨论了一些接近我的问题...

关于希尔伯特曲线方法的更新

1. 我们将每个字符串映射到N维空间中的一个点,其中N是集合中字符串的最大长度.顺便说一下,字符串中的第i个字符代码可以用作第i个坐标值吗？
2. 我们通过N维空间绘制希尔伯特曲线.
3. 对于每个字符串,我们在曲线上取点,最接近字符串的坐标.该点的希尔伯特值(从曲线起点开始的长度)是我寻求的一维值.
4. 如果我们需要3D值,我们在3D中绘制希尔伯特曲线并选取匹配希尔伯特值的拾取点,如上所述.

这看起来不错吗？这里的计算费用是多少？

我特别致力于一个允许拼写错误和别名的 人的功能.我做了一些研究,发现字符串度量和语音库也有很多算法.

我已经尝试了一些,其中Jaro Winkler给出了一些好的结果,如下所示.

compareStrings("elon musk","elon musk"))    --> 1.0 
compareStrings("elonmusk","elon musk"))     --> 0.98
compareStrings("elon mush","elon musk"))    --> 0.99
compareStrings("eln msuk","elon musk"))     --> 0.94
compareStrings("elon","elon musk"))         --> 0.89
compareStrings("musk","elon musk"))         --> 0.0  //This is bad, but can fix that.
compareStrings("mr elon musk","elon musk")) --> 0.81

以上是Apache commons Library的实现.我想知道是否有更好的实现可以更好地实现目的.任何帮助表示赞赏.

编辑:@newuserua_ext @Trasher谢谢,我感谢你的时间.我已经完成了与此相关的所有StackExchange问​​答.并发布了这个关注人名的问题.

根据维基百科,可以对Wagner-Fischer算法进行修改,该算法可以计算出两个单词的Levenshtein距离是否低于某个阈值,如果你想知道的话,这比原来的快得多.

"通过检查对角线而不是行,并通过使用延迟评估,我们可以在O(m(1 + d))时间内找到Levenshtein距离(其中d是Levenshtein距离),这比常规动态编程算法快得多如果距离很小."

这个解决方案如何运作？我真的很难看到它,因为感觉任何矩阵单元格的值都取决于上面的单元格的值,左边和左边的对角线,所以我不知道如何遍历矩阵仅使用斜条.