Burrows-Wheeler变换
Burrows–Wheeler Transform（简称BWT，也称作块排序压缩），是一个被应用在数据压缩技术（如bzip2）中的算法。该算法于1994年被Michael Burrows和David Wheeler在位于加利福尼亚州帕洛阿尔托的DEC系统研究中心发明[1]。它的基础是之前Wheeler在1983年发明的一种没有公开的转换方法。 当一个字符串用该算法转换时，算法只改变这个字符串中字符的顺序而并不改变其字符。如果原字符串有几个出现多次的子串，那么转换过的字符串上就会有一些连续重复的字符，这对压缩是很有用的。该方法能使得基于处理字符串中连续重复字符的技术（如MTF变换和游程编码）的编码更容易被压缩。 举个例子：
该算法的输出因为有更多的重复字符而更容易被压缩了。 Burrows–Wheeler变换过程算法将输入字符串的所有循环字符串按照字典序排序，并以排序后字符串形成的矩阵的最后一列为其输出。
Burrows–Wheeler变换的还原过程
经过六次排序转移与组合，还原出了原有的字符串即“$banana”。 python实现(基于next值方式)def bwt(s):
"""对字符串进行Burrows-Wheeler变换 不使用唯一字符('EOF')做标记 返回索引值列表"""
#创建所有循环字符串
table = [s[i:] + s[:i] for i in range(len(s))]
#获取排序后的结果
table_sorted = table[:]
table_sorted.sort()
#获取已排序表每个字符串在未排序表中对应字符串的下一个字符串在已排序表中的索引值
indexlist = []
for t in table_sorted:
index1 = table.index(t)
index1 = index1+1 if index1 < len(s)-1 else 0
index2 = table_sorted.index(table[index1])
indexlist.append(index2)
#取排序后结果的最后一列作为结果字符串
r = ''.join([row[-1] for row in table_sorted])
return r, indexlist
def ibwt(r,indexlist):
"""对字符串进行反Burrows-Wheeler变换 有索引值的反变换比使用唯一标记的反变换简单很多"""
s=''
x = indexlist[0]
for _ in r:
s = s + r[x]
x = indexlist[x]
return s
python实现(基于末尾添加唯一字符方式)通过在末尾添加唯一字符(不与输入字串中任何字符相同)后再进行变换，可以不需要传递索引值列表，不过逆变换的时候要做更多计算。 下面的伪代码提供了一个逆过程的朴素实现（输入字符串s为原过程之输出）： function inverseBWT(string s)
生成length（s）个空串
repeat length(s) times
将字符串s作为一列插入每个字符串的串首
对所有字符串排序
返回结尾为EOF的行
END = '\1' #必须不与原字符串中任何字符相同
def bwt(s):
"""对字符串进行Burrows-Wheeler变换"""
s = s + END
#创建所有循环字符串
table = [s[i:] + s[:i] for i in range(len(s))]
#获取排序后的结果
table_sorted = table[:]
table_sorted.sort()
#取排序后结果的最后一列作为结果字符串
return ''.join([row[-1] for row in table_sorted])
def ibwt(r):
table = [''] * len(r)
for _ in r:
table = sorted([r[m] + table[m] for m in range(len(r))])
s = [row for row in table if row.endswith(END)][0]
return s.rstrip(END)
参考资料外部链接
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Index:
pl ar de en es fr it arz nl ja pt ceb sv uk vi war zh ru af ast az bg zh-min-nan bn be ca cs cy da et el eo eu fa gl ko hi hr id he ka la lv lt hu mk ms min no nn ce uz kk ro simple sk sl sr sh fi ta tt th tg azb tr ur zh-yue hy my ace als am an hyw ban bjn map-bms ba be-tarask bcl bpy bar bs br cv nv eml hif fo fy ga gd gu hak ha hsb io ig ilo ia ie os is jv kn ht ku ckb ky mrj lb lij li lmo mai mg ml zh-classical mr xmf mzn cdo mn nap new ne frr oc mhr or as pa pnb ps pms nds crh qu sa sah sco sq scn si sd szl su sw tl shn te bug vec vo wa wuu yi yo diq bat-smg zu lad kbd ang smn ab roa-rup frp arc gn av ay bh bi bo bxr cbk-zam co za dag ary se pdc dv dsb myv ext fur gv gag inh ki glk gan guw xal haw rw kbp pam csb kw km kv koi kg gom ks gcr lo lbe ltg lez nia ln jbo lg mt mi tw mwl mdf mnw nqo fj nah na nds-nl nrm nov om pi pag pap pfl pcd krc kaa ksh rm rue sm sat sc trv stq nso sn cu so srn kab roa-tara tet tpi to chr tum tk tyv udm ug vep fiu-vro vls wo xh zea ty ak bm ch ny ee ff got iu ik kl mad cr pih ami pwn pnt dz rmy rn sg st tn ss ti din chy ts kcg ve
Portal di Ensiklopedia Dunia
