shanonFano.cpp

#include <vector>
#include <algorithm>

using namespace std;

struct Symbol {
    char ch;
    double probability;
    string code;
};

// Функция для разделения массива символов на две группы с приблизительно равной суммой вероятностей
int findSplitIndex(vector<Symbol>& symbols, int start, int end) {
    double totalSum = 0.0;
    for (int i = start; i <= end; ++i) totalSum += symbols[i].probability;

    double sum = 0.0;
    for (int i = start; i <= end; ++i) {
        sum += symbols[i].probability;
        if (sum >= totalSum / 2) return i;
    }
    return start;
}

// Рекурсивное кодирование методом Шеннона-Фано
void shannonFano(vector<Symbol>& symbols, int start, int end) {
    if (start >= end) return;

    int split = findSplitIndex(symbols, start, end);

    for (int i = start; i <= split; ++i) symbols[i].code += "0";
    for (int i = split + 1; i <= end; ++i) symbols[i].code += "1";

    shannonFano(symbols, start, split);
    shannonFano(symbols, split + 1, end);
}

int main() {
    vector<Symbol> symbols = {
        {'A', 0.190}, {'B', 0.165}, {'C', 0.137}, {'D', 0.122},
        {'E', 0.112}, {'F', 0.107}, {'G', 0.091}, {'H', 0.076}
    };

    // Сортировка по убыванию вероятности
    sort(symbols.begin(), symbols.end(), [](const Symbol& a, const Symbol& b) {
        return a.probability > b.probability;
    });

    // Запуск алгоритма
    shannonFano(symbols, 0, symbols.size() - 1);

    // Вывод кодов
    cout << "Коды Шеннона-Фано:" << endl;
    for (const auto& sym : symbols) {
        cout << sym.ch << ": " << sym.code << endl;
    }

    return 0;
}