Nén/giải nén LZW trong điều kiện bộ nhớ thấp

Question

Ai cũng có thể cung cấp cho con trỏ cách tôi có thể thực hiện nén/giải nén lzw trong điều kiện bộ nhớ thấp (< 2k). điều đó có thể không?

Answer 1

Đề xuất tốt nhất của tôi là kiểm tra nguồn BusyBox và xem việc triển khai LZW của họ có đủ nhỏ để hoạt động trong môi trường của bạn không.

Answer 2

Đã hơn 15 năm kể từ lần cuối tôi chơi với thuật toán nén LZW, vì vậy hãy thực hiện các thao tác sau với một hạt muối.

Với những hạn chế về bộ nhớ, điều này sẽ khó khăn nhất. Từ điển bạn xây dựng sẽ tiêu thụ phần lớn những gì bạn có sẵn. (Giả sử rằng mã + bộ nhớ < = 2k.)

Chọn kích thước cố định nhỏ cho từ điển của bạn. Nói 1024 mục.

Hãy mỗi mục từ điển mang hình thức của ....

struct entry { 
    intType prevIdx; 
    charType newChar; 
}; 

Cấu trúc này làm cho đệ quy điển. Bạn cần mục ở chỉ mục trước có giá trị để nó hoạt động đúng. Điều này có khả thi không? Tôi không chắc. Tuy nhiên, chúng ta hãy giả định cho thời điểm đó là và tìm ra nơi nó dẫn chúng ta ...

Nếu bạn sử dụng các loại tiêu chuẩn cho int và char, bạn sẽ hết bộ nhớ nhanh. Bạn sẽ muốn đóng gói mọi thứ lại với nhau càng chặt càng tốt. 1024 mục sẽ mất 10 bit để lưu trữ. Nhân vật mới của bạn, có thể sẽ mất 8 bit. Tổng cộng = 18 bit.

18 bit * 1024 mục = 18432 bit hoặc 2304 byte.

Thoạt nhìn, điều này xuất hiện quá lớn. Chúng ta làm gì? Tận dụng lợi thế của thực tế là 256 mục đầu tiên đã được biết đến - bộ ascii mở rộng điển hình của bạn hoặc những gì có bạn. Điều này có nghĩa là chúng tôi thực sự cần 768 mục.

768 * 18 bit = 13824 bit hoặc 1728 byte.

Điều này khiến bạn có khoảng 320 byte để phát cùng với mã. Đương nhiên, bạn có thể chơi xung quanh với kích thước từ điển và xem những gì tốt cho bạn, nhưng bạn sẽ không kết thúc với rất nhiều không gian cho mã của bạn. Vì bạn đang tìm kiếm rất ít không gian mã, tôi mong rằng bạn sẽ kết thúc việc lập trình.

Tôi hy vọng điều này sẽ hữu ích.

Answer 3

Thư viện zlib mà mọi người sử dụng đều cồng kềnh trong số các vấn đề khác (để nhúng). Tôi khá chắc chắn nó sẽ không làm việc cho trường hợp của bạn. Tôi đã có một bộ nhớ nhiều hơn một chút có thể 16K và không thể làm cho nó phù hợp. Nó phân bổ và zeros khối lớn của bộ nhớ và giữ bản sao của các công cụ, vv Các thuật toán có thể có thể làm điều đó, nhưng việc tìm kiếm mã hiện tại là thách thức.

Tôi đã đi với http://lzfx.googlecode.com Vòng giải nén là nhỏ, nó là loại nén lz cũ dựa vào kết quả trước, do đó bạn cần truy cập vào kết quả không nén ... byte tiếp theo là 0x5, byte tiếp theo là 0x23, 15 byte tiếp theo là bản sao của 15 200 byte trước, 6 byte tiếp theo là bản sao của 127 trước ... thuật toán lz mới hơn là bảng chiều rộng biến có thể lớn hoặc lớn tùy thuộc vào cách được triển khai .

