Move-to-front transform

✍ dations ◷ 2025-07-22 12:09:41 #算法

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。

相关

  • 二次文献二次文献也称二级来源、次级资料,它是将大量分散、零乱、无序的一次文献进行整理、浓缩、提炼,并按照一定的逻辑顺序和科学体系加以编排存储,使之系统化,以便于检索利用。其主要
  • 刘新垣刘新垣(1927年11月7日-)是一位中国分子生物学家。1927年生于湖南衡东。l952年南开大学化学系毕业后在河北医学院任教,l963年中国科学院上海生物化学研究所副博士研究生班毕业,留
  • 茂林茂林区(茂林鲁凯语:Teldreka)是中华民国高雄市的一个市辖区,位于高雄市东北半叶东南端,北临桃源区,西邻六龟区、台湾省屏东县高树乡,东邻台湾省台东县延平乡,南接台湾省屏东县三地门
  • 大长今长今是朝鲜王朝宫廷的一位医女,在中宗18年被封为国王的主治医女,赐号“大长今”,是朝鲜王朝历史上唯一一位医治国王的女性医生。有关长今的史料不多,以下为朝鲜王朝实录《中宗大
  • 卢木斋卢木斋(1856年-1948年8月),名靖,字勉之,号木斋,以号行,湖北沔阳(今仙桃市)人,著名实业家、教育家,私立南开大学早期建校的资助人之一。卢木斋将兴办实业的全部财产用于发展教育事业,先后
  • 铜仁学院铜仁学院为中国贵州省铜仁市的一所公立高校。现有全日制本、专科生5700余人。1978年,铜仁师范高等专科学校成立。2006年2月14日,改名铜仁学院。
  • 中性流中性流(Neutral current)是次原子粒子相互作用现象之一,这些相互作用由Z玻色子所引发。弱中性流的发现是弱力与电磁力(弱电理论)统一的重要关键,并导致W及Z玻色子最终被发现。1973
  • 硝酸亚铊硝酸亚铊是一种无机化合物,化学式为TlNO3。存在α、β和γ三种结构。剧毒。它可由金属铊和13%硝酸在80 °C反应,溶液结晶后用乙醇洗涤并在50 °C干燥得到。
  • 洞头区洞头区在中国浙江省东南海上,隶属于温州市。洞头原为中国12个海岛区县之一,称“百岛之县”。同时,洞头也是温州惟一以区县名冠名的省级风景名胜区。1953年6月,以温州专区玉环县
  • 性别指定疗法性别指定疗法(英语:Intersex medical interventions)是使用手术、激素和其他医疗干预措施干预性别,以改变双性人的非典型或模糊的生殖器,主要目的是使一个人的外表更加正常,并减少