20

Excel VBAを使用して長い文字列の短いハッシュを取得するにはどうすればよいですか

与えられたもの

  • 入力文字列は 80 文字以内です
  • 有効な入力文字は [0..9] [A_Z] です。_ /
  • 有効な出力文字は [0..9] [A_Z] [a_z] です (小文字と大文字を使用できます)
  • 出力ハッシュは最大 12 文字を超えてはいけません (短い方が良いです)
  • ハッシュが長くなりすぎるため、一意である必要はまったくありません

これまでに行ったこと

このSOの回答は、4桁の16進数コード(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 からコピーできます。
それらを新しい Excel ワークブックの列 A に貼り付け、上記のコードを実行します。

Q:十分に短く (12 文字)、わずかな割合の重複を取得するのに十分な長さの文字列ハッシュを取得するにはどうすればよいですか?

4

4 に答える 4

39

多分他の人はこれが役に立つと思うでしょう。

VBAで文字列の短いハッシュを生成するために、いくつかの異なる関数を収集しました。
私はコードを信用せず、すべてのソースが参照されています。

ここに画像の説明を入力してください

  1. CRC16
    • 機能:=CRC16HASH(A1)このコードで
    • ハッシュは4文字の長さのHEX文字列です
    • 19コード行
    • 4桁の長さのハッシュ=6895行で624回の衝突=9%の衝突率
  2. CRC16数値
    • 機能:=CRC16NUMERIC(A1)このコードで
    • ハッシュは5桁の長さの数字です
    • 92コード行
    • 5桁の長さのハッシュ=6895行で616回の衝突=8.9%の衝突率
  3. CRC162回
    • 機能:=CRC16TWICE(A1)このコードで
    • ハッシュは8文字の長さのHEX文字列です
    • ハッシュを12/16/20などの文字に拡張して、衝突率をさらに減らすことができます
    • 39コード行
    • 8桁の長さのハッシュ=6895行で18回の衝突=0.23%の衝突率
  4. SHA1
    • 機能:=SHA1TRUNC(A1)このコードで
    • ハッシュは40文字の長さのHEX文字列です
    • 142コード行
    • 切り捨てることができます
    • 4桁のハッシュ=6895行で726回の衝突=10.5%の衝突率
    • 5桁のハッシュ=6895行で51回の衝突=0.73%の衝突率
    • 6桁のハッシュ=0895行での衝突=0%衝突率
  5. SHA1 + Base64
    • 機能:=BASE64SHA1(A1)このコードで
    • ハッシュは28文字の長さのUnicode文字列です(大文字と小文字を区別+特殊文字)
    • 41コード行
    • ライブラリ「MicrosoftMSXML」を使用しているため、.NETが必要です
    • 切り捨てることができます
    • 4桁のハッシュ=6895行で36回の衝突=0.5%の衝突率
    • 5桁のハッシュ=0895行で0回の衝突=0%の衝突率

これは、すべてのサンプル関数と多数のテスト文字列を含む私のテストワークブックです

独自の関数を自由に追加してください。

于 2013-02-07T11:18:49.327 に答える
16

文字列を3つの短い文字列に分割します(3で割り切れない場合、最後の文字列は他の2つより長くなります)。それぞれに対して「短い」アルゴリズムを実行し、結果を連結します。

私はコードを書くことができましたが、質問の質に基づいて、ここからそれを取ることができると思います!

編集:そのアドバイスは十分ではないことが判明しました。元のCRC16コードに重大な欠陥があります。つまり、次のような行です。

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

これは、16進値として解釈できるテキストのみを処理します。小文字と大文字は同じであり、アルファベットの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があなたが必要とするすべてであることを示唆しています。

原則として、4文字の16進数は64kの一意の値を持つ必要があります。したがって、同じハッシュを持つ2つのランダムな文字列の可能性は64kに1つです。400個の文字列がある場合、400 x 399/2の「衝突の可能性のあるペア」〜80kの機会があります(非常にランダムな文字列があると仮定)。したがって、サンプルデータセットで3つの衝突を観察することは、不合理なスコアではありません。文字列の数Nが増えると、衝突の確率はNの2乗になります。hash12に追加の32ビットの情報があると、N> 20 M程度のときに衝突が発生することが予想されます(手振り、in-my-頭の数学)。

明らかに、hash12コードをもう少しコンパクトにすることができます。そして、それを任意の長さに拡張する方法を簡単に理解できるはずです。

ああ-そして最後にもう1つ。RCアドレス指定を有効にしている場合=CRC16("string")、スプレッドシートの数式として使用すると、追跡が難しい#REFエラーが発生します...そのため、名前を変更しましたhash4

于 2013-02-06T17:25:41.983 に答える
5

低レベルの衝突を伴う文字列の 32 ビット ハッシュ関数:

Public Function StrHash(text As String) As Long
    Dim i As Long
    StrHash = &H65D5BAAA

    For i = 1 To Len(text)
        StrHash = ((StrHash + AscW(Mid$(text, i, 1))) Mod 69208103) * 31&
    Next
End Function

または、64 ビットのハッシュ関数として:

Public Function StrHash64(text As String) As String
    Dim i&, h1&, h2&, c&
    h1 = &H65D5BAAA
    h2 = &H2454A5ED

    For i = 1 To Len(text)
        c = AscW(Mid$(text, i, 1))
        h1 = ((h1 + c) Mod 69208103) * 31&
        h2 = ((h2 + c) Mod 65009701) * 33&
    Next

    StrHash64 = Right("00000000" & Hex(h1), 8) & Right("00000000" & Hex(h2), 8)
End Function

FNV ハッシュアルゴリズムに基づく

于 2015-02-06T09:04:05.610 に答える