Задача
Дана строка, после которой следует символ перехода на следующую строку (далее — endl. Вывести:
- Код графа на языке DOT, иллюстрирующий кодирование символов строки;
- Символы строки и соответствующие им коды Хаффмана;
- Закодированную строку.
Входные данные
Некоторая последовательность символов и endl.
Выходные данные
- Код графа на языке DOT, иллюстрирующий кодирование символов строки;
- Символы строки и соответствующие им коды Хаффмана;
- Закодированная строка.
Тест
| Входные данные | Выходные данные |
|---|---|
| MOLOKO KIPIT | digraph G { "'MLO KITP', 12, code: ''" -> "'MLO', 5, code: '0'" [ label = "0" ]; "'MLO KITP', 12, code: ''" -> "' KITP', 7, code: '1'" [ label = "1" ]; "'MLO', 5, code: '0'" -> "'ML', 2, code: '00'" [ label = "0" ]; "'MLO', 5, code: '0'" -> "'O', 3, code: '01'" [ label = "1" ]; "'ML', 2, code: '00'" -> "'M', 1, code: '000'" [ label = "0" ]; "'ML', 2, code: '00'" -> "'L', 1, code: '001'" [ label = "1" ]; "' KITP', 7, code: '1'" -> "' K', 3, code: '10'" [ label = "0" ]; "' KITP', 7, code: '1'" -> "'ITP', 4, code: '11'" [ label = "1" ]; "' K', 3, code: '10'" -> "' ', 1, code: '100'" [ label = "0" ]; "' K', 3, code: '10'" -> "'K', 2, code: '101'" [ label = "1" ]; "'ITP', 4, code: '11'" -> "'I', 2, code: '110'" [ label = "0" ]; "'ITP', 4, code: '11'" -> "'TP', 2, code: '111'" [ label = "1" ]; "'TP', 2, code: '111'" -> "'T', 1, code: '1110'" [ label = "0" ]; "'TP', 2, code: '111'" -> "'P', 1, code: '1111'" [ label = "1" ]; } Codes of letters: Encoded string: |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 |
#include <iostream> #include <algorithm> #include <vector> #include <string> using namespace std; struct ltcode { unsigned long long frequency; unsigned char letter; string code = ""; }; void zeroset(ltcode *c) { for (unsigned int i = 0; i < 256; ++i) { c[i].frequency = 0; c[i].letter = i; } } bool f(ltcode x, ltcode y) { if (x.frequency != y.frequency) return x.frequency > y.frequency; else return x.letter > y.letter; } struct B { string list; int i; int left; int right; string code = ""; B() { list = ""; i = 0; } }; void print_binary_tree(int num, vector <B> &tree) { if (tree[num].list.size() > 1) { cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].left].list << "', " << tree[tree[num].left].i << ", code: \'" << tree[tree[num].left].code << "\'\" [ label = \"0\" ];\n"; cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].right].list << "', " << tree[tree[num].right].i << ", code: \'" << tree[tree[num].right].code << "\'\" [ label = \"1\" ];\n"; print_binary_tree(tree[num].left, tree); print_binary_tree(tree[num].right, tree); } } void print_tree_graph(vector <B> &tree) { cout << "digraph G {\n"; print_binary_tree(tree.size()-1, tree); cout << "}\n"; } void huffman_encoding_in(int num, string code, vector <B> &tree, ltcode *letter_codes) { tree[num].code = code; if (tree[num].list.size() > 1) { huffman_encoding_in(tree[num].left, code+"0", tree, letter_codes); huffman_encoding_in(tree[num].right, code+"1", tree, letter_codes); } else { for (int j = 0; ; ++j) { if (letter_codes[j].letter == tree[num].list[0]) { letter_codes[j].code = code; break; } } } } void huffman_encoding(vector <B> &sorted_tree, ltcode *letter_codes) { huffman_encoding_in(sorted_tree.size()-1, "", sorted_tree, letter_codes); } int main() { unsigned char c; string S; ltcode count[256], stringlinks[256]; zeroset(count); while (scanf("%c", &c)) { if (c == '\n') break; S += c; ++count[c].frequency; } sort(count, count+256, f); vector <B> tree; B tmp; tmp.list = "0"; int j = 0, letter_amount; for (j = 0; (count[j].frequency); ++j) { tmp.i = count[j].frequency; tmp.list[0] = count[j].letter; tree.push_back(tmp); } int maxsize = j-1, size; sort(tree.begin(), tree.end(), [] (B a, B b) { if (a.i != b.i) return (a.i < b.i); else return (a.list.size() < b.list.size()); }); for (j = 0; size < maxsize;) { tmp.list = tree[j].list + tree[j+1].list; tmp.i = tree[j].i + tree[j+1].i; tmp.left = j; tmp.right = j+1; size = tmp.list.size(); tree.push_back(tmp); j += 2; sort(tree.begin()+j, tree.end(), [] (B a, B b) { if (a.i != b.i) return (a.i < b.i); else return (a.list.size() < b.list.size()); } ); } huffman_encoding(tree, count); print_tree_graph(tree); cout << "\nCodes of letters:\n"; for (j = 0; (count[j].frequency); ++j) { cout << '\'' << count[j].letter << "\'(" << count[j].code << ") "; stringlinks[count[j].letter].code = count[j].code; } cout << "\n\nEncoded string:\n"; for (unsigned int i = 0; i < S.size(); ++i) { cout << stringlinks[S[i]].code; } cout << '\n'; return 0; } |
Решение задачи
Для начала считываем посимвольно строку и запоминаем её, параллельно запоминая частоты появлений символов в ней в массиве count. Останавливаем считывание, когда встречается endl. После этого отсортировуем массив count в порядке убывания частот.
После этого элементы массива count, которые имеют ненулевую частоту, преобразовываем в элементы вектора tree (при этом символы конвертируются в строки), который после сортируется в порядке возрастания частот. Затем обрабатываем массив по алгортиму Хаффмана, объединяя элементы вектора с номерами [latex]j[/latex], [latex]j+1[/latex] в новый (который будет представлять собой структуру из конкатенации строк ранее упомянутых элементов и суммы их частот, а так же номеров его «предков»). После этого вектор вновь сортируется по частотам/суммам частот в порядке возрастания начиная с номера[latex]j+2[/latex], при этом элементы, которые имеют больший размер строк будут иметь меньший приоритет.
Такой алгоритм приводит к тому, что элементы с меньшей частотой/суммой частот не затрагиваются при добавлении новых, и система индексов (условных указателей на «предков») не нарушается.
После этого, используя поиск в глубину, кодируем элементы массива tree, начиная с последнего (строка которого в результате использования алгоритма всегда оказывается объединением всех символов). Остальная часть решения поставленной задачи — вопрос техники.
Интересная реализация. Отличается от того, что я предлагал.