В данной статье речь пойдет об алгоритме HEngine и реализации решения проблемы подсчета расстояния Хэмминга на больших объемах данных.

Введение

Расстояние Хэмминга - это количество различающихся позиций для строк с одинаковой длинной. Например, HD(100, 001) = 2.

Впервые проблема подсчета расстояния Хэмминга была поставлена Minsky и Papert в 1969 году , где задача сводилась к поиску всех строк из базы данных, которые находятся в пределах заданного расстояния Хэмминга к запрашиваемой.

Подобная задача является необычайно простой, но поиск ее эффективного решения до сих пор остается на повестке дня.

Расстояние Хэмминга уже довольно широко используется для различных задач, таких как поиск близких дубликатов, распознавание образов, классификация документов, исправление ошибок, обнаружения вирусов и т.д.

Например, Manku и сотоварищи предложили решение проблемы кластеризации дубликатов при индексации веб документов на основе подсчета расстояния Хэмминга .
Также Miller и друзья предложили концепцию поиска песен по заданному аудио фрагменту , .
Подобные решения были использованы и для задачи поиска изображений и распознавание сетчатки , и т.д.

Описание проблемы

Имеется база данных бинарных строк T , размером n , где длина каждой строки m . Запрашиваемая строка a и требуемое расстояние Хэмминга k .

Задача сводится к поиску всех строк, которые находятся в пределах расстояния k .

В оригинальной концепции алгоритма рассматривается два варианта задачи: статическая и динамическая.

В статическая задачи расстояние k предопределено заранее.
- В динамической, наоборот, требуемое расстояние заранее неизвестно.

В статье описывается решение только статической задачи.

Описание алгоритма HEngine для статической задачи

Данная реализация фокусируется на поиске строк в пределах k <= 10.

Существует три решения статической задачи: линейный поиск (linear scan), расширение запроса (query expansion) и расширение базы данных (table expansion).

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

HEngine использует комбинацию этих трех методов для эффективного балансирования между памятью и временем исполнения.

Немного теории

Алгоритм базируется на небольшой теореме, которая гласит следующее:

Если для двух строк a и b расстояние HD(a , b ) <= k , то если поделить строки a и b на подстроки методом rcut используя фактор сегментации
r >= ⌊k /2⌋ + 1
обязательно найдется по крайней мере q = r − ⌊k /2⌋ подстрок, когда их расстояние не будет превышать единицу, HD(a i, b i) <= 1.

Выделение подстрок из базовой строки методом rcut выполняется по следующим принципам:
Выбирается значение, названное фактором сегментации , которое удовлетворяет условию
r >= ⌊k /2⌋ + 1

Длина первых r − (m mod r ) подстрок будет иметь длину ⌊m / r ⌋, а последние m mod r подстроки ⌈m /r ⌉. Где m - это длина строки, ⌊ - округление до ближайшего снизу, а ⌉ округление до ближайшего сверху.

Теперь тоже самое, только на примере:

Даны две бинарные строки длиной m = 8 бит: A = 11110000 и B = 11010001, расстояние между ними k = 2.
Выбираем фактор сегментации r = 2 / 2 + 1 = 2, т. е. всего будет 2 подстроки длиной m /r = 4 бита.

a1 = 1111, a2 = 0000
b1 = 1101, b2 = 0001

Если мы сейчас подсчитаем расстояние между соответствующими подстроками, то по крайней мере q = 2 - 2/2 = 1, одна подстрока совпадет или их расстояние не будет превышать единицу.

Что и видим:
HD(a1, b1) = HD(1111, 1101) = 1
и
HD(a2, b2) = HD(0000, 0001) = 1

Подстроки базовой строки были названы сигнатурами .
Сигнатуры или подстроки a1 и b1 (a2 и b2, a3 и b3 …, ar и br ) называются совместимыми с друг другом, а если их количество отличающихся битов не больше единицы, то эти сигнатуры называются совпадающими .

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

Предварительная обработка базы данных

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

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

Но как производить поиск по подстрокам?

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

В оригинальной версии алгоритма еще описывается перестановка подстрок таким образом, чтобы выбранные подстроки были на первом месте. Это делается больше для удобства реализации и для дальнейших оптимизаций алгоритма:

Имеется строка A, которая делится на 3 подстроки, a1, a2, a3, полный список перестановок будет соответственно:
a1, a2, a3
a2, a1, a3
a3, a1, a2

