Метрика минимального расстояния в кодированной последовательности

Question

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

Рассмотрим следующие примеры:

AABBAA
CCDDCC

имеет расстояние 0, потому что A = C и B = D (или AA = CC и BB = DD).

AABBBBBB
CCDDEEEE

имеет расстояние 2, потому что A = C и B = E (или AA = CC или BB = EE или BBBB = EEEE), но B =/= D (или BB =/= DD).

Однако эта функция может работать не совсем так. Мне просто нужно знать, как некодированная последовательность похожа, с точки зрения повторения, на закодированную. Можно предположить, что вторая последовательность закодирована чем-то вроде шифра Цезаря (хотя я не уверен, что, например, сдвиг может меняться во времени).

Примечание:

Я также подумал о сжатии двух последовательностей с помощью алгоритма LZW и сравнил степень их сжатия. Любая другая идея?

Answer 1

Вы можете перечислять элементы в ваших последовательностях с непрерывными числами с начала, а затем использовать расстояние Левенштейна или что-то в этом роде.

AACCAABB  --> 11221133  (A->1, C->2, B->3)
CCXXCCYY  --> 11221133  (C->1, X->2, Y->3)

d(AACCAABB, CCXXCCYY) = d(11221133, 11221133) = 0