2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Наилучшее наложение двух бит-векторов
Сообщение24.04.2008, 10:34 
Подскажите, пожалуйста, как называют следующее расстояние между бит-векторами $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\}$.
Как я понимаю, это что-то промежуточное между расстояниями Хэмминга и Левенштейна.

 
 
 
 
Сообщение24.04.2008, 10:45 
Аватара пользователя
Непонятно, в каких пределах изменяется $s$, в каких $i$, какова размерность векторов... Дайте строгое определение.

 
 
 
 
Сообщение24.04.2008, 11:05 
Аватара пользователя
Я бы сказал, что это обычное расстояние Хемминга, но не между векторами, а между множествами векторов.

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

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

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

 
 
 
 Re: Наилучшее наложение двух бит-векторов
Сообщение24.04.2008, 12:20 
Аватара пользователя
Егор писал(а):
Подскажите, пожалуйста, как называют следующее расстояние между бит-векторами $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.$

 
 
 
 третья попытка
Сообщение24.04.2008, 12:53 
:oops: :oops: Извините, опять не продумал пределы суммирования. Проще всего написать так:
$$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$.

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

 
 
 
 
Сообщение24.04.2008, 12:59 
Аватара пользователя
Что-то я "суммарного веса обрезков" не вижу в формуле.

 
 
 
 подробно про веса обрезков
Сообщение24.04.2008, 14:50 
Веса обрезков появляются, если разбить на несколько сумм.

Попытаюсь расписать подробно, какая величина должна быть при фиксированном $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*}
Получилось расстояние Хемминга между «накладываемыми частями исходных векторов» плюс веса «обрезков».

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

Я бы лучше определил пресловутое расстояние как:
$$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$$

 
 
 
 
Сообщение24.04.2008, 21:18 
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$?

 
 
 
 
Сообщение24.04.2008, 21:45 
Аватара пользователя
Посмотрите в сторону суффиксных и префиксных деревьев. Построив суффиксное дерево для одного вектора и префикcное для другого, можно попробовать поискать в них "похожие" пути...

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group