Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Localhost

Tries / Strings

Mensagens Recomendadas

Localhost

Boas, é o seguinte, eu sou um bocado mau a resolver problemas que envolvam strings e não gosto lá muito deste tipo de problemas. Alguém me podia dar umas noções sobre tries e outros tipos de estruturas de dados que sejam úteis para trabalhar com strings.

Sobre as tries podia-me dar algumas aplicações da sua implementação?


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

Não há muitos estruturas de dados especificamente para strings.. Acho que as únicas que conheço são mesmo as Tries e as Suffix Trees/Suffix Arrays (com arrays é significativamente mais fácil).

O único algoritmo útil que me vem à memória é o KMP (Knuth-Morris-Pratt) (a sua extensão, o Aho-Corasick, nunca precisei de usar nem conheço nenhum problema que tenha saído em concursos onde fosse necessário).

Acho que para te dares melhor com problemas de strings o melhor a fazer é resolver muitos problemas. A maior parte dos problemas de strings são problemas onde te podes abstrair do facto de serem strings, de modo que alguém que está à vontade com problemas ad-hoc genéricos.

As Tries são úteis quando pretendes fazer pesquisas de uma string num conjunto de strings extremamente rápidas. Qualquer problema onde isto seja uma necessidade, a Trie é a estrutura adequada (podendo eventualmente usar-se uma hash table, mas para quem está habituado a dificuldade de implementação não é substancialmente superior).

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mjamado
As Tries são úteis porque permitem verificar se uma string

Caíste da cadeira abaixo,  ou quê?  :cheesygrin:

Localhost, no meu site pessoal está uma implementação de Trie em C#. Não te deve dar grande dor de cabeça a traduzir para outras linguagens, até porque está devidamente comentado. Se leres as postas do blog relacionadas, melhor.


"Para desenhar um website, não tenho que saber distinguir server-side de client-side" - um membro do fórum que se auto-intitula webdesigner. Temo pelo futuro da web.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

@Warrior, e quanto às aplicações que podem ter esta estruturas de dados que falaste (suffix trees, tries, hash tables), etc? Eu li uma vez que suffix trees tinham muitas aplicações (bem concretas) como por exemplo, encontrar o maior palindromo numa string. Li isto quando estava a resolver o Calf Flac da usaco.

@mjamado, vou dar uma olhada no teu site. Obrigado. :)


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

As Tries e as Hash Tables servem unicamente para indexar strings, não há muito mais a dizer em relação a isso.

As suffix trees/suffix arrays são normalmente usados quando pretendes utilizar substrings da tua string.

O melhor mesmo é começares por perceber o que são estas estruturas de dados. Não precisas de conhecer os algoritmos para as construir, mas se souberes o que são mais facilmente sabes para que servem, e se eventualmente leres um problemas podes pensar "aqui um suffix array dava jeito" e aí sim, vais ver como implementar.

Acho é que devo salientar que estamos a falar de estruturas de dados complexas, principalmente as árvores de sufixos, longe daquilo que se espera de um aluno do secundário OU universitário. Mesmo em concursos universitários (como a MIUP) eu diria que os dedos de uma mão chegam para contar as equipas que conhecem estas estruturas.

Se o teu objectivo é treinar para as ONI, diria que resolver problemas genéricos é o melhor caminho. As soluções para 100 pontos poderão eventualmente utilizar estas estruturas, mas é muito raro tal acontecer. Tão raro que nunca aconteceu.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Não achas que se tivesse conhecimento destas estruturas seria muito mais fácil olhar para um problema de strings e saber que posso resolvê-lo com certeza com uma suffix tree ou com uma trie? Acho que era bom que conseguisse chegar a pensar assim.

Em relação às tries, tive a ler alguns artigos e até já sei mais ou menos como construir.

