在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; 
} 

這是我幾年前想出的基本思想，哪些爲我工作。讓我知道如果有什麼不清楚或有一些錯誤。