Data Structures (Spell Checker Implementation in Pascal from April 1999)

{Program Created By:      Dan Piehl     4/30/99 }

{ Overview:  This program creates a trie structure based on words in the input
  dictionary file.  The document file will be checked based on this trie and the
  words in the document which are not identified as valid words (or spelled correctly)
  will be listed on the screen.  Upper/lower case will be ignored and the trie
  is handled case insensitive.  Since I did not bring my book to the computer lab,
  I have just typed some simple sentences in the files.  You may substitute
  the correct file if you wish.  Sorry for the inconvenience. }


Program Main;

uses WinCrt;




{**********  Object Declarations **************}


Type
  NodePtr=^Node;        {Define Node Pointer}

  Node=Object           {NODE OBJECT}
    NextLetter : array[0..26] of NodePtr;
    Constructor Init;
  end;

  Trie=Object           {TRIE OBJECT}
    Root : NodePtr;
    Constructor Init;
  end;


{Implementation}
Constructor Node.Init;
var
  I : integer;

Begin
  For I := 0 to 26 Do   {Loop thru number of times needed}
    NextLetter[I] := nil;

End;

Constructor Trie.Init;
Var
   TempNode : NodePtr;
Begin
  New(TempNode,Init);
  Root := TempNode;
End;




{*** Node Insertion Procedure ***}
{This procedure will attempt to insert a trie node, if needed}

Procedure AddWord(Word : String; TrieRoot :  NodePtr);
Var
  Current : NodePtr;
  TempNode : NodePtr;
  CharCode : Integer;
  I : Integer;
Begin
  Current := TrieRoot;
  For I := 1 to Length(Word) Do   {Loop thru number of times needed}
    Begin
      CharCode := ord(Word[I])-64;
      if CharCode<0 then CharCode:=0;            {Check lower bound}
      if CharCode>32 then CharCode:=CharCode-32; {Ignore lower case bit}
      if Current^.NextLetter[CharCode] = nil Then
        Begin
          New(TempNode,Init);
          Current^.NextLetter[CharCode]:=TempNode;
        end;
      Current := Current^.NextLetter[CharCode]
    end;
  Current^.NextLetter[0] := Current;  {Make sure node points to itself}
End;



{*** Spell Checking Procedure ***}
{This procedure will attempt to locate a trie node}

Function CheckWord(Word : String; TrieRoot : NodePtr) : boolean;
Var
  Current : NodePtr;
  CharCode : Integer;
  I : Integer;
Begin
  Current := TrieRoot;
  I:=0;
  While (Current<>nil) and (I<Length(Word)) Do
    Begin
      I:=I+1;
      CharCode:=ord(Word[I])-64;
      if CharCode<0 then CharCode:=0;            {Check lower bound}
      if CharCode>32 then CharCode:=CharCode-32; {Ignore lower case bit}
      Current := Current^.NextLetter[CharCode];
    end;
  if Current=nil then
    CheckWord:=false
  else if Current^.NextLetter[0]=Current then
    CheckWord:=True
  else
    CheckWord:=false;
End;




{*********** Main Program **********}
Var
  T : Trie;     {Trie being used for testing}
  I : Integer;  {Miscellaneous loop counter}
  X : Integer;  {Next number to be inserted}
  W : String;   {Word variable}
  C :  Char;
  DictionaryFile,
  DocumentFile : Text;


Begin
  Assign(DictionaryFile,'a:\trie_dct.dat');
  Assign(DocumentFile,'a:\trie_doc.dat');
  Reset(DictionaryFile);
  Reset(DocumentFile);
  T.Init;       {Start with an empty tree}


  {Read Dictionary File and Build Trie}
  W:='';
  While Not Eof (DictionaryFile) do
    Begin
      Read(DictionaryFile,C);
      if ((ord(C)>=65) and (ord(C)<=90))
         or ((ord(C)>=97) and (ord(C)<=122)) then
        W := Concat(W,C)
      else
        Begin
          if Length(W)>0 then AddWord(W,T.Root);
          W:='';
        end;
    End;


  {Read Document File and Check Spelling}
  Writeln('Spell Check List of Words not in Dictionary:');
  W:='';
  While Not Eof (DocumentFile) do
    Begin
      Read(DocumentFile,C);
      if ((ord(C)>=65) and (ord(C)<=90))
         or ((ord(C)>=97) and (ord(C)<=122)) then
        W := Concat(W,C)
      else
        Begin
          if Length(W)>0 then
             if Not CheckWord(W,T.Root) then
               Writeln (W);
          W:='';
        end;
    End;



end.