Jump to content
Amoguai

[Dúvida] Data Structure

Recommended Posts

Amoguai

Boa tarde a todos!

Se já existe este tópico, algures neste fórum, peço desde já desculpa por não o ter encontrado; chances são que já existe.

Eu estou a criar um pequeno projecto que envolve validar palavras de um dicionário.

Se tivermos que criar uma estrutura grande de dados (todas as palavras de um dicionário), e ter que realizar uma procura que seja o mais rápida possível, para, por exemplo, correcção automática em tempo real, que estrutura de dados devemos implementar?

Encontrei vários artigos na internet acerca de Binary Search Trees e como as implementar, mas penso que o que eu preciso é de uma Search Tree que não seja binária, porque para cada letra do alfabeto existem 26 ramos/letras e assim consecutivamente até se formarem todas as palavras do dicionário. Não consegui encontrar artigos que não fossem sobre BST's. Gostaria que alguém me dissesse qual a melhor estrutura de dados para este efeito, que estrutura de dados é usada nos processadores de texto mais comuns M$ Word/OpenOffice Writer, e já agora alguns links para artigos e how-to's.

Abraços!

Amoguai

Share this post


Link to post
Share on other sites
Localhost

Só mesmo para adicionar algo ao tópico deixo aqui uma implementação minha de uma Trie em C++:

#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;
}


here since 2009

Share this post


Link to post
Share on other sites
Warrior

A minha resposta imediata seria "Trie" até que cheguei a esta parte:

e ter que realizar uma procura que seja o mais rápida possível, para, por exemplo, correcção automática em tempo real

e fiquei na dúvida.

Se o que pretendes é correcção automática, ou seja, dar sugestões para palavras incorrectas, então vais precisar de calcular levenshtein distances frequentemente e a Trie deixou de ser a solução adequada..

Share this post


Link to post
Share on other sites
mjamado

A minha resposta imediata seria "Trie" até que cheguei a esta parte:e fiquei na dúvida.

Se o que pretendes é correcção automática, ou seja, dar sugestões para palavras incorrectas, então vais precisar de calcular levenshtein distances frequentemente e a Trie deixou de ser a solução adequada..

Por acaso, Warrior, também estava a pensar nisso - mas usava uma Trie na mesma. Depois, para fazer as correcções, puxava todas as palavras da Trie a menos duma distância de Levenshtein definida (sei lá, o arredondamento para cima de 1/5 do tamanho da palavra?), usando em meu benefício a velocidade de pesquisa da Trie, com wildcards.

Por exemplo: amanhõ; distância de Levenshtein máxima permitida: ceil(6*1/5) = 2. Pesquisar: ??anhõ, ?m?nhõ, [...], aman??, etc. Dar os resultados ordenados da menor para a maior distância.


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

Share this post


Link to post
Share on other sites
Warrior

O problema é que em palavras grandes e permitindo inserções/modificações, temos um conjunto de wildcards para pesquisar enorme. E a sua geração não é trivial..

Share this post


Link to post
Share on other sites
mjamado

O problema é que em palavras grandes e permitindo inserções/modificações, temos um conjunto de wildcards para pesquisar enorme. E a sua geração não é trivial..

Não me parece "enorme"... Repara, para o exemplo que dei, vamos imaginar uma palavra errada de 20 caracteres (que já é um grande palavrão), somamos-lhe mais dois caracteres no início e no fim, 22 posições; com a distância definida, será ceil(22/5) = 5, o que vem a dar C(22;5) = 26.334 pesquisas. Muitas delas, vazias. Não sei para que plataforma o OP está a pensar desenvolver isto, mas qualquer dispositivo móvel desenrasca 26k pesquisas de Trie enquanto o diabo esfrega um olho.

Para uma palavra mais "normal", imaginemos, 8 caracteres, mais dois dá 10, sendo ceil(10/5) = 2, e C(10;2) = 45.

Isto parece-me o mais rápido, tanto em execução como em implementação. Está-me a escapar alguma coisa?


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

Share this post


Link to post
Share on other sites
Warrior

Sim, o facto que 26.334 wildcards não são 26.334 palavras. Na verdade, num caso extremo, tendo 5 '?', podemos estar a falar de 11881376 palavras por wildcard.

De qualquer modo, não era a eficiência o que me preocupava. Repara que só consideraste edições, seria preciso agora acrescentar inserções e combinações das duas..

Share this post


Link to post
Share on other sites
Amoguai

Eu lembrei-me agora de um pormenor importante acerca das tries. A validação e a remoção de elementos.