Затем эти таблицы сигнатур сортируются.

Реализация поиска

На этом этапе, после предварительной обработки базы данных мы имеем несколько копий отсортированных таблиц, каждая для своей подстроки.

Очевидно, что если мы хотим сперва найти подстроки, необходимо из запрашиваемой строки получить сигнатуры тем же способом, который был использован при создании таблиц сигнатур.

Так же нам известно, что необходимые подстроки отличаются максимум на один элемент. И чтобы найти их потребуется воспользоваться методом расширения запроса (query expansion).

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

Такие действия надо произвести для всех подстрок и для всех таблиц.

И в самом конце потребуется отфильтровать те строки, которые не вмещаются в заданный предел расстояния Хэмминга. Т.е. произвести линейный поиск по найденным строкам и оставить только те строки, которые отвечают условию HD(a , b ) <= k .

Фильтр Блума

Если перед двоичным поиском подстроки в таблице фильтр возвращает, что эта подстрока не находится в этой таблице, то нет смысла производить поиск.

Соответственно надо создать по одному фильтру на каждую таблицу сигнатур.

Авторы также отмечают, что использование фильтра Блума таким способом снижает время обработки запросов в среднем на 57.8%. На моих тестовых выборках такой фильтр практически не влияет на результирующее время работы. Ощутим только на случайным образом сгенерированной базе данных.

Теперь тоже самое, только на примере

Имеется база данных бинарных строк длиной 8 бит:
11111111
10000001
00111110

Задача найти все строки, где количество отличающихся битов не превышает 2 к целевой строке 10111111.

Значит требуемое расстояние k = 2.

1. Выбираем фактор сегментации.

Исходя из формулы, выбираем фактор сегментации r = 2 и значит всего будет две подстроки из одной строки.

2. Создаем набор сигнатур.

Так как количество подстрок 2, то требуется создать только 2 таблицы:

3. Сохраняем подстроки в соответствующих таблицах с сохранением ссылки на первоисточник.

Т1 Т2
1111 1111 => 11111111
1000 0001 => 10000001
0011 1110 => 00111110

4. Сортируем таблицы. Каждую в отдельности.

Т1
0011 => 00111110
1000 => 10000001
1111 => 11111111

Т2
0001 => 10000001
1110 => 00111110
1111=> 11111111

На этом предварительная обработка закончена. И приступаем к поиску.

5. Получаем сигнатуры запрашиваемой строки.

Искомая строка 10111110 разбивается на сигнатуры. Получается 1011 и 1100, соответственно первая для первой таблицы, а вторая для второй.

6. Генерируем все комбинации отличающихся на единицу.
Количество вариантов будет 5.

6.1 Для первой подстроки 1011:
1011
0 011
11 11
100 1
1010

6.2 Для второй подстроки 1100:
1100
0 100
10 00
111 0
1101

7. Двоичный поиск.

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

1011
0011 == 0011 => 00111110
1111 == 1111 => 11111111
1001
1010

Найдено две подстроки.

7.2 Теперь для всех вариантов второй подстроки 1100 производим двоичный поиск во второй таблице.

1100
0100
1000
1110 == 1110 => 00111110
1101

Найдена одна подстрока.

8. Объедением результаты в один список:
00111110
11111111

9. Линейно проверяем на соответствие и отфильтровываем неподходящие по условию <= 2:

HD(10111110, 00111110) = 1
HD(10111110, 11111111) = 2

Обе строки удовлетворяют условию различия не больше двух элементов.

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

Наглядно

На рисунке №1 показан пример работы алгоритма поиска.
Для длины строки 64 и предел расстояния 4, фактор сегментации равен 3, соответственно только 3 подстроки на строку.
Где T1, T2 и Т3 - это таблицы сигнатур, содержащие только подстроки B1, B2, B3.

Запрашиваемая строка делится на подстроки. Далее для соответствующих подстрок генерируются диапазон сигнатур. И вконце производится двоичный поиск.

Рис 1. Упращенная версия обработки запросов к таблицам сигнатур.

Результаты

Сложность подобного алгоритма в среднем случае O (m (log n + 1)), где n - это общее число строк в базе данных, m - количество двоичных поисков, а log n + 1 двоичный поиск.
В экстремальных случаях может превышать линейную. Например, при условии q = 1 и когда все строки из всех таблицы сигнатур, кроме последней, совпадают с запрашиваемой, то получается O ((r - 1)m n (log n + 1)).

