Имя (это специфическое) алгоритма хеширования XOR для местоположений / строк массива

Question

Имя (это специфическое) алгоритма хеширования XOR для местоположений / строк массива

У меня есть следующий код C здесь:

http://marknelson.us/1989/10/01/lzw-data-compression/

В нем говорится, что он использует алгоритм хеширования XOR, чтобы избежать необходимости искать элементы массива подстроки и вместо этого генерировать "адрес" для подстроки.

Тогда есть функция хеширования, для которой строка ниже кажется мне основной частью:

index = (hash_character << HASHING_SHIFT) ^ hash_prefix;

Здесь мы имеем целочисленное значение, которое сдвигается в пределах от 4 бит влево (согласно определениям констант).
Затем это значение получает XOR с другим целочисленным значением.

Я почти уверен, что сдвигающаяся часть предназначена только для того, чтобы избавиться от неиспользуемых битов, и затем одна простая операция XOR применяется к очень короткой подстроке, от 12 до 16 бит; хотя я могу быть очень неправ в этом.

Какое имя или возможный список имен алгоритмов объясняют этот конкретный алгоритм хеширования 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;
  }
}

2

algorithm hash xor lzw

Источник

user681164 30 ноя '12 в 02:09

1 ответ

Решение

Другие вопросы по тегам algorithm hash xor lzw

user1911064 01 янв '13 в 22:10 2013-01-01 22:10 · Accepted Answer · 2013-01-01 22:10

Подобная хеш-функция была описана в работе Бруно Прайса "Структуры данных и алгоритмы с объектно-ориентированными шаблонами проектирования в Java" John Wiley & Sons, 2000

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