Discussion :

[Geno312]

Bonjour,

Voici ma situation: Je cherche à comparer un fichier binaire qui est divisé en catégorie. Ces catégories sont visibles grâce aux premiers bits. Par exemple,
0000 - appartient à la catégorie 00 et a la propriété 00
0001 - appartient à la catégorie 00 et a la propriété 01
0110 - appartient à la catégorie 01 et a la propriété 10
0101 - appartient à la catégorie 01 et a la propriété 01
0111 - appartient à la catégorie 01 et a la propriété 11
(Le nombre de bits dans une catérogorie et le nombre de bits dans une propriété sont les mêmes.)
On veut donc trouver les cas similaires entre les propriétes et les catégories.
Dans ce cas ci, on aurait 0001 et 0101 qui sont similaires ce qui fait un % de similitude de 1/3 soit 33%.
Je dois comparer ensuite ce taux de % avec un paramètre pour déterminer si le taux est assez significatif pour nous. Si c'est le cas alors on mémorise ce cas de similitude pour éventuellement l'afficher. Bien entendu il peut y avoir plusieurs catégories qui ont différentes propriétes. Il faut donc toutes les comparer les une et les autres sans répéter, bien entendu, la même combinaison(exemple la combinaison 2,1 est la même chose que la combinaison 1,2).

Une idée?

[souviron34]

Une idée?

et la tienne ??

ici on ne fait pas les choses à ta place. On t'aide si tu as un problème..

Poste tes idées, et on avisera...

[Geno312]

J'ai très bien mon idée la dessus mais elle n'est pas assez performante.

Merci de me rappeler que vous ne faites pas les choses à ma place je le sais très bien.........

Pour en revenir à ce que je cherche, je prends le premier élément binaire et je la décortique pour trouver la catégorie et sa propriété pour ensutie l'ajouter à mon tableau de valeurs courantes. Ensuite, je le compare avec le second élément binaire. Si le second élément est de la même catégorie alors j'ajoute sa propriété à mon tableau de valeurs courantes sinon je regarde si la propriété se trouve dans mon tableau de valeurs courantes. Je continue ainsi de suite jusqu'à temps que la catégorie change. Je fais donc mon calcul de similitudes pour déterminer si je retiens les cas de similitudes ou non. Je passe ensuite à la prochaine catégorie pour effectuer le même traitement. Une fois rendu à la fin de mon fichier, je reprends le même processus mais cette fois-ci en partant avec la seconde catégorie de mon fichier.

[pseudocode]

Bonsoir,

J'ai pas bien vu le rapport entre le "probleme" du post 1 et la "solution" du post 3.

Au vu de l'ennoncé du probleme, je pensais a un calcul de matrice de covariance catégorie/propriété, mais c'est peut-etre pas ca...

[Geno312]

En gros ce que j'essaie de faire s'est de trouver les cas de similitudes dans un CSS afin de le simplifier.

Une façon que j'ai trouvé s'est de créer un dictionnaire des classes et des attributs donc 2 tableaux. Ensuite, je créer un fichier binaire en fonction de l'index de ceux-ci. Par exemple si ma première classe a la position 0 dans mon tableau de classes et qu'elle a comme attribut l'élément 0 et l'élément 1 de mon tableau d'attributs tout en sachant que j'ai 3 classes et 3 attributs au total alors ca veut dire que ma première classe est représentée comme suit:
00|00 = 0000
00|01 = 0001

S'il y avait eu disons un total de 4 classes et 8 attributs alors ma première classe aurait été représentée comme suit:
000|0000 = 0000000
000|0001 = 0000001

Ensuite, il ne reste plus qu'à trouver les cas de similitudes entre les différentes classes et de les afficher d'où vient mon algorithme à mon second post mais comme j'ai mentionné, il n'est pas assez performant. (Je fais le tout en java.)

[pseudocode]

