home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / 2360 < prev    next >
Encoding:
Text File  |  1992-11-08  |  1.4 KB  |  37 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!ukma!darwin.sura.net!max.fiu.edu!serss0!richard
  3. From: richard@serss0 (Richard A Simm)
  4. Subject: compressed trie table
  5. Organization: Florida International University, Miami
  6. Date: Fri, 6 Nov 1992 20:29:42 GMT
  7. Message-ID: <BxBA9J.Dz3@fiu.edu>
  8. Sender: news@fiu.edu (Usenet Administrator)
  9. Lines: 26
  10.  
  11. In the latest 'Software, Practice & Experience', an article is presented
  12. detailing a new algorithm for handling tries. The new altorithm stores the
  13. trie in two one-dimensional arrays. Ambiguities are resolved in a third
  14. one-dimensional array. Apart from the sample code being buggy, I've run
  15. across a problem implementing the authors' algorithm. I want to insert
  16. the following two strings:
  17.     to
  18.     too
  19.  
  20. If these are the only two strings I want to insert, then I do the following:
  21.     to: use case 1.
  22.     too: use case 3 but a problem arises. The string 'to' will be
  23.          inserted in the BASE array. Because of this, I can no
  24.          longer recognize the string 'to'. I can make a special case
  25.          of one string being a subset of another in which case the
  26.          shorter string would have a 0 tacked on to the end (like a
  27.          C-style string) and then perform X_CHECK (1,'o'). The node
  28.          returned by X_CHECK would then be used to help match 'to'
  29.          by having as its value -1 to signal the end of the string.
  30.          The reason for doing XHECK(1,'o') is so we have BASE[1] > 0.
  31.  
  32.  
  33. Any other ideas?
  34.  
  35.  
  36. Albert Chin    richard@serss0.fiu.edu
  37.