Clojure: Как создать «Trie»?

Question

Учитывая следующее ...

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

Как бы вы преобразовали это в этот три?

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

Answer 1

Вот очищенное решение. Это исправляет ошибку метода добавления Брайана, поскольку в настоящее время он зависит от того, вставляете ли вы seqs в порядке увеличения длины. Это также позволяет запрашивать tree по префиксу, что является распространенным случаем использования.

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

(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

Списки здесь очень неуклюжие, не говоря уже о неэффективности. В 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 `(~@x :terminal) true))

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

Если вы хотите, чтобы он печатал отсортированные, вы могли бы вместо этого использовать sorted-map s, но вам нужно было бы написать свою собственную версию 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

Answer 3

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

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

-> (ноль (1 (2 (4 (20 (25))) (10 (15)) (5 ​​(9))) (3))))

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

Answer 4

В общем случае вот что я бы сделал:

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

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