私はここから次のCコードを持っています:
http://marknelson.us/1989/10/01/lzw-data-compression/
XOR ハッシュ アルゴリズムを使用して、部分文字列配列要素を検索する必要がなくなり、代わりに部分文字列の「アドレス」を生成すると述べています。
次に、以下の行が主要部分であると思われるハッシュ関数があります。
index = (hash_character << HASHING_SHIFT) ^ hash_prefix;
ここでは、(定数の定義に従って) 4 ビットから左にシフトされた整数値があります。
次に、この値に別の整数値を適用した XOR を取得します。
シフト部分は未使用のビットを取り除くだけであり、12 ビットから 16 ビットの非常に短い部分文字列に単一の単純な XOR 演算が適用されていることは確かです。私はこれについて非常に間違っているかもしれませんが。
この特定の XOR ハッシュ アルゴリズムを説明する名前またはアルゴリズム名の可能なリスト、または可能であれば、この部分文字列アプリケーションに適したアルゴリズム名のリスト (部分文字列の LZW 辞書など) は?
#define BITS 12 /* Setting the number of bits to 12, 13*/
#define HASHING_SHIFT (BITS-8) /* or 14 affects several constants. */
#define MAX_VALUE (1 << BITS) - 1 /* Note that MS-DOS machines need to */
#define MAX_CODE MAX_VALUE - 1 /* compile their code in large model if*/
/* 14 bits are selected. */
#if BITS == 14
#define TABLE_SIZE 18041 /* The string table size needs to be a */
#endif /* prime number that is somewhat larger*/
#if BITS == 13 /* than 2**BITS. */
#define TABLE_SIZE 9029
#endif
#if BITS <= 12
#define TABLE_SIZE 5021
#endif
……
……
……
/*
** This is the hashing routine. It tries to find a match for the prefix+char
** string in the string table. If it finds it, the index is returned. If
** the string is not found, the first available index in the string table is
** returned instead.
*/
int find_match(int hash_prefix,unsigned int hash_character)
{
int index;
int offset;
index = (hash_character << HASHING_SHIFT) ^ hash_prefix;
if (index == 0)
offset = 1;
else
offset = TABLE_SIZE - index;
while (1)
{
if (code_value[index] == -1)
return(index);
if (prefix_code[index] == hash_prefix &&
append_character[index] == hash_character)
return(index);
index -= offset;
if (index < 0)
index += TABLE_SIZE;
}
}