Objectif du projet
L'algorithme de Hu-Tucker est un algorithme qui permet de construire un arbre alphabétique binaire optimal: un arbre, qui garde l'ordre lexicographique de ses éléments et dont le chemin pour atteindre chacun de ses éléments est en moyenne le plus court. On l'utilise par exemple pour compresser du texte quand l'ordre des caractères doit être préservé, par exemple pour stocker des dictionnaires.
Le travail demandé consiste à implémenter l'algorithme de Hu-Tucker en Python. Il faudra dans un premier temps produire une implémentation qui fonctionne à partir d'une explication de l'algorithme, avant de réfléchir à diverses optimisations. On comparera aussi la performance avec des implémentations existantes (par exemple en C)
Encadrement
Le projet sera encadré par Julien Gori, chercheur à l'ISIR en méthodes computationelles pour l'Interaction Humain-Machine.
Contexte
On a récemment montré que la construction d'un arbre binaire alphabétique pouvait être exploité pour minimiser la durée pour effectuer certains tâches sur un ordinateur, comme de la navigation sur une carte avec un nombre d'actions limitées. Le but de ce projet est de travailler vers une évaluation empirique qui exploite Hu-Tucker, pour notamment avoir une première estimation dans un cadre restreint du gain de temps possible. Ce projet peut être poursuivi par un stage dans l'été.
Contact