對字符串進行編碼（最好是一個值），使得更接近的值意味着更類似的字符串？

Question

我要尋找的編碼，可以每串編碼爲一個唯一的編號，使得 - >

1. 每兩個字符串是相似必須彼此接近的值。
2. 每兩個彼此接近的值必須表示相似的字符串。

字符串的相似性意味着一個字符串中的幾個替換可以形成另一個字符串。不考慮增加或刪除。

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

事情我試圖 - >

1. 格雷碼 - >它滿足第二個但沒有按不符合第一標準。兩個相似的字符串並不意味着它們在格雷碼中的值更接近。

2. 漢明與引用字符串的距離 - >很明顯，如果漢明距離相同，它並不意味着字符串是相似的，只是它們距離引用相等。所以它不符合第二個標準。

如果你知道這個問題，請給出一個方法。

Answer 1

我想你要找的是一個空間填充曲線： A coloured Hilbert Curve

考慮一個字符串是字符的N維向量，並有以N維空間中的對應點。任何兩個字符串的曼哈頓距離等於它們字符差異的總和，因此在這個表示中相近的字符串是相似的字符串。

我們使用希爾伯特曲線將N維向量轉換爲0到n之間的數字，其中n是最高可能值的字符串。在圖像中，我們只有兩個維度，但希爾伯特曲線可以推廣到更高的維度。

如果你看圖像，這條線是連續的，因此滿足條件2.希爾伯特曲線本質上是一個廣義的格雷碼。

大多數情況下，條件1也是如此。如果你看圖像，希爾伯特曲線的顏色在它的長度上變化緩慢。希爾伯特曲線的相鄰區域之間的顏色通常非常相似，在這種情況下，例外情況將在左側的一半處，顏色從橙色變爲藍色。然而，Hillbert曲線在移動到下一個曲面之前會填滿一個小區域，因此大多數類似的字符串將具有彼此接近的整數表示。這並不完美，但相當不錯。