algorithm - 了解 Skiena 对“哈希和字符串”的描述

Question

在 Skiena 的“算法设计手册”一书中，以下段落出现在第 80 页标题3.7 散列和字符串下

令 α 为写有给定字符串 S 的字母表的大小。让 char(c) 是一个函数，它将字母表的每个符号映射到一个从 0 到 α - 1 的唯一整数。

上一段中的“字母大小”是什么意思？不是所有的字母 (az) 都有相同的大小吗？还有怎么可能把字符串 S 写在字母 α 上。字母不是放在一起形成一个字符串吗？

Answer 1

字母的大小 α 是指可用于字符串 S 的符号总数。根据情况，字母可能会有所不同。例如，可以使用字母表{0,1}（α=2）表示二进制数，可以使用拉丁小写字母（α=26）或使用（α=16）{a,...,z}以十六进制表示数字的符号。{0,...,9,A,...,F}

Answer 2

我想你可能会对“字母”的含义感到困惑。字母表不是单个符号，而是字符串中可能出现的所有可能符号的集合。英文字母表有 26 个符号。希伯来字母表有 22 个符号（它们与英语字母表的符号不同）。

Answer 3

我一直在努力理解散列函数，直到我找到了它的用法示例。Skiena 描述的是 Wikipedia 上描述的 Rabin-Karp 字符串搜索算法的变体。

使用的哈希函数如下：

让是写给α定字符串的字母表的大小S。让char(c)是一个函数，将字母表的每个符号映射到从0到的唯一整数α − 1：

字母表的大小 α 是可以用来表示字符串 S 的符号数。

从上面链接的维基百科页面：

Rabin 指纹将每个子字符串视为某个基数中的一个数字，该基数通常是一个大素数。例如，如果子字符串是 "hi"且基数是101，则哈希值将是：

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

请注意，Skiena 将char()函数定义为从字母符号到整数的映射0to α − 1，而在 Wikipedia 示例中，数字代码实际上可能大于字母大小，无论如何这应该让您了解如何应用公式。