Кодировка для строк (предпочтительно значение) такая, что более близкие значения означают более похожие строки?

Question

Я ищу кодировку, которая может закодировать каждую строку в уникальный номер, такой что ->

1. Каждые две одинаковые строки должны иметь значения, близкие друг к другу.
2. Каждые два значения, которые близки друг к другу, должны представлять одинаковые строки.

Сходство строк будет означать, что несколько подстановок в одной строке могут образовывать другую строку. Никакие добавления или удаления не рассматриваются.

Строка может содержать только символы A, C, T и G (только четыре варианта)

Вещи, которые я пробовал ->

1. Код Грея -> Он удовлетворяет второму, но не удовлетворяет первому критерию. Две одинаковые строки не обязательно означают, что они имеют более близкие значения в сером коде.

2. Расстояние Хэмминга от исходной строки -> Понятно, что если расстояние Хемминга одинаково, это вовсе не означает, что строки одинаковы, просто они одинаково далеки от исходной. Так что это не удовлетворяет вторым критериям.

Пожалуйста, предложите метод, если вы знаете какой-либо для этой конкретной проблемы.

Answer 1

Я думаю, что вы ищете, это кривая заполнения пространства: цветная кривая Гильберта

Предположим, что строка является N-мерным вектором символов и имеет соответствующую точку в N-мерном пространстве. Любые две строки будут иметь манхэттенское расстояние, равное сумме разностей их символов, поэтому строки, которые находятся близко друг к другу в этом представлении, являются похожими строками.

Мы преобразуем наш N-мерный вектор в число от 0 до n, где n - максимально возможная строка, используя кривую Гильберта. На изображении у нас есть только два измерения, но кривые Хилберта можно обобщить до более высоких измерений.

Если вы посмотрите на изображение, линия будет непрерывной и, следовательно, удовлетворяет условию 2. Кривые Хилберта - это, по сути, обобщенный серый код.

По большей части условие 1 также верно. Если вы посмотрите на изображение, цвет кривой Гильберта медленно изменяется по всей его длине. Цвет между смежными областями кривой Гильберта обычно довольно похож, исключение в этом случае будет на полпути вниз по левой стороне, где цвет меняется с оранжевого на синий. Однако кривые Хилберта заполнят небольшую область, прежде чем перейти к следующей, поэтому большинство похожих строк будут иметь целочисленное представление, близкое друг к другу. Это не идеально, но это довольно хорошо.