Algoritmo de Markov
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:
- Testa-se cada uma das regras, da esquerda para direita,
r1
,r2
, ...,rk
; - Se nenhuma for aplicável, i. e., se
str
não contém algumai
, i=1,2,...n, o algoritmo pára; - Se alguma for aplicável, i. e., se
str
contém algumai
, i=1,2,...n, procede-se à substituição deai
porbi
emstr
; go to
1.
Veja-se um exemplo retirado da Wikipedia (http://en.wikipedia.org/wiki/Markov_algorithm). Consideremos as regras:
r1:"|0" -> "0||"
r2:"1" -> "0|"
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/keywords: algoritmo, Markov, Emacs, LispCriado/Created: NaN
Última actualização/Last updated: 10-10-2022 [14:26]
(c) Tiago Charters de Azevedo