Подсчет расстояния хэмминга на большом наборе данных

3.9 Вес и расстояние Хэмминга. Способность кодов обнаруживать и исправлять ошибки – Теория информации – Конспект лекций

3.9  Вес и расстояние Хэмминга. Способность кодов обнаруживать и исправлять ошибки

Пусть u=(u1, u2, …, un) – двоичная последовательность длиной n.

Число единиц в этой последовательности называется весом Хэмминга вектораuи обозначается как w(u).

Например: u=(1 0 0 1 0 1 1), тогда w(u)=4.

Пусть u и v – двоичные слова длинойn.

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

Обратите внимание

Например: u=(1 0 0 1 0 1 1), v=(0 1 0 0 0 1 1), тогда d(u, v)=3.

Легко видеть, что расстояние между двоичными последовательностями u и v  равно весу их поразрядной суммы, т. е.

d(u,v)=w(u+v).                                      (3.9)

Вероятность того, что слово v будет принято за u, равна

Рош=рn–d(u, v)×qd(u, v),                                  (3.10)

где p – вероятность правильной передачи бита сообщения; q=1–p– вероятность ошибки.

Задав линейный код, т. е., определив все 2k кодовые слова, можно определить расстояние между всеми возможными парами кодовых слов, минимальное из них называется минимальным кодовым расстоянием dmin.

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

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

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

Для обнаружения кодом ошибок кратности не больше l необходимо и достаточно, чтобы минимальное  расстояние между его словами было l+1:

dmin≥ l+1 .                                            (3.11)

Для исправления кодом  ошибок кратности, не больше l, необходимо и достаточно, чтобы наименьшее расстояние между его словами было 2l+1:

dmin ≥ 2l+1.                                                      (3.12)

Установлено, что в линейном (k, n)-коде,минимальное расстояние между кодовыми словами которого равно 2l+1, значенияn– длины кодовой последовательности,r=n–k– числа дополнительных разрядов иl– кратности ошибки, обнаруживаемой кодом, должны соответствовать неравенству

,                     (3.13)        

которое называется нижней границей Хэмминга.

Важно

Кроме того, если параметры n, rиlсоответствуют неравенству

,             (3.14)

которое называется верхней границей Варшамова-Гильберта, то существует (n–r, n)-код, исправляющий все ошибки весаlи менее.

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

Верхняя граница задаёт достаточные условиядля существования помехоустойчивого кода.

Для линейных блочных (k, n)-кодов с минимальным расстоянием dminсуществует нижняя граница Плоткина, устанавливающая минимальное количество проверочных символов r при n≥ 2dmin–1:

.                                (3.15)

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

1)    количество исходных кодовых комбинаций (число строк)порождающейматрицы равно k, т. е. количеству информационных элементов;

2)    все кодовые комбинации порождающей матрицы должны быть различны, причём нулевая комбинация в их состав не включается;

3)    все кодовые комбинации порождающей матрицы линейно независимы;

4)    количество единиц в каждой кодовой комбинации порождающей матрицы должно быть ³dmin;

5)    кодовое расстояние между какими-либо парами кодовых слов должно быть ³dmin.

Совет

Таким образом, порождающая матрица линейного систематического блочного кода составляется из двух подматриц: информационной подматрицы Ik×k (которую удобно представлять в виде единичной матрицы) и проверочной подматрицы Рk´r.

Проверочная подматрица Pk´(n–k) составляется подбором r-разрядных комбинаций с количеством единиц в строке ≥ dmin-1 и кодовым  расстоянием между строками  ≥  dmin-2.

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Подсчет расстояния Хэмминга на большом комплекте данных

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

Вступление

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

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

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

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

Скажем, Manku и сотоварищи предложили решение задачи кластеризации дубликатов при индексации веб документов на основе подсчета расстояния Хэмминга [2]. Также Miller и друзья предложили доктрину поиска песен по заданному аудио фрагменту [3], [4].

Сходственные решения были использованы и для задачи поиска изображений и идентификация сетчатки [5], [6] и т.д.

Изложение задачи

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

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

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

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

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

Изложение алгорифма HEngine для статической задачи

Данная реализация фокусируется на поиске строк в пределах k mark!Для длины строки 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 )mn( log n 1 ) ).

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