Отмечается, что такой подход использует в 4.65 меньше памяти и на 16 % быстрее, чем предыдущая работа описанная в .

Реализация

Все это конечно заманчиво, но пока не потрогаешь на деле, тяжело оценить масштабы.
Был создан прототип HEngine и протестирован на имеющихся реальных данных.

Tests$ ./matches 7 data/db/table.txt data/query/face2.txt Reading the dataset ........ done. 752420 db hashes and 343 query hashes. Building with 7 hamming distance bound ....... done. Building time: 12.964 seconds Searching HEngine matches ....... found 100 total matches. HEngine query time: 0.228 seconds Searching linear matches ....... found 100 total matches. Linear query time: 6.828 seconds

Результаты обрадовали, т. к. поиск 343 хеша из базы в 752420 занимает ~0.2 секунды, что в 30 раз быстрее линейного поиска.

Казалось бы тут можно было остановиться. Но уж больно хотелось попробовать это использовать как-то в реальном проекте.

В один клик до реального применения

Имеется база данных хешей изображений, и бекенд на PHP.
Задача стояла как-то связать функциональность HEngine и PHP.
Решено было использовать FastCGI , в этом мне сильно помогли посты habrahabr.ru/post/154187/ и habrahabr.ru/post/61532/ .

Из PHP достаточно вызвать:

$list = file_get_contents("http://fcgi.local/?" . $hashes);

Что за примерно 0.5 секунды возвращает результат. Когда линейным поиском требуется 9 сек, а через запросы к MySQL не меньше 20 секунд.

Спасибо всем, кто осилил.

На множестве двоичных слов длины m расстоянием d(a,b) между словами a и b называют число несовпадающих позиций этих слов, например: расстояние между словами a = 01101 и b = 00111 равно 2.

Определенное таким образом понятие называется расстоянием Хемминга.

Оно удовлетворяет следующим аксиомам расстояний:

1) d(a,b)  0 и d(a,b)=0 тогда и только тогда, когда a = b;

2) d(a,b) = d(b,a) ;

3) d(a,b) + d(b,c)  d(a,c) (неравенство треугольника).

Весом w(a) слова a называют число единиц среди его координат. Тогда расстояние между словами a и b есть вес их суммы a b: d(a,b)=w(a b) , где символом  обозначена операция покоординатного сложения по модулю 2. Интуитивно понятно, что код тем лучше приспособлен к обнаружению и исправлению ошибок, чем больше различаются кодовые слова. Понятие расстояния Хемминга позволяет это уточнить.

Теорема Для того, чтобы код позволял обнаруживать ошибки в k (или менее) позициях, необходимо и достаточно, чтобы наименьшее расстояние между кодовыми словами было  k + 1.

Доказательство этой теоремы аналогично доказательству следующего утверждения.

Теорема. Для того, чтобы код позволял исправлять все ошибки в k (или менее) позициях, необходимо и достаточно, чтобы наименьшее расстояние между кодовыми словами было  2k + 1.

32. Теорема о корректирующей способности кодов.

Коды, в которых возможно автоматическое исправление ошибок, называются самокорректирующимися. Для построения самокорректирующегося кода, рассчитанного на исправление одиночных ошибок, одного контрольного разряда недостаточно. Как видно из дальнейшего, количество контрольных разрядов k должно быть выбрано так, чтобы удовлетворялось неравенство 2k≥k+m+1или k≥log2(k+m+1), где m - количество основных двоичных разрядов кодового слова. В настоящее время наибольший интерес представляют двоичные блочные корректирующие коды. При использовании таких кодов информация передаётся в виде блоков одинаковой длины и каждый блок кодируется и декодируется независимо друг от друга. Почти во всех блочных кодах символы можно разделить на информационные и проверочные.

Основными характеристиками самокорректирующихся кодов являются:

1. Число разрешенных и запрещенных комбинаций. Если n - число символов в блоке, r - число проверочных символов в блоке, k - число информационных символов, то 2n - число возможных кодовых комбинаций, 2k - число разрешенных кодовых комбинаций, 2n−2k - число запрещенных комбинаций.

2. Избыточность кода. Величину rn называют избыточностью корректирующего кода.

3. Минимальное кодовое расстояние. Минимальным кодовым расстоянием d называется минимальное число искаженных символов, необходимое для перехода одной разрешенной комбинации в другую.

4. Число обнаруживаемых и исправляемых ошибок. Если g - количество ошибок, которое код способен исправить, то необходимо и достаточно, чтобы d≥2g+1

5. Корректирующие возможности кодов.

33. Матричное кодирование. Групповые коды.

При явном задании схемы кодирования в (m, n)-коде следует указать 2 m кодовых слов, что весьма неэффективно.

Одним из экономных способов описания схемы кодирования является методика матричного кодирования.

Ранее каждая схема кодирования описывалась таблицами, задающими кодовое слово длины n для каждого исходного слова длины m. Для блоков большой длины этот способ требует большого объема памяти и поэтому непрактичен. Например, для (16, 33 )-кода потребуется 33 * 2 16 = 2 162 688 бит.

Гораздо меньшего объема памяти требует матричное кодирование. Пусть E матрица размерности m × n , состоящая из элементов e ij , где i - это номер строки, а j - номер столбца. Каждый из элементов матрицы e ij может быть либо 0, либо 1. Кодирование реализуется операцией b = аЕ или где кодовые слова рассматриваются как векторы, т.е как матрицы-строки размера 1 × n.

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

Матричные коды называют также линейными кодами. Для линейных (n − r, n )-кодов с минимальным расстоянием Хэмминга d существует нижняя граница Плоткина (Plotkin) для минимального количества контрольных разрядов r при n³ 2d − 1 ,

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

Заметим, что множество всех двоичных слов длины m образует коммутативную группу с операцией покоординатного сложения по модулю 2, в которой выполняется соотношение a a. Следовательно, множество слов-сообщений a длины m есть коммутативная группа.

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

Если код является групповым, то наименьшее расстояние между двумя кодовыми словами равно наименьшему весу ненулевого слова.

Это следует из соотношения d(b i , b j ) = w(b i + b j ).

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

Такие строки ошибок переводят одно кодовое слово в другое.

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

Множество всех двоичных слов a = a 1 ... a m длины m образует абелеву (коммутативную) группу относительно поразрядного сложения.

Пусть E - кодирующая m × n -матрица, у которой есть m ×m- подматрица с отличным от нуля определителем, например, единичная. Тогда отображение a → a E переводит группу всех двоичных слов длины m в группу кодовых слов длины n.

Предположим, что Тогда для получаем

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

Свойство группового кода: минимальное кодовое расстояние между кодовыми векторами равно минимальному весу ненулевых векторов. Вес кодового вектора равен числу единиц в кодовой комбинации.

Групповые коды удобно задавать при помощи матриц, размерность которых определяется параметрами k и n. Число строк равно k, а число столбцов равно n = k+m.

Коды, порождаемые этими матрицами, называются (n, k)-кодами, а соответствующие им матрицы порождающими (образующими, производящими).

Cтраница 1

Расстояние Хемминга между двумя последовательностями равной длины соответствует числу позиций, занятых несовпадающими элементами. В случае последовательностей различной длины расстояние Хэмминга определяется как минимальное число позиций, занятых несовпадающими элементами при.

