← Back to branch summary

~ubuntu-branches/debian/wheezy/abyss/wheezy

« back to all changes in this revision

Viewing changes to FMIndex/FMIndex.h

  • Committer: Package Import Robot
  • Author(s): Shaun Jackman
  • Date: 2012-05-31 11:39:13 UTC
  • mfrom: (1.1.5)
  • Revision ID: package-import@ubuntu.com-20120531113913-39atrfritvjevhv6
Tags: 1.3.4-1
* New upstream release.
* debian/copyright: Add CityHash, which has an Expat license.
* debian/control: Bump Standards-Version to 3.9.3.1.

Show diffs side-by-side

added added

removed removed

Lines of Context:
FMIndex/FMIndex.h
84
84
        assert(first < last);
85
85
        assert(!m_alphabet.empty());
86
86
        std::transform(first, last, first, Translate(*this));
87
 
        std::replace(first, last, SENTINEL(), T(0));
88
87
}
89
88
 
90
89
/** Decode the alphabet of [first, last). */
97
96
                *it = m_alphabet[*it];
98
97
}
99
98
 
100
 
/** Build the BWT of [first, last). */
 
99
/** Build the BWT of [first, last).
 
100
 * The BWT including the sentinel is stored in [first, last].
 
101
 * @return the position of the sentinel
 
102
 */
101
103
template<typename It>
102
104
size_type buildBWT(It first, It last) const
103
105
{
104
106
        assert(first < last);
105
107
        assert(size_t(last - first)
106
108
                        < std::numeric_limits<size_type>::max());
 
109
        encode(first, last);
 
110
        std::replace(first, last, SENTINEL(), T(0));
 
111
 
107
112
        std::cerr << "Building the Burrows-Wheeler transform...\n";
108
113
        size_t n = last - first;
109
114
        std::vector<sais_size_type> sa(n);
115
120
        assert(sentinel >= 0);
116
121
        if (sentinel < 0)
117
122
                abort();
 
123
        // Insert the sentinel.
 
124
        std::copy_backward(first + sentinel, last, last + 1);
 
125
        first[sentinel] = SENTINEL();
118
126
        return sentinel;
119
127
}
120
128
 
121
 
/** Build the BWT of [first, last) and write the result to out. */
 
129
/** Set the specified element of the sampled suffix array. */
 
130
void setSA(size_t sai, size_t pos)
 
131
{
 
132
        if (sai % m_sampleSA == 0) {
 
133
                size_t i = sai / m_sampleSA;
 
134
                assert(i < m_sa.size());
 
135
                m_sa[i] = pos;
 
136
        }
 
137
}
 
138
 
 
139
/** Construct the suffix array from the FM index. */
 
140
void constructSuffixArray()
 
141
{
 
142
        // The length of the original string.
 
143
        size_t n = m_occ.size() - 1;
 
144
        assert(n > 0);
 
145
        assert(m_sampleSA > 0);
 
146
        m_sa.resize(n / m_sampleSA + 1);
 
147
        size_t sai = 0;
 
148
        for (size_t i = n; i > 0; i--) {
 
149
                setSA(sai, i);
 
150
                T c = m_occ.at(sai);
 
151
                assert(c != SENTINEL());
 
152
                sai = m_cf[c] + m_occ.rank(c, sai);
 
153
                assert(sai > 0);
 
154
        }
 
155
        setSA(sai, 0);
 
156
}
 
157
 
 
158
/** Build an FM-index of the specified BWT. */
122
159
template<typename It>
123
 
std::ostream& buildBWT(It first, It last, std::ostream& out) const
 
160
void assignBWT(It first, It last)
124
161
{
125
 
        assert(first < last);
126
 
        assert(out);
127
 
 
128
 
        // Construct the BWT.
129
 
        encode(first, last);
130
 
        sais_size_type sentinel = buildBWT(first, last);
131
 
        assert(sentinel <= last - first);
132
 
        decode(first, last);
133
 
 
134
 
        // Output the BWT.
135
 
        out.write(reinterpret_cast<char*>(&first[0]),
136
 
                        sentinel);
137
 
        out.put('\0');
138
 
        out.write(reinterpret_cast<char*>(&first[sentinel]),
139
 
                        last - first - sentinel);
140
 
        assert(out);
141
 
        return out;
 
162
        assert(last - first > 1);
 
163
        assert(size_t(last - first)
 
164
                        < std::numeric_limits<size_type>::max());
 
165
 
 
166
        std::cerr << "Building the character occurrence table...\n";
 
167
        m_occ.assign(first, last);
 
168
        countOccurrences();
 
169
 
 
170
        // Construct the suffix array from the FM index.
 
171
        std::cerr << "Building the suffix array...\n";
 
172
        constructSuffixArray();
142
173
}
143
174
 
144
175
/** Build an FM-index of the specified data. */
150
181
                        < std::numeric_limits<size_type>::max());
151
182
 
152
183
        encode(first, last);
 
184
        std::replace(first, last, SENTINEL(), T(0));
153
185
 
154
186
        // Construct the suffix array.
155
187
        std::cerr << "Building the suffix array...\n";
175
207
                bwt[i] = m_sa[i] == 0 ? SENTINEL() : first[m_sa[i] - 1];
176
208
 
177
209
        std::cerr << "Building the character occurrence table...\n";
178
 
        m_occ.assign(bwt);
 
210
        m_occ.assign(bwt.begin(), bwt.end());
179
211
        countOccurrences();
180
212
}
181
213
 
187
219
                return;
188
220
        assert(m_sampleSA == 1);
189
221
        m_sampleSA = period;
190
 
        if (m_sampleSA == 1)
 
222
        if (m_sampleSA == 1 || m_sa.empty())
191
223
                return;
192
224
        std::vector<size_type>::iterator out = m_sa.begin();
193
225
        for (size_t i = 0; i < m_sa.size(); i += m_sampleSA)
431
463
        return findSubstring(s.begin(), s.end(), k);
432
464
}
433
465
 
434
 
/** Set the alphabet to [first, last). */
 
466
/** Set the alphabet to [first, last).
 
467
 * The character '\0' is treated specially and not included in the
 
468
 * alphabet.
 
469
 */
435
470
template <typename It>
436
471
void setAlphabet(It first, It last)
437
472
{
442
477
                mask[*it] = true;
443
478
        }
444
479
 
 
480
        // Remove the character '\0' from the alphabet.
 
481
        mask[0] = false;
 
482
 
445
483
        m_alphabet.clear();
446
484
        m_mapping.clear();
447
485
        for (unsigned c = 0; c < mask.size(); ++c) {
499
537
        assert(in);
500
538
 
501
539
        size_t n;
502
 
        char c;
503
 
 
504
 
        in >> n;
 
540
        in >> n >> expect("\n");
505
541
        assert(in);
506
 
        c = in.get();
507
 
        assert(c == '\n');
508
542
        assert(n < std::numeric_limits<size_type>::max());
509
543
        o.m_alphabet.resize(n);
510
544
        in.read(reinterpret_cast<char*>(&o.m_alphabet[0]),
511
545
                        n * sizeof o.m_alphabet[0]);
512
546
        o.setAlphabet(o.m_alphabet.begin(), o.m_alphabet.end());
513
547
 
514
 
        in >> n;
 
548
        in >> n >> expect("\n");
515
549
        assert(in);
516
 
        c = in.get();
517
 
        assert(c == '\n');
518
550
        assert(n < std::numeric_limits<size_type>::max());
519
551
        o.m_sa.resize(n);
520
552
        in.read(reinterpret_cast<char*>(&o.m_sa[0]),