Discussion :

[-Syn.-]

Bonjour,

Je souhaite appliquer la méthode de Burrows Wheeler à un fichier texte ; il faut donc préalablement rentrer ce fichier dans une matrice, ce que j'ai réussi. Cependant, me voilà arrivé à une étape où je ne sais pas comment m'y prendre : il faudrait que je range par ordre alphabétique les diverses lignes de la matrice.
Pourriez-vous m'orienter pour que je réussisse à faire ce tri s'il vous plaît ? Après diverses recherches, celles-ci ont été peu fructueuses.

Exemple : Le fichier texte contient les caractères "TEXTUEL" ; après être entré dans ma matrice et commencé la méthode de B.W, j'obtiens :

T E X T U E L
L T E X T U E
E L T E X T U
U E L T E X T
T U E L T E X
X T U E L T E
E X T U E L T

Je souhaiterais, après tri, obtenir ceci :

E L T E X T U
E X T U E L T
L T E X T U E
T E X T U E L
T U E L T E X
U E L T E X T
X T U E L T E

Merci d'avance de votre aide.

[Roland Chastain]

Bonjour !

La première chose à savoir, c'est qu'on peut comparer des caractères et même des chaînes au moyen des comparateurs < et >.
Ce qui est alors comparé, c'est le rang des caractères dans la table ASCII, ce qui correspond à l'ordre alphabétique, sauf que majuscules et minuscules n'ont pas le même rang.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
program Comparer;
 
{$APPTYPE CONSOLE}
 
begin
  WriteLn('A'<'B');     // TRUE
  WriteLn('ABB'<'ABC'); // TRUE
 
  WriteLn('a'<'B');     // FALSE
 
  WriteLn(Ord('a'));    // 97
  WriteLn(Ord('B'));    // 66
  ReadLn;
end.

Le plus simple serait peut-être de comparer des chaînes ; mais on peut aussi comparer les lignes d'un tableau caractère par caractère : on commence par la gauche, et dès qu'on a trouvé deux caractères différents, on sait du même coup laquelle des deux lignes est "plus grande" que l'autre.

[-Syn.-]

Bonjour !

Merci de votre réponse,
J'ai cependant un petit problème, en effet je n'arrive à trier la matrice que sur un rang, c'est à dire que s'il trouve "ACB", il réussira à donner "ABC", cependant s'il trouve "CBA", il ne ressortira que "BCA" sans remettre le A à la bonne place.
Pourriez-vous m'aider pour obtenir le bon code s'il vous plait ?
Autre petite chose, je n'arrive pas à formuler le code lorsque deux lettres sont identiques, à s'intéresser à la 2eme, si l'on a la matrice suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
BCC
BAC
BCA

il faudrait obtenir

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
BAC
BCA
BCC

A l'heure actuelle, ma procédure du tri de la matrice est comme suit :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
Procedure matri(var matrice : mat);
 
Begin
 
setlength(temp,nb_car);
i := 0;
for i := 0 to high(temp) do
temp[i] := '0';;
 
i:=0;
j:=0;
 
 for i := 0 to high(matrice)-1 do
 	begin
 	if ord(matrice[i,0]) > ord(matrice[i+1,0]) then // B > A //
 	begin
 
 		writeln('passeparla');
 		for j := 0 to high(matrice) do
 		begin	
		 	temp[j] := matrice[i,j];
		 	writeln('temp[',j,'] : ',temp[j], ' ');	 	
		 	matrice[i,j] := matrice[i+1,j];		
		 	matrice[i+1,j] := temp[j];
		end;
 
	end; 
 
	if ord(matrice[i,0]) = ord(matrice[i+1,0]) then
	writeln('passeparici');
	end;
end;

Merci d'avance de votre aide

[Roland Chastain]

Difficile de corriger un code quand on n'en voit qu'un morceau. Il serait peut-être bon de le poster en entier.

Autrement, je conseillerais de bien distinguer deux problèmes, à savoir 1° la comparaison des lignes et 2° le tri de la matrice.

Je commencerais par m'occuper de la comparaison des lignes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
program tri_matrice_1;
 
{$APPTYPE CONSOLE}
 
type
  tLigne   = array[0..6]of char;
  tMatrice = array[0..6]of tLigne;
 
const
  exLigne1: tLigne = ('a','b','c','d','e','f','g');
  exLigne2: tLigne = ('a','a','a','a','a','a','a');
  exLigne3: tLigne = ('t','e','x','t','u','e','l');
 
function CompareLignes(const aLigne1, aLigne2: tLigne): integer;
var
  i: integer;
