Строка хэша VBA

Как получить короткий хэш длинной строки с помощью Excel VBA

Что дано

Входная строка не длиннее 80 символов
Допустимые символы ввода: [0..9] [A_Z]. _/
Допустимые выходные символы: [0..9] [A_Z] [a_z] (можно использовать нижний и верхний регистр)
Выходной хэш не должен быть длиннее ~ 12 символов (короче еще лучше)
Не нужно быть уникальным вообще, так как это приведет к слишком длинному хешу

Что я сделал до сих пор

Я подумал, что этот SO-ответ - хорошее начало, поскольку он генерирует 4-значный шестнадцатеричный код (CRC16).

Но 4 цифры были мало. В моем тесте с 400 строками 20% получили дубликаты где-то еще.
Вероятность возникновения столкновения слишком высока.

Sub tester()
    For i = 2 To 433
        Cells(i, 2) = CRC16(Cells(i, 1))
    Next i
End Sub


Function CRC16(txt As String)
Dim x As Long
Dim mask, i, j, nC, Crc As Integer
Dim c As String

Crc = &HFFFF

For nC = 1 To Len(txt)
    j = Val("&H" + Mid(txt, nC, 2))
    Crc = Crc Xor j
    For j = 1 To 8
        mask = 0
        If Crc / 2 <> Int(Crc / 2) Then mask = &HA001
        Crc = Int(Crc / 2) And &H7FFF: Crc = Crc Xor mask
    Next j
Next nC

CRC16 = Hex$(Crc)
End Function

Как воспроизвести

Вы можете скопировать эти 400 тестовых строк из pastebin.
Вставьте их в столбец A в новой книге Excel и выполните приведенный выше код.

Q: Как я могу получить хеш строки, который достаточно короткий (12 символов) и достаточно длинный, чтобы получить небольшой процент дубликатов.

Ответ 1

Разделите свою строку на три короткие строки (если они не делятся на три, последний будет длиннее двух других). Запустите свой "короткий" алгоритм для каждого и соедините результаты.

Я мог бы написать код, но в зависимости от качества вопроса, который, я думаю, вы можете взять его здесь!

EDIT: Оказывается, этого совета недостаточно. В вашем исходном коде CRC16 есть серьезный недостаток, а именно строка, которая гласит:

j = Val("&H" + Mid(txt, nC, 2))

Это обрабатывает только текст, который может быть интерпретирован как шестнадцатеричные значения: буквы в нижнем и верхнем регистре одинаковы, и все, что после F в алфавите игнорируется (насколько я могу судить). То, что ничего хорошего выходит вообще, - это чудо. Если вы замените строку на

j = asc(mid(txt, nC, 1))

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

Объединив это изменение с предложением, которое я сделал ранее, вы получите следующий код:

Function hash12(s As String)
' create a 12 character hash from string s

Dim l As Integer, l3 As Integer
Dim s1 As String, s2 As String, s3 As String

l = Len(s)
l3 = Int(l / 3)
s1 = Mid(s, 1, l3)      ' first part
s2 = Mid(s, l3 + 1, l3) ' middle part
s3 = Mid(s, 2 * l3 + 1) ' the rest of the string...

hash12 = hash4(s1) + hash4(s2) + hash4(s3)

End Function

Function hash4(txt)
' copied from the example
Dim x As Long
Dim mask, i, j, nC, crc As Integer
Dim c As String

crc = &HFFFF

For nC = 1 To Len(txt)
    j = Asc(Mid(txt, nC)) ' <<<<<<< new line of code - makes all the difference
    ' instead of j = Val("&H" + Mid(txt, nC, 2))
    crc = crc Xor j
    For j = 1 To 8
        mask = 0
        If crc / 2 <> Int(crc / 2) Then mask = &HA001
        crc = Int(crc / 2) And &H7FFF: crc = crc Xor mask
    Next j
Next nC

c = Hex$(crc)

' <<<<< new section: make sure returned string is always 4 characters long >>>>>
' pad to always have length 4:
While Len(c) < 4
  c = "0" & c
Wend

hash4 = c

End Function

Вы можете разместить этот код в своей таблице как =hash12("A2") и т.д. Для удовольствия вы также можете использовать "новый, улучшенный" алгоритм hash4 и посмотреть, как они сравниваются. Я создал сводную таблицу для подсчета коллизий - для алгоритма hash12 не было никого, и только 3 для hash4. Я уверен, что вы можете понять, как создать hash8,... из этого. "Не нужно быть уникальным" из вашего вопроса предполагает, что возможно "улучшенный" hash4 - это все, что вам нужно.

