Clojure: Comment générer un 'trie'?

Question

Compte tenu de ce qui suit ...

(def inTree 
'((1 2) 
    (1 2 3) 
    (1 2 4 5 9) 
    (1 2 4 10 15) 
    (1 2 4 20 25))) 

Comment voulez-vous transformer à cette structure arborescente?

(def outTrie 
'(1 
    (2() 
     (3()) 
     (4 (5 
      (9())) 
      (10 
      (15())) 
      (20 
      (25())))))) 

Answer 1

Voici une solution nettoyée. Cela corrige un bogue de la méthode add-to-trie de Brian car elle dépend actuellement de l'insertion des seqs dans l'ordre croissant de longueur. Il permet également d'interroger le préfixe trie, ce qui est un cas d'utilisation courant.

Notez que l'utilisation de la mémoire ici est plus élevée car elle stocke les valeurs dans les nœuds feuille du trie afin que vous puissiez effectuer des recherches.

(defn add-to-trie [trie x] 
    (assoc-in trie x (merge (get-in trie x) {:val x :terminal true}))) 

(defn in-trie? [trie x] 
    "Returns true if the value x exists in the specified trie." 
    (:terminal (get-in trie x) false)) 

(defn prefix-matches [trie prefix] 
    "Returns a list of matches with the prefix specified in the trie specified." 
    (keep :val (tree-seq map? vals (get-in trie prefix)))) 

(defn build-trie [coll] 
    "Builds a trie over the values in the specified seq coll." 
    (reduce add-to-trie {} coll)) 

Answer 2

Comme une approche générale, voici ce que je ferais:

• écrire quelques fonctions pour créer une structure arborescente et pour insérer de nouveaux éléments dans un Trie.
• Créer un nouveau trie.
• Effectuez une itération sur la liste d'entrée et insérez chaque élément dans la liste.

Ce problème se prête très bien à une implémentation récursive. Je viserais pour cela si possible.

Answer 3

Je suis sûr qu'il ya une façon plus jolie (il y avait voir la réponse de Brian, il vaut mieux!):

(defn find-in-trie 
    "Finds a sub trie that matches an item, eg: 
    user=> (find-in-trie '(1 (2) (3 (2))) 3) 
    (3 (2))" 
    [tr item] 
    (first (for [ll (rest tr) :when (= (first ll) item)] ll))) 


(defn add-to-trie 
    "Returns a new trie, the result of adding se to tr, eg: 
    user=> (add-to-trie nil '(1 2)) 
    (1 (2))" 
    [tr se] 
    (cond 
    (empty? se) tr 
    (empty? tr) (add-to-trie (list (first se)) (rest se)) 
    :else (if-let [st (find-in-trie tr (first se))] 
      (cons (first tr) 
        (cons (add-to-trie st (rest se)) 
         (filter (partial not= st) (rest tr)))) 
      (cons (first tr) 
        (cons (add-to-trie (list (first se)) (rest se)) 
         (rest tr)))))) 

(def in '((1 2) 
      (1 2 3) 
      (1 2 4 5 9) 
      (1 2 4 10 15) 
      (1 2 4 20 25))) 

(reduce add-to-trie '(nil) in) 

-> (néant (1 (2 (4 (20 (25)) (10 (15)) (5 ​​(9))) (3))))

Notez que j'ai choisi d'utiliser nil comme nœud racine et que je n'ai pas pris la peine de garder des listes vides pour ne pas indiquer d'enfants. En fait, le faire de cette façon n'est pas correct car il ne conserve pas l'identité de la sous-chaîne.

Answer 4

Les listes sont très maladroites ici, pour ne pas dire inefficaces. Dans Clojure, il est plus idiomatique d'utiliser des vecteurs et des hash-maps et des ensembles, le cas échéant. En utilisant hachage cartes:

(def in-tree 
'((1 2) 
    (1 2 3) 
    (1 2 4 5 9) 
    (1 2 4 10 15) 
    (1 2 4 20 25))) 

(defn add-to-trie [trie x] 
    (assoc-in trie `(~@x :terminal) true)) 

(defn in-trie? [trie x] 
    (get-in trie `(~@x :terminal))) 

Si vous le vouliez à imprimer triés vous pouvez utiliser sorted-map s à la place, mais vous devez écrire votre propre version de assoc-in qui ont utilisé l'ensemble des cartes triées chemin vers le bas. Dans tous les cas:

user> (def trie (reduce add-to-trie {} in-tree)) 
#'user/trie 
user> trie 
{1 {2 {4 {20 {25 {:terminal true}}, 10 {15 {:terminal true}}, 5 {9 {:terminal true}}}, 3 {:terminal true}, :terminal true}}} 
user> (in-trie? trie '(1 2)) 
true 
user> (in-trie? trie '(1 2 4)) 
nil 
user> (in-trie? trie '(1 2 4 20 25)) 
true