Я сейчас пытаюсь реализовать обобщенный массив суффиксов в соответствии с алгоритмом, описанным в этой статье: бумага.
Однако на данный момент я застрял с реализацией алгоритм сортировки в главе 2.
Мой текущий код на C ++ выглядит примерно так (мой алфавит состоит из строчных букв английского алфавита):
std::vector<std::pair<int,int>> suffix_array(const std::vector<std::string>& ss) {
std::vector<std::vector<std::pair<int,int>>> tmp(26);
size_t n = 0;
for (size_t i = 0; i < ss.size(); i++) {
if (ss[i].length() > n) {
n = ss[i].length();
}
for (size_t j = 0; j < ss[i].length(); j++) {
tmp[ss[i][j] - 'a'].push_back(std::make_pair(i,j));
}
}
// initialize pos
std::vector<std::pair<int,int>> pos;
std::vector<bool> bh;
for (auto &v1 : tmp) {
bool b = true;
for (auto &p: v1) {
pos.push_back(p);
bh.push_back(b);
b = false;
}
}
// initialze inv_pos
std::map<std::pair<int,int>,int> inv_pos;
for (size_t i = 0; i < pos.size(); i++) {
inv_pos[pos[i]] = i;
}
int H = 1;
while (H <= n) {
std::vector<int> count(pos.size(), 0);
std::vector<bool> b2h(bh);
for (size_t i = 0, j = 0; i < pos.size(); i++) {
if (bh[i]) {
j = i;
}
inv_pos[pos[i]] = j;
}
int k = 0;
int i = 0;
while (i < pos.size()) {
int j = k;
i = j;
do {
auto t = std::make_pair(pos[i].first, pos[i].second - H);
if (t.second >= 0) {
int q = inv_pos[t];
count[q] += 1;
inv_pos[t] += (count[q] - 1);
b2h[inv_pos[t]] = true;
}
i++;
} while (i < pos.size() && !bh[i]);
k = i;
i = j;
do {
auto t = std::make_pair(pos[i].first, pos[i].second - H);
if (t.second >= 0) {
int q = inv_pos[t];
if ((j <= q) && (q < k) && (j <= (q+1)) &&
((q+1) < k) && b2h[q+1]) {
b2h[q+1] = false;
}
}
i++;
} while (i < k);
}
bh = b2h;
for (auto &x : inv_pos) {
pos[x.second] = x.first;
}
H *= 2;
}
return pos;
}
На данный момент я получаю результаты мусора с моей реализацией. И я не совсем понимаю из описания алгоритма в статье, как inv_pos
правильно обновляется после каждого этапа …
Если кто-то может определить, что не так с моей реализацией, и показать мне правильное направление с кратким объяснением, я был бы очень благодарен.
Задача ещё не решена.
Других решений пока нет …