4

複雑なタイトルでごめんなさい、私はそれを意識させるために最善を尽くしました。さて、あなたがより良いアイデアを持っているなら、それを変えてください！

混乱しないように、これはEmacs Lisploopであり、CommonLispではありません。

(defun hxswfml-build-trie (alist)
  "Builds a trie (a list, containing number of hash-maps, each hash-map
uses single character for a key, except for `t' symbol, which, if present
as a key is the key for the value one has to substitute with."
  (loop for (key . value) in alist
        with trie = (make-hash-table)
        do (loop for c across key
                 with branch =
                 (or (gethash c trie)
                     (puthash c (make-hash-table) trie))
                 with first-time = t
                 do (if first-time (setq first-time nil)
                      (setq branch
                            (or (gethash c branch)
                                (puthash c (make-hash-table) branch))))
                 finally (puthash t value branch))
        finally (return trie)))

これにより、リストがハッシュテーブルで構成されたツリーに変換されます。各テーブルには、後で検索して置換する文字列の文字であるキーが含まれています。これは、テキストの大きな本文でおそらく同様のプレフィックスを持つ複数のキーの検索を最適化し、それぞれを対応するキーに置き換えるために必要です。

branch問題は、内側のループで初期化しtrie、その後のすべての反復で、新しいハッシュテーブル（既知のプレフィックスの一部ではない文字用に作成された）またはハッシュテーブルのいずれかに設定したいということです。これは、プレフィックスからの文字に対してすでに作成されています。

理想的には、次のようになります。

for branch = (or (and branch (gethash c branch)) (puthash c (make-hash-table) trie))
;;                    ^-----------------^------- cannot reference it here

first-timeそしてそれが私が避けられた愚かな旗を持っている理由です。どういうわけかinitiallyフォームを使用できますか、またはこのフラグとそれによる余分なものを回避するために他の方法で関数を再構築できますifか？この関数が高速であることはそれほど重要ではありませんが（検索は高速である必要がありますが、ツリーの構築は高速である必要はありません）、見た目は醜いです:)

4

4 に答える 4

3

潜在的なオプションとしてリファクタリングについて明示的に言及しているので、関数が組み合わせる2つの操作（トライの作成とトライへの要素の挿入）を分離することをお勧めします。

試行の定義をよりモジュール化されたデータ構造と見なす場合、たとえば、次の2つの関数から始めることができます。

(defun trie-create ()
  (make-hash-table :test 'equal))

(defun trie-put (key value trie)
  (if (equal key "")
      (puthash t value trie)      
    (let* ((c (substring key 0 1))
           (child-trie (gethash c trie)))
      (unless child-trie
        (setq child-trie (trie-create))
        (puthash c child-trie trie))
      (trie-put (substring key 1) value child-trie))))

（ご覧のとおり、ここではネストされたloopsの代わりに再帰を提案しています。これは好みの問題かもしれませんが、コードがいくらか単純でクリーンになるように思えます。）

trie-get次に、またはtrie-removeなどの関数を追加することをお勧めします。

このコードを使用すると、リストをトライに変換することは、新しいトライを作成し、上記の関数を使用してすべての要素をトライに挿入することの組み合わせになります。

(let ((trie (trie-create)))
  (mapc '(lambda (x) (trie-put (car x) (cdr x) trie)) alist))
于 2012-11-11T01:35:10.940 に答える
2

未テスト：

(defun hxswfml-build-trie (alist)
  "Builds a trie (a list, containing number of hash-maps, each hash-map
uses single character for a key, except for `t' symbol, which, if present
as a key is the key for the value one has to substitute with."
  (loop for (key . value) in alist
        with trie = (make-hash-table)
        for leaf = (reduce (lambda (branch c)
                             (or (gethash c branch)
                                 (puthash c (make-hash-table) branch)))
                           key :initial-value trie)
        do (puthash t value leaf)
        finally (return trie)))
于 2012-11-11T02:45:00.123 に答える
2

Elispには一般的な試行を実装するパッケージがすでにあることに注意してくださいtrie.el（免責事項：私はパッケージの作成者です）。それはもう数年前からあり、最近の十分なEmacsenでGNUELPAから入手できます。または、パッケージのWebページからダウンロードすることもできます。

ハッシュテーブルの代わりに、デフォルトで試行の基礎となるデータ構造としてAVLツリーを使用します。ただし、トライを作成するときに、異なる基になるデータ構造を指定できます。すべての標準的なトライ検索（およびいくつかの追加機能）が実装されており、基になるデータ構造に依存しません。

これはあなたの質問に直接答えることはありませんが、あなたの仕事を節約するかもしれません。

于 2013-04-30T03:31:39.097 に答える
1

私はそれを理解しているかどうかはわかりませんが、CommonLispでは次のようにします。

(loop for i = (foo) then (1+ i) ...)
于 2012-11-10T23:20:25.947 に答える