multitudinous v1.0.0
Projet ALGAV Master STL @UPMC 2017-2018
Author : Kaan YAGCI - 3201099
1. Présentation
1.1 Structure 1 : Patricia - Tries
RAPPEL
Trie : Représentation arborescente d'un ensemble de clés en évitant de répeter les préfixes communs.
- prem(cle) : Renvoie la première caractère de la clé.
- reste(cle) : Renvoie la clé privée de son premier caractère
- car(e,i) : Renvoie la i-ème caractère de la clé
- lgueur(cle) : Renvoie le nombre de caractères de la clé.
Question 1.1
Dans le vrai vie, on dit qu'un mot est fini quand il ne reste plus de caractères. Pour cela je choisi le caractère numéro 0 parmi les 128 caractères ASCII pour indiquer la fin d'un mot. Ce caractère est le caractère NUL (https://fr.wikipedia.org/wiki/American_Standard_Code_for_Information_Interchange)
Question 1.2
Pour la réalisation de la structure Patricia-tries j'ai créé et utilisé les classes suivantes :
TODO :
- Insert file structure
Noeud : La classe qui représente le structure du noeud. Elle contient un objet de type Noeud qui peut être undefined qui représente le noeud père s'il y en a un, une chaîne de caractères appelé cle qui représente la clé du noeud et une liste des objets de type Noeud qui représente les fils du noeud (les sous arbres dans le cas le noeud est la racine d'une arbre de recherche) et les primitives d'un structure noeud. (Dans le cas d'une feuille la liste des fils sont vide). Ces primitives sont les suivants : + constructor(cle,fils,pere) : La fonction permet d'identifier un objet Noeud. Il prend une chaîne de caractères cle qui représente la clé du noeud, une liste des objets de type Noeuds qui représente la liste des fils du noeud et un objet de type Noeud qui peut être undefined dans le cas du neoud est une racine qui représente le père du noeud.
```typescript constructor(cle : string, fils : Array<Noeud>, pere? : Noeud) { this.cle = cle; this.fils = fils; this.pere = pere; } ``` + **getPere()** : La fonction qui retourne le père du noeud et undefined si le noeud est le père d'un arbre. ` getPere() : void -> Noeud|undefined ` ```typescript public getPere(): Noeud|undefined { return this.pere; } ``` + **getCle()** : La fonction retourne la clé du noeud. ` getCle(): void -> string` ```typescript public getCle(): string { return this.cle; } ``` + **getFils()** : La fonction retourn la liste des fils du noeud. ` getFils(): void -> Array<Noeud> ` ```typescript public getFils(): Array<Noeud> { return this.fils; } ``` + **setPere(p)** : La fonction permet de reinitialiser le père du noeud avec l'objet de type Noeud passé en paramètre. ` setPere(p): Noeud|undefined -> Noeud|undefined ` ```typescript public setPere(p : Noeud|undefined): Noeud|undefined { return this.pere = p; } ``` + **setCle(c)** : La fonction permet de reinitialiser la clé du noeud avec la clé passée en paramètres. ` setCle(c): string -> string ` ```typescript public setCle(c : string): string { return this.cle = c; } ``` + **setFils(f)** : La fonction permet de reinitialiser la liste des fils du noeud avec la nouvelle liste f passée en paramètres. ` setFils(f): Array<Noeud> -> Array<Noeud> ` ```typescript public setFils(f : Array<Noeud>): Array<Noeud> { return this.fils = f; } ``` + **prem()** : La fonction renvoie la première caractère de la clé du noeud. ` prem(): void -> string ` ```typescript public prem(): string { return this.cle.split('')[0]; } ``` + **reste()** : La fonction renvoie la clé privée de son premier caractère. ```typescript public reste(): string { return this.cle.slice(1); } ``` + **car(i)** : La fonction renvoie la ième caractère de la clé. ` car(i): number -> string ` ```typescript public car(i : number): string { return this.cle.split('')[i]; } ``` + **lgueur()** : La fonction renvoie le nombre de caractères de la clé. ` lgueur(): void -> number` ```typescript public lgueur(): number { return this.cle.length; } ``` + **compare(n)** : La fonction permet de comparer le noeud avec le noeud passé en paramètre. Elle compare la clé du noeud actuelle avec la clé du noeud passé en paramètres. ` compare(n): Noeud -> number ` ```typescript public compare(n : Noeud): number { if (this.cle < n.getCle()) { return -1; } if (this.cle > n.getCle()) { return 1; } return 0; } ``` + **update()** : La fonction permet de mettre à jour la liste des noeud fils du noeud. Elle trie la liste dans l'ordre l'alphabétique. ` update(): void -> Array<Noeud> ` ```typescript public update(): Array<Noeud> { return this.fils = this.fils .sort( (a: Noeud, b: Noeud) => a.compare(b) ); } ``` + **add(mot)** : La fonction permet d'ajouter le mot passé en paramètres dans le noeud. ` add(mot): string -> boolean ` ```typescript public add(mot : string) : boolean { /* La constante encommun contiens les caractères en commun au début du mot de la clé et le mot à insérer */ const encommun = match2Strings(this.cle,mot); if (encommun.length > 0) { if (encommun === this.cle) { /* Si la clé est un préfixe du mot à insérer */ const reste = mot.slice(encommun.length); if (reste.length === 0) { console.log('Le mot à ajouter est la même que la clé.'); if (this.fils.length > 0) { console.log("On check s'il contient la feuille indiquant la fin du mot"); for (var f of this.fils) { if (f.getCle() === '\0') { console.log('Le mot ' + mot + 'existe déjà dans l\'arbre!!!'); return false; } } } console.log("La feuille indiquant la fin du mot a été ajouté à la liste des fils"); this.fils.push(new Noeud('\0',new Array<Noeud>(),this)); return true; } for (var f of this.fils) { if (match2Strings(f.getCle(),reste).length > 0) { /* Si on trouve le noeud à insérer */ return f.add(reste); } } /* Si on n'a pas trouvé un noeud avec caractère en commun */ /* On crée une feuille avec le reste des caractères */ const faj = new Noeud(reste,new Array<Noeud>(),this); /* On regarde d'abord s'il y a déjà des fils dans la liste des fils */ if (this.fils.length === 0) { /* S'il y en a aucun c'est à dire qu'on essaie d'ajouter à une feuille */ /* Donc on ajoute une feuille pour indiquer la fin du mot dans la liste des fils */ this.fils.push(new Noeud("\0",new Array<Noeud>(),this)); } /* On l'ajoute à la liste des fils */ this.fils.push(faj); /* On met à jour la liste des fils */ this.update(); return true; } if (encommun.length < this.cle.length) { const aux = this.cle.slice(encommun.length); const nn = new Noeud(aux,this.fils,this); this.fils = new Array<Noeud>(); this.cle = encommun; this.fils.push(new Noeud(mot.slice(encommun.length),new Array<Noeud>(),this)); this.fils.push(nn); this.update(); return true; } return false; } if (this.pere !== undefined) { console.log('Le mot ' + mot + ' existe déjà dans l\'arbre'); } return false; } ``` + **isFeuille()** : La fonction permet de déterminer si le noeud est une feuille. ` isFeuille(): void -> boolean ` ```typescript public isFeuille(): boolean { return this.fils.length === 0; } ``` * **showOnConsole()** : La fonction permet d'afficher le contenu du noeud dans la console. ` showOnCOnsole() : void -> void ` ```typescript public showOnConsole(): void { console.log('Clé : ' + this.cle); if (this.isFeuille()) { console.log('Est une feuille'); } else { console.log('Fils : ' + this.fils.length + ' fils'); for (var f of this.fils) { f.showOnConsole(); } } } ```Arbre : La classe qui répresente la structure de l'arbre de recherche, en stockant un objet de type Noeud comme la racine de l'arbre et des primitives d'une stucture d'arbre de recherhe. Les primitives sont les suivants : + constructor() : La fonction permet d'identifier un objet Arbre.
```typescript constructor(racine: Noeud) { this.racine = racine; } ``` + **getRacine()** : La fonction qui renvoie la racine d'un arbre. ` getRacine(): void -> Noeud ` ```typescript public getRacine(): Noeud { return this.racine; } ``` + **setRacine(nouvelleRacine)** : La fonction permet de changer la racine de l'arbre. ` setRacine(r): Noeud -> Noeud ` ```typescript public setRacine(r: Noeud): Noeud { return this.racine = r; } ``` + **compare(a)** : La fonction permet de comparer l'arbre avec un autre objet de type Arbre. ` compare(a): void -> number ` ```typescript public compare(a: Arbre): number { return this.racine.compare(a.getRacine()); } ``` + **canAdd(mot)** : Le prédicat qui permet de tester si le mot passé en paramètre peut être ajouté dans l'arbre. ` canAdd(mot): string -> boolean ` ```typescript public canAdd(mot: string): boolean { return match2Strings(this.racine.getCle(),mot).length > 0; } ``` + **add(mot)** : La fonction permet d'ajouter le mot passé en paramètre à l'arbre. Ici nous testons quand même la possibilité d'ajout du mot dans l'arbre. ` add(mot): string -> boolean ` ```typescript public add(mot: string): boolean { if (this.canAdd(mot)) { return this.racine.add(mot); } else { return false; } } ``` + **showOnConsole()** : La fonction permet d'afficher l'arbre sur le console pour une affichage basique. ` showOnConsole(): void->void ` ```typescript public showOnConsole(): void { console.log('Racine '); this.racine.showOnConsole(); } ```PatriciaTrie : La classe qui représente la structure Patricia-tries. Elle régroupe des objets Arbre sous une liste et contient les primitives d'un structure Patricia-tries. Les primitives sont les suivants : + constructor() : La fonction qui permet de identifier un objet PatriciaTrie.
```typescript constructor() { this.noeuds = new Array<Arbre>(); } ``` + **update()** : La fonction permet de trier la liste des sous-arbres alphabétiquement. Cette fonction est privée parce qu'elle est destiné uniquement à l'usage l'interne de l'objet PatriciaTrie. ` update(): void -> Arbre[] ` ```typescript private update(): Array<Arbre> { return this.noeuds = this.noeuds.sort((a : Arbre, b : Arbre) => a. compare(b)); } ``` + **add(m)** : La fonction qui permet d'ajouter un mot dans le patricia-trie. Elle trouve le sous arbre qu'elle doit ajouter le mot (crée une s'il n'y en existe pas) et mis à jour la liste des sous arbres pour qu'elle restent triée pour pour le cas qu'il n'y en a aucun sous-arbre existant que nous pouvons ajouter le mot passé en paramètres. Cette fonction n'est pas sensible à la casse pour éviter tout futur conflit. ` add(m): string -> boolean ` ```typescript public add(m: string): boolean { const mot = m.toLowerCase(); for (var n of this.noeuds) { if (n.canAdd(mot)) { return n.add(mot); } } console.log('Le mot ' + mot + ' sera ajouté comme étant un nouveau arbre dans la liste des arbres'); this.noeuds.push(new Arbre(new Noeud(mot,new Array<Noeud>()))); return true; } ``` + **showOnConsole()** : La fonction permet qui permet d'afficher l'objet dans le console. Pour une affichage basique. ` showOnConsole(): void -> void ` ```typescript public showOnConsole(): void { console.log('Patricia trie of ' + this.noeuds.length + ' elements' ); for (var n of this.noeuds) { n.showOnConsole(); } } ```
Question 1.3
L'exemple de base défini dans l'énoncé est le suivant A quel genial professeur de dactylographie sommes nous redevables de la superbe phrase ci dessous, un modele du genre, que toute dactylo connait par coeur puisque elle fait appel a chacune des touches du clavier de la machine a ecrire ?. J'ai fais l'hypothèse que ça ne soit pas sensible à la casse pour éviter les conflits liés aux changement de code ASCII par rapport à sa casse. Donc on obtient un Patricia-tries de 16 sous arbres. Le command suivant permet d'exécuter ces tests sur la console.
npm run question131.2 Structure 2 : Tries Hybrides
RAPPEL
Trie Hybride : Une trie hybride est un arbre ternaire dont chaque noeud contient un caractère et une valeur (non vide lorsque le noeud réprésente une clé). Chaque noeud a 3 pointeurs : un lien Inf (resp. Eq, resp. Sup) vers le sous arbre dont le premier caractère est inférieur (resp. égal, resp. supérieur) à son caractère.
Question 1.4
Pour la réalisation de la structure tries hybrides j'ai crée la classe TrieHybride. C'est la classe qui contient tous les attributs et les fonctions concernant le structure tries hybrides. Ces attributs sont suivantes :
- valeur : Attribut de type entier facultatif qui représente la valeur de la racine (s'il y en a une).
valeur : number|undefined
private valeur: number|undefined;- cle : Attribut de type chaîne de caractères représente la clé de la racine.
cle: string
private cle: string;- pere : Attribut de type TrieHybride qui permet représente le père de l'arbre (s'il y en a un, undefined sinon).
pere: TrieHybride|undefined
private pere: TrieHybride|undefined; - inf : Attribut de type TrieHybride qui représente le sous-arbre Inf de l'arbre (s'il y en a un. undefined sinon).
inf : TrieHybride|undefined
private inf: TrieHybride|undefined;- eq : Attribut de type TrieHybride qui représente le sous-arbre Eq de l'arbre (s'il y en a un, undefined sinon).
eq: TrieHybride|undefined
private eq: TrieHybride|undefined;- sup : Attribut de type TrieHybride qui représente le sous-arbre Sup de l'arbre (s'il y en a un undefined sinon)
sup: TrieHybride|undefined
private sup: TrieHybride|undefined;HYPOTHESE: Tous ces attributs sont privées.
Ses fonctions sont suivants :
- constructor(cle,valeur,inf,eq,sup,pere) : Le fonction permet d'identifier un objet TrieHybride. Les paramètres cle,valeur,inf,eq,sup,pere sont tous des paramètres facultatifs représentent la clé,la valeur, le sous-arbre inf, le sous-arbre eq, le sous-arbre sup et le pere de la racine. Dans le cas de non présence d'un des paramètres, celui ci est initalisé à la valeur null.
constructor(cle?: string,
valeur?: number,
inf?: TrieHybride,
eq?: TrieHybride,
sup?: TrieHybride,
pere?: TrieHybride)
{
if (cle)
{
this.cle = cle;
}
else
{
this.cle = '\0';
}
this.valeur = valeur;
this.inf = inf;
this.eq = eq;
this.sup = sup;
this.pere = pere;
}- getValeur() : Fonction retourne la valeur de la racine de l'arbre (et undefined s'il y en a pas)
getValeur(): void -> number|undefined
public getValeur(): number|undefined {
return this.valeur;
}- getCle() : Fonction retourne la clé de la racine de l'arbre
getCle(): void -> string
public getCle(): string {
return this.cle;
}- getInf() : Fonction retourne le sous-arbre Inf de l'arbre (undefined s'il y en a pas).
getInf(): void -> TrieHybride|undefined
public getInf(): TrieHybride|undefined {
return this.inf;
}- getEq() : Fonction retourne le sous-arbre Eq de l'arbre (undefined s'il y en a pas).
getEq(): void -> TrieHybride|undefined
public getEq(): TrieHybride|undefined {
return this.eq;
}- getSup() : Fonction retourne le sous-arbre Sup de l'arbre (undefined s'il y en a pas).
getSup(): void -> TrieHybride|undefined
public getSup(): TrieHybride|undefined {
return this.sup;
}- getAllSuccessors() : Fonction retourne la liste de tous les sous-arbres.
getAllSuccessors(): void -> Array<TrieHybride|undefined>
public getAllSuccessors(): Array<TrieHybride|undefined> {
return new Array<TrieHybride|undefined>(this.inf,this.eq,this.sup);
} - getPere() : Fonction retourne le pere de l'arbre (s'il y en a, undefined sinon)
getPere(): void -> TrieHybride|undefined
public getPere(): TrieHybride|undefined {
return this.pere;
}- setValeur(valeur) : Fonction permet de changer la valeur de la racine de l'arbre.
setValeur(valeur): number|undefined -> number|undefined
public setValeur(valeur: number|undefined): number|undefined {
return this.valeur = valeur
}- setCle(cle) : Fonction permet de changer la clé de la racine de l'arbre.
setCle(cle): string -> string
public setCle(cle: string): string {
return this.cle = cle;
}- setInf(inf) : Fonction permet de changer le sous-arbre Inf de l'arbre.
setInf(inf): TrieHybride|undefined -> TrieHybride|undefined
public setInf(inf: TrieHybride|undefined): TrieHybride|undefined {
return this.inf = inf;
}- setEq(eq) : Fonction permet de changer le sous-arbre Eq de l'arbre.
setEq(eq): TrieHybride|undefined -> TrieHybride|undefined
public setEq(eq: TrieHybride|undefined): TrieHybride|undefined {
return this.eq = eq;
}- setSup(sup) : Fonction permet de changer le sous-arbre Sup de l'arbre.
setSup(sup): TrieHybride|undefined -> TrieHybride|undefined
public setSup(sup: TrieHybride|undefined): TrieHybride|undefined {
return this.sup = sup;
}- setPere(p) : Fonction permet de changer le père de la racine de l'arbre.
setPere(p): TrieHybride|undefined -> TrieHybride|undefined
public setPere(p: TrieHybride|undefined): TrieHybride|undefined {
return this.pere = p;
}- prem() : Fonction renvoie la première caractère de la clé de la racine de l'arbre.
prem(): void -> string
public prem(): string {
return this.cle.split('')[0];
}- reste() : Fonction renvoie la clé de la racine privée de son premier caractère
reste(): void -> string
public reste(): string {
return this.cle.slice(1);
}- car(i) : Fonction renvoie la ième caractère de la clé de la racine.
car(i): number -> string
public car(i : number): string {
return this.cle.split('')[i];
}- lgueur() : Fonction renvoie le nombre de caractères de la clé de la racine.
lgueur(): void -> number
public lgueur(): number {
return this.cle.length;
}- estVide() : Fonction permet de déterminer si l'arbre est vide
estVide(): void -> boolean
public estVide(): boolean {
return (this.cle === '\0') &&
(
(this.inf === undefined) ||
(this.inf.getCle() === '\0')
) &&
(
(this.eq === undefined) ||
(this.eq.getCle() === '\0')
) &&
(
(this.sup === undefined) ||
(this.sup.getCle() === '\0')
) &&
(this.valeur === undefined);
}- compare(t) : Fonction permet de comparer deux tries hybrides.
compare(t): TrieHybride -> number
public compare(t: TrieHybride): number {
if (this.cle < t.getCle())
{
return -1;
}
if (this.cle > t.getCle())
{
return 1;
}
return 0;
}- add(mot) : Fonction permet d'ajouter un mot au trie hybride.
add(mot): string -> TrieHybride
public add (mot: string, v:number): TrieHybride {
const mt = mot.split('');
var aux: TrieHybride = this;
for (var i = 0; i < mt.length; i++) {
if (i === mt.length-1) {
aux = aux.addChar(mt[i],v);
console.log('Ajout du mot ' + mot + ' est terminé!');
}
aux = aux.addChar(mt[i],undefined);
//console.log('Ajout du caractère ' + mt[i] + ' est terminé');
}
return this;
}- addChar(char) : Fonction permet d'ajouter qu'un seul caractère au trie hybride. Cette fonction est privée parce qu'elle est destiné uniquement à l'usage dans la classe.
addChar(char): string -> TrieHybride
private addChar (char: string, v: number|undefined): TrieHybride
{
if (this.estVide() === true)
{
this.cle = char;
this.valeur = v;
return this;
}
else
{
if (char.localeCompare(this.cle) < 0)
{
if (this.inf === undefined)
{
this.inf = new TrieHybride();
}
return this.inf.addChar(char,v);
}
if (char.localeCompare(this.cle) > 0)
{
if (this.sup === undefined)
{
this.sup = new TrieHybride();
}
return this.sup.addChar(char,v);
}
if (this.valeur === undefined) {
this.valeur = v;
}
if (this.eq === undefined)
{
this.eq = new TrieHybride();
}
return this.eq;
}
}Question 1.5
On insère le même phrase que la questio 1.3 appelé exemple de base. Cet insetion nous donne un trie hybride de 40 mots. Le command suivant permet d'exécuter ces tests sur la console.
npm run question152. Fonctions avancées pour chacune des structures.
Question 2.6
4. Complexités
Question 4.10
L'étude de la complexités des fonctions de la question 2.6 sont les suivants :
Les fonctions du structure Patricia Tries sont les suivants:
La fonction recherche(arbre,mot) -> booleéen de la classe ArbreFactory est le suivant :
static recherche(arbre: PatriciaTrie|TrieHybride, mot:string):boolean { return arbre.recherche(mot); }Il fait dont un simple appel à la fonction recherche du structure Patricia Tries. On étudie donc la complexité de la fonction recherhce(mot) de la classe Patricia Trie qui le suivant :
public recherche(mot: string,verbose: boolean = false): boolean { mot = mot.toLowerCase(); if (verbose) { console.log("On recherche le mot " + mot + " dans le patricia tries"); } for (var n of this.noeuds) { if (verbose) { console.log("On trouve le sous-arbre dont la clé à sa racine est un préfixe du mot " + mot); } if ( (n.racine !== undefined) && (mot.indexOf(n.racine.getCle()) === 0) ) { if (verbose) { console.log("Si on a trouvé l'arbre qu'on cherche. On lance notre recherche dessus"); } return n.recherche(mot,verbose); } } if (verbose) { console.log("Si un tel arbre n'exsiste pas alors on retourne false"); } return false; }Dans le pire des cas le fonction parcourt tous la liste des sous-arbres, et à la fin il fait un appel à la fonction recherche(mot) de la classe ArbreNoeudSimple qui est le suivant :
public recherche(mot: string, verbose: boolean = false): boolean { mot = mot.toLowerCase(); if (verbose) { console.log("On controle d'abord si le mot est vide"); } if (mot.length === 0) { if (verbose) { console.log("Le mot et vide alors on retourne true"); } return true; } else { if (verbose) { console.log("Le mot n'est pas vide. Alors on contrôle d'abord si l'arbre est vide"); } if (this.estArbreVide() === true) { if (verbose) { console.log("Si l'arbre est vide alors on retourne false"); } return false; } else { if (verbose) { console.log("Si l'arbre n'est pas vide alors on contrôle si la clé de la racine de l'arbre est un préfixe du mot"); } if ( (this.racine !== undefined) && (mot.indexOf(this.racine.getCle()) === 0) ) { if (verbose) { console.log("Si la racine de l'arbre est bien définie et que la clé de la racine de l'arbre est un préfixe du mot " + mot); console.log("On trouve les caractères du mot privé de la clé de la racine de l'arbre"); } const mreste = mot.slice(this.racine.getCle().length); if (verbose) { console.log("Les caractères du mot privé de la clé de la racine de l'arbre est " + mreste); console.log("On contrôle d'abord si cette reste est vide"); } if (mreste.length === 0) { if (verbose) { console.log("Si cette reste est vide. Alors on contrôle d'abord si c'est une feuille"); } if (this.estFeuille()) { if (verbose) { console.log("Si c'est une feuille alors on retourne true"); } return true; } else { if (verbose) { console.log("Si ce n'est pas une feuille alors on regarde s'il y a un arbre qui indique la fin du mot. C'est à dire s'il y a un arbre qui a '\0' commme la clé à sa racine"); } for (var sa of this.sousArbres.filter(s => s !== undefined)) { if ((sa !== undefined) && (sa.racine !== undefined)) { if (verbose) { console.log("La clé de la racine est " + sa.racine.getCle()); console.log("C'est la clé qu'on cherche " + (sa.racine.getCle() === "\0")); } if ((sa.racine.getCle() === "\0")) { if (verbose) { console.log("Si un tel arbre existe c'est à dire que le mot existe. Alors on retourne true"); } return true; } } } return false; } } else { for (var sae of this.sousArbres.filter(sa => sa !== undefined)) { if ( (sae !== undefined) && (sae.recherche(mreste) === true) ) { return true; } } return false; } } else { if (verbose) { console.log("Si la racine de l'arbre n'est pas définie ou la clé de la racine de l'arbre n'est pas un préfixe du mot " + mot + " on retourne false"); } return false; } } } }La fonction recherche du structure ArbreNoeudSimple a comme complexité dans le pire des cas O(2n). Qui fait la complexité de la fonction recherche précédent (de la classe PatriciaTrie) O(3n). Donc on peut dire que la complexité de la fonction recherche(arbre,mot) -> booleén du structure Patricia Tries est O(n).
La fonction ComptageMots(arbre) -> entier de la classe ArbreFactory:
static comptageMots(arbre:PatriciaTrie|TrieHybride):number { return arbre.comptageDeMots(); }Fonction fait un simple appel à la fonnction comptageDeMots() de la classe PatriciaTrie qui est le suivant :
public comptageDeMots(): number { return this.noeuds.map(n => n.comptageDeMots()).reduce((a,b) => a + b, 0); }La compléxité de cette fonction est égal à la compléxité de la fonciton map de l'interface Array fois puis le compléxité e la fonction comptageDeMots() de la classe ArbreNoeudSimple plus la complexité de la fonction reduce de l'interface Array. D'après ECMA les fonctions .map et .reduce de l'interface Array ont comme complexité O(n). On va donc étudier la complexité de la fonction comptageDeMots() de la classe ArbreNoeudSimple qui est le suivant:
public comptageDeMots(verbose:boolean = false): number { if (verbose) { console.log("On contrôle d'abord si l'arbre est vide"); } if (this.estArbreVide()) { if (verbose) { console.log("Si l'arbre est vide alors on retourne 0"); } return 0; } else { if (verbose) { console.log("Si l'arbre n'est pas vide alors on contrôle s'il s'agit d'une feuille"); } if (this.estFeuille()) { if (verbose) { console.log("S'il s'agit d'une feuille. Alors on retourne 1"); } return 1; } else { if (verbose) { console.log("Si ce n'est pas une feuille on lance notre fonction sur les sous-arbres definis et on fait une somme de tous"); } return this.sousArbres.filter(sa => sa !== undefined).map(a => (<ArbreNoeudSimple>a).comptageDeMots()).reduce((accumulateur, valeurCourante) => accumulateur + valeurCourante,0); } } }La complexité dans le pire des cas de cette fonction est O(n) qui viens des complexités des fonctions filter, map et reduce de l'interface Array et de l'appels recursives de la fonction elle-mmême. Donc on peut déduire que la coplexité de la fonction ComptageMots(arbre) -> number de la classe ArbreFactory est en O(n).
La fonction listeDeMots(arbre) -> listemots de la classe ArbreFactory est le suivant :
static listeMots(arbre: PatriciaTrie|TrieHybride): Array<string> { return arbre.listeMots(); }Il fait un simple appel à la fonction listeMots de la classe Patricia Tries qui est le suivant :
public listeMots(prefixe: string = "",verbose:boolean = false): Array<string> { return this.noeuds.map(n => n.listeMots("",verbose)).reduce((a,b) => a.concat(b)).sort(); }La complexité de cette fonction est donc la complexité de la fonciton map de l'interface Array fois la complexité de la fonction listeMots de la classe ArbreNoeudSimple plus la complexité de la fonction reduce de l'interface Array. Les fonctions map et reduce de l'interface Array ont comme complexité O(n) d'après ECMA. Donc on va étudier la complexité de la fonction listeMots de la classe ArbreNoeudSimple qui est le suivant:
public listeMots(prefixe: string = "",verbose: boolean = false): Array<string> { if (verbose) { console.log("On crée une liste qui va contenir tous les mots dans l'arbre. On appele ça res"); } var res = new Array<string>(); if (verbose) { console.log("On contrôle d'abord si l'arbre est vide"); } if (this.estArbreVide()) { if (verbose) { console.log("Si l'arbre est vide. On rajoute la préfixe à la liste des mots et on retourne res"); } res.push(prefixe); return res; } else { if (verbose) { console.log("Si l'arbre n'est pas vide alors on contrôle si l'arbre est une feuille."); } if (this.estFeuille()) { if (verbose) { console.log("Si l'arbre est une feuille. On contrôle si la racine de l'arbre est définie"); } if (this.racine !== undefined) { if (verbose) { console.log("Si la racine de l'arbre est définie. On ajoute la clé de la racine à la fin du préfixe et on rajoute le préfixe a la res"); } const np: string = prefixe + this.racine.getCle(); if (verbose) { console.log("Le nouvel préfixe est donc " + np); } res.push(np); return res; } else { if (verbose) { console.log("Si la racine n'est pas définie alors on rajoute le préfixe à la liste res et on retourne res"); } res.push(prefixe); return res; } } else { if (verbose) { console.log("Si l'arbre n'est pas une feuille. Alors on contrôle si la racine est définie"); } if (this.racine !== undefined) { if (verbose) { console.log("Si la racine de l'arbre est bien défini alors on crée une nouvelle préfixe. Où on va concatener le préfixe actuel avec la clé de la racine."); } const mpre:string = prefixe + this.racine.getCle(); if (verbose) { console.log("Ancien préfixe " + prefixe); console.log("La clé à la racine " + this.racine.getCle()); console.log("Notre nouvelle préfixe est donc " + mpre); } return this.sousArbres.filter(s => s !== undefined).map(x => (<ArbreNoeudSimple>x).listeMots(mpre,verbose)).reduce((l1,l2) => l1.concat(l2), new Array()); } else { if (verbose) { console.log("Si la racine n'est pas définie. Alors on ajoute le préfixe à la res. Et on retourne res."); } res.push(prefixe); return res; } } } }La complexité de cette fonciton est en O(n) qui venant des appels recursives et des fonctions reduce et concat. Donc on peut en déduire que la complexité de la fonction listeMots(arbre) -> Listemots de la classe ArbreFactory est en O(n)
La fonction ComptageNil(arbre) -> entier de la classe ArbreFactory est le suivant:
public comptageNil(verbose?: boolean): number { return ((this.racine !== undefined)?this.racine.comptageNil():1) + (this.sousArbres.filter(x => x === undefined).length) + ((this.pere !== undefined)?1:0) + (this.sousArbres.filter(c => c !== undefined).map(v => (<ArbreNoeudSimple>v).comptageNil(verbose)).reduce((a,b) => a + b,0)); }Soit n le nombre d'arbre de Patricia Tries la complexité de cette fonction est en n fois (qu'il vient de la compléxité de la fonction filter de l'interface Array) la compléxité de la fonction comptageNil de la classe ArbreNoeudSimple. On étudie donc la fonction comptageNil de la classe ArbreNoeudSimple pour conclure sur l'étude de la complexité de la fonction ComptageNil(arbre) -> entier. Cette fonction est le suivant :
public comptageNil(verbose?: boolean): number { return ((this.racine !== undefined)?this.racine.comptageNil():1) + (this.sousArbres.filter(x => x === undefined).length) + ((this.pere !== undefined)?1:0) + (this.sousArbres.filter(c => c !== undefined).map(v => (<ArbreNoeudSimple>v).comptageNil(verbose)).reduce((a,b) => a + b,0)); }La fonction donc contrôle si la racine est bien défini et si elle est bien défini elle fait appel à la fonction comptageNil de la classe NoeudSimple parce que l'attribut racine est de cette type et rajoute cette resultat à la longueur de la liste des sousArbres qui est égal à undefined qui est aussi ajouté à 0 ou à 1 en fonction du père de l'arbre (si le père de l'arbre est défini 0 et 1 sinon) et la somme des resultats de l'appel de la fonction comptageNil sur chacune des sous-arbres. Don la complexité de cette fonction est en O(n²). D'où on peut déduire de la complexité de la fonction comptageNil(arbre) de la classe ArbreFactory pour le structure Patricia Tries.
La fonction Hauteur(arbre) -> entier de la classe ArbreFactory est le suivant :
public hauteur(verbose:boolean = false):number { return this.noeuds.map(v => v.hauteur()).reduce((a,b) => Math.max(a,b),-1); }Cette fonction appel la fonction hauteur de chacun des sous-arbres et prend le max de tous ces resultats. Donc pour un Patricia Tries de n arbres elle fait n fois l'appel à la fonction hauteur de la classe ArbreNoeudSimple qui est le suivant :
public hauteur( verbose: boolean= false ): number { /* Si l'arbre est vide on retourne -1 Si l'arbre est une feuille on retourne 0 Sinon l'hauteur est le maximum des hauteurs de ses sous-arbres + 1 */ return (this.estArbreVide() === true)? -1: ((this.estFeuille() === true)? 0: ((this.sousArbres. filter(x => x !== undefined). map(x => (<ArbreNoeudSimple>x).hauteur()). reduce((a,b) => Math.max(a,b),-1) ) + 1 ) ); }La complexité de cette fonction est O(n) parce qu'elle parcourt tous les sous-arbres pour trouver la branche la plus longue. Donc on peut en déduire de la complexité de cette fonction est O(n).
La fonction profondeurMoyen(arbre) -> entier de la classe ArbreFactory est le suivant:
static profondeurMoyenne(arbre: PatriciaTrie|TrieHybride): number { return arbre.profondeurMoyen(); }Cette fonction donc fait une simple appel à la fonction profondeurMoyen de la classe Patricia Tries qui est le suivant :
public profondeurMoyen(verbose:boolean = false): number { return this.profondeurs(verbose).reduce((a,b) => a+b,0)/this.profondeurs().length; }Cette fonction calcule le profondeur moyen en faisant la somme de profondeur de tous les feuilles et le divise par le nombre de feuilles dant l'arbre. On étudie donc la complexité de la fonction profondeurs qui calcule la liste des profondeurs de tous les feuilles de l'arbre qui est le suivant:
public profondeurs(verbose:boolean=false,index:number = 0): Array<number>{ if (this.estArbreVide()) { if (verbose) { console.log("L'arbre est vide"); } return [0]; } else if (this.estFeuille()) { if (verbose) { console.log("L'arbre est une feuille. Index = " + index); } return [index]; } else { if (this.pere == undefined) { index++; } var feuilles = this.sousArbres.filter(x => (x !== undefined) && (x.estFeuille() === true)); var nonFeuilles = this.sousArbres.filter(c => (c !== undefined) && (c.estFeuille() === false)); if (verbose) { console.log("Le nombre des feuilles à niveau " + index + " est " + feuilles.length); console.log("Le nombre des non-feuilles sont " + nonFeuilles.length); } var res = new Array<number>(); for (var i = 0; i<feuilles.length; i++) { res.push(index); } return res.concat(nonFeuilles.map(v => (<ArbreNoeudSimple>v).profondeurs(verbose,index+1)) .reduce((a,c) => a.concat(c),[])); } }Cette fonction parcourt l'arbre niveaux par niveaux et ajoute le profondeur du niveau aux feuilles qui ont trouvé dans le niveau. Donc la complexité de cette fonction est O(n) avec n l'hauteur de l'arbre.
La fonction Prefixe(arbre,mot) -> entier de la classe ArbreFactory est le suivant :
static prefixe(arbre: PatriciaTrie|TrieHybride, mot: string): number { return arbre.prefixe(mot); }La fonction fait simplement un appel à la fonction prefixe(mot) de la classe ArbreNoeudSimple qui est le suivant:
public prefixe(mot:string,verbose:boolean= false): number { return (this.find(mot).estArbreVide() === true)?0:this.find(mot).listeMots().length; }La fonciton calcule la liste des mots de la sous-partie de l'arbre que le mot passé en paramètres est une préfixe. Donc on étudie la fonction find de la classe ArbreNoeudSimple qui est le suivant:
public find(mot:string, verbose: boolean = false): ArbreNoeudSimple { if ((mot.length === 0)) { if (verbose) { console.log("Si le mot est vide. On retourne l'arbre actuel"); } return this; } else { if (this.estArbreVide()) { if (verbose) { console.log("Si l'arbre est vide alors on retourne undefined."); } return new ArbreNoeudSimple(); } else { if (verbose) { console.log("Si l'arbre n'est pas vide. On regarde si la racine est définie"); } if (this.racine !== undefined) { if (verbose) { console.log("Si la racine de l'arbre est définie. Alors on controle si la clé est une préfixe du mot"); } if (mot.indexOf(this.racine.getCle()) === 0) { if (verbose) { console.log("Si la clé de la racine est une préfixe du mot. On contrôle si la clé est égale au mot"); } if (this.racine.cle === mot) { if (verbose) { console.log("Si la clé est le mot on retourne this"); } return this; } else { if (verbose) { console.log("Si la clé n'est pas le mot mais une préfixe du mot. Alors on va calculer le reste du mot. Et on va lancer notre recherche ce mot sur le sous arbre eligible"); } const reste = mot.slice(this.racine.cle.length); var eligible = this.sousArbres.filter(r => (r !== undefined) && (r.racine !== undefined) && (reste.indexOf(r.racine.getCle()) === 0)); if (eligible.length === 1) { if (verbose) { console.log("Si un sous-arbre eligible existe on lance notre fonction dessus "); } return (<ArbreNoeudSimple>eligible[0]).find(reste); } if (eligible.length === 0) { if (verbose) { console.log("Si il n'y a aucun arbre eligible."); } return new ArbreNoeudSimple(); } if (eligible.length > 1) { if (verbose) { console.log(Error,"Il y a plusieurs arbres existent"); } return new ArbreNoeudSimple(); } } } else { if (verbose) { console.log("Si la racine n'est pas un préfixe du mot. On retourne undefined"); } return new ArbreNoeudSimple(); } } } } if (verbose) { console.log("On est rentré dans aucun if"); } return new ArbreNoeudSimple(); }Cette fonction a les mêmes démarches de la fonction recherche donc sa complexités aussi en O(n). Alors la complexité de la fonction prefixe(arbre,mot) pour le structure Patricia Tries est en O(n) qui est la même que la recherche.
La fonction Suppression(arbre,mot) -> PatriciaTrie de la classe ArbreFactory est le suivant:
static suppression(arbre: PatriciaTrie|TrieHybride, mot: string): PatriciaTrie|TrieHybride { return arbre.supprimer(mot); }La fonction fait simplement un appel à la fonciton suppression de la classe PatriciaTrie qui est le suivant:
public supprimer(mot:string,verbose:boolean = false): PatriciaTrie { if (verbose) { console.log("Le nombre des mots " + this.listeMots().length); console.log("Les nombres des mots : " + this.noeuds.map(x => x.listeMots().length)); console.log("Les nouvelles nombres des mots " + this.noeuds.map(x => x.supprimer(mot).listeMots().length)); console.log("Les nombres des mots de la liste des sous arbres " + this.noeuds.map(x => x.listeMots().length)) } this.noeuds = new Array<ArbreNoeudSimple>(...this.noeuds.map(w => w.supprimer(mot,false))); if (verbose) { console.log("Les nombres des mots de la liste des sous arbres " + this.noeuds.map(x => x.listeMots().length)) } return this; }La fonction parcourt la liste des arbres de la Patricia Tries et pour chacun des arbres elle appelle la fonciton supprimer(mot) de la classe ArbreNoeudSimple qui est le suivant:
public supprimer(mot:string,verbose:boolean=false): ArbreNoeudSimple { if (verbose) { console.log("On contrôle d'abord si le mot existe dans l'arbre"); } if (this.recherche(mot) === true) { if (verbose) { console.log("Si le mot existe dans l'arbre"); console.log("On retrouve la partie qui contient ce mot"); } var partie: ArbreNoeudSimple = this.find(mot); if (verbose) { console.log("La variable partie contient la sous partie de l'arbre qui contient le mot " + mot); console.log("On va supprimer le noeud qui indique la fin du mot de ses sous-arbres"); partie.showOnConsole(); } if (partie.estFeuille()) { if (verbose) { console.log("Si la partie est une feuille. Alors on va supprimer ceci"); console.log("Le nombre des mots avant l'affichage" + this.listeMots().length); } partie.pere?partie.pere.sousArbres[partie.pere.sousArbres.indexOf(partie)] = undefined:partie.racine = undefined; partie.racine = undefined; while(partie.pere !== undefined) { partie = partie.pere; } if (verbose) { console.log("Le nombre des mots dans la partie après while " + partie.listeMots().length); } return partie; } else { if (verbose) { console.log("Si l'arbre n'est pas une feuille"); console.log("Le nombre des sous arbres " + partie.sousArbres.length); console.log("le nombre des mots avant la suppression " + this.listeMots().length) } partie.sousArbres = partie.sousArbres.filter(c => ((c !== undefined) && (c.racine !== undefined) && (c.racine.cle !== "\0"))); if (verbose) { console.log("Le nombre des sous arbres après" + partie.sousArbres.length); } while(partie.pere !== undefined) { partie = partie.pere; } if (verbose) { console.log("La variable partie après while"); partie.showOnConsole(); console.log("Le nombre des mots dans la partie après while " + partie.listeMots().length); } return partie; } } else { if (verbose) { console.log("Si le mot n'existe pas dans l'arbre"); } return this; } }La fonction teste d'abord si le mot existe dans l'arbre et si il y existe il trouve la sous-partie associé au mot et supprime juste le noeud qui indique le fin de mots. Donc la complexité de cette fonction est le même que la recherche qui est en O(n).
Les fonctions du structure Trie Hybride sont les suivants:
- Fonction recherche(arbre,mot) -> booléen de la classe ArbreFactory fait simplement un appel à la fonction recherche(mot) de la classe TrieHybride qui est le suivant:
public recherche(mot: string,verbose: boolean = false): boolean { /** TODO: */ mot = mot.toLowerCase(); if (verbose) { console.log("On cherche le mot " + mot + " dans le trie hybride"); } // - On contrôle d'abord si le mot est vide if (mot.length === 0) { // Si le mot est vide on retourne true if (verbose) { console.log("Si le mot est vide"); } return true; } else { if (verbose) { console.log("Si le mot n'est pas vide. Alors on contrôle si l'arbre est vide"); } // Si le mot n'est pas vide alors on contrôle si l'arbre est vide if (this.estArbreVide()) { // Si l'arbre est vide alors on retourne false if (verbose) { console.log("Si l'arbre est vide. Alors on retourne false"); } return false; } else { // Si l'arbre n'est pas vide, alors on contrôle si la clé de la racine de l'arbre est le premier lettre du mot passé en paramètres. if (verbose) { console.log("Si l'arbre n'est pas vide. Alors "); } if ((this.racine !== undefined) && (mot.indexOf(this.racine.getCle()) === 0)) { // Si la clé de la racine de l'arbre est le premier caractère du mot passé en paramètres, on côntrole d'abord si le mot a plus de 1 caractères. if (verbose) { console.log("La clé de la racine est le premier caractère du mot passé en paramètres. On contrôle si le mot plus de 1 caractères"); } if (mot.length > 1) { if (verbose) { console.log("Si le mot contient plus de 1 caractères"); } // Si le mot contient plus de 1 caractères on contrôle si l'arbre eq est défini if (this.eq !== undefined) { // Si l'arbre eq est défini on lance notre recherche avec la reste des mots sur l'arbre eq if (verbose) { console.log("L'arbre eq est bien defini. On lance notre recherche avec la reste du mot " + mot.slice(1) + " sur l'arbre eq"); } return this.eq.recherche(mot.slice(1),verbose); } else { if (verbose) { console.log("Si l'arbre eq n'est pas defini on retourne false"); } // Si l'arbre eq n'est pas défini alors on retoune false return false; } } else { if (verbose) { console.log("Si le mot contient qu'un seul caractère alors on retorne true si la valeur est defini, false sinon"); } return ((this.racine !== undefined) && (this.racine.valeur !== undefined)); } } else { // Si la clé de la racine n'est pas le premier lettre du mot passé en paramètres. if (verbose) { console.log("La clé de la racin n'est pas le premier lettre du mot passé en paramètres"); } if (this.racine !== undefined) { if (verbose) { console.log("La racine de l'arbre est défini"); } if (this.racine.getCle()<mot.split('')[0]) { if (verbose) { console.log("Si la clé de racine est plus petit que le premier caractère du mot. On contrôle si l'arbre sup existe"); } if (this.sup === undefined) { //Si l'arbre sup n'existe pas on retourne false if (verbose) { console.log("Si l'arbre sup n'existe pas on retourne false"); } return false; } else { //Si l'arbre sup existe on lance notre recherche sur l'arbre sup avec le mot comme tel. if (verbose) { console.log("Si l'arbre sup existe on lance notre recherche sur l'arbre sup avec le mot comme tel."); } return this.sup.recherche(mot,verbose); } } else { if (verbose) { console.log("La clé de la racine de l'arbre est plus grand que le premier caractère du mot passé en paramètres. Alors on va traiter l'arbre inf"); } if (this.inf === undefined) { if (verbose) { console.log("Si l'arbre inf n'est pas défini alors on retourne false"); } return false; } else { if (verbose) { console.log("Si l'arbre inf est défini alors on relance notre recherche sur l'arbre inf avec le mot tel quel"); }
- Fonction recherche(arbre,mot) -> booléen de la classe ArbreFactory fait simplement un appel à la fonction recherche(mot) de la classe TrieHybride qui est le suivant:
6 years ago