Para finalizar a primeira fase desta minha incursão pelas tries, vamos agora colocá-la a fazer alguma coisa de útil. Convenhamos que verificar se uma palavra existe ou não é trabalho fraquinho, tendo em consideração as potencialidades desta estrutura de dados. E uma dessas potencialidades é precisamente construir listagens a partir de verificações parciais. Estas podem servir para auto-completar palavras (como nos telemóveis, motores de busca) e para sistemas de correcção ortográfica, com listas de palavras semelhantes a palavras erradas, isto é, não constantes da lista. A implementação específica deste tipo de sistema está fora do âmbito desta posta, visto que não é trabalho específico da trie; esta, apenas devolve uma lista de palavras partindo de uma incompleta, usando wildcards1.

Começando pelo caso do wildcard ‘?’, correspondente a um caracter naquela posição, uma aproximação naïve seria iterar por todas as letras do alfabeto, incluindo as acentuadas, colocá-las na posição correcta e verificar a existência das palavras resultantes na trie. Salta à vista a inocência deste processo: em primeiro lugar, iterar por todos os caracteres possíveis para a posição incluiria muito mais do que os 26 normais do alfabeto – só em caracteres com diacríticos, seria bem mais do dobro; em segundo lugar, a ocorrência de palavras que obviamente não existem, com quatro consoantes seguidas, por exemplo; em terceiro e último lugar, quando quiséssemos implementar a pesquisa com o wildcard ‘*’, representando vários caracteres, os nossos problemas aumentariam exponencialmente.

O truque é deixar a trie decidir por onde pode e não pode ir, tirando partido de cada ramo saber quem são os filhos, percorrendo apenas caminhos válidos até às folhas finais. Aliás, é exactamente o mesmo processo de se verificar se uma palavra existe ou não; simplesmente, ao encontar um ‘?’, vai partir por cada filho, ao invés de percorrer apenas um. De forma análoga, ao encontrar um ‘*’, além de percorrer cada filho, passa-lhes também o próprio ‘*’, para que esse possa efectuar o mesmo tipo de pesquisa.

O código correspondente é constituído por um método público, aceitando apenas o termo a pesquisar e um privado, onde o trabalho efectivamente decorre, preenchendo a lista de palavras. O código foi movido para um projecto próprio, em ficheiros cs, visto que tenciono voltar à carga com outras funcionalidades – mas mais tarde.

Ao fazer uma pequena demonstração das tries, dei conta de um bug irritante: algumas palavras curtas eram reportadas como inexistentes. Ao início, pensei que fosse um problema da instrução ToLower, visto que a mesma tem um comportamento não muito intuitivo por causa da globalização e da codificação de caracteres. Quando mudei para ToLowerInvariant e o problema não ficou resolvido, comecei a ficar preocupado. De salientar que a instrução ToLowerInvariant, apesar de não resolver este problema, é a forma correcta de se trabalhar quando os ficheiros ou strings de origem não são controlados por nós, nem podemos garantir que o nosso código irá correr sempre em máquinas com culturas de globalização semelhantes.

Entretanto descobri que as folhas finais dessas palavras não estavam marcadas como finais. Daí à conclusão foi um saltinho: como estava a usar structs, a partir do momento em que as gravava no Dictionary, eram gravadas por valor e não por referência, como seria de esperar de um objecto. Este comportamento está correcto e é uma propriedade das structs. Mudando a trie para uma classe de pleno direito, o problema ficou automaticamente resolvido.

Finalmente, no capítulo da limpeza, esta classe mudou de nome, é agora CharTrie, que é um nome mais representativo do tipo de dados que aceita. Um parâmetro que andava ali para trás e para a frente sem se lhe fazer nada foi removido (ideia que depois não foi necessária), várias correcções menores foram efectuadas e a classe foi devidamente comentada.

1 Lamento, mas não sei o nome em português desta coisa. O translate do google sugere-me curinga, que os brasileiros chamam ao nosso joker das cartas. E parece que os nossos irmãos lá do outro lado do Atlântico chamam mesmo caracteres-curinga aos wildcards, mas não me soava muito bem... Se alguém souber o nome desta coisa, drop me a line...

Projecto

Outros Projectos » Trie

Da mesma série:

Trie - Uma estrutura de alta performance de pesquisa
Trie, o regresso - usar embedded resource

Partilhar no Sapo Links Partilhar no del.icio.us Partilhar no Digg Partilhar no Twitter Partilhar no StumbleUpon Partilhar no MySpace Partilhar no Facebook

Comentários Deixar um comentário

 Categorias
 Arquivo
 Projectos em Destaque
 Últimas Postas no Blog
 Últimos Comentários do Blog