Transformée Burrows Wheeler - Historique des versions

Sleonard le 17 mai 2020 à 21:42

2020-05-17T21:42:10Z

← Version précédente		Version du 17 mai 2020 à 21:42
Ligne 7 :		Ligne 7 :

	Vous pouvez essayer cette transformée [http://sb.bde-maite.fr/leonards ici] !		Vous pouvez essayer cette transformée [http://sb.bde-maite.fr/leonards ici] !
	Mon code est disponible sur [https://github.com/Matows/VISI201/BTW.PY github].		Mon code est disponible sur [https://github.com/Matows/VISI201/blob/master/BTW.py github].

	== Utilisation ==		== Utilisation ==

Sleonard le 17 mai 2020 à 21:41

2020-05-17T21:41:10Z

← Version précédente		Version du 17 mai 2020 à 21:41
Ligne 7 :		Ligne 7 :

	Vous pouvez essayer cette transformée [http://sb.bde-maite.fr/leonards ici] !		Vous pouvez essayer cette transformée [http://sb.bde-maite.fr/leonards ici] !
			Mon code est disponible sur [https://github.com/Matows/VISI201/BTW.PY github].

	== Utilisation ==		== Utilisation ==

El-huissier le 17 mai 2020 à 14:15

2020-05-17T14:15:27Z

← Version précédente		Version du 17 mai 2020 à 14:15
Ligne 6 :		Ligne 6 :
	</blockquote>		</blockquote>

	Vous pouvez essayer cette ~~trasnformée~~ [http://sb.bde-maite.fr/leonards ici] !		Vous pouvez essayer cette transformée [http://sb.bde-maite.fr/leonards ici] !

	== Utilisation ==		== Utilisation ==
	Cette transformée est utilisée pour faire apparaître des motifs redondants dans une séquence de lettres ou d'octets, ce qui aide à la compression avec [https://fr.wikipedia.org/wiki/Codage_de_Huffman l'encoding d'Huffman].		Cette transformée est utilisée pour faire apparaître des motifs redondants dans une séquence de lettres ou d'octets, ce qui aide à la compression avec [https://fr.wikipedia.org/wiki/Codage_de_Huffman l'encoding d'Huffman].

	Elle est aussi utilisée dans le domaine de la génétique, pour chercher une sous-~~chaine~~ (une séquence) dans un génome humain de plusieurs gigaoctets.		Elle est aussi utilisée dans le domaine de la génétique, pour chercher une sous-chaîne (une séquence) dans un génome humain de plusieurs gigaoctets.

	== Principe de fonctionnement ==		== Principe de fonctionnement ==
Ligne 36 :		Ligne 36 :
	A A B R A C A D A B R		A A B R A C A D A B R

	2. On trie les lignes suivant un ordre choisi, qu'il ~~fraudra~~ respecter pour l'inverse de la transformée. Ici, je choisis l'ordre alphabétique		2. On trie les lignes suivant un ordre choisi, qu'il faudra respecter pour l'inverse de la transformée. Ici, je choisis l'ordre alphabétique

	A A B R A C A D A B R		A A B R A C A D A B R
Ligne 64 :		Ligne 64 :
	R A C A D A B R A A B		R A C A D A B R A A B

	4. Pour finir cette transformée, nous devons avoir l'indice du mot initial et la dernière ~~colone~~ de la matrice :		4. Pour finir cette transformée, nous devons avoir l'indice du mot initial et la dernière colonne de la matrice :

	A A B R A C A D A B '''R'''		A A B R A C A D A B '''R'''
Ligne 78 :		Ligne 78 :
	R A C A D A B R A A '''B'''		R A C A D A B R A A '''B'''

	Le résultat est donc ''3RDARCAAAABB''. On voit que dans cet exemple, quatre ''A'' se suivent ainsi que deux ''B''. Il est facile d'imaginer que sur des séquences beaucoup plus grande, il y aura ~~suffisament~~ de motifs redondants pour que la compression soit bonne.		Le résultat est donc ''3RDARCAAAABB''. On voit que dans cet exemple, quatre ''A'' se suivent ainsi que deux ''B''. Il est facile d'imaginer que sur des séquences beaucoup plus grande, il y aura suffisamment de motifs redondants pour que la compression soit bonne.

	=== L'inverse de la transformée ===		=== L'inverse de la transformée ===
Ligne 84 :		Ligne 84 :
	# On insert la séquence en première colonne		# On insert la séquence en première colonne
	# On tri les lignes par ordre alphabétique		# On tri les lignes par ordre alphabétique
	Une fois que nous ~~avont~~ la matrice carré reconstruite, on prend la ligne correspondant à l'indice.		Une fois que nous avons la matrice carré reconstruite, on prend la ligne correspondant à l'indice.

	Partons de ''3BNENAA''. L'indice est de 3 et la séquence est ''BNENAA''.		Partons de ''3BNENAA''. L'indice est de 3 et la séquence est ''BNENAA''.
Ligne 192 :		Ligne 192 :

	== Algorithmes ==		== Algorithmes ==
	À partir du [https://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.pdf document de référence], on peut établir plusieurs versions d'implémentations de la transformée de Burrows-Wheeler. Une première "naïve", en appliquant la transformée sans se poser de question. La seconde en se basant sur la partie 4 ''An efficient ~~implementation~~'' de l'article officiel.		À partir du [https://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.pdf document de référence], on peut établir plusieurs versions d'implémentations de la transformée de Burrows-Wheeler. Une première "naïve", en appliquant la transformée sans se poser de question. La seconde en se basant sur la partie 4 ''An efficient implémentation'' de l'article officiel.
	=== Implémentation naïve ===		=== Implémentation naïve ===
	==== Algorithmes Python ====		==== Algorithmes Python ====
Ligne 237 :		Ligne 237 :

	==== Limitations ====		==== Limitations ====
	Le problème de cet algorithme, c'est qu'à chaque fois nous construisons une matrice de taille <math>N\times N</math>, avec <math>N=</math> taille des données passées à la transformée (e.g. : ABRACADABRA -> Matrice 11,11). Cela n'est pas un problème pour des mots, mais pour des fichiers de plusieurs gigaoctets cela prendrait trop de place mémoire en plus d'être ~~complètemement~~ inefficace, dû au grand nombre d'itérations sur la matrice.		Le problème de cet algorithme, c'est qu'à chaque fois nous construisons une matrice de taille <math>N\times N</math>, avec <math>N=</math> taille des données passées à la transformée (e.g. : ABRACADABRA -> Matrice 11,11). Cela n'est pas un problème pour des mots, mais pour des fichiers de plusieurs gigaoctets cela prendrait trop de place mémoire en plus d'être complètement inefficace, dû au grand nombre d'itérations sur la matrice.

	=== Implémentation avancée ===		=== Implémentation avancée ===
Ligne 243 :		Ligne 243 :
	Chaque "ligne" de la matrice ne peut en faite contenir que deux informations : une référence à la chaîne de caractère et l'indice de position de la première lettre de la rotation.		Chaque "ligne" de la matrice ne peut en faite contenir que deux informations : une référence à la chaîne de caractère et l'indice de position de la première lettre de la rotation.

	Puisque nous voulons trier ces lignes, nous devons pouvoir les comparer (inférieur, ~~suppérieur~~, égale...).		Puisque nous voulons trier ces lignes, nous devons pouvoir les comparer (inférieur, supérieur, égale...).

	On peut donc créer une classe ''Rotation'' qui réponde à ces critères :		On peut donc créer une classe ''Rotation'' qui réponde à ces critères :

Sleonard le 16 mai 2020 à 14:47

2020-05-16T14:47:54Z

← Version précédente		Version du 16 mai 2020 à 14:47
Ligne 5 :		Ligne 5 :
	<p>- Julian Seward</p>		<p>- Julian Seward</p>
	</blockquote>		</blockquote>

			Vous pouvez essayer cette trasnformée [http://sb.bde-maite.fr/leonards ici] !

	== Utilisation ==		== Utilisation ==

Sleonard : /* L'inverse de la transformée */

2020-05-16T14:21:02Z

L'inverse de la transformée

← Version précédente		Version du 16 mai 2020 à 14:21
Ligne 187 :		Ligne 187 :
	\|}		\|}

	Le mot d'origine est donc ''BANANE''		Le mot d'origine est donc ''BANANE''.

	== Algorithmes ==		== Algorithmes ==

Sleonard : /* L'inverse de la transformée */

2020-05-16T14:20:48Z

L'inverse de la transformée

← Version précédente		Version du 16 mai 2020 à 14:20
Ligne 186 :		Ligne 186 :
	NEBANA 6		NEBANA 6
	\|}		\|}

			Le mot d'origine est donc ''BANANE''

	== Algorithmes ==		== Algorithmes ==

Sleonard : /* L'inverse de la transformée */

2020-05-16T14:18:04Z

L'inverse de la transformée

← Version précédente		Version du 16 mai 2020 à 14:18
Ligne 181 :		Ligne 181 :
	ANANEB 1		ANANEB 1
	ANEBAN 2		ANEBAN 2
	BANANE ↤3		'''BANANE 3'''
	EBANAN 4		EBANAN 4
	NANEBA 5		NANEBA 5

Sleonard : /* L'inverse de la transformée */

2020-05-16T14:17:13Z

L'inverse de la transformée

← Version précédente		Version du 16 mai 2020 à 14:17
Ligne 84 :		Ligne 84 :
	Une fois que nous avont la matrice carré reconstruite, on prend la ligne correspondant à l'indice.		Une fois que nous avont la matrice carré reconstruite, on prend la ligne correspondant à l'indice.

	Partons de ''~~2BNENAA~~''. L'indice est de 2 et la séquence est ''BNENAA''.		Partons de ''3BNENAA''. L'indice est de 3 et la séquence est ''BNENAA''.

	{\| class="wikitable"		{\| class="wikitable"
Ligne 179 :		Ligne 179 :
	ANEBAN		ANEBAN
	\|		\|
	ANANEB		ANANEB 1
	ANEBAN		ANEBAN 2
	BANANE		BANANE ↤3
	EBANAN		EBANAN 4
	NANEBA		NANEBA 5
	NEBANA		NEBANA 6
	\|}		\|}

Sleonard : /* L'inverse de la transformée */

2020-05-16T14:13:44Z

L'inverse de la transformée

← Version précédente		Version du 16 mai 2020 à 14:13
Ligne 84 :		Ligne 84 :
	Une fois que nous avont la matrice carré reconstruite, on prend la ligne correspondant à l'indice.		Une fois que nous avont la matrice carré reconstruite, on prend la ligne correspondant à l'indice.

	Partons de ''2BNENAA''. L'indice est de 2 et la séquence est ''~~BNEAA~~''.		Partons de ''2BNENAA''. L'indice est de 2 et la séquence est ''BNENAA''.

	{\| class="wikitable"		{\| class="wikitable"

Sleonard : /* L'inverse de la transformée */

2020-05-16T14:13:16Z

L'inverse de la transformée

@@ Ligne 88 : / Ligne 88 : @@
 {| class="wikitable"
 |-
 | Insertion
 | Tri
@@ Ligne 137 : / Ligne 143 : @@
  NAN
  NEB
 |}

Transformée Burrows Wheeler - Historique des versions

Sleonard le 17 mai 2020 à 21:42

Sleonard le 17 mai 2020 à 21:41

El-huissier le 17 mai 2020 à 14:15

Sleonard le 16 mai 2020 à 14:47

Sleonard : /* L'inverse de la transformée */

Sleonard : /* L'inverse de la transformée */

Sleonard : /* L'inverse de la transformée */

Sleonard : /* L'inverse de la transformée */

Sleonard : /* L'inverse de la transformée */

Sleonard : /* L'inverse de la transformée */

Sleonard : /* L'inverse de la transformée */

Sleonard : /* L'inverse de la transformée */

Sleonard : /* L'inverse de la transformée */

Sleonard : /* L'inverse de la transformée */

Sleonard : /* L'inverse de la transformée */

Sleonard : /* L'inverse de la transformée */