Move-to-front transform

✍ dations ◷ 2025-04-10 01:45:22 #算法

MTF(Move-To-Front)是一种数据编码方式,作为一个额外的步骤,用于提高数据压缩技术效果。MTF主要使用的是数据“空间局部性”,也就是最近出现过的字符很可能在接下来的文本附近再次出现。

(1)首先维护一个文本字符集大小的栈表,“recently used symbols”(最近访问过的字符),其中每个不同的字符在其中占一个位置,位置从0开始编号。(2)扫描需要重新编码的文本数据,对于每个扫描到的字符,使用该字符在“recently used symbols”中的index替换,并将该字符提到“recently used symbols”的栈顶的位置(index为0的位置)。重复上一步骤,直到文本扫描结束。

以字符串“annbaa”为例(“annbaa”在这里为字符串“banana”经过BWT变换后的结果Bzip2 Burrows-Wheeler变换)。基于recently used symbols,设立一个栈表“abcdefghijklmnopqrstuvwxyz”。

a n n b a a
a n n b a a
a n n b a a
a n n b a a
a n n b a a
a n n b a a
结果
0
0,13
0,13,0
0,13,0,2
0,13,0,2,2
0,13,0,2,2,0
0,13,0,2,2,0
abcdefghijklmnopqrstuvwxyz
nabcdefghijklmopqrstuvwxyz
nabcdefghijklmopqrstuvwxyz
bnacdefghijklmopqrstuvwxyz
abncdefghijklmopqrstuvwxyz
abncdefghijklmopqrstuvwxyz
abncdefghijklmopqrstuvwxyz
Index of a = 0; record 0; a is on the top
Index of n = 13; record 13; move n to the top
Index of n = 0; record 0; n is on the top
Index of b = 2; record 2; move b to the top
Index of a = 2; record 2; move a to the top
Index of a = 0; record 0; a is on the top

MTF的压还原过程

以序列“0, 13, 0, 2, 2, 0”为例(“0, 13, 0, 2, 2, 0”在这里为字符串“aaabnn”经过MVT压缩后的结果)。基于栈表“nbacdefghijklmopqrstuvwxyz”,n的指数为0,z的指数为25。

相关

  • 转座子转座子(英语:Transposon,亦称为转座元件,跳跃子)是一类DNA序列,它们能够在基因组中通过转录或逆转录,在内切酶(Nuclease)的作用下,在其他基因座上出现。转座子的这种行为,与假基因(Pseud
  • span style=color:black;small第四纪冰期/small/span第四纪冰河时期,也称作“第四纪冰期”、“第四纪大冰期”、“第四纪冰河期”、“第四纪冰川期”、“更新世冰川期”、“当前冰河时期”、“末次冰河时期”,是指从258万年前到
  • 冠礼冠礼,又称元服,是中国、朝鲜、越南及日本传统的成年礼,于男子20岁时举行,与之相对应的女子成年礼被称为笄礼,一般在女子15岁时举行。冠礼从原始社会的成丁礼(又名“入社礼”)演变而
  • 纸草纸草可能指以下条目:
  • 幸福来了《幸福来了》为民间全民电视公司20周年台庆八点档连续剧,以“幸福”为主轴。此剧于2017年1月3日开镜,6月6日开拍,7月3日举办试片记者会,7月4日接档《春花望露》首播,2018年7月1日
  • 玛格丽特·斯佩林斯玛格丽特·斯佩林斯(Margaret Spellings,1957年11月30日-),美国政治家,美国共和党成员,前美国教育部长(2005年至2009年)。
  • 施肥堆肥是被分解和回收的有机物质作为肥料和土壤调理剂(英语:Soil conditioner)。堆肥是有机农业的关键成分。在最简单的层面上,堆肥过程需要将一批被称为绿色废物(英语:Green waste)(
  • 拉丁文缩写列表拉丁文曾是欧洲通用的学术语言。18世纪起,学者开始使用自己的母语写作。然而由于许多拉丁文缩写简洁、精确,所以其仍被继续使用。所有的缩写后必须紧接一个英文句号,但实际上这
  • 陈瑞宪陈瑞宪(1957年- )生于台北市,台湾设计师,小美冰淇淋创办人陈阿章家族之后代。淡江大学化学系毕业,后不顾家中反对赴日本就读东京设计者学院建筑系,先后曾师于安藤忠雄、黄永洪。中
  • 爱情的开关《爱情的开关》(英语:),2020年中国都市爱情偶像剧,改编自匪我思存的同名小说。该剧起初是钟汉良、颖儿、乔振宇、宋茜等参演该剧的主演,在2016年浙江卫视节目招商大会宣布预计于20