Реализация

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

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 [10], в этом мне крепко помогли посты habrahabr.ru/post/154187/ иhabrahabr.ru/post/61532/.

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

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

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

Спасибо каждому, кто осилил.

Ссылки

[1] M. Minsky and S. Papert. Perceptrons. MIT Press, Cambridge, MA, 1969. [2] G. S. Manku, A. Jain, and A. D. Sarma. Detecting nearduplicates for web crawling. In Proc. 16Th WWW, May 2007. [3] M. L. Miller, M. A. Rodriguez, and I. J. Cox.

Audio fingerprinting: Nearest neighbor search in high-dimensional binary space. In MMSP, 2002. [4] 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.

[5] J. Landr

Эффективно находите двоичные строки с низким расстоянием Хэмминга в большом наборе

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

Если вы работаете с файлами, вы создаете столько файлов, сколько у вас есть куски (например, здесь 4), причем каждый фрагмент переставляется впереди, а затем сортирует файлы.

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

Обратите внимание

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

Итак, чтобы повторить: скажите, что у вас есть куча 32-битных строк в БД или файлах и что вы хотите найти каждый хеш, находящийся в пределах 3-х битного расстояния или меньше вашей битовой строки запроса:

• создать таблицу с четырьмя столбцами: каждая из них будет содержать 8 бит (как строку или int) фрагмент хэшей 32 бит, islice 1 – 4. Или, если вы используете файлы, создайте четыре файла, каждый из которых будет перестановка срезов, имеющих одну “изоляцию” в передней части каждой “строки”
• отрежьте строку запроса так же, как в qslice с 1 по 4.
• запросить эту таблицу, чтобы любой из qslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4. Это дает вам каждую строку, которая находится в пределах 7 бит (8 – 1) строки запроса. Если вы используете файл, выполните двоичный поиск в каждом из четырех перестановленных файлов для тех же результатов.
• для каждой возвращаемой битовой строки, вычислите точное расстояние хамминга с помощью битовой строки запроса (восстановление битовых строк на стороне индекса из четырех фрагментов либо из БД, либо из перестановленного файла)

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

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

Если вы работаете в памяти вместо файлов, ваш набор данных длиной 100 Мбит 32 бит будет находиться в диапазоне 4 ГБ. Следовательно, для четырех переписанных списков может потребоваться около 16 ГБ + ОЗУ. Хотя я получаю отличные результаты с файлами с отображением памяти вместо этого и должен иметь меньше ОЗУ для аналогичных наборов данных размера.

Доступны версии с открытым исходным кодом. Лучшим в пространстве является IMHO, сделанный для Simhash by Moz, С++, но предназначен для 64-битных строк, а не 32 бит.

algorithm python java модифицированный – Эффективно находите двоичные строки с низким расстоянием Хэмминга в большом наборе

Вопрос: Что мы знаем о расстоянии Хэмминга d (x, y)?

Ответ:

Он неотрицателен: d (x, y) ≥ 0

Он равен нулю только для одинаковых входов: d (x, y) = 0 ⇔ x = y

Он симметричен: d (x, y) = d (y, x)

Он подчиняется неравенству треугольника , d (x, z) ≤ d (x, y) + d (y, z)

Вопрос: Почему нас это волнует?

Ответ. Потому что это означает, что расстояние Хэмминга является метрикой для метрического пространства . Существуют алгоритмы индексирования метрических пространств.

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

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

static inline int distance(unsigned x, unsigned y)
{ return __builtin_popcount(x^y);
}

Если вы затем сообщите GCC, что вы компилируете для компьютера с SSE4a, то я считаю, что это должно сводиться только к парам операций opcodes.

Редактировать: в соответствии с рядом источников это иногда / часто медленнее, чем обычный код маски / сдвига / добавления. Бенчмаркинг показывает, что в моей системе версия C-версии превосходит GCC __builtin_popcount примерно на 160%.

Добавление: мне было очень интересно узнать о проблеме, поэтому я профилировал три реализации: линейный поиск, дерево BK и дерево VP. Обратите внимание, что деревья VP и BK очень похожи.

