Discussion :

[cbil1]

Bonjour,

Je cherche à détecter dans une matrice binaire le groupement maximum de valeur à 1 formant un rectangle si regroupé.
J'entend par maximum, qu'il contient le plus de 1 possible.

Exemples:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
1 0 0 1			
1 1 1 1			1 1 1 1
1 1 1 1			1 1 1 1
0 1 0 0 	donne			(8 valeurs)

1 0 0 1 0 1		1 1 1
1 1 0 1 1 1		1 1 1
1 0 1 1 1 1		1 1 1
0 1 0 0 1 0	donne			(9 valeurs)

Après avoir parcouru brièvement les cours algorithmique, je me rend compte à quel point le sujet est vaste. Si un algo existe déjà ou se rapproche, comment s'appellerait-il ?

Pour le moment, sans aucune logique d'optimisation, je teste tous les ensembles possibles et garde le maximum (traitement de plusieurs heures sur de grandes matrices *aïe*). Je tente de lister des cas éliminatoire afin de ne pas vérifier tous les ensembles possibles... (ex: en n'utilisant le nombre de 1 sur une ligne et sur une colonne) mais je me demande s'il n'y a pas une autre méthode...

Avez-vous des idées ?

Merci !

A+
Cédric.

[souviron34]

Déjà, soit je n'ai pas compris ton problème, soit dans ton 2ième exemple je compte 6 et non pas 9..

Ensuite, j'avoue être perplexe quand je lis :

Je cherche à détecter dans une matrice binaire le groupement maximum de valeur à 1 formant un rectangle si regroupé.
J'entend par maximum, qu'il contient le plus de 1 possible.
...
je teste tous les ensembles possibles

Tu cherches le plus grand rectangle ou bien les combinaisons ????

[kwariz]

Salut,

c'est vrai que la formulation n'est pas très claire ...
Je comprends le problème comme la recherche d'un motif M sur les colonnes en maximisant le produit (nombre de 1 de M) fois (nombre de colonnes possédant ce motif), la contrainte étant que le motif est composé d'un nombre consécutif n de 1 entouré de 0. Il n'y a qu'une recherche de motif sur les colonnes et non les lignes, enfin si je comprends bien.

Dans le premier exemple la solution est le motif (à lire en colonne)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
| 0
| 1
| 1
| 0

qui est matché sur 4 colonnes -> solution de taille 8=4x2

le motif

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
| 1
| 1
| 1
| 0

est matché sur 2 colonnes -> solution de taille 6=2x3

etc ...

si la matrice dispose de n lignes et m colonnes, tu auras n(n-1)/2 motifs à tester
{tu as n motifs avec un 1
(n-1) motif avec deux 1
...
n-i+1 motifs avec i 1
...
1 motif avec n 1} sur chaque colonne. Donc je dirais à priori un algo de premier jet en O(mn^2).

Pour l'implémentation en passant par des bit tricks ça pourrait améliorer les perf, mais une optimisation précoce est mère de tous les maux.

Juste une question, la matrice

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
1 0 1
0 0 0
1 0 1

a pour solution

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
1 1 -> taille 2

ou

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
1 1
1 1 -> taille 4

????

[souviron34]

Juste une question, la matrice

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
1 0 1
0 0 0
1 0 1

a pour solution

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
1 1 -> taille 2

ou

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
1 1
1 1 -> taille 4

????

ou taille 0 : moi je pense que c'est 0

il n'y a pas de "pixels" jointifs, que des points isolés.. donc pas de rectangle.

[kwariz]

ou taille 0 : moi je pense que c'est 0

il n'y a pas de "pixels" jointifs, que des points isolés.. donc pas de rectangle.

Ça dépend de ce que cbil1 a en tête ... et de sa réponse à cette question. Je suppose que ce n'est pas 0, je pense que pour lui la réponse sera 2, mais comme sa formulation est relativement vague je n'en suis pas persuadé.
Il serait intéressant de savoir dans quel contexte est faite cette recherche, pourquoi, la taille des matrices utilisées, etc ...

[souviron34]

Ça dépend de ce que cbil1 a en tête ... et de sa réponse à cette question. Je suppose que ce n'est pas 0, je pense que pour lui la réponse sera 2, mais comme sa formulation est relativement vague je n'en suis pas persuadé.

je sais pas.. Quand je lis :

Je cherche à détecter dans une matrice binaire le groupement maximum de valeur à 1 formant un rectangle si regroupé.

