Debian Codegraph @

README

raw
1 libdivsufsort - A lightweight suffix-sorting library.
2 -----------------------------------------------------
3
4 Introduction:
5 -------------
6
7 The libdivsufsort project provides a fast, lightweight, and robust
8 C API library to construct the suffix array and the Burrows-Wheeler
9 transformed string for any input string of a constant-size alphabet.
10
11 The suffix-sorting algorithm runs in O(n log n) worst-case time
12 using only 5n+O(1) bytes of memory space, where n is the length of
13 the input string.
14
15 The latest version of libdivsufsort is available at:
16 http://libdivsufsort.googlecode.com/
17
18
19 License:
20 --------
21
22 libdivsufsort is released under the MIT/X11 license. See the file
23 COPYING for more details.
24
25
26 APIs:
27 -----
28
29 * Data types
30 typedef int32_t saint_t;
31 typedef int32_t saidx_t;
32 typedef uint8_t sauchar_t;
33
34 * Constructs the suffix array of a given string.
35 * @param T[0..n-1] The input string.
36 * @param SA[0..n-1] The output array or suffixes.
37 * @param n The length of the given string.
38 * @return 0 if no error occurred, -1 or -2 otherwise.
39 saint_t
40 divsufsort(const sauchar_t *T, saidx_t *SA, saidx_t n);
41
42 * Constructs the burrows-wheeler transformed string of a given string.
43 * @param T[0..n-1] The input string.
44 * @param U[0..n-1] The output string. (can be T)
45 * @param A[0..n-1] The temporary array. (can be NULL)
46 * @param n The length of the given string.
47 * @return The primary index if no error occurred, -1 or -2 otherwise.
48 saidx_t
49 divbwt(const sauchar_t *T, sauchar_t *U, saidx_t *A, saidx_t n);
50
51 * Constructs the burrows-wheeler transformed string of a given string and suffix array.
52 * @param T[0..n-1] The input string.
53 * @param U[0..n-1] The output string. (can be T)
54 * @param SA[0..n-1] The suffix array. (can be NULL)
55 * @param n The length of the given string.
56 * @param idx The output primary index.
57 * @return 0 if no error occurred, -1 or -2 otherwise.
58 saint_t
59 bw_transform(const sauchar_t *T, sauchar_t *U, saidx_t *SA,
60 saidx_t n, saidx_t *idx);
61
62 * Inverse BW-transforms a given BWTed string.
63 * @param T[0..n-1] The input string.
64 * @param U[0..n-1] The output string. (can be T)
65 * @param A[0..n-1] The temporary array. (can be NULL)
66 * @param n The length of the given string.
67 * @param idx The primary index.
68 * @return 0 if no error occurred, -1 or -2 otherwise.
69 saint_t
70 inverse_bw_transform(const sauchar_t *T, sauchar_t *U,
71 saidx_t *A, saidx_t n, saidx_t idx);
72
73 * Checks the correctness of a given suffix array.
74 * @param T[0..n-1] The input string.
75 * @param SA[0..n-1] The input suffix array.
76 * @param n The length of the given string.
77 * @param verbose The verbose mode.
78 * @return 0 if no error occurred.
79 saint_t
80 sufcheck(const sauchar_t *T, const saidx_t *SA,
81 saidx_t n, saint_t verbose);
82
83 * Search for the pattern P in the string T.
84 * @param T[0..Tsize-1] The input string.
85 * @param Tsize The length of the given string.
86 * @param P[0..Psize-1] The input pattern string.
87 * @param Psize The length of the given pattern string.
88 * @param SA[0..SAsize-1] The input suffix array.
89 * @param SAsize The length of the given suffix array.
90 * @param idx The output index.
91 * @return The count of matches if no error occurred, -1 otherwise.
92 saidx_t
93 sa_search(const sauchar_t *T, saidx_t Tsize,
94 const sauchar_t *P, saidx_t Psize,
95 const saidx_t *SA, saidx_t SAsize,
96 saidx_t *idx);
97
98 * Search for the character c in the string T.
99 * @param T[0..Tsize-1] The input string.
100 * @param Tsize The length of the given string.
101 * @param SA[0..SAsize-1] The input suffix array.
102 * @param SAsize The length of the given suffix array.
103 * @param c The input character.
104 * @param idx The output index.
105 * @return The count of matches if no error occurred, -1 otherwise.
106 saidx_t
107 sa_simplesearch(const sauchar_t *T, saidx_t Tsize,
108 const saidx_t *SA, saidx_t SAsize,
109 saint_t c, saidx_t *idx);
110
111 * Returns the version string of libdivsufsort.
112 * @return the version string.
113 const char *
114 divsufsort_version(void);
115
116
117 Benchmark:
118 ------------------
119
120 = Specifications =
121 Processor: 2.66 GHz Intel Core 2 Duo E6750
122 L1 Cache: (32 Kb + 32 Kb) x 2
123 L2 Cache: 4 Mb
124 RAM: 2 Gb main memory
125 Operating system: Windows XP Home SP 3 (with Cygwin)
126 Compiler: GCC version 4.3.1
127
128 = Programs =
129 Archon4r0 kvark's sorting algorithm http://forum.compression.ru/viewtopic.php?t=352
130 BPR Bucket-Pointer Refinement algorithm http://bibiserv.techfak.uni-bielefeld.de/bpr/
131 DC Difference-Cover algorithm (v = 32) http://www.cs.helsinki.fi/juha.karkkainen/publications/cpm03.tar.gz
132 DS Deep-Shallow sorting algorithm http://www.mfn.unipmn.it/~manzini/lightweight/
133 divsufsort1 libdivsufsort version 1.2.3 http://libdivsufsort.googlecode.com/
134 divsufsort2 libdivsufsort version 2.0.0 http://libdivsufsort.googlecode.com/
135 KA Ko-Aluru algorithm http://ko.pang.cn.googlepages.com/software2
136 KS Kärkkäinen-Sanders algorithm http://www.mpi-inf.mpg.de/~sanders/programs/suffix/
137 MSufSort3 MSufSort version 3.1.1 beta http://www.michael-maniscalco.com/msufsort.htm
138 qsufsort Larsson-Sadakane algorithm http://www.larsson.dogma.net/research.html
139 sais Induced Sorting algorithm http://yuta.256.googlepages.com/sais
140
141 All programs were compiled with gcc/g++ using '-O3 -fomit-frame-pointer -DNDEBUG'
142 optimization options. The times are the average of five runs, in seconds, and were
143 measured using the standard Unix/Cygwin 'time' command. (user + system) The spaces
144 were measured using the 'memusage' command.
145
146 = Testfiles =
147 Manzini's Large Corpus http://www.mfn.unipmn.it/~manzini/lightweight/corpus/
148 The Gauntlet http://www.michael-maniscalco.com/testset/gauntlet/
149
150 = Running times =
151
152 == Manzini's Corpus ==
153 Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
154 chr22.dna 34553758 6.030 6.196 22.694 7.514 5.404 5.362 16.980 50.006 7.132 10.642 10.796
155 etext99 105277340 22.160 32.582 79.872 34.264 18.758 18.064 73.236 202.684 24.106 56.612 38.748
156 gcc-3.0.tar 86630400 13.856 20.692 61.690 35.822 10.382 10.084 40.908 135.174 14.952 40.766 20.990
157 howto 39422105 5.806 8.326 25.432 8.288 5.472 5.320 20.694 64.834 5.672 16.366 11.388
158 jdk13c 69728899 18.106 22.252 61.234 32.182 9.260 9.010 34.172 101.096 11.314 39.792 16.396
159 linux-2.4.5.tar 116254720 18.174 26.226 82.830 25.912 14.672 14.290 58.586 194.412 19.890 54.054 29.614
160 rctail96 114711151 32.490 55.826 119.026 62.502 18.500 17.914 70.072 190.562 21.060 70.456 33.248
161 rfc 116421901 20.736 35.404 91.284 29.666 16.116 15.658 64.390 196.500 17.936 61.436 32.224
162 sprot34.dat 109617186 22.832 36.720 93.122 32.096 17.894 17.404 68.084 187.594 23.352 56.946 34.092
163 w3c2 104201579 27.264 29.384 89.352 54.682 13.866 13.486 52.660 162.582 17.090 77.804 25.498
164 totals 896819039 187.454 273.608 726.536 322.928 130.324 126.592 499.782 1485.444 162.504 484.874 252.994
165
166 == The Gauntlet ==
167 Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
168 abac 200000 0.044 0.064 0.104 27.914 0.042 0.036 0.058 0.048 0.050 0.062 0.044
169 abba 10500600 3.270 5.124 10.766 30.702 1.714 1.602 2.570 7.952 3.514 15.272 1.460
170 book1x20 15375420 4.392 3.530 13.872 97.468 2.312 2.154 7.442 15.756 3.542 22.376 3.912
171 fib_s14930352 14930352 12.728 10.830 18.524 179.040 3.638 3.588 3.544 10.232 6.700 18.224 2.542
172 fss10 12078908 11.390 8.974 15.130 85.328 2.828 2.824 3.344 8.646 4.618 14.754 2.076
173 fss9 2851443 1.002 1.210 1.644 5.256 0.410 0.416 0.618 1.290 0.554 2.836 0.336
174 houston 3840000 0.344 0.708 2.226 118.960 0.118 0.128 0.520 0.744 0.242 1.230 0.238
175 paper5x80 981924 0.110 0.154 0.454 0.806 0.092 0.090 0.210 0.256 0.144 0.448 0.110
176 test1 2097152 0.332 2.132 1.108 8.680 0.268 0.280 0.376 1.066 1.302 2.762 0.202
177 test2 2097152 0.710 0.616 1.110 8.682 0.180 0.176 0.374 1.076 3.354 2.768 0.206
178 test3 2097152 0.488 213.154 1.164 1.772 0.220 0.226 0.388 1.082 0.922 3.246 0.212
179 totals 67050103 34.810 246.496 66.102 564.608 11.822 11.520 19.444 48.148 24.942 83.978 11.338
180
181 = Space (in MiBytes) =
182
183 == Manzini's Corpus ==
184 Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
185 chr22.dna 34553758 174.66 296.88 193.60 165.18 165.02 165.02 289.97 428.39 199.72 263.62 164.77
186 etext99 105277340 531.13 915.48 589.85 503.23 502.25 502.25 907.34 1305.20 604.45 803.20 502.00
187 gcc-3.0.tar 86630400 437.14 756.43 485.38 415.87 413.34 413.34 709.50 1074.01 497.79 660.94 413.09
188 howto 39422105 199.20 367.53 220.88 188.45 188.23 188.23 331.54 488.75 227.67 300.77 187.98
189 jdk13c 69728899 351.96 603.99 390.68 333.40 332.74 332.74 609.71 864.48 401.04 531.99 332.49
190 linux-2.4.5.tar 116254720 586.46 1061.83 651.36 555.76 554.60 554.60 977.81 1441.30 667.39 886.95 554.35
191 rctail96 114711151 578.68 987.64 642.71 548.32 547.24 547.24 1004.98 1422.16 658.43 875.18 546.99
192 rfc 116421901 587.30 1005.85 652.29 556.53 555.39 555.39 956.52 1443.37 668.26 888.23 555.14
193 sprot34.dat 109617186 553.01 941.95 614.17 524.03 522.95 522.95 930.06 1359.01 629.26 836.31 522.70
194 w3c2 104201579 525.71 958.37 583.82 498.09 497.12 497.12 912.00 1291.87 598.82 795.00 496.87
195 totals 896819039 4525.25 7895.95 5024.74 4288.86 4278.88 4278.88 7629.43 11118.54 5152.83 6842.19 4276.38
196 mean - 5.29 9.23 5.88 5.01 5.00 5.00 8.92 13.00 6.02 8.00 5.00
197
198 == The Gauntlet ==
199 Files Size Archon4r0 BPR DC DS divsufsort1 divsufsort2 KA KS MSufSort3 qsufsort sais
200 abac 200000 1.51 1.73 1.12 0.98 1.21 1.20 1.75 2.48 3.15 1.53 0.95
201 abba 10500600 53.43 90.19 58.83 50.21 50.32 50.32 86.20 130.18 62.09 80.11 50.07
202 book1x20 15375420 78.00 134.00 86.15 73.52 73.57 73.57 132.42 190.62 89.99 117.31 73.32
203 fib_s14930352 14930352 75.75 128.15 83.65 71.71 71.44 71.44 117.16 185.10 87.43 113.91 71.19
204 fss10 12078908 61.38 103.68 67.68 58.05 57.85 57.85 107.05 149.75 71.12 92.16 57.60
205 fss9 2851443 14.87 24.48 15.98 13.71 13.85 13.85 25.27 35.35 18.32 21.76 13.60
206 houston 3840000 19.85 36.96 21.52 18.46 18.56 18.56 28.79 47.58 23.98 29.30 18.31
207 paper5x80 981924 5.45 11.40 5.50 4.72 4.93 4.93 8.59 12.17 7.63 7.49 4.68
208 test1 2097152 11.07 82.00 11.75 10.10 10.25 10.25 18.34 25.99 14.01 16.00 10.00
209 test2 2097152 11.07 82.00 11.75 10.10 10.25 10.25 18.34 25.99 14.01 16.00 10.00
210 test3 2097152 11.07 82.00 11.75 10.05 10.25 10.25 18.34 26.00 14.63 16.00 10.12
211 totals 67050103 343.45 776.59 375.68 321.61 322.48 322.47 562.25 831.21 406.36 511.57 319.84
212 mean - 5.37 12.14 5.88 5.03 5.04 5.04 8.79 13.00 6.35 8.00 5.00
213
214
215 Algorithm:
216 ----------
217
218 libdivsufsort uses the following algorithms for suffix sorting.
219 - The improved version of Itho-Tanaka two-stage sorting algorithm. [2][6]
220 - A substring sorting/encoding technique. [1][3]
221 - Maniscalco's tandem repeat sorting algorithm. [5]
222 - Larsson-Sadakane sorting algorithm. [4]
223
224
225 References:
226 -----------
227
228 1. Stefan Burkhardt and Juha K"arkk"ainen. Fast lightweight suffix
229 array construction and checking. Proceedings of the 14th Annual
230 Symposium on Combinatorial Pattern Matching, LNCS 2676,
231 Springer, pp. 55-69, 2003.
232
233 2. Hideo Itoh and Hozumi Tanaka, An Efficient Method for in Memory
234 Construction of Suffix Arrays, Proceedings of the IEEE String
235 Processing and Information Retrieval Symposium, pp. 81-88, 1999.
236
237 3. Pang Ko and Srinivas Aluru, Space-efficient linear time
238 construction of suffix arrays, Proceedings of the 14th Annual
239 Symposium on Combinatorial Pattern Matching, pp. 200-210, 2003.
240
241 4. Jesper Larsson and Kunihiko Sadakane, Faster suffix sorting.
242 Technical report LU-CS-TR:99-214, Department of Computer
243 Science, Lund University, Sweden, 1999.
244
245 5. Michael Maniscalco, MSufSort.
246 http://www.michael-maniscalco.com/msufsort.htm
247
248 6. Yuta Mori, Short description of improved two-stage suffix sorting
249 algorithm, 2005.
250 http://homepage3.nifty.com/wpage/software/itssort.txt