2 
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 関数の上にも両方を含めました。

4

1 に答える 1

0

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

これは私が数年前に思いついた基本的なアイデアであり、私にとってはうまくいきました. 不明な点や間違いがあれば教えてください。

于 2016-05-14T20:39:43.030 に答える