clojure: Xác định hiệu quả nếu một chuỗi bắt đầu với bất kỳ tiền tố nào trong bộ sưu tập

Question

Tôi có một tập hợp các cặp tiền tố/giá trị và muốn tìm bất kỳ giá trị nào trong kết nối này được liên kết với tiền tố mà chuỗi đích hiện tại của tôi bắt đầu. (Nó không quan trọng là hành vi được định nghĩa trong trường hợp có nhiều hơn một tiền tố khớp với nhau, vì bản chất của ca sử dụng của tôi là như vậy mà điều này sẽ không bao giờ xảy ra).

Một ngây thơ (làm việc) thực hiện sau:

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

như vậy mà:

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

này hoạt động như dự định, nhưng là O (n) với chiều dài của chuỗi pairs. (Nhanh chóng chèn vào pairs cũng là mong muốn, nhưng không quan trọng như tra cứu nhanh). Điều đầu tiên xuất hiện trong đầu là chia một bộ sưu tập được sắp xếp với truy cập ngẫu nhiên hiệu quả, nhưng tôi không chắc cấu trúc dữ liệu nào trong Clojure phù hợp nhất với nhiệm vụ. Gợi ý?

Answer 1

Cách tiếp cận hiệu quả, ngắn gọn là tận dụng lợi thế của rsubseq, hoạt động trên mọi loại triển khai clojure.lang.Sorted - bao gồm 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))) 

này vượt qua các bài kiểm tra có liên quan trong bộ tôi:

(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

Làm thế nào về một 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))))) 

Cách sử dụng:

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

Có vẻ như đơn giản nhất để chỉ cần bật danh sách các tiền tố vào một biểu thức chính quy, và thức ăn những thành một khớp regex, được tối ưu hóa cho chính xác loại này nhiệm vụ. Một cái gì đó như

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

Bạn nên dùng regex phù hợp để thử nghiệm với chuỗi (nhưng tôi có thể có một số tên phương thức sai hoặc thứ gì đó).

Answer 4

Các giải pháp sau thấy tiền tố phù hợp nhất và các công trình cũng đáng ngạc nhiên khi bản đồ là rất lớn và chuỗi là tương đối ngắn. Nó cố gắng khớp với v.d. "foobar", "fooba", "foob", "foo", "fo", "f" theo thứ tự và trả về kết quả trùng khớp đầu tiên.

(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