Дети узла в дереве BK являются «оболочками» деревьев, содержащих точки, каждый из которых имеет фиксированное расстояние от центра дерева. Узел в дереве VP имеет двух детей, один из которых содержит все точки внутри сферы, центрированной на центре узла, а другой дочерний элемент, содержащий все внешние точки.

Важно

Таким образом, вы можете представить узел VP как узел BK с двумя очень толстыми «оболочками» вместо многих более мелких.

Результаты были зафиксированы на моем ПК с частотой 3,2 ГГц, и алгоритмы не пытаются использовать несколько ядер (что должно быть легко). Я выбрал размер базы данных из 100 М псевдослучайных целых чисел. Результатом является среднее число 1000 запросов для расстояния 1..5 и 100 запросов для 6..10 и линейный поиск.

• База данных: 100 М псевдослучайные целые числа
• Количество испытаний: 1000 для расстояния 1..5, 100 для расстояния 6..10 и линейного
• Результаты: Среднее число запросов (очень приблизительное)
• Скорость: количество запросов в секунду
• Покрытие: Средний процент проверенных баз данных на запрос

— BK Tree — — VP Tree — — Linear —
Dist Results Speed Cov Speed Cov Speed Cov
1 0.90 3800 0.048% 4200 0.048%
2 11 300 0.68% 330 0.65%
3 130 56 3.8% 63 3.4%
4 970 18 12% 22 10%
5 5700 8.5 26% 10 22%
6 2.6e4 5.2 42% 6.0 37%
7 1.1e5 3.7 60% 4.1 54%
8 3.5e5 3.0 74% 3.2 70%
9 1.0e6 2.6 85% 2.7 82%
10 2.5e6 2.3 91% 2.4 90%
any 2.2 100%

В своем комментарии вы упомянули:

Я думаю, что это именно то, почему дерево VP работает (немного) лучше, чем дерево BK. Будучи «более глубоким», а не «более мелким», он сравнивается с большим количеством очков, а не с использованием более тонких сравнений против меньшего количества очков. Я подозреваю, что различия более экстремальны в пространствах более высокого размера.

Последний совет: узлы листа в дереве должны быть просто плоскими массивами целых чисел для линейного сканирования. Для небольших наборов (возможно, 1000 точек или меньше) это будет быстрее и эффективнее.

Вопрос: Как найти ближайшие пары (расстояние Хэмминга) строки бинарных ящиков в Ruby без проблем O ^ 2?

У меня есть MongoDB с около 1 миллионами документов. Все эти документы содержат строку, представляющую 256-битный бит 1 с и 0, например:

0110101010101010110101010101

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

В настоящее время это не поддерживается в Монго. Итак, я вынужден сделать это на прикладном уровне.

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

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

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

Любые мысли будут оценены.

9

2018-01-04 21:06

источник

Ответы:

Я закончил работу по извлечению всех документов в память .. (подмножество с идентификатором и строкой).

Затем я использовал BK Tree  для сравнения строк.

6

2018-01-05 19:13

Расстояние Хэмминга определяет метрическое пространство , поэтому вы можете использовать алгоритм O (n log n) для найти ближайшую пару точек , который имеет типичный характер «разделяй и властвуй».

Затем вы можете применить это повторно до тех пор, пока у вас не будет достаточно пар.

Редактировать:  Теперь я вижу, что Википедия фактически не дает алгоритма, поэтому вот одно описание ,

Изменить 2:  Алгоритм может быть изменен, чтобы отказаться, если нет пар на расстоянии меньше, чем n, Для случая расстояния Хэмминга: просто подсчитайте уровень рекурсии, в которой вы находитесь.

Совет

Если вы не нашли что-то на уровне n в любом филиале, тогда сдайтесь (другими словами, никогда не вводите n + 1).

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

4

2018-01-04 21:18

Насколько я понял, у вас есть строка ввода X и вы хотите запросить базу данных для документа, содержащего поле строки b так что расстояние Хэмминга между X а также document.b меньше небольшого числа d,

Вы можете сделать это в линейное время , просто просмотрев все ваши N= 1M документов и вычисление расстояния (которое занимает небольшое фиксированное время для каждого документа). Поскольку вам нужны документы с расстоянием меньше, чем d, вы можете отказаться от сравнения после d непревзойденные символы; вам нужно всего лишь сравнить все 256 символов, если большинство из них совпадают.

