Algo

[Algo] + longue Sequence commune à 2 sequences

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : [Algo] + longue Sequence commune à 2 sequences

farib

pour faire cet algo je procede en construisant un tableau qui donne les longueurs des plus longues sous chaines communes des sous-chaines

, determinees par les indices du tableau, puis en lisant la derniere ligne il est facile de reconstituer la plus longue sous

chaine. Je suis ptet pas super clair mais sans doute ceux qui connaissent cet algorithme me comprendront

$ ./plsc.exe abcdefghijkl abbcdfghj
horizontalement : abbcdfghj
verticalement : abcdefghijkl
0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1
0 1 2 2 2 2 2 2 2 2
0 1 2 2 3 3 3 3 3 3
0 1 2 2 3 4 4 4 4 4
0 1 2 2 3 4 4 4 4 4
0 1 2 2 3 4 5 5 5 5
0 1 2 2 3 4 5 6 6 6
0 1 2 2 3 4 5 6 7 7
0 1 2 2 3 4 5 6 7 7
0 1 2 2 3 4 5 6 7 8
0 1 2 2 3 4 5 6 7 8
0 1 2 2 3 4 5 6 7 8
La plus longue sous-chaine est abcdfghj

la question est : c'est une complexité m x n ,c'est pas si mal, mais en memoire ca bouffe bcp. En fait il n'est pas

nécessaire de sauvegarder tout le tableau, donc je peux ne sauvegarder que la derniere colonne remplie a chaque fois, ca fera

une belle optimisation de memoire (m+n au lieu de m*n).
Sinon Y a t-il un autre algo plus effiace que m*n ( nivo complexite, pas memoire)?

mon code, sous license GPL

Code :

#include <iostream>
#include <vector>
#include <string>
using namespace std ;
int main(int argc, char *argv[])
{
if (argc != 3 ){ cout << "erreur d'argument" << endl ; return 0;}
string Chaine_X = argv[1];
string Chaine_Y = argv[2];
vector< vector<int> > Tableau_K(Chaine_X.length()+1) ;
for (int i = 0; i <= Chaine_X.length() ; i++)
{
Tableau_K[i]=vector<int>(Chaine_Y.length()+1);
fill(Tableau_K[i].begin(),Tableau_K[i].end(),0);
}
for ( int i = 1 ; i <= Chaine_X.length() ; i++)
for ( int j = 1 ; j <= Chaine_Y.length() ; j++)
if (Chaine_X[i-1]!=Chaine_Y[j-1] && Tableau_K[i-1][j]==Tableau_K[i][j-1] && Tableau_K[i-1][j]==Tableau_K[i-1][j-1] )
{
Tableau_K[i][j]=Tableau_K[i-1][j-1] ;
}
else
{
Tableau_K[i][j]=Tableau_K[i-1][j-1]+1 ;
}
cout << "horizontalement : " << Chaine_Y << endl;
cout << "verticalement : " << Chaine_X << endl;
for ( int i = 0 ; i <= Chaine_X.length() ; i++)
{for ( int j = 0 ; j <= Chaine_Y.length() ; j++) cout << Tableau_K[i][j] << " ";cout << endl;}
string PLSC="";
for (int i = 1; i <= Chaine_Y.length(); i++)
if (Tableau_K[Chaine_X.length()][i]==Tableau_K[Chaine_X.length()][i-1]+1)
PLSC+= Chaine_Y[i-1];
cout << "La plus longue sous-chaine est " << PLSC << endl;
return 0;
}

Publicité

Taz

bisounours-codeur

je regarde l'alog, mais niveau implémentation, y a du boulot!

farib

++Taz a écrit :

je regarde l'alog, mais niveau implémentation, y a du boulot!

je sais. LA c'est l'étape : "ca marche".

ensuite, je pase à l'étape : "çai bô" et "çai rapide"

Taz

bisounours-codeur

putain, sur google, y a plein de resultat avec ton algo en m*, mais des fois est evoqué un algo en temps pseudo linéaire

Evadream -jbd-

J'ai trouvé une page qui pourrait peut-être t'intéressé :

http://www.crpgl.lu/cortina/Details/LCS.html

Je n'ai pas apercu de calcul complexité, mais ca semble balayer pas mal de type de solutions !

@+

Taz

bisounours-codeur

c'est le meme aglo qui est expliqué

Evadream -jbd-

Ok, je sors.

Taz

bisounours-codeur

http://www.csse.monash.edu.au/~llo [...] 6.IPL.html

meme algo, à un truc pres, qui donne un bon boost apparemment

farib

++Taz a écrit :

http://www.csse.monash.edu.au/~llo [...] 6.IPL.html

meme algo, à un truc pres, qui donne un bon boost apparemment

merci bien, je sens que je v passer un bon bout de temps là-dessus le comprendre. De la m^me maniere qu'il a fallut qq heures pour comprendre mon algo qui s'implémente en qq misérables lignes de code

Taz

bisounours-codeur

Publicité

farib

bon la j'ai compris ou était l'astuce, masi j'ai pas encore compris pourquoi effectivement ca marchait

Citation :

Each segment extends from the position of a 1 in rowi-1 rightward to the position to the left of the next 1. If the left-hand bit of rowi-1 is zero, the left-most segment extends from the left of the bi-string to the position left of the first 1. Rowi is formed by setting only the right-most 1 bits in each segment of the bi-string. If a segment is all zero, the bit defining the left end of the segment should be set in rowi (that is the segmenting bit in rowi-1). This can be ensured by first or-ing rowi-1 into the bi-string.

je comprend que la c genial, mais je comprend pas pkoi

par la suite, y'a encore 2-3 optimsation que je dois comprendre, mé c pas facile

Taz

