Alignement de chaines de caractères

Version imprimable

Bonjour !

Je me suis inspiré de cette fonction sur wikipedia

Code:

1
2
3
4
5
6
7
8
9
10
11
12
function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i > 0 and j > 0 and X[i] = Y[j]
        printDiff(C, X, Y, i-1, j-1)
        print "  " + X[i]
    else if j > 0 and (i = 0 or C[i,j-1] ≥ C[i-1,j])
        printDiff(C, X, Y, i, j-1)
        print "+ " + Y[j]
    else if i > 0 and (j = 0 or C[i,j-1] < C[i-1,j])
        printDiff(C, X, Y, i-1, j)
        print "- " + X[i]
    else
        print ""

pour faire ce bout de code, qui va aligner des séquences de lettres.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    public static void printDiff(int opt[][], char input1[], char input2[], int i, int j) {
 
        if (i > 0 && j > 0 && input1[i] == input2[j]) {
            printDiff(opt, input1, input2, i-1, j-1);
            //System.out.print("" + input1[i]);
 
        } else if (j > 0 && (i == 0 || opt[i][j-1] >= opt[i-1][j])) {
            printDiff(opt, input1, input2, i, j-1);
            System.out.print("-" + input2[j]);
 
        } else if (i > 0 && (j == 0 || opt[i][j-1] < opt[i-1][j])) {
            printDiff(opt, input1, input2, i-1, j);
           //System.out.print("-" + input1[i]);
 
        } else {
            System.out.print(input1[i]);
 
        }
 
    }

Par exemple voici la sortie voulue pour cette entrée

Entrée
ABCDE
ACDC

Sortie Désirée
ABCDE-
A-CD-C

Sortie actuelle
A-C-D-C

Le problème est que je ne sais pas comment faire en sorte que l'algo ajoute +1 lorsqu'un tiret est ajouté pour que la chaine soit alignée. Clairement dans mon code, il ne considère pas le tiret donc la boucle continue de voir des différences dans mes chaines.

Je veux pricipalement utiliser cette facon de faire, car je vais devoir refaire le même programme en assembleur et je suis très limité dans les fonctions et espace memoire.

Merci !

22/02/2013, 10h00
wax78

Pourquoi as tu commentés ces 2 lignes en fait :

Code:

//System.out.print("-" + input1[i]);

?

En fait l'affichage (print) sauf si je me trompe n'est pas la même dans la première version du code et dans la 2 ème c'est cela qui m'intrigue.

En fait voici le code complet, j'avais mis des lignes en commentaires pour voir la sortie... L'aglo donne la différence de charactères avec des + et -, ce qui n'est pas vraiment ce que je veux faire, mais cela fait en partie. Donc je me demandais comment modifier l'algo pour faire plus un alignement de séquence un peut comme on aligne un code génétique !

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
public class PrintDiff {
 
    char[]  input1  = "ABCDE".toCharArray();
    char[]  input2  = "ACDC".toCharArray();
    int     M       = input1.length;
    int     N       = input2.length;
 
    public void run() {
        int[][] opt = lcsLength(input1, input2);
        printDiff(opt, input1, input2, M - 1, N - 1);
    }
 
    public int[][] lcsLength(char[] input1, char[] input2) {
        int[][] opt = new int[M][N];
        for (int i = 1; i < input1.length; i++) {
            for (int j = 1; j < input2.length; j++) {
                if (input1[i] == input2[j]) {
                    opt[i][j] = opt[i - 1][j - 1] + 1;
                } else {
                    opt[i][j] = Math.max(opt[i][j - 1], opt[i - 1][j]);
                }
            }
        }
        return opt;
    }
 
    public void printDiff(int opt[][], char input1[], char input2[], int i,
            int j) {
        if ((i >= 0) && (j >= 0) && (input1[i] == input2[j])) {
            printDiff(opt, input1, input2, i - 1, j - 1);
            System.out.print("  " + input1[i]);
        } else if ((j > 0) && ((i == 0) || (opt[i][j - 1] >= opt[i - 1][j]))) {
            printDiff(opt, input1, input2, i, j - 1);
            System.out.print(" +" + input2[j]);
        } else if ((i > 0) && ((j == 0) || (opt[i][j - 1] < opt[i - 1][j]))) {
            printDiff(opt, input1, input2, i - 1, j);
            System.out.print(" -" + input1[i]);
        } else {
            System.out.print("");
        }
    }
 
    public static void main(String[] args) {
        new PrintDiff().run();
    }
 
}

22/02/2013, 23h15
metraon

En gros ce que je veux faire c'est ceci avec le diff, sans passer par un Algorythme de 200 lignes comme celui de Needleman–Wunsch.

Input
Array 1 : MKNLASREVN
Array 2 : QMASREVNIY

Output
Array 1 (or a simple print) : -MKNLASREVN
Array 2 (or a simple print) : QM---ASREVN
27/02/2013, 06h03
Sharcoux

Suite du topic :
http://www.developpez.net/forums/d13...chage-fontion/