clojure: Skuteczne określanie, czy ciąg znaków zaczyna się od dowolnego prefiksu w zbiorze

Question

Mam kolekcję par przedrostków/wartości i chciałbym znaleźć dowolną wartość w tym połączeniu powiązaną z prefiksem, od którego zaczyna się mój bieżący ciąg docelowy. (Nie jest ważne, aby zachowanie było zdefiniowane w przypadku, gdy pasuje więcej niż jeden prefiks, ponieważ natura mojego użycia jest taka, że ​​nigdy nie powinno to nastąpić).

naiwny (pracy) realizacja się następująco:

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

takie, że:

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

to działa zgodnie z założeniami, to jednak O (n), przy długości sekwencji pairs. (Szybkie wstawianie do pairs jest również pożądane, ale nie tak ważne jak szybkie wyszukiwanie).

Pierwszą rzeczą, która przychodzi na myśl, jest podzielenie posortowanej kolekcji na wydajny, losowy dostęp, ale nie jestem pewien, które struktury danych w Clojure są najbardziej odpowiednie do zadania. Propozycje?

Answer 1

Skuteczne, zwięzłe podejście polega na skorzystaniu z rsubseq, która działa na każdym typie implementującym clojure.lang.Sorted - który obejmuje 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))) 

ten przechodzi odpowiednie testy w moim apartamencie:

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

Co powiesz na 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))))) 

Zastosowanie:

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 3

Wydaje najprostszych wystarczy włączyć listę prefiksów do wyrażenia regularnego, a karmić tych, do dopasowującego regex, który jest zoptymalizowany do dokładnie tego rodzaju zadania. Coś jak

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

Jeżeli Ci regex nadaje się do testowania przeciwko ciąg (ale nie testowałem go w ogóle, więc może mam jakieś nazwy metod źle lub coś).

Answer 4

Poniżej rozwiązanie znajdzie pasujący najdłuższy prefiks i działa zaskakująco dobrze, gdy mapa jest ogromny i łańcuchy są stosunkowo krótkie. Próbuje dopasować np. "foobar", "fooba", "foob", "foo", "fo", "f" w kolejności i zwraca pierwszy mecz.

(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