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).

(defparameter *table* (make-hash-table))
(setq *random-state* (make-random-state t)) ; Random seed

(defun space-position (string)
  "Finds the position of a 'space' character in a string. By 'space' I mean a
newline, space or tab character."
  (let ((sp (position #\Space string))
        (nlp (position #\Newline string))
        (tp (position #\Tab string)))
    (let ((values-list (remove-if #'null (list sp nlp tp))))
      (if values-list
          (apply #'min values-list)
          nil))))

(defun split-string (string)
  "Splits a string into a list of strings use spaces as delimeters."
  (let ((pos (or (space-position string) -1)))
    (cond ((= pos -1) (list string))
          ((= pos 0)  (split-string (subseq string (1+ pos))))
          (t (append (list (subseq string 0 pos))
                     (split-string (subseq string (+ pos 1))))))))

(defun last-two (list)
  "Returns the last two elements from a list."
  (let ((l (length list)))
    (if (> l 1)
        (list (nth (- l 2) list) (nth (- l 1) list))
        nil)))

(defun random-elt (list)
  "Returns a random element from a list"
  (let ((l (length list)))
    (if (= l 0)
        nil
        (nth (random (length list)) list))))

(defun random-key (table)
  "Returns a random key from table"
  (random-elt (loop for key being the hash-keys of table collect key)))

(defun list->triples (list)
  "Returns sequencial triples from a list."
  (if (< (length list) 3)
      nil
      (append (list (list (nth 0 list) (nth 1 list) (nth 2 list)))
              (list->triples (cdr list)))))

(defun string->symbol (string)
  "Convert a string into a symbol"
  (intern (string-upcase string)))

(defun insert-triple-into-table (triple)
  "Insert a triple of symbols in the table"
  (if (hash-table-p (gethash (first triple) *table*))
      (progn
        (setf (gethash (second triple) (gethash (first triple) *table*))
              (push (third triple) (gethash (second triple) (gethash (first triple) *table*)))))
      (progn
        (setf (gethash (first triple) *table*) (make-hash-table))
        (setf (gethash (second triple) (gethash (first triple) *table*))
              (list (third triple))))))

(defun insert-string-into-table (string)
  "Inserts the string into a hash table."
  (mapcar #'insert-triple-into-table
          (list->triples (mapcar #'string->symbol (split-string string)))))

(defun insert-file-into-table (filename)
  (let ((str ""))
    (with-open-file (f filename :direction :input)
      (loop for line = (read-line f nil 'eof) until (eq line 'eof)
         do (setq str (concatenate 'string str '(#\newline) line))))
    (insert-string-into-table str)))

(defun generate (words)
  "Generate a text with 'words' words."
  (let* ((first-word (random-key *table*))
         (second-word (random-key (gethash first-word *table*)))
         (text (list second-word first-word))) ;;; This list will be reversed
    (dotimes (i words)
      (let ((first-table (gethash (second text) *table*)))
        (if (hash-table-p first-table)
            (push (random-elt (gethash (first text) first-table)) text))))
    (format t "~(~{~a ~}~)" (reverse text))))
Publicidade

Uma resposta para “Gerador de Markov

  1. Pingback: MIT demonstra máquina de pesadelos com Inteligência Artificial | S U P R I M A T E C

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s

%d blogueiros gostam disto: