Editierabstand oder so ähnlich

Und noch ein wenig Lisp-Code, diesmal eine Übungsaufgabe für meine Vorlesung Kognitive Systeme. Es ging darum, das Wort mit der größten Ähnlichkeit zu *word-from* aus der Liste *words-to* herauszufinden. Höherer Score bedeutet hier eine höhere Ähnlichkeit, in den Vorlesungen Info II und Info IV war das andersherum definiert (Editierabstand) und die Matrix anders initialisiert.

(defparameter *word-from* "DAABBCADBBA")
(defparameter *words-to* '("DDABCBA" "BAAATTCDBA" "DAABCCACBBA" "DAABBAABB" "AABDBCDBBC"))
(defparameter *word-to* nil)
(defparameter *matrix* nil)

(defun run ()
(declare (special *word-to*))
(dolist (*word-to* *words-to*)
(setf *matrix* (make-array (list (1+ (length *word-from*)) (1+ (length *word-to*))) :initial-element nil))
(init-matrix)
(do-score)
(show-matrix)))

(defun init-matrix ()
(dotimes (x (array-dimension *matrix* 0))
(setf (aref *matrix* x 0) 0))
(dotimes (y (array-dimension *matrix* 1))
(setf (aref *matrix* 0 y) 0)))

(defun show-matrix ()
(format t "        ")
(dotimes (x (length *word-from*))
(format t "~G   " (subseq *word-from* x (1+ x))))
(format t "~%")
(dotimes (y (array-dimension *matrix* 1))
(if (zerop y)
(format t "  ")
(format t "~G " (subseq *word-to* (1- y) y)))
(dotimes (x (array-dimension *matrix* 0))
(format t "~3D " (aref *matrix* x y)))
(format t "~%"))
(format t "~%"))

(defun score (x y)
(apply #'max
(list           (if (equal (subseq *word-from* (1- x) x)
(subseq *word-to* (1- y) y))
(+ (aref *matrix* (1- x) (1- y)) 2)
(+ (aref *matrix* (1- x) (1- y)) -1))
(+ (aref *matrix* (1- x) y) -3)
(+ (aref *matrix* x (1- y)) -2))))

(defun do-score ()
(loop for y from 1 to (length *word-to*) do
(loop for x from 1 to (length *word-from*) do
(setf (aref *matrix* x y) (score x y)))))