Nén văn bản (tiếng Anh Text Compression, Lossless data compression) là thay đổi cách biểu diễn tệp văn bản nhằm mục đích giảm không gian lưu trữ và giảm thời gian truyền tải trên mạng, nhưng vẫn có thể tái tạo chính xác tệp văn bản ban đầu.
Số lượng văn bản cần lưu trữ và truyền tải giữa các máy tính tăng nhanh làm tăng nhu cầu nén văn bản mặc dù các công nghệ lưu trữ và truyền tải vẫn tiếp tục cải tiến. Một đĩa compact (CD) có thể lưu trữ 600 triệu ký tự, đủ cho một bách khoa thư. Tuy khả năng lưu trữ lớn như vậy nó vẫn không đủ cho các mục đích lưu trữ khác mà các nhà xuất bản đang tìm cách nén văn bản để tránh xuất bản ấn phẩm thành nhiều tập trên các đĩa CD. Tiết kiệm bộ nhớ lưu trữ là lý do chính dẫn tới sử dụng nén văn bản. Nén làm tăng lượng thông tin, nhiều văn bản hơn được lưu trữ trong máy tính, dẫn tới tiết kiệm phần cứng lưu trữ hơn. Nén văn bản có thể đẩy nhanh tính toán các thuật toán trên máy tính, ví dụ tăng tốc độ tìm kiếm văn bản bằng cách nén khóa tìm kiếm thay cho giải nén văn bản đang tìm kiếm. Nén văn bản để truyền tải làm giảm kinh phí đồng thời làm giảm thời gian truyền. Văn bản có thể nén được là do thực tế một số ký tự xuất hiện thường xuyên hơn các ký tự khác và một số ký tự thường xuất hiện cùng nhau. Nén văn bản được quan tâm vì lý do kinh tế và thời gian, tuy nhiên nén văn bản cũng có một số nhược điểm, trong đó có thể là các dữ liệu nén khá nhạy cảm với lỗi. Đặc trưng chính của nén văn bản là nén không hao hụt thông tin, có nghĩa là văn bản sau giải nén giống hệt văn bản gốc.
Phương pháp nén[sửa]
Văn bản không nén được gọi là văn bản thô (raw, plain text), là trình tự các ký hiệu trong bộ chữ và mỗi chúng được biểu diễn bởi |log2|∑|| bít. Có phương pháp chính nén văn bản thành, đó là phương pháp ký hiệu (symbolwise), phương pháp phân tích cú pháp (cg. phương pháp trên cơ sở từ điển) và phương pháp trên cơ sở biến đổi (transform).
Phương pháp nén ký hiệu[sửa]
Mã hóa theo từng ký hiệu văn bản bằng cách gán từ mã (codeword) có độ dài khác nhau cho mỗi chúng. Đôi khi gọi phương pháp nén này là phương pháp thống kê vì nó phải xây dựng mô hình dữ liệu trên cơ sở thống kê phục vụ cho quá trình nén. Có ba loại mô hình, đó là: mô hình tĩnh, mô hình bán thích nghi (cg. mô hình bán tĩnh) và mô hình thích nghi. Tên mô hình dựa vào cách ước lượng xác suất khi duyệt văn bản đầu vào. Mô hình tĩnh là mô hình cố định mà cả bên nén và giải nén đều biết, nó không phụ thuộc vào dữ liệu nén (cn. được sử dụng cho mọi văn bản đầu vào). Mô hình này là đơn giản nhất nhưng nó không phụ thuộc đầu vào cho nên kém hiệu quả. Ví dụ với văn bản tiếng Anh, tần số của các ký tự tiếng Anh được tính toán từ kho lớn tài liệu tiếng Anh đã có và được sử dụng như mô hình. Mô hình bán thích nghi cũng là mô hình cố định, được xây dựng từ tệp văn bản gốc bằng cách đếm tổng số lần xuất hiện của từng ký tự và tính toán xác xuất cho mỗi chúng. Quá trình nén sau đó đọc lại lần lượt từng ký tự của tệp văn bản gốc lần nữa và sử dụng thông tin trong mô hình xác xuất để nén chúng. Dữ liệu mô hình sẽ được gộp vào dữ liệu nén cho nên làm tăng kích thước đầu ra. Hình 1 mô tả trình tự nén văn bản theo phương pháp thống kê. Phương pháp mã hóa số học hay mã hóa Huffman sử dụng kỹ thuật này.
Mô hình thích nghi thay đổi trong quá trình nén, được hình thành khi xử lý văn bản đầu vào. Vào một thời điểm nén, mô hình là hàm số của phần dữ liệu đã được nén trước đó. Không cần chuyển mô hình thích nghi đến bộ giải nén.
Phương pháp nén từ điển (phân tích cú pháp)[sửa]
Biểu diễn một cụm từ bằng từ mã duy nhất, trong khi phương pháp nén ký hiệu chỉ nén từng ký tự vào một thời điểm. Phương pháp nén từ điển quản lý một từ điển các cụm từ (xâu ký tự) được nhận biết bởi từ mã khác nhau. Phương pháp nén từ điển không cần duyệt trước tệp văn bản gốc để xây dựng mô hình. Từ điển của từ hay cụm từ được hình thành trong quá trình nén. Khi gặp một cụm từ, bộ nén kiểm tra xem câu đã được lưu trong từ điển chưa. Nếu chưa, bổ sung cụm từ vào từ điển và sinh ra một mã chỉ vị trí của câu trong từ điển. Nếu cụm từ đã được lưu trữ trong từ điển thì bộ nén chỉ đơn giản cho lại mã vị trí của cụm từ đó. Mã được xem như chỉ mục đến từ điển, là danh sách các cụm từ thường xuyên sử dụng. Phương pháp nén LZW là ví dụ của tiệm cận này.
Nguyên tắc chung của phương pháp nén thống kê là gán từ mã ngắn hơn cho các ký tự hoặc cụm từ có xác xuất cao hơn để tối ưu độ dài trung bình của mã từ.
Phương pháp biến đổi[sửa]
Thực hiện biến đổi văn bản đầu vào để có thể nén dễ dàng hơn bằng lược đồ mã hóa đơn giản. Phép biến đổi được sử dụng (vd. hoán vị các ký tự đầu vào) phải không mất mát thông tin, có thể biến đổi ngược vàtính toán phải hiệu quả. Ví dụ biến đổi BWT (Burrows-Wheeler) có thể được sử dụng, nó thực hiện biến đổi và biến đổi ngược trong thời gian tuyến tính với độ dài văn bản đầu vào. Đầu ra của biến đổi BWT là chuỗi trong đó các ký tự có cùng bối cảnh được nhóm lại với nhau, tạo ra cụm cáctừ gần giống nhau. Đặc trưng này tạo ra dư thừa ở văn bản đầu vào nhiều hơn so với các lược đồ nén đơn giản. Phương pháp này được kết hợp văn bản sau biến đổi với nén thống kê, nén loạt dài RLE (Run-length encoding), v.v. để thực hiện nén.
Có nhiều kỹ thuật được sử dụng để nén văn bản, hầu hết chúng được kết hợp với nhau để tạo thành một thuật toán nén hiệu quả hơn.
Lịch sử hình thành và phát triển[sửa]
Nén văn bản có lịch sử rất lâu đời cùng với sự ra đời của mã Morse vào năm 1838. Mã Morse được xem như phiên bản mã hóa văn bản đầu tiên, trong đó các ký tự tiếng Anh như “t”, “e” được gán cho mã ngắn hơn để truyền tin.
Năm 1949, Claude Shannon và Robert Fano đã phát minh ra thuật toán mã hóa Shannon-Fano sử dụng phương pháp thống kê.
Năm 1951, David Huffman khi còn là sinh viên của MIT đã đề xuất lược đồ mã hóa Huffman trên cơ sở lược đồ Shannon-Fano. Sự khác biệt là lược đồ Huffman xây dựng cây xác suất từ dưới lên còn Shannon-Fano xây dựng cây từ trên xuống.
Năm 1977, Abraham Lempel và Jacob Ziv công bố LZ77, thuật toán nén văn bản đầu tiên sử dụng từ điển. Sau đó, vào năm 1978 họ công bố phiên bản mới của LZ77 là thuật toán LZ78 với từ điển được sinh ra tự động. Các thuật toán nén này được cài đặt trong nhiều phần mềm nén như winzip, Snappy, LZMA, LZ4.
Năm 1979, IBM đề xuất phương pháp nén số học để sử dụng trên máy tính lớn của họ. Mã hóa số học được cho là kỹ thuật mã hóa entropy tối ưu nhất, nó có tỷ lệ nén tốt hơn mã hóa Huffman. Tuy nhiên, lược đồ của nó khá phức tạp so với các kỹ thuật mã hóa khác.
Những năm 1980 phương pháp mã hóa không sử dụng từ điển PPM (Prediction by partial matching) được đề xuất. PPM là kỹ thuật nén dữ liệu thống kê thích nghi dựa trên mô hình và dự đoán bối cảnh. Các mô hình PPM sử dụng một tập hợp các ký tự trước đó ở đầu vào để dự đoán ký tự tiếp theo để làm giảm entropy của dữ liệu đầu ra.
Năm 1984, Sperry cấp bằng sáng chế cho thuật toán LZW, một phái sinh của thuật toán LZ78. Bản quyền thuật toán LZW hết hạn vào năm 2003.
Năm 1993, Stac Electronics công bố thuật toán LZS, được Microsoft sử dụng để nén và lưu trữ hệ điều hànhMS-DOS 6.0 trên đĩa từ.
Năm 1994, kỹ thuật nén dựa trên biến đổi Burrows-Wheeler được đề xuất. Bản thân BWT không thực hiện nén, nó chỉ đơn giản biến đổi văn bản đầu vào để thực hiện nén hiệu quả bằng các phương pháp khác, ví dụ RLE.
Năm 2002, Matt Mahoney cải tiến PPM để có thuật toán nén PAQ. PAQ sử dụng kỹ thuật “trộn bối cảnh” để tổ hợp nhiều mô hình thống kê để có khả năng dự báo tốt hơn ký tự tiếp theo.
Tài liệu tham khảo[sửa]
- Guojun Lu, Multimedia Database Management Systems, Artech House, 1999.
- Jayant N., Signal Compression – Coding of Speech, Text, Image and Video, World Scientific Publishing, 1997.
- Ling Liu, Tamer Özsu (Editors), Encyclopedia of Database Systems, Second Edition, Springer Nature, 2018.
- Timothy C. Bell, John G. Cleary, Ian H. Witten, Text Compression, Prentice-Hall, 1990.
