Move-to-front transform

✍ dations ◷ 2025-02-23 16:54:46 #算法

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。

相关

  • 大灭绝生物集群灭绝是指在一个相对短暂的地质时段中,在一个以上并且较大的地理区域范围内,生物数量和种类急剧下降的事件。这个概念主要是指宏观生物,因为微生物的多样性和数量很难推
  • Henrietta Leavitt亨丽爱塔·斯万·勒维特(英语:Henrietta Swan Leavitt,1868年7月4日-1921年12月12日)是一位美国天文学家,毕业于拉德克利夫学院。1893年起,她在哈佛大学天文台担任计算员,负责监视感
  • 单孔目单孔目(学名:Monotremata)是哺乳纲动物中原兽亚纲的仅有的一目。只分布在大洋洲地区,主要在澳大利亚东部及塔斯曼尼亚生活,是一群卵生哺乳类。历史上曾存在另外两个科,但都已灭绝
  • 高雄糖厂坐标:22°45′28″N 120°18′51″E / 22.7577768°N 120.3141186°E / 22.7577768; 120.3141186桥头糖厂现在名为高雄糖厂,旧称为“桥仔头糖厂”,是台湾第一座现代化机械式制
  • 面孔脸(“脸”通“面”、脸又称脸孔、脸庞、颜脸)是人类和动物的多种感觉器官的集合。脸通常位于头部的正面,而且通常只有一个。脸的范围约为额至颔。包括额、眉、睫毛、眼、鼻、耳
  • 诸生生员,俗称秀才,雅称弟子员。是中国、朝鲜、越南的科举中经过院试,得到入学资格的士人,也是士大夫的最基层。对太学的监生称太学生、弟子员;府、州、县学生员也称庠生,又有贡生、监
  • 鼠科鼠科(学名:Muridae),哺乳纲啮齿目的一科,包括家鼠、旅鼠、田鼠、草原兔尾鼠)等之许多常见动物,原产于亚洲、欧洲、非洲、澳洲等广大地区,现在则已遍布地球每个角落。共分为四个亚科,
  • 嘉明湖嘉明湖(布农语:Cidanumas-Buan)位于台湾台东县海端乡,座落于三叉山东侧,距向阳山直线距离7公里处,海拔3,310/11米,是台湾湖泊中第二高的高山湖泊,仅次于3,520米的雪山翠池。日治时期
  • 李伯璋 (1954年)李伯璋(1954年4月29日-),台湾移植外科名医,曾任国立成功大学外科教授、卫生福利部台南医院院长,担任医师期间钻研移植领域并推动器官捐赠,后担任卫生福利部中央健康保险署署长。
  • 2012年夏季奥林匹克运动会马术比赛2012年夏季奥林匹克运动会马术比赛于2012年7月28日至8月9日于格林威治公园举行。本届马术赛事设有六个比赛项目,包括:本届马术比赛共有75位骑手及75匹马参与,除了主办国英国外,