Расстояние Хемминга в древней СУБД Microsoft

Question

Эта проблема

Я хочу найти дубликаты изображений и подобные изображения в MS SQL Server 7.

редактировать

Я запустил его, используя sql курсоры - это медленно, но работает, еще раз спасибо за комментарий. Смотрите мой ответ для решения, которое я придумал.

Конкретно...

У меня есть база данных, содержащая пути к изображениям и отпечатки пальцев связанных изображений, вычисленные с помощью этого алгоритма dhash. Я использую вариант, где я храню 128 бит на изображение (горизонтальный и вертикальный градиент) в BINARY(16) колонка.

То, что я хочу сделать, это что-то вроде:

DECLARE @id INT
SET @id = ...

DECLARE @given_hash BINARY(16)
SET @given_hash = ...

SELECT TOP 10 file_path,hash,
    (hamming_distance(hash, @given_hash)) AS distance
FROM my_table
WHERE distance <= 20
ORDER BY distance ASC

Что работает?

Получить точные дубликаты тривиально - просто используйте WHERE hash = @hash_to_compare и это все.

Что не работает?

Тем не менее, я хочу иметь возможность использовать меру сходства ( расстояние Хэмминга) для учета небольших манипуляций / дефектов / артефактов сжатия и т. Д. Я придумал хранимую процедуру, реализующую меру расстояния:

CREATE PROCEDURE hamming_distance128
    @hash BINARY(16),
    @supplied BINARY(16)
AS
    DECLARE @i INT, @j INT
    SET @i = 1
    SET @j = 1

    DECLARE @count INT
    SET @count = 0

    DECLARE @byte TINYINT

    DECLARE @length TINYINT
    SET @length = 16

    WHILE @i <= @length
    BEGIN
        SET @j = 1
        SET @byte = CAST((ASCII(SUBSTRING(@hash,@i,1)) ^ ASCII(SUBSTRING(@supplied,@i,1))) AS TINYINT)

        WHILE @j < 256
        BEGIN
            SET @count = @count + (CASE (@byte & @j) WHEN 0 THEN 0 ELSE 1 END)
            SET @j = @j * 2
        END

        SET @i = @i + 1
    END

    SELECT @count
GO

К сожалению, СУБД (SQL Server 7 - это невозможно обновить / изменить) не позволяет мне использовать ее для вычисления расстояний в запросе, и этот фрагмент j*nk не поддерживает пользовательские функции. Конечно же, я не нашел ничего похожего на MySQL BIT_COUNT это сделало бы это легкой задачей для T-SQL.

Есть ли надежда заставить это работать в T-SQL на SQL Server 7?

Помощь очень ценится!

Answer 1

Я запустил его, используя SQL-курсоры и временную таблицу. Еще раз спасибо @Tomalak

Я предоставляю свою реализацию для дальнейшего использования, надеюсь, это пригодится всем

CREATE PROCEDURE hamming_distance128
    @hash BINARY(16),
    @supplied BINARY(16),
    @distance TINYINT OUTPUT
AS
    DECLARE @i INT, @j INT
    SET @i = 1
    SET @j = 1

    DECLARE @count TINYINT
    SET @count = 0

    DECLARE @byte TINYINT

    DECLARE @length TINYINT
    SET @length = 16

    WHILE @i <= @length
    BEGIN
        SET @j = 1
        SET @byte = CAST((ASCII(SUBSTRING(@hash,@i,1)) ^ ASCII(SUBSTRING(@supplied,@i,1))) AS TINYINT)

        WHILE @j < 256
        BEGIN
            SET @count = @count + (CASE (@byte & @j) WHEN 0 THEN 0 ELSE 1 END)
            SET @j = @j * 2
        END

        SET @i = @i + 1
    END

    SET @distance = @count
GO


DECLARE @min_similarity FLOAT
SET @min_similarity = 0.85 -- | 85%

DECLARE @supplied_hash BINARY(16)
SET @supplied_hash = 0x392929295B4B13371B0301272D2B2509

IF OBJECT_ID('tempdb..#distances') IS NOT NULL
BEGIN DROP TABLE #distances END

CREATE TABLE #distances
(id INT NOT NULL,
 similarity FLOAT NOT NULL)

DECLARE
    @tmp_id INT,
    @dhash BINARY(16),
    @distance TINYINT,
    @similarity FLOAT

DECLARE rowCursor CURSOR
LOCAL FORWARD_ONLY READ_ONLY
FOR
    SELECT id,dhash_value
    FROM hashes
    OPEN rowCursor
        FETCH NEXT FROM rowCursor
        INTO @tmp_id,@dhash

        WHILE @@FETCH_STATUS = 0
        BEGIN
            EXECUTE hamming_distance128 @dhash, @supplied_hash, @distance OUTPUT

            IF @distance < 128
            BEGIN
                SET @similarity = CAST(128 - @distance AS FLOAT) / 128.0

                IF @similarity >= @min_similarity
                BEGIN
                    INSERT INTO #distances (id,similarity)
                    VALUES (@tmp_id,@similarity)
                END
            END

            FETCH NEXT FROM rowCursor
            INTO @tmp_id,@dhash
        END
    CLOSE rowCursor
DEALLOCATE rowCursor

SELECT hashes.id,#distances.similarity
FROM #distances
    INNER JOIN hashes
    ON hashes.id = #distances.id
ORDER BY #distances.similarity DESC

DROP TABLE #distances