Расстояние Хемминга d (u, v) между двумя словами и и v одинаковой длины равно числу несовпадающих разрядов этих слов. Оно используется в теории блочных кодов (В.

С использованием метрических свойств расстояния Хемминга непосредственно проверяется, что / л является метрикой на Хц, но не является метрикой на множестве смешанно-периодических последовательностей.

Эта функция близости эквивалентна расстоянию Хемминга.

Метрика р в алгоритме KLOP задана расстоянием Хемминга.

Если процедура поиска сможет найти положение, где расстояние Хемминга равно нулю, задача будет решена.

Сопоставление нечетких подмножеств В и В3, степеней нечеткости, а также расстояния Хемминга показывает, что рассматриваемые нечеткие подмножества отличаются. Однако если в качестве рассчитанного значения принимать элемент м2 G Uz, степень принадлежности которого полученному нечеткому подмножеству максимальна, то применение нечеткого отношения R, вычисленного таким способом, может быть оправдано. Наряду с тем, что при данном подходе удается описать нелинейность связи между максимальной температурой во второй зоне реактора и показателем текучести расплава полиэтилена, этот способ не учитывает нестационарность процесса получения ПЭВД, которая связана с изменением характеристик технологического процесса.

Передаточная функция этого кода указывает на то, что имеется единственный путь с расстоянием Хемминга d - от пути из одних нулей, который сливается с путем из одних нулей при данном узле. Из диаграммы состояний, показанной на рис. 8.2.6, или решетчатой диаграммы, показанной на рис. 8.2.5, видно, что путь с d6 это acbe. Снова из диаграммы состояний или решетки мы видим, что этими путями являются acdbe и acbcbe. Третье слагаемое в (8.1.2) указывает, что есть четыре пути с расстоянием d 0 и так далее. Таким образом, передаточная функция дает нам дистанционные свойства сверточного кода.

Этот результат согласуется с наблюдением, что путь из одних нулей (/ 0) имеет расстояние Хемминга d3 от принимаемой последовательности, в то время как путь с / 1 имеет расстояние Хемминга d5 от принимаемого пути. Таким образом, расстояние Хемминга является эквивалентной метрикой для декодирования с жестким решением.

Расстояние Хемминга

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

Определение 13.1. Рассмотрим на множестве всех двоичных слов в алфавите В = {0,1} длины т расстояние d (x , у ), которое равно числу несовпадающих позиций этих слов. Например, Для слов х = 011101, у = 101010 расстояние равно d (x , y ) = 5. Это расстояние носит название расстояние Хемминга .

Можно показать, что расстояние Хемминга удовлетворяет аксиомам метрического пространства:

1) d (x , у ) ≥ 0, d (x , у ) = 0 тогда и только тогда, когда х = у;

2) d (x , y ) = d (y , x );

3) d (x , у ) ≤ d (x , z ) + d (z , у ) - неравенство треугольника.

Теорема 13.1 (об обнаруживающем коде ). Код является обнаруживающим в случае, когда в передаваемом слове имеется не более чем k

d (b 1, b 2) ≥ k + 1.

Теорема 13.2 (об исправляющем коде .). Код является исправляющим все ошибки в случае, когда в передаваемом слове имеется не более k ошибок, тогда и только тогда, когда наименьшее расстояние между кодовыми словами

d (b 1, b 2) ≥ 2k + 1.

Доказательство . Доказательства этих теорем аналогичны. Поэтому докажем только последнюю теорему.

Достаточность . Пусть для любых кодовых слов имеем d (b 1, b 2) ≥ 2k + 1. Если при передаче кодового слова b 1произошло не более k ошибок, то для принятого слова с имеем d (b 1, c ) ≤ k . Но из неравенства треугольника для любого другого кодового слова b 2имеем d (b 1, с ) + d (c , b 2) ≥ d (b 1, b 2) ≥ 2 k + 1. Следовательно, от принятого слова до любого другого кодового слова расстояние d (c , b 2) ≥ k + 1, т. е. больше, чем до b 1. Поэтому по принятому слову с можно однозначно найти ближайшее кодовое слово b 1и далее декодировать его.

Необходимость . От противного. Предположим, что минимальное расстояние между кодовыми словами меньше, чем 2 k + 1. Тогда найдутся два кодовых слова, расстояние между которыми будет d (b 1, b 2) ≤ 2 k . Пусть при передаче слова b 1принятое слово с находится на отрезке между словами b 1, b 2и имеет ровно k ошибок. Тогда d (c , b 1) = k , d (c , b 2) = d (b 1, b 2) – d (c , b 1) ≤ k . Тем самым по слову с нельзя однозначно восстановить кодовое слово, которое было передано, b 1или b 2. Пришли к противоречию.

Пример 13 .3 . Рассмотрим следующие пятиразрядные коды слов длиной 2 в алфавите В = {0,1}:

b 1= K (00) = 00000, b 2= K (01) = 01011,

b 3= K (10) = 10101, b 4= k (11) =11110.

Минимальное расстояние между различными кодовыми словами равно d (bi , bj ) = 3. В силу первой теоремы об обнаруживающем коде, этот код способен обнаруживать не более двух ошибок в слове. В силу второй теоремы, код способен исправлять не более одной ошибки в слове.

Групповые коды

