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

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

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

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

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

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

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

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

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


string encoding hamming-distance gray-code
person Prakhar Ganesh    schedule 15.08.2017    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

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

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

person PilotInPyjamas    schedule 15.08.2017
comment
Спасибо, это похоже на то, что я хочу. Я попробую и посмотрю, работает ли это для меня. - person Prakhar Ganesh; 15.08.2017