lecture_notes:04-22-2011
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Last 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/10 00:22] eyliaw [Searching] |
||
|---|---|---|---|
| Line 11: | Line 11: | ||
| GOOGOL | GOOGOL | ||
| Append end character: | Append end character: | ||
| - | GOOGOL$ | + | X = 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 $GOOGOL |
| - | 4 GOL$GOO | + | 3 GOL$GOO |
| - | 1 GOOGOL$ | + | 0 GOOGOL$ |
| - | 6 L$GOOGO | + | 5 L$GOOGO |
| - | 3 OGOL$GO | + | 2 OGOL$GO |
| - | 5 OL$GOOG | + | 4 OL$GOOG |
| - | 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 | ||
| + | ===== Searching ===== | ||
| + | We can use the FM-index to find the upper and lower bounds of a substring. | ||
| + | |||
| + | C_X(a) is the number of characters lexicographically before a in X. | ||
| + | G 0 | ||
| + | L 2 | ||
| + | O 3 | ||
| + | O_X(a,i) is the number of occurrences of a in B_X[0,i]. | ||
| + | ^ i ^ B_X[0,i] ^ O_X(G,i) ^ O_X(L,i) ^ O_X(O,i) ^ | ||
| + | | 1 | L | 0 | 1 | 0 | | ||
| + | | 2 | LO | 0 | 1 | 1 | | ||
| + | | 3 | LO$ | 0 | 1 | 1 | | ||
| + | | 4 | LO$O | 0 | 1 | 2 | | ||
| + | | 5 | LO$OO | 0 | 1 | 3 | | ||
| + | | 6 | LO$OOG | 1 | 1 | 3 | | ||
| + | | 7 | LO$OOGG | 2 | 1 | 3 | | ||
| + | |||
| + | There are then two recursive formulas to find the start and end positions of a substring. | ||
| + | End R_(aW) = C(a) + O(a,R_(W) - 1) + 1 or 1 if W is the empty string | ||
| + | Start R-(aW) = C(a) + O(a,R-(W)) or (n - 1) if W is the empty string | ||
| + | Where a is the first character and W is the word. | ||
lecture_notes/04-22-2011.txt · Last modified: 2015/08/09 23:06 by 212.129.31.47
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported
