Spell Checking

April 17, 2009

Spell checkers are ubiquitous. Word processors have spell checkers, as do browser-based e-mail clients. They all work the same way: a dictionary is stored in some data structure, then each word of input is submitted to a search in the data structure, and those that fail are flagged as spelling errors. There is a certain art to building the word list on which a spell checker is based; Exxon isn’t a word in anybody’s dictionary, but it is likely included in the word list, but cwm (a geological structure), which is certainly a word, is most likely omitted from the word list, on the grounds it is more likely an error than a legitimate spelling (unless you are a geologist).

There are many appropriate data structures to store the word list, including a sorted array accessed via binary search, a hash table, or a bloom filter. In this exercise you are challenged to store the word list character-by-character in a trie. Consider this sample trie that stores the words CAR, CART, CAT and DOG:

trie

To see that CAT is a valid spelling, follow the C branch, then the A branch, then the T branch, where you find a filled circle, indicating a word. To see that CAB is not a valid spelling, follow the C branch, then the A branch, and fail when there is no B branch.

Tries can be very fast; for instance, to see that QARTER (a misspelling of QUARTER) is not a word, follow the Q branch, then fail when there is no A branch. This is even faster than hashing, which must read all six letters of QARTER just to compute the hash value. And tries can also be space-efficient, since space is shared between common prefixes.

Your task is to build a spell checker based on tries. When you are finished, you can read or run a suggested solution, or post your solution or discuss the exercise in the comments below.

Posted by programmingpraxis

Filed in Exercises

6 Comments »

6 Responses to “Spell Checking”

FalconNL said
April 17, 2009 at 9:53 AM
In Haskell:

import qualified Data.ByteString.Char8 as B
import Data.Trie

main = do trie <- fmap (fromList . map (flip (,) ()) . B.lines) $ B.readFile "words.txt" print $ valid trie "qarter" valid trie = flip member trie . B.pack [/sourcecode]
veer said
April 17, 2009 at 2:08 PM
In scheme :

http://codepad.org/aHBN2HbM

Eric H said

April 19, 2009 at 6:40 PM

Another in scheme:

#! /bin/sh

#| Hey Emacs, this is -*-scheme-*- code!

#$Id: v4-script-template.ss 5887 2008-12-30 18:12:50Z erich $

exec  mzscheme -l errortrace –require "$0" –main — ${1+"$@"}

|#

#lang scheme

(require "trie.ss"

         (planet schematics/schemeunit:3)

         (planet schematics/schemeunit:3/text-ui))

(define snarf-dictionary

  (match-lambda

   [(? string? inp)

    (snarf-dictionary (build-path inp))]

   [(? path? inp)

    (fprintf (current-error-port) "Reading dictionary ~s … " inp)

    (let ((dict (call-with-input-file inp snarf-dictionary)))

      (fprintf (current-error-port) "done; ~s words~%"

               (dict-count dict))

      dict)]

   [(? input-port? inp)

    (for/fold ([dict (make-immutable-trie)])

              ([word (in-lines inp)])

              (dict-set dict word word ))]))

