Как называется эта схема сжатия текста?

Question

Пару лет назад я прочитал об очень легком алгоритме сжатия текста, и теперь я не могу найти ссылку или вспомнить его название.

Он использовал разницу между каждой последовательной парой символов. Так как, например, строчная буква предсказывает, что следующим символом также будет строчная буква, различия, как правило, невелики. (Возможно, он выкинул младшие биты предыдущего символа перед вычитанием; я не могу вспомнить.) Мгновенное снижение сложности. И это Unicode дружественный.

Конечно, было несколько наворотов и подробностей о создании битового потока, но он был очень легковесным и подходил для встраиваемых систем. Нет здоровенного словаря для хранения. Я почти уверен, что резюме, которое я видел, было в Википедии, но я ничего не могу найти.

Я помню, что это было изобретено в Google, но это был не Snappy.

Answer 1

Я думаю, о чем вы говорите, это BOCU, Binary-Ordered Compression для Unicode или одного из его предшественников / преемников. Особенно,

Основная структура BOCU проста. При сжатии последовательности кодовых точек вы вычитаете последнюю кодовую точку из текущей кодовой точки, создавая дельта-значение со знаком, которое может находиться в диапазоне от -10FFFF до 10FFFF. Дельта затем кодируется в серии байтов. Небольшие различия кодируются небольшим количеством байтов; большие различия кодируются в последовательно большем количестве байтов.