В принципе, шестнадцатеричный шестнадцатеричный символ должен иметь уникальные значения 64k, поэтому вероятность того, что две случайные строки имеют одинаковый хеш, будет равна 1 в 64k. Когда у вас 400 строк, есть 400 x 399/2 "возможных пар столкновений" ~ 80k (при условии, что у вас были случайные строки). Поэтому наблюдение трех столкновений в наборе данных выборки не является необоснованным. По мере увеличения числа строк N вероятность столкновений идет как квадрат N. С дополнительными 32 битами информации в hash12 вы ожидаете увидеть столкновения при N > 20 М или около того (ручная работа, голова-математика).

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

О - и последнее. Если у вас включена RC-адресация, используя =CRC16("string") в качестве формулы для электронных таблиц, вы получите ошибку "t29" с жестким треком... поэтому я переименовал ее hash4

Ответ 2

Возможно, другие найдут это полезным.

Я собрал несколько разных функций для генерации короткого хеша строки в VBA.
Я не беру на себя ответственность за код, и на все источники ссылаются.

CRC16
- Функция: =CRC16HASH(A1) с этим кодом
- хэш - это шестнадцатеричная строка длиной 4 символа
- 19 строк кода
- Длинный хэш из 4 цифр = 624 столкновения в 6895 строках = частота столкновений 9%
CRC16 числовой
- Функция: =CRC16NUMERIC(A1) с этим кодом
- хэш - это 5-значный номер
- 92 строки кода
- Хэш длиной 5 цифр = 616 столкновений в 6895 строках = частота столкновений 8,9%
CRC16 дважды
- Функция: =CRC16TWICE(A1) с этим кодом
- хеш - это шестнадцатеричная строка длиной 8 символов
- хеш может быть расширен до 12/16/20 и т.д., чтобы еще больше снизить вероятность столкновения
- 39 строк кода
- 8-значный длинный хэш = 18 столкновений в 6895 строках = частота столкновений 0,23%
SHA1
- Функция: =SHA1TRUNC(A1) с этим кодом
- хэш - это шестнадцатеричная строка длиной 40 символов
- 142 строки кода
- можно обрезать
- Хэш из 4 цифр = 726 столкновений в 6895 строках = частота столкновений 10,5%
- Хэш из 5 цифр = 51 коллизия в 6895 строках = 0,73% частоты столкновений
- Хэш из 6 цифр = 0 коллизий в 6895 строках = 0% коллизий
SHA1 + Base64
- Функция: =BASE64SHA1(A1) с этим кодом
- хэш - это строка в Unicode длиной 28 символов (с учетом регистра + специальные символы)
- 41 строка кода
- требует .NET, так как использует библиотеку "Microsoft MSXML"
- можно обрезать
- Хэш из 4 цифр = 36 столкновений в 6895 строках = частота столкновений 0,5%
- Хэш из 5 цифр = 0 коллизий в 6895 строках = 0% коллизий

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

Не стесняйтесь добавлять собственные функции.

Ответ 3

Для записи это быстро генерирует 32-битный хеш с низким уровнем столкновения:

Public Function HashFNV(txt As String) As Long
  Const max# = 2 ^ 31
  Dim hash#, upper&, i&
  If txt = Empty Then Exit Function
  hash = &H11C9DC5
  For i = 1 To Len(txt)
    hash = 31# * (hash - upper * max Xor AscW(Mid$(txt, i, 1)))
    upper = hash / max
  Next
  HashFNV = hash - upper * max Or &H80000000 * (upper And 1&)
End Function

Ответ 4

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

Как это работает: Столбец A удерживает строки из строки 2 дальше. В строке 1 A1 и B1 удерживают произвольную начальную и конечную позицию в середине строки. Формула использует первую букву строки и фиксированную букву, взятую из середины строки, и использует LEN() как функцию "fanning", чтобы уменьшить вероятность столкновений.

 =CODE(A2)*LEN(A2) + CODE(MID(A2,$A$1,$B$1))*LEN(MID(A2,$A$1,$B$1))

Если строки извлекаются из таблицы базы данных с полями фиксированной ширины, вам может потребоваться обрезать длины:

 =CODE(TRIM(C8))*LEN(TRIM(C8))
       +CODE(MID(TRIM(C8),$A$1,1))*LEN(MID(TRIM(C8),$A$1,$B$1))