对字符串进行编码（最好是一个值），使得更接近的值意味着更类似的字符串？

Question

我要寻找的编码，可以每串编码为一个唯一的编号，使得 - >

1. 每两个字符串是相似必须彼此接近的值。
2. 每两个彼此接近的值必须表示相似的字符串。

字符串的相似性意味着一个字符串中的几个替换可以形成另一个字符串。不考虑增加或删除。

串只能有字符A，C，T和G（仅四种可能性）

事情我试图 - >

1. 格雷码 - >它满足第二个但没有按不符合第一标准。两个相似的字符串并不意味着它们在格雷码中的值更接近。

2. 汉明与引用字符串的距离 - >很明显，如果汉明距离相同，它并不意味着字符串是相似的，只是它们距离引用相等。所以它不符合第二个标准。

如果你知道这个问题，请给出一个方法。

Answer 1

我想你要找的是一个空间填充曲线： A coloured Hilbert Curve

考虑一个字符串是字符的N维向量，并有以N维空间中的对应点。任何两个字符串的曼哈顿距离等于它们字符差异的总和，因此在这个表示中相近的字符串是相似的字符串。

我们使用希尔伯特曲线将N维向量转换为0到n之间的数字，其中n是最高可能值的字符串。在图像中，我们只有两个维度，但希尔伯特曲线可以推广到更高的维度。

如果你看图像，这条线是连续的，因此满足条件2.希尔伯特曲线本质上是一个广义的格雷码。

大多数情况下，条件1也是如此。如果你看图像，希尔伯特曲线的颜色在它的长度上变化缓慢。希尔伯特曲线的相邻区域之间的颜色通常非常相似，在这种情况下，例外情况将在左侧的一半处，颜色从橙色变为蓝色。然而，Hillbert曲线在移动到下一个曲面之前会填满一个小区域，因此大多数类似的字符串将具有彼此接近的整数表示。这并不完美，但相当不错。