Unit SS, Part A: PAT, PAT Trees

Key definitions

• Sistrings (semi-infinite strings)
  • Lexicographic sistring ordering
    • "A SA..." < "AMP..." < "E ST..."
  • ID = position (e.g., 2 for "his is...")
• PAT tree = Patricia tree of all sistrings in a text

String to sistrings - example

01 - THIS IS A SAMPLE STRING

02 - HIS IS A SAMPLE STRING

03 - IS IS A SAMPLE STRING

04 - S IS A SAMPLE STRING

06 - IS A SAMPLE STRING

07 - S A SAMPLE STRING

09 - A SAMPLE STRING

11 - SAMPLE STRING

12 - AMPLE STRING

13 - MPLE STRING

...

18 - STRING

Patricia tree

• Binary digital tree
• n external nodes with key values
• n-1 internal nodes
  • indicates bit for branching (count of bits to skip or absolute bit position)