Digamos que queríamos verificar se "Anticon" é uma palavra válida e tinhamos na nossa Trie a palavra "Anticonstitucionalissimamente". Já que "Anticonstitucionalissimamente" contém "Anticon", esta seria incorretamente uma palavra válida. Por outro lado a palavra "Anagrama" tem "Ana" e neste caso "Ana" já é uma palavra válida (assim como "Camaleão" tem "Cama" e por aí adiante).

Outra coisa que me preocupa é que tem que ser possível remover palavras da estrutura de dados. Como é que se remove a palavra "Ana" sem remover todas as palavras que começam por "Ana*"?

Eu pensei em fazer duas estruturas de dados em paralelo, já que memória não é um problema. Uma Trie para a procura e um array para remoção de palavras que não acabem em folhas da Trie.

Mas o problema da validação permaneceria. Secalhar a Trie não é a estrutura de dados adequada ao meu problema, ou estará a escapar-me alguma coisa?

Share this post


Link to post
Share on other sites
Warrior

Tipicamente, os nós da Trie possuem uma flag de "fim de palavra" que indicam se uma palavra termina em determinado nó.

Ou seja, verificar a existência de uma palavra envolve verificar a existência do nó E a verificação da flag. Acho que para a remoção rapidamente percebes como implementar.

Share this post


Link to post
Share on other sites
mjamado

Amoguai, a Trie sabe o que é uma palavra válida: nos ramos, tem um indicador de terminação, activado ou não. Ali no código do Localhost é a propriedade is_end.

Com o teu exemplo: a (!is_end) -> n (!is_end) -> a (is_end) -> g (!is_end) -> r (!is_end) -> a (!is_end) -> m (!is_end) -> a (is_end).

EDIT: ya, o que o Warrior disse.

Warrior, as 26k pesquisas não dão, sequer, 26k respostas. O exemplo dado foi, propositadamente, uma situação limite. Palavras com 20+ caracteres não são assim tão comuns. Por curiosidade, corri uma pesquisa com 22 '?' numa Trie com aquele famoso dicionário da Universidade do Minho, e devolveu 700 e tal resultados - muitos deles são palavras hifenizadas (-lhes, -los, essas coisas).

Verdade que só contemplei edições, contemplar eliminações e inserções é só uma extensão do pensamento, mas continua a ser relativamente trivial...


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

Share this post


Link to post
Share on other sites
Amoguai

Desculpem a nobice em C (o meu background é em java  :P ), mas não consegui perceber que parte da estrutura guarda o caracter. A variável children é do tipo struct e a is_end é booleana. Outra coisa que me fez confusão foram aqueles parentesis rectos à frente de children[var]: às vezes var é int outras é char.  :wallbash:

Share this post


Link to post
Share on other sites
Localhost

Desculpem lá não ter implementado a função de remoção de uma palavra. Nunca cheguei a implementar isso mas penso que a ideia é:

1) Procurar pelo nó na Trie em que exista apenas uma posição no vector children que seja diferente de NULL (que não esteja ocupado).

2) Eliminar esse nó da Trie, eliminando assim todos os outros "abaixo" desse.

Correcto?


here since 2009

Share this post


Link to post
Share on other sites
Amoguai

Não é só isso. Tens o outro caso em que a palavra que queres eliminar está contida dentro de outras palavras, como por exemplo "cama" em "camaleão". Neste caso é só alterar o is_end para false.

Ou seja, tens que ir ao último caracter da palavra e verificar se esse children tem pelo menos um nó. Se sim é só alterar o is_end para false. Se não tens que andar para trás na àrvore até encontrares um is_end == true. Apagas o nó que estiver à frente desse, apagando todos os outros abaixo dele.

Penso ser isso.

Alguém me pode responder à minha pergunta 2 posts atrás? :P

Share this post


Link to post
Share on other sites
mjamado

Amoguai, se te sentires mais à vontade com C#, tens uma implementação de Trie no meu site pessoal com pesquisa, eliminação e contagem.


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

Share this post


Link to post
Share on other sites
Amoguai

O meu problema não é a implementação, é a sintaxe. Também não conheço C#, mas pode ser que ajude. Põe aí o link do teu site pessoal.

EDIT: Devias ter o link do teu site na tua assinatura :P

Share this post


Link to post
Share on other sites
mjamado
EDIT: Devias ter o link do teu site na tua assinatura ;)

'Tás a ver o meu avatar? Por baixo, tem um mundo azul... Topas:P


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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.