Compression d'un tableau d'entier

29 mai 2024, 09:07

Bonjour à tous,

J'ai un projet qui utilise comme clé entre table un tableau de tableau d'entier de ce type
((0,1,2,3,4,5),(0,1,2,3,4,5,6,7),(-1,-1,-1,-1,0,0,0,0),(-1,-1,-1,-1,4,5,6,7,8,9,10,11),(0,1,0,1,0,0,0,0,0,0,0,0))
Pour les curieux il s'agit de l'état d'un rubik's cube. Les tableaux représentent : la position des centres, la position des coins, l'orientation des coins, la position des arêtes et l'orientation des arêtes. Donc il s'agit d'entier de -1 à 11.

Je le stocke sous forme de string, je cherche à le compresser au maximum de façon réversible et unique.

J'ai pensé à quelques algo perso qui devrait bien marcher, mais il existe peut être des solutions toute faite et bien pensé.
Idéalement cette compression peut se faire en javascript, php ou mysql.

Merci d'avance

29 mai 2024, 11:37

Une piste : https://www.php.net/manual/fr/function.gzdeflate.php

29 mai 2024, 23:43

Merci de ton commentaire je ne connaissait pas ces fonctions et je les ai donc tester gzdeflate/gzinflate ainsi que gzcompress/gzuncompress.
J'arrive à reduire mes masques de moitié.
J'ai trouvé aussi COMPRESS/UNCOMPRESS en MYSQL, qui est un tout petit peu moins bon mais demande de modifier mon champs VARCHAR en BLOB.

J'ai finalement opté pour un couple de fonction perso en MYSQL qui se base sur un masque de réfèrence. L'idée est que la majorité des masques ne diffèrent pas beaucoup de cette reférence.
Je commence donc par supprimer mes paranthèse (elle sont toujours au même endroit), et remplacer chaque chiffre par une lettre 0 =>a, 1=>b ... 11=>l et -1=>z.
Je "soustrais" mon masque de réfèrence charactère par charactère (en conservant les virgule)
Ensuite je remplace les suite de virgule > 2 par le nombre de virgule et supprime les virgules unique.

Et je fait l'inverse pour decoder

Code : Tout sélectionner

