Наилучшее наложение двух бит-векторов

[Егор]

Подскажите, пожалуйста, как называют следующее расстояние между бит-векторами $a=(a_1,\ldots,a_n)$ и $b=(b_1,\ldots,b_n)$:

$$d_?(a,b)=\min_{-n\le s\le n}\sum_{1-n\le i\le 2n} |a_{s+i}-b_i|.$$

Здесь считается, что $a_{s+i}=0$ при $s+i\notin\{1,\ldots,n\}$ и $b_i=0$ при $i\notin\{1,\ldots,n\}$.
Как я понимаю, это что-то промежуточное между расстояниями Хэмминга и Левенштейна.

[maxal]

Непонятно, в каких пределах изменяется $s$, в каких $i$, какова размерность векторов... Дайте строгое определение.

[PAV]

Я бы сказал, что это обычное расстояние Хемминга, но не между векторами, а между множествами векторов.

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

[Егор]

Да, в условии нужно было сразу уточнить, что при выходе за границы массивов доопределяем нулями. Подправил.

PAV, спасибо за ответ. Если не будет ещё более точной наводки, то воспользуюсь Вашей.

[maxal]

Егор писал(а):

Подскажите, пожалуйста, как называют следующее расстояние между бит-векторами $a=(a_1,\ldots,a_n)$ и $b=(b_1,\ldots,b_n)$:

$$d_?(a,b)=\min_{-n\le s\le n}\sum_{1\le i\le n} |a_{s+i}-b_i|.$$

Здесь считается, что $a_{s+i}=0$ при $s+i\notin\{1,\ldots,n\}$.

Странное определение. Во-первых, оно несимметрично: $d_?(a,b)\ne d_?(b,a).$
Во-вторых, расстояние от вектора $a=(1,1,\dots,1)$ до $b=(0,0,\dots,0)$ размерности $n$ равно нулю - достаточно взять $s=n.$

[Егор]

Извините, опять не продумал пределы суммирования. Проще всего написать так:

$$d_?(a,b)=\min_{-n\le s\le n}\sum_{i\in{\mathbb Z}} |a_{s+i}-b_i|.$$

Здесь считается, что $a_{s+i}=0$ при $s+i\notin\{1,\ldots,n\}$ и $b_i=0$ при $i\notin\{1,\ldots,n\}$.
Фактически, достаточно изменять $i$ от $1-n$ до $2n$.

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

[maxal]

Что-то я "суммарного веса обрезков" не вижу в формуле.

[Егор]

Веса обрезков появляются, если разбить на несколько сумм.

Попытаюсь расписать подробно, какая величина должна быть при фиксированном $s$. Векторы $a$ и $b$ доопределяем нулями до двусторонних последовательностей, потом сдвигаем $a$ на $s$ влево (при $s<0$ получится сдвиг вправо). Эту сдвинутую последовательность обозначим через $T_{-s}a$:

$$(T_{-s}a)_i=a_{s+i}.$$

Рассматриваем расстояние Хемминга между последовательностями $T_{-s} a$ и $b$:

$$d_H(T_{-s} a,b)=\sum_{i=-\infty}^{+\infty}|a_{i+s}-b_i|.$$

На самом деле, достаточно суммировать от $1-n$ до $2n$, точнее даже от $\min(1,1-s)$ до $\max(n,n-s)$.

Если $s>0$, то
\begin{align*} d_H(T_{-s} a,b) &=\sum_{i=1-s}^{0}a_{i+s} +\sum_{i=1}^{n-s}|a_{i+s}-b_i| +\sum_{i=n-s+1}^{n}b_i =\\ &=w(a_{1}^{s})+d_H(a_{s+1}^n,b_1^{n-s})+w(b_{n-s+1}^n). \end{align*}
Если $s<0$, то
\begin{align*} d_H(T_{-s} a,b) &=\sum_{i=1}^{-s}b_i +\sum_{i=1-s}^{n}|a_{i+s}-b_i| +\sum_{i=n+1}^{n-s}a_{i+s} =\\ &=w(b_{1}^{-s})+d_H(a_{1}^{n+s},b_{1-s}^n)+w(a_{n+s+1}^n). \end{align*}
Получилось расстояние Хемминга между «накладываемыми частями исходных векторов» плюс веса «обрезков».

[maxal]

Есть проблема с доопределение нулями - она вносит "перекос" в сторону нулей. Например, нулевой вектор можно сдвигать как угодно, на результат это не повлияет, а вот вектор из всех единиц лучше не двигать, так как получаются "тяжелые обрезки".

Я бы лучше определил пресловутое расстояние как:

$$d(a,b) = \min_{-n\leq s\leq n} 2|s| + \sum_{1\leq i\leq n\atop 1\leq s+i\leq n} |a_{i+s}-b_{i}|$$

Здесь ничего доопределять не надо, и вес "обрезков" не зависит от доопределения, а только от их длины.

Добавлено спустя 6 минут 4 секунды:

Чуть более подробно тоже самое можно записать так:

$$d(a,b) = \min_{0\leq s\leq n} \min\left\{ \sum_{i=1+s}^n |a_i-b_{i-s}|, \sum_{i=1}^{n-s} |a_{i+s}-b_i|\right\} + 2s$$

[Егор]

maxal, спасибо за сообщения об ошибках. Я ещё раз подправил исходное сообщение.

maxal писал(а):

Я бы лучше определил пресловутое расстояние как:

$$d(a,b) = \min_{-n\leq s\leq n} 2|s| + \sum_{1\leq i\leq n\atop 1\leq s+i\leq n} |a_{i+s}-b_{i}|$$

Да, в случае «равноправных» букв правильнее учитывать длины обрезков.

Меня сейчас больше волнует ситуация, когда одна из букв (нуль) играет роль фона. Например, бит-векторы 000110111 и 0110111000 отождествляются. Тогда важны веса обрезков.

Эти две задачи кажутся довольно близкими, поэтому интересна информация о любой из них. Главный вопрос: можно ли вычислять какое-нибудь из этих расстояний за время $O(n^p)$, где $p<2$?

[maxal]

Посмотрите в сторону суффиксных и префиксных деревьев. Построив суффиксное дерево для одного вектора и префикcное для другого, можно попробовать поискать в них "похожие" пути...