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 wildcards¹.

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.

¹ 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