Tôi đã xử lý dữ liệu lặp đi lặp lại và cố gắng nén một vài K xuống vài trăm, tôi nghĩ rằng nén là khoảng 50%, không lớn nhưng công việc và thói quen giải nén rất nhỏ.Gói lzfx ở trên là nhỏ, không giống như zlib, giống như hai hàm chính có mã ngay tại đó, không phải hàng tá tệp. Bạn có thể thay đổi độ sâu của bộ đệm, có lẽ cải thiện thuật toán nén nếu bạn mong muốn. Tôi đã phải sửa đổi các mã giải nén (như 20 hoặc 30 dòng mã có lẽ) nó đã được con trỏ nặng và tôi chuyển nó sang mảng vì trong môi trường nhúng của tôi các con trỏ ở sai vị trí. Ghi có thể là một đăng ký thêm hoặc không phụ thuộc vào cách bạn thực hiện nó và trình biên dịch của bạn. Tôi cũng đã làm điều đó vì vậy tôi có thể tóm tắt các fetches và các cửa hàng của các byte như tôi đã có chúng đóng gói vào bộ nhớ mà không phải là byte địa chỉ.

Nếu bạn tìm thấy điều gì đó tốt hơn, hãy đăng nó ở đây hoặc ping tôi qua stackoverflow, tôi cũng rất quan tâm đến các giải pháp nhúng khác. Tôi tìm kiếm khá một chút và ở trên là một trong những hữu ích duy nhất tôi tìm thấy và tôi đã may mắn rằng dữ liệu của tôi là như vậy mà nó nén đủ tốt bằng cách sử dụng thuật toán đó ... cho bây giờ.

Answer 4

Ai cũng có thể cung cấp cho con trỏ cách tôi có thể triển khai nén/giải nén lzw trong điều kiện bộ nhớ thấp (< 2k). điều đó có thể không?

Vì sao LZW? LZW cần rất nhiều bộ nhớ. Nó dựa trên tỷ lệ băm/từ điển và nén tỉ lệ thuận với kích thước băm/từ điển. Nhiều bộ nhớ hơn - nén tốt hơn. Ít bộ nhớ hơn - đầu ra có thể lớn hơn đầu vào.

Tôi chưa chạm mã hóa cho thời gian dài rất, nhưng IIRC Huffman coding thì tốt hơn một chút khi nói đến mức tiêu thụ bộ nhớ.

Nhưng tất cả phụ thuộc vào loại thông tin bạn muốn nén.

Answer 5

Nếu lựa chọn thuật toán nén không được đặt trong đá, bạn có thể thử gzip/LZ77 thay thế. Dưới đây là một thực hiện rất đơn giản tôi đã sử dụng và thích nghi một lần:

ftp://quatramaran.ens.fr/pub/madore/misc/myunzip.c

Bạn sẽ cần phải dọn dẹp đường nó đọc đầu vào, xử lý lỗi, vv nhưng đó là một khởi đầu tốt. Nó có lẽ cũng là cách quá lớn nếu dữ liệu và mã của bạn cần phải phù hợp trong 2k, nhưng ít nhất là kích thước dữ liệu là nhỏ rồi.

Điểm cộng lớn là miền công cộng nên bạn có thể sử dụng nó theo cách bạn muốn!

Answer 6

Tôi đã sử dụng LZSS. Tôi đã sử dụng code từ Haruhiko Okumura làm cơ sở. Nó sử dụng phần cuối của dữ liệu không nén (2K) làm từ điển. Mã tôi liên kết có thể được sửa đổi để sử dụng gần như không có bộ nhớ nếu bạn có tất cả các dữ liệu chưa nén sẵn có trong bộ nhớ. Với một chút googling bạn sẽ thấy rằng rất nhiều triển khai khác nhau.

Answer 7

typedef unsigned int  UINT; 
typedef unsigned char BYTE; 

BYTE *lzw_encode(BYTE *input ,BYTE *output, long filesize, long &totalsize); 
BYTE *lzw_decode(BYTE *input ,BYTE *output, long filesize, long &totalsize);