[Resolu][MY-AL]Recherche de mots dans dico

Pour les scripts écrits en C#
Règles du forum
Merci de respecter la NOMENCLATURE suivante pour vos TITRES de messages :

Commencez par le niveau de vos scripts
DB = Débutant
MY = Moyen
CF = Confirmé

Puis le domaine d'application
-RS = Réseau
-AL = Algorithmie

Exemple :

[DB-RS] Mouvement perso multijoueur
djulio74
Messages : 682
Inscription : 19 Déc 2009 22:55

Re: [Resolu][MY-AL]Recherche de mots dans dico

Message par djulio74 » 26 Jan 2020 01:56

de mon coté une question me viens, comment arriver a trouver tout ces mots alors que la grille ne fait que 5x5? ne devrais tu pas te retrouver qu'avec des mots de 5 lettre maximum? ou alors il y a un truc que j'ai pas saisi depuis le début. ^^

J'ai pas trop compris la solution de Alesk (un peu lu juste en diagonale je l'avoue) mais mon retour sur la longueur du traitement :
- j'ai idée tes fonctions recherche ne sont pas au point dans le sens ou tu trouve de si longs mots,
- l'utilisation des string est plutôt longue comparé aux int d’après ce qu'il me semble avoir déjà lu (j'y reviendrai après)
- l'optimisation est certainement possible : je traite bien des millions (voir milliard je pense) d'opération en 2-3 seconde pour mon ile)

Je vais tenter un bout de script et je reposte dans un moment, mais l'idée qui m'est venue est :
- utilisation d'array plutôt que d'un seul string contenant tout les mots
- Convertir tes mots en array de int avec pour correspondance la place des lettres dans l’alphabet.
- surtout pas utiliser de liste, plutôt des array avec un compteur a part pour savoir la place des élément a "ajouter".

Comme je disait je vais tenter un petit script vite fait, surement pas fonctionnel mais pour avoir une idée de ce que j'ai en tête. ;)

______________________________________________________________
\_______________________ Impossible is nothing _______________________/

djulio74
Messages : 682
Inscription : 19 Déc 2009 22:55

Re: [Resolu][MY-AL]Recherche de mots dans dico

Message par djulio74 » 26 Jan 2020 04:34

voila un petit exemple test de comment je verrai les choses, et se servant de "int" plutôt que de "char" et de "string" :

Code : Tout sélectionner

using System;
using System.Collections.Generic;
using UnityEngine;

public class TestMots : MonoBehaviour
{

	// exemple d'array de string correspondant au dictionnaire
	private string[] Dictionnaire = new string[18] {
		"Bonjour", "comment", "allez", "vous", "en", "Ce", "beau", "jour", "si", "magnifique",
		"Je", "vais", "bien", "merci", "bonsoir", "bon", "bo", "botte"	
	};

	// pour chaque élément, on aura un int[] correspondant au nombre de lettre du mot et de la position de chaque lettre du mot.
	private int[][] DicoNumérique;
	// stock l'index des mots retenu dans les recherches
	private int[] MotsTrouvés = new int[18];
	private int MotsTrouvésCount;
	// stock l'array des mots complets trouvé pendant la recherche.
	private int[] MotsFinal = new int[18];
	private int MotsFinalCount;

	void Start ()
	{
		// convertir les mots du dictionnaire en array de int, avec a = 1, b = 2 .. etc
		// rapide, testé avec 100000 itération de mon "Dictionnaire" pour simuler la traduction de 1 000 000 de mots, prend 1s
		DicoNumérique = new int[Dictionnaire.Length][];
		for (int i = 0; i < Dictionnaire.Length; i++) {
			DicoNumérique [i] = new int[Dictionnaire [i].Length];
			for (int j = 0; j < Dictionnaire [i].Length; j++) {
				DicoNumérique [i] [j] = char.ToUpper (Dictionnaire [i] [j]) - 64;
			}
		}

		// mots à retrouver commençant par b, se trouvant dans le mot bonjour par exemple
		char[] A = "bonjour".ToCharArray ();
		MotsFinalCount = 0;

		// commence par trouver tout les mots commençant par la premiere lettre
		MotCommencantPar (char.ToUpper (A [0]) - 64);

		// ensuite pour chacune des autre lettre, les mots correspondant
		for (int i = 1; i < A.Length; i++) {
			if ( MotsTrouvésCount >0){
				MotAvec (i, char.ToUpper (A [i]) - 64);
			}
		}

		// a la fin, petit print de tout les mots trouvés
		for ( int i = 0 ; i < MotsFinalCount ; i++){
			print ( Dictionnaire[MotsFinal[i]]);
		}
	}

	void MotCommencantPar (int L)
	{
		// on reset le count des mots trouvé
		MotsTrouvésCount = 0;

		// on stock l'index des mots trouvés dans un int[] MotsTrouvés
		// on incrémente le compteur de mot
		// pour éviter d'utiliser les List et Add
		for (int i = 0; i < DicoNumérique.Length; i++) {
			if (DicoNumérique [i] [0] == L) {
				MotsTrouvés [MotsTrouvésCount] = i;
				MotsTrouvésCount++;
			}
		}

		// on resize (optionnel) la taille de l'array des mots trouvé, on en aura pas plus
		Array.Resize (ref MotsTrouvés, MotsTrouvésCount);
	}

	void MotAvec (int P, int L)
	{
		// on stock les mots trouvés dans un temp pour chercher dedans
		int[] temp = MotsTrouvés;

		// on reinitialise le compteur de mots trouvé, 
		MotsTrouvésCount = 0;

		// on cherche dans le temps ceux qui ont la lettre voulu a la place voulu
		for (int i = 0; i < temp.Length; i++) {
			if (DicoNumérique [temp [i]].Length > P && DicoNumérique [temp [i]] [P] == L) {
				MotsTrouvés [MotsTrouvésCount] = temp [i];
				MotsTrouvésCount++;
			}

			// si la lettre rechercher est la derniere du mot, on stock l'index de ce mot dans un int[] MotsFinal
			// idem incrémente le compteur pour se passer des list
			if (DicoNumérique [temp [i]].Length == P+1 && DicoNumérique [temp [i]] [P] == L) {
				MotsFinal[MotsFinalCount] = temp [i];
				MotsFinalCount ++;
			}
		}

		// on resize l'array, pour ne garder que la longueur des nouveaux mots
		Array.Resize (ref MotsTrouvés, MotsTrouvésCount);
	}
}
en gros dans ton cas, pour chaque case, pour chacune des 8 directions, stocker les suite de lettre de ta case jusqu'au bord de la grille et faire la recherche avec ce "mot" que ça formera.

______________________________________________________________
\_______________________ Impossible is nothing _______________________/

EmileF
Messages : 673
Inscription : 18 Mars 2017 19:39

Re: [Resolu][MY-AL]Recherche de mots dans dico

Message par EmileF » 26 Jan 2020 10:59

Merci Alesk, Merci Djulio,

Pour ton idée Alesk, ça oblige de refaire un dico en mettant toutes les lettres de chaque mot dans l'ordre alphabétique et ensuite de les trier par longueur, si j'ai bien compris.

De ce fait, pour chaque recherche, je serai aussi obligé de trier les lettres de mon mot par ordre alphabétique et ensuite de rechercher la référence pour avoir les mots finaux.

Excuse-moi Djulio de t'avoir fait couché si tard.
Pour la longueur des mots il faut savoir qu'a partir de chaque case le lettre suivante peut partir dans toutes les directions, c'est camme ça que je peux avoir des mots de 25 lettres et même plus. Il n'y a que le dico comme limite.

Je n'ai pas encore regardé ton script, ce que je vais faire immédiatement, mais s'il ne tiens pas compte de toutes les directions à chaque lettre il ne sera pas bon. C'est d'ailleurs à cause de cela que c'est si long.

J'utilise les strings pour pouvoir bénéficier des ReGex, je pense que c'est plus rapide et efficace qu'un script perso.

Je vais étudier ton script pour essayer de comprendre et de l'adapter à mon cas.

En tout cas merci à tous les deux
La différence entre l'intelligence et la stupidité est que l'intelligence est limitée.

EmileF
Messages : 673
Inscription : 18 Mars 2017 19:39

Re: [Resolu][MY-AL]Recherche de mots dans dico

Message par EmileF » 26 Jan 2020 11:15

Si j'ai bien compris, Djulio, tu fais ta recherche par rapport à un mot de ton dictionnaire. Mais tu ne tiens pas compte des lettres de la grille, ou j'ai mal compris.

Pour la recherche initiale OK, mais à partir de la 2ème lettre, il faut qu'elle corresponde à une des lettres des cases qui entoure la case courante, et ainsi de suite. Je ne vois rien dans ton script qui corresponde à ça. Ou je n'ai rien compris.

Par contre pour ce qui est du tri de ton dico je pense que tu te rapproches un peu des explications d'Alesk, mais là, j'avoue que je n'ai rien compris.
Dernière édition par EmileF le 26 Jan 2020 11:40, édité 1 fois.
La différence entre l'intelligence et la stupidité est que l'intelligence est limitée.

EmileF
Messages : 673
Inscription : 18 Mars 2017 19:39

Re: [Resolu][MY-AL]Recherche de mots dans dico

