algorithm - "Absolute"字符串公制

Question

我有大量(但有限)的自然语言字符串。

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

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

我还不知道我需要的字符串差异的确切定义是什么。无论如何都没有自然语言解析。它可能应该类似于 Levenstein(但 Levenstein 是相对的，我需要绝对度量)。让我们从简单的事情开始。

维度更新

我很乐意接受多维(最好是 3d)向量而不是单一数值。

更新预期结果的正确性

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

但是我不需要绝对的解决方案。我愿意接受从 N 维字符串空间到我的 3D 空间的任何“足够好”的转换。

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

从扫描引用资料来看，我的印象是 Hilbert space-filling curve可以在这里帮助我。看起来像 Analysis of the Clustering Properties of the Hilbert Space-Filling Curve文章讨论了一些接近我的问题...

希尔伯特曲线方法更新

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

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

Answer 1

我认为这是不可能的。从一个简单的字符串开始，并将其赋值为零(数字是多少并不重要)

• “ Hello World ”= 0

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

• "XXllo 世界"= a
• "HeXXo 世界"= b
• "你好 XXrld"= c
• "你好 WorXX"= d

然而，这些字符串中的每一个都彼此相差 4。对于以下实例，无法对数字进行排序以使其起作用:

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

考虑 c 到 0 是 2，而 c 到 a 是 1，但 0 比 a 更接近。

这只是一个简单的案例。