Basicamente, temos de ter uma estrutura que vai contêr a letra e um array de ponteiros com no máximo N ponteiros em que N são a quantidade de letra que o alfabeto tem. Depois tinhamos uma função que adicionava à árvore uma palavra. Esta função seria recursiva, ou não, mas como vi era recursiva, depois basicamente, verificava se a letra que estou a percorrer existe na árvore (no nó abaixo), se existir não faço nada, se não existir crio um novo nó. Acho que também é um pouco de listas ligadas para o meio. Vou depois analisar como é que faço para pesquisar por uma palavra e tal, e depois vou ver se vou para as suffix trees.

Eu acho que já sei como fazer isto em C, vou tentar implementar.

Depois dá-me um feedback sobre a maneira que eu interpretei o que li sobre como se construi uma trie, se está correcta ou não.

edit: Esqueci-me de dizer que tenho de criar por ordem alfabética e que a cada letra que adiciono tenho de "cortá-la" da string que quero adicionar, ou seja, tenho de "cortar" sempre a letra que está mais à esquerda.

Estou a ver isto tudo pelo topcoder.

edit2: Tenho uma dúvida. Sempre que quero adicionar uma nova palavra tenho de voltar ao principio da árvore certo? Ainda estou a falar na construção de uma trie.


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

Não percebi muito bem o teu primeiro PS, mas não necessitas de adicionar por ordem alfabética se voltares ao início da árvore (isto respondendo ao teu PS2).

Podes evitar voltar ao princípio se as palavras estiverem por ordem alfabética, mas não compensa o trabalho extra..

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Imagina que já tenho uma palavra adicionada à árvore, depois para começar a adicionar outra tenho de voltar à raíz da mesma não?

Acho que se dentro do array de ponteiros pusesse já por ordem, por exemplo, adiciono uma letra que ainda não existe mas adiciono-a mesmo na posição a que corresponde essa letra no alfabeto, por exemplo, se adicionasse a letra A, esta ficaria numa estrutura que estaria na posição 0 ou 1 do array. Depois para pesquisar seria só consultar essas posições, "cortando" na mesma cada letra inicial da palavra que quero procurar.

Agora usando o meu pseudocódigo, para adicionar uma palavra acho que era algo como isto:

se str estiver vazia return;
indice = firstChar(str);
se str[indice] nao existe
  pts[indice] = novoNo()
cortaPrimeiraLetra(str)
adicionaPalavra(str,pts[indice])

Achas que era algo como isto? :)  


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Bom dia,

Já consegui implementar qualquer coisa, só não sei é se está bem.

Podem-me ver e corrigir?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ABC 100
#define FIRST 97

typedef struct t {
    struct t *child[ABC];
}Trie;

int add(Trie *root, char *word) {
    int len = strlen(word);
    int k = 0,j = 0;
    Trie *edge = root;
    while(len > 0) {
        k = word[j] - FIRST;
        printf("%i\n", k);
        if(edge->child[k] == NULL) {
            edge->child[k] = (Trie *) malloc(sizeof(Trie));
            edge = edge->child[k];
            memset(edge->child,0,ABC);
        }else edge = edge->child[k];
        j++;
        len--;
    }
}

int main(void) {
    Trie trie;
    memset(trie.child,0,ABC);
    add(&trie,"an");
    return 0;
}

edit: esqueci-me de um pormenor no código.


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

Parece-me tudo bem.

Vais precisar de adicionar uma flag a cada nó da Trie para saber se acaba uma palavra nesse nó.

Por exemplo, se adicionas "a", "aa" e "aaaaa", necessitas de saber que "a" e "aa" existem mas "aaa" não.

A melhor forma de testares é implementares o find, inserir várias strings e depois procurar por várias strings (que existam e não existam) e verificar se os resultados estão correctos.

Só um detalhe, talvez pretendas substituir o teu ciclo por algo como isto:

