Trie - Uma estrutura de alta performance de pesquisa » Blog

Início » Blog » Trie - Uma estrutura de alta performance de pesquisa

25 2010 Fevereiro 00:25

Trie - Uma estrutura de alta performance de pesquisa

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