string相似度分数/散列
有没有一种方法来计算一个string的一般“相似性分数”？ 在某种程度上，我不是比较两个string在一起，而是我得到一些数字（哈希）为每个string，可以稍后告诉我，两个string是或不相似的。 两个相似的string应该有相似的（接近）散列。
让我们以这些string和分数为例：
Hello world 1000 Hello world! 1010 Hello earth 1125 Foo bar 3250 FooBarbar 3750 Foo Bar! 3300 Foo world! 2350 你可以看到Hello world！ 和你好世界是相似的，他们的分数是相互接近的。
这样，find给定string的最相似的string将通过从其他分数中减去给定的string得分，然后对它们的绝对值进行sorting来完成。
我相信你在找什么叫做局部敏感哈希 。 而大多数散列algorithm是这样devise的，即input的小变化引起输出的大变化，这些散列尝试相反：input的小变化产生比例小的输出变化。
正如其他人所提到的，将多维映射强制为二维映射存在固有的问题。 这类似于创build地球的平面地图…你永远不能准确地表示一个平面上的球体。 你可以做的最好的办法是find一个LSH，该LSH针对你用来确定string是否“相似”的任何特性进行了优化。
一般来说，这是不可能的，因为string之间的编辑距离集形成了度量空间 ，而不是一个具有固定维度的空间。 这意味着你不能提供string和整数之间的映射，保留它们之间的距离度量。
例如，您不能将数字分配给这三个短语：
- 一二
- 一个六
- 两个六
这样的数字反映了所有三个短语之间的差异。
莱文斯坦距离或其衍生物是你想要的algorithm。 将给定的string与字典中的每个string匹配。 （在这里，如果只需要固定数量的最相似的string，则可能需要使用min-heap。）如果对字典中的所有string运行Levenstein距离太昂贵，那么先使用一些粗略的algorithm来排除太远的字候选人名单。 之后，在左边候选人上运行levenstein距离。
消除遥远话语的一种方法是索引n-gram。 通过将每个单词分成n-gram列表来预处理字典。 例如，考虑n = 3：
(0) "Hello world" -> ["Hel", "ell", "llo", "lo ", "ow", " wo", "wor", "orl", "rld"] (1) "FooBarbar" -> ["Foo", "ooB", "oBa", "Bar", "arb", "rba", "bar"] (2) "Foo world!" -> ["Foo", "oo ", "ow", " wo", "wor", "orl", "rld", "ld!"]
接下来，创buildn-gram的索引：
" wo" -> [0, 2] "Bar" -> [1] "Foo" -> [1, 2] "Hel" -> [0] "arb" -> [1] "bar" -> [1] "ell" -> [0] "ld!" -> [2] "llo" -> [0] "lo " -> [0] "ow" -> [0, 2] "oBa" -> [1] "oo " -> [2] "ooB" -> [1] "orl" -> [0, 2] "rba" -> [1] "rld" -> [0, 2] "wor" -> [0, 2]
当你需要为给定的stringfind最相似的string时，将给定的string分成n-gram，并且只select那些至less有一个匹配的n-gram的字典。 这将候选人的数量减less到合理的数量，并且您可以将给定string的levenstein匹配进行到每个左候选人。
如果string足够长，可以通过使用最小散列技术来减小索引大小：计算n-gram中的每一个的普通散列值，只使用K个最小散列值，其他散列值将被丢弃。
PS 这个演讲似乎是一个很好的介绍你的问题。
虽然这个想法似乎非常甜蜜…我从来没有听说过这个。
我已经阅读了许多关于拼写纠正/错字校正的技术，论文和科学论文，最快的提案围绕着一个索引和levenshtein距离。
有相当详细的工艺，我目前正在工作的结合：
- 一个爆炸的Trie，水平紧凑
- Levenshtein自动机
尽pipe这并不意味着获得分数是“不可能的”，但是我总觉得如果这种“得分”方法被certificate是有效的，那么就不会有那么多关于string比较的研究。
如果你find这样的方法，我非常感兴趣:)
Levenshtein距离会为你工作吗？
你的想法听起来像本体论，但适用于整个短语。 越相似的两个短语越接近图表（假设您使用加权边缘）。 反之亦然：不相似的短语彼此非常远。
另一种方法是使用傅立叶变换得到给定string的“索引”（它不会是一个单一的数字，但总是）。 本文中您可能会发现更多。
还有另外一个基于Levenshtein距离的想法：你可以比较两个给定短语给出一些相似指数的n-gram – 它们越接近越接近1.这可以用来计算距离graphics。 如果你想我可以分享它，几年前写了一篇文章。
无论如何：尽pipe我不知道确切的解决scheme，但我也对你想出的东西感兴趣。
在一个无限的问题中，没有任何解决scheme可以将任何可能的单词序列或任何可能的字符序列转换为描述局部性的单个数字。
想象一下在angular色层面上的相似性
stops spots hello world world hello
在这两个例子中，消息都是不同的，但消息中的字符是相同的，所以度量需要保存一个位置值以及一个字符值。 （char 0 =='h'，char 1 =='e'…）
然后比较以下类似的消息
hello world ello world
虽然这两个string是相似的，但在开始或结束时它们可能会有所不同，这使得按位置缩放成为问题。
如果是
spots stops
这些字只是由于字符的位置而不同，所以某种forms的位置是重要的。
如果以下string是相似的
yesssssssssssssss yessssssssssssss
那么你有一个矛盾的forms。 如果向第二个string添加2个字符，它应该共享与第一个string的距离，但是它应该是不同的。 这可以重复得到逐渐变长的琴弦，所有这些都需要接近比它们更短和更长的琴弦。 我看不出如何实现这一点。
一般来说，这被视为一个多维问题 – 将string分解为一个向量
[ 'h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd' ]
但是vector的值不可以
- 由一个固定大小的数字表示，或者
- 给出好的质量差异度量。
如果字的数量或string的长度是有界的，那么编码的解决scheme是可能的。
有限的价值
使用诸如算术压缩之类的东西，然后可以将一个单词序列转换成代表序列的浮点数。 但是，这会将序列中的项目视为比序列中的最后一个项目更重要。
数据挖掘解决scheme
如果您接受问题的高维度，那么您可以将您的string存储在度量标准树wikipedia：Metric树中 。 这将限制您的search空间，同时不解决您的“单号”解决scheme。
我在github上有这样的代码：集群
一起放在一起的东西应该放在树的一部分里，但实际上是没有保证的。 子树的半径用于修剪search空间。
编辑距离或Levenshtein距离
这被用在一个sqlite扩展来执行相似性search，但没有单一的数字解决scheme，它计算出多less编辑更改一个string到另一个。 然后得到一个分数，显示相似性。
我想到这样的事情：
- 删除所有非单词字符
- 申请soundex
从两个短语中得到一个相当小的数字是不太可能的，这两个短语相比较，可以提供相关的初始短语的相似性。
一个原因是这个数字在一个维度上给出了一个指示，而这个短语是在长度和强度两个维度上演变的。
这个数字可能会随着强度的变化而变化，但我不确定这会有多大的帮助。
在两个维度上，你最好看一个matrix，其中行列式 （matrix的一种导数）等性质可以粗略地理解短语趋势 。
也许使用PCA ，其中matrix是string和固定字母之间的差异列表（àla ABCDEFGHI …）。 答案可能只是主要组件的长度。
只是一个想法。
在C＃中准备运行的PCA
在自然语言处理中，我们有一个叫最小编辑距离 （也称为Levenshtein距离）
它基本上定义为将string1转换为string2所需的最小操作量
包括插入，删除，取消在内的操作，每个操作都有一个你添加到距离的分数
解决你的问题的想法是计算MED从你select的string，到所有其他string，sorting该集合，并挑出第n个第一个最小的距离string
例如：
{"Hello World", "Hello World!", "Hello Earth"} Choosing base-string="Hello World" Med(base-string, "Hello World!") = 1 Med(base-string, "Hello Earth") = 8 1st closest string is "Hello World!"
这有点给你的string集合的每个string得分
C＃实现（Add-1，Deletion-1，Substitution-2）
public static int Distance(string s1, string s2) { int[,] matrix = new int[s1.Length + 1, s2.Length + 1]; for (int i = 0; i <= s1.Length; i++) matrix[i, 0] = i; for (int i = 0; i <= s2.Length; i++) matrix[0, i] = i; for (int i = 1; i <= s1.Length; i++) { for (int j = 1; j <= s2.Length; j++) { int value1 = matrix[i - 1, j] + 1; int value2 = matrix[i, j - 1] + 1; int value3 = matrix[i - 1, j - 1] + ((s1[i - 1] == s2[j - 1]) ? 0 : 2); matrix[i, j] = Math.Min(value1, Math.Min(value2, value3)); } } return matrix[s1.Length, s2.Length]; }
复杂度O（nxm）其中n，m是每个string的长度
最小编辑距离的更多信息可以在这里find
那么，你可以将每个angular色的ASCII值加起来，然后比较分数，得到的最大值可以不同。 这并不能保证它们是相似的，同样的原因，两个不同的string可以有相同的散列值。
你当然可以做一个更复杂的函数，首先检查string的大小，然后逐一比较每个字符，再次设置最大差异。
