Programming Pearls: Parte 4

Coluna 14: Heap

Essa coluna descreve a estrutura de dados heap e como usá-la para implementar uma fila de prioridades e para ordenar um vetor de elementos (heapsort). O código de heapsort fornecido é bem conciso:

void down(int *v, int l, int u){
    while (1){
        int c = 2*l;
        if(c > u) return;
        if(c + 1 <= u && v[c+1] > v[c]) c++;
        if(v[l] >= v[c]) return;
        std::swap(v[c], v[l]);
        l = c;
    }
}
void heapsort(int *v, int n){
    for(int i=n/2; i>=1; i--)
        down(v, i, n);
    for(int i=n; i>=1; i--){
        std::swap(v[1], v[i]);
        down(v, 1, i-1);
    }
}

Observando que o vetor v deve conter os n elementos nas posições de 1 a n (e não de 0 a n-1 como de costume).

Um dos exercícios dá como aplicação de heaps, a soma de n números do tipo ponto flutuante. A motivação é que somar números pequenos com grandes pode acarretar perda de precisão. A ideia é ir somando a partir dos menores. Dá para fazer isso em O(n log n) usando heaps. Acho que daria um exercício de laboratório legal de estruturas de dados.

Coluna 15: String of Pearls

Como o nome sugere, nesta coluna são apresentados alguns algoritmos envolvendo strings. Inicialmente o autor apresenta um algoritmo para contar a frequência de palavras em um texto. A primeira abordagem é usando o set da biblioteca STL. Depois ele apresenta uma versão usando hash.

Depois é introduzida uma outra estrutura de dados, o array de sufixos. A definição é bem simples: dada uma string S, gere todos os seus sufixos e ordene-os em ordem lexicográfica, o que pode ser feito de maneira simples em O(L^2 log L), onde L é o tamanho de S — dá pra construir essa estrutura em O(L log L) com um algoritmo mais complicado. Algumas operações como por exemplo encontrar quais substrings de S têm os primeiros k caracteres iguais, podem ser feitas de maneira eficiente usando essa estrutura.

A parte mais interessante da coluna é sobre a cadeia de Markov. Como exemplo ele utiliza um gerador de texto aleatório (por exemplo o gerador de lero-lero ou o that can be my next tweet). A ideia é bem simples: pegue um texto e para cada palavra p, conte quais e quantas palavras sucedem p no texto. Inicialmente geramos uma palavra do texto aleatoriamente, denotada p0. Olhamos para as palavras que sucedem p0 e escolhemos uma delas com probabilidade proporcional à frequência delas. Repetimos esse procedimento até ter gerado um número suficiente de palavras.

Por exemplo no seguinte texto,

Toda a poesia – e a canção é uma poesia ajudada – reflecte o que a alma não tem. Por isso a canção dos povos tristes é alegre e a canção dos povos alegres é triste.

Fernando Pessoa

Para a palavra “a”, temos as palavras “poesia”, “alma” e três vezes “canção”. Se geramos “a” em algum momento, a próxima palavra será: “alma” ou “poesia” com 20% de chance cada e “canção” com 60%.

Como a escolha da próxima palavra só depende da última palavra gerada, temos uma cadeia de ordem 1. Generalizando, é possível usar as k últimas palavras na escolha da próxima, usando uma cadeia de ordem k. Note que conforme a ordem vai aumentando, o texto aleatório vai se tornando mais parecido com o texto original.

O autor fornece um algoritmo para gerar um texto aleatório de ordem k a partir de um texto fornecido através da entrada padrão:

– Comece com um trecho correspondente ao início do texto.
– Procure ocorrências no texto que têm as k primeiras palavras iguais a esse trecho (isso pode ser feito de maneira eficiente usando array de sufixos + busca binária).
– Escolha uma das ocorrências de forma aleatória (como não sabemos a priori quantas ocorrências existem, aquele algoritmo de selecionar um elemento de um vetor de tamanho desconhecido é bem útil).
– Imprima a (k+1)-ésima palavra da ocorrência escolhida e faça o trecho corrente começar na segunda palavra dessa ocorrência e repita o procedimento até que um número suficiente de palavras tenha sido gerado.

A ideia da leitura da entrada é bem interessante: as palavras lidas são concatenadas em um vetorzão chamado buffer e ao mesmo tempo vamos salvando em um vetor W, o endereço em que cada palavra começa em buffer. Note que cada entrada de W representa um sufixo de buffer no nível de palavras.

