基于Lisp中的字符匹配对列表进行排序

Question

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

例如,如果列表是:( TEAM TEEN THCH THEN THEN TUR)然后你在函数中提供参数("thim")然后它应该按列表中常见字符的相似性对列表进行排序.它应该返回:(那个时间团队,然后是镇上的)因为他们有更多的共同特征与"thim"所以它先行等等.

我的尝试:

       (defun correctSX_SIM(word)

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

       )

我知道我的答案已经过时了.但我需要LISP的帮助,因为我不知道LISP的所有功能.

Answer 1

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

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

您必须为符合要求的单词定义距离函数.如果我没有记错,以下应该有效:

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

我们查看两个字符串中共同的元素数量并将其否定,以便共享最大元素数量的元素具有最低分数.我不知道它是否重要,但长相同的字符串得分低于短的相同字符串.

根据您的要求,您需要执行稳定的排序,以便与所选单词保持相同距离的单词保持其相对排序.这也是为什么我使用了严格#'<的比较函数:比较两个单词时一个和b具有与输入相等的距离时,比较返回nil两个A <B和B <,允许STABLE-SORT知道一个和b是等价WRT部分订购.还要注意我COPY-LIST用来避免改变字典.对于您的示例,实际排序如下:

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

=> (them time team than then teen town)

其结果是从你的榜样略有不同,但我认为这是符合您的评论: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变换(感谢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,一旦计算出结果列表,就会丢弃中间距离.