et ses 2 exemples, je pencherais pour vraiment un "patch" contigu de 1 formant un rectangle.. Et donc 0 dans le cas que tu présentes.

[cbil1]

Bonsoir,

Il y a deux solutions qui dépendent de la longueur des chaînes :
1 1 en colonne =
a,div.comment {font:3px}
div.comment {color:blue}
50 caractères

1 1 en ligne
a {font:3px}
div.comment {color:blue,font:3px}
47 caractères

Dans le cas d'une égalité, je donne la priorité au groupement de déclarations (ici le 2eme, 1 1 en ligne) plutôt qu'au groupement de sélecteurs.
J'ai fait plusieurs tests papier, il s'avère qu'à chaque fois l'avantage revient au groupement de déclarations.
La complexité ne devrait pas changer, mais cela apporte de l'importance en revanche au sens de parcours de la matrice.

A première vue, ca ne me semble pas évident de trouver la meilleure combinaison possible sans devoir tester un grand nombre e combinaisons.

En effet, c'est pour ça que je partais plus sur des idées d'éliminations des combinaisons.

On doit pouvoir par contre trouver une solution approchée avec des algos dynamiques. Je commencerais déjà par construire la matrice de co-occurence des attributs pour trouver les meilleurs regroupements possibles.

Merci, je vais rechercher des informations sur les algos dynamiques. Et "construire la matrice de co-occurence" me donne l'idée de travailler avec plusieurs matrices "intelligentes" plutôt qu'une seule gigantesque.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
si mat(i,j) = 1
    si ( mat(i-1,j) = 0 ET mat(i+1,j) = 0) ET (mat(i,j-1) = 0 ET mat(i,j+1) = 0)
          pixel isolé
    fin si
fin si

Ola, je vais relire ça tête reposé et avec attention, fatigué ce soir. Merci pour la proposition.
Kwariz, propose de supprimer les pixel isolés dès le début. (message du 17/03/2012 12h50)

Donc ta représentation sous forme de matrice est fausse.. :
tous les champs ne peuvent pas avoir toutes les valeurs, et toutes les valeurs ne sont pas possibles pour tous les champs..

L'information booléenne 1/0 dans la case indique si le champ utilise la valeur ou non.
Cela répond-il à la remarque ? Sinon, je n'ai pas compris pourquoi la représentation sous forme de matrice est fausse.

Il y a 3 solutions compactes possibles à ton problème :
...
Cette manière est la plus compacte, mais nécessite déjà une interprétation, et , pour garder une rétro-compatibilité, de n'ajouter des valeurs/champs qu'à la fin de la matrice (colonnes ou lignes en plus), et d'avoir un flag pour signaler l'obsolescence dans le code..

C'est en effet un peu près le raisonnement actuel que j'ai.
Pour le moment, je parse le fichier CSS et je construit :
* Un tableau de sélecteurs, qui contient sa liste de déclarations
* Un tableau de declarations, qui contient sa liste de sélecteurs
* Pour chaque objet (Selector & Declaration), j'ai prévu des flags du style "writed, used" et une méthode size() qui me retourne la taille du selecteur ou declaration en ignorant les styles déjà utilisés. (ce qui revient à additionner les 1 non utilisé de la matrice)

Ensuite, un traitement hyper long qui vérifie les combinaisons... (plusieurs heures sur le CSS de la fnac ^^) et c'est là que j'ai voulu passé par une idée "matrice" car je me suis rendu compte qu'en prenant le plus grand rectangle de "1" -sans compter les lignes/colonnes non utilisées- j'avais ma combinaison la plus optimale. Je n'ai pas présenté ce que j'avais déjà fait, car je pensais avoir suffisamment bien isolé mon problème pour le rendre indépendant du contexte.

Pour la matrice, je comptais la créer à partir de référence du type tab[int][int]{boolean} (false:0, true:1) ou tab[int][int]{int} (int: 0/1 ou somme de 1 sur la ligne, si utile).
Bien sûr, une fois la meilleur combinaison trouvée, je recréé ou recalcule la matrice pour trouver la suivante.

A noter, que je construit la matrice à partir du fichier parsé : je n'inventerai pas de couple propriété/valeur non utilisé d'une declaration.
Si on a p{ background-color: blue;} et a{color: red}, je n'aurais pas dans la matrice, les déclarations "background-color: red" et "color: blue".