Вы можете попробовать сканировать меньше, чем N документов, то есть получить лучше, чем линейное время ,

Позволять ones(s) быть числом 1s в строке s, Для каждого документа храните ones(document.b) как новое индексированное поле ones_count, Затем вы можете запрашивать документы только в том случае, если число из них достаточно близко к ones(X), в частности, ones(X) – d 

Поиск изображений по фрагменту

В своем выступлении Александр Крайнов рассказал каким способом Яндекс.Картинки кластеризировали дубликаты изображений. Другими словами, выделяли и отфильтровывали дубли картинок.

Где основная идея была в том, чтобы выделить контуры изображения посредством фильтра DoG, после чего найти ключевые точки и получить их дескрипторы. Кластеризация дубликатов сводится к поиску совпадений дескрипторов.

Обратите внимание

Это и есть «цифровой формат» ключевых точек из статьи Кластеризация дубликатов в поиске по картинкам.

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

Дескрипторы

Ключевые точки — это точки, которые в идеале не должны меняться при изменении или модификации изображения. Дескрипторы — это, в общем виде, свертка характеристик и представление ключевых точек в формате доступном для проверки на совпадение.

Поиск эффективного выделения ключевых точек, их дескрипторов, а также методов проверки на совпадения, все еще остается на повестке дня.

Но надо с чего-то начинать, поэтому обратимся на помощь к библиотеке OpenCV.

Первое на что бросается взгляд — это дескрипторы SURF. Которые обещают необычайную точность. Что и подтверждается после тестов.

Но есть несколько нюансов. Дескрипторы SURF — это вектора из 128 (или 64) чисел на одну ключевую точку. Проверка на совпадение выполняется поиском ближайшей точки (или даже двух). И чем ближе точка, тем лучше.

Получается что на изображение с 1 000 ключевых точек, потребуется 128 000 чисел с плавающей точкой. Кроме того, само обнаружение точек довольно сложная операция и требует значительное время. Что не позволяет эффективно использовать данный алгоритм на небольших устройствах. К тому же сам алгоритм закрытый и запатентован (в США).

После ознакомления с SIFT и SURF, захотелось чего-то простого в реализации с возможностью применить на небольшом сервере либо устройстве.

Перцептивные хеши

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

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

Данный метод рассчитан на поиск полных либо частичных дубликатов изображения. Т.е. при значительном изменении формата изображения либо вмешательство в контент приводит к невозможности проверки на совпадение, так как хеши будут заметно отличаться.

Другими словами перцептивные хеши не годятся для поиска полудубликатов.

Важно

Исходя из этого была предпринята попытка объединить SURF дескрипторы и перцептивные хеши с целью решить проблему поиска нечетких полудубликатов.

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

У данного метода есть два с половиной значительных недостатка: 1. низкая скорость проверки на совпадение на большом наборе хешей. Поиск по 1 млн хешей занимало 20 секунд 2. низкая скорость получения ключевых точек 3. низкая точность, множество ложных срабатываний, высокие требование к целевой базе, годится не для всех картинок, требует премодерации и т.д

Сама идея о том, что бы из изображения выделялось некоторое количество отпечатков (fingerprint), которые можно было бы просто сопоставить друг с другом, завораживала.

Поэтому было решено попытаться найти решения данным проблемам.

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

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

Был выбран и реализован наиболее эффективный из имеющихся алгоритм названный HEngine, который позволил в ~60 раз ускорить выборку из базы данных.

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

В общем виде OpenCV предоставляет два типа дескрипторов:

— Дескрипторы с плавающей точкой — И бинарные дескрипторы

Совет

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

ORB: an efficient alternative to SIFT or SURF OpenCV уже имеет у себя отличную альтернативу SURF, которая мало того, что открытая и без лицензионных ограничений, так еще легче и работает быстрее [1].

ORB — это Oriented FAST and Rotated BRIEF — улучшенная версия и комбинация детектора ключевых точек FAST и бинарных дескрипторов BRIEF.

ORB имеет один существенный нюанс для нас — размер дескрипторов 32 байта на одну точку. Проверка на совпадение — это сумма расстояний Хэмминга для каждого байта дескриптора (первый сравнивается с первым, второй со вторым и тд).

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

