clojure:有效地确定字符串是否以集合中的任何前缀开头

Question

我有一组前缀/值对，并希望在此连接中找到与当前目标字符串开头的前缀相关联的任何值。 (在多个前缀匹配的情况下定义行为并不重要，因为我的用例的性质是这种情况永远不会发生)。

一个天真的(工作)实现如下:

(defn prefix-match [target-str pairs]
  (some
    (fn [[k v]]
        (if (.startsWith target-str k)
            v
            false))
    pairs))

这样:

user=> (prefix-match "foobar" {"meh" :qux, "foo" :baz})
:baz

这按预期工作，但是 O(n) 的长度为 pairs顺序。 (快速插入 pairs 也是可取的，但不如快速查找重要)。

想到的第一件事是用高效的随机访问将排序的集合一分为二，但我不确定 Clojure 中的哪些数据结构最适合该任务。建议？

Answer 1

试一试怎么样？

(defn build-trie [seed & kvs]
  (reduce
   (fn [trie [k v]]
     (assoc-in trie (concat k [:val]) v))
   seed
   (partition 2 kvs)))

(defn prefix-match [target trie]
  (when (seq target)
    (when-let [node (trie (first target))]
      (or (:val node)
          (recur (rest target) node)))))

用法:

user> (def trie (build-trie {} "foo" :baz "meh" :qux))
#'user/trie
user> trie
{\m {\e {\h {:val :qux}}}, \f {\o {\o {:val :baz}}}}
user> (prefix-match "foobar" trie)
:baz
user> (prefix-match "foo" trie)
:baz
user> (prefix-match "f" trie)
nil
user> (prefix-match "abcd" trie)
nil