Journal d'un Terrien

Web log de Serge Boisse

On line depuis 1992 !

Publicité
Si cette page vous a plu, Copiez son adresse et partagez-la !
http://sboisse.free.fr/programmation/Algorithmes/repetitions dans une sequence.php
Savez-vous quels sont les articles les plus vendus sur Amazon.fr ?
répétitions dans une séquence
programmation > Algorithmes > répétitions dans une séquence

répétitions dans une séquence

Auteur : Serge Boisse

Références : cf références ci-dessous

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".

exemple

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) :

Séquences binaires

Syntaxe

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

îR code une chaine suivie de son inverse
t code une chaîne suivie de sa transposée 0<->1
îX code une chaîne suivie de l'inverse de sa transposée
tn code une chaine suivie de sa transposée répétée n fois
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.

programmation dynamique

On pose la longueur séquence d'entrée, et la longueur minimale dans laquelle la séquence entre les index et peut être compressée.

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 :

  • collage : pour tous les de à
  • répétition : pour tous les qui divisent la chaîne en sous-chaînes identiques de longueur . Je pense que le minimum sera pour la plus petite valeur de k (pas sûr ?)
    Calculer le minium de toutes ces valeurs DP.

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.

Calcul incrémental

Lorsqu'on a des séquence croissantes on peut bien sûr mémoriser les précédemment calculées pour et de 0 à .
Lorsqu'on a une è nouvelle donnée, donc à l'index , l'objectif est de calculer et la séquence résultante.

au fil de l'eau

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

fenêtre glissante

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

Essai de programmation...

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

ce programme n'est pas le plus rapide ni le plus efficace, et de loin ! En fait au delà de 25 symboles il devient trop lent...

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

autre algorithme de compression de chaînes de symboles (beaucoup plus rapide !)

L'idée est toute simple :
On suppose que "()^{}" ne sont pas des symboles terminaux.

  1. chercher dans la chaîne les sous-chaînes ... qui se répètent (c'est à dire est un fragment répété ni fois), et qui sont les plus longues possibles.
  2. si on a trouvé plusieurs sous chaînes de même longueur maximale choisir celle qui a le plus grand nombre de répétitions (d'un pattern ). On a donc S=prefixe(F)^{n}suffixe
  3. compresser le préfixe, puis F puis le suffixe et concaténer.

(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 !

compresseur de chaînes de caractère par détection de répétition

@ calculateur compression chaîne
@ calculateur compression chaîne

non-unicité

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 selon l'agorithme, mais serait tout aussi bon

compresser des séquences qui se répètent, mais non forcément consécutives

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 : alors que sans cette virgule et cet espace, "ainsi font font font, les petites marionnettesainsi font font font, les petites marionnettes" sera compressé en :

Plus difficile :
"ainsi font font font, les petites marionnettes, ainsi font les petites marionnettes, "

références

Publicité
Commentaires

Commentaires (0) :

Page :



Ajouter un commentaire (pas besoin de s'enregistrer)

Pseudo :
Message :


image de protection
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.
< Retour en haut de la page