Announcement

Collapse
No announcement yet.

Trie Tree: comments

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Stanley Durham
    replied
    Could indexes to a database be replaced with this if it has duplicate keys (with unique client ids?)
    This implementation is memory based.
    (can be saved to string - file)
    I'd like to make a file based Trie, but it might be over my head.
    There's a lot of fairly resent research papers and patents on file based Tries.

    To allow duplicate Keys would require another container to hold the duplicate values.

    Could binary data be used, not necessary, but curious.
    Currently, the Value is stored in an ASCIIZ string pointer.
    It could be easly modified, but it would add 4 bytes per node. (buffer len)

    I need to convert this into a PATRICIA Trie.
    A PATRICIA Trie merges nodes with only one character, into string segments.

    Leave a comment:


  • Mike Doty
    replied
    Ditto, awesome!

    Tried unzipping from PB site using WinZip and PKUNZIP (crc error) on both files.
    Did download and unzip from your site without a problem.
    Could indexes to a database be replaced with this if it has duplicate keys (with unique client ids?)
    Could binary data be used, not necessary, but curious.

    Leave a comment:


  • Guy Dombrowski
    replied
    Trie

    Stanley,

    This is awesome !
    I was thinking of writing something like that but I see you beat me to it !

    Leave a comment:


  • Stanley Durham
    started a topic Trie Tree: comments

    Trie Tree: comments

    Trie Tree: find 1,000,000 strings in 0.3 seconds

    A Trie as a tree structure that's as fast as a hash.
    So, you get the benefits of a tree and a hash.
    - blazing fast search
    - traverse in Key order

    A Trie is the fastest structure for a "prefix’ search.
    Anyone interested in adding "IntelliSense" like search to a PB editor, here you go.

    The reason a Trie is so fast, each character in the key word is the index to the child node of the next character in the key word.

    Instead of doing a string comparison, you’re doing a branch jump based on the ASC() of each character in the key word.

    As you move through each character in the key, you’re moving down the tree.

    That’s also the reason it’s so good for prefix search, once you reach the end of the prefix in the tree, every key word below there belongs to the prefix. No further comparisons necessary.
Working...
X