mtf算法(似乎有误,应该提前将不重复字符按字典序排序),关于该算法(https://www2.cs.duke.edu/csed/algoprobs/beta/bw1.html):
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void mtf_encode(const char *s, unsigned len, int *code)
{
int pos = 0, num, trace = 0;
unsigned i, j, k;
int is_hav[26], stack[26];
memset(is_hav, 0, 26);
while (*s)
{
if (!is_hav[*s - ‘a‘])
{
stack[pos] = *s - ‘a‘ + 1;
is_hav[*s - ‘a‘] = 1;
++pos;
code[trace++] = pos;
}
else
{
j = 0;
while (stack[j] != *s - ‘a‘ + 1) j++;
code[trace++] = j + 1, num = stack[j];
while (j > 0) stack[j] = stack[j - 1], j--;
stack[j] = num;
}
s++;
}
}
void print_mtf_encode(int*code, int len)
{
unsigned i;
printf("[");
for (i = 0; i < len; i++)
{
printf("%d", code[i]);
if (i != len - 1)
printf(", ");
}
printf("]");
}
int main()
{
char s[] = "abcabcaaaaaaaab";
int len = strlen(s);
int *code = (int *)malloc(sizeof(int) * len);
mtf_encode(s, len, code);
print_mtf_encode(code, len);
return 0;
}
rle算法,暂时没太明白。了解该算法:https://en.wikipedia.org/wiki/Run-length_encoding
Move-to-front(MTF) and Run-lenght encoding(RLE) algorithms
原文:https://www.cnblogs.com/darkchii/p/10060029.html