bisounours-codeur

ben comme toutes les optimsiations aggressives, c'est cahud...

quand t'auras besoin de conseil d'implémentation, n'hesite pas

farib

bon, la g compris ce qu'il faillait faire, mais je demande que le taré qui a mis au point cette technique soit interné en maison de repos.

sinon, nivo implémentation, je vois pas ce que tu me reproches ? ( sans doute as-tu raison mais je suis aveugle)

farib

y'a juste son point 2.3 ke je capte pas, pour prendre une LCS il suffit de lire la dernière ligne, et pourtant lui il fait une technique super compliquée...

Taz

bisounours-codeur

doit y avoir un moyen d'améliorer les choses si les chaines sont pas de meme longueur [:spamafote]

farib

pour ce qui est de de trouver une PLSC, il suffit de "lire" une dernieres ligne ou colonne

---------------
Bitcoin, Magical Thinking, and Political Ideology

Taz

bisounours-codeur

en tout cas je sais pas si tu as vu, mais avec seulement les 2 dernières lignes, on fait tout le boulot sans problèmes

Taz

bisounours-codeur

hey, mais j'ai bien l'impression que l'algo foire dis-donc?

Angel_Dooglas

Le dernier des humains

farib a écrit :

Non, la complexite restera de l'ordre m*n.

farib

++Taz a écrit :

hey, mais j'ai bien l'impression que l'algo foire dis-donc?

lekel ?

---------------
Bitcoin, Magical Thinking, and Political Ideology

farib

++Taz a écrit :

en tout cas je sais pas si tu as vu, mais avec seulement les 2 dernières lignes, on fait tout le boulot sans problèmes

vivi, puis qu'elles indiquent les lettres a prendre dans l'autre chaine pour former la PLSC

---------------
Bitcoin, Magical Thinking, and Political Ideology

Taz

bisounours-codeur

ben regarde ton exemple

farib

++Taz a écrit :

ben regarde ton exemple

bah il est coherent.

---------------
Bitcoin, Magical Thinking, and Political Ideology

Taz

bisounours-codeur

abcdefghijkl abbcdfghj

abcdfghj n'est pas dans abcdefghijkl
abcdfghj n'est pas dans abbcdfghj

c'est pas ce que j'appelle etre en "commun"

farib

++Taz a écrit :

abcdefghijkl abbcdfghj

abcdfghj n'est pas dans abcdefghijkl
abcdfghj n'est pas dans abbcdfghj

c'est pas ce que j'appelle etre en "commun"

tu ne connais pas le probleme

en fait ce probleme de plsc c'est la plus longue sous chaine obtenue en supprimant si necessaires de elements de la chaine 1 ou 2, c'est pour cela que ca devient interessant, avec ta definition c trivial

( application : diff, en considerant qu'une ligne de code est un symbole )

Message édité par farib le 26-05-2003 à 12:45:59

---------------
Bitcoin, Magical Thinking, and Political Ideology

Taz

bisounours-codeur

avec ma definition c'est pas trivial, mais la tienne je la comprends pas, on dirait l'interesction d'ensemble

farib

++Taz a écrit :

avec ma definition c'est pas trivial, mais la tienne je la comprends pas, on dirait l'interesction d'ensemble

avec ta définition ca se fait de maniere quasi-linéraire

moi c'est la plus longue sous chaine commune en supprimant des élements

application : tu veux comparer deux chaines d'adn, une originale et une mutée. la mutée, elle aura des segments insérés, supprimes, ou remplacés. masi grace a l'algo tu retrouve la plsu longue chaien commune.

---------------
Bitcoin, Magical Thinking, and Political Ideology

Angel_Dooglas

Le dernier des humains

farib a écrit :

avec ta définition ca se fait de maniere quasi-linéraire

moi c'est la plus longue ~~sous~~ chaine commune en supprimant des élements

application : tu veux comparer deux chaines d'adn, une originale et une mutée. la mutée, elle aura des segments insérés, supprimes, ou remplacés. masi grace a l'algo tu retrouve la plsu longue chaien commune.

Et la je pense qu'il n'y a plus de probleme de "definition".

farib

le probleme c'est qu'on l'appelle plsc

Message édité par farib le 27-05-2003 à 00:37:06

---------------
Bitcoin, Magical Thinking, and Political Ideology

Angel_Dooglas

Le dernier des humains

Ce qui est qualifie de sous chaine ici est en fait la plus longue chaine commune possible avec gaps:
En reprenant ton exemple:

abbcdfghj
ab-cd-fgh-j--
abcdefghijkl

Taz

bisounours-codeur

__avec__ des gaps... la notion de chaine/sequence en prends un coup... mais si ça te satisfait [:spamafote]

Angel_Dooglas

Le dernier des humains

Sans gaps, on ne s'en sort pas dans les sequences biologiques. Par contre cette maniere de faire n'est absolument pas interressante pour trouver des alignements biologiquement satisfaisants.

Publicité

FORUM HardWare.fr

Programmation

Algo

[Algo] + longue Sequence commune à 2 sequences

Sujets relatifs
Algo pour conversion Timestamp <-> Date ISO	algo de conversion d image 16 bits en 24 bits
[HTML] Problème d'esthétique : déformation de page avec url tro longue	Algo QuickSearch
[Oracle] utiliser une sequence dans une insertion	[Algo] Affichage d'un tableau dans un format particulier
[algo] tri de liste+retirer les doublons	Algo de prim, kruskal et dijskra
[Algo] Détecter l'orientation d'une image (et étapes intermédiaires)	Algo de Dijkstra en C : j'y arrive pas !!!!
Plus de sujets relatifs à : [Algo] + longue Sequence commune à 2 sequences

Page générée en 0.075 secondes