Ferramentas de Site


algoritmo:tries

Esta é uma versão antiga do documento!


Tries - estrutura de dados para armazenar Strings

Ora bem, hoje trago-vos uma estrutura de dados para armazenar strings mais propriamente. Tem a vantagem de ser muito rápida e de ter a capacidade de partilhar posições das strings que queremos guardar, sendo assim eficiente também a nível de memória.

Basicamente em cada nó vamos ter em cada nó um vector de ponteiros que vai ser o nosso "abecedário", ou seja, poderá ter, por exemplo, 26 posições. Se determinada letra existir na string a partir de determinado nó criámos uma nova estrutura do mesmo tipo da anterior.

No final da string marcámos numa flag que é mesmo o final da string para não existirem problemas na pesquisa de strings.

Complexidade:

  • Inserção de uma string: O(Len). Len = tamanho da string.
  • Procurar string: O(Len). Len = tamanho da string.

A partir daqui já podemos ver que a complexidade é muito boa visto que se guardássemos as strings num vector (como se costuma fazer) teríamos uma complexidade de O(n * len) em que n é o número de strings e len é o tamanho máximo de cada string - temos que percorrer todas as strings e comparar uma a uma com a que queremos encontrar.

Vou deixar aqui uma imagem com a estrutura.
Estrutura Tries
http://www.topcoder.com/i/education/alg_tries.png


O código fica assim:

#include <cstdio>
#include <cstring>
 
using namespace std;
 
const int MAX = 255;
 
typedef struct Trie
{
	struct Trie *children[MAX];
	bool is_end;
} trie;
 
void init_node (trie *node)
{
	for (int k = 0; k < MAX; k++) 
		node -> children[k] = NULL;
 
	node -> is_end = false;
}
 
void add_word (char *str, trie *head)
{
	trie *walk = head;
 
	for (int k = 0; str[k]; k++)
	{
		if (walk -> children[str[k]] == NULL)
		{
			walk -> children[str[k]] = new trie;
			init_node (walk -> children[str[k]]);
		}
		walk = walk -> children[str[k]];
	}
 
	walk -> is_end = true;
}
 
bool find_word (char *str, trie *head)
{
	trie *walk = head;
 
	for (int k = 0; str[k]; k++)
	{
		if (walk -> children[str[k]] == NULL) 
			return false;
		walk = walk -> children[str[k]];
	}
	if (walk -> is_end == true) 
		return true;
}
 
int main ()
{
	char input[MAX];
	trie *head = new trie;
 
	init_node (head);
 
	scanf ("%s", input);
	while (strcmp (input, "stop") != 0)
	{
		add_word (input, head);
		scanf ("%s", input);
	}
 
	scanf ("%s", input);
	while (strcmp (input, "exit") != 0)
	{
		if (find_word (input, head) == true) 
			printf ("String found!\n");
 
		else 
			printf ("String not found!\n");
 
		scanf ("%s", input);
	}
 
	return 0;
}
algoritmo/tries.1305673953.txt.gz · Última modificação em: 2018/05/14 21:37 (edição externa)