the running time of the suffix array computation is dominated by the sorting stepwhich uses on log comparisons in many circumstances this can be reasonably acceptable performance for instancea suffix array for , , -character english-language novel can be built in just few seconds howeverthe on log costbased on the number of comparisonshides the fact that string comparison between and takes time that depends on lcp( )so while it is true that almost all these comparisons end quickly when run on the suffixes found in natural language processingthe comparisons will be expensive in applications where there are many long common substrings one such example occurs in pattern searching of dnawhose alphabet consists of four characters (acgtand whose strings can be huge for instancethe dna string for human chromosome has roughly million characterswith maximum lcp of approximately , and an average lcp of nearly , and even the html/java distribution for jdk (much smaller than the current distributionis nearly million characterswith maximum lcp of roughly , and an average lcp of roughly , in the degenerate case of string that contains only one characterrepeated timesit is easy to see that each comparison takes (ntimeand the total cost is on log in section we will show linear-time algorithm to construct the suffix array suffix trees suffix arrays are easily searchable by binary searchbut the binary search itself automatically implies log cost what we would like to do is find matching suffix even more efficiently one idea is to store the suffixes in trie binary trie was seen in our discussion of huffman codes in section the basic idea of the trie is to store the suffixes in tree at the rootinstead of having two brancheswe would have one branch for each possible first character then at the next levelwe would have one branch for the next characterand so on at each level we are doing multiway branchingmuch like radix sortand thus we can find match in time that would depend only on the length of the match in figure we see on the left basic trie to store the suffixes of the string deed these suffixes are ddeededand eed in this trieinternal branching nodes are drawn in circlesand the suffixes that are reached are drawn in rectangles each branch is labeled with the character that is chosenbut the branch prior to completed suffix has no label this representation could waste significant space if there are many nodes that have only one child thus in figure we see an equivalent representation on the rightknown as compressed trie heresingle-branch nodes are collapsed into single node notice that although the branches now have multicharacter labelsall the labels for the branches of any given node must have unique first characters thusit is still just as easy as before to choose which branch to take thus we can see that search for patternpdepends only on the length of the pattern pas desired (we assume that the letters of the alphabet are represented by numbers then each node stores an array representing each possible branch and we can locate the appropriate branch in constant time the empty edge label can be represented by if the original string has length nthe total number of branches is less than howeverthis by itself does not mean that the compressed trie uses linear spacethe labels on the edges take up space the total length of all the labels on the compressed