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

Streams (listas infinitas) em C

Ultimamente tenho feito duas coisas: lido sobre Haskell e não postado no blog (além das outras coisas do dia-a-dia, claro).

Programas em Haskell são preguiçosos. Isso significa que quando uma variável é definida, ela só será computada quando seu valor for necessário. Assim, se fizermos um programa similar ao de baixo, fatorial de 1000 nunca será calculado, já que o seu valor não é necessário para calcular 1+1.

x = factorial 1000
putStrLn $ show (1+1)

Extrapolando essa mesma ideia* para outras definições, podemos definir uma lista de infinitos uns:

uns = repeat 1

Ou então com todos os números naturais:

naturais = [1..]

Com um pouco mais de perspicácia, é possível criar listas contendo todos os números de Fibonacci, ou então todos os fatoriais:

fibs = 1:1: (zipWith (+) fibs (tail fibs))
facs = 1:(zipWith (*) facs [1..])

Se quisermos 10 elementos de cada, fazemos:

dezFibs = take 10 fibs
dezFacs = take 10 facs

Essa implementação é bastante eficiente : se precisamos do fatorial de 10 e logo em seguida o de 11, não precisamos calcular 11×10×9×…×1, basta calcular 11×10!, que já havia sido computado. Melhor ainda : se uma hora precisarmos do fatorial de 7, ele já estará calculado, pronto para ser utilizado.

Agora sim a parte interessante, em que C entra nessa história. Embora minha implementação não seja nem de longe tão interessante como a utilizada pelo Haskell, ela serve de base para mostrar como uma implementação de stream ou listas infinitas pode ser feita em C.

A grande diferença entre listas e streams é que não trabalharemos com a idéia de um ponteiro para o próximo elemento, mas sim com uma expressão que ao ser executada nos dará o próximo elemento. Ou seja, ao invés de um ponteiro para outro elemento do mesmo tipo, nós temos um ponteiro para uma função.

typedef struct {
    int i;
    int (*cont)(int);
} stream;

Isso altera a forma como acessamos o próximo elemento. Não podemos mais utilizar o famoso ptr = ptr->prox porque estaremos apontando para uma função. Por isso, abstraí o processo de chamar a função com o valor da stream em uma função chamada proximo, que retorna uma nova struct com seu valor i atualizado pela função cont, o que dá a impressão de que avançamos na lista.

stream proximo(stream inicio)
{
    stream tmp;

    tmp.i = (*inicio.cont)(inicio.i);
    tmp.cont = inicio.cont;

    return(tmp);
}

Para exemplificar o uso de streams, criei a função pega que é similar à função take no Haskell, mas que no caso não retorna os valores, só os imprime.

void pega(int elementos, stream inicio)
{
    int i;
    stream atual = inicio;

    for(i = 0; i < elementos; i++)
    {
        printf("%d\n",atual.i);
        atual = proximo(atual);
    }
    printf(".\n.\n.\n\n");
}

Por fim, criei duas streams e duas funções auxiliares (que falta fazem expressões lambda). O código completo se encontra abaixo:

#include <stdlib.h>
#include <stdio.h>

typedef struct {
    int i;
    int (*cont)(int);
} stream;

stream proximo(stream inicio)
{
    stream tmp;

    tmp.i = (*inicio.cont)(inicio.i);
    tmp.cont = inicio.cont;

    return(tmp);
}

int soma_um(int i)
{
    return(i+1);
}

int repete(int i)
{
    return(i);
}

void pega(int elementos, stream inicio)
{
    int i;
    stream atual = inicio;

    for(i = 0; i < elementos; i++)
    {
        printf("%d\n",atual.i);
        atual = proximo(atual);
    }
    printf(".\n.\n.\n\n");
}       

int main(int argc, char *argv[])
{
    stream naturais, identidade;

    naturais.i = 1;
    naturais.cont = &soma_um;

    identidade.i = 1;
    identidade.cont = &repete;

    pega(10, naturais);
    pega(10, identidade);
    return 0;
}

*eu escrevi “idéia” mas aparentemente os verificadores ortográficos já aderiram todos às novas regras ortográficas… fica assim mesmo.

C: Hash tables, arrays associativos, dicionários…

Não sei quantos nomes existem para descrever esta forma de organizar séries de dados na memória, esses três do título foram as que eu consegui pensar em 5 segundos.

Enfim, comecemos pela forma mais simples de armazenar séries de dados na memória, arrays, seguiremos para listas, árvores, e então chegaremos às hash tables. Se tudo que você quer é um exemplo de implementação, vá ao fim do artigo.

… então eu resolvi criar um blog

Quem clicou no meu identi.ca viu que só estou escrevendo em inglês lá. Entretando, às vezes quero escrever um texto maior, e lá no identica não há espaço, então eu resolvi criar um blog em inglês.

Um blog não substitui o outro, a idéia é que eles se complementem, mas a verdade é que no momento eu gosto mais do outro, por motivos que constam no primeiro post do outro blog: aqui eu sou muito mais um tradutor que um criador de conteúdo, e eu mesmo não faço parte do meu público alvo. Com isso eu consigo separar as coisas e ver cada blog em seu devido lugar, e evitar decepções.

αρσ (alpha rho sigma)

I can has twitter?

Acabei de criar um conta no Identi.ca e no Twitter. Eu vou postar principalmente em inglês, mas quem quiser fique à vontade para me seguir (preferencialmente no Identi.ca, mas isso é com vocês).

BigBusca

