Реализация алгоритма суффиксного массива - PullRequest
Новая
       43

Реализация алгоритма суффиксного массива

0 голосов
/ 11 декабря 2018

В настоящее время я пытаюсь реализовать обобщенный массив суффиксов в соответствии с алгоритмом, описанным в этой статье: paper .Однако в данный момент я застрял с реализацией алгоритма сортировки в главе 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;
}

Atмомент я получаю результаты мусора с моей реализацией.И я не совсем понимаю из описания алгоритма в статье, как inv_pos корректно обновляется после каждого этапа ... Если кто-то может определить, что не так с моей реализацией, и показать мне правильное направление с кратким объяснением, я был быочень благодарен.

...