[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