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

私が正しく見れば、ソートがquicksortの場合、アルゴリズムの複雑さは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); 
    }  
} 

最後のステップは、あなた自身のコンパレータの元と同様の機能（が、に取り組んでいます

/** 
* 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; 
} 

これは私が数年前に思いついた、私のために働いた基本的な考えです。明確でないものや間違いがあるかどうかを教えてください。