Alfabetos e a classe Alphabet

Livro de Sedgewick e Wayne: introdução do cap.5, p.698.  Website do livro: slides.  Página algs4.cs.​princeton.edu/​code/: código fonte e documentação de todos os programas do livro.

Esta pequena aula não trata de uma estrutura de dados mas de uma classe Java que permite definir alfabetos arbitrários.  A ferramenta é útil para para manipular strings cujos caracteres são extraídos de um alfabeto restrito.  A ferramento é usada em implementações de tabelas de símbolos de strings (em particular, tries) e em compressão de dados.

A classe Alphabet

• Um alfabeto é um conjunto de caracteres.
• Em Java, cada caractere é um número do conjunto 0 . . 65535.
• A classe Alphabet permite definir um alfabeto personalizado com R caracteres numerados de 0 a R − 1.
• API (= interface) da classe Alphabet:

  public class Alphabet
  	Alphabet(String s)	cria um novo alfabeto cujas letras são os caracteres da string s
  int	toIndex(char c)	converte c em um índice entre 0 e R-1
  char	toChar(int index)	converte index no correspondente caractere deste alfabeto
  boolean	contains(char c)	o caractere c pertence a este alfabeto?
  int	R()	base (número de caracteres deste alfabeto)
  int	lgR()	número de bits para representar um índice
  int[]	toIndices(String s)	converte s em um número inteiro na base R
  String	toChars(int[] indices)	converte um inteiro na base R em uma string sobre este alfabeto

• Exemplo: Se queremos trabalhar com o alfabeto do DNA, cujos caracteres são A (igual a 65), C (igual a 67), T (igual a 84), G (igual a 71), convertemos os caracteres em índices e vice-versa:

  c	A	C	T	G
  toIndex(c)	0	1	2	3

  i	0	1	2	3
  toChar(i)	A	C	T	G

• Para o alfabeto ASCII temos simplesmente toIndex(c) == c para todo c  e  toChar(i) == i para todo i.

       0   1   2   3   4   5   6   7   8   9 
                                              
   0   NUL SOH STX ETX EOT ENQ ACK BEL BS  HT  
   1   LF  VT  FF  CR  SO  SI  DLE DC1 DC2 DC3 
   2   DC4 NAK SYN ETB CAN EM  SUB ESC FS  GS 
   3   RS  US  SP  !   "   #   $   %   &   '  
   4   (   )   *   +   ,   -   .   /   0   1  
   5   2   3   4   5   6   7   8   9   :   ;   
   6   <   =   >   ?   @   A   B   C   D   E  
   7   F   G   H   I   J   K   L   M   N   O
   8   P   Q   R   S   T   U   V   W   X   Y  
   9   Z   [   \   ]   ^   _   `   a   b   c  
  10   d   e   f   g   h   i   j   k   l   m  
  11   n   o   p   q   r   s   t   u   v   w  
  12   x   y   z   {   |   }   ~   DEL
  

Exemplo

• Um cliente típico de Alphabet: Recebe um alfabeto pela linha de comando e conta o número de ocorrências dos caracteres da entrada que estão no alfabeto (a contagem é armazenada num vetor count[0..R-1]):

  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]);
     }
  }
  

• Teste:

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

Alfabetos padrão

• Alguns alfabetos padrão constantes da classe Alphabet:

  nome	R()	lg(R)	conjunto de caracteres
  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
  UPPERCASE	26	5	ABCDEFGHIJKLMNOPQRSTUVWXYZ
  ASCII	128	7	alfabeto ASCII
  EXTENDED_ASCII	256	8	alfabeto ASCII estendido
  UNICODE16	65536	16	alfabeto Unicode

• Os alfabetos padrão são representados por variáveis de instância da classe Alphabet.  Assim, para se referir a um alfabeto como DNA, basta dizer  Alphabet.DNA.

Implementação

• Veja a implementação e a documentação da classe Alphabet no website do livro (não está no livro impresso).