spellcheck.lisp

;; This is based on the solution given here http://programmingpraxis.com/2009/04/21/probabilistic-spell-checking/2/
;; just ported to common lisp

(defvar *k* 7)
(defvar *m* 1000000)

(defvar *bloom* (make-array *m* :initial-element nil))

(defun key (i word)
  (let* ((c (string (code-char (+ i 96))))
         (s (concatenate 'string c (string-downcase word) c)))
    (mod (string-hash s) *m*)))

(defun read-words-file (path)
  (with-open-file (stream path)
    (do ((word (read-line stream nil)
               (read-line stream nil)))
        ((null word))
      (do ((i 0 (+ i 1))) ((= i *k*))
        (setf (elt *bloom* (key i word)) t)))))
      ;(print word))))
      
(defun spell (word)
  (loop for i from 0 to (1- *k*)  always (elt *bloom* (key i word))))

(defun string-hash (str)
  (defun sh (s v)
    (cond
     ((equal s "") v)
     (t (sh (subseq s 1)
            (+ (* v 31) (char-code (char s 0)))))))
  (sh str 0))

(read-words-file "/usr/share/dict/words")