Geek asks and answers

How do Suffix trees work?

I will talk about the head of the data structure in the Algorithm Design Guide and stumbled upon suffix trees.

The example indicates:

Input:

XYZXYZ$
 YZXYZ$
  ZXYZ$
   XYZ$
    YZ$
     Z$
      $

Conclusion:

enter image description here

I cannot understand how this tree is generated from a given input string. Suffix trees are used to find a given substring in a given string, but how does this tree help with this? I understand the other trie example below, shown below, but if below the trie is compressed to a suffix tree, then how does it look?

enter image description here

+5
source share
3 answers

, , . . , , , .

, radix try, , O (n 2), .

, , trie ( ). S T T, , , T trie. , T S, - T. - trie, .

, !

+5

, .

patricia trie , . patricia trie , char , , , , node . , ($, a, e, h, i, n, r, s, t, w). .

, ?

"hen", , "h" . "h" "h" , "h" . "h" , "hen" "he" "h" , "h" , "n", "n", .

Trie:

└── (black)
    β”œβ”€β”€ (white) as
    β”œβ”€β”€ (white) e
    β”‚   β”œβ”€β”€ (white) eir
    β”‚   β”œβ”€β”€ (white) en
    β”‚   └── (white) ere
    β”œβ”€β”€ (white) he
    β”‚   β”œβ”€β”€ (white) heir
    β”‚   β”œβ”€β”€ (white) hen
    β”‚   └── (white) here
    β”œβ”€β”€ (white) ir
    β”œβ”€β”€ (white) n
    β”œβ”€β”€ (white) r
    β”‚   └── (white) re
    β”œβ”€β”€ (white) s
    β”œβ”€β”€ (white) the
    β”‚   β”œβ”€β”€ (white) their
    β”‚   └── (white) there
    └── (black) w
        β”œβ”€β”€ (white) was
        └── (white) when

:

String = the$their$there$was$when$
End of word character = $
└── (0)
    β”œβ”€β”€ (22) $
    β”œβ”€β”€ (25) as$
    β”œβ”€β”€ (9) e
    β”‚   β”œβ”€β”€ (10) ir$
    β”‚   β”œβ”€β”€ (32) n$
    β”‚   └── (17) re$
    β”œβ”€β”€ (7) he
    β”‚   β”œβ”€β”€ (2) $
    β”‚   β”œβ”€β”€ (8) ir$
    β”‚   β”œβ”€β”€ (31) n$
    β”‚   └── (16) re$
    β”œβ”€β”€ (11) ir$
    β”œβ”€β”€ (33) n$
    β”œβ”€β”€ (18) r
    β”‚   β”œβ”€β”€ (12) $
    β”‚   └── (19) e$
    β”œβ”€β”€ (26) s$
    β”œβ”€β”€ (5) the
    β”‚   β”œβ”€β”€ (1) $
    β”‚   β”œβ”€β”€ (6) ir$
    β”‚   └── (15) re$
    └── (29) w
        β”œβ”€β”€ (24) as$
        └── (30) hen$
+1

The suffix tree basically just squeezes the letter runs together when there is no choice. For example, if you look at the right side three in your question, after you see w, there are actually only two options: wasand when. The trie asin wasand henin wheneach of them still has one node for each letter. In the suffix tree, you merge them into two nodes, holding asand hen, so the right side of your trie will turn into:

enter image description here

0
source

More articles:


All Articles