trie Télécharger - trie Téléchargement du code source

trie

Autre code source

v0.0.1

Télécharger

essayer

Une implémentation de la structure de données Trie dans Go. Il fournit plus de fonctionnalités que la recherche de préfixe Trie habituelle et est destiné à être utilisé pour la saisie semi-automatique.

Démo

Une démo WebAssembly peut être essayée sur shivamMg.github.io/trie.

Caractéristiques

Les clés sont []string au lieu de string , prenant ainsi en charge davantage de cas d'utilisation - par exemple, []string{the quick brown fox} peut être une clé où chaque mot sera un nœud dans le Trie
Prise en charge de la clé Put et de la clé Supprimer
Prise en charge de la recherche de préfixe : par exemple, la recherche de nation peut renvoyer nation , national , nationalism , nationalist , etc.
Prise en charge de la recherche Modifier la distance (alias distance de Levenshtein) - par exemple, la recherche de blé peut renvoyer des mots similaires tels que blé , triche , chaleur , quoi , etc.
L'ordre des résultats de recherche est déterministe. Il suit l'ordre d'insertion.

Exemples

 tri := trie.New()// Mettre les clés ([]string) et les valeurs (any)tri.Put([]string{"le"}, 1)tri.Put([]string{"le", " rapide", "marron", "renard"}, 2)tri.Put([]string{"le", "rapide", "sports", "voiture"}, 3)tri.Put([]string{" le", "vert", "arbre"}, 4)tri.Put([]string{"une", "pomme", "arbre"}, 5)tri.Put([]string{"une", "parapluie"}, 6)tri.Root(). Print()// Sortie (trie complète avec terminaux se terminant par ($)):// ^// ├─ le ($)// │ ├─ rapide// │ │ ├─ marron// │ │ │ └─ renard ($)// │ │ └─ sports// │ │ └─ voiture ($)// │ └─ vert// │ └─ arbre ($)// └─ an/ / ├─ pomme// │ └─ arbre ($)// └─ parapluie ($)results := tri.Search([]string{"the", "quick"})for _, res := range results.Results { fmt.Println( res.Clé, res.Valeur)
}// Sortie (recherche basée sur le préfixe):// [le renard brun rapide] 2// [la voiture de sport rapide] 3key := []string{"the", "tree"}results = tri.Search(key , trie.WithMaxEditDistance(2), // Une modification peut être insérée, supprimée, remplacéetrie.WithEditOps())pour _, res := range results.Results { fmt.Println(res.Key, res.EditDistance) // EditDistance est le nombre de modifications nécessaires pour convertir en [l'arbre]}// Sortie (les résultats ne se trouvent pas à plus de 2 modifications de [l'arbre]):// [le] 1// [l'arbre vert] 1// [un pommier] 2// [un parapluie] 2result := results.Results[2]fmt.Printf("Pour convertir %v en %v:n", result.Key, key)printEditOps(result.EditOps)// Sortie (opérations d'édition nécessaires pour convertir un résultat en [l'arbre]):// Pour convertir [un pommier] en [l'arbre]:// - supprimer "un"// - remplacer "apple" par "the"// - ne pas modifier "tree"results = tri.Search(key, trie.WithMaxEditDistance(2), trie.WithTopKLeastEdited(), trie.WithMaxResults(2))for _, res := plage results.Results { fmt.Println(res.Key, res.Value, res.EditDistance)
}// Sortie (les 2 premiers résultats les moins édités):// [le] 1 1// [l'arbre vert] 4 1