Skip to content

Latest commit

 

History

History
190 lines (121 loc) · 11.9 KB

README-RU.md

File metadata and controls

190 lines (121 loc) · 11.9 KB

rutf8-toolkit

Библиотека для сериализации и сжатия небольших кириллических текстов. Включает алгоритмы для кодирования, сжатия и декодирования данных, такие как RUTF8, Хаффман, LZSS, LZ77, BWT и RLE.

Установка

Для установки rutf8-toolkit используйте npm:

npm install rutf8-toolkit

Поддержка ESM и CommonJS:


import { rutf8BinaryEncode } from 'rutf8-toolkit';

const { rutf8BinaryEncode } = require('rutf8-toolkit');

Особенности

  • rutf8: Храните и передавайте кириллические буквы в формате uint8 c поддержкой Unicode.
  • Хаффман: Кодирование переменной длины с использованием дерева Хаффмана.
  • LZSS и LZ77: Компрессия текста через алгоритмы со скользящим окном.
  • BWT: Обратимые перестановки Барроуза-Уилера для улучшения сжатия.
  • RLE: Простое кодирование повторяющихся символов.
  • Оптимальное сжатие: Подсчет теоретически возможного минимального* размера строки с помощью энтропии Шеннона.

Комбинирование алгоритмов

Для интересных результатов рекомендуется использовать несколько алгоритмов последовательно. Комбинация различных методов сжатия и кодирования может значительно повысить эффективность хранения и передачи данных. Например, можно предварительно обработать текст с помощью RUTF8, после BWT, а затем применить RLE и кодирование Хаффмана.

Модули

1) rutf8

Кастомный метод кодирования, который меняет местами кириллические символы и символы ASCII в таблице Unicode. Это позволяет представлять русский текст однобайтовыми символами ASCII, сохраняя полную поддержку всех остальных символов Unicode.

Как это работает:

  • Алгоритм выполняет двустороннее преобразование:
    • Русские символы заменяются на соответствующие ASCII при кодировании.
    • ASCII заменяются на соответствующие русские символы при декодировании.
  • Поддерживаются все символы, поэтому ничего не теряется в процессе кодирования/декодирования.

Функции:

  • rutf8Encoder: Кодирует русские символы в ASCII.
  • rutf8Decoder: Декодирует ASCII обратно в русские символы.
  • rutf8BinaryEncode: Кодирует в бинарный буффер с данными RUTF-8.
  • rutf8BinaryDecode: Декодирует из бинарного буффера с данными RUTF-8.

Примеры:

const string = 'Карл-Франц'
const rutfEncoded = rutf8Encoder(string) // 'Larm-Vraox'
const string = 'Карл-Франц'
const rutfBinaryEncoded = binaryEncoder(string) // ArrayBuffer

2) Хаффман

Модуль кодирования Хаффмана использует алгоритм дерева Хаффмана для кодирования текста с помощью "variable-length encoding", что позволяет сжимать данные, присваивая короткие коды частым символам.

Как это работает:

  • Анализирует частоту символов.
  • Создает коды переменной длины для каждого символа.
  • Кодирует текст с использованием этих кодов и упаковывает дерево Хаффмана вместе с закодированными данными в двоичный буфер.
  • Декодирует текст без необходимости в дополнительной схеме (безсхемное декодирование).

Основные функции:

  • huffmanBinaryEncode: Кодирует в бинарный буффер данные обработанные Хаффманом.
  • huffmanBinaryDecode: Декодирует из бинарного буффера данные обработанные Хаффманом.
  • createHuffmanTree: Позволяет увидеть литерал древа кодирования Хаффмана.

Схема двоичного кодирования

Huffman Binary Schema

3) LZSS

LZSS — это оптимизированная версия LZ77, которая сжимает текстовые данные с помощью скользящего окна.

Как это работает:

  • Lookahead Buffer (буфер предсмотра) содержит символы, которые алгоритм попытается сопоставить с Search Buffer (буфер поиска). Это помогает алгоритму находить повторяющиеся шаблоны.
  • Search Buffer содержит уже обработанные символы и используется для поиска совпадений с Lookahead Buffer.
  • LZSS кодирует повторяющиеся шаблоны в виде кортежей [смещение, длина]:
    • Кодирование происходит только если длина повторяющегося паттерна > 2 символов.
    • В остальных случаях символы кодируются как uint8 (ASCII).
    • Если совпадение найдено в конце Search Buffer, алгоритм проверяет его на предмет возможности применения RLE.

Основные функции:

  • lzssBinaryEncode: Кодирует в бинарный буффер данные обработанные с помощью LZSS.
  • lzssBinaryDecode: Декодирует из бинарного буффера данные, сжатые с использованием LZSS.
  • lzssEncode: Позволяет увидеть литерал схему кодирования LZSS.

Примеры:

const string =
  "Император Карл-Франц обычно одет в полный доспех. Император Карл-Франц. обычно одет. в полный доспех.";

const lzssEncoded = lzssEncode(string)

lzssEncoded.length // 63
lzssEncoded.schema // [ 0, 0, 0, 0, 0, 0, 53, 0 ]
lzssEncoded.data // [ 'И','м','п','е','р','а','т','о','р',' ','К','а','р','л','-','Ф','р','а','н','ц',' ','о','б','ы','ч','н','о',' ','о','д','е','т',' ','в',' ','п','о','л','н','ы','й',' ','д','о','с','п','е','х','.',' ',[ 50, 14 ],[ 50, 6 ],'.',[ 51, 12 ],'.',[ 52, 14 ],'е','х','.' ],

Схема двоичного кодирования

LZSS Schema

4) LZ77

LZ77 — один из базовых алгоритмов сжатия текста, предложенный Лемпелем и Зивом в 1977 году. Этот алгоритм также использует скользящее окно для поиска повторяющихся последовательностей символов.

  • LZ77 кодирует символы и повторяющиеся шаблоны с помощью кортежей [смещение, длина, следующий символ].
  • Если совпадение найдено в конце Search Buffer, алгоритм проверяет его и применяет RLE, если это возможно.

Основные функции:

  • lz77BinaryEncode: Кодирует данные в бинарный буффер с использованием LZ77.
  • lz77BinaryDecode: Декодирует данные из бинарного буффера, сжатые с помощью LZ77.
  • lz77Encode: Позволяет увидеть литерал схему кодирования LZ77.

Примеры:

const string =
  "Император Карл-Франц обычно одет в полный доспех. Император Карл-Франц. обычно одет. в полный доспех.";

const lz77Encoded = lz77Encode(string)

lz77Encoded // [ [ 0, 0, 'И' ],[ 0, 0, 'м' ],[ 0, 0, 'п' ],[ 0, 0, 'е' ],[ 0, 0, 'р' ],[ 0, 0, 'а' ],[ 0, 0, 'т' ],[ 0, 0, 'о' ],[ 4, 1, ' ' ],[ 0, 0, 'К' ],[ 6, 1, 'р' ],[ 0, 0, 'л' ],[ 0, 0, '-' ],[ 0, 0, 'Ф' ],[ 12, 2, 'н' ],[ 0, 0, 'ц' ],[ 11, 1, 'о' ],[ 0, 0, 'б' ],[ 0, 0, 'ы' ],[ 0, 0, 'ч' ],[ 7, 1, 'о' ],[ 7, 2, 'д' ],[ 27, 1, 'т' ],[ 5, 1, 'в' ],[ 2, 1, 'п' ],[ 8, 1, 'л' ],[ 13, 1, 'ы' ],[ 0, 0, 'й' ],[ 7, 1, 'д' ],[ 7, 1, 'с' ],[ 43, 2, 'х' ],[ 0, 0, '.' ],[ 8, 1, 'И' ],[ 50, 15, 'р' ],[ 50, 3, '.' ],[ 51, 12, '.' ],[ 52, 15, 'х' ],[ 17, 1, '\u0000' ] ]

Схема двоичного кодирования

LZ77 Schema

5) BWT

Обратимая сортировка Барроуза-Уилера (BWT) — это алгоритм предварительной обработки данных, который переставляет символы текста для улучшения последующего сжатия. Одно из преимуществ этого метода — простота восстановления оригинального текста, достаточно сохранить всего одно число.

Основные функции:

  • bwtEncode: Кодирует текст с помощью BWT.
  • bwtDecode: Восстанавливает оригинальный текст из BWT-кодированных данных.

Примеры:

const string = 'banana'
const bwtEncoded = bwtEncode(string) // { bwt: 'annb$aa', index: 4 }

const bwtDecoded = bwtDecode(bwtEncoded.bwt, bwtEncoded.index) // 'banana'

6) RLE (Run-Length Encoding)

RLE — это простой, но эффективный алгоритм сжатия, который особенно хорошо работает с данными, содержащими длинные последовательности повторяющихся символов. Поэтому его часто применяют после BWT.

Основные функции:

  • rleEncode: Кодирует данные с использованием RLE.
  • rleDecode: Декодирует данные, сжатые с помощью RLE.

Примеры:

const string = 'aaab4bbbbbcc'
const rleEncoded = rleEncode(string) // "a3b�4b5c2"

7) Прочее

  • getByteLength: Функция возвращает размер строки в байтах

  • calculateOptimalBytesCompression: Функция вычисляет теоретически возможное минимальное количество байт для сжатия строки на основе энтропии Шеннона. Учтите, что эта оценка может не совпадать с фактическим результатом других методов сжатия.