Как компактная запись хранит информацию: интервалы арифметического кода, GF(2), линейная рекурсия и слияние регистров.
Задачи модуля
Закрепите соглашения о порядке символов и битов. Затем сравните несколько компактных представлений: каждое сохраняет свой объект и допускает собственную обратную проверку.
Кодовое слово, модель конечного префикса и вероятностный эскиз дают разные гарантии. Компактность не означает ни восстановления неизвестного будущего, ни точного числа элементов.
Проверять включение двоичного цилиндра в интервал сообщения и учитывать завершение кода.
Восстанавливать XOR-многочлен, минимальную рекурсию префикса и ближайшие кодовые слова.
Объединять совместимые HyperLogLog-регистры с сохранением идемпотентности.
Коды и эскизы
Код Хэмминга: синдром, исправление и граница одной ошибки
Синдром указывает позицию единственной ошибки лишь при заранее принятой модели искажения. Та же процедура при двух ошибках может уверенно исправить третий, изначально правильный бит.
Перед началом: Двоичная арифметика; Чётность.
Проверочные биты кодируют номер позиции
В коде Хэмминга (7,4) проверочные позиции равны 1,2,4. Для каждого разряда двоичного номера позиции задают проверку чётности всех позиций с этим разрядом. Информационные биты занимают 3,5,6,7. Здесь используем чётную чётность и нумерацию от единицы. Другие соглашения допустимы, но менять их между кодированием и декодированием нельзя. Матрица проверок содержит в столбцах семь разных ненулевых трёхбитовых номеров.
Одна инверсия оставляет свой столбец
У правильного слова синдром нулевой. Инверсия бита j добавляет по модулю два ровно j-й столбец проверочной матрицы, то есть двоичный номер j. Поэтому при одной ошибке достаточно инвертировать указанную позицию. Минимальное расстояние кода равно трём: он исправляет одну ошибку. Это не означает безопасного автоматического исправления любого ненулевого синдрома без предположения о числе искажений. Нулевая проверка тоже не исключает всех многобитовых ошибок.
Две ошибки складывают номера
Для ошибок i,j синдром равен их побитовому XOR. Он может совпасть с номером третьего бита, и одноошибочный декодер переведёт слово в другое допустимое кодовое слово. Расширенный код с общей проверкой чётности позволяет различать часть таких случаев и реализовать SECDED при соответствующей модели, но это уже другой код. Полезный тест декодера включает все семь одиночных инверсий и отдельные двойные, чтобы документация не обещала больше фактической гарантии.
Одиночную ошибку в проверочном бите исправляют тем же правилом, что и в информационном. Синдром не различает их роли; он кодирует позицию. Извлекать данные нужно только после завершения коррекции всех семи позиций.
Информация 1011
Условие. Закодируйте биты в позициях 3,5,6,7 как 1,0,1,1. Затем исправьте инверсию позиции 6.
Проверка позиций 1,3,5,7 требует p₁=0.
Проверка 2,3,6,7 требует p₂=1, проверка 4,5,6,7 требует p₄=0.
Получаем слово 0110011. После ошибки 6 принимаем 0110001.
Синдром равен двоичному 110, то есть 6; инверсия этой позиции восстанавливает исходное слово.
Ответ. Кодовое слово 0110011, исправленная позиция 6.
Проверка. XOR номеров единичных позиций правильного слова равен 2⊕3⊕6⊕7=0. Ошибки в 1 и 2 дали бы синдром 3 и неверное одноошибочное исправление.
Где легко ошибиться. Не интерпретируйте любой ненулевой синдром как доказательство ровно одной ошибки: это внешнее предположение канала.
Проверьте понимание
Вопросы к этой главе
Почему позиции проверок — степени двойки?
Так каждый проверочный бит входит в собственную проверку и не входит в остальные, что позволяет независимо задать их значения.
Обнаружение двух ошибок равно их исправлению?
Нет. Даже обнаруженный факт искажения не обязательно даёт единственную исходную комбинацию.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
§§6.2–6.5: проверочная матрица и синдром; все одиночные инверсии собственного слова проверены отдельно. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Код Хаффмана: длина сообщения и неоднозначность дерева
Кратчайший префиксный код определяется частотами, но конкретные нули и единицы в кодовых словах не единственны. Проверять нужно префиксность и взвешенную длину, а не совпадение рисунка дерева.
Перед началом: Двоичное дерево; Частота символа.
Сливайте два наименьших веса
Алгоритм Хаффмана выбирает два символа или поддерева с минимальными весами и заменяет их общим узлом с суммарным весом. Повторение заканчивается корнем. Переходы дерева помечают нулём и единицей, а символы остаются только в листьях, поэтому ни одно кодовое слово не является префиксом другого. Длина слова равна глубине листа. Равные веса могут обрабатываться в разном порядке и давать разные, но одинаково хорошие коды.
Каждое слияние добавляет известную стоимость
При объединении двух поддеревьев глубина каждого их листа увеличивается на единицу. Взвешенная длина сообщения возрастает ровно на сумму их весов. Поэтому итоговая стоимость равна сумме весов всех слияний. Этот способ проверки независим от выписанных кодовых слов. Оптимальность среди двоичных префиксных кодов следует из обменного аргумента: два наименьших веса можно расположить соседними самыми глубокими листьями оптимального дерева и затем сжать задачу.
Оптимальность имеет конкретную модель
Хаффман минимизирует среднюю длину при известных частотах и посимвольном префиксном кодировании. Он не обещает минимальный размер файла с заголовком дерева и не моделирует зависимости соседних символов. Для одного символа нужно заранее выбрать соглашение о пустом или одноразрядном коде. В нашей задаче частоты — целые количества появлений, поэтому взвешенная сумма даёт точное число бит сообщения без служебных данных. Проверка всех пар слов подтверждает отсутствие префиксов.
При равных минимальных весах выбор пары может изменить глубины отдельных равновероятных символов, сохранив общую стоимость. Поэтому тест оптимальности должен сравнивать стоимость и префиксность, а не требовать единственного расположения листьев.
Пять собственных частот
Условие. Частоты A=7,B=5,C=3,D=2,E=1. Постройте код и найдите длину сообщения.
Сливаем E,D: вес 3. Затем C и этот узел: вес 6.
Сливаем B=5 с узлом 6: получаем 11, затем A=7 с 11: корень 18.
Один код: A=0,B=10,C=110,D=1110,E=1111.
Стоимость 7·1+5·2+3·3+2·4+1·4=38 бит; сумма слияний 3+6+11+18 также 38.
Ответ. Длина сообщения 38 бит, средняя длина 38/18=19/9 бита на символ.
Проверка. Все слова заканчиваются в листьях и ни одно не начинается полным другим словом; два независимых подсчёта стоимости совпали.
Где легко ошибиться. Перестановка меток 0 и 1 не ухудшает код. Отличие битовых слов от чужого дерева не доказывает ошибку.
Проверьте понимание
Вопросы к этой главе
Почему частые символы обычно ближе к корню?
Каждый дополнительный уровень стоит их частоту, поэтому большие веса выгодно держать на меньшей глубине.
Включены ли служебные данные?
Нет. Здесь считается только закодированное сообщение при уже известном кодовом дереве.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
§4.4: слияние двух минимальных весов и оптимальность префиксного кода. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
CRC: полиномиальный остаток и необнаруживаемая ошибка
CRC проверяет делимость двоичного многочлена, а не криптографическую подлинность. Любое искажение, кратное генератору, оставляет нулевой остаток и показывает точную границу такой проверки.
Перед началом: Многочлены над полем из двух элементов; XOR.
Деление выполняется без переносов
Битовая строка задаёт коэффициенты многочлена, старший бит соответствует старшей степени. Сложение и вычитание одинаковы и выполняются через XOR. Для генератора g степени r сообщение умножают на xʳ, делят на g и прибавляют остаток. Полученное слово делится на g, потому что в характеристике два вычитание остатка совпадает с прибавлением. Здесь используется учебная несмещённая модель без начального регистра, отражения битов и финального XOR.
Приёмник видит только остаток ошибки
Если передано кратное g слово c, а ошибка e добавлена через XOR, остаток принятого слова равен остатку e. Значит все ошибки, кратные g, не обнаруживаются. Условия на генератор позволяют гарантировать обнаружение определённых классов, например одиночных ошибок при ненулевом постоянном члене и подходящей степени. Но обещание «обнаруживает любую ошибку» невозможно для короткого конечного контрольного поля. Для защиты от намеренной подделки нужен другой механизм.
Параметры протокола нельзя опускать
Реальные варианты CRC отличаются направлением обработки битов, представлением многочлена и начальными условиями. Одинаковое имя степени не задаёт совместимость. Для проверки учебного вычисления удобно использовать целочисленные сдвиги и XOR, которые буквально реализуют деление над GF(2). Отдельный тест должен подтвердить нулевой остаток кодового слова и показать хотя бы один необнаруживаемый шаблон ошибки. Такой контрпример не означает бесполезность CRC; он уточняет модель гарантии.
Если ошибка имеет степень меньше степени генератора и ненулевая, она не может делиться на генератор. Поэтому такой короткий шаблон обязательно обнаруживается в учебной модели. Однако длинный шаблон с тем же числом единиц может уже оказаться кратным и пройти проверку.
Три контрольных бита
Условие. Сообщение 1101, генератор 1011. Постройте систематическое слово и приведите необнаруживаемую ошибку.
Степень генератора 3, поэтому дописываем три нуля: 1101000.
Деление XOR даёт остаток 001.
Кодовое слово равно 1101001 и имеет нулевой остаток.
Ошибка 0101100 равна генератору, сдвинутому на два разряда. После XOR получается 1000101, тоже кратное генератору.
Ответ. Контроль 001, слово 1101001; ошибка 0101100 не обнаруживается.
Проверка. Независимое полиномиальное деление обоих слов даёт нулевой остаток; ошибка ненулевая, поэтому принятый текст действительно изменился.
Где легко ошибиться. Не сравнивайте учебный остаток с библиотечным CRC без совпадения всех параметров обработки битов.
Проверьте понимание
Вопросы к этой главе
Почему контроль прибавляют, а не вычитают?
Над GF(2) это одна операция: 1+1=0, переносов между разрядами нет.
Нулевой остаток доказывает отсутствие искажения?
Нет. Он доказывает лишь, что принят многочлен из кода; ненулевая кратная генератору ошибка тоже проходит.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
§6.6: CRC как полиномиальный код, кратность генератору и синдром ошибки. Используется явно оговорённая учебная битовая конвенция. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Фильтр Блума: отсутствие достоверно только без удалений
Несколько установленных битов могут имитировать никогда не добавленный ключ. Но нулевой проверяемый бит действительно исключает присутствие — пока реализация только устанавливает биты и не очищает общие позиции.
Перед началом: Хеш-функция; Битовый массив.
Вставка объединяет следы ключей
Фильтр Блума хранит m битов, изначально нулевых, и k хеш-позиций для каждого ключа. Вставка устанавливает эти биты в единицу. Запрос отвечает «возможно есть», если все нужные позиции установлены. Коллизии объединяют следы разных ключей, поэтому положительный ответ не доказывает наличие. Отрицательный ответ при корректной вставочной модели точен: ранее добавленный ключ установил бы все собственные позиции, а последующие вставки не могли их очистить.
Обычное удаление нарушает односторонность
Если очистить биты удаляемого ключа, можно уничтожить общий след другого, который всё ещё находится в множестве. Тогда появится ложное отрицание. Счётный фильтр хранит счётчики вместо битов и позволяет уменьшать их при правильной дисциплине удалений, но имеет собственные вопросы переполнения и согласованности. Удаление ключа, которого не было, тоже способно повредить счётчики. Поэтому название структуры не заменяет точное описание поддерживаемых операций.
Вероятность требует предположений о хешировании
Популярные оценки ложного положительного ответа используют приближение независимых равномерных хеш-позиций. На маленьком фиксированном массиве можно вычислить результат запроса точно, не выдавая его за универсальную вероятность. Рост заполнения повышает риск положительных ответов, но не ухудшает корректность отрицаний в вставочной модели. Если хеши или размер массива меняются, старые ключи нужно перестроить согласованно. Применять новые функции к старому битовому состоянию значит изменить саму структуру и потерять гарантию.
Для точного подтверждения положительного ответа обычно обращаются к основному хранилищу. Фильтр экономит отрицательные запросы, но не заменяет само множество ключей.
Общие биты трёх запросов
Условие. Массив из 8 бит. Позиции a={1,4}, b={3,6}, c={1,6}, d={0,4}. Вставьте a,b и проверьте c,d.
После вставок единицы стоят в {1,3,4,6}.
Обе позиции c установлены, поэтому ответ «возможно есть», хотя c не вставляли.
У d позиция 0 нулевая, поэтому d точно отсутствует в принятой модели.
Если затем очистить позиции a, ключ с позициями {1,6}, ранее вставленный отдельно, мог бы получить ложное отрицание.
Ответ. c даёт ложное положительное совпадение, d — корректное отрицание.
Проверка. Сопоставление с точным множеством {a,b} проверяет смысл ответов; простой просмотр битов подтверждает оба результата.
Где легко ошибиться. Очищение обычного битового фильтра при удалении одного ключа может повредить сведения о других ключах.
Проверьте понимание
Вопросы к этой главе
Почему отрицание точнее подтверждения?
Один нулевой бит несовместим с прежней вставкой ключа, а единицы могли быть установлены другими ключами.
Ложное положительное совпадение означает плохой хеш?
Не обязательно. Это предусмотренное следствие ограниченного битового представления даже при хорошем хешировании.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
§6.1: битовый фильтр и ложные положительные ответы; удаление отдельно показано как нарушение вставочной модели. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Count-Min Sketch: почему оценка завышена при положительных обновлениях
Частоту ключа можно оценивать по нескольким коротким массивам счётчиков. Коллизии добавляют чужую массу, а минимум по строкам выбирает наименее загрязнённую оценку, сохраняя одностороннюю границу.
Перед началом: Поток обновлений; Хеширование.
Каждая строка хранит общий счёт корзины
В Count-Min Sketch ключ обновляет по одному счётчику в каждой строке согласно своей хеш-функции. При запросе берут минимум этих счётчиков. Если все обновления неотрицательны, собственная частота ключа полностью присутствует в каждом выбранном счётчике, а коллизии только добавляют чужие значения. Поэтому оценка не меньше истинной частоты. Минимум не устраняет коллизии гарантированно, но выбирает лучшую из доступных верхних оценок.
Вероятностная точность отличается от односторонности
Незанижение следует алгебраически из неотрицательных обновлений и не требует случайности хешей. Вероятностная граница величины завышения уже зависит от семейства хеш-функций, ширины, числа строк и суммарной массы потока. Нельзя выдавать минимум двух произвольных счётчиков за точную частоту. Для малой таблицы полезнее выписать все коллизии явно. Даже ключ, которого никогда не было, может получить положительную оценку из чужих обновлений.
Удаления меняют доказательство
При произвольных отрицательных обновлениях чужая масса способна уменьшить корзину, и простое доказательство верхней границы перестаёт работать. Для специальных моделей допустимых удалений существуют уточнённые условия, но их нужно назвать отдельно. Переполнение машинного счётчика также разрушает монотонность, даже если пользовательские обновления положительны. Эскиз не хранит полный набор ключей и не даёт возможности восстановить точную историю; это компактный ответ на ограниченный класс запросов о частотах.
Консервативное обновление, изменяющее только минимальные корзины, является другой разновидностью алгоритма. В нашем worked каждое обновление прибавляется ко всем соответствующим счётчикам. Нельзя смешивать трассу одной разновидности с доказательством другой без проверки её инвариантов.
Две разные схемы коллизий
Условие. Частоты a=4,b=2,c=3. Первая строка: a,b→0,c→1. Вторая: a,c→0,b→1. Найдите оценки.
Первая строка получает счётчики [6,3].
Вторая строка получает [7,2].
Для a минимум 6 и 7 равен 6, хотя истинная частота 4.
Для b минимум 6 и 2 равен 2; для c минимум 3 и 7 равен 3.
Ответ. Оценки a=6,b=2,c=3; только a завышена на 2.
Проверка. Сумма каждой строки равна общей массе 9; ни один ответ не меньше истинной неотрицательной частоты.
Где легко ошибиться. Не обещайте точность только потому, что взят минимум: один и тот же ключ может столкнуться с другими в каждой строке.
Проверьте понимание
Вопросы к этой главе
Почему сумма строк одинаковая?
Каждое обновление добавляет один и тот же вес ровно в один счётчик каждой строки.
Можно ли получить частоту отсутствующего ключа ноль?
Иногда да, если хотя бы одна его корзина пуста. Но положительный ответ не доказывает присутствия.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
§6.4: таблицы счётчиков и минимум по строкам; только неотрицательные обновления. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Связанные методы
Сообщение как вложенный интервал: что именно передают биты арифметического кода
Арифметическое кодирование последовательно сужает интервал по накопленным вероятностям символов. Для передачи выбирают двоичный префикс, весь интервал продолжений которого лежит внутри итогового интервала сообщения. Модель и правило завершения передаются отдельно.
Из таблицы истинности в XOR-многочлен: сначала закрепите порядок переменных
Алгебраическая нормальная форма записывает булеву функцию как XOR-сумму квадратсвободных мономов. Коэффициенты находятся над GF(2) по таблице значений. Подстановка во все исходные наборы проверяет и коэффициенты, и принятую нумерацию переменных.
Ближайшее кодовое слово и гарантированное исправление — разные утверждения
Строки порождающей матрицы складываются по модулю два. Минимальный вес ненулевого кодового слова равен минимальному расстоянию кода. Он определяет гарантированный радиус исправления, а отдельное принятое слово дополнительно проверяют на ничью ближайших вариантов.