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

Stanislaw Pusep creaktive at gmail.com
Mon Aug 1 11:46:06 PDT 2011


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 em gmail.com>

> 2011/7/29 Stanislaw Pusep <creaktive em 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 em pm.org
>  L<http://mail.pm.org/mailman/listinfo/saopaulo-pm>
> =end disclaimer
>
>
-------------- Pr�xima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://mail.pm.org/pipermail/saopaulo-pm/attachments/20110801/65ebbaeb/attachment.html>


More information about the SaoPaulo-pm mailing list