clojure: determinazione efficiente se una stringa inizia con qualsiasi prefisso in una raccolta

Question

Ho una collezione di coppie prefisso/valore e desidero trovare qualsiasi valore in questa connessione associato a un prefisso con cui inizia la mia attuale stringa di destinazione. (Non è importante che il comportamento sia definito nel caso in cui più di un prefisso corrisponda, poiché la natura del mio caso d'uso è tale che questo non dovrebbe mai verificarsi).

A naive (di lavoro) attuazione segue:

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

Tale che:

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

Questo funziona come previsto, ma è O (n) con la lunghezza della sequenza pairs. (Anche l'inserimento rapido in pairs è auspicabile, ma non così importante come la ricerca rapida).

La prima cosa che viene in mente è bisecare una raccolta ordinata con un accesso casuale efficiente, ma non sono sicuro quali strutture dati in Clojure siano più adatte all'attività. Suggerimenti?

Answer 1

Un approccio efficiente e teso è quello di sfruttare il numero rsubseq, che funziona su qualsiasi tipo che implementa clojure.lang.Sorted - che include 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))) 

Questo passa i relativi test nella mia suite:

(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

Che ne dici di un 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))))) 

Usage:

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

Sembra più semplice per trasformare solo l'elenco dei prefissi in un'espressione regolare, e nutrire chi in un matcher regex, che è ottimizzato proprio per questo tipo di compito. Qualcosa di simile

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

dovrebbe ottenere una regex adatto per essere esaminati in una stringa (ma non l'ho provato a tutti, quindi forse ho ottenuto alcuni nomi di metodo sbagliato o qualcosa del genere).

Answer 4

La seguente soluzione trova il prefisso corrispondente più lungo e funziona sorprendentemente bene quando la mappa è enorme e le stringhe sono relativamente brevi. Prova ad abbinare per es. "foobar", "fooba", "foob", "foo", "fo", "f" nell'ordine e restituisce la prima corrispondenza.

(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