Liens utiles
-
la liste des "Advent of Code"
Antisèches Go
Les bases
- opérations et comparaisons [AFFICHER]
-
opérations +,-,*,/pour les entiers et flottants,%(modulo) pour les entiers... ||(ou),&&(et),!(négation) pour les booléens... >>,<<(décalage),|,&(ou/et bit à bit),^(négation bit à bit et XOR bit à bit)... +(concaténation pour les chaines)comparaisons ==,!=,>,<,<=,>=pour les entiers, flottants ou chaines - types [AFFICHER]
-
types int8,int16,int32etint64entiers 8, 16, 32 ou 64 bits... variantes uint8, ...,uint64pour les entiers non signés ;byteest un synonyme deuint8... intetuintpour les entiers "machine" (32 ou 64 bits suivants l'architecture)... float32etfloat64pour les flottants 32 ou 64 bits... stringpour les chaines (non mutable, comme en Python)... []intpour les tableaux d'entiers,[][]float64pour les tableaux à 2 dimensions de flottants, etc.... map[string] intpour les dictionnaires avec chaines comme clés et des entiers comme valeurs, etc. - tableaux et dictionnaires [AFFICHER]
-
tableaux len(T)(taille),T[0]pour l'accès à une case... Attention T[i]provoque une erreur sii<0oui>=len(T)... T = append(T, 1)ouT = append(T, 1,2,3)pour ajouter des éléments à la fin d'un tableaudictionnaires D[k]renvoie la valeur associée à la clék, ou la valeur "zéro" si la clé n'est pas présente... v, ok = D[k]met la valeur deD[k]dansv, et un booléen dansok: vrai sikétait présente, faux sinoninitialisation (tableau) T := make([]int)déclare un tableau vide d'entiers... T := make([]int, 10)déclare un tableau d'entiers de taille 10, où toutes les cases ont la valeur "zéro"... T := []int{1,2,3}déclare un tableau d'entiers de taille 3, avec les éléments1,2et3initialisation (dictionnaire) D := make(map[string]int)déclare un dictionnaire vide... D := map[string]int{"un": 1, "deux": 2}déclare un dictionnaire - variables [AFFICHER]
-
variables (déclaration) var n int: déclaration sans initialisation (valeur par défaut: "zéro")... var n int = 10: déclaration avec initialisation... n := 10: déclaration simple, le type est inféré... Attention : x := 10ouvar x intpeuvent redéfinir une nouvelle variable dans un sous blocaffectation n = 10: affectation pour une variable existante... +=,-=, etc. permettent de faire une mise à joursx += 3est équivalent àx = x+3, etc.... i++eti--sont équivalents ài = i+1eti = i-1affectation multiple a,b,c = 1,2,3affectation de plusieurs variablesdéclaration multiple a,b,c := 1,2,3déclaration de plusieurs variables... Attention, dans a,b,c := 1,2,3seules les variables que l'on peut (re)déclarer sont déclarées; pour les autres, cela fait une affectation - fonctions [AFFICHER]
-
fonction func f(x float64, n int) {première ligne d'une définition de fonction à 2 arguments, sans valeur de retour... func f(n int) string {première ligne d'une définition de fonction à 1 argument, qui renvoie une chaine... func f(n int) (string, bool) {première ligne d'une définition de fonction à 1 argument, qui renvoie 2 valeurs... Attention, si frenvoie 2 valeurs, il faut utiliser 2 variables pour enregistrer le résultat :s, b := f(12).... On peut ignorer un des résultats avec _:s, _ := f(12) - boucles et conditionnelles [AFFICHER]
-
conditionnelles if <CONDITION> {...} else {...}... if <INIT>; <CONDITION> {...} else {...}permet de définir des variables (avec:=) uniquement pour la conditionnelleboucles for <INIT>; <CONDITION>; <MAJ> {...}... for <CONDITION> {...}(c'est la boucle while !)... for {...}pour une boucle infinie... continueetbreakfonctionnent comme d'habitude
Niveau 2
- compléments sur les dictionnaires / tableaux [AFFICHER]
-
sous tableaux T[debut:fin]est un tableau qui contient les valeurs deTdepuis les indices dedebut(inclu) àfin(exclu)... attention, contrairement à Python, les valeurs ne sont pas copiées, TetT[debut:fin]utilisent la même zone mémoireboucles for i := range T {...}permet de faire une boucle sur les indices du tableauxT... for i, v := range T {...}permet de faire une boucle sur les indices / valeurs du tableauT... for k := range D {...}permet de faire une boucle sur les clés du dictionnaireD... for k, v := range D {...}permet de faire une boucle sur les clés / valeurs du dictionnaireD - point virgules [AFFICHER]
-
En général, un retour chariot termine une instruction. Plus précisément :
-
le séparateur d'instruction
;est inséré à la fin d'une ligne si-
le token précédent est un identifiant,
-
le token précédent est un nombre ou une chaine (ou une "rune", càd un littéral unicode),
-
le token précédent est un des mots clé
break,continueoureturn(oufallthrough), -
le token précédent est
++,--,),},].
-
-
Un séparateur d'instruction
;peut être omis avant)ou}.
-
- structures et définitions de types [AFFICHER]
-
structures ex : struct {x int; y int; c string}type des structures à 3 champs, etc.... ex : s := struct{x int; y int; c string}{1,2,"rien"}pour définir une variable du type précédent... on accède aux champs avec s.x,s.yets.cdéfinition de type type <NOM> <TYPE>... type pointAnnot struct {x int; y int; c string}pour définir un type de structures... p := pointAnnot{1,2,"rien"}pour définir une variable dans le type correspondant... attention, il ne faut (en général) pas mettre de =entre<NOM>et<TYPE>méthodes func (p pointAnnot) m(<ARGUMENTS>) <RETOUR> {...}... le receiver est donné avant le nom de la fonction ... on peut définir des méthodes sur n'importe quel type qu'on a définit ... remarque : il n'y a pas d'héritage comme en POO - switch [AFFICHER]
-
switch <EXPR> {...}: les cas sont traités dans l'ordre et seul le premier cas égal à<EXPR>est utilisé (sauf si on utilise le mot cléfallthrough).Par exemple :
switch n { case 0: fmt.Println("zéro") case 1,2,3: fmt.Println("petit") case 4: fmt.Println("gros") case 5,6,7: fmt.Println("énorme") default: fmt.Println("???") }Comme pour
if, on peut ajouter une initialisation :switch <INIT>; <EXPR> {...}Attention, les instructions
breaketcontinueagissent sur lesswitch, on ne peut donc pas les utiliser directement pour sortir d'une boucle depuis l'intérieur d'unswitch.
Séance 1 (06-01-2025)
-
Vérifiez que go fonctionne correctement sur votre machine, par exemple en lançant la commande
$ go version -
Installez le plugin Go dans vscode, (ou un autre plugin dans un autre IDE).
-
Testez un programme de type bonne année (version saisonnière de hello world).
-
Connectez vous sur Advent of Code, par exemple avec votre compte Github.
-
Pour initialiser un nouveau module ("projet"), il faut lancer la commande
$ go mod init <NOM_DU_MODULE>dans le répertoire du module.
-
Votre fichier doit commencer par la ligne
package mainet un des fichiers du projets doit contenir une fonction
mainsans argument ni valeur de retour. -
Le mot clé pour définir une fonction est
func, et la fonction Go pour faire un affichage simple estfmt.Println. (Attention à ne pas oublier la majuscule !) Elle fonctionne comme la fonctionprintde Python. Vous pouvez aussi utiliserfmt.Printfpour avoir une fonction similaire àprintfdu langage C. Pour utiliserfmt.Println, il faut ajouterimport "fmt"en haut du du fichier. Normalement, vscode s'en chargera tout seul ! -
Si votre plugin Go est bien installé, votre code sera automatiquement formaté à chaque sauvegarde !
-
Pour lancer votre programme, il faut utiliser la commande
$ go run .ou le lancer à partir de vscode.
Écrivez un programme pour résoudre les problèmes suivants (parties 1 et 2).
| année | jours | lien |
|---|---|---|
| 2022 | 1 | Calorie Counting |
| 2020 | 2 | Password Philosophy |
| 2021 | 2 | Dive! |
Notez bien que pour obtenir vos fichier de données personnalisés, vous devez être connecté sur le site Advent of Code.
Un problème est résolu lorsque vous avez pu valider votre réponse sur le site et que vous avez obtenu les 2 étoiles "**" correspondantes. (Ou une seule étoile "*" pour les 25 décembre.)
Note : Eric Wastl, le créateur de Advent of Code, demande explicitement que les fichiers de données ne soient pas partagés sur Internet. Ne les mettez donc pas dans un dépot Git public.
Pour gagner du temps
- lecture des lignes d'un fichier
-
f, _ = os.Open(filename) sc = bufio.NewScanner(f) for sc.Scan() { line := sc.Text() ... } - conversion depuis une chaine
-
Les fonctions du module
strconvpermettent de convertir des chaines en entiers, flottants, etc. Parcourez la documentation des fonctionsstrconv.Atoi,strconv.ItoA,strconv.ParseBool,strconv.ParseFloat,strconv.ParseInt,strconv.ParseUinten cas de besoin.Attention, ces fonctions renvoient deux valeurs : le résultat et un code d'erreur. Pour ignorer ce dernier, il faut donc écrire :
var n int n, _ = strconv.Atoi(<CHAINE>) - documentation
-
Vous pouvez obtenir la documentation de la bibliothèque standard avec
$ go doc bufio $ go doc strconv.parsebool - extraction de valeurs d'une chaine formatée, à la scanf
-
var i, j int var color string fmt.Sscanf(s, "(%d,%d): %s", &i, &j, &color)Si
sest la chaine"(12,-123): rouge clair", les variablesietjauront les valeurs12et-123, et la variablecoloraura la valeur"rouge". - tri
-
La fonction
slices.Sortpermet de trier un tableau dans l'ordre croissant.
Travail à la maison
-
Commencez le tutoriel officiel
-
Parcourez les conseils de style officiels Go style guide et Go Style Decisions (notamment la partie sur les noms de variables).
-
Écrivez un programme qui utilise un dictionnaire et un programme qui utilise une structure (cf tutoriel), et réfléchissez aux différences entre ces 2 types de données.
-
Finissez les problèmes Advent of Code commencés :
2022 1 Calorie Counting 2020 2 Password Philosophy 2021 2 Dive!
Séance 2 (14-01-2025)
Écrivez des fonctions pour résoudre les problèmes suivants (parties 1 et 2).
| année | jours | lien |
|---|---|---|
| 2020 | 1 | Report Repair |
| 2016 | 1 | No Time for a Taxicab |
| 2015 | 4 | The Ideal Stocking Stuffer |
Pour chaque problème, définissez une fonction de type func (filename
string) int qui renverra la solution trouvée. Vous n'aurez qu'à
l'appeler dans votre fonction main avec le bon nom de fichier en
argument.
Pour gagner du temps
- lecture entière d'un fichier dans un tableau de
bytes -
T, _ = os.ReadFile(filename)Attention, en cas d'erreur (fichier inexistant, etc.),
Tsera vide. Pour gérer ça, il faut regarder la deuxième valeur de retour. Par exemple, le code suivant provoque une "panique" en cas d'erreur.T, err = os.ReadFile(filename) if err != nil { panic(err) } - les modules
stringsetbytes -
contiennent de nombreuses fonctions sur les chaines / tableaux d'octets :
Trim,Split,Join,HasPrefix, ...Utilisez les commandes go doc strings et go doc bytes pour avoir la liste de ces fonctions.
- l'empreinte MD5 d'un tableau
Td'octets (type[]byte) -
peut se calculer de la manière suivante
import "crypto/md5" ... E := md5.Sum(T)Econtiendra alors un tableau statique avec exactement 16 octets (type[16]byte).Attention, lors de la résolution du problème 2015-04, les "0" que vous devez chercher dans l'empreinte MD5 sont des "0" dans la représentation hexadécimale de l'empreinte. Chaque octet de l'empreinte donne deux chiffres hexadécimaux. Pour trouver cinq "0", il faut donc regarder deux octets et demi (20 bits) !
Travail à la maison
-
Finissez le tutoriel officiel, si ce n'est pas déjà fait.
-
Décrivez une manière de coder un type de tableaux dynamiques d'entiers en C pur, en utilisant
mallocetrealloc. Il s'agit d'un type avec les opérations suivantes :-
len(T): renvoie le nombre d'éléments du tableau, -
get(T, i): renvoie la case numéroi(indéterminé siine correspond pas à une case valide), -
set(T, i, v): mets la valeurv(un entier) dans la case numéroi(indéterminé siine correspond pas à une case valide), -
append(T, v): ajoute une valeurvà la fin du tableau. (La taille du tableau doit donc augmenter de 1.)
Réfléchissez également à la complexité de ces opérations.
-
-
Écrivez une méthode
showpour le typetype grid map[[2]int] byte: le dictionnaire contient des caractères ASCII (typebyte) à des coordonnées entières (type[2]int).La méthode
showdevra afficher les caractères à leur coordonnées, mais uniquement pour la boite englobante des coordonnées présentes dans le dictionnaire. Par exemple, pourG := grid(map[[2]int]byte{ {10, -7}: 'h', {11, -7}: 'e', {12, -7}: 'l', {13, -7}: 'l', {14, -7}: 'o', {14, -6}: 'w', {15, -6}: 'o', {16, -6}: 'r', {17, -6}: 'l', {18, -6}: 'd', }) G.show()on obtiendra
$ go run . hello worldVérifiez que votre code fonctionne en mettant le fichier mystere.go dans votre répertoire et en appelant
G := mystere() G.show() -
Finissez les problèmes Advent of Code commencés :
année jours lien 2020 1 Report Repair 2016 1 No Time for a Taxicab 2015 4 The Ideal Stocking Stuffer
Séance 3 (20-01-2025)
Écrivez des fonctions pour résoudre les problèmes suivants (parties 1 et 2).
| année | jours | lien |
|---|---|---|
| 2023 | 6 | Wait For It |
| 2021 | 13 | Transparent Origami |
Pour chaque problème, définissez une fonction de type func (filename
string) int (ou func (filename string) string) qui
renverra la solution trouvée. Vous n'aurez qu'à l'appeler dans votre fonction
main avec le bon nom de fichier en argument.
Pour gagner du temps
- découper une chaine
-
La fonction
strings.Splitpermet de découper une chaine à partir d'un séparateur.Lorsque le séparateur n'est pas fixe (par exemple une suite d'espaces dans le problème Wait For It), on peut parfois utiliser une expression régulière :
func main() { r := regexp.MustCompile(`[a-z]+`) fmt.Printf("résultat => %#v\n", r.Split("AbCDefGHIjklMnoQRSTuvWXYZ", -1)) }affichera
$ go run . résultat => []string{"A", "CD", "GHI", "M", "QRST", "WXYZ"}Remarque : l'utilisation des guillemets "
`" n'est pas réservé aux expressions régulières. Ils sont utilisés pour les chaines "brutes" sans interprétations des séquences d'échappement. Ils permettent, dans le cas des expressions régulières, l'utilisation de "\s" (caractères blancs), "\d" (chiffres), etc. sans que Go n'essaie de les interpréter (comme les "\n" par exemple). (Syntaxe des expressions régulières, ou go doc regexp/syntax)
Travail à la maison
-
Le problème Calorie Counting nécessitait de calculer les 3 valeurs maximales parmi une liste de nombres calculés.
-
Pour trouver les 3 valeurs maximales de
fsur les entiers0, ..., 999, je vous avais montréT := []int{0,0,0} // les 3 valeurs maximales for i:=3; i<1000; i++ { // on ajoute la nouvelle valeur T = append(T, f(i)) // et on enlève la plus petite slices.Sort(T) T = T[1:4] } -
Expliquez pourquoi mon code initial ressemblait en fait à
T := []int{0,0,0} // les 3 valeurs maximales for i:=3; i<1000; i++ { // on ajoute la nouvelle valeur T = append(T, f(i)) // et on enlève la plus petite slices.Sort(T) T[0] = T[3] T = T[0:3] } -
Complétez le code suivant pour faire la même chose sans utiliser ni
slices.Sort, niappendn1, n2, n3 := 0, 0, 0 // les 3 valeurs maximales for i:=3; i<1000; i++ { // nouvelle valeur n4 := f(i) // on ne garde que les plus grandes ... } -
Pouvez vous mettre une différence de temps d'exécution en évidence ?
-
-
Comparez le temps d'exécution des 3 manières suivantes d'initialiser un tableau (dynamique) de taille
1000-
naïf :
T := make([]int, 0) for i := 0; i<1000; i++ { T = append(T, i) } -
en allouant directement un tableau de taille
1000T := make([]int, 1000) for i := 0; i<1000; i++ { T[i] = i } -
en allouant un tableau de taille
0et de capacité1000T := make([]int, 0, 1000) for i := 0; i<1000; i++ { T = append(T, i) }
-
-
Finissez les problèmes Advent of Code commencés :
année jours lien 2023 6 Wait For It 2021 13 Transparent Origami
Séance 4 (27-01-2025)
Écrivez des fonctions pour résoudre les problèmes suivants (parties 1 et 2).
| année | jours | lien |
|---|---|---|
| 2021 | 6 | Lanternfish |
| 2022 | 14 | Regolith Reservoir |
Pour chaque problème, définissez une fonction de type func (filename
string) int qui renverra la solution trouvée. Vous n'aurez qu'à
l'appeler dans votre fonction main avec le bon nom de fichier en
argument.
Pour gagner du temps
- lire les entiers dans un fichier
-
Mon fichier utils.go contient, entre autre, les fonctions
// ReadFile is a simple wrapper around os.ReadFile that panics in case of // error. func ReadFile(filename string) string { B, err := os.ReadFile(filename) if err != nil { panic(err) } return string(bytes.TrimSpace(B)) } // Atoi is a simple wrapper around strconv.Atoi that panics in case of error. func Atoi(s string) int { n, err := strconv.Atoi(s) if err != nil { panic(err) } return n } // ParseInts returns a list of integers read from the argument string `s`. // The argument `sep` is a regular expression used to match the separators. // No error checking or reporting is done and the function panics if one part // of the input string cannot be converted to an integer. func ParseInts(s, sep string) []int { var result []int sepRegex := regexp.MustCompile(sep) for _, n := range sepRegex.Split(strings.TrimSpace(s), -1) { result = append(result, Atoi(n)) } return result }Si vous les ajoutez dans votre module, vous pourrez récupérer la liste des entiers pour le premier problème avec
L := ParseInts(ReadFile(filename), ",")
Travail à la maison
-
Finissez les problèmes commencés en séance (parties 1 et 2) et le deuxième de la séance précédente.
année jours lien 2021 6 Lanternfish 2022 14 Regolith Reservoir 2021 13 Transparent Origami -
Cherchez une solution efficace pour le problème Wait For It).
Pour tester, généralisez le problème de la manière suivante : au lieu de 2 lignes, le fichier contient plusieurs courses, chacune décrite sur 2 lignes. Vous devez faire la somme des nombres de manières de battre le record actuel pour chaque course.
Comme dans le problème original, pour la partie 2, concaténez les valeurs pour chaque paire de lignes.
Par exemple, le fichier test06_small contient les 3 courses suivantes
Time: 90 92 96 79 Distance: 1473 353 1918 413 Time: 88 63 96 87 Distance: 805 362 788 1470 Time: 87 74 92 78 Distance: 1042 599 1512 1364Pour la partie 2, vous devriez trouver les résultats suivants
-
Time = 90929679, Distance = 14733531918413 => 90605036
-
Time = 88639687, Distance = 8053627881470 => 88457784
-
Time = 87749278, Distance = 104259915121364 => 85339885
pour un total de 90605036+88457784+85339885 = 264402705.
Testez votre solution sur le fichier test06_big (1000 courses), test06_bigger (10000 courses), voir même sur le fichier test06_even_bigger (100000 courses).
-
-
Expliquez pourquoi le benchmark BenchmarkMax3Sort3Prefix est plus rapide que BenchmarkMax3Sort3Suffix. (Dans le fichier max3_test.go.)
Note : pour lancer le benchmark, copiez le fichier max3_test.go dans un dossier contenant un module Go, et utilisez la commande
$ go test -bench=Max3
Séances 5, 6, 7 (03-02-2025, ...) : mini projet
Pour les 3 prochaines séances, chacun d'entre vous devra travailler sur un problème différent, attribué de manière aléatoire.
La colonne "objectifs" donne des pistes intéressantes à considérer. N'hésitez pas à nous demander si vous ne savez pas quoi faire.
Parmi les choses à envisager :
-
avoir une solution pour les deux parties de votre problème,
-
vérifiez que votre solution marche sur d'autres fichiers d'entrée,
-
écrire un générateur de fichiers d'entrée pour tester et comparer plusieurs solutions,
-
améliorer la complexité "pratique" de votre solution,
-
améliorer et mettre en évidence la complexité "théorique" de votre solution,
-
implémenter un algorithme connu pour le problème et le comparer à une version "naïve",
-
visualiser vos solutions de manière "sympa",
-
etc.
Vous devrez présenter votre travail lors de la dernière séance du 24 février. Chaque présentation devra durer 10 minutes, en incluant 3 minutes de questions !
Chacun devra également présenter son problème de manière simple et succincte (3 minutes) lors de la séance du 12 ou 17 février.
| année | jours | lien | objectifs | ... |
|---|---|---|---|---|
| 2023 | 18 | Lavaduct Lagoon | partie 2 en moins de 10ms | surface de polyomino |
| 2024 | 7 | Bridge Repair | comparaison de plusieurs méthodes | choix d'opérateurs pour un résultat |
| 2016 | 14 | One-Time Pad | partie 2 en moins de 5 secondes | plein de MD5 |
| 2024 | 21 | Keypad Conundrum | partie 2 efficace | déplacement avec plusieurs indirections |
| 2023 | 12 | Hot Springs | solution récursive et solution automate | expression régulière "à l'envers" |
| 2023 | 23 | A Long Walk | partie 2 en moins de 1s | plus long chemin dans un graphe |
| 2021 | 22 | Reactor Reboot | partie 2 efficace et code clair | union / intersections de pavés |
| 2024 | 23 | LAN Party | version "directe" et algorithme de Bron-Kerbosch | clique maximale |
| 2024 | 20 | Race Condition | partie 2 efficace et plus générale | chemin dans un arbre |
| 2024 | 14 | Restroom Redoubt | partie 2 automatique et générale | découverte de motif visuel |
| 2022 | 17 | Pyroclastic Flow | partie 2 fonctionnelle | tetris |
| 2024 | 24 | Crossed Wires | partie 2 plus générale | correction d'erreurs dans un circuit |
Séance 8 (20-03-2025)
Pour commencer, écrivez des fonctions pour résoudre les problèmes suivants (parties 1 et 2).
| année | jours | lien |
|---|---|---|
| 2024 | 19 | Linen Layout |
Bonus : [AFFICHER]
decompositions (efficace) qui calcule la liste des
décompositions possibles. Pour reprendre un exemple du problème, pour la
chaine "rrbgbr", votre fonction devra renvoyer la liste
{
{"r", "r", "b", "g", "b", "r"},
{"r", "r", "b", "g", br"},
{"r", "r", "b", "gb", r"},
{"r", "rb", "g", "b", r"},
{"r", "rb", "g", "br"},
{"r", "rb", "gb", "r""},
}Projet compression de données
Pour les prochaines séances, vous serez répartis en 3 groupes. Chaque groupe travaillera sur un algorithme de compression :
-
Lempel–Ziv–Welch,
-
compression par intervalles ("codage arithmétique"),
-
bzip2 et transformée de Burrows-Wheeler.
Les groupes ne sont pas des "groupes de projet" : chacun doit implémenter sa propre version de l'algorithme. L'objectif est que vous puissiez discuter, partager et comparer ce que vous faites.
-
un lien qui décrit assez bien comment on peut agencer un module Go, avec plusieurs "packages"
-
Votre code devra fournir des types satisfaisant les interfaces
type Compresser interface { Compress([]byte) []byte }et
type Deompresser interface { Decompress([]byte) []byte }(Il s'agit de la même interface, avec des noms différents.)
Objectifs
Les objectifs sont les suivants :
- implémenter, un programme de compression / décompression de fichiers arbitraires sans utilisation de bibliothèque externe.
-
Votre programme final devra, au minimum, avoir les fonctionnalités suivantes :
-
compression d'un fichier et sauvegarde du résultat dans un autre fichier
-
décompression d'un fichier et sauvegarde du résultat dans un autre fichier
-
test automatique qui compresse, décompresse et vérifie que le résultat est identique au fichier de départ.
-
chaque exécution devra afficher des informations de manière lisible, notamment
-
le temps d'exécution,
-
le gain en espace (100 * (1 - taille(chaine_compressée)/taille(chaine_originale))),
-
Vous pouvez faire un programme de compression et un programme de décompression, mais il probablement plus simple d'utiliser des arguments pour choisir l'action à effectuer. (Module
flagde la bibliothèque standard.)Voici par exemple une exécution de mon de mon programme pour LZW :
$ go build $ ./lzw -T test_files/karamazov.txt ### Lempel / Ziv / Welch compression ## compressing file 'test_files/karamazov.txt' >>> reading file: ( 1ms) => 2042003 bytes >>> compressing: ( 85ms) => 780332 bytes, compression 62% >>> saving: ( 0ms) ## compressed file 'test_files/karamazov.txt.lzw' saved ## decompressing file 'test_files/karamazov.txt.lzw' <<< read file: ( 0ms) => 780332 bytes <<< decompressing: ( 24ms) => 2042003 bytes <<< saving: ( 0ms) ## decompressed file 'test_files/karamazov.txt.lzw.wzl' saved ## comparing: OK ( 1ms)L'option -T lance le test complet. Les options -C et -D permettent respectivement de compresser ou décompresser.
-
- améliorer la vitesse d'exécution et le gain de compression
-
Les 2 objectifs sont en général contradictoires. Des pistes sont données dans la section suivante.
Il faut pouvoir choisir la version de votre programme afin de pouvoir les comparer facilement. Par exemple, vous pouvez utiliser -C 1 pour compresser avec la première version, -C 2 avec la deuxième, etc.
Quel que soit votre choix, votre programme doit disposer d'une aide qui permet de savoir ce que l'on fait. Voici un exemple minimaliste :
$ ./lzw -h Usage of ./lzw: -C compress input file -D decompress input file -P turn on profiling -T compress, decompress and check the result -max-dict int maximal dictionnary size (default 65536) - tester, comparer et conclure
-
Vous devrez comparer vos algorithmes sur différents type de fichier pour étudier les taux de compression / vitesses d'exécution sur différents fichiers et détailler les points forts et faibles de votre algorithme. L'archive test_files.zip contient plusieurs fichiers de 2M chacun, ainsi qu'un script Python qui génère d'autres fichiers qui peuvent servir pour vos premiers tests.
Idéalement, vous devrez également comparer vos versions individuelles au sein du même groupe, ainsi que les différents algorithmes entre eux.
Détails
Groupe 1 : Lempel–Ziv–Welch
- liens utiles
-
-
la page wikipedia est plutôt bien : LZW
-
l'article de Terry Welch de 1984 : welch1984.pdf
-
un TP de L1 où nous faisons implémenter LZ78, dont LZW est une variante : tp2.html
-
- point de départ
-
L'algorithme de base est le plus simple des 3. Vous pouvez utiliser le TP mentionné ci dessus, en adaptant le code pour LZW. L'algorithme de décompression est légèrement plus complexe (cf la page Wikipedia), mais il n'y a pas besoin de gérer des "liste alternées" avec des caractères et des entiers.
Stockez les entiers sur 2, 3 ou 4 octets suivant la taille du dictionnaire et vous aurez une première version de LZW. (Le dictionnaire contient initialement 256 valeurs, les indices doivent donc être codés sur 2 octets dès la seconde étape.)
- améliorations possibles
-
-
Il faudra impérativement utiliser une table de hachage pour la compression (fin du TP de L1).
-
Pour gagner de la place, on peut stocker les entiers sur le nombre minimal de bits nécessaires. Au lieu de passer de 2 octets à 3 octets quand la taille du dictionnaire arrive à 65536, on peut passer de 9 bits à 10 bits quand elle arrive à 512 ; puis de 10 bits à 11 bits quand elle arrive à 1024 ; etc.
Attention, cela nécessitera de gérer la lecture et l'écriture de bits individuels dans un fichier. C'est l'occasion parfaite d'écrire un package dans votre projet. Il faudra également ajouter du "padding" pour que le nombre final de bits écrits soit un multiple de 8.
-
Pour accélérer la compression, on peut remplacer le dictionnaire
map[string]intpar un dictionnairemap[[2]int] int: au lieu de stocker le mot précédent suivi du nouvel octet, on utilise l'indice du mot précédent (premier entier) et le nouvel octet (stocké second entier).Plusieurs choix sont possibles pour les clés : tableau statique de 2 entiers,
structavec un entier et un octet, entier 64 bits où les bits de poids fort / faible sont utilisés pour l'indice précédent et le nouvel octet, et probablement d'autres.Testez différentes versions et comparez les.
-
Pour éviter que le dictionnaire ne deviennent trop grand, on peut arrêter d'y ajouter les nouveaux motifs lorsqu'il atteint une certaine taille.
On peut également le réinitialiser: soit directement, soit lorsqu'on détecte que le taux de compression devient trop petit.
Attention, il faut que l'algorithme de décompression utilise les même paramètres que celui de compression. Vous pouvez gérer ça "à la main", ou en ajoutant une entête (quelques octets au début du fichier compressé) pour que la décompression utilise automatiquement les bon paramètres.
-
Groupe 2 : codage arithmétique
- liens utiles
-
-
La page Wikipedia est pas mal : Arithmetic coding , mais il n'est pas évident d'en retirer une implémentation raisonnable.
-
Une manière d'implémenter les codages arithmétiques se trouve sur la page Wikipedia "range coding", mais la qualité de cette page ... laisse fortement à désirer !
-
Le chapitre 2.2.2 du livre "Théorie des codes", de JM. Dumas, JL. Roch, É. Tannier et S. Varrette explique bien le fonctionnement général de l'algorithme, mais sans rentrer dans les détails d'implémentation. Nous vous donnerons une copie des parties pertinentes.
-
L'article de Ian Witten, Radford Neal et John Gleary de 1987 : acm87_arithmetic_coding.pdf est bien et fournit une implémentation complète, en C.
-
L'article de A. Moffat, RN. Neal et IH. Witten de 1998 : acm98_arithmetic_coding_revisited.pdf contient des amélioration du précédent, mais je ne les ai pas étudiées de prêt.
-
- point de départ
-
L'algorithme de départ est plus difficile à coder que les 2 autres, notamment parce qu'il est moins facile à tester "incrémentalement". Par contre, les premières améliorations sont très simples.
Commencez par utiliser un "modèle" fixe pour les octets du message. Vous pouvez l'obtenir en parcourant le fichier à compresser une première fois pour compter les caractères qu'il contient. (Attention, il faut dans ce cas sauvegarder les fréquences des caractères trouvés dans une entête du fichier compressé.)
Pour bien comprendre le fonctionnement, vous pouvez implémenter une version "en base 10" en suivant le chapitre du livre "Théorie des codes". Cela permet de se familiariser avec le fonctionnement et de faire tourner des petits exemples "à la main".
La version définitive devra travailler "en base 256" pour travailler directement avec des octets. L'article de I. Witten, R. Neal et J. Gleary est un bon point de départ. Il faudra convertir le code donné en Go, mais cela donne une bonne base.
- améliorations possibles
-
Si vous avez une version "en base 10" et une autre "en base 256", vous pouvez les comparer. (Sans comptabiliser la sauvegarde dans un fichier.)
Une fois que vous avez une version "en base 256", vous pouvez regarder des améliorations sur le modèle prédictif des caractères. Au lieu de faire un passage préliminaire sur le fichier à compresser, on part d'un modèle (presque) vide, et on ajoute les caractère au fur et à mesure qu'on les compresse. On risque de perdre un peu de place au début (car le modèle n'est pas précis), mais il n'est alors plus nécessaire de sauvegarder le modèle dans le fichier.
On peut essayer de jouer sur la taille des intervalles pour voir ce qui se passe.
On peut modifier le modèle pour qu'il "oublie" les caractères très anciens.
D'autres améliorations sont décrites dans l'article de A. Moffat, RN. Neal et IH. Witten.
Groupe 3 : transformée de Burrows Wheeler et bzip
- liens utiles
-
-
la page wikipedia est plutôt bien : Burrows–Wheeler transform
-
la page wikipedia de bzip2 contient des détails sur l'utilisation de Burrows-Wheeler pour la compression : bzip2
-
la description originale de 1994 par M. Burrows et DJ. Wheeler est assez lisible et contient la description des algorithmes en pseudo-code : bwt-1994.pdf
-
- point de départ
-
La transformée de Burrows Wheeler est une phase préparatoire à la compression : on transforme une suite d'octets en une autre suite d'octet de même taille. Cette suite est plus facile à compresser et permet de retrouver la suite originale.
L'algorithme de compression de base se décompose en plusieurs étapes :
-
transformée de Burrows Wheeler ("BTW")
-
transformation "move to front"
-
"run-length encoding" ("RLE", facultatif)
-
codage de Huffman
Cela fait un peu plus de code que les algorithmes précédents, mais chacun d'entre eux est assez simple, et on peut les tester indépendamment.
Dans un premier temps, utilisez un algorithme "naïf" pour calculer BWT, par exemple en utilisant directement la fonction
slices.Sortde Go.Les étapes "move to front" et "RLE" sont très simples.
Le codage de Huffman est la partie la plus complexe dans cette première version, mais cela ne demande pas tellement de code. (Première implémentation : 45 lignes pour le codage, 35 pour le décodage.) Comme pour le groupe qui implémente LZW, il faudra gérer l'écriture de bits en nombres arbitraires dans un fichier.
-
- améliorations possibles
-
-
tester l'impact de l'étape "RLE" : bzip2 l'utilise, mais la description initiale ne l'utilise pas
-
améliorer le calcul de BWT :
-
en utilisant
slices.SortFuncpour améliorer la fonction de comparaison -
en implémentant un meilleur tri spécialement optimisé pour les permutations circulaires d'une chaine (cf l'article de M. Burrows et DJ. Wheeler)
-
en utilisant une implémentation existante : la bibliothèque standard de go contient un package
suffixarrayqui calcule l'arbre des suffixes d'une chaine en temps linéaire. Il est possible d'en extraire une variante de la transformée de Burrows-Wheeler. L'inversion sera légèrement différente de ce que décrivent M. Burrows et DJ. Wheeler. Comme la fonction pertinente du packagesuffixarrayest privée, vous devrez copier les 2 fichiers $GOROOT/src/index/suffixarray/{sais.go,sais2.go} dans votre module (n'oubliez pas de modifier les lignespackage ...). La fonctiontext_32vous permettra de calculer "l'arbre des suffixes" d'une suite d'octets.
-
-
