Быстрая реализация BWT на Lua

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

Выше приведен мой текущий код для достижения кодирования BWT в Lua. Проблема в том, что из-за размера таблиц и длины циклов выполнение занимает много времени. Для ввода 1000 символов среднее время кодирования составляет около 1,15 секунды. Есть ли у кого-нибудь предложения по более быстрой функции кодирования BWT?

наибольшее замедление наблюдается в функциях fLexTblSort и fShallowCopy. Я также включил обе выше функции BWT.


compression lua burrows-wheeler-transform
person HDeffo    schedule 14.05.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Если я правильно понимаю, ваш алгоритм имеет сложность 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;
}

Это основная идея, которую я придумал несколько лет назад и которая сработала для меня. Дайте мне знать, если есть что-то не ясно или какая-то ошибка.

person Jakuje    schedule 14.05.2016
comment
Хотя это очень блестящее решение, оно, к сожалению, не решает проблему. ваши функции быстрой сортировки и сравнения занимают столько же времени, сколько и мои старые. Все равно спасибо за попытку помочь! Я думаю, он просто не переносится на Lua. - person HDeffo; 15.05.2016
comment
Да. Lua немного медленнее, чем C. Если вам нужна производительность, вы можете попробовать реализовать сжатие в C и экспортировать функцию в Lua. Это может стать быстрее. Также зависит от вашей реализации Lua, если она копирует таблицы снова и снова или использует единственную ссылку в качестве версии C. - person Jakuje; 15.05.2016
comment
К сожалению, использование другого языка в этом проекте невозможно. Возможно, мне просто нужно убрать кодировку BWT из моего сжатия и страдать от небольших потерь при сжатии. - person HDeffo; 15.05.2016