Clojure: Как сгенерировать "trie"?

Ответ 1

Здесь очищенное решение. Это исправляет метод Brian add-to-trie, поскольку он в настоящее время зависит от того, как вы вставляете seqs в порядке увеличения длины. Он также позволяет запрашивать trie по префиксу, который является обычным прецедентом.

Обратите внимание, что использование памяти здесь выше, поскольку оно хранит значения в листовых узлах trie, чтобы вы могли выполнять поиск.

(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))

Ответ 2

Списки очень неуклюжи здесь, не говоря уже о неэффективности. В Clojure более идиоматично использовать векторы и хеш-карты и множества, когда это необходимо. Использование хэш-карт:

(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 `([email protected] :terminal) true))

(defn in-trie? [trie x]
  (get-in trie `([email protected] :terminal)))

Если вы хотите, чтобы он отсортировался, вы могли бы использовать sorted-map вместо этого, но вам придется написать собственную версию assoc-in, которая использовала отсортированные карты в обратном порядке. В любом случае:

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

Ответ 3

Как общий подход, вот что я буду делать:

• Напишите несколько функций для создания trie и вставки новых элементов в trie.
• Создайте новый трюк.
• Перейдите через список ввода и вставьте каждый элемент в trie.

Эта проблема очень хорошо подходит для рекурсивной реализации. Я бы постарался, если это было возможно.

Ответ 4

Я уверен, что есть более красивый способ (там было! см. Брайан, ответьте лучше):

(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)

Обратите внимание, что я решил использовать nil как root node и не беспокоился о том, чтобы пустые списки не отображали никаких детей. Фактически это делается неправильно, так как не сохраняет подстроку.