Discussion :

[yarf]

Bonjour,

en essayant d'insérer des n-grammes dans une ArrayList<int[]>, je me retrouve avec un doublon deux éléments plus loin. Un extrait du résultat :

Code :

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

1
2
3
4
5
6
7
8
9
10
1476	3384	2804	1.0
1477	79	323	0.03515625
1477	79	990	1.0
1477	79	323	0.9609375
1477	990	1630	0.23828125
1477	990	1080	1.0
1477	990	1630	0.7578125
1477	1700	4244	0.88671875
1477	1700	388	1.0
1477	1700	4244	0.109375

En effectuant des tests sur un quelconque doublon observé, il s'avère qu'il n'est bien inséré qu'une seule fois (le programme ne passe qu'une seule fois dans le bloc d'insertion pour cet élément).

Ci-dessous la partie critique du code :

Code :

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
if (found){
	//modify the corresponding value
	double value = ngramcounts.get(ind);
	value += Math.pow(2, -d);
	ngramcounts.set(ind, value);
}
else if (ind == -1){
	//insert the new ngram at the end of the list 
	ngramlist.add(ngram1);
	ngramcounts.add(Math.pow(2, -d));
}
else{
	//insert the new ngram at position ind
	ngramlist.add(ind, ngram1);
	ngramcounts.add(ind, Math.pow(2, -d));
}

Quelqu'un peut-il m'aider ?

[CyberChouan]

Ton message manque d'informations...