Рассмотрим подробнее коды слов в алфавите В = {0, 1}. Если для слов длиной т используются кодовые слова длиной n , то такие коды будем называть (т , п )-коды. Всего слов длиной m равно 2 m . Чтобы задать (т , п )-код, можно перечислить кодовые слова для всех возможных слов длиной m , как в предыдущем примере. Более экономным способом задания кодовых слов является матричное задание.

В этом случае задается порождающая матрица G = ∣∣ gij ∣∣ порядка т × п из 0 и 1. Кодовые слова определяются каждый раз по слову а = а 1a 2... ат путем умножения этого слова слева, как вектора, на порождающую матрицу

Здесь сложение определяется по модулю 2. Для того чтобы разным словам соответствовали разные кодовые слова, достаточно иметь в матрице G единичный базисный минор порядка т , например крайний левый.

Пример 13 .4 . Рассмотрим порождающую матрицу

Эта матрица задает (3, 4)-код. При этом три первые символа в кодовом слове информационные, а четвертый - контрольный. Он равен 0, если четное число единиц в исходном слове, и 1, если нечетное число единиц. Например, для слова а = 101 кодом будет b = aG = 1010. Минимальное расстояние Хемминга между кодовыми словами равно d (bi , bj ) = 2. Поэтому это - код, обнаруживающий однократную ошибку.

Определение 13.2. Код называется групповым , если множество всех кодовых слов образует группу. Число единиц в слове а называется весам слова и обозначается Если b - кодовое слово и принятое в канале связи слово с = b + е , то слово е называется вектором ошибок .

Теорема 13.3. Пусть имеется групповой (т , п )-код. Тогда коммутативная группа К всех кодовых слов является подгруппой коммутативной группы С всех слов длины п , которые могут быть приняты в канале связи. Наименьшее расстояние между кодовыми словами равно наименьшему весу ненулевого кодового слова и

Рассмотрим фактор-группу С / K . Смежные классы здесь будут определяться сдвигом е + b , b ∈ K .

В качестве представителя смежного класса выберем элемент с наименьшим весом. Будем такие элементы называть лидерами смежного класса .

Если лидеры трактовать как векторы ошибок, то каждый смежный класс - множество искаженных слов в канале связи с фиксированным вектором ошибок, в частности при е = 0 имеем смежный класс слов без искажений, т. е. множество всех кодовых слов. Процесс коррекции и декодирования слова с заключается в поиске того смежного класса, к которому относится слово с = е + b . Вектор ошибок е определяет число и локализацию ошибок, кодовое слово b определяет коррекцию принятого слова.

Чтобы облегчить поиск смежного класса и тем самым вектора ошибок, Хемминг предложил использовать групповые коды со специальными порождающими матрицами.

Хемминговы коды

Рассмотрим построение хеммингова (т , п )-кода с наименьшим весом кодового слова равным 3, т. е. кода, исправляющего одну ошибку.

Положим п = 2 r – 1 и пусть в каждом кодовом слове будут r символов контрольными, а т символов (т = п – r = 2 r – 1– r ) - информационными, r ≥ 2, например (1, 3)-код, (4, 7)-код и т. д. При этом в каждом кодовом слове b = b 1b 2... b п символы с индексами, равными степени 2, будут контрольными, а остальные информационными. Например, для (4, 7)-кода в кодовом слове b = b 1b 2b 3b 4b 5b 6b 7 символы b 1b 2b 4будут контрольными, а символы b 3b 5b 6b 7- информационными. Чтобы задать порождающую матрицу G хеммингова (т , п )-кода, рассмотрим вспомогательную матрицу М порядка r × п , где п = 2 r – 1, такую, что в каждом j столбце матрицы М будут стоять символы двоичного разложения числа j , например для (4, 7)-кода матрица М будет 3 × 7:

Множество всех кодовых слов зададим как множество решений однородной системы линейных алгебраических уравнений вида

b МТ = 0.

Например, для (4, 7)-кода такая система будет:

Выберем естественный базисный минор системы b МТ = 0, стоящий в столбцах с номерами, равными степени 2. Тем самым переменные разделим на базисные (кодовые) и свободные (информационные). Теперь, задав свободные переменные, легко получить базисные. Найдем фундаментальную систему m = п – r решений этой однородной системы. Тогда любое решение системы есть линейная комбинация этих m решений. Поэтому, выписав построчно m решений фундаментальной системы в виде матрицы G размером m × п , получим порождающую матрицу хеммингова группового (т , п )-кода, например для (4, 7)-кода фундаментальной системой решений будут 4 = 7 – 3 следующих решения однородной системы:

