• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

paperless

Lista de palavras / dicionário de palavras em português (de Portugal)

65 mensagens neste tópico

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Encontrei a resposta:

http://natura.di.uminho.pt/download/sources/Dictionaries/misc/wordlist/

http://natura.di.uminho.pt/download/sources/Dictionaries/wordlists/

Aí pode-se encontrar uma lista com 688106 palavras.

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:

cat wordlist.txt | sort > listaordenada.txt

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
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:

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

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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  :D).

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 :P

Abraço!

Amoguai

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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 ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

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 )

b) 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. log2(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 mantém-se.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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):

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. Incluindo 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, saltávamos 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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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 é

#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

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); 

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ups, esqueci-me de actualizar os limites...  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... :D 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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

Abraço!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Secalhar não me perceberam :P

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 :thumbsup:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pelo que percebi a serialização armazena um objecto num ficheiro XML, que pode posteriormente ser usado.

O meu problema é precisamente o contrário, eu já tenho o meu ficheiro, que é um dicionário em txt de ~700.000 palavras.

O que eu preciso é de arranjar uma solução para a fastidiosa tarefa de puxar todas as linhas do txt para um array de cada vez que o programa se abre.

Por exemplo, um processador de texto com correcção automática há de conseguir aceder ao seu dicionário sem ter que o escrever de raiz num array ou trie de cada vez que se o abre. Muito provavelmente será possível pegar nesse array ou trie, uma vez feitos, e armazená-los num ficheiro que permita o acesso imediato assim como a todas as funções que se usariam normalmente como se o array fizesse parte do programa.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pelo que percebi a serialização armazena um objecto num ficheiro XML, que pode posteriormente ser usado.

(...) Muito provavelmente será possível pegar nesse array ou trie, uma vez feitos, e armazená-los num ficheiro que permita o acesso imediato assim como a todas as funções que se usariam normalmente como se o array fizesse parte do programa.

É precisamente esse o problema que a serialização de objectos resolve! Ela permite armazenar a estrutura com todos os dados num ficheiro/buffer para depois os carregares. Lê o primeiro parágrafo da wikipédia:

http://en.wikipedia.org/wiki/Serialization

Eu próprio experimentei implementar uma trie em C#, e o ficheiro demora um tempo considerável a carregar (talvez até seja da minha implementação, não tenho forma de confirmar isso, mas acredito que o total do ficheiro contribua para isso). Lembra-te que tu tens de meter essas linhas nalgum lado, se não as queres num ficheiro, então talvez as possas colocar já no programa. Mas lembra-te que isso te vai pesar no executável.

Quando falas no Word, acredito que eles não usem este tipo de base de dados para as correcções ortográficas, mas se baseiem nas variantes das palavras, por exemplo, supõe uma palavra 'bacdf', que se pode escrever das seguintes maneiras

bacdf

becdf

bicdf

bocdf

bucdf

Repara que podes por qualquer vogal. Então para puopar essas cinco combinações, podes colocar um wilcard, seja *, que vale por todas as vogais: ficas com apenas 1 representação em vez das 5 possíveis:

b*cdf

Outra forma de reduzir muito comum é também os pronomes (acho que são os pronomes... :-[ ), do género -se, -lhe, etc, que completam as frases e também sofrem desta "optimização". Logo nestas, se deres uma olhada ao ficheiro, vês que cortam bastante e essas 700k linhas são facilmente reduzidas.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Há estruturas de dados mais "úteis" (permitem operações mais diversificadas) que uma Trie, como as Suffix Tree, mas são significativamente mais difíceis de implementar.

Se não quiseres usar serialização, podes escrever para um ficheiro a árvore num formato mais fácil de inserir.

Por exemplo, em vez de:

aaa

aaab

aab

aac

ac

Podes ter:

aaa

>b

<b

.c

<c

E passas a navegar na árvore de maneira muito simples, em vez de partir da raiz sempre que pretendes inserir uma palavra.

Podes criar qualquer sintaxe que pretendas.

(Neste meu exemplo, > significa mais um caracter, < menos um, . os mesmos, seguido da alteração relativamente ao último (podes ser mais de um caracter..))

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Fiquei com a ideia que um ficheiro XML era um ficheiro de texto especialmente formatado. Sendo um ficheiro de texto, pode este ser "puxado" directamente para a memória e comportar-se como um array/Trie como se fizesse parte do programa?

Se não for o caso, não será a mesma coisa ter um ficheiro de texto especialmente formatado (e consideravelmente maior por causa dessa formatação) e lê-lo linha a linha para a memória e ter o tal dicionário em TXT?

Alguém que brilhe uma luz sobre este assunto :P

0

Partilhar esta mensagem


Link 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