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 

これは、意図したとおりに動作するが、pairs配列の長さはO（n）です。 （pairsへの高速挿入も望ましいが、高速検索ほど重要ではない）。

最初に気になるのは、効率的なランダムアクセスでソートされたコレクションを二等分することですが、Clojureのどのデータ構造がタスクに最も適しているかわかりません。提案？

Answer 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"))))) 

Answer 2

トライはどうですか？

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

ちょうど、正規表現に接頭辞のリストをオンにし、タスクのまさにこの種のために最適化された正規表現マッチャー、にそれらを養うために最も簡単なようです。

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

のようなものは、あなたの文字列に対する試験に適した正規表現を取得する必要があります（私は全くそれをテストしていない、ので、多分私が間違っているか何かいくつかのメソッド名を得ました）。

Answer 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