Jump to content
Sign in to follow this  
softklin

Pesquisa de elementos comuns em 2 ficheiros

Recommended Posts

softklin

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?


Nick antigo: softclean | Tens um projeto? | Wiki P@P

Ajuda a comunidade! Se encontrares algo de errado, usa a opção "Denunciar" por baixo de cada post.

Share this post


Link to post
Share on other sites
softklin

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!


Nick antigo: softclean | Tens um projeto? | Wiki P@P

Ajuda a comunidade! Se encontrares algo de errado, usa a opção "Denunciar" por baixo de cada post.

Share this post


Link to post
Share on other sites
djthyrax

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


Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Share this post


Link to post
Share on other sites
Triton

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


<3 life

Share this post


Link to post
Share on other sites
djthyrax

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

Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Share this post


Link to post
Share on other sites
softklin

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


Nick antigo: softclean | Tens um projeto? | Wiki P@P

Ajuda a comunidade! Se encontrares algo de errado, usa a opção "Denunciar" por baixo de cada post.

Share this post


Link to post
Share on other sites
Triton

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.


<3 life

Share this post


Link to post
Share on other sites
softklin

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


Nick antigo: softclean | Tens um projeto? | Wiki P@P

Ajuda a comunidade! Se encontrares algo de errado, usa a opção "Denunciar" por baixo de cada post.

Share this post


Link to post
Share on other sites
Warrior

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.

Share this post


Link to post
Share on other sites
Triton
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


<3 life

Share this post


Link to post
Share on other sites
softklin

Estive a ver melhor as tries. Com a ajuda de um simulador em http://www-sr.informatik.uni-tuebingen.de/~buehler/AC/AC.html, percebi melhor como funciona, e parece ser bastante eficiente, caso a palavra não coincida. Pensei que tinha de seguir o esquema de uma binary search tree, que só tinha dois ramos em cada nó...

Vou ver se faço alguma coisa com isso...


Nick antigo: softclean | Tens um projeto? | Wiki P@P

Ajuda a comunidade! Se encontrares algo de errado, usa a opção "Denunciar" por baixo de cada post.

Share this post


Link to post
Share on other sites
JC1

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.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this  

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