Вес Хэмминга / количество населения в T-SQL - PullRequest
Новая
       32

Вес Хэмминга / количество населения в T-SQL

2 голосов
/ 07 мая 2011

Я ищу быстрый способ для вычисления веса Хэмминга / количества населения / "числа 1 бит" поля BINARY (1024).MySQL имеет функцию BIT_COUNT, которая делает что-то подобное.Я не смог найти подобную функцию в T-SQL?

Или вы бы предложили хранить двоичные данные в поле другого типа?

Если вы не знаете, что яКстати, вот статья Википедии о весе Хэмминга .

Ответы [ 4 ]

4 голосов
/ 09 мая 2011

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

-- define Hamming weight helper table
DECLARE @hwtally TABLE (byte tinyint, hw int);
INSERT INTO @hwtally (byte, hw) VALUES (0, 0);
INSERT INTO @hwtally (byte, hw) SELECT   1 - byte, 1 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT   3 - byte, 2 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT   7 - byte, 3 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT  15 - byte, 4 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT  31 - byte, 5 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT  63 - byte, 6 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT 127 - byte, 7 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT 255 - byte, 8 - hw FROM @hwtally;

-- calculate
WITH split AS (
  SELECT SUBSTRING(@value, number, 1) AS byte
  FROM master.dbo.spt_values
  WHERE type = 'P' AND number BETWEEN 1 AND LEN(@value)
)
SELECT
  Value = @value,
  HammingWeight = SUM(t.hw)
FROM split s
  INNER JOIN @hwtally t ON s.byte = t.byte
1 голос
/ 13 октября 2015

Когда вы играете с меньшим значением (например, 16-битным макс.), Самый эффективный способ сделать это с SQL Server - это использовать таблицу со всеми вычисленными результатами и использовать объединение.выполнить запрос от 30 секунд до 0 секунд, выполнив такие действия для запроса, который должен вычислять вес Хэмминга для 4-битного значения на 17 000 строк. 

WITH HammingWeightHelper AS (
        SELECT  x, Fx 
        FROM (VALUES(0,0),(1,1),(2,1),(3,2),
                    (4,1),(5,2),(6,2),(7,3),
                    (8,1),(9,2),(10,2),(11,3),
                    (12,2),(13,3),(14,3),(15,4)) AS HammingWeight(x, Fx)
    )
SELECT HammingWeight.Fx As HammingWeight, SomeTable.Value As bitField
FROM   SomeTable INNER JOIN
       HammingWeightHelper ON HammingWeightHelper.x = SomeTable.Value

Конечно, это уродливое решениеи это, вероятно, не подойдет для длинных битовых полей.

0 голосов
/ 09 мая 2011

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

0 голосов
/ 07 мая 2011

Не нашел ничего конкретно о весе Хэмминга, но вот что касается расстояния Хэмминга: 

create function HamDist(@value1 char(8000), @value2 char(8000))
returns int
as
begin
    declare @distance int
    declare @i int
    declare @len int

    select @distance = 0,
           @i =1,
           @len = case when len(@value1) > len(@value2)
                       then len(@value1)
                       else len(@value2) end

    if (@value1 is null) or (@value2 is null)
        return null

    while (@i <= @len)
        select @distance = @distance +
                           case when substring(@value1,@i,1) != substring(@value2,@i,1)
                                then 1
                                else 0 end,
               @i = @i +1

    return @distance
end

Это вычисляет расстояние Хэмминга между двумя значениями. Вес Хэмминга одного значения будет расстоянием Хэмминга между этим значением и массивом нулевых значений.

...