Так как наш хеш это 64битное число, то требуется 32 байта дескриптора ужать в 8 байт и при этом не сильно потерять в точности.

После некоторых тестов было решено попробовать эти 32 байта представить в виде матрицы 16×16 бит. А потом эту матрицу пропустить через перцептивный хеш PHash. Результатом должно было оказаться как раз 64 битное число.

Теперь мы подошли к полному описанию концепта.

Как работает индексация

1. Получаем ключевые точки и дескрипторы ORB, выбираем количество требуемых точек на изображении. 2. Полученные дескрипторы по 32 байта представляем в виде битовой матрицы 16×16. 3. Конвертируем матрицу в 64битное число с помощью PHash. 4. Сохраняем 64битные отпечатки в MySQL. 5. Выбираем требуемое расстояние Хэмминга и запускаем демон HEngine, который будет выполнять поиск.

Как работает поиск

Выполняем идентичные шаги 1 — 3 из индексации, но только на запрашиваемом изображении. 4. Делаем запрос демону HEngine, который возвращает все хеши в заданном пределе. 5. Если требуется, отфильтровать неактуальные результаты.

Рис 1. Предел расстояния Хэмминга 7. Серые точки — это найденные ключевые точки. Зеленые — совпадающие точки. Красные — совпадающие стандартным ORB полным перебором.

А что в итоге?

В итоге удалось решить нескольких проблем: — найти способ быстрого подсчета расстояния Хэмминга на большом наборе данных — избавиться от большого и неудобного SURF — увеличить скорость выделения ключевых точек и их отпечатков — а также не потерять сильно в точности.

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

Рис 2. Сладкое к пятнице

Учитывая то, что в зависимости от настроек, описанный алгоритм через бинарные дескрипторы ORB выдает около 1 000 хешей на картинку. На базу в 1 000 изображений получается 1 000 000 хешей в базе. Поиск и кластеризация всех дубликатов занимает полторы минуты. Включает в себя полный перебор и поиск совпадающих хешей.

Обратите внимание

Ссылки [1] Ethan Rublee, Vincent Rabaud, Kurt Konolige, Gary R. Bradski: ORB: An efficient alternative to SIFT or SURF. ICCV 2011: 2564-2571. [2] en.wikipedia.org/wiki/SURF [3] ru.wikipedia.org/wiki/Расстояние_Хэмминга [4] phash.org/ [5] habrahabr.

ru/post/143667/ Кластеризация дубликатов в Яндекс.Картинках [6] habrahabr.ru/post/211264/ HEngine — алгоритм поиска хешей в пределах заданного расстояния Хэмминга на большом наборе данных [7] github.com/valbok/img.

chk Мой прототип поиска по фрагментам

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

страница 1

Статья по информатике из журнала МИФ-2 №1 за 2003 год

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

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

Понятие кодирования достаточно универсально, так как этот процесс используется на всех этапах обработки информации: при сборе, передаче, обработке, хранении и представлении.

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

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

Кодирование информации можно рассматривать как в широком, так и в узком смысле слова.

В широком смысле кодирование информации – это представление сведений в той или иной стандартной форме.

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

Важно

При любых видах работы с информацией всегда идет речь о ее представлении в виде определенных символьных структур. Наиболее распространены одномерные представления информации, при которых сообщения имеют вид последовательностей символов. Так информация представляется в письменных текстах, при передаче по каналам связи, в памяти ЭВМ.

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

Часто термин «кодирование» употребляется в более узком смысле.

Кодирование в узком смысле слова подразумевает представление сообщения в форме, удобной для передачи по некоторому каналу связи.

В теории передачи информации важным является решение проблемы кодирования и декодирования, обеспечивающее надежную передачу по каналам связи с «шумом»1.

Наша основная цель – знакомство с методами построения эффективных схем кодирования информации для передачи по реальным каналам с «шумами».

Информационное сообщение всегда связано с источником информации, приемником информации и каналом передачи.

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

Источник информации
Канал связи
Приемник информации

Рис.1 Информационная модель канала связи Чтобы передать информацию, её необходимо предварительно преобразовать.

Кодирование – это преобразование сообщения в форму, удобную для передачи по каналу связи.

