Loading ...
Sorry, an error occurred while loading the content.

Re: How to implement a prefix tree?

Expand Messages
  • nyharel
    Robert Sedgewick, the same guy who wrote my favorite algorithms book, has a paper on Ternary trees and related stuff. Check out:
    Message 1 of 3 , Oct 26, 2003
    • 0 Attachment
      Robert Sedgewick, the same guy who wrote my favorite algorithms book,
      has a paper on Ternary trees and related stuff. Check out:

      http://www.cs.princeton.edu/~rs/strings/paper.ps

      I also found a rumor that such an algorithm is already included in
      "libiberty", whatever that is; Check out:
      http://gcc.gnu.org/ml/gcc-patches/2001-04/msg00840.html

      > A more reasonable method, that I haven't tried myself but saw in
      books, is
      > ternary trees: when you have the next input character "g", you don't
      decide
      > what to do based on just one node; Instead, say the node holds a
      character "e".
      > You now go to one of three possible nodes based on whether "g" is
      smaller than,
      > equal or larger than "e". Unless you chose the "equal" case, you
      continue
      > with the same input character without going forward to the next one.
      > Check out your favorite algorithm for the ternary tree algorithm, or if
      > you can't find it ask me for a reference.
      >
      > Good luck.
      >
      > --
      > Nadav Har'El | Saturday, Oct 25 2003, 30
      Tishri 5764
      > nyh@m... |-----------------------------------------
      > Phone: +972-53-790466, ICQ 13349191 |A cat has claws ending its paws. A
      > http://nadav.harel.org.il |sentence has a pause ending its
      clause.
    Your message has been successfully submitted and would be delivered to recipients shortly.