(define dict-tests

  (test-suite

   "dictionary"

   (let ((d (snarf-dictionary "/usr/share/dict/words")))

     (check-not-false (dict-ref d "dog"))

     (check-false     (dict-ref d "I bet this word isn't in the dictionary"))

     (printf "Hey: ~a~%"

             (for/list ((w (in-list '("sam" "Sam" "snord" "flutter" "butter" "smith" "Smith"))))

                       (cons w (dict-ref d w))))

     )))

(define trie-tests

  (test-suite

   "top"

   (test-case

    "tries"

    (let ((t (make-immutable-trie)))

      (check-true (trie? t))

      (check-equal? (dict-count t) 0)

      (let ((t (dict-set t "c" "The letter 'c'")))

        (check-equal? (dict-count t) 1)

        (check-equal? (dict-ref t "c") "The letter 'c'")

        (let* ((exp  "The furry 'cat'")

               (t (dict-set t "cat" exp)))

          (check-false (dict-ref t "ca" #f))

          (check-equal? (dict-count t) 2)

          (check-equal? (dict-ref t "cat") exp)

          ))

      )

    (let ((t (make-immutable-trie)))

      (check-true  (dict? t))

      (check-false (dict-ref t "cat" #f))

      (check-equal? (dict-count t) 0)

      (let ((t (dict-set t "c" 'plurgh)))

        (check-equal? (dict-ref t "c" #f) 'plurgh)

        (check-equal? (dict-count t) 1)

        (let ((t (dict-set t "cat" "hat")))

          (check-equal? (dict-ref t "cat" #f) "hat")

          (let ((t (dict-set t "cats" "mats")))

            (check-equal? (dict-ref t "cat"  #f) "hat")

            (check-equal? (dict-ref t "cats" #f) "mats")

            (check-equal? (dict-count t) 3))

          )

        )))

   dict-tests))

(provide main)

(define (main . args)

  (exit (run-tests

         trie-tests

         'verbose)))

view raw
trie-tests.ss
hosted with ❤ by GitHub

#lang scheme

(require mzlib/trace)

(define (ref t key [failure-result #f])

  (define (ref-inner t chars)

    (if (null? chars)

        (if (box? (trie-value t))

            (unbox (trie-value t))

            failure-result)

        (let ((probe (dict-ref (trie-alist t) (car chars) #f)))

          (cond

           ((not probe)

            failure-result)

           ((box? probe)

            (unbox probe))

           (#t

            (ref-inner probe

                       (cdr chars)))))))

  ;; (trace ref-inner)

  (ref-inner t (string->list key)))

;; (trace ref)

(define (set t key value)

  (define (set-inner t chars value)

    ;; chars: () => set the box

    ;; chars: (ch . rest) => lookup ch => old value; (set-inner oldvalue (cdr chars) value)

    (let ((new (make-trie '() (box-immutable value))))

      (if (null? chars)

          new

          (let ((probe (dict-ref (trie-alist t) (car chars) (make-trie '() #f))))

            (make-trie

             (dict-set (trie-alist t) (car chars)

                       (set-inner probe (cdr chars) value))

             (trie-value t))))))

  ;; (trace set-inner)

  (set-inner  t (string->list key) value))

;; (trace set)

(define (count t)

  (foldl +

         (if (box? (trie-value t))

             1

             0)

         (map (compose count cdr) (trie-alist t))))

;; (trace count)

(define (iterate-first t)

  (and (not (null? t))

       0))

;; (trace iterate-first)

(define (iterate-next t pos)

  (if (= pos (sub1 (length t)))

      #f

      (add1 pos)))

;; (trace iterate-next)

(define (iterate-key t pos)

  (car (list-ref t pos)))

;; (trace iterate-key)

(define (iterate-value t pos)

  (cdr (list-ref t pos)))

;; (trace iterate-value)

(define-struct trie

  (alist

   value ;;either #f or a box

   )

  #:property prop:dict (vector

                        ref

                        #f set

                        #f remove

                        count

                        iterate-first iterate-next

                        iterate-key iterate-value)

  #:transparent)

(provide make-immutable-trie trie?)

(define (make-immutable-trie)

  (make-trie '() #f))

view raw
trie.ss
hosted with ❤ by GitHub

Vikas Tandi said
April 23, 2011 at 5:59 AM
implemented in c language:
http://codepad.org/PmYVlSN6
ftt said
November 19, 2018 at 10:19 PM
In Rust:

https://gist.github.com/ftt/1e22d9f7873eb955455b11bfee503cf4.js
ftt said
November 19, 2018 at 10:20 PM
Sorry, bad link above :( https://gist.github.com/ftt/1e22d9f7873eb955455b11bfee503cf4

S	M	T	W	T	F	S
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30

Programming Praxis

Spell Checking

April 17, 2009

6 Responses to “Spell Checking”

Leave a Reply Cancel reply

Categories

Archives

Archives

Blogroll

	#! /bin/sh
	#\| Hey Emacs, this is --scheme-- code!
	#$Id: v4-script-template.ss 5887 2008-12-30 18:12:50Z erich $
	exec mzscheme -l errortrace –require "$0" –main — ${1+"$@"}
	\|#

	#lang scheme

	(require "trie.ss"
	(planet schematics/schemeunit:3)
	(planet schematics/schemeunit:3/text-ui))

	(define snarf-dictionary
	(match-lambda

	[(? string? inp)
	(snarf-dictionary (build-path inp))]

	[(? path? inp)
	(fprintf (current-error-port) "Reading dictionary ~s … " inp)

	(let ((dict (call-with-input-file inp snarf-dictionary)))

	(fprintf (current-error-port) "done; ~s words~%"
	(dict-count dict))
	dict)]

	[(? input-port? inp)
	(for/fold ([dict (make-immutable-trie)])
	([word (in-lines inp)])
	(dict-set dict word word ))]))

	(define dict-tests
	(test-suite
	"dictionary"
	(let ((d (snarf-dictionary "/usr/share/dict/words")))
	(check-not-false (dict-ref d "dog"))
	(check-false (dict-ref d "I bet this word isn't in the dictionary"))
	(printf "Hey: ~a~%"
	(for/list ((w (in-list '("sam" "Sam" "snord" "flutter" "butter" "smith" "Smith"))))
	(cons w (dict-ref d w))))
	)))

	(define trie-tests

	(test-suite
	"top"

	(test-case
	"tries"
	(let ((t (make-immutable-trie)))
	(check-true (trie? t))
	(check-equal? (dict-count t) 0)
	(let ((t (dict-set t "c" "The letter 'c'")))
	(check-equal? (dict-count t) 1)
	(check-equal? (dict-ref t "c") "The letter 'c'")

	(let* ((exp "The furry 'cat'")
	(t (dict-set t "cat" exp)))
	(check-false (dict-ref t "ca" #f))
	(check-equal? (dict-count t) 2)
	(check-equal? (dict-ref t "cat") exp)

	))
	)

	(let ((t (make-immutable-trie)))
	(check-true (dict? t))
	(check-false (dict-ref t "cat" #f))
	(check-equal? (dict-count t) 0)
	(let ((t (dict-set t "c" 'plurgh)))
	(check-equal? (dict-ref t "c" #f) 'plurgh)
	(check-equal? (dict-count t) 1)
	(let ((t (dict-set t "cat" "hat")))
	(check-equal? (dict-ref t "cat" #f) "hat")
	(let ((t (dict-set t "cats" "mats")))
	(check-equal? (dict-ref t "cat" #f) "hat")
	(check-equal? (dict-ref t "cats" #f) "mats")
	(check-equal? (dict-count t) 3))
	)
	)))
	dict-tests))

	(provide main)
	(define (main . args)

	(exit (run-tests
	trie-tests
	'verbose)))

	#lang scheme

	(require mzlib/trace)

	(define (ref t key [failure-result #f])
	(define (ref-inner t chars)
	(if (null? chars)
	(if (box? (trie-value t))
	(unbox (trie-value t))
	failure-result)
	(let ((probe (dict-ref (trie-alist t) (car chars) #f)))
	(cond
	((not probe)
	failure-result)
	((box? probe)
	(unbox probe))
	(#t
	(ref-inner probe
	(cdr chars)))))))
	;; (trace ref-inner)
	(ref-inner t (string->list key)))
	;; (trace ref)

	(define (set t key value)

	(define (set-inner t chars value)
	;; chars: () => set the box
	;; chars: (ch . rest) => lookup ch => old value; (set-inner oldvalue (cdr chars) value)
	(let ((new (make-trie '() (box-immutable value))))
	(if (null? chars)
	new
	(let ((probe (dict-ref (trie-alist t) (car chars) (make-trie '() #f))))
	(make-trie
	(dict-set (trie-alist t) (car chars)
	(set-inner probe (cdr chars) value))
	(trie-value t))))))
	;; (trace set-inner)
	(set-inner t (string->list key) value))

	;; (trace set)

	(define (count t)
	(foldl +
	(if (box? (trie-value t))
	1
	0)
	(map (compose count cdr) (trie-alist t))))

	;; (trace count)

	(define (iterate-first t)
	(and (not (null? t))
	0))
	;; (trace iterate-first)

	(define (iterate-next t pos)
	(if (= pos (sub1 (length t)))
	#f
	(add1 pos)))
	;; (trace iterate-next)

	(define (iterate-key t pos)
	(car (list-ref t pos)))
	;; (trace iterate-key)

	(define (iterate-value t pos)
	(cdr (list-ref t pos)))
	;; (trace iterate-value)

	(define-struct trie
	(alist
	value ;;either #f or a box
	)
	#:property prop:dict (vector
	ref
	#f set
	#f remove
	count
	iterate-first iterate-next
	iterate-key iterate-value)
	#:transparent)

	(provide make-immutable-trie trie?)
	(define (make-immutable-trie)
	(make-trie '() #f))

Programming Praxis

Spell Checking

April 17, 2009

Share this:

Like this:

Related

6 Responses to “Spell Checking”

Leave a Reply Cancel reply

Categories

Archives

Archives

Blogroll