<div class="gmail_quote">2011/7/29 Stanislaw Pusep <span dir="ltr"><<a href="mailto:creaktive@gmail.com">creaktive@gmail.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div>Perlssoal, não sei se isso tem a ver com o tópico, mas tenho a seguinte coleção de strings (1 por linha):</div><div><br></div><div><font face="'courier new', monospace" size="1"><html><head><title>teste 1</title></head><body><h1>teste 1</h1>qwerty</body></html></font></div>
<div><font face="'courier new', monospace" size="1"><html><head><title>teste 2</title></head><body><h1>teste 2</h1><h2>subtitulo</h2>asdfghj</body></html></font></div>
<div><font face="'courier new', monospace" size="1"><html><head><title>404</title></head><body>not found</body></html></font></div><div><br>
</div><div>Quero obter a seguinte estrutura (espécie de grafo):</div><div><br></div><div><font face="'courier new', monospace" size="1"> - teste 1 - ---------- qwerty -----------</font></div>
<div><font face="'courier new', monospace" size="1"> / \ / \</font></div><div>
<font face="'courier new', monospace" size="1"> - teste 1 - - <h1> - - </h1> - -</font></div>
<div><font face="'courier new', monospace" size="1"> / \ / \ / \ / \</font></div>
<div><font face="'courier new', monospace" size="1"><html><head><title> --- teste 2 --- </title></head><body> - - teste 2 - - <h2>subtitulo</h2>asdfghj - - </body></html></font></div>
<div><font face="'courier new', monospace" size="1"> \ / \ /</font></div>
<div><font face="'courier new', monospace" size="1"> --- 404 --- ------------------------- not found --------------------------</font></div>
<div>
<br></div><div>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 :/</div></blockquote><div><br></div>
<div>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.</div>
<div><br></div><div>Sobre o seu problema, talvez o que você queira é algo como um algoritmo de distância de edição:</div><div><a href="http://en.wikipedia.org/wiki/Levenshtein_distance">http://en.wikipedia.org/wiki/Levenshtein_distance</a> </div>
<div><br></div><div>O problema desse tipo de algoritmo é que ele é O(mn), logo com duas strings grandes a sua complexidade vai crescer rapidamente.</div><div>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).</div>
<div>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.</div><div><br></div><div>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).</div>
</div><div><br></div>[ ]'s<br>-- <br>Bruno C. Buss<br><a href="http://brunobuss.wordpress.com/">http://brunobuss.wordpress.com/</a><br><a href="http://www.dcc.ufrj.br/~brunobuss/">http://www.dcc.ufrj.br/~brunobuss/</a><br>