Кодирование при повторной установке
-
Основы тансталловского кодирования
- Тансталловское кодирование — это энтропийное кодирование без потерь.
- Кодирование было разработано Брайаном Паркером Танстоллом в 1967 году.
- Оно предшествует кодированию Lempel-Ziv.
-
Свойства и алгоритм
- Кодирование Танстолла преобразует символы в фиксированное количество битов.
- Оно анализирует стохастический источник, используя коды переменной длины.
- Для достаточно большого словаря количество битов на букву близко к энтропии источника.
-
Алгоритм кодирования
- Алгоритм требует алфавит и распределение вероятностей для слов.
- Он использует константу C для ограничения размера словаря.
- Словарь строится в виде дерева вероятностей.
-
Пример использования
- В примере закодирована строка «hello, world» с использованием 4 и 5 битов соответственно.
- Итерации могут быть продолжены для увеличения количества слов.
-
Ограничения и модификации
- Предварительное кодирование требует знания распределения вероятностей.
- Кодирование менее эффективно, чем Lempel-Ziv, из-за необходимости вывода блока фиксированной длины.
- Базовая модификация используется для изменения базы данных и повышения эффективности передачи данных.
-
Эффективность считывания
- Считывание данных с использованием тансталловского кодирования позволяет эффективно передавать данные по каналам с другой базой данных.
- Эффективность считывания близка к эффективности идеального двоичного кода Хаффмана.
Полный текст статьи: