Announcement

Collapse
No announcement yet.

Trie Tree: comments

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

  • 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.
    stanthemanstan~gmail
    Dead Theory Walking
    Range Trie Tree
    HLib ~ Free Data Container Lib ~ Arrays, Lists, Stacks, Queues, Deques, Trees, Hashes

  • #2
    Trie

    Stanley,

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

    Comment


    • #3
      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.
      How long is an idea? Write it down.

      Comment


      • #4
        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.
        stanthemanstan~gmail
        Dead Theory Walking
        Range Trie Tree
        HLib ~ Free Data Container Lib ~ Arrays, Lists, Stacks, Queues, Deques, Trees, Hashes

        Comment

        Working...
        X