Функции расстановки

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

1. По символам строки s определяем положительное целое H. Преобразование одиночных символов в целые обычно можно сделать средствами языка реализации. В Паскале для этого служит функция ord, в Си при выполнении арифметических операций символьные значения трактуются как целые.
2. Преобразуем H, вычисленное выше, в номер элемента, то есть целое между 0 и N - 1, где N - размер таблицы расстановки, например, взятием остатка при делении H на N. Функции расстановки, учитывающие все символы строки, распределяют лучше, чем функции, учитывающие только несколько символов, например, в конце или середине строки. Но такие функции требуют больше вычислений. Простейший способ вычисления H - сложение кодов символов. Перед сложением с очередным символом можно умножить старое значение H на константу q. То есть полагаем H0 = 0, Hi = q*Hi-1 + ci для 1
   
   i
   
   k, k - длина строки. При q = 1 получаем простое сложение символов. Вместо сложения можно выполнять сложение ci и q *Hj-1 по модулю

3. Переполнение при выполнении арифметических операций можно игнорировать. Функция Hashpjw, приведенная ниже [?], вычисляется, начиная с H = 0 (предполагается, что используются 32- битовые целые). Для каждого символа c сдвигаем биты H на 4 позиции влево и добавляем очередной символ. Если какой- нибудь из четырех старших бит H равен 1, сдвигаем эти 4 бита на 24 разряда вправо, затем складываем по модулю 2 с H и устанавливаем в 0 каждый из четырех старших бит, равных 1.

#define PRIME 211 #define EOS '\0' int Hashpjw(char *s) {char *p; unsigned H=0, g; for (p=s; *p!=EOS; p=p+1) {H=(H<<4)+(*p); if (g=H&0xf0000000) {H=H^(g>>24); H=H^g; } } return H%PRIME; }

Содержание раздела

---

---