62 respostas a este tópico

[paperless]

Alguém sabe onde posso arranjar uma lista de palavras da língua portuguesa?

Do dicionário do firefox consegui 31497 palavras mas queria mais

(já agora: http://www.mediafire.com/?tmzd9mylnvt)

Quero fazer um programa que sugira soluções para palavras cruzadas ou problemas equivalentes.

Cumprimentos.

[paperless]

Encontrei a resposta:

http://natura.di.umi.../misc/wordlist/


Aí pode-se encontrar uma lista com 688106 palavras  :w00t2:

Espero que possa ser útil  a mais gente.

Nota: Essa lista inclui verbos conjugados, penso que seja por isso que é tão grande,

Se quiserem ordenar a lista façam isto:

Citar

cat wordlist.txt | sort > listaordenada.txt

[Amoguai]

Boa tarde!

Eu estou a construir um programa que compara uma palavra A com todas as palavras de um dicionário e se encontrar uma palavra igual, valida essa palavra A.
Uma espécie de corrector automático, se quiserem.

Ora o problema é que com este TXT existem muitas sequências de caracteres que não são palavras.
Será que existe alguma maneira de arranjar estas palavras todas de forma a que se possam por num array?

Cumprimentos,
Amoguai

[IceBrain]

Citar

Ora o problema é que com este TXT existem muitas sequências de caracteres que não são palavras.

Queres dizer as siglas (tipo UNESCO ou XIII) ? Se for isso, acho que basta remover todas as palavras que contenham mais do que um caractere maiúsculo seguido:

Código (Bash):

 grep -v -E '[A-Z]{2}' wordlist.txt

(para perceber isto, 'man grep' e 'man regex')

[Amoguai]

Não, eu refiro-me ao facto de as palavras estarem "coladas" umas às outras e de não haver maneira de distinguir umas das outras a não ser usando a intuição (que os PC's não têm  ).

No início do TXT até podemos observar que o início de cada palavra começa com letra maiúscula, o que seria uma maneira de distinguir diferentes palavras para as poder então comparar, mas lá para o meio, essa convenção perde-se e não há maneira de distinguir uma palavra da outra, para que seja possível comparar cada uma das palavras do dicionário com a palavra introduzida pelo utilizador.

Por exemplo, o conjunto de caracteres definido pelo fim de uma palavra e pelo início de outra não é um conjunto de caracteres a que possamos chamar de palavra, ou seja, não é uma palavra válida. Se o utilizador introduzir uma palavra deste género, esta pode estár contemplada no TXT mas continua a ser uma palavra inválida.

Espero estár a fazer-me compreender
Abraço!
Amoguai

[mogers]

Não estarás a usar o notepad do windows para abrir o ficheiro? O notepad tem problemas em visualizar correctamente os ficheiros que não estejam de acordo com o esperado em windows (estes ficheiros provavelmente usam apenas '\n' como fim de linha, ao estilo unix, em vez do '\r'+'\n' do estilo windows). Usa antes o notepad++ http://notepad-plus....net/uk/site.htm que é um excelente editor de texto.

Eu fiz o download do ficheiro "latest" e pareceu-me tudo ok. Uma palavra por linha.

[mogers]

Ja agora, se não tiveres problemas de memória, uma Trie parece-me ideal para o que queres fazer.

[Amoguai]

Exacto, instalei o Notepad++ e apresentou-me uma palavra por linha, como devia ser.

Tenho 4GB de RAM, mas o que é uma Trie?    :-[

EDIT: Ok, já sei, eu conhecia-a por "Tree" do inglês árvore  :P E o "trie" nem vem de tree, vem de retrieval. Enfim, aprendem-se coisas todos os dias

[mogers]

Trie é um tipo especial de árvore. Eu coloquei o link para a descrição na palavra Trie, se calhar não reparaste - http://en.wikipedia.org/wiki/Trie

[mjamado]

Oh mogers, para esta situação não será overkill usar um trie?

Do meu ponto de vista, mais vale ordenar a lista de palavras à priori e depois usar uma pesquisa binária - na pior das hipóteses, percorre-se meio array...

[Warrior]

Na pior das hipóteses percorre-se log n elementos do array, metade era imenso.
Com a trie a pesquisa é feita em tempo de constante, além de não se perder tempo a ordenar (ordenação é n log n). É mais frequentemente usada em casos em que o dicionário pode mudar, porque manter o array ordenado é muito dispendioso, mas é melhor em todos os casos e relativamente fácil de implementar, portanto não vejo porque será overkill. Especialmente na secção de algoritmia e lógica!

[mogers]

mjamado, em 18 de Fevereiro de 2010 - 22:08, disse:

Oh mogers, para esta situação não será overkill usar um trie?

Do meu ponto de vista, mais vale ordenar a lista de palavras à priori e depois usar uma pesquisa binária - na pior das hipóteses, percorre-se meio array...

Depende um bocado da utilização real que a aplicação tenha. Ele falou em comparar uma palavra com todas do dicionário para a validar.

O ficheiro de palavras que foi referido tem mais de 690.000 palavras, por isso o uso de uma Trie não é nada overkill, pelo contrário. E ainda é preciso ver que uma Trie é simples de implementar, por isso nem é pela complexidade da coisa que se deve ignorar.

[mjamado]

Não me parece que um dicionário de palavras portuguesas com quase 700k entradas mude frequentemente, mas ok...  :ipool:

A ordenação é feita uma vez, em ambiente de development, nunca em runtime, porque o dicionário não muda assim tão frequentemente, do meu ponto de vista. Mesmo que mudasse, era uma questão de se ser disciplinado na inserção, inserindo os novos registos na posição correcta.

Comparar a dificuldade de implementação duma pesquisa binária com uma estrutura trie, vai lá, vai...

Algoritmia e Lógica, muitas vezes, passa por encontrar a melhor solução tendo em consideração todos os parâmetros do problema. Neste caso, mantenho, é overkill implementar um trie - e duvido mesmo que seja mais rápido, em média, do que uma pesquisa binária, que nem sequer requer o desenvolvimento duma estrutura, usando um simples array numérico.

[mogers]

mjamado, em 18 de Fevereiro de 2010 - 23:16, disse:

Comparar a dificuldade de implementação duma pesquisa binária com uma estrutura trie, vai lá, vai...

Visto que uma Trie (com funções de inserção e pesquisa) se implementa com cerca de 25 linhas, tendo em conta o normal nas estruturas de dados, isto é muito pouco.

Citar

Neste caso, mantenho, é overkill implementar um trie - e duvido mesmo que seja mais rápido, em média, do que uma pesquisa binária, que nem sequer requer o desenvolvimento duma estrutura, usando um simples array numérico.

Em primeiro lugar, como propões implementar um dicionário e pesquisa de uma palavra num dicionário com um array numérico?
Se tens dúvidas na eficiência, é só fazer as contas (vou ignorar tanto a ordenação/leitura das palavras para o dicionario como a inserção na trie que são coisas feitas apenas uma vez no inicio do programa):

Arredonde-se N, o número de palavras, para 700.000
Quer-se saber se uma palavra de tamanho P pertence ao dicionário.

a) Pesquisa Binária (PB) num dicionário seria O( log N ) se a comparação de elementos fosse O(1) como se costuma considerar com números, mas aqui temos palavras. A comparação necessita de O(P). Assim usando PB é necessário O( P * log N )

Pesquisa numa Trie. Tal como foi dito, é linear no tamanho da palavra a pesquisar - O(P)


Não há grandes dúvidas em afirmar qual o mais rápido. log₂(700000) ~ 19, por isso a PB é cerca de 19 vezes mais lenta que a pesquisa numa Trie.


edit: eu tenho uma implementação de Trie em C++, noutras linguagens poderá ser preciso mais ou menos linhas de código, mas a ideia base mantem-se.

[mjamado]

Implementação em pseudo-código (tal como tu, também ignorei a construção e ordenação do array, que já disse que deve ser feita à priori e não sempre que isto é executado):

Código :

palavras = ['aardvark', ..., 'zztop']; // array numérico
palavraPesquisar = 'palavra'

tamanhoArray = palavras.tamanho;
curIndex = tamanhoArray / 2; // eventualmente, dependendo da linguagem, poderá ser necessário aqui um floor
ultimoLimiteSup = tamanhoArray;
ultimoLimiteInf = 0;

encontrou = falso;
iteraccao = 0;

repetir
    se palavras[curIndex] = palavraPesquisar então
        encontrou = verdadeiro;
        parar repetir;
    senão se palavras[curIndex] > palavraPesquisar // ver nota
        curIndex += (ultimoLimiteSup - curIndex) / 2;
    senão
        curIndex -= (curIndex - ultimoLimiteInf) / 2;

    iteraccao++;
enquanto (não encontrou) e (iteraccao < tamanhoArray / 2);

Nota: a maior parte das linguagens aceita a comparação de strings. Sinceramente, nem me lembro de nenhuma que não aceite, mas admito que exista, visto já não trabalhar com linguagens antigas (Pascal, C, Lisp) há muitos anos. Também não seria por aí, seria fácil implementar qualquer coisinha.

Implementado em 22 linhas Incluíndo diversos espaçamentos e indentação eventualmente desnecessária nos "senão", que eu gosto do meu código limpinho e legível.

Tal como eu tinha dito, um mero array numérico, e, na pior das hipóteses, seria preciso iterar por meio array.

Claro que, se fosse mesmo para nos armarmos aos cucos e fazer uma pesquisa que fosse rápida em média, preferia partir deste pseudo-código e implementar, por exemplo, o cálculo da distância teórica, em vez de andar aos saltos entre metades - por exemplo, se a pesquisa é "c...", viemos de "f..." e estamos em "b...", em vez de saltar para o meio, saltavamos para 1/4.

Mas implementa lá isto em C++, pega no ficheiro de texto, e corre uma contra a outra em 100 palavras distintas. Nada como testar para tirar as dúvidas. Já agora também estou curioso.

[mogers]

As contas que te apresentei são em termos do worst case. Não me está a apetecer implementar isso agora, apesar de não ser muita coisa, mas já mostrei os tempos.

Isso não é uma pesquisa binária, uma pesquisa binária demora O( log N ) iterações e não O(N/2) no worst case.
Aquele O(P) é porque a comparação de strings vai necessitar de percorrer P caracteres.

Btw, 100 palavras seria muito pouco tendo em conta a dimensão do dicionário.

PS: para mim isso é um array de strings e não numérico.

Se alguém quiser, o código da Trie é

Código (C++):

#define MAX 26
struct trie {  
    trie * next[MAX];
    int val;
 
    trie()  { val = 0; memset(next, 0, MAX * sizeof(trie *));   }
    ~trie() { for(int i=0;i<MAX;i++) if(next[i]) delete next[i]; }
};
//insere caso a palavra nao exista, retorna o numero de ocorrências
int trie_insert(trie * t, const char *s) {  
    while(*s) {
        if(!t->next[*s-'a']) t->next[*s-'a'] = new trie();
        t = t->next[*s-'a'];
        s++;
    }
    return ++t->val;
}
int trie_search(trie *t, const char *s) {
    while(*s) {
        if(!t->next[*s-'a']) return 0;
        t = t->next[*s-'a'];
        s++;
    }
    return t->val;
}

E uma pesquisa binária correcta seria

Código :

limiteSup = tamanhoArray-1;
limiteInf = 0;
repetir
    curIndex = ( limiteInf + limiteSup ) / 2
    se palavras[curIndex] = palavraPesquisar então
        encontrou = verdadeiro;
        parar repetir;
    senão se palavras[curIndex] > palavraPesquisar
        limiteSup = curIndex - 1
    senão
        limiteInf = curIndex + 1
enquanto (não encontrou) e (limiteInf <= limiteSup);

[mjamado]

Ups, esqueci-me de actualizar os limites...  :rant_01: E sim, tem todos razão, não é n/2, é log n, sim senhor. A cena das metades deixou-me confuso.

Estás a ver, ainda atalhaste mais o código do que eu... Quando eu digo que o array é numérico, é a indexação. Pronto, um dicionário com chaves numéricas, está mais correcto.

Já mostraste os tempos, tal como disseste, e bem, para os piores cenários. Numa utilização normal, queremos é saber dos cenários médios.

Além disso, e é esse o meu ponto desde o início desta discussão, a questão dos tempos é uma faca de dois "legumes". Neste particular, com menos de 1M de registos sem grandes perspectivas de crescimento, qualquer linguagem da treta (até o PHP, que costuma ser uma nódoa nestas coisas) itera pelo array enquanto o diabo esfega um olho...

Se a pesquisa binária* demorar 400 ms a fazer isto e a estrutura trie for as tais 20x mais rápida (que continuo a duvidar para os casos médios), eu quero é mandar isto à fava e trocar a velocidade absoluta (ie: não em percentagem) pela facilidade de implementação, porque estamos a falar duma diferença de 380 ms.

Também achei piada às tuas 25 linhas...  :biggrin: Tens para ali inlines que é obra...

______________________________
* aliás, a maior parte das linguagens até tem coisinhas bem mais directas - voltando ao PHP, está ali a instrução in_array mesmo a olhar para nós

[mjamado]

Entretanto, estava aqui a implementar as duas coisas em C#, só para tirar as teimas, e sou gajo para ter que baixar as calcinhas...  :wallbash:

Em 20.000 testes com palavras aleatórias, das quais 5% não existem (situação worst case), a estrutura trie é entre oito a nove vezes mais rápida...

[Amoguai]

Upa, vou tentar implementar então com a Trie.

De facto, eu estava a passar cada uma das linhas/palavras do dicionário para um array, mas... meia hora passada e ainda vou no "i"...
Desculpem a nobice, mas como é que eu dou a volta a isto de maneira a que só tenha que processar isto uma vez e fique com o dicionário todo guardado num array/Trie?

EDIT: Estou a desenvolver este programa em Visual Basic 2005  :wallbash:

Abraço!

[Amoguai]

Secalhar não me perceberam

Existe alguma maneira de "compilar" o ficheiro de texto (dicionário) numa Trie/array de maneira a que cada vez que o programa se inicia não seja preciso ler cada linha do ficheiro de texto, mas já tenha acesso à Trie/Array construídos?

Cumps