Site de Vincent Gripon

Compressing multisets using tries

Nous considérons le problème de représenter sans perte et efficacement des multiensembles de m éléments tirés avec répétitions dans un ensemble de taille 2^n. On est en droit de penser que l'encodage d'un tel multiensemble devrait apporter un grand gain par rapport à celui de la séquence des tirages correspondante, puisque l'information correspondant à l'ordre des tirages dans la séquence représente une permutation. Nous proposons et analysons un encodeur/décodeur basé sur des arbres préfixes. La phase d'encodage a une complexité en O(m(n+log m)) tandis que la phase de décodage a une complexité en O(mn). Nous nous intéressons plus particulièrement au cas où le nombre d'éléments m est 2^n/c, pour c > 1 et n → ∞. Sous ces conditions, et si les éléments du multiensemble sont tirés avec équiprobabilité, nous montrons que l'encodage proposé permet un gain non borné. De plus, l'espérance de la longueur du multiensemble encodé est asymptotiquement à un facteur 5/3 de la borne inférieure.

@inproceedings{GriRabSkaGro20129,
  author = {Vincent Gripon and Michael Rabbat and
Vitaly Skachek and Warren J. Gross},
  title = {Compressing multisets using tries},
  booktitle = {Proceedings of Information Theory
Workshop},
  year = {2012},
  address = {Lausanne, Switzerland},
  month = {September},
  pages = {647--651},
}