[SP-pm] Bioinformática e Sequenciamento [Was: ordenando arquivos.]

Mon Aug 1 12:23:50 PDT 2011

Vc tá afim é de perder o emprego mesmo né!?!?

Porra, programa esses scrappers aí cara! :D

Cheers!

2011/8/1 Stanislaw Pusep <creaktive at gmail.com>

> Sim, seria um node para cada char, no caso ideal; e, para piorar: não
> seriam apenas 3 strings, mas sim N strings. A ideia é o cúmulo da preguiça:
> ao invés de fazer scrappers individuais para os sites, fazer um
> "destemplatizador", um programa que percorre sites relativamente grandes
> (>1K páginas) e descobre o que é forma e o que é conteúdo, automaticamente.
> Um algoritmo bacana é implementado via Tree::Suffix (
> http://en.wikipedia.org/wiki/Longest_common_substring_problem), mas é
> impraticável, para esta aplicação, em qqer coisa abaixo do Blue Gene :(
>
> ABS()
>
>
>
> 2011/7/29 Bruno Buss <bruno.buss at gmail.com>
>
>> 2011/7/29 Stanislaw Pusep <creaktive at gmail.com>
>>
>>> Perlssoal, não sei se isso tem a ver com o tópico, mas tenho a seguinte
>>> coleção de strings (1 por linha):
>>>
>>> <html><head><title>teste 1</title></head><body><h1>teste
>>> 1</h1>qwerty</body></html>
>>> <html><head><title>teste 2</title></head><body><h1>teste
>>> 2</h1><h2>subtitulo</h2>asdfghj</body></html>
>>> <html><head><title>404</title></head><body>not found</body></html>
>>>
>>> Quero obter a seguinte estrutura (espécie de grafo):
>>>
>>>                                                                      -
>>> teste 1 -           ---------- qwerty -----------
>>>                                                                     /
>>>       \         /                             \
>>>                       - teste 1 -                           - <h1> -
>>>         - </h1> -                               -
>>>                      /           \                         /        \
>>>       /         \                             / \
>>> <html><head><title> --- teste 2 --- </title></head><body> -          -
>>> teste 2 -           - <h2>subtitulo</h2>asdfghj -   - </body></html>
>>>                      \           /                         \
>>>                                                  /
>>>                       --- 404 ---
>>> ------------------------- not found --------------------------
>>>
>>> Estou ciente de que, se eu empregar grafo "as is", a minha RAM vai
>>> estourar logo na home do UOL, a menos que eu "tokenize" por tags ou algo do
>>> gênero :/
>>>
>>
>> Pelo o que entendi, não... o seu problema não é o mesmo do tópico (mas é
>> mais por causa que não entendi qual era o problema original do tópico ainda,
>> estou esperando o e-mail do Thiago explicando para que serve a ordenação)...
>> apesar que o seu problema tem alguns equivalentes em bioinfo.
>>
>> Sobre o seu problema, talvez o que você queira é algo como um algoritmo de
>> distância de edição:
>> http://en.wikipedia.org/wiki/Levenshtein_distance
>>
>> O problema desse tipo de algoritmo é que ele é O(mn), logo com duas
>> strings grandes a sua complexidade vai crescer rapidamente.
>> Outro problema é que para conseguir esse tipo de output você vai precisar
>> guardar a matriz toda da PD (ou quase toda... mas mesmo assim ainda é muita
>> coisa).
>> E por fim... não me recordo agora uma forma - simples - de comparar as 3
>> strings em um só algoritmo... a não ser talvez adicionar mais uma dimensão a
>> matriz de PD.
>>
>> Só mais uma coisa... eu não entendi o que você quis dizer com " grafo "as
>> is" ". Seria cada char um nó do grafo ou coisa parecida? Se sim... o
>> algoritmo de distância de edição, a PD em si, pode ser modelada como um
>> grafo desse jeito (e como você mesmo disse, para strings grandes... vai
>> faltar memória).
>>
>> [ ]'s
>> --
>> Bruno C. Buss
>> http://brunobuss.wordpress.com/
>> http://www.dcc.ufrj.br/~brunobuss/
>>
>> =begin disclaimer
>>   Sao Paulo Perl Mongers: http://sao-paulo.pm.org/
>>  SaoPaulo-pm mailing list: SaoPaulo-pm at pm.org
>>  L<http://mail.pm.org/mailman/listinfo/saopaulo-pm>
>> =end disclaimer
>>
>>
>
> =begin disclaimer
>   Sao Paulo Perl Mongers: http://sao-paulo.pm.org/
>  SaoPaulo-pm mailing list: SaoPaulo-pm at pm.org
>  L<http://mail.pm.org/mailman/listinfo/saopaulo-pm>
> =end disclaimer
>
>

-- 
André Garcia Carneiro
Analista/Desenvolvedor Perl
(11)82907780
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.pm.org/pipermail/saopaulo-pm/attachments/20110801/114e5cfe/attachment.html>