Во-первых, определить специальную переменную для списка известных слов:
(defparameter *dictionary* '(TEAM TEEN THAN THEM THEN TIME TOWN))
Вы должны определить расстояние функцию слов, который отвечает вашим требованиям. Если я не ошибаюсь, должно работать:
(defun distance (u v)
(- (length (intersection (coerce u 'list)
(coerce v 'list)))))
Мы на количество общих элементов в обеих строках и свести на нет его, так что элементы, которые разделяют максимальное количество элементов, имеют самые низкие баллы. Я не знаю, важно ли это, но длинные одинаковые строки имеют более низкий балл, чем короткие идентичные.
Основываясь на ваших требованиях, вам необходимо выполнить устойчивую сортировку, чтобы слова, находящиеся на одинаковом расстоянии от выбранного слова, сохраняли относительный порядок. Это также, почему я использую строгую функцию #'< сравнения: при сравнении двух слов и б, имеющие равное расстояние до ввода, сравнение возвращает nil для обоих < б и б <, позволяя STABLE-SORT знать, что a и b эквивалентны по частичный порядок. Обратите внимание, что я использую COPY-LIST, чтобы избежать изменения словаря. Фактическая сортировка выполняется следующим образом для примера:
(stable-sort (copy-list *dictionary*)
#'<
:key (lambda (e) (distance "THIM" (string e))))
=> (them time team than then teen town)
результат немного отличается от вашего примера, но я думаю, что это соответствует your comment: ЧЕМ должны прийти до ТОГДА потому что (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 версии, вы сохраняете известные результаты для разных призываний сорта (если вы явно ясно их), тогда как с сортированным-словарем вы отбрасываете промежуточные расстояния после вычисления результирующего списка.
Вы не должны использовать 'levenshtein: distance' as: KEY, потому что ключевая функция вызывается каждый раз, когда' sort' производит сравнение (я предполагаю, что она зависит от реализации, но на SBCL в этом случае она называется 19 раз). Вероятно, лучше отобразить список в conses, который имеет расстояние, а затем использовать '# 'car' как: KEY. – jkiiski
@jkiiski Похоже, что CLHS не предписывает, как называется ключевая функция, так что «один раз и помнить» или «каждый раз» являются абсолютно допустимыми. Тем не менее, выполняя сопоставление, возвращаем элемент '(cons (key element))', затем сортируем, используя ': key # 'car' и заканчивая' (mapcar #' cdr ...) 'гарантируется только вызов (дорогой) ключ один раз на элемент. – Vatine
Этот шаблон (украсить, сортировать, undecorate) имеет имя, кстати: преобразование Шварца. – Svante