Hi Gene, this help of yours is much appreciated. Thanks a lot. On 3/15/12, Gene <[email protected]> wrote: > In case you want to play with this, here is a little program > that computes suffix trees with a simple brute force algorithm > and prints their sizes. It looks like the actual growth is > O(m^2). So my quick analysis was too conservative: > > m=1 chars=0 > m=3 chars=3 > m=6 chars=11 > m=10 chars=29 > m=15 chars=67 > m=21 chars=137 > m=28 chars=254 > m=36 chars=436 > m=45 chars=704 > m=55 chars=1082 > m=66 chars=1597 > m=78 chars=2279 > m=91 chars=3161 > m=105 chars=4279 > m=120 chars=5672 > m=136 chars=7382 > m=153 chars=9454 > m=171 chars=11936 > m=190 chars=14879 > m=210 chars=18337 > m=231 chars=22367 > m=253 chars=27029 > m=276 chars=32386 > m=300 chars=38504 > m=325 chars=45452 > m=351 chars=53302 > m=378 chars=62129 > m=406 chars=72011 > m=435 chars=83029 > m=465 chars=95267 > m=496 chars=108812 > m=528 chars=123754 > m=561 chars=140186 > m=595 chars=158204 > m=630 chars=177907 > m=666 chars=199397 > m=703 chars=222779 > m=741 chars=248161 > m=780 chars=275654 > m=820 chars=305372 > m=861 chars=337432 > m=903 chars=371954 > m=946 chars=409061 > m=990 chars=448879 > m=1035 chars=491537 > > public class SuffixTreeProblem { > > // We store strings implicitly. If there is an "a" child, > // there is an "a" edge out of the node. If dollar is > // true then this node marks the end of a suffix. > static class Node { > Node a = null, b = null; > boolean dollar = false; > } > > // Produce a string that requires a big suffix tree. > byte [] genString(int n) { > byte [] s = new byte [1 + n + n * (n + 1) / 2]; > int i = 0; > for (int in = n; in > 0; in--) { > s[i++] = 'b'; > for (int j = 0; j < in; j++) { > s[i++] = 'a'; > } > } > s[i] = '$'; > return s; > } > > // Brute force: Build the tree counting characters used. > int suffixTreeChars(byte [] s) { > Node tree = new Node(); > int n = 0; > for (int iStart = s.length - 1; iStart >= 0; --iStart) { > Node p = tree; > for (int i = iStart; ; ++i) { > if (s[i] == '$') { > p.dollar = true; > break; > } > else if (s[i] == 'a') { > if (p.a == null) { > p.a = new Node(); > ++n; > } > p = p.a; > } > else { > if (p.b == null) { > p.b = new Node(); > ++n; > } > p = p.b; > } > } > } > return n; > } > > void test() { > for (int n = 0; n < 50; ++n) { > byte [] s = genString(n); > int m = s.length; > System.out.println("m=" + m + " chars=" + > suffixTreeChars(s)); > } > } > > public static void main(String [] argv) { > new SuffixTreeProblem().test(); > } > } > > On Mar 14, 1:06 am, Gene <[email protected]> wrote: >> Let's try >> >> { reverse( $ a b a a b a a a b ... a^n b ) | n = 0,1,2,... } . >> >> Note that m = n(n+1)/2 + n = O(n^2) >> >> Think about adding suffixes to the tree from shortest to longest. >> >> So suppose you are now adding something of the form >> >> reverse( $ X a^L Y ) >> >> where L is the length of the longest run of a's and X and Y are what >> comes before and after. Well we know the length of Y is at most L >> and the length of X must be L(L-1)/2+(L-1) = L(L+1)/2 - 1 . What's >> already in the tree will match no more than 2L characters before a new >> branch occurs. The new branch will therefore have at least >> L(L+1)/2 - 1 - 2L characters. This is O(L^2). >> >> You should do the math more rigorously, but roughly you will be >> getting for the total of all branches added, >> >> sum_{L=0,1,..n} O(L^2) = O(n^3) = O(m ^ 1.5) >> >> with one character per branch. This is super-linear. >> >> On Mar 13, 12:47 am, reynald reni <[email protected]> wrote: >> >> >> >> >> >> >> >> > Construct an infinite family of strings over a fixed alphabet, where >> > the total length of the edge-labels on their suffix tree grows faster >> > than O(m), where 'm' is the length of the string. [That is, show that >> > linear time suffix tree algorithm would be impossible if edge-labels >> > were written explicitly on the edges.] > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > >
-- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
