移动到前端数据转换算法-yiteyi-C++库

什么是MTF转换？ 这个 MTF（移到前面）是一种数据转换算法，它以一种更可压缩的方式重新构造数据，因此被用作压缩中的额外步骤。从技术上讲，它是输入字符序列到输出数字数组的可逆转换。

null

为什么是MTF？ 1.在许多情况下，输出数组给出了频繁重复字符的较低索引，这在 数据压缩算法。

2.这是在实现Burrows–Wheeler数据压缩算法时连续执行的三个步骤中的第一步，该算法构成Unix压缩实用程序bzip2的基础。

MTF背后的主要理念是：

1.MTF背后的主要思想是维护一个有序的法律符号列表（在我们的示例中是a到z）。

2.从输入字符串中一次读取一个字符。

3.打印出该字符在列表中出现的位置。

4.将该字符移动到列表的前面，并重复该过程，直到获得所有输入字符的索引。

Illustration for "panama".  
List initially contains English alphabets in order. 
We one by one characters of input to front.

input_str chars   output_arr       list
  p              15               abcdefghijklmnopqrstuvwxyz
  a              15 1             pabcdefghijklmnoqrstuvwxyz
  n              15 1 14          apbcdefghijklmnoqrstuvwxyz
  a              15 1 14 1        napbcdefghijklmoqrstuvwxyz
  m              15 1 14 1 14     anpbcdefghijklmoqrstuvwxyz
  a              15 1 14 1 14     manpbcdefghijkloqrstuvwxyz

推论： 1.如果字母在输入中多次出现，那么许多输出值将是小整数，如0、1、2等。

2.因此，对这些字母的极高频率进行编码是一个理想的解决方案 哈夫曼编码。

例如：

Input : panama
Output : 15 1 14 1 14 1

Input : geeksforgeeks
Output : 6 5 0 10 18 8 15 18 6 6 0 6 6

下面是上面解释的idea代码：

                     // C program to find move to front transform of                   
                     // a given string                   
                     #include <stdio.h>                   
                     #include <stdlib.h>                   
                     #include <string.h>                   
                             
                     // Returns index at which character of the input text                   
                     // exists in the list                   
                     int                               search(                               char                               input_char,                               char                               * list)                   
                     {                   
                                         int                               i;                   
                                         for                               (i = 0; i <                               strlen                               (list); i++) {                   
                                         if                               (list[i] == input_char) {                   
                                         return                               i;                   
                                         break                               ;                   
                                         }                   
                                         }                   
                     }                   
                             
                     // Takes curr_index of input_char as argument                   
                     // to bring that character to the front of the list                   
                     void                               moveToFront(                               int                               curr_index,                               char                               * list)                   
                     {                   
                                         char                               * record = (                               char                               *)                               malloc                               (                               sizeof                               (                               char                               ) * 26);                   
                                         strcpy                               (record, list);                   
                             
                                         // Characters pushed one position right                   
                                         // in the list up until curr_index                   
                                         strncpy                               (list + 1, record, curr_index);                   
                             
                                         // Character at curr_index stored at 0th position                   
                                         list[0] = record[curr_index];                   
                     }                   
                             
                     // Move to Front Encoding                   
                     void                               mtfEncode(                               char                               * input_text,                               int                               len_text,                               char                               * list)                   
                     {                   
                                         int                               i;                   
                                         int                               * output_arr = (                               int                               *)                               malloc                               (len_text *                               sizeof                               (                               int                               ));                   
                             
                                         for                               (i = 0; i < len_text; i++) {                   
                             
                                         // Linear Searches the characters of input_text                   
                                         // in list                   
                                         output_arr[i] = search(input_text[i], list);                   
                             
                                         // Printing the Move to Front Transform                   
                                         printf                               (                               "%d "                               , output_arr[i]);                   
                             
                                         // Moves the searched character to the front                   
                                         // of the list                   
                                         moveToFront(output_arr[i], list);                   
                                         }                   
                     }                   
                             
                     // Driver program to test functions above                   
                     int                               main()                   
                     {                   
                                         char                               * input_text =                               "panama"                               ;                   
                                         int                               len_text =                               strlen                               (input_text);                   
                             
                                         // Maintains an ordered list of legal symbols                   
                                         char                               * list = (                               char                               *)                               malloc                               (                               sizeof                               (                               char                               ) * 26);                   
                                         strcpy                               (list,                               "abcdefghijklmnopqrstuvwxyz"                               );                   
                             
                                         printf                               (                               "Input text: %s"                               , input_text);                   
                                         printf                               (                               "Move to Front Transform: "                               );                   
                             
                                         // Computes Move to Front transform of given text                   
                                         mtfEncode(input_text, len_text, list);                   
                             
                                         return                               0;                   
                     }                   

输出：

Input text: panama
Move to Front Transform: 15 1 14 1 14 1

时间复杂性： O（n^2）

练习： 实现“移动到前”变换的反转。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章