Move-to-front transform

✍ dations ◷ 2025-10-24 03:01:16 #算法

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。

相关

  • 出芽生殖出芽生殖 (英文: budding),是一种无性繁殖方式,亲代借由细胞分裂产生子代,但是子代并不立即脱离母体,而与母体相连,继续接受母体提供养分,直到个体可独立生活才脱离母体。是一种特
  • 严重特殊传染性肺炎防治及纾困振兴特别条例《严重特殊传染性肺炎防治及纾困振兴特别条例》(简称:武汉肺炎纾困条例)是中华民国为因应2019冠状病毒病疫情,维护台湾人民健康,并因应其对台湾经济、社会之冲击所制定之条例,共有
  • 线性元件电子电路中,线性元件是一种电子元件,与电流和电压有线性的关系。电阻是最普遍的线性元件范例,其他的例子如电容、电感和变压器。
  • 中国切音新字中国切音新字是清末拼音字方案中最早的一种。卢戆章创制,他用“两字合即成音”的方法,仿拉丁字母笔形制定字母55个,于1892年出版《一目了然初阶》,次年出版《新字初阶》(两书都是
  • 纯净水纯净水,简称净水或纯水,文义上是纯洁、干净,不含有杂质或细菌的水,是以符合生活饮用水卫生标准的水为原水,通过电渗析器法、离子交换器法、反渗透法、蒸馏法及其他适当的加工方法
  • 图莱里县图莱里县(Tulare County)是美国加利福尼亚州中央谷地内的一个县,面积12,533.2平方公里。根据2010年人口普查,本县共有人口368,021人。本县县治为维塞利亚。本县成立于1852年,县名
  • 罗杰·威克罗杰·弗雷德里克·威克(英语:Roger Frederick Wicker;1951年7月5日-),是一位美国共和党政治人物,2007年起担任密西西比州美国参议院议员。自密西西比大学毕业后,威克于1976年到1980
  • 乔治亚总统府乔治亚总统府(格鲁吉亚语:საქართველოს პრეზიდენტის ადმინისტრაცია)是格鲁吉亚总统的办公场所,位于提比里斯市区库拉河左岸。乔治亚总统府修
  • 依斯迈阿都拉曼敦依斯迈·阿都·拉曼(马来语:Tun Dr Ismail Abdul Rahman,1915年11月4日-1973年8月2日),马来西亚第二任副首相,曾任巫统副主席、马来亚联合邦驻美国大使,并常驻联合国。位于吉隆坡
  • 阿兰·芬基尔克罗阿兰·芬基尔克罗(Alain Finkielkraut,1949年6月30日-),法国哲学家、作家、公共知识分子。其涉猎领域广泛,包括犹太身份与反犹主义、法国殖民主义、法国教育与移民同化、南斯拉夫