en cherchant un peu sur le net en essayant de regarder quelles solutions ont déjà été mises en oeuvre pour ce genre d'optimisation je suis tombé sur un de ces optimiseurs qui explique quelles optimisations il implémente mais aussi lesquelles il n'implémente pas et pourquoi. Tu peux tout trouver sur http://www.lotterypost.com/css-compress.aspx.
Entre autre, vers la fin de la page, l'auteur déconseille les optimisations que tu essayes de mettre en oeuvre en raison du "C" de CSS

Oui, j'ai bien pris en compte la raison de C "Cascading" : j'ai conscience que cet optimisation peut "casser" la page sans retravailler un peu le CSS à la main, mais je pense que cette action manuelle est plus simple que d'optimiser tout le CSS à la main. Car les optimiseurs actuels que j'ai trouvé ne s'occupe pas vraiment de l'"erreur humaine" (genre, si tu n'as pas pensé à regrouper les sélecteurs), cette étape étant assez prise de tête voir difficile lorsque tu as pondu 1000 lignes de CSS.
Les éléments suivants nous sont en plus favorable à la limite de la "casse" graphique :
- A égalité d'optimisation, je fais/ferais (selon l'algo final) en sorte de prendre les premiers éléments du fichier
- On connaît déjà l'ordre "qui marche" (fichier parsé), rien n'empêchera de faire un outil qui liste les déplacements d'ordre pour faciliter la correction dans un second temps.

Peut-on supposer, pour la suite, que tu as implémenté les règles de simplifications syntaxiques que l'on trouve sur le site ?

Oui. Si je le fait pas personnellement, c'est que j'utiliserai un outil déjà prévu pour.

Peut-on aussi supposer que ta matrice (qui sera donc à revoir au niveau sdd) ne contient pas les cas de figure suivant
"que des 0" = une ligne ou une colonne dont tous les éléments sont des 0

Il n'y aura jamais "que des 0" sur une ligne ou colonne, car je me base sur un fichier parsé : si une declaration ou sélecteur est dans la matrice, c'est qu'elle est utilisé.
Dans le cas d'un second passage, je prévois de recréer la matrice.

"1 vraiment isolé" = un 1 qui se retrouve au croisement d'une ligne et d'une colonne qui autrement ne contiennent que des 0

J'avoue que je n'avais pas pensé à ce cas éliminatoire dès le début. Je peux faire en sorte qu'il n'y ait pas de "1 vraiment isolé" dans la matrice.

Désires-tu aussi implémenter l'optimisation "regroupement des style de police de caractères"? :

Pour le moment, j'ai l'intention d'utiliser des déclarations déjà optimisés, avant la création de la matrice. Et donc "font: bold 12px Arial;".
Je vérifierai plus tard si il peut réellement avoir un cas où il est préférable de l'avoir en séparé afin de générer des groupements.


Pour information, j'ai également pensé à ceci sur la matrice, afin de faciliter le parcours et la recherche du fameux rectangle imaginaire

• Pour chaque ligne compter le nombre de 1, garder le maximum
• Pour chaque colonne compter le nombre de 1, garder le maximum
• pour chaque case à 1, vérifiez le nombre de 1 sur la colonne (nb1Col)
  
  
  • en déduire le nombre de 1 nécessaire au minimum sur la ligne pour dépasser le maximum (min1required) si tous les nb1Col "1" sont utilisés. (de mémoire min1required = floor(nb1Col/2) )
  • Si une ligne < min1required : élimination
  • Continuer avec nb1Col-1

C'est un peu lourd, mais cela faisait partie de mes idées "éliminatoire" entre autre.

Je vous remercie sincèrement pour l'intérêt que vous portez à mon sujet d'algorithme.

Bonne soirée à tous !
A+
Cédric.

[souviron34]

Avant de réfléchir plus à ton post, un truc saute aux yeux :

tu dis :

Ola, je vais relire ça tête reposé et avec attention, fatigué ce soir. Merci pour la proposition.
Kwariz, propose de supprimer les pixel isolés dès le début. (message du 17/03/2012 12h50)

Mais après :

J'avoue que je n'avais pas pensé à ce cas éliminatoire dès le début. Je peux faire en sorte qu'il n'y ait pas de "1 vraiment isolé" dans la matrice.

qui, ou alors je n'ai rien compris, est exactement ce que je proposais - et sans doute kwarz avant moi..

[cbil1]

Bonjour Souviron34,

qui, ou alors je n'ai rien compris, est exactement ce que je proposais - et sans doute kwarz avant moi..