Ah... c'est plutot la matrice de cooccurence alors. On incremente de "1" a chaque fois qu'on rencontre un couple (categorie,propriété). Visiblement dans ton cas, on aura jamais une case supérieure a "1" (si j'ai bien compris).

Code :

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

1
2
3
4
5
6
7
8
9
10
 
         propriété
cat. | 00| 01| 10| 11|
     |---------------|
  00 | 1 | 1 |   |   | 
     |---------------|
  01 |   | 1 | 1 |   | 
     |---------------|
  10 | 1 |   | 1 |   | 
     |---------------|

Après c'est moins clair... Si tu cherches la propriété qui revient le plus souvent, il faut chercher la colonne qui a la plus grande somme. Si tu cherches la combinaison des "n" propriétés qui reviennent le plus souvent il faut regarder du coté des algo de "covering set"...

[Geno312]

Hihi Je vais essayer d'être plus clair.

Bon supposons que j'ai le fichier css suivant :

.titre {
width: 500px;
height: 200px;
}

.titre2 {
backgound-color: #000000;
width: 500px;
height: 200px;
}

.titre3 {
font-weight: bold;
backgound-color: #000000;
}

On voit qu'il y a de la redondance dans les différentes classes. Si je compare titre à titre2 on voit q'il y a 2/3 de similitude soit 66%, si je compare titre à titre3 on voit qu'il y a 0 similitude et si je compare titre2 à titre 3 on voit qu'il y a 1/3 de similitude soit 33%.

Donc ce que je pensais faire était d'analyser mon fichier css afin de créer une sorte de dictionnaire de mes classes et mes attributs. Par exemple on aurait dans un premier tableau toutes mes classes
0: titre
1: titre1
2: titre2

et dans un autre tableau on aurait toutes mes propriétés ainsi que leurs valeurs (font-weight: bold; n'est pas la même chose que font-weight: xyz

0: width: 500px;
1: height: 200px;
2: backgound-color: #000000;
3: font-weight: bold;

En trouvant une propriété, on crérait en parallèle un fichier binaire. Le nombre binaire serait la combinaison entre l'index de la classe de notre tableau et l'index de l'attribut de son tableau respectif. Également, puisqu'il y a un total de 3 classes on écrirait notre première partie de notre nombre binaire avec 2 chiffres et pour ce qui est des attributs, vu qu'il y en a 4 dans cet exemple on écrirait notre seconde partie de notre nombre binaire avec 2 chiffres binaire (puisque la valeur maximale est de 11 qui représente 3).

On aurait donc comme fichier:
0000
0001
0110
0100
0101
1011(10 est la classe et 11 est l'attribut)
1010

Ensuite, il faut trouver les cas de similitudes comme j'ai indiqué un peu plus haut. Par exemple si je compare la classe titre et titre1 on aurait comme cas de similitude :
0000 = 0100 et 0001 = 0101

[pseudocode]

c'est clair.

Ce n'est peut-etre pas la structure de données optimale pour ton probleme, mais nous verrons cela plus tard.

Maitenant quel est la forme du résultat que tu souhaites obtenir: un tableau, une liste, des couples, une fonction, ... ?

[Geno312]

La manière que je pensais faire était de sortir un rapport sortant les attributs de la première classe qui sont similaires aux autres classes et ensuite de sortir les attributs de ces autres classes et ainsi de suite. Exemple:

Les attributs de cette classe se retrouvent dans d'autres classes:
.titre {
width: 500px;
height: 200px;
}
Voici la liste :
.titre2 {
width: 500px;
height: 200px;
}

Les attributs de cette classe se retrouvent dans d'autres classes:
.titre2 {
backgound-color: #000000;
}
Voici la liste:
.titre3 {
backgound-color: #000000;
}

Enfin vous voyez le genre de représentation (Si vous avez d'autres suggestions qui pourrait être plus simple à comprendre ne vous gênez pas ! ).

Bien entendu, comme j'ai écrit un peu plus haut, le résultat va dépendre de notre % de similitude entre les classes. Celui-ci sera comparé avec un % minimum que l'on va passer comme argument de départ à notre programme. Donc si notre % de similitude minimal est de 80% et que l'on a une similitude de 50% alors elle ne sera pas dans notre résultat.

[pseudocode]

Comme je l'ai dit plus haut, je pense qu'une matrice d'occurence est un bon debut:

Code :

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

1
2
3
4
5
6
7
8
9
10
 
         propriété
class| p0| p1| p2| p3|
     |---------------|
  c0 | 1 | 1 |   |   | 
     |---------------|
  c1 |   | 1 | 1 |   | 
     |---------------|
  c2 | 1 |   | 1 |   | 
     |---------------|

avec:
p0=width:500px, p1=height:200px, p2=backgound-color:#000000, ...
c0=.titre, c1=.titre2, c2=.titre3, ...

Ensuite il va falloir faire des choix: performance versus completude.
- Si tu cherches a avoir tous les regroupements possibles, tu n'a pas d'autre choix que de comparer les lignes 2 a 2 comme tu l'as déja fait.
- Si tu recherches la performance, tu peux te concentrer sur les lignes qui ont un fort taux de remplissage (somme horizontale)

Dans les 2 cas, puisque tu as un seuil % minimum, tu peux eviter de comparer les lignes qui ont trop peu de propriétés pour atteindre le seuil (meme dans le meilleur des cas).

[Geno312]

Car la solution de comparaison que j'ai trouvée se fait avec 4 boucles donc O(n^4) ce qui est beaucoup...

[pseudocode]

Car la solution de comparaison que j'ai trouvée se fait avec 4 boucles donc O(n^4) ce qui est beaucoup...

. oui ca parrait beaucoup.

Si "n" est le nombre de ligne de la matrice (= nb de classes), alors il faut comparer la 1ere ligne avec les n-1 suivantes, puis la 2nd avec les n-2 suivantes, ...

soit NmbComparaisonLigne= (n-1)+(n-2)+... = n*(n-1)/2

Pour chaque ligne on doit comparer les "p" colonnes (=nb de propriétés), donc la complexité totale est p*n*(n-1)/2 = O(p.n²)

Je ne vois pas ou est la 4eme boucle...

[Geno312]

Comment peut-on créer cette matrice dynamique au niveau des colonnes je veux dire puisque celle-ci sera créer et remplie au fur et à mesure que j'analyse mon fichier.

Le n^4 est lorsque je change mon fichier en binaire comme j'avais expliqué un peu plus haut mais il est surement possible de le faire en "moins de temps".

[pseudocode]

Comment peut-on créer cette matrice dynamique au niveau des colonnes je veux dire puisque celle-ci sera créer et remplie au fur et à mesure que j'analyse mon fichier.

Ca dépend du langage... En java tu peux utiliser des structures dynamiques comme Map et Collection:

Code java :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
public class TestCss {
 
	private class Category { /* ... */ }
	private class Property { /* ... */ }
	private Map<Category, Collection<Property>> matrix;
 
	public TestCss() {
		this.matrix = new HashMap<Category, Collection<Property>>();
	}
 
	private void addElement(Category c, Property p) {
		if (!matrix.containsKey(c))
			matrix.put(c, new HashSet<Property>());
 
		matrix.get(c).add(p);
	}
 
	private double similarity(Category c1, Category c2) {
		Collection<Property> allPropertiesOfC1 = matrix.get(c1); 
		Collection<Property> allPropertiesOfC2 = matrix.get(c2);
 
		int common=0;
		for(Property p1:allPropertiesOfC1)
			if (allPropertiesOfC2.contains(p1)) common++;
 
		return (double)common/allPropertiesOfC1.size();
	}
...

[souviron34]

Ca dépend du langage... En java tu peux utiliser des structure dynamiques comme Map et Collection:

et en C il y a de l'allocation dynamique

[Geno312]

Ça je ne savais pas ! Merci !

[Geno312]

Quand je regarde le code, ce n'est pas plutôt O(n^3) ?

Puisque si j'ai 3 catégories(c1, c2, c3), je dois comparer c1 avec c2, c1 avec c3 et c2 avec c3 donc 2 boucles for (O(n^2)) et à chaque fois que je compare 2 catégories, je regarde leurs propriétés.

n^2 * n = n^3

À moins que je le vois de la mauvaise façon...

[pseudocode]

Quand je regarde le code, ce n'est pas plutôt O(n^3) ?

Puisque si j'ai 3 catégories(c1, c2, c3), je dois comparer c1 avec c2, c1 avec c3 et c2 avec c3 donc 2 boucles for (O(n^2)) et à chaque fois que je compare 2 catégories, je regarde leurs propriétés.

n^2 * n = n^3

À moins que je le vois de la mauvaise façon...

Pourquoi est-ce qu'il y aurait autant de propriétés que de catégories ?

[Geno312]

.titre { ----> Catégorie1
width: 500px; ----> Propriété1
height: 200px; ----> Propriété2
}

.titre2 { ----> Catégorie2
backgound-color: #000000; ----> Propriété3
width: 500px; ----> Propriété1
height: 200px; ----> Propriété2
}

.titre3 { ----> Catégorie3
font-weight: bold; ----> Propriété4
backgound-color: #000000; ----> Propriété3
}

Comme tu peux le voir, une propriété peut se répéter d'où vient les similitudes. Dans cet exemple on peut voir qu'il y a 3 catégories et 4 propriétés.

De plus, ta matrice le démontre clairement:

Code :

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

1
2
3
4
5
6
7
8
9
10
 
         propriété
cat. | 00| 01| 10| 11|
     |---------------|
  00 | 1 | 1 |   |   | 
     |---------------|
  01 |   | 1 | 1 |   | 
     |---------------|
  10 | 1 |   | 1 |   | 
     |---------------|

[pseudocode]

Comme tu peux le voir, une propriété peut se répéter d'où vient les similitudes. Dans cet exemple on peut voir qu'il y a 3 catégories et 4 propriétés.

Donc il n'y a pas autant de catégories (n) que de propriétés (p). La complexité est donc O(p*n²) et pas O(n^3).