Estava dando uma olhada numa entrevista com o criador do BigLinux. Além de manter a distro, ele tem um site de buscas chamado “BigBusca”. Entrei para dar uma olhada, crente de que seria uma porcaria. Engano meu. Apesar do sistema de busca não ser exatamente dele (são buscas personalizadas do Google), existem opções que ficam meio escondidas no Google mesmo.

Por exemplo, na pesquisa Web, é possível escolher a idade máxima dos artigos (24 horas, um mês, um ano, etc). A busca por documentos permite especificar se quero pdfs, docs, odts… A busca por imagens novamente apresenta facilidades do tipo.

Ah sim, o link: BigBusca

Melhorando a aparência das fontes no Arch Linux

Eu instalei os pacotes cairo-lcd e libxft-lcd aqui e as fontes ficaram com uma aparência bem melhor. Claro que isso é subjetivo, então recomendo que experimentem os pacotes cairo-cleartype, freetype2-cleartype e libxft-cleartype.

A diferença entre eles é o algoritmo usado no subpixel shading. Pessoalmente, acho o algortimo padrão ruim, tanto que eu o deixava desligado. O Cleartype é o mesmo usado pelo Windows, mas também não gosto, acho que as fontes ficam “embaçadas”. O LCD, se não me engano, é um conjunto de patches utilizado pelo Ubuntu.

Infelizmente, nenhum desses dois últimos poderá vir a ser o padrão por questões legais.

Criando fractais no Linux

Eu adoro imagens de fractais, geralmente servem como ótimos papéis de parede e acho interessante essa conexão entre Matemática e Arte.

Durante algum tempo dei uma pesquisada nos programas disponiveis para Linux e elegi meus três favoritos:

• xaos – é o mais antigo, mas é relativamente leve e roda bem até mesmo em máquinas mais modestas. Da minha galeria no DeviantArt, o único que foi feito com ele foi este: Burtonian Brain.
• qosmic – é uma interface gráfica para o flam3, mas ainda não aprendi a usá-lo muito bem.
• gnofract4d – é o mais amigável de todos e é possível chegar a resultados interessantes usando apenas a função “Explorer”. Um detalhe interessante é que um dos meus fractais está nos favoritos do criador do software (o Malignific).

Para quem quiser ver, minha galeria no DeviantArt tem alguns fractais que foram feitos usando esses programas.

Sinto-me iluminado (uma crítica aos gerenciadores de janelas do Linux) – Parte 2

Após uma semana mais ou menos com o Enlightenment, posso dizer que gosto dele, mas que ele ainda não está pronto para uso. Não duvido que quando ele estiver pronto ele será um ótimo gerenciador de janelas / desktop, mas no momento os pequenos defeitos me encomodam.

Pesquisei mais gerenciadores de janelas aqui e ali, mas os que pareciam promissores eram projetos mortos, todos os outros que pareciam interessantes eu já tinha testado e não gostava por um detalhe ou por outro.

Por fim, resolvi fazer o meu próprio gerenciador, baseado no que eu gostava ou não em cada gerenciador que já experimentei (e acreditem, eu já experimentei vários). Se você não quiser ler um pequeno review de cada gerenciador, pule direto para o cabeçalho “O meu”.

Sinto-me iluminado (Enlightenment17)

Não preciso nem dizer que sou um chato em relação a gerenciadores de janelas. Passei um tempo com o PekWM, mas ele não estava se entendendo muito bem com o Emacs. Além disso, algumas leituras recentes sobre inovações no Desktop me fizeram querer largar mão um pouco do minimalismo, estava até cogitando usar o KDE 4.3, e estou ansioso pelo GNOME 3.

Dei uma olhada na Wiki do Arch Linux para ver que outras opções eu tinha e me lembrei do Enlightenment 17. Logo quando editei meu .xinitrc e iniciei o X com o Enlightenment, uma surpresa : Uma tela inicial permitindo a configuração de algumas coisas. O interessante é que existem “perfis” pré-configurados : um minimalista, que creio que não tenha tantos efeitos visuais, o tradicional, e dois que me chamaram a atenção para dispositivos de tela pequena (um é voltado para Netbooks e outro para dispositivos embarcados).

Comecei a mexer com ele e me impressionei com a atenção que foi dada aos mínimos detalhes. Por exemplo, no pager, dispositivos que mostra os Desktops Virtuais, existem miniaturas das janelas que estão abertas naquele Desktop. Se uma janela chama a atenção, sua miniatura no pager fica balançando. O ícone que aparece no canto superior esquerdo da decoração da janela também fica balançando, e aparece um ponto de exclamação.

Outro detalhe interessante é a existência de um botão “Modo de apresentação”. Ele desliga temporariamente a proteção de tela e as configurações de economia de energia, assim a tela não desliga enquanto você está fazendo aquela apresentação ou assistindo aquele filme.

Vale lembrar, entretanto, que ele ainda é uma versão em desenvolvimento. Apesar dessa atenção dispensada até aos mínimos detalhes, ele ainda não é perfeito. Por exemplo, nas configurações de que aplicativos serão iniciados automaticamente ao iniciar não é possível adicionar aplicações arbitrárias. Quando eu quis que o xbindkeys fosse iniciado junto ao Enlightenment, tive de criar um “ícone” para a aplicação e então adicioná-la à lista de aplicações iniciadas.

Outro problema é o gerenciador de arquivos. No momento, ele é minimamente funcional. Minimamente. Para se ter uma idéia, se estou em /home/usuario, não há como acessar /home diretamente. Ao invés de abrir Home e subir um nível, é necessário abrir o Root e clicar em home. Por enquanto fica só a promessa e a curiosidade de como seria um gerenciador de arquivos inovador.