Autant pour moi, désolé. Je n'avais pas tres bien compris la logique des séries "mat(i,j)" hier soir, mais comme j'ai vu "pixel isolé", j'ai fait le lien avec le message de kwariz (j'ai rajouté "Kwariz, propose de supprimer..." après).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
si mat(i,j) = 1
    si ( mat(i-1,j) = 0 ET mat(i+1,j) = 0) ET (mat(i,j-1) = 0 ET mat(i,j+1) = 0)
          pixel isolé
    fin si
fin si

Je comprend donc (ce matin) que ce petit algo me permet de détecter les pixels isolés. Sauf qu'ici, l'algo montre que le pixel est isolé sur un pas de une case seulement, non ? Il faut donc que je fasse la même chose avec une boucle de parcours de la ligne/colonne. (Pas de soucis la dessus)


Merci, A+
Cédric.

[souviron34]

L'information booléenne 1/0 dans la case indique si le champ utilise la valeur ou non.
Cela répond-il à la remarque ? Sinon, je n'ai pas compris pourquoi la représentation sous forme de matrice est fausse.

Pourquoi ? c'est simple..

Tu compliques le traitement - et la modélisation, et donc la solution - inutilement..

• Quand on a une image, on n'a pas le choix, on a un rectangle, une matrice.
• Quand on fait du calcul matriciel, certaines choses sont complexes (comme dans ton problème de prendre en compte le nombre de lignes/colonnes).
• Quand on stocke des informations sur quelque chose pour lequel cette information n'a aucun sens, on perd du temps, de la place, et on augmente la complexité inutilement
• Quand on modélise quelque chose de variable (nombre de valeurs par rapport au nombre de champs) en quelque chose de fixe (matrice) on se complique la vie et on ne voit pas le vrai problème : on rend dépendant des choses qui sont indépendantes.
• Quand on a quelque chose d'adapté , on trouve une solution simple et élégante, et qui plus est souvent rapide

En conséquence, et vu le sujet que tu veux aborder, je pense et maintiens que la solution la plus adaptée est une solution dynamique. Théoriquement la solution est celle que j'ai mentionné en 2, mais si tu veux hyper-compact alors c'est la 3, mais présentée différemment de manière algorithmique / structurelle...

Non seulement c'est compact, souple, mais la solution algorithmique est beaucoup plus simple..

Au lieu d'avoir une matrice, je te propose un tableau de tableaux, ou, si tu préfères, une liste de tableaux ou un tableau de structures

Element de la liste / structure = indice A, nb, tableau d'indices B

• L'indice A correspond (au choix) à ce que dans ta matrice tu mettais en ligne/colonne.
• Le tableau d'indices B correspond à l'autre, mais ne contient que ce pour lequel A fait du sens

Tu élimines le problème des 0 et des 1 contigus ou non, et donc l'ensemble du problème de ce fil, puisque tu restes cohérent.. L'usage de la mémoire est optimisé (pas de champs inutiles), et le temps de calcul l'est aussi, de même que la taille du fichier produit..

Le fichier se présenterait donc comme :

0:2,4;val/3:1,5;val/....

et l'écriture ou la lecture serait directe...

Si tu te fabrqiues des tableaux internes de correspondance (ce qui est déjà le cas, d'après ce que j'ai compris), du style :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
tableau champ [h1, h2, h3, a, p, div.comment, etc]
 
tableau valeur (  color, font-size;, left, etc ]

tu auras ET la structure la plus compacte ET le fichier le plus compact..

Dans le cas de ton exemple, cela ne change pas ton fichier par rapport à stocker une matrice, puisque tu as une correspondance 1-1 entre paramètres et valeurs, mais de manière générale, "color" ou "left" peut être partagé par plusieurs champs... et donc, plus il y a de champs pouvant avoir les mêmes valeurs, plus on compresse....

On pourrait donc avoir un fichier comme :

0:0,6,7;blue/1:1,7;12/...

