Пользователи

Проверил четвертую контрольную (баллы в таблице уже стоят). Напомню, требовалось написать про плюсы и минусы кодирования Шеннона-Фано, Хаффмана и арифметического кодирования.

Основное замечание - во многих работах очень странно было читать, что, одновременно, алгоритмы являются двухпроходными (это минус) и что подсчет вероятностей и построение кода проводится одновременно. Это явная ошибка, так как во втором случае алгоритм однопроходный. Это относится лишь к адаптивным алгоритмам (адаптивному алгоритму Хаффмана и адаптивному арифметическому кодированию), но никак не к алгоритмам, про которые был сформулирован вопрос. Все алгоритмы, про которые надо было написать, двухпроходные и это их общий минус.

Второй момент - многие указали недостатком арифметического кодирования сложность производимых вычислений. Но это сложность для нас (для человека). С точки зрения теории и практики реализации алгоритма на ЭВМ сложности никакой нет. Умножение и тем более сложение считаются простыми операциями.

Еще была сложность с плюсами арифметического кодирования. То, что там можно раскодировать сообщение и для этого вводится признак конца строки - это не плюс, а констатация факта (можно раскодировать, без этого алгоритм просто бы не состоялся) и необходимость (введение признака конца строки, что является скорее минусом, чем плюсом). Плюс в том, что арифметическое кодирование применимо в ситуации и дает хороший результат, когда энтропия источника сообщения меньше единицы. Кодирование Шеннова-Фано и Хаффмана в этом случае результат дают плохой. Про этот факт, к сожалению, никто не написал. Но я не стал ха это снижать баллы. Возможно, на лекции мы это не записали, а просто проговорили устно.

Ну а про задачу о разделении камне все написали правильно, молодцы ))