Lua中BWT的快速实现

2016-5-14 15:18:24
收藏：0
阅读：61
评论：1
local function fShallowCopy(tData)
    local tOutput = {}
    for k,v in ipairs(tData) do
        tOutput[k] = v
    end
    return tOutput
end

local function fLexTblSort(tA,tB) --这是用于表排序的函数
    for i=1,#tA do
        if tA[i]~=tB[i] then
            return tA[i]<tB[i]
        end
    end
    return false
end

function fBWT(tData)

    --初始化--
    local iSize = #tData
    local tSolution = {}
    local tSolved = {}

    --关键表--
    for n=1,iSize do
        tData[iSize] = fRemove(tData,1)
        tSolution[n] = fShallowCopy(tData)
    end
    table.sort(tSolution,fLexTblSort)

    --编码输出--
    for i=1,iSize do
        tSolved[i] = tSolution[i][iSize]
    end

    --完成--
    for i=1,iSize do
        if fIsEqual(tSolution[i],tData) then
            return i,tSolved
        end
    end
    return false
end

上面是我目前用 Lua 实现 BWT 编码的代码。问题在于由于表的大小和循环的长度，运行时间很长。对于一个 1000 个字符的输入，平均编码时间约为 1.15 秒。有人有更快的 BWT 编码函数的建议吗？

最大的减速似乎出现在 fLexTblSort 和 fShallowCopy 中。我已经将它们都包括在 BWT 函数的上方。

点赞
用户2196426
用户2196426

如果我没看错的话，你的算法在快速排序的情况下的复杂度是O(n^2 log n)。comparator函数fLexTblSort本身对于比较的每一对数值都需要O(n)的时间。

经过我几年前的实现检查，我发现可以改进的空间。你创建了所有可能的tData的旋转，这也需要很长时间。我只使用了单个数据块，并只存储了特定旋转的起始位置。你还使用了很多循环，可以缩小到更少。

我的实现是用C语言的，但这个概念也可以用在Lua中。这是一种在你的Lua和C之间混合的伪代码。

function fBWT(tData)

  local n = #tData
  local tSolution = {}
  for(i = 0; i < n; i++)
    tSolution[i] = i;

  --table.sort(tSolution, fLexTblSort)
  quicksort(tData, n, tSolution, 0, n)

  for(i = 0; i < n; i++){
    tSolved[i] = tData[(tSolution[i]+n-1)%n];
    if( tSolution[i] == 0 )
        I = i;
  }

  return I, tSolved
end

你还需要自己的排序函数，因为标准不提供足够的灵活性用于这种魔法。快速排序是一个不错的选择（你可能可以避免一些参数，但我只是贴上了我使用的C版本）：

void swap(int array[], int left, int right){
    int tmp = array[right];
    array[right] = array[left];
    array[left] = tmp;
}

void quicksort(uint8_t data[], int length, int array[], int left, int right){
    if(left < right){
        int boundary = left;
        for(int i = left + 1; i < right; i++){
            if( offset_compare(data, length, array, i, left) < 0 ){
                swap(array, i, ++boundary);
            }
        }
        swap(array, left, boundary);
        quicksort(data, length, array, left, boundary);
        quicksort(data, length, array, boundary + 1, right);
    }
}

最后一步是你自己的比较函数（类似于你最初的函数，但是在旋转上工作，仍然是C语言）：

/**
 *  compare one string (fixed length) with different rotations.
 */
int offset_compare(uint8_t *data, int length, int *array, int first, int second){
    int res;
    for(int i = 0; i < length; i++){
        res = data[(array[first]+i)%length] - data[(array[second]+i)%length];
        if( res != 0 ){
            return res;
        }
    }
    return 0;
}

这是我几年前想出的基本思路，对我来说工作得很好。如果有什么不清楚或错误的地方，请让我知道。

2016-05-14 20:39:43

作者:

用户3788161

用户3788161
推荐文章