Một người dùng khác muốn ghi một phần dữ liệu mới vào ổ cứng nhưng anh ta không có đủ dung lượng trống để thực hiện việc này. Tôi cũng không muốn xóa bất cứ thứ gì vì “mọi thứ đều rất quan trọng và cần thiết”. Và chúng ta nên làm gì với nó?
Không ai có vấn đề này. Có hàng terabyte thông tin trên ổ cứng của chúng ta và lượng này không có xu hướng giảm. Nhưng nó độc đáo đến mức nào? Cuối cùng, tất cả các tệp chỉ là tập hợp các bit có độ dài nhất định và rất có thể, tệp mới không khác nhiều so với tệp đã được lưu trữ.
Rõ ràng rằng việc tìm kiếm những mẩu thông tin đã được lưu trữ trên ổ cứng, nếu không phải là một thất bại thì ít nhất không phải là một nhiệm vụ hiệu quả. Mặt khác, nếu chênh lệch nhỏ thì bạn có thể điều chỉnh một chút...
TL;DR - nỗ lực thứ hai để nói về một phương pháp tối ưu hóa dữ liệu kỳ lạ bằng cách sử dụng các tệp JPEG, giờ đây ở dạng dễ hiểu hơn.
Về bit và sự khác biệt
Nếu bạn lấy hai phần dữ liệu hoàn toàn ngẫu nhiên thì trung bình một nửa số bit chúng chứa trùng nhau. Thật vậy, trong số các cách bố trí có thể có cho mỗi cặp ('00, 01, 10, 11'), chính xác một nửa có cùng giá trị, mọi thứ ở đây đều đơn giản.
Nhưng tất nhiên, nếu chúng ta chỉ lấy hai tệp và ghép cái này vào cái thứ hai thì chúng ta sẽ mất một trong số chúng. Nếu chúng tôi lưu các thay đổi, chúng tôi sẽ chỉ phát minh lại , tồn tại hoàn toàn tốt mà không cần đến chúng tôi, mặc dù nó thường không được sử dụng cho các mục đích tương tự. Chúng ta có thể cố gắng nhúng một chuỗi nhỏ hơn vào một chuỗi lớn hơn, nhưng ngay cả như vậy, chúng ta vẫn có nguy cơ mất các phân đoạn dữ liệu quan trọng nếu sử dụng nó một cách liều lĩnh với mọi thứ.
Giữa cái gì và cái gì thì sự khác biệt có thể được loại bỏ? Chà, nghĩa là, một tệp mới do người dùng viết chỉ là một chuỗi các bit mà chúng ta không thể tự mình làm bất cứ điều gì. Sau đó, bạn chỉ cần tìm những bit như vậy trên ổ cứng để có thể thay đổi chúng mà không cần phải lưu trữ phần chênh lệch, để bạn có thể sống sót sau khi mất chúng mà không gây hậu quả nghiêm trọng. Và việc thay đổi không chỉ tệp trên chính FS mà còn một số thông tin ít nhạy cảm hơn bên trong nó là điều hợp lý. Nhưng cái nào và như thế nào?
Phương pháp lắp
Các tập tin nén bị mất sẽ được giải cứu. Tất cả các tệp jpeg, mp3 và các tệp khác này, mặc dù bị nén kém nhưng vẫn chứa một loạt bit có thể được thay đổi một cách an toàn. Có thể sử dụng các kỹ thuật tiên tiến để sửa đổi các thành phần của chúng một cách dễ dàng ở các giai đoạn mã hóa khác nhau. Chờ đợi. Những kỹ thuật tiên tiến... sự biến đổi không thể nhận ra... từng chút một... nó gần giống như vậy !
Thật vậy, việc nhúng thông tin này vào thông tin khác gợi nhớ đến các phương pháp của cô ấy không giống bất kỳ phương pháp nào khác. Tôi cũng bị ấn tượng bởi sự không thể nhận biết được của những thay đổi xảy ra đối với các giác quan của con người. Nơi mà các đường dẫn khác nhau được giữ bí mật: nhiệm vụ của chúng tôi là người dùng phải nhập thông tin bổ sung vào ổ cứng của mình; điều đó sẽ chỉ gây hại cho anh ta. Anh ấy sẽ lại quên mất.
Vì vậy, mặc dù có thể sử dụng chúng nhưng chúng ta cần thực hiện một số sửa đổi. Và sau đó tôi sẽ kể và hiển thị chúng bằng ví dụ về một trong các phương pháp hiện có và định dạng tệp phổ biến.
Về chó rừng
Nếu bạn thực sự bóp nó, nó sẽ là thứ dễ nén nhất trên thế giới. Tất nhiên, chúng ta đang nói về các tệp JPEG. Không chỉ có rất nhiều công cụ và phương pháp hiện có để nhúng dữ liệu vào đó mà đây còn là định dạng đồ họa phổ biến nhất trên hành tinh này.
Tuy nhiên, để không tham gia vào việc chăn nuôi chó, bạn cần giới hạn lĩnh vực hoạt động của mình trong các tệp có định dạng này. Không ai thích những hình vuông đơn sắc xuất hiện do bị nén quá mức, vì vậy bạn cần hạn chế làm việc với một tệp đã được nén, tránh mã hóa lại. Cụ thể hơn, với các hệ số nguyên, còn lại sau các hoạt động chịu trách nhiệm về mất dữ liệu - DCT và lượng tử hóa, được hiển thị hoàn hảo trong sơ đồ mã hóa (nhờ wiki của Thư viện Quốc gia Bauman):
Có nhiều phương pháp khả thi để tối ưu hóa tệp jpeg. Có tối ưu hóa không mất dữ liệu (jpegtran), có tối ưu hóa "“, điều này thực sự đóng góp vào điều gì đó khác, nhưng chúng tôi không quan tâm đến chúng. Xét cho cùng, nếu người dùng sẵn sàng nhúng thông tin này vào thông tin khác để tăng dung lượng ổ đĩa trống, thì anh ta đã tối ưu hóa hình ảnh của mình từ lâu hoặc hoàn toàn không muốn làm điều này vì sợ giảm chất lượng.
F5
Cả một nhóm thuật toán phù hợp với những điều kiện này mà bạn có thể tự làm quen . Tiên tiến nhất trong số đó là thuật toán của Andreas Westfeld, nghiên cứu các hệ số của thành phần độ sáng, vì mắt người ít nhạy cảm nhất với những thay đổi của nó. Hơn nữa, nó sử dụng kỹ thuật nhúng dựa trên mã hóa ma trận, giúp thực hiện ít thay đổi hơn khi nhúng cùng một lượng thông tin, kích thước của vùng chứa được sử dụng càng lớn.
Bản thân các thay đổi tập trung vào việc giảm một giá trị tuyệt đối của các hệ số trong một số điều kiện nhất định (nghĩa là không phải lúc nào cũng vậy), điều này cho phép bạn sử dụng F5 để tối ưu hóa việc lưu trữ dữ liệu trên ổ cứng của mình. Vấn đề là hệ số sau khi thay đổi như vậy rất có thể sẽ chiếm ít bit hơn sau khi mã hóa Huffman do sự phân bố thống kê của các giá trị trong JPEG và các số XNUMX mới sẽ mang lại lợi ích khi mã hóa chúng bằng RLE.
Các sửa đổi cần thiết nhằm loại bỏ phần chịu trách nhiệm về tính bí mật (sắp xếp lại mật khẩu), giúp tiết kiệm tài nguyên và thời gian thực thi, đồng thời thêm cơ chế làm việc với nhiều tệp thay vì từng tệp một. Người đọc có thể không quan tâm đến quá trình thay đổi một cách chi tiết hơn, vì vậy hãy chuyển sang mô tả cách thực hiện.
Công nghệ cao
Để chứng minh cách thức hoạt động của phương pháp này, tôi đã triển khai phương pháp này bằng C thuần túy và thực hiện một số tối ưu hóa cả về tốc độ thực thi và bộ nhớ (bạn không thể tưởng tượng được những bức ảnh này nặng bao nhiêu nếu không nén, ngay cả trước DCT). Đa nền tảng đạt được bằng cách sử dụng kết hợp các thư viện , и , mà chúng tôi cảm ơn họ. Tất cả điều này được tập hợp lại với nhau bởi 'make', vì vậy người dùng Windows muốn tự cài đặt một số Cygwin để đánh giá hoặc tự mình xử lý Visual Studio và các thư viện.
Việc triển khai có sẵn ở dạng tiện ích bảng điều khiển và thư viện. Những người quan tâm có thể tìm hiểu thêm về cách sử dụng cái sau trong readme trong kho lưu trữ trên Github, liên kết mà tôi sẽ đính kèm ở cuối bài.
Cách sử dụng?
Cẩn thận. Các hình ảnh được sử dụng để đóng gói được chọn bằng cách tìm kiếm bằng biểu thức chính quy trong thư mục gốc đã cho. Sau khi hoàn thành, các tệp có thể được di chuyển, đổi tên và sao chép theo ý muốn trong phạm vi ranh giới của nó, thay đổi tệp và hệ điều hành, v.v. Tuy nhiên, bạn nên hết sức cẩn thận và không thay đổi nội dung ngay lập tức dưới bất kỳ hình thức nào. Việc mất giá trị dù chỉ một bit cũng có thể khiến thông tin không thể khôi phục được.
Sau khi hoàn thành, tiện ích sẽ để lại một tệp lưu trữ đặc biệt chứa tất cả thông tin cần thiết để giải nén, bao gồm cả dữ liệu về hình ảnh được sử dụng. Bản thân nó nặng khoảng vài kilobyte và không có bất kỳ tác động đáng kể nào đến dung lượng ổ đĩa bị chiếm dụng.
Bạn có thể phân tích dung lượng có thể có bằng cách sử dụng cờ '-a': './f5ar -a [thư mục tìm kiếm] [biểu thức chính quy tương thích với Perl]'. Việc đóng gói được thực hiện bằng lệnh './f5ar -p [thư mục tìm kiếm] [biểu thức chính quy tương thích Perl] [tệp đã đóng gói] [tên lưu trữ]' và giải nén bằng './f5ar -u [tệp lưu trữ] [tên tệp đã khôi phục ]' .
Trình diễn công việc
Để cho thấy tính hiệu quả của phương pháp, tôi đã tải lên bộ sưu tập 225 bức ảnh hoàn toàn miễn phí về những chú chó từ dịch vụ và tìm thấy trong tài liệu một bản pdf lớn dài 45 mét của tập thứ hai Knuta.
Trình tự khá đơn giản:
$ du -sh knuth.pdf dogs/
44M knuth.pdf
633M dogs/
$ ./f5ar -p dogs/ .*jpg knuth.pdf dogs.f5ar
Reading compressing file... ok
Initializing the archive... ok
Analysing library capacity... done in 17.0s
Detected somewhat guaranteed capacity of 48439359 bytes
Detected possible capacity of upto 102618787 bytes
Compressing... done in 39.4s
Saving the archive... ok
$ ./f5ar -u dogs/dogs.f5ar knuth_unpacked.pdf
Initializing the archive... ok
Reading the archive file... ok
Filling the archive with files... done in 1.4s
Decompressing... done in 21.0s
Writing extracted data... ok
$ sha1sum knuth.pdf knuth_unpacked.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth_unpacked.pdf
$ du -sh dogs/
551M dogs/Ảnh chụp màn hình dành cho người hâm mộ
Tệp đã giải nén có thể và vẫn nên được đọc:
Như bạn có thể thấy, từ 633 + 36 == 669 megabyte dữ liệu ban đầu trên ổ cứng, chúng tôi đã đạt được 551 dễ chịu hơn. Sự khác biệt cơ bản như vậy được giải thích bằng việc giảm giá trị của các hệ số, ảnh hưởng đến chúng nén không mất dữ liệu tiếp theo: việc giảm từng cái một có thể dễ dàng “ cắt bỏ một vài byte khỏi tệp cuối cùng. Tuy nhiên, đây vẫn là tình trạng mất dữ liệu, mặc dù là một tổn thất cực kỳ nhỏ mà bạn sẽ phải đối mặt.
May mắn thay, chúng hoàn toàn vô hình trước mắt. Trong phần spoiler (vì habrastorage không thể xử lý các tệp lớn), người đọc có thể đánh giá sự khác biệt bằng mắt và cường độ của chúng, thu được bằng cách trừ các giá trị của thành phần đã thay đổi so với bản gốc: , , (màu càng xỉn thì độ chênh lệch trong khối càng nhỏ).
Thay vì một kết luận
Xem xét tất cả những khó khăn này, việc mua một ổ cứng hoặc tải mọi thứ lên đám mây có vẻ như là một giải pháp đơn giản hơn nhiều cho vấn đề. Nhưng ngay cả khi chúng ta đang sống trong một thời đại tuyệt vời như vậy, không có gì đảm bảo rằng ngày mai bạn vẫn có thể truy cập trực tuyến và tải tất cả dữ liệu bổ sung của mình lên đâu đó. Hoặc ra cửa hàng và mua cho mình một ổ cứng nghìn terabyte khác. Nhưng bạn luôn có thể sử dụng những ngôi nhà hiện có.
->
Nguồn: www.habr.com