Para gerar o array de sufixos, precisamos ordenar os sufixos em W. Para esse problema em especial, estamos interessados apenas em agrupar os sufixos que têm as k primeiras palavras iguais. É exatamente isso que a função wordncmp implementa. A função wordnless é apenas um wrapper para a função sort da STL. Observe que usamos um vetor auxiliar P para evitar de ordenar o vetor W, já que estamos interessados em preservar a ordem inicial de W. O i-ésimo elemento do vetor ordenado é dado por W[P[i]].

vector<char *> W; // vetor de enderecos das palavras
vector<int> P; // vetor de permutacao dos indices de W

/*
 * Constroi o array de sufixos que trabalha no nivel
 * de palavras.
 */
void build_suffix_array(char *buffer){
  /* Salva o endereco em buffer onde se inicia cada
     palavra */
  W.assign(1, buffer);
  while (scanf("%s", W.back()) != EOF)
    W.push_back(W.back() + strlen(W.back()) + 1);

  /* Gera indices correspondendo a um vetor ordenado 
     comparando as k primeiras palavras */
  P.resize(W.size());
  for(int i = 0; i < (int) P.size(); i++)
    P[i] = i;
  sort(P.begin(), P.end(), wordnless);
}

/*
 * Compara as k primeiras palavras dos textos 
 * começando em p e q */
int wordncmp(char *p, char *q){
  int n = k;
  for(; *p == *q; p++, q++)
    if (*p == 0 && --n == 0) 
      return 0;
  return *p - *q;
}
/*
 * Função para ordenar os indices de W
 */
bool wordnless(int a, int b){
  return wordncmp(W[a], W[b]) < 0;
}

Uma vez que temos o vetor ordenado, dado um sufixo S do texto, encontrar a primeira posição no vetor ordenado que tem as k primeiras palavras iguais a S pode ser feito com uma busca binária.

/*
 * Busca binaria para encontrar a primeira ocorrencia
 * da palavra W[curr_index] no vetor ordenado de
 * palavras 
 */
int binsearch(int curr_index){
  int l = -1, u = (int)P.size(), m;
  while (l + 1 != u){
    m = (l + u) / 2;
    if (wordnless(P[m], curr_index))
      l = m;
    else u = m;
  }
  return u;
}

Definidas essas funções, o gerador de textos aleatórios de ordem k pode ser assim definido:

/*
 * Gerador de texto aleatorio
 */
void generator(){

  char buffer[100000];
  /* Lê a entrada em 'buffer' e gera o array de 
     sufixos */
  build_suffix_array(buffer);

  int curr = rand() % W.size();
  for(int wleft = 100; wleft > 0; wleft--){
    
    /* Encontra a primeira ocorrencia, no vetor 
       ordenado, da palavra word[curr] */
    int j = binsearch(curr);
    
    /* Para todos os trechos no texto que têm as k
       primeiras palavras iguais ao trecho corrente, 
       escolha uma aleatoriamente */
    int tmp_index;
    for(int i = 0; j + i < W.size() && 
	  wordncmp(W[curr], W[P[j + i]]) == 0; i++)
      if (rand() % (i+1) == 0)
        tmp_index = P[j + i];
    curr = tmp_index + 1;
    if (curr + k - 1 >= (int) W.size()) break;
    printf("%s ", W[curr + k - 1]);
  }
  printf("\n");
}

O código completo encontra-se aqui.

Conclusão

Com esse capítulo eu fecho a leitura do livro Programming Pearls do Jon Bentley. A minha impressão é que o livro é mais voltado para programadores sem um background teórico em computação. O conteúdo não foge muito do que aprendemos durante cursos da graduação na Unicamp e nos treinos de maratona, exceto pelos tópicos de geradores de números aleatórios e cadeias de Markov. Além disso, o autor fornece algoritmos bastante elegantes para diversos problemas clássicos.

A experiência de fazer posts conforme ia estudando, foi boa. Esse é um dos únicos livros técnicos que li do fim ao começo (pulando os apênces :P), embora a leitura seja bem leve. Já tenho outros livros na fila de leitura com os quais pretendo repetir a experiência.

Os comentários estão fechados.

%d bloggers like this: