Как найти дубликаты в массиве 64-битных чисел по (битовому) расстоянию Хэмминга?

Question

[d'Ivan]

Из базы изображений получил набор perceptive hash - 64-битных чисел, представленных в 16-ричной форме.
Необходимо выявить те группы таких чисел, (битовое) расстояние Хэмминга между которыми не превышает некоторого порога C.

Хранится в таблице images, колонка phash: char(16).
Каким SQL запросом можно выявить дубликаты?

Answer 1

[Rsa97]

Расстояние Хэмминга на MySQL посчитать несложно.
BIT_COUNT(HEX(:value1) ^ HEX(:value2))
Но надо определиться с понятием "группы таких чисел". Возьмём три двоичных числа (001, 011, 111) и определим расстояния между ними.
d(001, 011) = 1
d(001, 111) = 2
d(011, 111) = 1
Таким образом, первое и третье числа находятся на расстоянии 1 до второго, но между собой они находятся на расстоянии 2. Если границей расстояния выбрать 1, то как должны сформироваться группы?

Comments

[d'Ivan]

Здесь 001, 011 - пара дублирующих изображений
и 011, 111 - другая пара.
Надо было добавить метку Postgresql.

[d'Ivan]

То есть в приведённом примере пара и есть группа. Просто таких дублей может быть много.

[Rsa97]

Роман Мирр: postgresql.nabble.com/Bit-count-td2139492.html
Пара - это пара, строго два элемента. Группа - это произвольное количество, от нуля до бесконечности.

[d'Ivan]

Rsa97: дублей в группе может быть минимум 2, иначе это не дубли. Кроме того, SQL не возвращает пустое множество, ведь так?

[Rsa97]

Роман Мирр: Почему? NULL - вполне себе пустое множество.

[d'Ivan]

Rsa97: ну я, собственно, об отдаче результатов (строк) по SELECT.
Так каким запросом найти дубликаты в таблице images?

[Rsa97]

Роман Мирр: LEFT JOIN таблицы с собой по расстоянию Хэмминга и GROUP_CONCAT даст для каждой картинки список похожих на неё. Для PostgreSQL не скажу, а в MySQL примерно так:

SELECT `o`.`id`, GROUP_CONCAT(`d`.`id`)
  FROM `table` AS `o`
  LEFT JOIN `table` AS `d` 
    ON BIT_COUNT(HEX(`o`.`hash`) ^ HEX(`d`.`hash`)) < :distance
  GROUP BY `o`.`id`

[d'Ivan]

Rsa97: Спасибо