À pala desta discussão no P@P, fui relembrado, dos confins da memória, desta estrutura: trie. Isto é daquelas coisas que se aprende em Algoritmos e Estruturas de Dados e depois, se não se trabalhar especificamente em motores de busca, gestão documental ou coisa que o valha, nunca mais se vai usar. E assim se perde nos interstícios da memória uma excelente estrutura.

O problema em causa - que não é exactamente o motivo pelo qual me reinteressei pelas tries, mas isso fica para outro dia - era a criação dum sistema que "sugira soluções para palavras cruzadas ou problemas equivalentes". Um dos primeiros passos é, como é lógico, criar um dicionário de palavras passível de ser pesquisado. A Universidade do Minho tem disponível um ficheiro de texto com quase 700.000 palavras (link inválido, neste momento), só faltava mesmo carregá-las e usá-las.

As primeiras respostas a esse tópico foram precisamente no sentido das tries, mas a minha primeira reacção foi trocar a dificuldade de implementação e debugging por uma certa penalidade em tempo de execução na pesquisa, usando um simples array com as palavras e pesquisa binária. Força do hábito.

Depois de levar nas beiças de alguns membros, cá fiz uns testes; acontece que "certa penalidade na pesquisa" era bem mais do que eu tinha previsto ao início - cerca de 9 vezes mais lento, e nem sequer estava a contemplar pesquisas parciais (e também não vai ser nesta posta que me debruçarei sobre isso). Seja então uma trie.

O que é então uma trie? Uma trie é uma estrutura em árvore que pode servir para guardar, por exemplo, registos ou valores como num array associativo, em que uma dada chave corresponde a um valor, ou então uma simples array sequencial, que é o caso em mãos. A trie guarda o caracter da chave correspondente ao nível; a chave “chave” seria guardada em cinco níveis duma trie, com o último nível marcado como final, podendo conter um valor correspondente a essa chave. Analogamente, a chave “chaveiro” seria guardada em oito níveis, mas os cinco primeiros seriam comuns à chave “chave”. Isto pode parecer uma compactação do espaço necessário, e até pode ser nalgumas condições (muitas chaves curtas); no caso de um dicionário com 700.000 itens, não é bem assim, como veremos mais à frente na serialização.

Mas qual é a vantagem, afinal? Como disse atrás, a maneira mais intuitiva de guardar um dicionário seria um array com as palavras todas. A pesquisa, neste caso, seria feita de forma eficaz recorrendo a um algoritmo de pesquisa binária, sendo forçoso, neste caso, que o array estivesse ordenado – o que seria mais um passo a fazer – na prática apenas uma vez – guardando de novo em ficheiro de texto.

Como alguns membros do P@P me fizeram notar, a complexidade temporal duma pesquisa numa trie e duma pesquisa binária é bastante diferente: O(m), sendo m o tamanho da chave a pesquisar, contra O(log n). Só aqui está toda a justificação de se usar a trie, visto que o tempo de pesquisa depende apenas do tamanho da chave a procurar, enquanto que numa pesquisa binária depende do tamanho do array – e estou a dar de barato a comparação das chaves com a chave pesquisada. Mas como bom céptico que sou, ainda fui perder umas horas a testar das duas maneiras. Como era previsível, os testes foram uma boa maneira de perder uma noite…

A minha implementação em C# duma trie é a seguinte (apenas inserção e verificação de existência):

public struct Trie
{
    public Dictionary<char, Trie> filhas;
    public bool final;

    public Trie(string palavra)
    {
        this.filhas = new Dictionary<char, Trie>();
        this.final = false;
        this.Inserir(palavra);
    }

    public void Inserir(string palavra)
    {
        if (palavra.Length > 0)
        {
            if (!this.filhas.ContainsKey(palavra[0]))
            {
                Trie newTrie = new Trie(this.GetSufixo(palavra));
                this.filhas.Add(palavra[0], newTrie);
            }
            else
                this.filhas[palavra[0]].Inserir(this.GetSufixo(palavra));
        }
        else
            this.final = true;
    }

    public bool Contem(string palavra)
    {
        if (palavra.Length == 0)
            return this.final;
        else if (this.filhas.ContainsKey(palavra[0]))
            return this.filhas[palavra[0]].Contem(this.GetSufixo(palavra));
        else
            return false;
    }

    private string GetSufixo(string palavra)
    {
        if (palavra.Length > 1)
            return palavra.Substring(1);
        else
            return "";
    }
}

