Oportunidade – Programador de Interfaces

A startup que trabalho (shoprizer.com) tem uma equipe formada por Jedis (onde eu sou o Mestre Yoda ), que trabalham com PHP Hardcore e está precisando agora de um NINJA, um programador de interfaces, para trabalho remoto. Os requisitos são:

• XHTML, CSS, Web standards
• Javascript/AJAX
• PHP básico/intermediário – só o necessário para a integração da lógica existente com a interface a ser feita.
• Smarty
• Disponibilidade de 20 horas semanais – flexíveis.
• Inglês básico para leitura e escrita
• Conhecimento de princípios de Usabilidade
• Precisa ter o espírito de startup!

Se você está interessado, mande seu CV com links do seu portfolio para van2br@yahoo.com, atenção à Vanessa.

Review e slides do CONAPHP

No último fim de semana (18 e 19 de outubro) houve em São Paulo o CONAPHP (www.conaphp.com.br), um evento feito pela comunidade PHP e que rolou dentro do CONISLI na FIAP.

O evento em geral foi bom, com bom nível de palestras mas o público foi um pouco abaixo do que eu esperava.

Para mim, o ponto alto foi quando estava assistindo a palestra do Elton Minetto (slides aqui) e “reconheci” um slide sobre o compilador JIT e o cache do opcode do PHP, um slide que fazia parte da apresentação que fiz em Recife no Encontro Pernambucano de SL, e para confirmar vi lá meu link nas referências, e isso me deixou bastante honrado por ter um material meu usado como referência por um ícone como o Elton.

A minha palestra foi a última e falei sobre PHP RESTful Web Services, por ser a última, o título não ser apelativo para o pessoal mais iniciante e eu ser um ilustre desconhecido da comunidade PHP de São Paulo, tive apenas metade da sala cheia, mas o feedback das pessoas que assitiram a palestra foi bastante positivo e fiquei muito satisfeito.

Os slides da palestra seguem abaixo, e o código apresentado está disponível aqui.

Quem tiver interesse sobre o assunto, deixo algumas referências:

• http://www.sematopia.com/?p=153
• http://www.lornajane.net/posts/2008/Using-curl-and-PHP-to-talk-to-a-REST-service
• http://www.lornajane.net/posts/2008/PHP-Rest-Server-part-1-of-3
• http://www.lornajane.net/posts/2008/PHP-Rest-Server-part-2-of-3
• http://www.lornajane.net/posts/2008/PHP-Rest-Server-part-3
• http://rest.blueoxen.net/cgi-bin/wiki.pl?FrontPage
• http://wiki.developer.mindtouch.com/REST/REST_for_the_Rest_of_Us
• http://www.xfront.com/REST-Web-Services.html
• http://tomayko.com/writings/rest-to-my-wife

Algoritmo de “Você quis dizer”

Recentemente precisei implementar um sistema de correção ortográfica à la Google.

Pesquisei bastante sobre como fazer isso, e encontrei duas maneiras que explicarei agora, mas antes disso explicarei algo que é comum às duas: A criação do dicionário

Para criar o dicionário, você precisa ter uma base de palavras, que idealmente é um arquivo txt.

Você lê o arquivo e cria um array onde as palavras são as chaves e as frequências com que aparecem nos textos serão os valores.

<?php
$text = file_get_contents('arquivo.txt');
preg_match_all("/[a-z]+/",strtolower($text),$matches);
$palavras = $matches[0];
$dicionario = array();
foreach($palavras as $palavra)
	$dicionario[$palavra] += 1;
sort($dicionario); /* Essa ordenação será útil para otimização de performance
                               no primeiro algoritmo */
file_put_contents('dicionario_serializado.dat',serialize($dicionario));
?>

1 – Algoritmo de Levenshtein

PHP implementa nativamente o algoritmo de Levenshtein (http://php.net/levenshtein), que calcula a distância de edição entre duas palavras, funcionando da seguinte forma:

• suponha que eu tenha duas palavras: água e mágua – A distância de edição delas é de uma inserção de carácter
• suponha que eu tenha as palavras: casa e caixa – A distância delas é de uma substituição (s por i) e uma inserção (x)
• suponha que eu tenha as palavras: arrocho e arroto – A distância delas é de uma substituição e uma remoção.

A função levenshtein também permite que você dê pesos diferenciados para inserção/remoção/substituição, sendo que o valor default é 1 para todas operações. Usando essa função, fica simples implementar um corretor, supondo que você tem um dicionário que já citei, você só precisa fazer:

<?php
function voce_quis_dizer($palavra_procurada) {
	$dicionario = unserialize(file_get_contents(‘dicionario_serializado.dat’));
	$minima_distancia = -1;
	$palavra_procurada = strtolower($palavra_procurada);
	foreach($dicionario as $palavra_do_dicionario) {
		if($palavra_procurada == $palavra_do_dicionario) return $palavra;
		$distancia = levenshtein($palavra_procurada,$palavra_do_dicionario);
		if($distancia < $minima_distancia || $minima_distancia == -1) {
			$minima_distancia = $distancia;
			$sugestao = $palavra_do_dicionario;
		}
	}
return $sugestao;
}
?>

Análise de desempenho:

Considerando que temos k palavras no dicionário, a palavra que desejamos procurar tem m letras e cada palavra do dicionário tem em média n letras, o algoritmo de Levenshtein tem ordem de complexidade O(m*n) onde para k comparações (no caso da palavra não existir no dicionário, já que se ela existir não teremos nenhuma comparação) teremos O(k*m*n) (k*m*n operações onde k é muito maior que m e n).

2 - Algoritmo de Peter Norvig

Toda explicação probabilística desse algorítmo está presente no site do Norvig, um cara renomado na área de inteligência artificial: http://norvig.com/spell-correct.html. Mas basicamente esse algoritmo apesar de mais complicado é bem mais inteligente que o primeiro. O que ele faz é o seguinte: gera perturbações na sua palavra procurada e vê quais dessas perturbações é a mais relevante no dicionário. Evitando comparações desnecessárias, já que no primeiro algoritmo cada palavra que você colocar será comparada com todas as outras (por exemplo: se você digitar BOLA, e ela não existir no dicionário ela será comparada com palavras absurdas como: LIVRO, que obviamente não é o que você quis dizer).

Apesar do conceito do Norvig ser simples, o código é um pouquinho complicado. Então eu criei uma classe que implementa ele e disponibilizei sob Licença BSD no PHPClasses.org (http://www.phpclasses.org/browse/file/24605.html) e tenho recebido elogios e feedback muito positivo de quem está usando.

Análise de desempenho:

Considerando 26 letras do alfabeto (depois da reforma da língua portuguesa, agora também temos 26 letras! ) e considerando que sua palavra tem m letras, teremos mais ou menos 26*m iterações para gerar as possíveis perturbações na palavra (inserções, remoções e substituições possíveis), e para garantir um segundo nível de perturbações teremos aproximadamente 26*m para cada perturbação gerada, que dá um total de aproximadamente (26*m)*(26*m) = 676 m². Agora só precisamos consultar cada uma das perturbações para vermos qual a mais relevante no dicionário. Cada consulta no dicionário é O(1) então desprezaremos na análise de performance.

E podemos considerar esse algoritmo como sendo mais eficiente do que o primeiro pois o tempo de execução cresce de acordo com o quadrado do tamanho da palavra (que normalmente é bem menor do que o tamanho do dicionário). Enquanto o primeiro sofre interferência do tamanho do dicionário e do tamanho médio das palavras contidas lá, então esse é bem mais inteligente e eficiente.

Espero ter ajudado!