Понимание описания Шиены "Хеширования и Струн"

Question

В книге Skiena "Руководство по разработке алгоритмов" на стр. 80 представлен следующий абзац под заголовком 3.7 Хеширование и строки

Пусть α будет размером алфавита, на котором написана данная строка S. Пусть char(c) будет функцией, которая отображает каждый символ алфавита в уникальное целое число от 0 до α - 1.

Что означает "размер алфавита" в вышеприведенном абзаце? Разве все алфавиты (аз) не имеют одинаковый размер? Также как можно написать строку S на алфавите α. Разве алфавиты не собраны вместе, чтобы сформировать строку?

Answer 1

Размер алфавита α означает общее количество символов, которое можно использовать для строки S. В зависимости от ситуации алфавиты могут различаться. Например, двоичные числа могут быть представлены с использованием алфавита {0,1} (α=2), можно использовать латинские строчные буквы {a,...,z} (α=26) или символы для представления чисел в шестнадцатеричном формате с использованием {0,...,9,A,...,F} (Α =16).

Answer 2

Я думаю, вы можете быть смущены тем, что означает "алфавит". Алфавит - это не один символ, а набор всех возможных символов, которые могут появиться в строке. Английский алфавит имеет 26 символов. Еврейский алфавит имеет 22 символа (и они отличаются от английского алфавита).

Answer 3

Я изо всех сил пытался понять эту функцию хеширования, пока не нашел пример ее использования. То, что Скиена описывает, есть вариант алгоритма поиска строк Рабина-Карпа, как описано в Википедии.

Используется функция хеширования:

Позволять α быть размер алфавита, на котором данная строка S написано. Позволять char(c) быть функцией, которая отображает каждый символ алфавита в уникальное целое число из 0 в α − 1:

описание здесь>

Размер α алфавита - это количество символов, которое можно использовать для представления строки S.

Со страницы Википедии, указанной выше:

Отпечаток Рабина рассматривает каждую подстроку как число в некоторой базе, основание обычно представляет собой большое простое число. Например, если подстрока "hi" и база 101, значение хеша будет:

104 * 101^1 + 105 * 101^0 = 10609 // (ASCII of 'h' is 104 and of 'i' is 105).

Обратите внимание, что Шиена определяет char() функционировать как отображение от символа алфавита до целого числа из 0 в α − 1в то время как в примере из Википедии цифровой код может быть больше размера алфавита, в любом случае это должно дать вам представление о том, как применять формулу.