This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
lecture_notes:04-22-2011 [2011/06/08 17:07] eyliaw [Suffix array] |
lecture_notes:04-22-2011 [2011/06/08 17:14] eyliaw [Suffix array] |
||
---|---|---|---|
Line 13: | Line 13: | ||
GOOGOL$ | GOOGOL$ | ||
Cyclic transformation: | Cyclic transformation: | ||
- | 1 GOOGOL$ | + | 0 GOOGOL$ |
- | 2 OOGOL$G | + | 1 OOGOL$G |
- | 3 OGOL$GO | + | 2 OGOL$GO |
- | 4 GOL$GOO | + | 3 GOL$GOO |
- | 5 OL$GOOG | + | 4 OL$GOOG |
- | 6 L$GOOGO | + | 5 L$GOOGO |
- | 7 $GOOGOL | + | 6 $GOOGOL |
Sort: | Sort: | ||
- | 7 $GOOGOL | + | 6 $GOOGO**L** |
- | 4 GOL$GOO | + | 3 GOL$GO**O** |
- | 1 GOOGOL$ | + | 0 GOOGOL**$** |
- | 6 L$GOOGO | + | 5 L$GOOG**O** |
- | 3 OGOL$GO | + | 2 OGOL$G**O** |
- | 5 OL$GOOG | + | 4 OL$GOO**G** |
- | 2 OOGOL$G | + | 1 OOGOL$**G** |
- | + | ||
+ | S(i) = [6,3,0,5,2,4,1] | ||
+ | The Burrows Wheeler transform takes the last character of the sorted cyclic strings: | ||
+ | B(i) = LO$OOGG |