0

我正在尝试实现 burrows Wheeler 的变换。我有一个包含索引（int）和数据（字符串）的 Dictionary 类。Dictionary 类用于构建后缀数组。我正在通过堆排序对 Dictionary 对象的后缀数组进行排序。当我有 < 10KiB 的短文本时，BWT 可以很好地使用堆排序，但是当我提供大于 100KiB 的较大文本文件时，程序会中断。我有一种感觉，我在堆排序实现中做错了。这是我在 Dictionary 类中实现的堆排序代码，其中包含两个数据成员（int 索引和字符串数据）：

void Dictionary::maxHeapify(Dictionary *obj, int size, int i){
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    Dictionary tmp;

    while (left < size && strCmp(obj[left].data, obj[largest].data) > 0){
        largest = left;
    }

    while (right < size && strCmp(obj[right].data, obj[largest].data) > 0){
        largest = right;
    }

    if (largest != i){
        // Swap
        tmp = obj[i];
        obj[i] = obj[largest];
        obj[largest] = tmp;
        maxHeapify(obj, size, largest);
    }
}

void Dictionary::heapSort(Dictionary *obj, int size){
    Dictionary tmp;
    for (int i = size/2-1; i >= 0; i--){
        maxHeapify(obj, size, i);
    }

    for (int i = size-1; i > 0; i--){
        // Swap
        tmp = obj[0];
        obj[0] = obj[i];
        obj[i] = tmp;
        maxHeapify(obj, i, 0);
    }
}

节点：如果需要，我将提供 BWT 类代码。

编辑：这是 BWT 类代码：

class BWT {
private:

    string input;
    int size;

public:

    BWT(string input, int size){
        this->input = input;
        this->size = size;
    }

    string bwt(){
        Dictionary *dict = new Dictionary[size];
        Dictionary *a;

        for (int i = 0; i < size; i++){
            dict[i].index = i;
            for (int j = i; j <= size; j++){
                dict[i].data += input[j];
            }
        }

        a.heapSort(dict, size);

        string bwt;
        for (int i = 0; i < size; i++){
            int x = dict[i].index - 1;
            if (x < 0){
                x += size;
            }
            bwt += input[x];
        }
        bwt += '\0';
        return bwt;
    }
};
4

0 回答 0