g 1= 1110000, g 2= 1001100, g 3= 0101010, g 4= 1101001.

Любая линейная комбинация этих решений будет решением, т. е. кодовым словом. Составим из этих фундаментальных решений порождающую матрицу

Теперь по любому слову а длиной т = 4 легко вычислить кодовое слово b длиной п = 7 при помощи порождающей матрицы b = aG . При этом символы b 3, b 5, b 6, b 7будут информационными. Они совпадают с а 1, а 1, а 3, а 4.Символы b 1, b 2, b 4 будут контрольными.

Вывод . Хемминговы коды удобны тем, что при декодировании легко определяются классы смежности. Пусть принятое по каналу связи слово будет с = е + b , где е - ошибка, b - кодовое слово. Тогда умножим его на вспомогательную матрицу сМТ = (е + b )МТ = еМ T . Если еМ T = 0, то слово с - кодовое и считаем: ошибки нет. Если еМ T ≠ 0, то слово е определяет ошибку.

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

Например, пусть принятое слово будет с = 1100011 для (4, 7)-кода Хемминга. Умножим это слово на матрицу М T . Получим

(1100011}М T =(010).

Следовательно, есть ошибка во втором символе. Поэтому кодовое слово будет b = 1000011. Вычеркнем контрольные символы b 1, b 2, b 4.Декодированное слово будет а = 0011.

Конечно, если ошибка была допущена более чем в одном символе, то этот код ее не исправит.

Обработка изображений

Tutorial

Введение

Описание проблемы

Задача сводится к поиску всех строк, которые находятся в пределах расстояния k .

В оригинальной концепции алгоритма рассматривается два варианта задачи: статическая и динамическая.

В статической задачи расстояние k предопределено заранее.
- В динамической, наоборот, требуемое расстояние заранее неизвестно.

В статье описывается решение только статической задачи.

Описание алгоритма HEngine для статической задачи

Данная реализация фокусируется на поиске строк в пределах k <= 10.

Немного теории

Алгоритм базируется на небольшой теореме, которая гласит следующее:

Если для двух строк a и b расстояние HD(a , b ) <= k , то если поделить строки a и b на подстроки методом rcut используя фактор сегментации
r >= ⌊k /2⌋ + 1
обязательно найдется, по крайней мере, q = r − ⌊k /2⌋ подстрок, когда их расстояние не будет превышать единицу, HD(a i, b i) <= 1.

Теперь тоже самое, только на примере:

A1 = 1111, a2 = 0000
b1 = 1101, b2 = 0001

Если мы сейчас подсчитаем расстояние между соответствующими подстроками, то, по крайней мере, (q = 2 - 2/2 = 1) одна подстрока совпадет или их расстояние не будет превышать единицу.

Что и видим:
HD(a1, b1) = HD(1111, 1101) = 1
и
HD(a2, b2) = HD(0000, 0001) = 1

Предварительная обработка базы данных

Но как производить поиск по подстрокам?

Затем эти таблицы сигнатур сортируются.

Реализация поиска

Такие действия надо произвести для всех подстрок и для всех таблиц.

Фильтр Блума

Авторы предлагают использовать фильтр Блума для уменьшения количества двоичных поисков.
Фильтр Блума может быстро определить находится ли подстрока в таблице с небольшим процентом ложных срабатываний. Что работает быстрее, чем хеш таблицы.

Соответственно надо создать по одному фильтру на каждую таблицу сигнатур.

Теперь тоже самое, только на примере

Имеется база данных бинарных строк длиной 8 бит:
11111111
10000001
00111110

Задача найти все строки, где количество отличающихся битов не превышает 2 к целевой строке 10111111.
Значит требуемое расстояние k = 2.

1. Выбираем фактор сегментации.
Исходя из формулы, выбираем фактор сегментации r = 2 и значит всего будет две подстроки из одной строки.

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

3. Сохраняем подстроки в соответствующих таблицах с сохранением ссылки на первоисточник.

Т1 Т2
1111 1111 => 11111111
1000 0001 => 10000001
0011 1110 => 00111110

4. Сортируем таблицы. Каждую в отдельности.
Т1
0011 => 00111110
1000 => 10000001
1111 => 11111111

