◈5.0.2 字母表

5.0.2 字母表

一些应用程序可能会对字符串的字母表作出限制。在这些应用中,可能常常会需要一个 API 如表 5.0.2 所示的 Alphabet 类。

表 5.0.2 字母表的 API

public class Alphabet``             Alphabet(String s)根据 s 中的字符创建一张新的字母表        char toChar(int index)获取字母表中索引位置的字符         int toIndex(char c)获取 c 的索引,在 0 到 ![R-1](https://private.codecogs.com/gif.latex?R-1) 之间     boolean contains(char c)``c 在字母表之中吗         int R()表示一个索引所需的比特数         int lgR()将 s 转换为 ![R](https://private.codecogs.com/gif.latex?R) 进制的整数       int[] toIndices(String s)将 ![R](https://private.codecogs.com/gif.latex?R) 进制的整数转换为基于该字母表的字符串      String toChars(int[] indices)

这份 API 定义了一个构造函数,它用一个含有 R 个字符的字符串参数指定了字母表。API 定义了 toChar() 方法和 toIndex() 方法来在字符和 0 到 R-1 之间的整型值进行转换(常数时间)。它还包含了 contains() 方法来检查给定的字符是否存在于字母表中。方法 R() 和 lgR() 用来获取字母表中的字符数以及表示它们所需的比特数。 toIndices() 方法和 toChars() 方法能够将由字母表中的字符组成的字符串与 int 数组相互转换。方便起见,下面的表格显示了各种内置的字母表,你可以通过类似 Alphabet.UNICODE16 的方式来访问它们。 Alphabet 的实现很简单,我们将它留作练习(请见 5.1.12)。我们会在表 5.0.3 后面的框注“ Alphabet 类的典型用例”来展示一个它的用例。

表 5.0.3 标准字母表

名称

R()

lgR()

字符集

BINARY

2

1

01

DNA

4

2

ACTG

OCTAL

8

3

01234567

DECIMAL

10

4

0123456789

HEXADECIMAL

16

4

0123456789ABCDEF

PROTEIN

20

5

ACDEFGHIKLMNPQRSTVWY

LOWERCASE

26

5

abcdefghijklmnopqrstuvwxyz

UPPPERCASE

26

5

ABCDEFGHIJKLMNOPQRSTUVWXYZ

BASE64

64

6

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxz0123456789+/

ASCII

128

7

ASCII 字符集

EXTENDED_ASCII

256

8

扩展 ASCII 字符集

UNICODE16

65 536

16

Unicode 字符集

public class Count
{
   public static void main(String[] args)
   {
      Alphabet alpha = new Alphabet(args[0]);
      int R = alpha.R();
      int[] count = new int[R];

      String s = StdIn.readAll();
      int N = s.length();
      for (int i = 0; i < N;  i++)
         if (alpha.contains(s.charAt(i)))
            count[alpha.toIndex(s.charAt(i))]++;

      for (int c = 0; c < R; c++)
         StdOut.println(alpha.toChar(c)
                             + " " + count[c]);

   }
}

Alphabet 类的典型用例

% more abra.txt
ABRACADABRA!

% java Count ABCDR < abra.txt
A 5
B 2
C 1
D 1
R 2

字符索引数组。我们使用 Alphabet 类的一个最重要的原因是字符索引的数组能够提高算法的效率。在这个数组中,用字符作为索引来获取与之相关联的信息。如果要使用 Java 的 String 类,那就必须使用一个大小为 65 536 的数组;有了 Alphabet 类,则只需要使用一个字母表大小的数组即可。我们将要学习的一些算法能够产生大量的此类数组。在这种情况下,大小为 65 536 的数组是不可接受的。例如前面框注中的 Count 类,它从命令行接受一个字符串并打印出从标准输入获得的每个字符的出现频率。 Count 中用来保存出现频率的 count[] 数组就是一个字符索引数组的示例。你可能会认为数组的计算有些繁琐,但实际上它是 5.1 节介绍的一系列快速排序算法的基础。

数字。你可以从几个标准的 Alphabet 类的示例中看到,我们经常要处理字符串形式的数字。 toIndices() 方法能够将任意基于给定的 Alphabet 类的 String 转换为一个 R 进制的数字,用一个元素均在 0 到 R-1 之间的 int[] 数组表示。在某些情况下,一开始就进行这样的转换可以使代码更简洁,因为任意数字都能作为一个字符串索引数组中的索引。例如,如果我们已知输入中仅含有字母表中的字母,那就可以将 Count 中的内循环替换为下面这段更加简洁的代码:

int[] a = alpha.toIndices(s);
for (int i = 0; i < N; i++)
   count[a[i]]++;

其中,我们将 R 称为 基数,即进制数。我们介绍的几种算法也常常被称为“基数”方法,因为它们一次只处理一位数。

% more pi.txt
3141592653
5897932384
6264338327
9502884197
... [π的100 000位]

% java Count 0123456789 < pi.txt
0 9999
1 10137
2 9908
3 10026
4 9971
5 10026
6 10028
7 10025
8 9978
9 9902

尽管使用 Alphabet 这样的数据类型能够为字符串处理算法带来许多好处(特别是对于较小的字母表),但是本书中并没有实现基于通用字母表 Alphabet 类得到的字符串类型,这是因为:

  • 大多数程序使用的都是 String 类型;
  • 将字符串转化为索引或是由索引得到字符串常常会落入内循环中,这会大幅降低实现的性能;
  • 这会使代码更加复杂,也更加难以理解。

因此我们仍然会使用 String 类,在代码中使用常数 R = 256 并在分析中将 R 作为参数。在适当的时候我们会讨论通用字母表的性能。本书的网站提供了基于 Alphabet 类的各种算法的完整实现。