Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 15 kết quả

Đề tài: Làm sao để mã hóa 3 kí tự chỉ với 2byte

  1. #1
    Ngày gia nhập
    10 2009
    Nơi ở
    ThăngLong.delay(1000);
    Bài viết
    312

    Mặc định Làm sao để mã hóa 3 kí tự chỉ với 2byte

    Mình cần cấp phát hàng trăm triệu phần tử, nên tiết kiệm dù chỉ 1 byte cũng quý.

    Mã hóa 3 kí tự - tức là 3 số tự nhiên <128, nhưng chỉ được phép dùng 2 byte (1 số nguyên 2byte)

    Tính toán phức tạp cũng được, ai có giải pháp gì giúp mình nhé

    EDIT: Mình bổ xung thêm 1 điều kiện là số sau lớn hơn số trước.
    Đã được chỉnh sửa lần cuối bởi vietduc : 17-09-2011 lúc 03:36 PM.

  2. #2
    Ngày gia nhập
    07 2010
    Nơi ở
    chỗ kín
    Bài viết
    446

    phải có thêm một điều kiện ràng buộc nữa để giảm số lượng byte xuống mới dc,

    trong điều kiện thiếu thốn, buộc phải giảm độ chính xác dữ liệu xuống ( xuống một mức nào đó có thể chấp nhận dc)

    với bài của bạn mình nghĩ nên làm thế này:
    chỉ dùng 6 bit để biểu diễn các số chẵn trong dải 0;127
    vậy ta cần 6*3 = 18 bit (hơn 2 byte 1 tý) để biểu diễn 3 số chẵn

    bạn muốn biểu diễn 3 số 68 25 44
    thì coi như bạn biểu diễn 3 số 68 24 44

    tức là 68 25 44 và 68 24 44 có chung một mã.

    bạn có thể còn phải dựa vào xác suất có số lẻ, chẵn để tăng độ chính xác lên.

    hi vọng bạn hiểu.

  3. #3
    Ngày gia nhập
    10 2009
    Nơi ở
    ThăngLong.delay(1000);
    Bài viết
    312

    Cách đó không đáp ứng được rồi, nếu tách từng số ra để biểu diễn thì chắc chắn không được.

  4. #4
    Ngày gia nhập
    07 2010
    Nơi ở
    chỗ kín
    Bài viết
    446

    mình có tách 3 số ra đâu

    biểu diễn 3 5 9 :

    biểu diễn thông thường ( không nén) là chuỗi 3 byte :
    0000 0011-0000 0101-0000 1001

    nhưng khi mã hóa sẽ được dãy này
    0000 0100 0010 0001 00
    (tức là 000001-000010 000100 = 1 2 4), chỉ cần nhân đôi chuỗi mã hóa, thêm 2 bit 0 và đầu tương ứng là dc chuỗi ban đầu ( đương nhiên độ chính xác là 50% mỗi số và độ chính xác cho cả 3 số là 12,5% nghĩa là tỉ lệ 8/1 đấy)

    hiểu ko ?

  5. #5
    Ngày gia nhập
    10 2009
    Nơi ở
    ThăngLong.delay(1000);
    Bài viết
    312

    Tức là dùng n bit để biểu diễn số 3 rồi n bít khác để biểu diễn số 5 và n bít khác để biểu diễn số 9 còn gì, tách rời 3 số đó thôi.

  6. #6
    Ngày gia nhập
    10 2009
    Nơi ở
    ThăngLong.delay(1000);
    Bài viết
    312

    Mặc định Làm sao để mã hóa 3 kí tự chỉ với 2byte

    Mình bổ xung thêm 1 điều kiện là số sau lớn hơn số trước nhé, thanks

  7. #7
    Ngày gia nhập
    07 2010
    Nơi ở
    chỗ kín
    Bài viết
    446

    thôi thì cứ nói thẳng bạn định ứng dụng nó vào đâu đi, lưu trữ kết quả của một quá trình tìm kiếm hay là thế nào ?

  8. #8
    Ngày gia nhập
    10 2009
    Nơi ở
    ThăngLong.delay(1000);
    Bài viết
    312

    Cho trước tầm 2000 ma trận 4x7 chứa số 0 hoặc số 1. (ma trận ở vị trí 0 chứa toàn số 0)
    mỗi khi nhận được 1 ma trận X cũng cỡ 4x7 thì in ra 3 số a, b, c sao cho:
    3 ma trận ban đầu ở vị trí a, b, c xor với nhau thì tạo ra ma trận X.
    Đó đề bài gần giống như thế, chứ đề bài thật thì dài vài trang và ảo lắm.

  9. #9
    Ngày gia nhập
    07 2011
    Bài viết
    160

    Trích dẫn Nguyên bản được gửi bởi vietduc Xem bài viết
    Cho trước tầm 2000 ma trận 4x7 chứa số 0 hoặc số 1. (ma trận ở vị trí 0 chứa toàn số 0)
    mỗi khi nhận được 1 ma trận X cũng cỡ 4x7 thì in ra 3 số a, b, c sao cho:
    3 ma trận ban đầu ở vị trí a, b, c xor với nhau thì tạo ra ma trận X.
    Đó đề bài gần giống như thế, chứ đề bài thật thì dài vài trang và ảo lắm.
    Mình không hiểu sao có ~2000 ma trận 4x7 mà a, b, c lại < 128?

    Nếu bạn lười đọc về khái niệm entropi thông tin thì mình trình bày bằng cách khác vậy:

    Nếu 0 <= a, b, c < 128 thì mỗi số cần 7 bit thông tin để biểu diễn và tổng cộng cần 21 bit mới đủ! 2 bytes = 16 bit => không đủ.
    Nếu có thêm điều kiện a < b < c: Số bộ 3 thỏa mãn điều kiện 0 <= a < b < c < 128 là C(128, 3) = 128!/((128 - 3)!3!) = 128*127*126/(3*2) = 341376 trường hợp
    Số này nằm giữa 2^18 và 2^19 nên cần tối thiểu 19 bit để biểu diễn. 16 bit vẫn không đủ!

    P.S: Hàng trăm triệu hay hàng chục tỷ phần tử thì việc bạn tiết kiệm được vẫn không đáng là bao. Bạn có thể dùng cache vào file trên đĩa cứng, đĩa cứng hiện giờ vài trăm GB cơ mà! Hệ điều hành cũng tự cache virtual memory vào đĩa cứng khi vượt quá dung lượng RAM, và bạn chẳng phải làm gì cả! Khả năng là chương trình sẽ vẫn chạy nhanh hơn so với bạn phải bóc tách từng bit (+ thuật toán giải nén nếu có) để truy cập được số.
    Đã được chỉnh sửa lần cuối bởi fbchicken : 17-09-2011 lúc 08:51 PM.

  10. #10
    Ngày gia nhập
    07 2010
    Nơi ở
    chỗ kín
    Bài viết
    446

    đọc đề mông lung quá, chưa hình dung ra dc nó thế nào cả. Bạn suy luận kiểu gì mà ra dc câu hỏi ở đầu topic vậy.

    tính ra cỡ 4000 ma trận như vậy chỉ lưu trữ trong vài chục KB là cùng, việc gì phải ép làm gì cho đau đầu.

Các đề tài tương tự

  1. Dịch vụ gửi hàng hóa đi Australia, gửi hàng hóa đi France, gửi hàng hóa đi Germany, gửi hàng hóa đi Janpan giá rẻ.
    Gửi bởi sales5ttico trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 1
    Bài viết cuối: 30-07-2014, 02:51 PM
  2. Hội thảo công nghệ: Ảo hóa và các PMNM ảo hóa ứng dụng trong học
    Gửi bởi maryl trang trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 02-10-2012, 10:30 PM
  3. Công nghệ nhận dạng chữ viết, số hóa thông tin, giải pháp số hóa cho các doanh nghiệp
    Gửi bởi thepbac trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 23-04-2010, 09:51 AM
  4. Mã hóa trên C++ | Giúp mình kiểu mã hóa này?
    Gửi bởi attain11 trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 1
    Bài viết cuối: 26-05-2009, 10:16 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn