Arquivos Mensais: novembro 2009

Gerador de Markov

Gerador de Markov

Um dos sites mais úteis que existem é o Gerador de Lero-lero. Não tenho certeza se o algoritmo usado é um Gerador de Markov mesmo, mas se não for, a idéia é bem parecida.

Gerador de Markov é um programa que analisa um texto procurando as combinações de palavras mais comuns e então gera um texto usando as mesmas combinações em um texto que é estatisticamente similar ao anterior. Como essa análise será feita depende da implementação. Eu escolhi usar combinações de 3 palavras, ou seja, uma palavra do texto gerado depende das duas anteriores a ela. Variando a quantidade de palavras usadas em cada combinação, altera-se o texto resultante: se eu escolhesse combinações de uma palavra, o texto gerado seria completamente aleatório, se eu escolhesse combinações de dez palavras, o texto resultante ficaria mais parecido com o original.

A implementação de um Gerador é relativamente simples, clique em “Ler o resto do artigo” para ter acesso ao código em Common Lisp. O código está bem dividido e cada função tem uma função clara (evidentemente).

Primeiramente, criamos uma hash-table que conterá as combinações de palavras. Usamos uma hash-table por ela ser mais eficiente. Se usássemos listas ou árvores, teríamos de fazer buscas toda vez que o Gerador fosse adicionar uma nova palavra ao texto. Logo no começo também, inicializamos o gerador de números aleatórios.

Para que possamos analisar as combinações de palavras, precisamos primeiro dividir a string em uma lista de strings. A função “space-position” se ocupa de descobrir onde fica o próximo “divisor de palavras”, ou seja, um espaço, um tab ou uma quebra de linha. O que vier antes será o delimitador. Se houver vários espaços em sequência, nós teríamos uma lista com algumas strings vazias, mas o “cond” na função “split-string” detecta isso com “(= pos 0)” e evita que isso aconteça.

Logo em seguida vem algumas funções auxiliares. “Last-two” retorna os dois últimos elementos de uma lista qualquer. Precisaremos dela mais tarde. “Random-elt” e “random-key” retornam um elemento aleatório de uma lista e uma chave aleatória de uma hash-table respectivamente. “List-triples” retorna os trios que podem ser formados de uma lista. Note que ela não gera todos os arranjos possíveis, apenas as combinações sequenciais. Imagine que existe um bloco com espaço para três “coisas”. Esse bloco percorre a lista sequencialmente gerando os trios. Assim, a lista ‘(1 2 3 4 5) seria percorrida como: ‘((1 2 3) 4 5), ‘(1 (2 3 4) 5) e ‘(1 2 (3 4 5)). Portanto, (list->triples ‘(1 2 3 4 5)) retornaria ‘((1 2 3) (2 3 4) (3 4 5)). “String->symbol” retorna um símbolo com o mesmo nome que o conteúdo da string passada como argumento. Não me pergunte porque eu preferi usar símbolos ao invés de strings mesmo. Talvez o gerador ficaria melhor assim, já que ele saberia diferenciar quando uma palavra está iniciando uma frase pela letra maiúscula, ou talvez isso não mudasse lá grande coisa.

“Insert-triple-into-table” é a função que faz o trabalho sujo: ela é a responsável por inserir os trios gerados por “list->triples” na hash-table que críamos no começo do programa. Ela é feia, não é uma função que me orgulho de ter escrito, mas ela funciona. Perceba que cada entrada na hash-table inicial é, por sua vez, outra hash-table. Essa segunda hash-table guarda uma lista com as possíveis palavras que podem ser usadas.

“Insert-string-into-table” organiza o trabalho de separar uma string em uma lista de strings, transformá-las em símbolos, gerar os trios e inserí-los na hash-table.

“Insert-file-into-table” foi uma função que deu trabalho escrever. Inicialmente, ela seria a função responsável por abrir um arquivo, salvá-lo como uma string e então passar para “insert-string-into-table”. Porém, a forma com que fiz isso era péssima, o consumo de memória ia para as alturas e o tempo de execução também. Em uma das tentativas, reimplementei boa parte da “insert-string-into-table” em “insert-file-into-table”, mas acabei deixando as duas funções mesmo assim, já que as duas são úteis. Depois, consegui implementar esta função segundo a idéia original com um desempenho muito melhor.

Finalmente, a parte interessante: “generate” gera um texto com no máximo o número específicado de palavras. Não há garantias de que ele gerará o número máximo, já que algumas combinações podem fazer com que ele não consiga gerar mais nada.

Só para me exibir, resolvi colocar alguns trechos que o Gerador criou tendo como base o texto deste artigo (um artigo recursivo):

“logo no começo também, inicializamos o gerador de markov mesmo, mas se não for, a idéia é bem parecida.”

“gerador de markov é um gerador de markov”

“se houver vários espaços em sequência, nãs teríamos uma lista e uma chave aleatória de uma lista e uma chave aleatória de uma lista com algumas strings vazias, mas o “cond” na função “split-string” detecta isso”

Eu o tenho usado nas conversas de MSN com sucesso. Ele detecta que a outra pessoa falou “oi :)” e gera o texto “olá =]” ou variação. Depois ele detecta a combinação “tudo bom?” e responde “sim, e contigo?”. Depois ele passa o comando para mim. OK, isso não é sério… ainda. Preciso aprender a fazer plugins para o Pidgin ainda (o bitlbee seria mais interessante nesse aspecto).

Saiba mais

Publicidade