lisp - 根据 Lisp 中的字符匹配对列表进行排序

Question

根据拼写中的常用字符计算并返回候选列表。

例如， 如果列表是:(团队比他们更年轻) 你在函数中提供参数(“thim”) 然后它应该根据列表中常见字符的相似性对列表进行排序。 它应该返回:(THEM TIME TEAM THAN TOWN TEEN) 由于 THEM 与“thim”有更多的共性，所以它排在前面，依此类推。

我的尝试:

       (defun correctSX_SIM(word)

        (setf w (correctSX word))  ; w is list of words.
        (sort w #'eq :key #'car)

       )

我知道我的回答有偏差。但是我需要 LISP 方面的帮助，因为我不了解 LISP 的所有内置功能。<​​/p>

Answer 1

首先，为已知单词列表定义一个特殊变量:

(defparameter *dictionary* '(TEAM TEEN THAN THEM THEN TIME TOWN))

您必须为满足您要求的单词定义一个距离 函数。如果我没记错的话，以下应该有效:

(defun distance (u v)
  (- (length (intersection (coerce u 'list)
                           (coerce v 'list)))))

我们查看两个字符串中共同元素的数量并将其取反，因此共享最大元素数量的元素得分最低。我不知道这是否重要，但相同的长字符串比相同的短字符串的得分低。

根据您的要求，您需要进行稳定排序，使与所选词距离相同的词保持其相对顺序。这也是我使用严格 #'< 的原因比较函数:当比较两个词a和b与输入的距离相等时，比较返回nil对于 a < b 和 b < a，允许 STABLE-SORT 知道 a 和 b 是等价的 w.r.t.偏序。 另请注意，我使用 COPY-LIST 以避免改变字典。对于您的示例，实际排序如下:

(stable-sort (copy-list *dictionary*) 
             #'< 
             :key (lambda (e) (distance "THIM" (string e))))

=> (them time team than then teen town)

结果与您的示例略有不同，但我认为它符合 your comment : THAN 应该出现在 THEN 之前，因为 (i) 在这种情况下距离相同，并且 (ii) 它们在原始列表中按该顺序出现。

正如@jkiiski 在评论中指出的那样，每次比较可能会调用一次距离函数(即 O(n.log(n)))。在我看来，在那种特殊情况下，距离函数非常便宜，但是对于大型数据集和更复杂的距离，缓存中间结果肯定会有所返回。您至少有两个选择:

• 定义另一个缓存已知结果的距离函数 (memoization)。这种方法的优点是您在排序部分和距离函数之间保持严格的分离。这应该足够了:

  (ql:quickload :memoize)
  (org.tfeb.hax.memoize:memoize-function 'distance
                                         :key #'identity
                                         :test #'equal)
  

• 将距离预先计算到另一个包含 (distance string) 的列表中对，按照第一个元素排序。然后，提取所有第二个元素以获得一个字符串序列。显然这被称为 Schwartzian transform (感谢 Svante)。这里整个过程更明确一点:

  (defun sorted-dictionary (input-word)
    (let ((list
            (stable-sort
              (loop for word in *dictionary*
                    collect (cons 
                              (distance input-word (string word))
                              word))
               #'<
               :key #'car)))
      (map-into list #'cdr list)))
  

但是有一个主要区别:使用memoized 版本，您可以在不同的排序调用中保留已知结果(除非您明确清除它们)，而使用sorted-dictionary，一旦计算出结果列表，您就会丢弃中间距离。