- Dans ton tableau, quelle doit être la "clé" (l'élément qui ne doit jamais apparaître en double). Ou plus simplement, que veux-tu faire exactement? Quel est ton algorithme?

- Ensuite, tu donnes vraiment peu de sources... comment est créé le booléen "found"? le problème vient peut-être de là...

[yarf]

Dans ton tableau, quelle doit être la "clé" (l'élément qui ne doit jamais apparaître en double). Ou plus simplement, que veux-tu faire exactement? Quel est ton algorithme?

Pour l'exemple que j'ai donné, ce sont des trigrammes qui sont considérés. Donc les trigrammes (1477, 79, 323), (1477, 990, 1630) et (1477, 1700, 4244) sont en double.

comment est créé le booléen "found"?

Le n-gramme ngram1 est recherché dans ngramlist qui contient environ 10000 éléments. S'il est trouvé la valeur de found est vraie, sinon elle est fausse. La première condition indique donc que le n-gramme ngram1 a été trouvé et qu'il faut modifier la valeur qui lui est associée dans ngramcounts. La deuxième condition indique que le n-gramme n'a pas été trouvé et qu'aucun indice n'a été trouvé pour son insertion dans ngramlist... ce qui signifie qu'il est plus grand que le dernier élément de ngramlist (la liste est ordonnée) et qu'il faut l'insérer à la fin. Enfin la dernière condition indique que le n-gramme n'a pas été trouvé et qu'il faut l'insérer à l'indice ind. Et c'est là que se trouve le problème : le n-gramme est inséré deux fois.

Comme je l'ai dit dans mon premier post, j'ai testé pour un élément qui avait été inséré deux fois, si on entrait deux fois dans le troisième bloc et il n'est mentionné qu'une seule fois. C'est le seul endroit où il y a une insertion. Encore pire : en regardant les éléments autour de l'indice conserné, l'ordre est bien respecté, c'est à dire que le bon indice est trouvé.

[lechewal]

Es tu sur que l'ArrayList est la collection adaptée à ce que tu veux faire ?

[yarf]

Non, quelles alternatives me conseilles-tu ?

[Rayndell]

En utilisant une HashMap, tu éviteras automatiquement les doublons. Quels sont les chiffres le plus à droite ?

[lechewal]

Oui hashmap

ou si tu n'as pas besoin de notion d'ordre, hashset

[yarf]

Merci je vais essayer.

Quels sont les chiffres le plus à droite ?

Ils correspondent en gros à un nombre d'occurences pondéré. Veux-tu une réponse détaillée ?

[benben02]

comment fais - tu pour determiner la valeur de la variable "found" ?

comment fait tu la comparaison ? travailles-tu avec des objets ?

donne nous le code

[mhamedbj]

au lieu de faire un ArrayList, fait un nouvel objet dans lequel tu vas redefinir la methode equels et hashset !

[yarf]

Bonjour,

j'ai essayé avec HashMap mais ça bouffe vraiment beaucoup de mémoire... j'ai un java heap space pour une mémoire vive d'1 giga.

au lieu de faire un ArrayList, fait un nouvel objet dans lequel tu vas redefinir la methode equels et hashset !

Tu veux dire une classe qui extend HashSet ? Je veux bien essayer mais cela bouffera de la mémoire aussi...

comment fais - tu pour determiner la valeur de la variable "found" ?

avec une dichotomie sur la liste des n-grammes.

donne nous le code

je mets la fonction concernée, elle fait partie d'une classe parce que c'est du java mais je ne travaille pas vraiment avec des objets, enfin si puisque j'utilise les classes ArrayList, Double, etc. mais je n'ai pas de classe Ngram par exemple, parce que j'ai peur que cela ralentisse le processus (le travail est sensé porter sur des données plus importantes)

Code :

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
void applySkipping(int n){
	//load the ngrams
	String [] tab = load(ngramsfile);
	List<int[]> ngramlist = new ArrayList<int[]>();  //list of ngrams
	List<Double> ngramcounts = new ArrayList<Double>();  //list of corresponding values
	for(int i = 0; i < tab.length; i++){
		String [] tab2 = tab[i].split(SEP);
		int [] ngram = new int[n];
		for(int j = 0; j < n; j++) ngram[j] = Integer.parseInt(tab2[j]);
		ngramlist.add(ngram);
		ngramcounts.add(Double.parseDouble(tab2[n]));
	}
 
	for(int i = 0; i < corpus.length - n; i++){
		for(int j = i + n; j < Math.min(i + n + 10, corpus.length); j++){
			//search w_i w_i+1 w_j in the list of ngrams		
			int [] ngram1 = new int[n];
			for(int k = 0; k < n - 1; k++) ngram1[k] = corpus[i + k];
			ngram1[n - 1] = corpus[j];
			int d = j - (i + n - 1);
 
			//binary search
			int lb = 0, ub = ngramlist.size() - 1, ind = -1;
			boolean found = false;
			while (ub - lb > 10 && !found){
				int r = (int) (Math.random() * (ub - lb) + lb);
				int [] ngram2 = ngramlist.get(r);
				if (pos(ngram1, ngram2) == -1) ub = r;
				else if (pos(ngram1, ngram2) == 1) lb = r;
				else{
					found = true;
					ind = r;
				}
			}
			if (!found){
				for(int k = lb; k <= ub && ind == -1; k++){
					int [] ngram2 = ngramlist.get(k);
					if (pos(ngram1, ngram2) == -1) ind = k;
					else if (pos(ngram1, ngram2) == 0){
						found = true;
						ind = k;
					}
				}
			}
 
			if (found){
				//add the 2^-d value
				double value = ngramcounts.get(ind);
				value += Math.pow(2, -d);
				ngramcounts.set(ind, value);
			}
			else if (ind == -1){
				//add the new ngram at the end of the list 
				ngramlist.add(ngram1);
				ngramcounts.add(Math.pow(2, -d));
			}
			else{
				//insert the new ngram at position ind
				ngramlist.add(ind, ngram1);
				ngramcounts.add(ind, Math.pow(2, -d));
			}
		}
	}
}

avec HashMap c'est plus simple, mais ça ne termine pas (java heap space) donc je ne sais pas si ça marche...

Code :

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
30
void applySkipping(int n){
	//load the ngrams
	String [] tab = load(ngramsfile);
	Map<int[], Double> ngrams = new HashMap<int[], Double>();
	for(int i = 0; i < tab.length; i++){
		String [] tab2 = tab[i].split(SEP);
		int [] ngram = new int[n];
		for(int j = 0; j < n; j++) ngram[j] = Integer.parseInt(tab2[j]);
		ngrams.put(ngram, Double.parseDouble(tab2[n]));
	}
 
	for(int i = 0; i < corpus.length - n; i++){
		for(int j = i + n; j < Math.min(i + n + 8, corpus.length); j++){
			//search w_i w_i+1 w_j in the list of ngrams
			int [] ngram1 = new int[n];
			for(int k = 0; k < n - 1; k++) ngram1[k] = corpus[i + k];
			ngram1[n - 1] = corpus[j];
			int d = j - (i + n - 1);
 
			Double value = ngrams.get(ngram1);
			if (value == null){
				ngrams.put(ngram1, new Double(Math.pow(2, -d)));
			}
			else{
				//add the 2^-d value
				ngrams.put(ngram1, new Double(value.doubleValue() + Math.pow(2, -d)));
			}
		}
	}
}

Le corpus est simplement un tableau d'entier.

Honnêtement, ça m'a un peu rebuté et je suis en train de tester en c++ parallèlement...

[mhamedbj]

au contraire une class ngrame sera bénéfique!!
voila comment j'imagine la chose:
une classe ListeNgrame qui implémente une methode private pour la recherche rapide des éléments (les éléments sont des objets ngrame), tu utilise cette methode dans le redefinition de le methode equals, tu implements aussi une methodes de tri rapide (Batcher par ex) pour situer un nouvel elements dans son emplacement.
plus tu fais des objets avec des méthodes spécifique plus ton exécution est rapides, peut importe le nombre d'objets que tu crée

[yarf]

Bonjour,

tu penses à une classe qui implémente l'interface List (comme ça à brûle-pourpoint ça me paraît beaucoup de travail...) ou bien une classe qui hérite d'une classe comme ArrayList ou Vector, ... ?