Compact pat trees
David Richard Clark · 1998
Given a text string $S = \sb{s\sb1s\sb2s\sb3\... s\sb{n}},$ we want to preprocess S such that given a pattern $P = p\sb1p\sb2p\sb3\... p\sb{m},$ we can find $\{i\vert s\sb{i\... s\sb{i+m-1}} = P\}$ as efficiently as possible. Suffix trees are a data structure solution to this problem. Unfortunately, when n is large, the storage required by a suffix tree can be prohibitive. This thesis presents several related new representations for a close relative of the suffix tree, the PAT tree, that retain the functionality of suffix trees while requiring a fraction of the storage used by current methods.