在Lua中快速实施BWT

Question

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) --sorter for tables 
    for i=1,#tA do 
     if tA[i]~=tB[i] then 
      return tA[i]<tB[i] 
     end 
    end 
    return false 
end 

function fBWT(tData) 

    --setup-- 
    local iSize = #tData 
    local tSolution = {} 
    local tSolved = {} 


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


    --encode output-- 
    for i=1,iSize do 
     tSolved[i] = tSolution[i][iSize] 
    end 


    --finalize-- 
    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功能之上加入了这两个功能。

Answer 1

如果我看对，你的算法的复杂性为O(n^2 log n)，如果排序是快速排序。比较器功能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; 
} 

这是我几年前想出的基本思想，哪些为我工作。让我知道如果有什么不清楚或有一些错误。