Move-to-front transform

✍ dations ◷ 2025-05-10 16:31:15 #算法

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。

相关

  • 砧板砧板,俗称切菜板或菜板,先秦又称俎,一种厨房用具,主要和刀具配合起来使用,用来切肉、鱼、蔬菜及水果等等。中国古代割肉所用的砧板称为俎,形如几案,多为木制,少有铜铸,长方形,两头有足
  • TLS/SSL传输层安全性协议(英语:Transport Layer Security,缩写:TLS)及其前身安全套接层(英语:Secure Sockets Layer,缩写:SSL)是一种安全协议,目的是为互联网通信提供安全及数据完整性保障。网
  • 风速计风速计是一种测量风速的仪器。通常分为风叶型(风车型)和风杯型。气象站使用的是风杯型的,一般安装在离地10米高的杆子上,四周应空旷。根据一定时间内风杯的转速,可算出平均速度。
  • 胡承珙胡承珙(1776年-1832年),字景孟,号墨庄,安徽泾县人,清朝官员。嘉庆十年(1805年)乙丑科进士。嘉庆十四年(1809年)授翰林院编修。道光元年(1821年)担任按察使衔分巡台湾兵备道。胡承珙潜心经
  • 中国特色社会主义经济建设协同创新中心中国特色社会主义经济建设协同创新中心是根据2011计划,由南开大学、南京大学、中国人民大学、中国社会科学院经济学部与国家统计局统计科学研究所等协同单位合作建立的非法人
  • 第四机械工业部中华人民共和国第四机械工业部(1963年-1982年)。1963年,第四机械工业部由第三机械工业部分出。1982年,第四机械工业部、国家广播电视工业总局、国家电子计算机工业总局(1979年3月
  • 瑞典殖民者瑞典殖民地建立于1638至1663年,以及1785至1878年。严格来说,“帝国”一词并不能代表其殖民地的版图,因为瑞典没有足够能力同时统治其相对细小的殖民地。17世纪中叶,瑞典帝国(1611
  • 德格拉斯伯爵海军中将弗朗索瓦·约瑟夫·保罗,格拉斯·蒂伊侯爵,格拉斯伯爵(François Joseph Paul, marquis de Grasse Tilly, comte de Grasse,1722年9月13日 - 1788年1月11日),法国海军将领
  • 系统综合巴生谷综合运输系统由13条列车线路和2条巴士线路组成,为巴生谷(大吉隆坡)地区提供便捷的城市轨道交通服务。一开始,各个公司各自运营不同的铁路系统,致使乘客需要通过走一段路、
  • 奥林匹克运动会艺术比赛从1912年到1948年的奥林匹克运动会曾举办了艺术竞争。竞争出自现代奥林匹克运动创建者皮埃尔·德·顾拜旦男爵的想法。奖牌分别授予给五个领域中:建筑学、文学、音乐、绘画,