И. Ю. Травкин [email protected] Май, 2018
Просто захотелось.
Алгоритм Хаффмана — жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.
В отличие от алгоритма Шеннона — Фано, алгоритм Хаффмана остаётся всегда оптимальным и для вторичных алфавитов m2 с более чем двумя символами.
Этот метод кодирования состоит из двух основных этапов:
- Построение оптимального кодового дерева.
- Построение отображения код-символ на основе построенного дерева.
См. Википедия
Дано сообщение длины M, записанное алфавитом с мощностью N. Например, если сообщение имеет вид «ВБВБВАВБАВ», то M = 10, N = 3 (в алфавите 3 символа — «А», «Б» и «В»). Для кодирования каждого символа алфавита равным и минимально возможным числом бит, потребуется log N бит. В нашем примере: log 3 = 1.58, т. е. потребуется 2 бита, а код может быть таким: «А» — 00, «Б» — 01, «В» — 11. Задача: построить оптимальный префиксный код (удовлетворяющий условию Фано), т. е. код переменной длины, в котором символам с большей частотой (в данном сообщении) соответствует более короткий код.
Пример (тот же). «ВБВБВАВБАВ», M = 10, N = 3:
- длина сообщения в битах при кодировании с фиксированной длиной (2 бита на символ): 20 бит;
- частоты символов алфавита: «А» — 2, «Б» — 3, «В» — 5 (в сумме 10 = M);
- оптимальный код: «А» — 10, «Б» — 11, «В» — 0;
- длина сообщения при оптимальном кодировании: (2 бита)·2 + (2 бита)·3 + (1 бит)·5 = 15 бит (на 25% меньше).
1 / Построение таблицы частот
const freqs = text =>
[...text].reduce((fs, c) =>
fs[c] ? (fs[c] = fs[c] + 1, fs)
: (fs[c] = 1, fs), {});Пример:
freqs("Мама мыла раму");
// => {"М":1,"а":4,"м":3," ":2,"ы":1,"л":1,"р":1,"у":1}2 / Преобразование таблицы в массив пар «символ-частота»
const topairs = freqs =>
Object.keys(freqs).map(c => [c, freqs[c]]);Пример:
topairs(freqs("Мама мыла раму"));
// => "[["М",1],["а",4],["м",3],[" ",2],["ы",1],["л",1],["р",1],["у",1]]"3 / Упорядочение пар (по возрастанию частот)
const sortps = pairs =>
pairs.sort((a, b) => a[1] > b[1]);Пример:
sortps(topairs(freqs("Мама мыла раму")));
// => [["М",1],["ы",1],["л",1],["р",1],["у",1],[" ",2],["м",3],["а",4]]4 / Построение кодового дерева
Предполагается, что передаваемый массив пар (аргумент ps) предварительно упорядочен с помощью определенной выше функции sortps.
const tree = ps =>
ps.length < 2
? ps[0]
: tree(sortps([[ps.slice(0, 2), ps[0][1] + ps[1][1]]].concat(ps.slice(2))));Пример:
tree(sortps(topairs(freqs("Мама мыла раму"))));
// => [[[[[[["у",1],[[["л",1],["р",1]],2]],3],["м",3]],6],[[[[[[["М",1],["ы",1]],2],[" ",2]],4],["а",4]],8]],14]
5 / Преобразование дерева в таблицу кодов
const codes = (tree, pfx = "") =>
tree[0] instanceof Array
? Object.assign(codes(tree[0][0], pfx + "0"),
codes(tree[0][1], pfx + "1"))
: {[tree[0]]: pfx};Пример:
codes(tree(sortps(topairs(freqs("Мама мыла раму")))));
// => {
// "а":"11"
// "м":"01",
// " ":"101",
// "у":"000",
// "л":"0010",
// "М":"1000",
// "р":"0011",
// "ы":"1001",
// }6 / Финальная композиция всех шагов
const getcodes = text => codes(tree(sortps(topairs(freqs(text)))));Шесть функций — шесть однострочников на JavaScript.
const freqs = text => [...text].reduce((fs, c) => fs[c] ? (fs[c] = fs[c] + 1, fs) : (fs[c] = 1, fs), {});
const topairs = freqs => Object.keys(freqs).map(c => [c, freqs[c]]);
const sortps = pairs => pairs.sort((a, b) => a[1] > b[1]);
const tree = ps => ps.length < 2 ? ps[0] : tree(sortps([[ps.slice(0, 2), ps[0][1] + ps[1][1]]].concat(ps.slice(2))));
const codes = (tree, pfx = "") => tree[0] instanceof Array ? Object.assign(codes(tree[0][0], pfx + "0"), codes(tree[0][1], pfx + "1")) : {[tree[0]]: pfx};
const getcodes = text => codes(tree(sortps(topairs(freqs(text)))));
👍