-- maskreduce function to compress mask
DROP FUNCTION IF EXISTS `v3db.francocube`.maskreduce;
DELIMITER |
CREATE FUNCTION `v3db.francocube`.maskreduce( str CHAR(255) ) RETURNS CHAR(255) DETERMINISTIC
BEGIN
DECLARE i, len SMALLINT DEFAULT 1;
DECLARE j SMALLINT DEFAULT 0;
DECLARE ret CHAR(255) DEFAULT '';
DECLARE c CHAR(1);
DECLARE d CHAR(1);
DECLARE ref CHAR(255) DEFAULT 'a,b,c,d,e,f,a,b,c,d,e,f,g,h,a,a,a,a,a,a,a,a,a,b,c,d,e,f,g,h,i,j,k,l,a,a,a,a,a,a,a,a,a,a,a,a';
IF str IS NOT NULL THEN
SET str = REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(IFNULL(str, ''),
'-1', 'z'),
'11', 'l'),
'10', 'k'),
'0', 'a'),
'1', 'b'),
'2', 'c'),
'3', 'd'),
'4', 'e'),
'5', 'f'),
'6', 'g'),
'7', 'h'),
'8', 'i'),
'9', 'j'),
'(', ''),
')', '');
SET len = CHAR_LENGTH( str );
REPEAT
BEGIN
SET c = MID( str, i, 1 );
SET d = MID( ref, i, 1 );
IF c = ',' THEN
SET j = j + 1;
ELSEIF c != d THEN
IF j > 1 THEN
SET ret=CONCAT(ret,j,c);
ELSE
SET ret=CONCAT(ret,c);
END IF;
SET j=0;
ELSE
SET ret=ret;
END IF;
SET i = i + 1;
END;
UNTIL i > len END REPEAT;
IF j > 1 THEN
SET ret=CONCAT(ret,j);
END IF;
ELSE
SET ret='';
END IF;
RETURN ret;
END |
DELIMITER ;
-- maskexpand function to uncompress mask
DROP FUNCTION IF EXISTS `v3db.francocube`.maskexpand;
DELIMITER |
CREATE FUNCTION `v3db.francocube`.maskexpand( str CHAR(255) ) RETURNS CHAR(255) DETERMINISTIC
BEGIN
DECLARE i, len SMALLINT DEFAULT 1;
DECLARE ret CHAR(255) DEFAULT '';
DECLARE c, e CHAR(1);
DECLARE d CHAR(2);
DECLARE ref CHAR(255) DEFAULT 'a,b,c,d,e,f,a,b,c,d,e,f,g,h,a,a,a,a,a,a,a,a,a,b,c,d,e,f,g,h,i,j,k,l,a,a,a,a,a,a,a,a,a,a,a,a';
IF str IS NOT NULL THEN
SET len = CHAR_LENGTH( str );
REPEAT
BEGIN
SET c = MID( str, i, 1 );
SET d = MID( str, i, 2 );
IF d REGEXP '^[[:digit:]]*$' THEN
SET ret=CONCAT(ret,LPAD('',d,','));
SET i = i + 1;
ELSEIF c REGEXP '^[[:digit:]]*$' THEN
SET ret=CONCAT(ret,LPAD('',c,','));
ELSEIF d REGEXP '^[[:alpha:]]*$' THEN
SET ret=CONCAT(ret,c,',');
ELSE
SET ret=CONCAT(ret,c);
END IF;
SET i = i + 1;
END;
UNTIL i > len END REPEAT;
SET i = 1;
SET len = CHAR_LENGTH( ref );
REPEAT
BEGIN
SET c = MID( ref, i, 1 );
SET e = MID( ret, i, 1 );
IF e=',' OR e='' THEN
SET ret=CONCAT(MID(ret,1,i-1),c,MID(ret,i));
END IF;
SET i = i + 2;
END;
UNTIL i > len END REPEAT;
SET ret = CONCAT('((',MID(ret,1,11),'),(',MID(ret,13,15),'),(',MID(ret,29,15),'),(',MID(ret,45,23),'),(',MID(ret,69,23),'))');
SET ret = REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(IFNULL(ret, ''),
'z', '-1'),
'l', '11'),
'k', '10'),
'a', '0'),
'b', '1'),
'c', '2'),
'd', '3'),
'e', '4'),
'f', '5'),
'g', '6'),
'h', '7'),
'i', '8'),
'j', '9');
ELSE
SET ret='';
END IF;
RETURN ret;
END |
DELIMITER ;

31 mai 2024, 10:06

Et par curiosité, tu as quel gain de compression entre ton algo et gzdeflate ?

31 mai 2024, 22:19

Hello,

de mémoire je n'ai pas gardé les infos
Pour une table de 371373 entrées,
sans compression +/-55 Mo
avec COMPRESS (MySQL) +/- 27 Mo
avec mon algo 15.0 Mo

J'ai fini par ajouter une touche en plus, les séquence de plus d'un z sont remplacé par une lettre majuscule
zz => A, zzz => B, ...
Car ce sont des séquences qui reviennent souvent. J'ai gagné +/- 2 Mo la dessus.

J'obtient des chaines de 5 à 27 caractères. Avant j'étais à 105 à 115 caractères.
Avec gzdeflate, mes chaines se réduisait à minimum 52 caractère avec un facteur de compression de 5 (au dessus n'apportait pas mieux). gzcompress était un peu moins bons
J'ai aussi opter pour ma solution car une oeil averti peut se faire une idée du masque sans le décoder.
Et aussi je me limite à des caractère alphanumérique contrairement à gz et compress ce qui me rassure dans le stockage, les comparaison, l'index et les transactions.

03 juin 2024, 00:20

Top, intéressant

Compression d'un tableau d'entier

Qui est en ligne