Depois de estar esta estrutura, é só abrir o ficheiro, iterar por cada linha, e inserir na trie:

// como este é o nodo principal da árvore
// não tem uma inicialização explícita.
Trie myTrie = new Trie();

// as struct tem um comportamento nem sempre muito intuitívo
// ao fazer inicializações sem parâmetros
// por via das dúvidas, vamos inicializar as variáveis aqui
myTrie.filhas = new Dictionary<char, Trie>();
myTrie.final = false;

// abrir o ficheiro com as palavras
StreamReader tr = new StreamReader("ficheiro_palavras.txt");
string[] linhas = tr.ReadToEnd().Split(‘\n’);
for(int i = 0; i < linhas.Length; i++)
    myTrie.Inserir(linhas[i].ToLower());

tr.Close();

Finalmente, podemos pesquisar na trie, usando o método nela contido:

string pesquisa;
// _exit é uma string especial para sair do ciclo
while ((pesquisa = Console.ReadLine()) != "_exit")
    Console.WriteLine(myTrie.Contem(pesquisa.ToLower()) ? "Presente" : "Não presente");

A rapidez das respostas é brutal. No meu sistema, é inferior a 1 milissegundo, qualquer que seja a palavra que procure.

Com isto fora do caminho, vamos ao outro problema que surgiu: guardar a trie para ser usada mais tarde. Ao contrário do que se parece intuir da forma como a trie guarda os dados, a memória ocupada – e consequente serialização – não é menor que o ficheiro de texto original: é que o ficheiro de texto apenas ocupa dois bytes por cada caracter (em utf-8), enquanto que a serialização da trie tem de guardar também os tipos – nomeadamente, na minha implementação, a classe Dictionary é uma gulosa ao nível da serialização.

Tal como os membros do P@P tinham referido, a serialização binária resultava em ficheiros na ordem da centena de MB. Para um ficheiro que começou em 8 MB, acho que é consensual que seja para o excessivo. A serialização que me deu menores resultados foi em JSON, mas ainda era maior que o ficheiro de texto. Finalmente, e apenas como proof of concept, ainda passei por um GZipStream e, at last, o ficheiro resultante era menor que o ficheiro de texto.

Tudo isto veio com um preço: tempo. Muito tempo. A serialização e gravação era penosa – estamos a falar de cerca de 40 segundos no meu sistema – e a desserialização, então, era completamente absurda: mais de dois minutos. Certo, eu ainda não disse quanto tempo demorou a ler o ficheiro de texto e a criar a trie, mas vou fazê-lo agora: cerca de 8 segundos! Retirar a instrução toLower() (para casos em que o ficheiro de texto foi pré-normalizado) baixa entre um a dois segundos.

A hipótese aqui é descartar completamente a serialização da trie e criá-la directamente sempre que o programa arranque. In extremis, é colocar todo o texto num array directamente no código-fonte, se o tamanho do executável ou libraria não for problema.

Por último, é de realçar que o ficheiro com que estamos a trabalhar contém quase 700.000 palavras! Muitas delas são compostas, nomeadamente pronomes (-lhe, –te). É possível reduzir bastante o tamanho do ficheiro original, usando apenas palavras não compostas – o que serviria perfeitamente para o problema original das palavras cruzadas.

Meu sistema

  • Intel Core2Quad @ 2.5 GHz – só é usado um dos cores nos testes
  • 4 Gb RAM
  • HDD SATA 3.0 Gbps | 32 MB buffer
  • Windows 7 Ultimate x64

Update @ 25 Fev 10:

Para carregar ainda mais depressa, ver Trie, o regresso - usar embedded resource.

Update @ 30 Mar 10:

Finalização desta primeira fase das tries, incluíndo correcções de alguns erros: Trie contra-ataca – uso de wildcards em pesquisas, correcções e limpeza. Alem disso, esta série está agora representada num projecto.

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 Comentários Imagem do Feed RSS

Marco

Ainda. Está aqui.

Atles

Olá, gostaria de saber se você ainda tem disponivel este dicionario ai.

 

Obrigado!

Marco

Ainda tinha para aqui, sim. Está aqui (onde não vai ficar muito tempo - link válido até ao final do mês).

jgcm

Oi,

Ainda tem esse dicionário?

 

Obrigado,

Joao

Comentários Deixar um comentário

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