Clojure: Эффективное определение того, начинается ли строка с любого префикса в коллекции

У меня есть набор пар префикс/значение и хочу найти любое значение в этом соединении, связанное с префиксом, с которого начинается моя текущая целевая строка. (Не важно, чтобы поведение определялось в случае, когда соответствует более одного префикса, поскольку характер моего варианта использования таков, что это никогда не должно происходить).

Ниже приведена наивная (рабочая) реализация:

(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 наиболее подходят для задачи. Предложения?

Ответ 1

Эффективный, кропотливый подход заключается в использовании 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")))))

Ответ 2

Как насчет trie?

(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

Ответ 3

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

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

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

Ответ 4

Следующее решение находит самый длинный совпадающий префикс и работает на удивление хорошо, когда карта огромна, а строки относительно короткие. Он пытается сопоставить, например. "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