IEEV

Chúng tôi không quan tâm thứ bạn có, chúng tôi cần cái bạn muốn chia sẻ.

Albert Einstein

Information is not knowledge

H. Jackson Brown Jr.

Don’t forget that a person’s greatest emotional need is to feel appreciated.

H. Jackson Brown Jr.

Life doesn't require that we be the best, only that we try our best.

Susanne K. Langer

If we would have new knowledge, we must get a whole world of new questions.

Thứ Tư, ngày 08 tháng 7 năm 2009

Mã tiền tố (prefix-free binary code)

Để mã hóa các kí hiệu (kí tự, chữ số, ...) ta thay chúng bằng các xâu nhị phân, được gọi là từ mã của kí hiệu đó (code word). Chẳng hạn bộ mã ASCII, mã hóa cho 256 kí hiệu là biểu diễn nhị phân của các số từ 0 đến 255, mỗi từ mã gồm 8 bít. Trong ASCII từ mã của kí tự "a" là 1100001, của kí tự "A" là 1000001. Trong cách mã hóa này các từ mã của tất cả 256 kí hiệu có độ dài bằng nhau (mỗi từ mã 8 bít). Nó được gọi là mã hóa với độ dài không đổi.
Khi mã hóa một tài liệu có thể không sử dụng đến tất cả 256 kí hiệu. Mặt khác trong tài liệu, các kí hiệu xuất hiện với tần xuất không giống nhau, chữ cái "a" có thể xuất hiện 1000000 lần còn chữ cái "A" có thể chỉ xuất hiện 2, 3 lần. Như vậy ta có thể không cần dùng đủ 8 bít để mã hóa cho một ký hiệu, hơn nữa độ dài (số bít) dành cho mỗi kí hiệu có thể khác nhau, kí hiệu nào xuất hiện nhiều lần thì nên dùng số bít ít, ký hiệu nào xuất hiện ít thì có thể mã hóa bằng từ mã dài hơn. Trong trường hợp đó ta có việc mã hóa được tiến hành với độ dài thay đổi. Tuy nhiên, nếu mã hóa với độ dài thay đổi, khi giải mã ta làm thế nào phân biệt được xâu bít nào là mã hóa của ký hiệu nào? Một trong các giải pháp là dùng các kí hiệu phân cách, ví dụ dấu phẩy (",") hoặc một kí hiệu quy ước nào đó để tách từ mã của các kí tự đứng cạnh nhau. Nhưng như thế số các dấu phẩy sẽ chiếm một không gian đáng kể trong bản mã và trong trường hợp kí hiệu cần mã hóa là chính dấu (",") thì thật trớ trêu. Một cách giải quyết khác thường dược sử dụng đó là sử dụng mã tiền tố.

::- Mã tiền tố là bộ các từ mã của một tập hợp các kí hiệu sao cho từ mã của mỗi ký hiệu không là tiền tố (phần đầu) của từ mã một ký hiệu khác trong bộ mã ấy. Đương nhiên mã hóa với độ dài không đổi là mã tiền tố.
Ví dụ: Giả sử mã hóa chuỗi "ARRAY", tập các ký hiệu cần mã hóa gồm 3 chữ cái "A","R","Y".
  • Nếu mã hóa bằng các từ mã có độ dài bằng nhau ta dùng ít nhất 2 bit cho một chữ cái chẳng hạn "A"=00, "R"=01, "Y"=10. Khi đó mã hóa của cả từ là 0001010010. Để giải mã ta đọc hai bit một và đối chiếu với bảng mã.
  • Nếu mã hóa "A"=0, "R"=01, "Y"=11 thì bộ từ mã này không là mã tiền tố ví từ mã của "A" là tiền tố của từ mã của "R". Để mã hóa cả chuỗi ARRAY phải đặt dấu ngăn cách vào giữa các từ mã 0,01,01,0,11
  • Nếu mã hóa "A"=0, "R"=10, "Y"=11 thì bộ mã này là mã tiền tố. Với bộ mã tiền tố này khi mã hóa xâu "ARRAY" ta có 01010011.
::- Làm thế nào để tạo ra bộ mã tiền tố cho các kí hiệu cần mã hóa?
Một trong những giải pháp là xây dựng bộ mã tiền tố dùng cây nhị phân
  • Nếu có một cây nhị phân n lá ta có thể tạo một bộ mã tiền tố cho n ký hiệu bằng cách đặt mỗi ký hiệu vào một lá. Từ mã của mỗi kí hiệu được được tạo ra khi đi từ gốc tới lá chứa ký hiệu đó, nếu đi qua cạnh trái thì ta thêm số 0, đi qua cạnh phải thì thêm số 1.

  • Ví dụ: Cây 3 lá sau đây biểu diễn bộ mã của A,R,Y trong ví dụ trên


  • Từ mã của "A" là 0, của "R" là 10, của "Y" là 11.
::- Mã tiền tố tối ưu

Từ ví dụ trên thấy mã hóa của xâu "ARRAY" bằng mã độ dài cố định mất 10 bít, bằng mã tiền tố đã đưa ra mất 8 bít, tiết kiệm được 20%. Bài toán đặt ra cho qua trình mã hóa dùng bộ mã tiền tố là làm sao tối ưu nhất số lượng bít sử dụng.

Binh Nguyen - Bioz (Wiki)

Ebook hay dành cho nghiên cứu

Khi mới tiếp cận một lĩnh vực nghiên cứu, điều quan trọng đầu tiên là phải xây dựng được một tầm nhìn bao quát về mảng công nghệ đó, tiếp đến là đi vào đọc các tài liệu, sách nhằm xây dựng nền tảng cần thiết. cuối là đọc paper nhằm tiếp cận những phát kiến mới và sáng tạo ra cái của riêng mình. Các giai đoạn có thể tiến hành song song, tuy nhiên dù thế nào thì sách và các bài nghiên cứu luôn đóng một vai trò hết sức quan trọng. Đọc đúng sách, đúng trình tự sẽ giúp bạn giãm thiểu thời gian và phát huy tối đa năng lực của bản thân. Chính vì lẽ đó bài viết này và một loạt các bài viết trong mục giới thiệu sách sẽ gởi đến mọi người những gợi ý về sách với tiêu chí: Hay, Dễ hiểu, Mới, tương ứng với từng lĩnh vực.

Binh Nguyen - bioz