for (j=0;word[j]; j++) {
    k = word[j] - FIRST;
    printf("%i\n", k);
    if(edge->child[k] == NULL) {
        edge->child[k] = (Trie *) malloc(sizeof(Trie));
        edge = edge->child[k];
        memset(edge->child,0,ABC);
    }
   else 
      edge = edge->child[k];
}

É desnecessário utilizar o comprimento da string quando só a pretendes percorrer.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Vou implementar uma função de pesquisa.

Quanto à flag, é mesmo necessário? Tries não servem só para fazer pesquisas? Para fazer uma pesquisa preciso de uma palavra, ou seja, eu vou nó a nó e quando chegar ao final da palavra corto a pesquisa. Para quê que preciso de uma flag? Não seria algo muito dificil de se fazer, acho que bastava adicionar um campo à struct, podia até ser um int, que indicava se uma palvra acabava ou não.


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

A função find é bastante simples de implementar, já a fiz.

Agora estou com uma dúvida, será que o meu algoritmo está a fazer a função find em O(L) (onde L é o tamanho da string que quero procurar)?

O que a minha função find faz é "saltar" de nó em nó e verificar se a posição em que se insere a letra no array é diferente de NULL, se for significa que a letra está lá, se não for posso cortar a pesquisa porque já não existe a palavra.

Vou deixar aqui o código para veres (actualizado):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ABC 100
#define FIRST 97

typedef struct t {
    struct t *child[ABC];
}Trie;

void add(Trie *root, char *word) {
    int k = 0,j = 0;
    Trie *edge = root;
    for(j = 0; word[j]; j++) {
        k = word[j] - FIRST;
        if(edge->child[k] == NULL) {
            edge->child[k] = (Trie *) malloc(sizeof(Trie));
            edge = edge->child[k];
            memset(edge->child,0,ABC);
        }else edge = edge->child[k];
        j++;
    }
}

int find(Trie *root, char *word) {
    int k = 0, j = 0;
    Trie *edge = root;
    for(k = 0; word[k]; k++) {
        j = word[k] - FIRST;
        if(edge->child[j]) edge = edge->child[j];
        else return -1;
        k++;
    }
    return 1;
}

int main(void) {
    Trie trie;
    memset(trie.child,0,ABC);
    add(&trie,"an");
    add(&trie,"ant");
    if(find(&trie,"an") == 1) printf("Palavra encontrada\n");
    else printf("Palavra não encontrada\n");
    return 0;
}

E sim, isto num concurso daria um trabalho muito grande a nível de implementação, visto que o tempo é +/- escasso e que pode levar a erros, devido à pressão. Mas até gosto de fazer este tipo de implementações. Vou ver agora se vou para as suffix trees porque esse é que é o meu verdadeiro objectivo.

edit: Pois, já percebi porque é que tenho de utilizar uma flag. Com esta lista de palavras:

-> an

-> ant

-> all

-> allot

Se pesquisar pela palavra allo o meu código retorna 1 porque não tem ali nenhuma flag que diga que a palavra não acaba ali. Vou ter de implementar isso.


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Suffix trees são mais dificeis de se implementar. Por enquanto, em termos de construção só sei construir em O(n^2), ainda não percebi como é que se constrói em O(n).

Sei contruir em O(n^2) mas é em forma de uma trie, ou seja, não sei construir compressed tries.

O que faço é percorrer a string em O(n^2) e ir adicionando à árvore cada sufixo.


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

Vê suffix arrays primeiro, é bastante mais simples e curto o código.

Quer dizer, no fundo no fundo o meu conselho seria esquecer estas estruturas para já..

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Ok, por enquanto, até depois das ONI vou esquecer isto.

Só para finalizar este tópico, qual é o tempo de construção de uma trie? Fiquei com dúvidas nisso.


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Então compensa implementar uma destas quando se tem um dicionário ou algo parecido. Depois pode-se procurar uma palavra em O(len), o que é excelente.

Obrigado por todos os esclarecimentos.


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.