[Java] classe Dictionnaire [Résolu/Fermé]

Signaler
Messages postés
21
Date d'inscription
vendredi 21 octobre 2005
Statut
Membre
Dernière intervention
7 mai 2007
-
 JulienHy -
Slt @ous

Pour le moment, je developpe un compilateur en Java (ascendant) et pour optimiser l'analyse syntaxique, je suis à la recherche d'un classe du style HashTable mais qui permet aussi de savoir si un String donné est le prefix d'une des clés du Hashtable.

(En gros : une classe 'Dictionnaire' qui stoke des String et qui permet de savoir efficacement si un String donné est un prefix d'au moin un element de la classe 'Dictionnaire')

...en fait je n'ai plus beaucoup de temp pour l'écrire moi-même
donc si quelqu'un a déja ecrit une classe similaire ca m'arrangerait qu'il me fassse signe ;)

A++

2 réponses

Messages postés
21
Date d'inscription
vendredi 21 octobre 2005
Statut
Membre
Dernière intervention
7 mai 2007
2
..pour ceux qui s'y sont interressé (du moins je l'espere)

C résolu :p :p :p
2
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 87676 internautes nous ont dit merci ce mois-ci

Messages postés
623
Date d'inscription
vendredi 26 juillet 2002
Statut
Membre
Dernière intervention
11 novembre 2012
964
Salut!

Ca devrait te convenir je pense...

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/*
 * Created on 25-avr.-2007
 * Author: HackTrack
 */

public class Dictionnaire extends HashMap<String, String> {
	private static final long serialVersionUID = -7497275099046620408L;

	public Dictionnaire() {
		super();
	}
	
	public Set get(String key){
		Set<String> results = new HashSet<String>();
		for(String entry: keySet()){
			if(entry.toUpperCase().startsWith(key.toUpperCase())){
				results.add(entry);
			}
		}
		return results;
	}
	
	public int countEntriesStartingWith(String prefix){
		return this.get(prefix).size();
	}

	public static void main(String[] args) {
		Dictionnaire dico = new Dictionnaire();
		dico.put("hello","bonjour");
		dico.put("help","aide");
		dico.put("good bye","au revoir");
		dico.put("gold","or");
		dico.put("golden","doré");
		
		String[] prefixes = {"go","gol","gold","golde","he","hell"};
		
		for(String prefix: prefixes){
		System.out.println("Entrées du dictionnaire commençant par '"+prefix+"': "+dico.countEntriesStartingWith(prefix)+ "  "+dico.get(prefix));
		}
	}

}


;-)
HackTrack
Nanda
Messages postés
21
Date d'inscription
vendredi 21 octobre 2005
Statut
Membre
Dernière intervention
7 mai 2007
2
Slt
...tout d'abord, Merci pour ta réponse

[En fait le probleme est déja résolu]