Т2
0001 => 10000001
1110 => 00111110
1111=> 11111111

На этом предварительная обработка закончена. И приступаем к поиску.

1. Получаем сигнатуры запрашиваемой строки.
Искомая строка 10111110 разбивается на сигнатуры. Получается 1011 и 1100, соответственно первая для первой таблицы, а вторая для второй.

2. Генерируем все комбинации отличающихся на единицу.
Количество вариантов будет 5.

2.1 Для первой подстроки 1011:
1011
0 011
11 11
100 1
1010

2.2 Для второй подстроки 1100:
1100
0 100
10 00
111 0
1101

3. Двоичный поиск.

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

1011
0011 == 0011 => 00111110
1111 == 1111 => 11111111
1001
1010

Найдено две подстроки.

3.2 Теперь для всех вариантов второй подстроки 1100 производим двоичный поиск во второй таблице.

1100
0100
1000
1110 == 1110 => 00111110
1101

Найдена одна подстрока.

4. Объедением результаты в один список:
00111110
11111111

5. Линейно проверяем на соответствие и отфильтровываем неподходящие по условию <= 2:

HD(10111110, 00111110) = 1
HD(10111110, 11111111) = 2

Обе строки удовлетворяют условию различия не больше двух элементов.

Наглядно

Запрашиваемая строка делится на подстроки. Далее для соответствующих подстрок генерируются диапазон сигнатур. Для первой и второй сигнатуры количество комбинаций будет 22. А последняя сигнатура дает 23 варианта. И вконце производится двоичный поиск.

Рис 1. Упращенная версия обработки запросов к таблицам сигнатур.

Результаты

Сложность подобного алгоритма в среднем случае O (P * (log n + 1)), где n - это общее число строк в базе данных, log n + 1 двоичный поиск, а P - количество двоичных поисков: считается, в нашем случае, как количество комбинаций на таблицу умнеженное на количество таблиц: P = (64 / r + 1) * r

В экстремальных случаях сложность может превышать линейную.

Отмечается, что такой подход использует в 4.65 меньше памяти и на 16 % быстрее, чем предыдущая работа описанная в . И является самым быстрым способом из ныне известных, чтобы найти все строки в заданном пределе.

Реализация

Tests$ ./matches 7 data/db/table.txt data/query/face2.txt Reading the dataset ........ done. 752420 db hashes and 343 query hashes. Building with 7 hamming distance bound ....... done. Building time: 12.964 seconds Searching HEngine matches ....... found 100 total matches. HEngine query time: 0.1 seconds Searching linear matches ....... found 100 total matches. Linear query time: 6.828 seconds

Результаты обрадовали, т. к. поиск 343 хешей из базы в 752420 занимает ~0.1 секунды, что в 60 раз быстрее линейного поиска.

Из PHP достаточно вызвать:
$list = file_get_contents("http://fcgi.local/?" . $hashes);
Что за ~0.5 секунды возвращает результат. Когда линейным поиском требуется 9 секунд, а через запросы к MySQL не меньше 20 секунд.

Спасибо всем, кто осилил.

Ссылки

M. Minsky and S. Papert. Perceptrons. MIT Press, Cambridge, MA, 1969.
G. S. Manku, A. Jain, and A. D. Sarma. Detecting nearduplicates for web crawling. In Proc. 16Th WWW, May 2007.
M. L. Miller, M. A. Rodriguez, and I. J. Cox. Audio fingerprinting: Nearest neighbor search in high-dimensional binary space. In MMSP, 2002.
M. L. Miller, M. A. Rodriguez, and I. J. Cox. Audio fingerprinting: nearest neighbor search in high dimensional binary spaces. Journal of VLSI Signal Processing, Springer, 41(3):285–291, 2005.
J. Landr ́e and F. Truchetet. Image retrieval with binary hamming distance. In Proc. 2nd VISAPP, 2007.
H. Yang and Y. Wang. A LBP-based face recognition method with hamming distance constraint. In Proc. Fourth ICIG, 2007.
B. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of ACM, 13(7):422–426, 1970.
Alex X. Liu, Ke Shen, Eric Torng. Large Scale Hamming Distance Query Processing. ICDE Conference, pages 553 - 564, 2011.
github.com/valbok/HEngine Моя реализация HEngine на С++ Добавить метки