Et même (si le code suit, en transformant la structure pour contenir un tableau de structures et non pas juste un tableau d'indices) plusieurs valeurs pour des champs différents pour la même propriété :

0:0,6,7;blue/0:8,9;red/1:1,7;12/...

Là, tu manipules des choses indépendantes en te limitant à ce qui fait du sens pour chaque élément, et donc tu enlèves purement et simplement ton problème algorithmique

De plus, si besoin est, il est facile d'éviter la remarque du "C Cascading" en remplaçant les indices dans le fichier par leurs libellés.. Le plus compact tout en étant en clair. Et ça pourrait se faire en code juste via un flag général ("explicite"" ou "non").

[kwariz]

Re-,

quelques idées en passant :

1. En gardant ta matrice 0/1
Tu as les selecteurs(S) et les descriptions (D) à partir desquels tu construis ta matrice. Un 1 à la croisée d'un S et d'un D signifie que S utilise D.
Tu disposes aussi d'une fonction nettoyage qui élimine simplement toute ligne ou colonne composée uniquement de 0 et qui élimine aussi les 1 strictement isolés en émettant le code CSS associé. Dans la suite je suppose que les S sont en ligne et les D en colonne.
Il peut être intéressant de trier S et D par ordre décroissant, cela va impliquer qu'utiliser des 1 le plus en haut à gauche sera "plus efficace" dans le sens "ça factorisera les plus longues chaines". Il serait peut être bien de commencer les recherches de ce côté là.
Il manque un petit truc, tous les 1 ont le même poids dans tes rectangles. Il faudrait pondérer autrement, quelquechose comme si le 1 en position i,j est utilisé dans un rectangle alors son poids P(i,j) vaut 0 auquel on ajoute (S(i) si le rectangle fait plus d'une ligne, 0 sinon) et (D(i) si le rectangle ait plus d'une colonne, 0 sinon). Le poids du rectangle est la somme des poids le formant. Il sera proportionnel "aux caractères économisés".
Une fois le code pour un rectangle émis on mets tous ses 1 à 0, on nettoie et on recommence.
Une recherche exhaustive sera évidemment très couteuse, mais on peut imaginer plusieurs heuristiques :
A. on élimine dans un premier temps le maximum de petites optimisation (en bas à droite) jusqu'à obtenir une matrice de taille raisonnable avec "les longues chaines" que l'on peut chercher exhaustivement.
B. on fait l'inverse, on cherche à factoriser au maximum en "haut à gauche", ...

2. En faisant une incursion dans la théorie des graphes
Tu définis en fait un graphe biparti, l'ensemble des noeuds étant D union S. Tu recherches à partitionner ce graphe en un ensemble de bicliques. Tu peux calculer le coût de cet ensemble et tu cherches à minimiser ce cout.
Une représentation possible peut être ce que j'expose en 1. D'autres pistes pourraient se trouver ... que représente dans ce cas le problème de trouver l'ensemble de stables minimum partitionnant le graphe complémentaire ?

3. En faisant une incursion dans la théorie des langages
Tu cherches à réecrire du code CSS. Y a-t-il quelquechose à faire en considérant l'AST que tu construis en parsant le code et en y appliquant des règles de réécritures/simplifications ?

Je vais essayer de me prendre un peu de temps pour réfléchir à tout ça.

Petites réflexions :

En fait tu cherches à construire un compresseur de CSS.
On trouve facilement des compresseurs CSS "sans perte". Quelquepart tu cherches à en construire un "avec perte", car les factorisations que tu essayes de faire peuvent amener de "petites modifications" aux résultat final. Dans cette veine on pourrait imaginer pousser le concept un poil plus loin : imagine un fichier CSS dans lequel tu trouves beaucoup de
font: 12px; et de font:11px;
On pourrait imaginer tester le "remplacement de l'un par l'autre" (ne garder que font:11px par exemple) pour augmenter le taux de compression mais en ayant "plus de perte" (un peu à la JPEG).

[souviron34]

Dans cette veine on pourrait imaginer pousser le concept un poil plus loin : imagine un fichier CSS dans lequel tu trouves beaucoup de
font: 12px; et de font:11px;
On pourrait imaginer tester le "remplacement de l'un par l'autre" (ne garder que font:11px par exemple) pour augmenter le taux de compression mais en ayant "plus de perte" (un peu à la JPEG).

Dans cette vene, le plus efficace est plutôt une compression "à la GIF" :

n*font:12px,m*font:11ps

ou même

font:n*12px,m*11px

Pour garder cependant les emplacements respectifs, "à la MPEG" serait le mieux, bien que moins efficace en terme de place

font:y*12px,x*11px,z*12px,w*11px...

[kwariz]

Dans cette vene, le plus efficace est plutôt une compression "à la GIF" :

n*font:12px,m*font:11ps

ou même

font:n*12px,m*11px

Pour garder cependant les emplacements respectifs, "à la MPEG" serait le mieux, bien que moins efficace en terme de place

font:y*12px,x*11px,z*12px,w*11px...

Il faut créer un code CSS valide, et sans vouloir faire de jeu de mots "à la JPEG" était une image
On a moins gros et suffisamment le même résultat pour que ça passe quasi inaperçu.
Mais bon ce ne sont que des remarques presque hors sujet.