key-compression.clj

(ns monger.key-compression)

(def select (comp first filter))

(defn- trie-add
  [trie words]
  (reduce
   (fn [trie word]
     (assoc-in trie (concat word [::val]) word))
   trie
   words))

(defn- trie-matches
  [trie prefix]
  (letfn [(search [node]
            (mapcat (fn [[k v]]
                      (if (= ::val k) [v] (search v)))
                    node))]
    (search (get-in trie prefix))))

(defn- get-prefixes
  [field]
  (reduce
   (fn [prefixes letter]
     (conj prefixes ((fnil str "") (last prefixes) letter)))
   []
   field))

(defn- get-unique-prefix
  [field trie]
  (let [prefixes (get-prefixes field)]
    (select (fn [prefix] (or (= 1 (count (trie-matches trie prefix)))
                             (= prefix field)))
            prefixes)))

(defn create-compression-map
  "Create a map of shortened unique field names from a list of fields."
  [field-list]
  (let [field-list (map name field-list)
        field-trie (trie-add {} field-list)]
    (into {}
          (map
           (fn [field]
             [(keyword (get-unique-prefix field field-trie)) field])
           field-list))))