pkg/compression/bookstack.go - master - pxlxnski/StringCompressionAlgorhitms

pkg/compression/bookstack.go
201 строка4 KB
Egor Polyanskiy
Initial gilbert-moore structure
13 ноя 2025, 21:54
13 ноя 2025, 21:543228cdb
package compression

import (
	"encoding/binary"
	"fmt"
	"os"
)

type BookStack struct {
	stack []byte
}

func NewBookStack() *BookStack {
	stack := make([]byte, 256)
	for i := 0; i < 256; i++ {
		stack[i] = byte(i)
	}

	return &BookStack{
		stack: stack,
	}
}

// кодирует байт. возвращает его позицию и перемещает в начало
func (bs *BookStack) Encode(symbol byte) byte {
	var position byte
	for i := 0; i < 256; i++ {
		if bs.stack[i] == symbol {
			position = byte(i)
			break
		}
	}
	// Перемещаем символ в начало
	if position > 0 {
		temp := bs.stack[position]
		// Сдвиг вправо
		for i := position; i > 0; i-- {
			bs.stack[i] = bs.stack[i-1]
		}
		// Помещаем символ в начало
		bs.stack[0] = temp
	}

	return position
}

// декодирует позицию. возвращает байт на этой позиции и перемещает в начало
func (bs *BookStack) Decode(position byte) byte {
	symbol := bs.stack[position]

	// Перемещаем символ в начало
	if position > 0 {
		temp := bs.stack[position]
		// Сдвигаем вправо
		for i := position; i > 0; i-- {
			bs.stack[i] = bs.stack[i-1]
		}
		// Помещаем в начало
		bs.stack[0] = temp
	}
	return symbol
}

// сжимает файл алгоритмом
func compressBookstack(inputFile, outputFile string) error {
	data, err := os.ReadFile(inputFile)
	if err != nil {
		return fmt.Errorf("ошибка чтения файла: %v", err)
	}
	if len(data) == 0 {
		return fmt.Errorf("файл пустой")
	}
	stack := NewBookStack()
	encoded := make([]byte, len(data))
	for i, b := range data {
		encoded[i] = stack.Encode(b)
	}
	// RLE для улучшения сжатия
	compressed := applyRLE(encoded)
	return saveBookstackFile(outputFile, compressed, len(data))
}

// разжимает файл
func decompressBookstack(inputFile, outputFile string) error {
	compressed, originalLength, err := loadBookstackFile(inputFile)
	if err != nil {
		return err
	}
	// Декодируем RLE
	encoded := decodeRLE(compressed, originalLength)
	stack := NewBookStack()

	// Декодируем данные
	decoded := make([]byte, len(encoded))
	for i, pos := range encoded {
		decoded[i] = stack.Decode(pos)
	}
	return os.WriteFile(outputFile, decoded, 0644)
}

// RLE кодирование
func applyRLE(data []byte) []byte {
	if len(data) == 0 {
		return data
	}

	var result []byte

	i := 0
	for i < len(data) {
		current := data[i]
		count := 1

		for i+count < len(data) && data[i+count] == current && count < 255 {
			count++
		}
		if count > 3 || current == 255 {
			result = append(result, 255, current, byte(count))
		} else {
			for j := 0; j < count; j++ {
				result = append(result, current)
			}
		}

		i += count
	}

	return result
}

// декодирует RLE
func decodeRLE(data []byte, expectedLength int) []byte {
	result := make([]byte, 0, expectedLength)

	i := 0
	for i < len(data) {
		if data[i] == 255 && i+2 < len(data) {
			value := data[i+1]
			count := int(data[i+2])

			for j := 0; j < count; j++ {
				result = append(result, value)
			}

			i += 3
		} else {
			result = append(result, data[i])
			i++
		}
	}

	return result
}

// сохраняет сжатые данные
func saveBookstackFile(filename string, compressed []byte, originalLength int) error {
	file, err := os.Create(filename)
	if err != nil {
		return err
	}
	defer file.Close()

	origLenBytes := make([]byte, 4)
	binary.LittleEndian.PutUint32(origLenBytes, uint32(originalLength))

	compressedSize := make([]byte, 4)
	binary.LittleEndian.PutUint32(compressedSize, uint32(len(compressed)))

	if _, err := file.Write(origLenBytes); err != nil {
		return err
	}
	if _, err := file.Write(compressedSize); err != nil {
		return err
	}
	if _, err := file.Write(compressed); err != nil {
		return err
	}

	return nil
}

// загружает сжатые данные
func loadBookstackFile(filename string) ([]byte, int, error) {
	data, err := os.ReadFile(filename)
	if err != nil {
		return nil, 0, err
	}

	if len(data) < 8 {
		return nil, 0, fmt.Errorf("файл слишком мал")
	}
	originalLength := int(binary.LittleEndian.Uint32(data[0:4]))
	compressedSize := int(binary.LittleEndian.Uint32(data[4:8]))

	if 8+compressedSize > len(data) {
		return nil, 0, fmt.Errorf("недостаточно данных")
	}
	compressed := data[8 : 8+compressedSize]

	return compressed, originalLength, nil
}