...Ici le probleme avec une solution comme celle que tu proposes
C'est qu' on doit parcourir tous les cles (donc si y'a beaucoup de cles ca risque de poser probleme). Cependant pour un compilateur, les performances des algos sont tres important => je pense qu'il est plus raisonable d'utiliser une implementation basé sur un arbre binaire

..Pour ceux que ca interesse , quelque chose du style :

import java.io.*;

public class Dico {
// Lettre à stocker
char lettre;
// Dictionnaire des suffixes
Dico suffixe;
// Dictionnaire des mots commençants par une lettre plus grande
// que 'lettre' dans l'ordre alphabétique
Dico autreLettre;

// Constructeur simple initialisant chacun des attributs d'un
// objet Dico.
private Dico(char lettre, Dico suffixe, Dico autreLettre) {
this.lettre = lettre;
this.suffixe = suffixe;
this.autreLettre = autreLettre;
}

// Constructeur récursif construisant un dictionnaire contenant
// un unique mot passé en argument
public Dico(String mot) {
if (mot == null || mot.length() == 0) {
this.lettre = '*';
this.suffixe = null;
} else {
this.lettre = mot.charAt(0);
this.suffixe = new Dico(mot.substring(1));
}
this.autreLettre = null;
}


// Méthode statique ajoutant mot au dictionnaire passé
// en second argument
public static Dico ajouter(String mot, Dico precedent) {
// Si le dictionnaire est vide construire un dictionnaire
// contenant uniquement mot.
if (precedent == null) {
return new Dico(mot);
}
// Si mot null ne pas modifier le dictionnaire
if(mot == null) {
return precedent;
}
// Si longueur du mot nulle et '*' déjà à cet endroit
// ne pas modifier le dictionnaire ('*' plus petit que
// toutes les lettres dans l'ordre < ), sinon ajouter '*'
// avant toutes les autres lettres contenu dans le dictionnaire
// précédent.
if(mot.length() == 0) {
if (precedent.lettre == '*') {
return precedent;
} else {
return new Dico('*',null,precedent);
}
}
// Si la première lettre du mot est plus petite que toutes les premières
// lettres des autres mots du dictionnaire ajouter le mot avant tous
// les autres mots.
if (precedent.lettre > mot.charAt(0)) {
Dico temp = new Dico(mot);
temp.autreLettre = precedent;
return temp;
}
// Si la première lettre du mot est plus grande que la première lettre
// du dictionnaire, ajouter le mot au dictionnaire des mots commençants
// par d'autres lettres
if (precedent.lettre < mot.charAt(0)) {
precedent.autreLettre = ajouter(mot,precedent.autreLettre);
return precedent;
}
// Si la première lettre du mot est déjà dans le dictionnaire,
// ajouter le suffie du mot au dictionnaire des suffixes de cette lettre.
precedent.suffixe = ajouter(mot.substring(1),precedent.suffixe);
return precedent;
}

// Méthode de recherche du mot dans le dictionnaire.
public boolean rechercher(String mot) {
// Si le mot ou le dictionnaire sont vide retourner faux
if (mot == null) {
return false;
}
// Si la longueur du mot est nulle, retourner vrai si
// la lettre courante est '*', sinon retourner faux.
if (mot.length() == 0){
return (lettre == '*');
}
// Si la première lettre du mot est plus petite que la
// première lettre de tous les mots du dictionnaire le
// mot n'est pas dans le dictionnaire.
if (lettre > mot.charAt(0)) {
return false;
}
// Si la première lettre du mot est plus grande que la lettre courante,
// rechercher le mot dans le dictionnaire des mots commençants par une autre lettre
if (lettre < mot.charAt(0)) {
return autreLettre != null ? autreLettre.rechercher(mot) : false;
}
// Si la première lettre du mot est la lettre courante, rechercher le suffixe du mot
// dans le dictionnaire.
return suffixe.rechercher(mot.substring(1));
}


// Méthode de recherche du mot dans le dictionnaire.
public Dico prefixSearch(String mot) {
// Si le mot ou le dictionnaire sont vide retourner faux
if (mot == null) {
return null;
}
// Si la longueur du mot est nulle, retourner vrai si
// la lettre courante est '*', sinon retourner faux.
if (mot.length() == 0){
return this;
}
// Si la première lettre du mot est plus petite que la
// première lettre de tous les mots du dictionnaire le
// mot n'est pas dans le dictionnaire.
if (lettre > mot.charAt(0)) {
return null;
}
// Si la première lettre du mot est plus grande que la lettre courante,
// rechercher le mot dans le dictionnaire des mots commençants par une autre lettre
if (lettre < mot.charAt(0)) {
return autreLettre != null ? autreLettre.prefixSearch(mot) : null;
}
// Si la première lettre du mot est la lettre courante, rechercher le suffixe du mot
// dans le dictionnaire.
return suffixe.prefixSearch(mot.substring(1));
}


// Méthode utilisée par println() pour afficher le dictionnaire.
// Appelle l'autre méthode toString avec un suffixe vide.
public String toString(){
return this.toString("");
}


// Méthode utilisée pour afficher le dictionnaire.
public String toString(String prefix){
String tmp = "";
if (lettre == '*'){
// Si '*' est la lettre courante le préfixe est un mot du dictionnaire,
// le stocker pour l'affichage suivi du caractère '\n' (retour à la ligne).
tmp = prefix + "\n";
} else {
// Sinon ajouter la lettre courante au préfixe pour afficher le dictionnaire des
// suffixes.
tmp = suffixe.toString(prefix+lettre);
}
// Si le dictionnaire des mots commençants par une autre lettre n'est pas vide
// l'afficher.
if(autreLettre != null) {
tmp += autreLettre.toString(prefix);
}
return tmp;
}
}

pour avoir le prefixe il suffit de modifier 2 ou trois lignes de la méthode rechercher() .
Le temp de calcul (pour un prefix de taille N) doit etre un petit peu plus que le temp qu'il faut pour comparer N caracteres !

...si g bien compris l'algo :)

<Nanda>
> Nanda
Messages postés
21
Date d'inscription
vendredi 21 octobre 2005
Statut
Membre
Dernière intervention
7 mai 2007

bonour
je suis tres interesse par ce petit projet j ai besoin d un dictionnaire en java pour le deposer comme un projet de fin de semestre
et j ai pas le temps pour le faire svp s il est possible vous m envoyez tte les classes de ce dictionnaire ansi la classe main
merci m_oud_swing@hotmail.com



merci d avance
Bonjour,

Quelqu'un a-t-il encore le projet en entier ?

merci d'avance