问题标签 [string-metric]

我有大量任意自然语言字符串。为了让我的工具分析它们，我需要将每个字符串转换为唯一的颜色值（RGB 或其他）。我需要颜色对比来取决于字符串的相似性（字符串与其他字符串不同，它们各自的颜色应该越不同）。如果我总是为相同的字符串获得相同的颜色值，那将是完美的。

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

更新字符串之间的距离

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

那是：

相似的。

也类似（但略少）。

很不相似。

（谢谢，韦尔博格！）

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

任务简化更新

我已经删除了我自己将任务分成两部分的建议——绝对距离计算和颜色分布。这不会很好，因为起初我们将维度信息减少到单个维度，然后尝试将其合成到三个维度。

我有一组巨大（但有限）的自然语言字符串。

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

两个给定的字符串越“不同”，两个对应的值应该越不同。它们越“相似”，不同的值应该越少。

我还不知道我需要的字符串之间差异的确切定义。反正没有自然语言解析。它可能应该类似于 Levenstein（但 Levenstein 是相对的，我需要绝对度量）。让我们从简单的事情开始。

尺寸更新

我很乐意接受多维（最好是 3d）向量而不是单个数值。

更新预期结果的正确性

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

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

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

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

希尔伯特曲线方法的更新

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

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

我想比较两个字符串并得到一些分数，它们看起来有多相似。例如“句子几乎相似”和“句子很相似”。

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

Java中有更好的方法吗？

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

我的软件从数据源接收自由文本输入，它应该将这些自由文本与数据库中的预定义字符串（上述字符串）相匹配。

例如，如果软件得到字符串，它应该识别出这与比它'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

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

我也用 Trigrams 尝试过（使用 Javascript 库模糊集），但我在那里得到了类似的结果。

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

So the problem collection is something like:

Using some type of string metric like Levenshtein distance, it's simple enough to find some sort of heuristic of string similarity between 2 strings.

However, I would like to determine, without evaluating all pairs of strings in the collection (an O(N^2) problem), some type of heuristic based on the entire collection that gives me a good idea of the overall similarity between all the strings.

The brute force approach is:

Is there a way to evaluate the similarity of the entire collection of A without evaluating every pair?

我有一些（大部分）按字母顺序处理的文本，例如这些是每个段落的第一个单词：

• 阿德兰托
• 阿古拉山
• 阿拉米达
• 奥尔巴尼
• 老奥尔巴尼
  • 新奥尔巴尼
• 阿罕布拉
• 阿利索维耶霍
• 阿尔图拉斯

所以上面的每个单词都代表一个段落的开头，例如：

阿德兰托是加利福尼亚州圣贝纳迪诺县的一座城市，位于维克多维尔西北约 9 英里（14 公里）处，位于大洛杉矶地区内陆帝国的高沙漠部分...

每个条目的文本可以有很多段落，因此不按字母顺序排列的段落被视为新条目。

所以每个条目都对应一个地方。

在示例中，O(ld) 在 A(lbany) 之后，所以Old Albany是一个条目，但 N(ew) 在 O(ld) 之前，所以 New Albany是 的延续Old Albany。

我的问题是：除了在 Postgresql中使用Albany和Old Albany/的第一个字母之间的 ASCII 字符差异之外，是否已经存在一些东西？New Albany例如 ASCII ('A') - ASCII ('O') 给出 -14。

那么我是否只在第一个字符上使用 ASCII 值？还是有更通用的解决方案？

我正在尝试找到一个字符串指标，以在我的列表中找到与任意输入最相似的条目。看起来最常见的字符串度量对无关字符很重视，即使子字符串完全匹配。例如，“Corvette, red 2013”​​和“corvette”使用 difflib.get_close_matches() 的匹配存储为 0.11，但“octet rev”和“corvette”的匹配分数为 0.23。

我知道我的列表可能包含无关信息（例如“red 2013”​​），但我更想知道“corvette”是完全匹配的，而忽略了无关信息。'Octet rev' 对我来说将被视为错误匹配。

是否有任何字符串匹配指标以我需要的方式衡量匹配？更好的是，是否已经在 python 包中实现了一个？

我一直在使用 [Simmetrics][1] Java 库成功地比较两个字符串，并取得了很好的成功。但似乎有两种方法，我需要将两者结合起来用于我的场景。

目前我正在使用 CosineSimilarity（我确实使用了一些简化器，但这里省略了以保持代码简单）

这工作得很好，除非我有一个简单的拼写错误我会期望一个比我得到的更高的分数

例如比较mony honey和money honey只返回0.5（分数从0.0到1.0，1.0是完美匹配），我本来期望更高。

使用 Levenshtein 它返回更好的0.9090909

但是我在阅读文档时注意到的一件事是，这是一个MultiSet指标，并且 whitespace() 实际上需要将输入分成几部分，而像Levenshtein这样的StringMetric则不需要

这意味着 Levenshtein 没有特别考虑空格，这是一个问题，因为我想匹配单词并且基本上忽略空格或顺序。

因此，例如使用 CosineSimilarity 它在比较蜂蜜陷阱和陷阱蜂蜜时返回 1.0，但 Levenshtein 返回 0.0，这对我没有好处。

我理想地想要的是词序不重要，然后如果单词中只有轻微的变化，例如money/mony，那么单个单词就可以很好地匹配

字符串可以是任何语言，但最常见的是英文，它们是歌曲标题，因此通常少于十个单词，通常大约 5 个单词长。

Simmetrics 是否提供另一种可以同时提供这两个部分的算法？

有诸如RefinedSoundex 之类的简化器可以应用于输入，但由于该语言可能不是英语，因此认为这不会很好。

你认为最好的算法是什么？

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

我已经尝试了一些，并且所有这些Jaro Winkler给出了一些好的结果，如下所示。

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

编辑：@newuserua_ext @Trasher 谢谢，感谢您抽出宝贵的时间。我已经完成了与此相关的所有 StackExchange Q&A。并发布了这个关注人名的问题。

假设我有不同的字母表∑={a1,a2,...,an}。我也有这些字母的两种排列，我们称它们为A,B。如何找到允许块编辑操作之间A的编辑距离？B

为了更清楚，一个例子是∑={a,b,c,d}。两种可能的排列是A=abcd, B=dabc。这里的编辑距离将是 1，因为我们可以交换块abc来d获得一个字符串到另一个。

显然，这种形式的问题不会有任何删除/插入，它纯粹是交换，因为两个字符串是相同字母的排列。

现在我知道所有操作的原始编辑块问题都是 NP-Hard，但是，仅块交换的限制是否可以在多项式时间内解决？我读过的大多数文本都没有解决这个版本，而是解决了原始问题的变体。任何帮助，将不胜感激。