Message par EmileF » 26 Jan 2020 11:37

Alesk, Merci pour ton message

Je ne vois pas très bien comment je peux adapter ton dico à mes recherches, sachant que je recherche mes mots par rapport au début du mot, pas par rapport au mot complet.

Mon dico est classé par ordre alphabétique et automatiquement par ordre de taille. Et j'utilise les ReGex pour faire mes recherches. Par contre pour faire des recherches d'anagrammes par exemple ça me semble idéal, j'ais déjà fait un truc dans ce genre à une certaine époque.
La différence entre l'intelligence et la stupidité est que l'intelligence est limitée.

djulio74
Messages : 682
Inscription : 19 Déc 2009 22:55

Re: [Resolu][MY-AL]Recherche de mots dans dico

Message par djulio74 » 26 Jan 2020 12:49

ahh ok!!! j'avais donc pas bien compris, je pensais que tu cherchait a faire un genre de mot-mélé où les mots ne se lisent qu'en ligne droite. Je comprend donc un peu mieux la longueur du traitement si pour chaque case tu peux partir dans toute les directions. ;)
Déjà aurait tu un fichier texte de ton dictionnaire pour pouvoir faire des test?

En effet dans mon exemple je fait des recherches par rapport à un mot donné,mais bien sur possible d'adapté pour chercher en fonction de la case suivante.

Pour expliqué vite fais ma vision. Je crois avoir lu que l’écriture/lecture de string n'était pas la chose la plus efficace en tant que temps d’exécution. Mon idée est de convertir les mot string en suite de int sous forme d'array.
En gros pour chaque mot du dictionnaire, tu retrouve un int[], avec le même nombre d'élément que de lettre du mots référence, et chaque int correspond à la place de la lettre dans l'alphabet.

tu fais la même chose pour chaque case de ta grille.
pour ta recherche, pour chaque case, donc le int, tu recherche parmi le dico numérique les élément dont le premier élément correspond à la case, et tu stock ces mot numérique dans un array de int, correspondant a l'index du mot.
Ensuite pour chaque case voisine tu recherche parmi les mots stocké ceux qui ont pour deuxième lettre celle correspondant a la case voisine, stock ces mots et ainsi de suite. donc plus tu avance tu recherche parmi une liste de moins en moins grande.
il y a une condition pour que si la lettre trouvé correspond a la dernière lettre du mot, stock l'index du mot dans Motfinal, qui sont les mot complets.
Je rajoute tout ça à mon script et si tu as la liste de ton dico je suis preneur. ;)

______________________________________________________________
\_______________________ Impossible is nothing _______________________/

EmileF
Messages : 673
Inscription : 18 Mars 2017 19:39

Re: [Resolu][MY-AL]Recherche de mots dans dico

Message par EmileF » 26 Jan 2020 13:57

Excuse Djulio, mais je ne sais pas comment insérer un fichier
Il me refuse les fichiers .txt, que ce soit par drag and drop ou par piéces jointes.
La différence entre l'intelligence et la stupidité est que l'intelligence est limitée.

djulio74
Messages : 682
Inscription : 19 Déc 2009 22:55

Re: [Resolu][MY-AL]Recherche de mots dans dico

Message par djulio74 » 26 Jan 2020 14:10

arf mince, bah au pire copie colle le entre des balise code, pour pas ça fasse un post à rallonge. ;)

______________________________________________________________
\_______________________ Impossible is nothing _______________________/

EmileF
Messages : 673
Inscription : 18 Mars 2017 19:39

Re: [Resolu][MY-AL]Recherche de mots dans dico

Message par EmileF » 26 Jan 2020 14:20

J'ai essayé mais les messages sont limités à 60000 caractères et mon fichier en contient plus de 2 millions.
Ca ne marche pas.

Mais voila un lien pour le télécharger comme une application:
https://drive.google.com/open?id=1YSa5q ... j8CnmzHln9
Je pense qu'ainsi ça va marcher
La différence entre l'intelligence et la stupidité est que l'intelligence est limitée.

Avatar de l’utilisateur
Aelhan
Messages : 124
Inscription : 11 Déc 2019 23:00

Re: [Resolu][MY-AL]Recherche de mots dans dico

Message par Aelhan » 26 Jan 2020 14:27

Sinon tu as des sites d'upload de fichiers, dont tu peux partager le lien (les moteurs de recherche proposent plein de résultats, avec validité du fichier d'une semaine en version gratuite souvent : https://www.qwant.com/?q=upload+fichier ... opensearch)
Celui qui pose une question risque cinq minutes d'avoir l'air bête.
Celui qui ne pose pas de question restera bête toute sa vie.

Répondre

Revenir vers « (C#) CSharp »