logoChat01.ai

Сжатие методом Шенона-Фано

Créé le : 13 octobre 2025

Répondu en utilisant GPT-5 Thinking par Chat01

Question

Сжатие методом Шенона-Фано

Réflexion

Explaining Shannon-Fano compression

The user asked about the Shannon-Fano compression method. It’s a type of variable-length encoding algorithm. The general steps include building a frequency table, sorting by probability, recursively splitting into two groups with sums near 0.5, and assigning 0 or 1 to the groups. While optional, I could also provide code or arithmetic examples.

Explaining Shannon-Fano with an example

Let’s take "BANANA" as an example. For the string, the frequencies are: B=1, A=3, N=2. This gives probabilities: A=0.5, N=0.333, B=0.167. We partition: [A] vs [N, B], then split N and B where N=0.333, B=0.167. The code for A=0, N=10, and B=11. The encoded string is “110101010”, requiring 9 bits. A fixed-length encoding would need 12 bits. Nice savings of 25%!

Discussing Shannon-Fano and Huffman comparison

Shannon-Fano coding has a complexity close to that of Huffman coding, but it’s not optimal. While Shannon-Fano generally yields an average code length close to entropy (H ≤ L < H + 1), it might not always meet this bound. Huffman coding is usually a better fit for optimal prefix codes.

Explaining Shannon-Fano code characteristics

The average code length for Shannon-Fano is close to the entropy but may be slightly worse than Huffman because of the partitioning method. We can say, "On average, the code length doesn’t exceed H + 1 (similar to Shannon’s code), but may perform a bit worse than Huffman.” I'll give an example with Python code and note key points like stability and prefix-free properties.

Thought for 24s

Réponse

Вот краткое, наглядное объяснение метода Шеннона–Фано для сжатия.

Что это

Шеннон–Фано — способ построения префиксного (мгновенно декодируемого) кода для алфавита с известными частотами. Идея: чаще встречающимся символам давать более короткие коды.

Алгоритм (шаги)

  1. Подсчитайте частоты символов и отсортируйте по убыванию вероятности.
  2. Рекурсивно делите множество символов на две группы с суммарными вероятностями как можно ближе друг к другу (≈ пополам).
  3. Присвойте левой группе префикс 0, правой — 1.
  4. Повторяйте деление для каждой группы, пока каждой букве не сопоставите уникальный битовый код.

Мини-пример

Строка: BANANA
Частоты: A×3, N×2, B×1 → вероятности: A=0.5, N≈0.333, B≈0.167.

Деление:

  • Группа1: {A} (0.5) → префикс 0
  • Группа2: {N,B} (0.5) → префикс 1
    • Внутри {N,B}: N (0.333) → 10, B (0.167) → 11

Коды: A=0, N=10, B=11.
Кодируем BANANA → 11 0 10 0 10 0 = 9 бит.
Фиксированный код для 3 символов дал бы 2 бита/символ × 6 = 12 бит → экономия ~25%.

Свойства

  • Префиксный код, однозначно декодируется без разделителей.
  • Почти всегда хуже/не лучше оптимального кода Хаффмана, но строится просто.
  • Качество зависит от того, насколько «ровно» удаются разбиения.

Небольшая реализация (Python)

python
from collections import Counter

def shannon_fano(symbols):
    # symbols: dict {symbol: freq}
    items = sorted(symbols.items(), key=lambda x: x[1], reverse=True)
    codes = {}

    def split_code(seq, prefix=""):
        if len(seq) == 1:
            sym, _ = seq[0]
            codes[sym] = prefix or "0"  # на случай 1 символа
            return
        total = sum(w for _, w in seq)
        acc = 0
        # точка разреза с суммами как можно ближе
        cut = 0
        best_diff = float("inf")
        for i in range(1, len(seq)):
            acc += seq[i-1][1]
            diff = abs(total/2 - acc)
            if diff < best_diff:
                best_diff = diff
                cut = i
        left, right = seq[:cut], seq[cut:]
        split_code(left,  prefix + "0")
        split_code(right, prefix + "1")

    split_code(items)
    return codes

# пример
s = "BANANA"
freqs = Counter(s)
codes = shannon_fano(freqs)
encoded = "".join(codes[ch] for ch in s)
codes, encoded, len(encoded)

Если хотите, могу:

  • закодировать/декодировать ваш текст,
  • сравнить с Хаффманом на ваших данных,
  • сделать таблицу экономии и график распределения длин кодов.

Partager cette Q&R