4

对不起，标题令人费解，我尽力使它有意识。好吧，如果您有更好的想法，请更改它！

不要让您感到困惑，这是Emacs Lisp loop，而不是 Common Lisp：

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

这会将 alist 转换为由哈希表组成的树，其中每个表都包含键，这些键是我稍后要搜索和替换的字符串的字符。这需要优化在大量文本中搜索具有可能相似前缀的多个键，然后用相应的键替换它们。

问题是，在内部循环中，我想初始化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

由于您明确提到重构是一种潜在的选择，我建议将您的函数组合的两个操作分开：创建 trie 并将元素插入到 trie 中。

如果您将尝试定义为更模块化的数据结构，您可以例如从以下两个函数开始：

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

（如您所见，我在这里建议使用递归而不是嵌套loop的 s - 这可能是个人喜好问题，但在我看来，这使代码更简单、更清晰。）

接下来，您可能想要添加诸如trie-getor之类的函数trie-remove。

使用此代码，将 alist 转换为 trie 成为创建新 trie 然后使用上述函数将所有元素插入其中的组合：

(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

请注意，trie.el在 Elisp 中已经有一个实现一般尝试的包（免责声明：我是包作者）。它已经存在好几年了，并且在最近的 Emacsen 中可以从 GNU ELPA 获得。或者可以从包的网页下载。

默认情况下，它使用 AVL 树作为尝试的底层数据结构，而不是哈希表。但是您可以在创建 trie 时指定不同的底层数据结构。所有标准的 trie 搜索（加上一些额外的）都已实现，并且与底层数据结构无关。

这不会直接回答您的问题，但可能会节省您的工作量。

于 2013-04-30T03:31:39.097 回答
1

我不确定我是否理解它，但在 Common Lisp 中我会这样做：

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