"绝对"字符串指标

Question

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

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

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

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

尺寸更新

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

更新预期结果的正确性

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

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

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

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

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

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

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

Answer 1

我不认为这是可能的.从一个简单的字符串开始,并将其指定为零(这个数字并不重要)

• "Hello World"= 0

以下字符串距离它的距离为2:

• "XXllo World"= a
• "HeXXo World"= b
• "你好XXrld"= c
• "Hello WorXX"= d

然而,这些字符串中的每一个彼此为4.对于以下实例,无法对数字进行排序以使其正常工作:

a = 1,b = -1,c = 2,d = -2

考虑到c到0是2,但c到a是1,但是0比a更接近.

这只是一个简单的案例.

Answer 2

要解决“相对距离”问题，您所需要做的就是选择一个固定点进行测量。

您仍然可以使用 Levenstein 距离，但是从固定的“Origin”字符串中获取它。例如，您可以使用所有空格的任意长度字符串作为原始字符串。

不管怎样，我首先用一小部分已知字符串来测试它，看看这些值是否反映了您期望看到的内容。