[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/zUt3Ezz1    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Apr 20:
; probabilistic spell checking

(define (string-hash str)
  (let loop ((cs (string->list str)) (s 0))
    (if (null? cs) s
      (loop (cdr cs) (+ (* s 31)
        (char->integer (car cs)))))))

(define (read-line . port)
  (define (eat p c)
    (if (and (not (eof-object? (peek-char p)))
             (char=? (peek-char p) c))
        (read-char p)))
  (let ((p (if (null? port) (current-input-port) (car port))))
    (let loop ((c (read-char p)) (line '()))
      (cond ((eof-object? c) (if (null? line) c (list->string (reverse line))))
            ((char=? #\newline c) (eat p #\return) (list->string (reverse line)))
            ((char=? #\return c) (eat p #\newline) (list->string (reverse line)))
            (else (loop (read-char p) (cons c line)))))))

(define (string-downcase str)
  (list->string
    (map char-downcase
      (string->list str))))

(define k 7)

(define m 1000000)

(define bloom (make-vector m #f))

(define (key i word)
  (let* ((c (string (integer->char (+ i 96))))
         (s (string-append c (string-downcase word) c)))
    (modulo (string-hash s) m)))

(with-input-from-file "/usr/dict/words"
  (lambda ()
    (do ((word (read-line) (read-line))) ((eof-object? word))
      (do ((i 0 (+ i 1))) ((= i k))
        (vector-set! bloom (key i word) #t)))))

(define (spell word)
  (let loop ((i 0))
    (if (= i k) #t
      (and (vector-ref bloom (key i word))
           (loop (+ i 1))))))

(display (spell "programming"))


Output:
1
with-input-from-file: cannot open input file: "/usr/dict/words" (No such file or directory; errno=2)


Create a new paste based on this one


Comments: