Algoritmo de Markov

Algoritmo de Markov em Emacs Lisp

O algoritmo de Markov1 é um sistema de escrita de caracteres cujas regras são apenas de substituição (a linguagem de programação SNOBOL é um exemplo disso, uma linguagem de Markov).

Algoritmo

Dados uma lista de símbolos a1, a2, ..., an, b1, b2, ..., bn e um conjunto de regras r1:a1->b1, r2:a2->b2, ..., rk:ak->bk e um conjunto inicial de símbolos str faz-se:

  1. Testa-se cada uma das regras, da esquerda para direita, r1, r2, ..., rk;
  2. Se nenhuma for aplicável, i. e., se str não contém algum ai, i=1,2,...n, o algoritmo pára;
  3. Se alguma for aplicável, i. e., se str contém algum ai, i=1,2,...n, procede-se à substituição de ai por bi em str;
  4. go to 1.

Veja-se um exemplo retirado da Wikipedia (http://en.wikipedia.org/wiki/Markov_algorithm). Consideremos as regras:

  1. r1:"|0" -> "0||"
  2. r2:"1" -> "0|"
  3. r3:"0" -> ""

que transforma uma lista de zeros e uns (representação de algum número em binário) na sua representação em base 1 (ou melhor, com pauzinhos ||||||||||).

O código seguinte implementa o algoritmo de Markov em Emacs Lisp. As regras anteriores são definidas através da lista

(setq rules '(("|0" "0||") ("1" "0|") ("0" " ")))

A regra r1 é (rule-1 (car rules)), a r2 (rule-2 (cadr rules)) e a r3 é dada por (rule-3 (cddr rules)).

(defun subst-str (from-str to-str str)
  (cond (from-str
         (cond ((string-match from-str str)
                (let ((last-str (nthcdr (+ (length from-str) (string-match from-str str))
                                        (string-to-list str))))
                  (concat (nreverse (nthcdr (+ (length last-str) (length from-str))
                                            (nreverse (string-to-list str))))
                          (string-to-list to-str) last-str)))
               (t
                nil)))
        (t
         str)))

(defun eval-rule (rule str)
  (subst-str (car rule) (cadr rule) str))

(defun eval-all-rules-once (str rules)
  (cond ((eval-rule (car rules) str)
         (eval-rule (car rules) str))
        (t
         (eval-all-rules-once str (cdr rules)))))

(defun eval-all (str rules)
  (setq old-str (eval-all-rules-once str rules)
        new-str (eval-all-rules-once old-str rules))
  (cond ((not (eql old-str new-str))
         new-str
         (eval-all new-str rules))
        (t
                    new-str)))

Assim (eval-all "101" rules) dá "|||||".

Consideremos a frase

> (setq frase "Eu comprei um 1 na 2 da Sra. 3")
e as regras 
> (setq rules '(("1" "pão") ("2" "padaria") ("3" "Julia")))

A primeira iteração dá

> (eval-all-rules-once "Eu comprei um 1 na 2 da Sra. 3" rules)
"Eu comprei um pão na 2 da Sra. 3"
a segunda 
> (eval-all-rules-once "Eu comprei um pão na 2 da Sra. 3" rules)
"Eu comprei um pão na padaria da Sra. 3"
e a última 
> (eval-all-rules-once "Eu comprei um pão na padaria da Sra. 3" rules)
"Eu comprei um pão na padaria da Sra. Julia"

Testes

http://rosettacode.org/wiki/Execute_a_Markov_algorithm

(a indexação é a da fonte anterior)

1º conjunto de regras

(setq rules '(("1" "apple")
              ("2" "bag")
              ("3" "shop")
              ("4" "the")
              ("the shop" "my brother")
              ("a never used" ".terminating rule")))

> (eval-all "I bought a 2 of 1s from 4 3." rules)
"I bought a bag of apples from my brother."

2º conjunto de regras

(setq rules '(("1" "apple")
              ("2" "bag")
              ("3" ".shop")
              ("4" "the")
              ("the shop" "my brother")
              ("a never used" ".terminating rule")))

> (eval-all "I bought a 2 of 1s from 4 3." rules)
"I bought a bag of apples from my brother."

Não funciona..., porque a terminating rule não está implementada (ver algoritmo no topo da página ponto 2.). Deveria dar "I bought a bag of apples from T shop.".

5ª conjunto de regras

Máquina de Turing com 3 estados e com representação com 5-uplos (estado inicial, símbolo, escrita, movimento, estado final).

(setq r-turing '(("a0" "1b")   ;state A, symbol 0 => write 1, move right, new state B
                 ("0a1" "c01") ;state A, symbol 1 => write 1, move left, new state C
                 ("1a1" "c11")
                 ("0b0" "a01") ;state B, symbol 1 => write 1, move right, new state B
                 ("1b0" "a11")
                 ("b1" "1b")   ;state B, symbol 1 => write 1, move right, new state B
                 ("0c0" "b01") ;state C, symbol 0 => write 1, move left, new state B
                 ("1c0" "b11")
                 ("0C1" "h01") ;state C, symbol 1 => write 1, move left, halt
                 ("1c1" "h11")))

> (eval-all "000000A000000" r-turing)
"00011h1111000"

1. Este Markov não é aquele em que está a pensar, este é outro Markov.

Continua...

Palavras chave: algoritmo, Markov, Emacs, Lisp

Última actualização/Last updated: 2012-02-26 [15:49]

1999-2011 (c) Tiago Charters de Azevedo

São permitidas cópias textuais parciais/integrais em qualquer meio com/sem alterações desde que se mantenha este aviso.

Verbatim copying and redistribution of this entire page are permitted provided this notice is preserved.