PICSI

Un moyen majeur de détection d’une suite aléatoire est d’observer la façon dont elle peut être compressée sans perte d’informations. En effet, les algorithmes de compression sans pertes utilisent des répétitions de séquences, appelées mots, pour économiser de la place : au lieu de stocker chaque octet, l’algorithme crée une table (un dictionnaire) de mots auxquels sont associés leurs occurrences dans le fichier. S’il n’y a aucune répétition, non seulement le gain de place est nul, mais il y a en réalité perte de place à cause de l’en-tête du fichier où sont stockées des informations nécessaires à la décompression. Ainsi lors de la compression d’une séquence aléatoire, aucune place significative ne doit être gagnée.

 Le test de Lempel-Ziv ne procède pas à la compression « effective » de la suite. Il utilise directement l’algorithme de Lempel-Ziv, mais il s’arrête à la création du dictionnaire. Celui-ci est créé de façon légèrement différente puisque toute la suite lui sert de base et que les mots ont une longueur quelconque. Il n’y a donc aucun paramètre à fixer pour ce test. Par ailleurs le dictionnaire ne stocke aucune valeur associée aux mots : en effet la valeur significative de ce test est cette fois le nombre de mots générés. Voici, sur un exemple, comment le dictionnaire est généré. La suite considérée est la suivante : 010110010.
Le programme examine le premier bit et décide que c’est un nouveau mot. Il examine le second bit et, comme il ne l’a pas rencontré avant, décide que c’est un nouveau mot. Il examine le bit suivant et, comme a déjà rencontré un mot commençant par ce bit, il continue jusqu’à former un mot nouveau ; il va donc ici jusqu’au bit 4 pour former le mot 01. Le programme parcours ainsi la suite jusqu’à la fin. Les mots du dictionnaire sont dans ce cas : 0, 1, 01, 10, 010.

            Cependant il faut noter que des lacunes théoriques en empêchent l’utilisation avec des longueurs de suites quelconques (on ne possède de données que pour n = 1 million). Il est également recommandé d’utiliser un générateur de type SHA-1 pour générer la suite. Des travaux sont en cours pour permettre l’utilisation d’autres générateurs (notamment le générateur de Blum-Blum-Schnorr) et d’autres tailles. L’implémentation de ce test utilise donc les valeurs théoriques disponibles. Si on souhaite tester d’autres générateurs, ou des suites de longueurs différentes, cela reste évidemment possible, mais l’interprétation des résultats devient plus complexe, notamment en cas « d’échec » : celui-ci peut être dû au générateur ou simplement aux données théoriques qui ne sont pas adaptées au générateur.