Пример: передача сообщения в виде телеграммы. Все символы кодируются с помощью телеграфного кода.

Декодирование – операция восстановления принятого сообщения.

В систему связи необходимо ввести устройства для кодирования и декодирования информации.

Источник информации
Кодер
Декодер
Получатель (приемник)

Канал

| | |

Помехи

Рис.2. Процесс передачи сообщения от источника к приемнику (получателю)

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

обнаружить ошибки, если они возникают;

исправлять найденные ошибки;

защищать информацию, передающуюся по каналам связи;

ускорять передачу информации по каналу связи.

Из перечисленных проблем теория кодирования исследует первую и вторую. Третьей проблемой занимается криптография.2 Четвертая же является прикладной для криптографии и теории кодирования как параметр, с помощью которого определяется качество криптографии и кодирования.

Пусть мы хотим передать сообщение, которое может быть строкой символов некоторого конечного алфавита: {0,1}, или {строчные и/или прописные латинские буквы}, или {арабские цифры} и т.п.

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

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

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

Двоичные симметричные каналы

При математическом анализе систем связи обычно пользуются упрощенными моделями. Для двоичного алфавита {0,1} простейшая достаточно реалистическая модель называется двоичным симметрическим каналом. Пусть двоичные сигналы 0,1 последовательно передаются по каналу связи на приемник.

На рис.3 представлена ситуация, когда каждый символ принимается правильно с вероятностью р и ошибочно с вероятностью q = 1- p.

Рис. 3 Вероятность перехода в двоичном симметричном канале.

Идея, положенная в основу использования любого систематического кода такова: сообщение, подлежащее передаче, кодируется по определенной схеме более длинной последовательностью символов в алфавите {0, 1}.

Эта последовательность называется кодом3 или кодовым словом.

Совет

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

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

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

Двоичным (m, n)–кодом называется пара, состоящая из схемы кодирования E:2m®2n и схемы декодирования D:2n®2m, где 2n – множество двоичных последовательностей длины n.

Все помехоустойчивые коды делятся на два больших класса:

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

Для иллюстрации приведем два примера.

Пример 1.

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

Пусть a=a1…am – сообщение любой фиксированной длины m.

Схема кодирования определяется так:

E: (a1, … ,am) =a1 … am = ab = b1…bm+1,

где bi = ai, при i=1,2,…,m,

Например, при m=2 схема кодирования определяется следующим образом:

00000

01011

10101

11110

Из схемы кодирования видно, что поразрядная сумма любой кодированной последовательности должна быть четной, т.е. b1 +…+ bm+10(mod2).

Соответствующая схема декодирования такова: D: bc,

где bi = ci, при i=1,2,…,m, (последний бит отбрасывается).

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

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

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

Пример реализации метода четности представлен в таблице.

Таблица 1

Число
Контрольный разряд
Проверка

10101011
1

11001010

10010001
1

11001011

1 – нарушение

Пример 2. Определить и исправить ошибку в передаваемой информации вида

1001110

1110101

0101101

1010110

1101011

1

Для контроля использовать метод четности по строкам (контрольный столбец 8).

Решение: Осуществим проверку на четность по каждой строке: для этого определим, если, то при передаче сообщения возникает ошибка в i

-той строке.

k1=0; k2=1; k3=0; k4=0; k5=0.

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

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

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

Пример 3. Рассмотрим двоичный симметричный канал для передачи строк двоичной информации. Иногда полезен следующий (m,3m) – код с тройным повторением. Например: 0000, 1111, где 000 и 111 – кодовые слова.

Обратите внимание

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

Схема декодирования определяется так: принятое сообщение разбивается на блоки длины 3m и в каждом блоке из трех символов ci, ci+m, ci+2m , принимающих значение или 1, выбирается тот, который встретился большее число раз (два или три раза). Этот символ считается i-ым символом в декодированном сообщении. В частности при схеме кодировки 0 ® 000, 1 ® 111, декодирование при возможности одной ошибки будет следующей

000®0

001®0

010®0

100®0

111®1

110®1

101®1

011®1

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

Можно определить также (1,r) – код с r – кратным повторением, в котором каждый символ или 1 кодируется последовательностью из r таких символов. Множество кодовых слов состоит из двух слов длины r каждое: 00…0 и 11…1.