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

Answer 2

Эффективный, краткий подход заключается в использовании преимущества rsubseq, которое работает с любым типом, реализующим clojure.lang.Sorted - который включает sorted-map.

(defn prefix-match [sorted-map target]
  (let [[closest-match value] (first (rsubseq sorted-map <= target))]
    (if closest-match
      (if (.startsWith target closest-match)
        value
        nil)
      nil)))

Это проходит соответствующие тесты в моем наборе:

(deftest prefix-match-success
  (testing "prefix-match returns a successful match"
    (is (prefix-match (sorted-map "foo" :one "bar" :two) "foobar") :one)
    (is (prefix-match (sorted-map "foo" :one "bar" :two) "foo") :one)))

(deftest prefix-match-fail
  (testing "prefix-match returns nil on no match"
    (is (= nil (prefix-match (sorted-map "foo" :one, "bar" :two) "bazqux")))
    (is (= nil (prefix-match (sorted-map "foo" :one, "bar" :two) "zzz")))
    (is (= nil (prefix-match (sorted-map "foo" :one, "bar" :two) "aaa")))))

Answer 3

Следующее решение находит самый длинный совпадающий префикс и работает на удивление хорошо, когда карта огромна, а строки относительно короткие.Он пытается сопоставить, например, "foobar", "fooba", "foob", "foo", "fo", "f" по порядку и возвращает первое совпадение.

(defn prefix-match
  [s m]
  (->> (for [end (range (count s) 0 -1)] (.subSequence s 0 end)) ; "foo", "fo", "f"
       (map m)           ; match "foo", match "fo", ...
       (remove nil?)     ; ignore unmatched
       (first)))         ; Take first and longest match

Answer 4

Кажется, проще всего просто превратить список префиксов в регулярное выражение и передать их в регулярное выражение, оптимизированное именно для такого рода задач.Что-то вроде

(java.util.regex.Pattern/compile (str "^"
                                      "(?:"
                                      (clojure.string/join "|"
                                                           (map #(java.util.regex.Pattern/quote %)
                                                                prefixes))
                                      ")"))

Должно дать вам регулярное выражение, пригодное для тестирования на строку (но я его вообще не проверял, так что, возможно, я неправильно назвал некоторые методы или что-то в этом роде).