Web log de Serge Boisse
On line depuis 1992 !
Auteur : Serge Boisse
Il s'agit de détecter des répétitions et de compresser une suite de symboles, par exemple binaires, afin éventuellement d'en prédire la suite.
Note : pour prédire une séquence, il est utile de détecter les répétitions, mais d'autres patterns sont possibles, comme
- l'inversion (une séquence, suivie de la même dans l'ordre inverse),
- la transposition (on remplace un symbole par un autre), e.g. S suivie de S(0<->1)
- le codage (une séquence en désigne en fait une autre, précédente et plus longue, ou une opération), ou sert de séparateur...
Les nombres dans les répétitions peuvent aussi suivre un certain pattern... e.g compteur : 1011011101111011110
Le détecteur le plus général est un automate de Turing ?
On peut évidement se référer aux algorithmes classiques de compression losseless classiques : run-length encoding, huffman encoding, Lempel-Ziv Schemes (LZSS), et pour les images, png et Qoi compression losseless d'images
Mais notre but ultime est de créer un module simple qui, si on lui fournit un stream de données, va "intuiter" la structure la plus "usuelle" de ces données et signaler les "évènements" tels qu'un "outlier" ou un changement de pattern. Ce module pourra ensuite être utilisé pour créer un nouveau style de programmes d'IA qui ne serait pas basé sur des réseaux de neurones, mais sur des détecteurs d'évènemenst "inhabituels".
cf https://stackoverflow.com/questions/56073698/algorithm-to-group-repetitions-in-a-sequence
Exemples
Entrée: 1, 1, 1, 2, 1, 1, 1, 2
Sortie: ((1)3, 2)2
Entrée: 1, 2, 1, 2, 1, 2
Sortie: (1, 2)3
Entrée: 1, 1, 1, 2, 1, 2
Sortie: (1)2, (1, 2)2
Restons sur l'exemple le plus simple (quoi que) :
Sortie :- code | code, Sortie
chaîne :- 0 | 1 | 0 chaîne | 1 chaîne
code :- chaîne | (Sortie)suffixe
suffixe : R | t | X | R n | t n | X n
exemples
- (1,0,1)3 -> 101101101
- (1,0,0)R -> 100001
- (1,0,0)t -> 100011
- (1,0,0)X -> 100110
- (1,0,0)t3 ->100011011011
pour coder la chaine 011 suivie de sa transposée, le tout répété n fois, il faut écrire ((0,1,1)t)n -> longueur 4
La longueur de la chaine Sortie sera comptée sans les parenthèse ni les virgules. Par exemple la longueur de (1)3, (1, 0)t2 est 6. (pour Entrée =1110101)
A voir : est-ce qu'on compte les suffixes, ou seulement le nombre de termes originaux de la séquence ? Je choisis la première option.
On pose
Entrée: 1, 1, 1, 2, 1, 2
Index: 0, 1, 2, 3, 4, 5
DP[0][1] = 2 chaîne 1,1 -> (1)2
DP[0][2] = 2 chaîne 1,1,1 ->(1)3
DP[0][3] = 3 chaîne 1,1,1,2 ->(1)3,1
Notre but est de calculer
On a bien sûr
si on ne tiens pas compte des transposées et inversions,
Il y a deux cas possibles pour trouver
remarque : dans (10)2, pourquoi fixer la longueur à 3 ? je pense qu'on peut la mettre à 2, c'est à dire ignorer "l'exposant" 2 ; une séquence compressée est toujours mieux qu'une séquence non compressée.
Lorsqu'on a des séquence croissantes on peut bien sûr mémoriser les
Lorsqu'on a une
Essayons de voir ce qui se passe quand on rajoute un symbole à la fin d'une une chaine déjà compressée : peut en déduire "facilement" une nouvelle chaîne compressée ?
Ce sujet est tellement vaste que j'en ai fait une page à part : voir compression au fil de l'eau
ici on imagine une fenêtre de longueur constante, donc lorsqu'on rajoute un symbole à droite on perd celui de gauche. Si le codage sortie commence à gauche par une chaine 0 ou 1 ce n'est pas grave. Mais supposons une fenêtre de largeur 10, et la chaine composée d'une suite de "110" tronquée à droite
1101101101 qui est codée par (110)3,1 ou 1,(101)3
si on rajoute le symbole 1 à droite (qui suit la séquence)
cela supprime aussi le premier 1 à gauche et la séquence devient 1011011011 qui sera codée par (101)3,1 ou 1,(011)3 et on ne reconnait plus la séquence 110
ici pour simplifier on ne va que tenter de coder les répétitions (10)n
on va créer une structure pour coder les résultats (10..)n
{
s: <la chaine r ou une sous-structure à répéter>
rep: <le nombre de répétitions, >=1>
}
Lorsque rep vaut 1 et fin, on écrira juste (s)
le résultat "code" sera un array de ces structures
la complexité sera juste la somme de la longueur des s
par exemple
"1010" -> [{s:"10", rep:2}], -> (10)2 complexité 2
"101"->[{s:"10",rep:1},{s:"1",rep:1}] -> (10)2(1) complexité 3
en fait pour les répétitions, on ajoutera le log2 de l'exposant, (moins 1. ?)
par contre on pourra chaîner les structures :
ainsi "((10)2(1))2" -> "(10101)2" -> 1010110101
cf. ci-dessous autre algorithme de compression de chaînes de symboles plus rapide
Entre une chaine de symboles, comme "aabbaa"
résultat:
ça marche ! Mais le programme ci-dessous est bien plus rapide
L'idée est toute simple :
On suppose que "()^{}" ne sont pas des symboles terminaux.
S=prefixe(F)^{n}suffixe(il y a quelques subtilités pour éliminer les parenthèses inutiles)
La difficulté de l'algorithme est évidemment dans le point (1). Mais il existe des algorithmes linéaires. Cf https://fr.wikipedia.org/wiki/Arbre_des_suffixes. Hint: build suffix tree, then find the highest node with at least 2 descendants.
à partir de "11101101110110110110" que je pensais égale à 1(110:2)1(110:4), ou en latex :
on obtient successivement
11101101110110110110
(1110110)^2110110
(1(110)^2)^2110110
(1(110)^2)^2(110)^2
(1(1^20)^2)^2(110)^2
(1(1^20)^2)^2(1^20)^2
soit en Latex :
WOW !
A noter que l'algo trouve une chaine courte (est-elle toujours la plus courte ?) mais qu'elle n'est pas forcément unique.
Ainsi "abababa" donne
Soit à compresser : "ainsi font font font, les petites marionnettes, ainsi font font font, les petites marionnettes" qui est de la forme AB, AB (le problème vient de la virgule e de l'espace au centre)
qui donnera :
Plus difficile :
"ainsi font font font, les petites marionnettes, ainsi font les petites marionnettes, "
Commentaires (0) :
Page :Ajouter un commentaire (pas besoin de s'enregistrer)
En cliquant sur le bouton "Envoyer" vous acceptez les conditions suivantes : Ne pas poster de message injurieux, obscène ou contraire à la loi, ni de liens vers de tels sites. Respecter la "netiquette", ne pas usurper le pseudo d'une autre personne, respecter les posts faits par les autres. L'auteur du site se réserve le droit de supprimer un ou plusieurs posts à tout moment. Merci !Ah oui : le bbcode et le html genre <br>, <a href=...>, <b>b etc. ne fonctionnent pas dans les commentaires. C'est voulu.