begin
  i := 0;
  while (aLigne1[i] = aLigne2[i]) and (i < 6) do
    Inc(i);
  result := Ord(aLigne1[i]) - Ord(aLigne2[i]);
end;
 
begin
  WriteLn(CompareLignes(exLigne1, exLigne2)); //   1 ( Ord('b') - Ord('a') )
  WriteLn(CompareLignes(exLigne2, exLigne3)); // -19 ( Ord('a') - Ord('t') )
  ReadLn;
end.

Une fois que ma fonction de comparaison est au point, je peux passer comme arguments les lignes d'une matrice :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
program tri_matrice_2;
 
{$APPTYPE CONSOLE}
 
type
  tLigne   = array[0..6]of char;
  tMatrice = array[0..6]of tLigne;
 
const
  exLigne1: tLigne = ('a','b','c','d','e','f','g');
 
function CompareLignes(const aLigne1, aLigne2: tLigne): integer;
var
  i: integer;
begin
  i := 0;
  while (aLigne1[i] = aLigne2[i]) and (i < 6) do
    Inc(i);
  result := Ord(aLigne1[i]) - Ord(aLigne2[i]);
end;
 
var
  matrice: tMatrice;
  i: integer;
 
begin
  for i := 0 to 6 do
    matrice[i] := exLigne1;
 
  WriteLn(CompareLignes(matrice[0], matrice[1])); // 0 ( les lignes sont identiques )
  ReadLn;
end.

Ensuite je ferais une procédure qui permute deux lignes d'une matrice :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

procedure Permute(var aMatrice: tMatrice; const indexLigne1, indexLigne2: integer);

Et pour finir, la procédure de tri.

[Roland Chastain]

La discussion paraissant abandonnée, je me permets de poster ma solution.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
program Exercice;
 
{$APPTYPE CONSOLE}
 
{ Trier par ordre alphabétique les lignes d'un tableau de caractères.
 
  Compilation FreePascal 2.6.2. }
 
type
  tLigne = array[0..6]of char;
  tTable = array[0..6]of tLigne;
 
const
  cTable: tTable = (
    ('T','E','X','T','U','E','L'),
    ('L','T','E','X','T','U','E'),
    ('E','L','T','E','X','T','U'),
    ('U','E','L','T','E','X','T'),
    ('T','U','E','L','T','E','X'),
    ('X','T','U','E','L','T','E'),
    ('E','X','T','U','E','L','T')
  );
 
function Compare(const aLigne1, aLigne2: tLigne): integer;
var
  i: integer;
begin
  i := 0;
  while (aLigne1[i] = aLigne2[i]) and (i < 6) do
    Inc(i);
  result := Ord(aLigne1[i]) - Ord(aLigne2[i]);
end;
 
procedure Permute(var aTable: tTable; const aIndex1, aIndex2: integer);
var
  ligne: tLigne;
begin
  ligne := aTable[aIndex2];
  aTable[aIndex2] := aTable[aIndex1];
  aTable[aIndex1] := ligne;
end;
 
procedure Trie(var aTable: tTable);
var
  ordre: boolean;
  i: integer;
begin
  repeat
    ordre := TRUE;
    for i:= 0 to 5 do
      if Compare(aTable[i], aTable[i+1]) > 0 then
      begin
        ordre := FALSE;
        Permute(aTable, i, i+1);
      end;
  until ordre;
end;
 
var
  table: tTable;
 
begin
  table := cTable;
 
  WriteLn(Compare(table[0], table[1]):2); //   8
  WriteLn(Compare(table[1], table[2]):2); //   7
  WriteLn(Compare(table[2], table[3]):2); // -16
  WriteLn(Compare(table[3], table[4]):2); //   1
  WriteLn(Compare(table[4], table[5]):2); //  -4
  WriteLn(Compare(table[5], table[6]):2); //  19
 
  Trie(table); WriteLn;
 
  WriteLn(Compare(table[0], table[1]):2); // -12
  WriteLn(Compare(table[1], table[2]):2); //  -7
  WriteLn(Compare(table[2], table[3]):2); //  -8 
  WriteLn(Compare(table[3], table[4]):2); // -16
  WriteLn(Compare(table[4], table[5]):2); //  -1
  WriteLn(Compare(table[5], table[6]):2); //  -3
 
  ReadLn;
end.

Une variante utilisant la fonction StrComp de l'unité SysUtils :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
function Compare(const aLigne1, aLigne2: tLigne): integer;
begin
  result := StrComp(pChar(@aLigne1), pChar(@aLigne2));
end;

En remplaçant StrComp par StrIComp, on obtient une fonction qui ne tient pas compte de la différence entre minuscules et majuscules.