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

softklin

Pesquisa de elementos comuns em 2 ficheiros

12 mensagens neste tópico

Boas pessoal.

Estava aqui a pensar fazer um programa em C para reavivar a memória, e queria fazer o seguinte: tenho 2 ficheiros para comparar, um com as frases/palavras que pretendo encontrar, e outro, maior ou de igual tamanho, no qual tenho várias frases. O que queria fazer é com as frases do primeiro ficheiro, verificar quais se encontram no segundo ficheiro (o nº de vezes é irrelevante, em principio nem sequer há repetições).

Para isto, pensei em duas soluções:

1) Percorrer cada linha e comparar com o ficheiro todo (demorado e tem muitas operações, n^2, senão estou em erro)

2) Criar uma hashtable do primeiro ficheiro, e percorrer as linhas do segundo, tentando verificar se as hashs coincidem.

3) Outra solução que eventualmente não me tenha lembrado

Que me sugerem?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

De realçar que isto não é nenhum trabalho para entregar, é um projecto pessoal e não quero que me dêem código, apenas me indiquem a solução que acham mais eficiente, ou eventualmente outra que saibam melhor!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Hmm, penso que uma Trie é uma estrutura de dados bastante eficiente para fazer esse tipo de pesquisas.

Mas é melhor esperares pelas respostas do pessoal dos algoritmos e estruturas de dados. :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Hmm, penso que uma Trie é uma estrutura de dados bastante eficiente para fazer esse tipo de pesquisas.

Mas é melhor esperares pelas respostas do pessoal dos algoritmos e estruturas de dados. :P

Bem visto, realmente não estava a pensar numa trie...
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Interessa ser muito rápido? Qual é o tamanho dos ficheiros?

Realmente não, porque em principio queria experimentar isto com ficheiro com 20 e tal linhas... Mas ao mesmo tempo, quero código que possa reaproveitar noutras situações mais complicadas, e ao mesmo tempo, começar a desenvolver soluções mais inteligentes do que o for (...) { for(...) { ... } } com estruturas de dados adequadas.

Hmm, penso que uma Trie é uma estrutura de dados bastante eficiente para fazer esse tipo de pesquisas.

Desconhecia a Trie. Pelo que vi, pareceu-me uma pesquisa em que a palavra era analisada letra a letra e "descendo" na árvore. Mas sou capaz de ter alguns problemas por causa de caracteres não ingleses como o ç e os acentos... Acho que não vai de encontro ao meu problema...  :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Porque haverias de ter algum problema com os caracteres relacionados com a estrutura de dados? Isso apenas depende dos tipo que escolheres para guardar caracteres. Se escolheres algo como UTF-8 não deves ter problema.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Estava a referir o caso, por exemplo, de comparar as letras. Com o alfabeto de A a Z é fácil, basta atribuir o 1 ao A e o 26 ao Z, mas como mete os "ç", "à", "ã", etc, torna-se difícil saber isso. Como saberia que nó seguir, visto que não conseguia fazer uma comparação?

Ou então não percebi bem o propósito da trie...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Podias sempre comparar, porque mesmo com UTF8 consegues comparar. Comparas um "ç" com um "A" sem problemas.

De qualquer forma, a melhor solução não é essa.

O algoritmo de Aho-Corasick foi construído exactamente para isso.

Permite pesquisar um conjunto de substrings numa string em O(n + m + z), sendo n o somatório dos comprimentos das strings do dicionário, m o tamanho do texto sobre o qual se efectua a pesquisa e z o número de ocorrências de padrões do dicionário no texto.

Para garantires matches completos linha a linha entre os ficheiros, basta-te não remover os "\n" na pesquisa.

Digo-te já que é bastante difícil de implementar, baseia-se numa máquina de estados. Eu pessoalmente nunca o implementei, mas sei que os melhores programadores são reticentes quando os têm que implementar em concursos, porque demora algum tempo.

O máximo que posso fazer é fornecer-te o código, já que se encontra na lista de algoritmos da FEUP, em C++, mas aprendes pouco com isso.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Informally, the algorithm constructs a trie with suffix tree-like set of links from each node representing a string (e.g. abc) to the node corresponding to the longest proper suffix (e.g. bc if it exists, else c if that exists, else the root). It also contains links from each node to the longest suffix node that corresponds to a dictionary entry; thus all of the matches may be enumerated by following the resulting linked list. It then uses the trie at runtime, moving along the input and keeping the longest match, using the suffix links to make sure that computation is linear. For every node that is in the dictionary and every link along the dictionary suffix linked list, an output is generated.

http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

Algoritmo interessante. Também usa Tries.

E aqui fica um link com montes de algoritmos relacionados com string-searching: http://en.wikipedia.org/wiki/String_searching_algorithm

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Podes utilizar Suffix Trees. Consegues a mesma complexidade do Aho-Corasick mas sempre ficas com a implementação duma estrutura de dados muito útil para uma grande quantidade de problemas.

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