Hồi đi học CNTT, anh em sợ nhất là môn gì? Để mình gợi ý nhé: Cấu Trúc Dữ Liệu & Giải Thuật. Ắt hẳn a/e nào không chịu khó hoặc có tư duy logic thì thấy môn này rất khó hiểu. Lớp mình cũng rớt lộp bộp, thà học lý thuyết có thể lướt qua để cuối kỳ đau 1 lần rồi thôi. Nó có luôn môn thực hành, thế là không phải đau 1 lần rồi vì thực hành mỗi tuần đều có task – không nộp lên Moodle thì ăn zero thôi.
Chắc hẳn a/e tưởng mình viết bài này là mình “ngon”. Không, mình cũng ăn hành ngập mồm. Nhưng may mắn thi qua môn được. Để mình kể cho a/e nghe 1 câu chuyện có thật, năm Nhất học kỳ 1 trường mình học 5 môn gì đấy, mình tạch 4/5 chỉ qua được môn Tin học cơ sở. Hồi đó đúng thảm, xin tiền ba má học lại mà nói láo là trường tăng học phí… Bài viết này hi vọng giúp anh em phần nào trong việc hiểu bản chất của 1 vấn đề và đừng bỏ cuộc nếu bạn gặp khó khăn.
Hôm nay mình sẽ chia sẻ 1 chút “bản chất” của việc nén dữ liệu. Nó liên quan mật thiết tới bộ môn “Cấu trúc dữ liệu & giải thuật” mà anh em đang học ak. Có thể a/e không thấy chương nào nói về việc nén dữ liệu nhưng khoan soi. A/e cứ đọc hết bài là hiểu.
Thuật toán nén có thể hiểu đơn giản là thuật toán mã hóa các chuỗi phổ biến bằng các từ khóa ngắn, còn các chuỗi ít phổ biến bằng các từ khóa dài hơn. Không có thuật toán mã hóa nào là hoàn hảo vì không thể mã hóa tất cả các chuỗi bằng từ khóa ngắn hơn được (bởi vì như vậy thì các từ khóa cũng có thể mã hóa bằng các từ khóa ngắn hơn,… => mâu thuẫn) và phụ thuộc vào phân bố các chuỗi.
Thuật toán càng lợi dụng được đặc điểm thống kê của dữ liệu gốc thì khả năng nén càng cao.
Đối với dữ liệu có cấu trúc thì tỷ lệ nén cao hơn với dữ liệu ngẫu nhiên(như ảnh, nhạc, video), dữ liệu dạng text thuần thì có tỷ lệ nén có thể lên đến 75 % (tiếng anh chứ tiếng Việt là 1 câu chuyện khác).
À quên, câu hỏi được đăng tải trên Quora. Và bạn Vũ Cường dịch, sau đó chia sẻ lại trên group Quora Việt Nam, mình thấy hay ho lắm nên muốn các bạn cùng đọc để tăng kiến thức.
Q: Làm cách nào ta có thể nén dữ liệu khi chúng chỉ là một lượng byte nào đó mà thôi?
A: Petr Titera, lập trình máy tính từ năm 1986
Hãy thử một vài ví dụ nhé.
Ví dụ 1:
Tôi cho bạn xâu này AAAAAAAAAAAAAAAABBBC, bạn nén nó kiểu gì đây? Bạn có thể viết gọn lại là 16A3BC (16 lần chữ A, 3 lần chữ B và C). Kiểu nén này có tên gọi là Mã Hóa Theo Độ Dài Một Loạt (Run Length Encoding – RLE) và dù không thể áp dụng cho mọi loại dữ liệu song có có thể trở nên cực kỳ hữu dụng trong trường hợp số giá trị là hữu hạn.
Ví dụ 2:
Giờ xâu lại là ABCDEABCDFABCDG. Trong trường hợp này, RLE sẽ không giúp gì được cho bạn đâu. Song bạn có thể làm gì đó với xâu này đấy. Hãy viết lại nó theo cách này: ABCDE(5,4)F(5,4)G. Các dấu ngoặc được ký hiệu ở đây có nghĩa là quay ngược lại 5 ký tự ở phần output và sao chép 4 ký tự tại đó. Đó là cách mà những phương pháp mã hóa giống kiểu LZ77 hoạt động.
Ví dụ 3:
Giờ xâu trở thành ABCDEFGH, có vẻ chẳng có gì lặp lại nữa rồi. Bạn có thể rút ngắn nó được nữa không? Có chứ, nếu bạn để ý rằng chỉ có 8 ký tự xuất hiện mà thôi và với mỗi ký tự ở đầu vào, bạn cần một byte. Vậy, hãy thử cách này mà xem, bạn thay chữ A bằng số 0, B bằng số 1, vv. Output sẽ là 01234567 nhưng mỗi con số sẽ chỉ tốn có 3 bit mà thôi. Đó là cách hoạt động của những thuật toán như phép mã hóa Huffman.
Trên đây chỉ là ba ví dụ cơ bản và tôi đã lược bỏ rất nhiều chi tiết, bạn sẽ phải tiếp tục mã hóa output, bạn phải xem xét khả năng input chứa tất cả các ký tự có thể có chứ không chỉ trong những tập giá trị hữu hạn, vv. Các bạn có thể thấy, bài toán lớn là nén dữ liệu sử dụng rất nhiều các thuật toán, tương ứng với tệp dữ liệu vào mà áp dụng thuật toán để cho kết quả tối ưu nhất.
Khuyến cáo các bạn nên bỏ ra 2 phút để coi video có thuyết minh tiếng Việt này:
Phần lớn những thuật toán nén hiện đại sử dụng nhiều cách thức được mô tả trên đây cùng với những phương pháp tiên tiến khác nữa.
Thuật toán siêu nén của Jan Sloot
Nhờ trí óc siêu phàm, thiên tài công nghệ thông tin Romke Jan Bernhard Sloot người Hà Lan đã từng sáng tạo ra thuật toán thu nhỏ dung lượng thông tin vô cùng ảo diệu: từ 10GB dữ liệu được nén xuống chỉ còn 8KB.
Năm 1999, ông đã bảo vệ công trình nghiên cứu của mình trước những “ông trùm” giới công nghệ và thuyết phục họ mua nó. Romke Jan Bernhard Sloot đã cho trình chiếu 16 bộ phim được chứa đựng trong một con chip 64KB.
Ai nấy cũng không khỏi ngạc nhiên khi có mặt trong sự kiện này và họ cho rằng chắc chắn ông sẽ trở thành tỷ phú từ việc nhượng lại sản phẩm của ý tưởng. Thế nhưng chỉ hai ngày trước khi chuyển giao thuật toán lại cho đối tác, Sloot đột ngột qua đời một cách bí ẩn.
Dư luận đồn đoán rằng Sloot đã bị đau tim, nhưng cũng có thể là bị ám hại để cướp ý tưởng sáng tạo. Chiếc đĩa chứa chìa khóa bí mật về thuật toán nén dữ liệu của ông đã mãi mãi biến mất…
Đọc bài viết các bạn có hiểu phần nào ý nghĩa không? Mình dốt môn Cấu trúc dữ liệu nhưng đọc thấy khá là dễ hiểu đấy. Hi vọng bài viết này cung cấp lượng kiến thức cho a/e IT, nhất là những bạn còn đang mơ hồ về những “giải thuật” học ra để làm gì. Và đây, bài viết này chính là 1 ví dụ điển hình =))
Nguồn: Quora
