Сегодня в: Давайте создадим что-то действительно классное на Javascript, и вы, вероятно, больше никогда не будете использовать сжатие LZSS или для краткости Lempel–Ziv–Storer–Szymanski. 🙌🏻 В предыдущем посте мы говорили о схеме кодирования LZ77. Мы обнаружили, что хотя в спецификации алгоритма сжатия DEFLATE упоминается его использование, на самом деле он не используется. 💩 Вместо этого он использует вариант схемы сжатия LZ, а именно LZSS. Но, конечно, мы все еще хотим иметь возможность создать библиотеку сжатия DEFLATE. Чтобы выполнить эту задачу, мы, любопытные и усердные разработчики, сегодня собираемся создать LZSS на Javascript.
ЛЗСС
LZSS имеет много общего с LZ77. Я начну с предположения, что вы уже знаете основы работы алгоритма LZ77. Если нет, то можете посмотреть мой предыдущий пост. Но для ясности давайте кратко повторим, как работает LZ77.
Обзор LZ77
LZ77 сжимает данные на основе повторяющихся последовательностей символов во входных данных. Он делает это, перемещая скользящее окно по входным данным, когда обрабатывает символы во входном потоке. Это окно состоит из:
- поисковый буфер: n символов, которые были обработаны и используются для проверки повторяющихся последовательностей символов.
- позиция кодирования: позиция текущего символа во входном потоке
- Упреждающий буфер: n символов, которые используются для получения максимально возможной длинной последовательности повторяющихся символов.
Размер окна можно настроить. Например, алгоритм DEFLATE утверждает, что смещение или расстояние составляет не более 32 КБ, а длина совпадения не превышает 258 байт. Это означает, что буфер поиска и просмотра ограничен. Есть компромисс. Чем больше ваш поисковый буфер, тем больше вероятность, что вы найдете совпадение. Но это также означает, что чем больше будет ваша кодировка, то есть вам нужно выделить байты для хранения потенциально длинного смещения.
Вывод, который он производит, представляет собой триплеты в форме [смещение, длина, символ]. Где смещение — это смещение в буфере поиска, длина — длина совпадения, а символ — первый несоответствующий символ. Если совпадений не найдено, выдается триплет в виде [0, 0, символ].
Следующий процесс повторяется до тех пор, пока не будут обработаны все символы:
- Проверьте, существует ли символ в нашей кодовой позиции в нашем буфере поиска.
a. Если он не выдает [0, 0, наш текущий символ]
б. Если он добавляет символы к нашему текущему символу, пока мы не достигнем первого несовпадающего символа или мы не дойдем до конца нашего поискового буфера и не выдадим [смещение в поисковом буфере, длина совпадения, несоответствующий символ].
Следует отметить, что мы можем превзойти нашу текущую позицию. Например, скажем, у нас есть A en, мы нашли его в нашем буфере поиска с -1, поэтому мы находимся в конце нашего буфера поиска. Основываясь на вышеизложенном, мы бы сказали, что мы закончили, не так ли? ну не обязательно. Предположим, что наш упреждающий буфер содержит AAAAB, мы можем продолжать сопоставление, пока не достигнем последнего A. Таким образом, в этом случае мы выдаем [1, 5, B]. Это означает, что мы бесплатно получили кодирование длин серий. - Обновить скользящее окно
Теперь при распаковке мы просто считываем все триплеты и преобразуем их обратно в исходную строку, где, когда мы генерируем вывод, вывод будет действовать как наш поисковый буфер. Что касается нашей закодированной длины прогона A, мы просто получаем и продолжаем добавлять ее к нашему выводу на протяжении всей прогона.
Чем LZSS отличается от LZSS
Итак, теперь мы знаем, как работает LZ77, чем отличается LZS? Что ж, одна из проблем с LZ77 заключается в том, что в его схеме указано, что каждая кодировка имеет форму триплета. Это означает, что даже не совпадающие символы получают дополнительные накладные расходы, что не является bueno. Например, если вы храните триплет как три байта, это означает, что каждый несоответствующий 8-битный символ теперь расширяется до одного-трех байтов. LZSS решает эту проблему следующим образом:
- используйте кодировку, которая хранит только пару длины и расстояния: [длина, расстояние]
- и кодирует символ или последовательность символов только в том случае, если он достигает точки безубыточности. Например, если ваша кодировка составляет 3 байта, то ваша точка безубыточности будет равна 3 байтам. Все, что ниже, вы будете расширять исходные данные.
Например, возьмем ввод ABCDAAABCD:
- В LZ77 это будет выглядеть так:
[<0, 0, A>, <0, 0, B>, <0, 0, C>, <0, 0, D>, <4, 1, A>, <6, 4, ''>]
- В LZSS с безубытком в 3 байта это будет выглядеть так:
[A, B, C, A, A, <4, 6>]
Как вы можете видеть в этом коротком примере, LZSS только как один закодированный кортеж для последних четырех байтов.
Вы можете подумать, что все в порядке, но как нам распаковать эти данные? Что ж, это хороший момент. Чтобы понять, что мы читаем, нам нужно хранить некоторую дополнительную информацию об информации, которую мы обрабатываем, то есть является ли это буквальным символом или парой длины-расстояния. В основном у нас есть два способа хранения этой информации: либо в виде битового флага для каждой записи. Таким образом, 1 для литерала и 0 для пары длины и расстояния. Или мы можем объединить 8 битов в байт, который затем используем для интерпретации следующих 8 записей в наших закодированных данных. В любом случае это означает, что нам нужно хранить дополнительную информацию. Если мы посмотрим на приведенный выше пример, это сведется к одному байту дополнительных данных. Это все еще намного меньше метаданных, чем использует LZ77.
Теперь давайте создадим эту присоску на Javascript.
Исходный код нашей библиотеки можно найти на Github: https://github.com/vincentcorbee/LZSS.
Я хотел бы начать с того, что это предназначено для изучения алгоритма и того, как мы можем реализовать его в Javascript. Не строить готовую к производству реализацию. Я стараюсь быть как можно более описательным в именах функций и переменных, поэтому, надеюсь, сам код может быть в значительной степени не требующим пояснений. Также эта реализация основана на предположении, что каждый символ на входе может быть прочитан как 8-битное целое число без знака.
Поскольку мы собираемся использовать Typescript, мы установим typescript, ts-node и types/nodes в качестве зависимостей для разработчиков. Следующие команды настроят базовую структуру, которая нам нужна для нашего проекта.
touch lzss && cd lzss yarn init -y yarn add -D ts-node typescript @types/node npx tsc --init mkdir src && mkdir src/lib && mkdir src/samples && mkdir src/modules touch src/lib/index.ts && touch src/index.ts && touch src/modules/index.ts && touch src/types.ts
Сначала мы настроим наши индексные файлы.
В index.ts добавить.
export * from './compress' export * from './decompress'
В lib/index.ts добавить.
export * from './get-options' export * from './get-match' export * from './get-lookahead-buffer' export * from './get-search-buffer' export * from './create-array-buffer'
И, наконец, в modules/index.ts добавить.
export * from './binary-reader' export * from './binary-writer'
Начнем с создания compress.ts в нашей папке src со следующим содержимым.
import { breakEven } from "./constants";
import { getOptions, getMatch, getLookaheadBuffer, getSearchBuffer, createArrayBuffer } from "./lib";
import { LZSSOptions, EncodedArray } from './types'
export function compress(
input: string,
options?: Partial<LZSSOptions>
) {
const { searchBufferLength, lookaheadBufferLength } = getOptions(options)
const encodedArray: EncodedArray = []
const flagBytes: number[] = []
const end = input.length - 1
let searchBuffer = ''
let codingPosition = 0
let uint8Length = 0
let flagByte = 0
let flagCount = 0
while (codingPosition <= end) {
const lookaheadBuffer = getLookaheadBuffer(input, codingPosition, lookaheadBufferLength)
const match = getMatch(
searchBuffer,
lookaheadBuffer,
breakEven
)
if (match) {
const [length, distance, matchedChars] = match
encodedArray.push([length, distance])
/*
We have length distance pair so we add a one to our flag byte.
*/
flagByte = flagByte << 1 | 1
uint8Length += 2
codingPosition += length
searchBuffer += matchedChars
}
else {
const [characterAtCodingPosition] = lookaheadBuffer
encodedArray.push(characterAtCodingPosition)
/*
We are going to store the symbol as is, so we add a 0 to our flag byte.
*/
flagByte <<= 1
uint8Length ++
codingPosition++
searchBuffer += characterAtCodingPosition
}
flagCount ++
searchBuffer = getSearchBuffer(searchBuffer, searchBufferLength)
/*
If we have a whole flag byte, add it to the flag byte array.
*/
if (flagCount === 8) {
flagBytes.push(flagByte)
flagCount = 0
flagByte = 0
}
}
/*
If we have a remaining flag byte, pad it to one byte and add it to the flag byte array.
*/
if (flagCount) flagBytes.push(flagByte <<= 8 - flagCount)
return createArrayBuffer(encodedArray, flagBytes, uint8Length)
}
Наша функция сжатия имеет много общего с нашей функцией сжатия lZ77. Он принимает входные данные и аргумент параметров для изменения длины буфера поиска и просмотра вперед. Разница заключается в добавлении байтов нашего флага. Помните, что нам нужно хранить информацию о типе записи, которую мы храним. И поскольку наш закодированный массив будет состоять из разных записей, нам нужно отслеживать его длину в 8-битных целых числах без знака, которые нам понадобятся для создания экземпляра нашего Uint8Array. Еще одна вещь, которая нам нужна, — это значение точки безубыточности.
Внутри нашего основного цикла мы получаем буфер просмотра, как и раньше, и вызываем getMatch. Эта функция теперь принимает дополнительный аргумент, а именно точку безубыточности, и возвращает ноль, если совпадения нет или мы не достигли точки безубыточности. В противном случае мы возвращаем длину, расстояние и совпадающие символы. В версии LZ77 мы использовали смещение, длину. Теперь используем длину, расстояние.
Теперь, если у нас есть совпадение, мы сохраняем пару длины и расстояния, а также добавляем единицу к байту флага. Мы также обновляем нашу длину uint 8 в соответствии с длиной нашего совпадения. Если у нас нет совпадения, мы просто сдвигаем байт флага на одну позицию влево, добавляя ноль. Мы также добавляем единицу к нашей длине uint 8. Наконец, мы проверяем, есть ли у нас целый байт. Если мы это сделаем, мы добавим его в наш массив байтов флага и сбросим байт флага.
Если наш цикл завершится, у нас может быть неполный байт флага. Если мы это сделаем, мы собираемся дополнить его нулями.
И, наконец, мы вызываем createArrayBuffer с нашим закодированным массивом, нашим блестящим новым байтом флага и длиной uint 8.
Теперь давайте сначала посмотрим на обновленную функцию совпадения. Создайте get-match.ts в нашей папке lib со следующим содержимым:
import { Match } from "../types"
export function getMatch(searchBuffer: string, lookaheadBuffer: string, breakEven: number): Match | null {
const [char] = lookaheadBuffer
let distance = 0
let length = 0
let matchedChars = searchBuffer.lastIndexOf(char) === -1 ? null : char
if (!matchedChars) return null
const searchBufferEnd = searchBuffer.length
let indexLookaheadBuffer = lookaheadBuffer.length
while (indexLookaheadBuffer > 0) {
const chars = lookaheadBuffer.substring(0, indexLookaheadBuffer)
const indexInSearchBuffer = searchBuffer.lastIndexOf(chars)
if (indexInSearchBuffer > -1) {
length = chars.length
matchedChars = chars
distance = searchBufferEnd - indexInSearchBuffer
/* Get the run length of the matched chars in the lookahead buffer */
if (indexInSearchBuffer + chars.length === searchBufferEnd) {
while (indexLookaheadBuffer <= lookaheadBuffer.length) {
const remainingChars = lookaheadBuffer.substring(indexLookaheadBuffer)
const match = remainingChars.indexOf(chars) === 0
if (!match) break
matchedChars += chars
indexLookaheadBuffer += chars.length
length = matchedChars.length
}
}
break
}
indexLookaheadBuffer--
}
/*
If our length is bigger then the break even point, we return a match.
Otherwise we return null
*/
if (length > breakEven) return [length, distance, matchedChars]
return null
}
Поскольку мы уже обсуждали это в предыдущем посте, мы собираемся посмотреть, что изменилось. Одно отличие состоит в том, что вместо смещения, длины мы теперь используем формулировку длина, расстояние. Также мы не возвращаем несоответствующую кодировку, мы просто возвращаем null. Если у нас есть совпадение, мы проверяем, превышает ли оно нашу точку безубыточности. Если да, то 🎉 возвращаем нашу кодировку, если нет — возвращаем null.
В types.ts добавьте следующее. Мы изменили кодировку, чтобы она была либо строкой, либо кортежем с [числом, числом]. Также мы добавили тип для нашего матча.
export type LZSSOptions = {
searchBufferLength: number
lookaheadBufferLength: number
}
export type Encoding = string | [number, number]
export type Match = [number, number, string]
export type EncodedArray = Encoding[]
В нашей папке lib создайте get-options.ts со следующим содержимым.
import { LZSSMaxSearchBufferLength, LZSSMaxLookaheadBufferLength } from "../constants";
import { LZSSOptions } from "../types";
export function getOptions(options: Partial<LZSSOptions> = {}): LZSSOptions {
const { searchBufferLength = 255, lookaheadBufferLength = 15 } = options
return {
searchBufferLength: Math.min(searchBufferLength, LZSSMaxSearchBufferLength),
lookaheadBufferLength: Math.min(lookaheadBufferLength, LZSSMaxLookaheadBufferLength)
}
}
Этот тоже почти такой же. Мы ограничиваем длину обоих буферов, потому что собираемся хранить наше смещение как 12 бит, а нашу длину как 4 бита. Таким образом, максимальная длина нашего поискового буфера равна 0xfff или 4095, а буфера упреждения — 0xf или 15.
В нашей папке src мы создаем constants.ts, мы добавили нашу точку безубыточности.
export const LZSSMaxSearchBufferLength = 0xfff export const LZSSMaxLookaheadBufferLength = 0xf export const breakEven = 0x2
Для нашего упреждающего буфера мы создаем get-lookahead-buffer.ts в нашей папке lib.
export function getLookaheadBuffer(
input: string,
codingPosition: number,
lookaheadBufferLength: number,
) {
/*
Return the lookahead buffer plus the current character
*/
return input.substring(codingPosition, codingPosition + lookaheadBufferLength)
}
Здесь мы по-прежнему возвращаем только подстроку наших входных данных на основе нашей позиции в коде и нашей длины поискового буфера.
В нашей папке lib создайте get-search-buffer-ts со следующим содержимым:
export function getSearchBuffer (searchBuffer: string, searchBufferLength: number) {
const currentLengthSearchBuffer = searchBuffer.length
/*
Move the search buffer n positions over based on the difference
between the current lenght of the search buffer and the max length of our search buffer
*/
if (currentLengthSearchBuffer >= searchBufferLength) return searchBuffer.substring(currentLengthSearchBuffer - searchBufferLength)
return searchBuffer
}
Этот все тот же, что и в нашей версии LZ77.
Помните наш бинарный ридер и писатель? Я уверен. 🥹 Мы немного модифицировали их для LZSS плюс я исправил ошибку 😱.
В папке с модулями создайте binary-reader.ts со следующим содержимым:
export class BinaryReader {
protected pos: number
protected bitCount: number
view: DataView
constructor(arrayBuffer: ArrayBuffer) {
this.view = new DataView(arrayBuffer)
this.pos = 0
this.bitCount = 0
}
protected getData(type = 'Uint8') {
if (this.view.byteLength > this.pos) {
// @ts-ignore
return this.view[`get${type}`](this.pos++)
}
throw new RangeError()
}
get buffer () {
return this.view.buffer
}
getBytePosition() {
return this.pos
}
seek(pos: number) {
const oldPos = this.pos
this.pos = pos
return oldPos
}
peak(index = this.pos) {
if (this.view.byteLength > index && index > -1) {
return this.view.getUint8(index)
}
return null
}
peakNext() {
const index = this.pos + 1
if (this.view.byteLength > index && index > -1) {
return this.view.getUint8(index)
}
return null
}
getUint16() {
return (this.getData() << 8) | this.getData()
}
getUint8() {
return this.getData()
}
getLengthDistancePair() {
const data = this.getUint16()
return [data >>> 12, data & 0xfff]
}
getCharacter() {
const uint8 = this.getData()
return uint8 ? String.fromCharCode(uint8) : ''
}
}
Мы добавили функцию с именемpeakNext, которая позволяет нам просмотреть следующую запись. Нам это нужно, когда мы распаковываем позже. Кроме того, теперь у нас есть функция getLengthDistancePair, которая возвращает (вы, вероятно, ее запустили) пару длины и расстояния.
Затем в той же папке создайте binary-writer.ts со следующим содержимым:
import { Encoding } from '../types';
import { BinaryReader } from './binary-reader'
export class BinaryWriter extends BinaryReader {
constructor(length: number) {
super(new ArrayBuffer(length))
}
private setData(data: number, type = 'Uint8') {
let advance = 0
switch(type) {
case 'Uint16':
advance = 2
break;
default:
advance = 1
}
if (this.view.byteLength > this.pos) {
// @ts-ignore
this.view[`set${type}`](this.pos, data)
this.pos += advance
return this
}
return this
}
setLengthDistancePair(encoding: Encoding) {
if (typeof encoding == 'string') throw Error('Encoding is not a length distance pair')
return this.setUint16(encoding[0] << 12 | encoding[1])
}
setUint16(data: number) {
return this.setData(data, 'Uint16')
}
setUint8(data: number) {
return this.setData(data)
}
}
Здесь мы добавили функцию setLengthDistancePair, которая принимает кодировку, и если это массив с длиной и расстоянием, мы сохраняем его как Uint16.
Теперь для нашей последней фазы в части сжатия, создания нашего буфера массива. Создайте create-array-buffer.ts в нашей папке lib со следующим содержимым:
import { BinaryWriter } from "../modules";
import { EncodedArray } from "../types";
import { shouldAddFlagByte } from "./should-add-flag-byte";
export function createArrayBuffer(encodedData: EncodedArray, flagBytes: number[], uint8Length: number) {
const binaryWriter = new BinaryWriter(uint8Length + flagBytes.length)
const lengthEncodedData = encodedData.length
encodedData.forEach((encoding, index) => {
if (shouldAddFlagByte(index, lengthEncodedData)) binaryWriter.setUint8(flagBytes[index / 8])
if (typeof encoding === 'string') binaryWriter.setUint8(encoding.charCodeAt(0))
else binaryWriter.setLengthDistancePair(encoding)
})
return binaryWriter.buffer
}
Этот немного отличается от версии LZ77. Сначала мы создаем двоичный модуль записи с длиной uint8 и длиной байтов нашего флага. Затем мы перебираем всю нашу кодировку. Поскольку мы храним 8 флагов на байт, нам нужно переплетать наш вывод с этими байтами каждые 8 байт, начиная с нуля. Итак, первое, что мы делаем, это проверяем, нужно ли вставлять флаговый байт. Если мы это делаем, мы записываем один в наш буфер. Затем мы проверяем, является ли наша кодировка строкой, если это так, у нас есть литеральный символ, поэтому мы записываем его как uint8 в наш буфер. Если у нас есть пара длины и расстояния, мы вставляем ее в наш буфер, когда наша новая блестящая функция.
Для нашей вспомогательной функции создайте lib/should-add-flag-byte.ts.
export function shouldAddFlagByte(index: number, lengthEncodedData: number) {
return index == 0 || lengthEncodedData !== 8 && index % 8 === 0 && index < lengthEncodedData
}
Нам нужно вставить байт флага, если мы находимся в начале или если наш индекс кратен 8.
Теперь наша компрессия завершена и очищена от пыли. 🕺🏻
Распаковать
Давайте теперь распаковываем, поэтому в нашей папке src создайте decompress.ts.
import { BinaryReader } from "./modules"
export function decompress(buffer: ArrayBuffer) {
const binaryReader = new BinaryReader(buffer)
let output = ''
let flagByte = binaryReader.getUint8()
let flagBytePosition = 7
while (binaryReader.peak() !== null) {
const flag = flagByte & 2**(flagBytePosition)
if (flag == 0) output += binaryReader.getCharacter()
else {
const [length, distance] = binaryReader.getLengthDistancePair()
const startIndex = output.length - distance
const overflow = Math.max(startIndex + length - output.length, 0)
const chars = output.substring(startIndex, startIndex + length)
if (overflow) {
let runLength = length / (length - overflow)
while (runLength > 0) {
output += chars
runLength--
}
} else {
output += chars
}
}
flagBytePosition --
if (flagBytePosition < 0 && binaryReader.peakNext() !== null) {
flagByte = binaryReader.getUint8()
flagBytePosition = 7
}
}
return output
}
Как видите, это немного дольше, чем распаковка для LZ77. Это потому, что нам нужно обработать байт флага. Итак, давайте посмотрим на изменения, которые мы сделали. Мы начинаем с получения байта флага, поскольку мы находимся в начале нашего ввода. Затем мы устанавливаем нашу позицию байта на 7, вы поймете, почему всего за секунду. Наш основной цикл будет работать так же, как и раньше, пока у нас есть данные.
Начнем с получения флага. Мы делаем это, просто проверяя, установлен ли бит в позиции байта флага, в которой мы находимся. Таким образом, в нашем первом запуске наша позиция байта флага равна 7, что дает нам 2⁷, а в двоичном формате это 1000 0000. Затем двоичный оператор И возвращает нам единицу для каждой битовой позиции, в которой установлена единица. Поскольку в нашей маске установлен только один бит, мы можем проверить, установлен ли флаг в позиции n-го бита.
Теперь, если наш флаг равен 0, мы просто получаем наш символ. Если это не так, мы получаем нашу пару длины и расстояния и продолжаем, как в LZ77. Наконец, мы уменьшаем позицию байта нашего флага. Наконец, если мы исчерпали наш байт флага, мы проверяем, есть ли еще данные. Если это так, мы обновляем байт нашего флага и сбрасываем наш flagBytePosition на 7.
Если все по плану, теперь мы сможем распаковаться, так что давайте проверим. 🤞🏻
Давайте проверим
В нашей папке src создайте test.ts со следующим содержимым:
import assert from "assert"
import { compress, decompress } from "."
import { sampleThree as input } from "./samples"
const compressed = compress(input)
const decompressed = decompress(compressed)
assert(decompressed === input)
console.log(compressed.byteLength, input.length)
if (compressed.byteLength < input.length) console.log('🎉')
else console.log('💩')
Как и в случае с LZ77, мы написали тест, чтобы проверить, совпадают ли наши исходные данные и данные распаковки, и заслуживаем ли мы аплодисментов или, по крайней мере, счастливой какашки.
В папке сэмплов находятся шесть разных сэмплов. Вы можете заменить sampleOne на любой из других семплов. Образцы можно найти на github.
Итак, давайте проведем несколько тестов. Я также включу результат, который мы получили с LZ77, чтобы мы могли сравнить разницу. Чтобы запустить тест, используйте следующую команду в нашей корневой папке:
yarn ts-node src/test.ts
Давайте запустим наш тест с образцом один.
LZSS 11 12 🎉 LZ77 15 12 💩
Да, мы получили сжатие с первой попытки. Если вы сравните это с LZ77, мы использовали на 4 байта меньше.
Давайте попробуем пример два
LZSS 12 45 🎉 LZ77 21 45 🎉
Хорошо, у нас все еще есть сжатие, и здесь мы использовали на 9 байт меньше, чем LZ77.
Следующий образец номер три.
LZSS 2514 3059 🎉 LZ77 2823 3059 🎉
В очередной раз мы обыграли LZ77 💪🏻
Посмотрим, что нам даст четвертая выборка.
LZSS 20204 24543 🎉 LZ77 22374 24543 🎉
Мы просто не можем остановиться! Мне начинает жалко LZ77
Хорошо, последний шанс для LZ77 🥁
LZSS 13 25 🎉 LZ77 21 25 🎉
Аааа, мы снова его обыграли.
Как вы можете видеть, LZSS намного лучше сжимает данные, чем LZ77, за счет изменения формы кодирования и принятия решения на основе точки безубыточности, стоит ли вообще кодировать символы или просто выводить их как есть.
Заключение
Итак, это конец строки для LZSS, мы это сделали.👏🏻 Это также приближает нас на один шаг к построению алгоритма DEFLATE. Я надеюсь, что вы, как и я, получили удовольствие от работы с LZSS в Javascript.
