Интернет магазин китайских планшетных компьютеров |
|
Компьютеры - Преобразование Барроуза Уилера - Примеры реализации23 января 2011Оглавление: 1. Преобразование Барроуза Уилера 2. Производительность BWT и алгоритмов сжатия на его основе, потребление памяти 3. Иллюстрация применения для задач сжатия 4. Примеры реализации На языке Си
#include <unistd.h>
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include <string.h>
typedef unsigned char byte;
byte *rotlexcmp_buf = NULL;
int rottexcmp_bufsize = 0;
int rotlexcmp
{
int li = *l, ri = *r, ac=rottexcmp_bufsize;
while
{
if
li = 0;
if
ri = 0;
if
return 0;
}
if
return 1;
else
return -1;
}
void bwt_encode
{
int indices;
int i;
for
indices = i;
rotlexcmp_buf = buf_in;
rottexcmp_bufsize = size;
qsort , rotlexcmp);
for
buf_out = buf_in;
for
{
if {
*primary_index = i;
return;
}
}
assert ;
}
void bwt_decode
{
byte F;
int buckets;
int i,j,k;
int indices;
for
buckets = 0;
for
buckets] ++;
for
for
F = i;
assert ;
for
{
while
j++;
buckets = j; // it will get fake values if there is no i in F, but
// that won't bring us any problems
}
for
indices]++] = i;
for
{
buf_out = buf_in;
j=indices;
}
}
int main
{
byte buf1 = "Wikipedia";
int size = strlen;
byte buf2;
byte buf3;
int primary_index;
bwt_encode ;
bwt_decode ;
assert );
printf ;
return 0;
}
Быстрое обратное преобразование на языке Python
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def BWT_decode_fast:
column = ''.join)
start = {}
for i in xrange):
if not column in start:
start] = i
links =
for c in src:
links.append
start += 1
ret = column
i = links
while i != primary:
ret += column
i = links
return ret + ret
print BWT_decode_fast
Примечание: о сортировкеЕсли вы сортируете строку используя сравнение по стандарту POSIX, то получаете слегка отличную строку на выходе: TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT вместо TEXYDST.E.XIIXIXXSMPPSS.B...S.EEUSFXDIOIIIIT ISO 8859 имеет сложные правила сравнения, но в данном случае точки игнорируются. Сравнение POSIX рассматривает точки как символы. Просмотров: 6530
|