Trang 2 trên tổng số 8 Đầu tiênĐầu tiên 1234... Cuối cùngCuối cùng
Từ 11 tới 20 trên tổng số 71 kết quả

Đề tài: một phương pháp mã hóa tiếng Việt

  1. #11
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    Mặc định một phương pháp mã hóa tiếng Việt

    Tôi cứ nghĩ là mình đã đọc hết những Tutorial của congdongcviet, nhưng không ngờ lại bỏ sót bài viết của Ada vào năm 2010. (-_-"). Đang xử lý những vấn đề liên quan đến tiếng Việt nên mới thấy được bài viết này có giá trị như thế nào. Cảm ơn Ada nhiều lắm. Tôi sẽ cố gắng nuốt đống lý thuyết của bạn, đọc sơ qua, thì có chút choáng ngợp. (-_-").
    P/s: Đẩy bài này lên top để những người khác có thể xem, nó chìm xuồng lâu quá rồi.
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

  2. #12
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    745

    Revision 2017. Định dạng mã xâu mà mình đề xuất trên chỉ gần tương thích, nhưng chưa tương thích với xâu ASCII: một xâu ASCII có độ dài là số chẵn được mã hóa thành chính nó, nhưng một xâu ASCII có độ dài là số lẻ sẽ được mã hóa thành chính nó nối thêm 1 byte không ASCII. Định dạng ấy hoàn toàn không tương thích với bất cứ định dạng Unicode thông dụng nào.

    Sau đây mình đề xuất một định dạng mới, tương thích với một định dạng xâu Unicode thông dụng và đang dần dần trở thành thống trị trong những năm gần đây. Đó là định dạng UTF-8.

    Ở đây khái niệm tương thích với UTF-8 được hiểu một cách tự nhiên: khi mã hóa một xâu UTF-8, mọi xâu [con] không chứa tiếng Việt, hoặc chứa tiếng Việt nhưng vì lẽ gì đó ta không muốn mã hóa, sẽ được mã hóa thành chính nó. Nói cách khác, các xâu mã bao hàm cả các xâu UTF-8. Do các xâu UTF-8 bao hàm cả các xâu ASCII, tính tương thích này bao hàm cả tương thích với ASCII.

    Ở đây, ký tự UTF-8 có 1 byte sẽ chỉ được gọi đơn giản là "ký tự ASCII", và ký tự UTF-8 có 2 byte trở lên sẽ được gọi là "ký tự UTF-8+".

    Tương tự như định dạng sơ khai đã giới thiệu ở đầu bài #5:
    Code:
    v1 v2 v3 v4 v5 v6 v7 v8     t1 t2 t3 p1 p2 p3 p4 p5
    ở đây, mỗi chữ Việt được mã hóa thành 2 byte, dạng
    Code:
    u1 u2 v3 v4 v5 v6 v7 v8     s1 s2 t3 p1 p2 p3 p4 p5
    thỏa 2 điều kiện:

    a) u1 = 1, bởi vì u1 s1 = 00 ứng với hai ký tự ASCII, và u1 s1 = 01 ứng với một ký tự ASCII theo sau là byte đầu tiên của một ký tự đa byte (UTF-8+ hoặc chữ Việt).

    b) u1 u2 s1 s2 != 1110, bởi vì u1 u2 s1 s2 = 1110 ứng với 2 byte đầu của một ký tự UTF-8+.

    Như thế, không gian mã có 16 ô, thì 9 ô đã được chiếm dụng. Chỉ còn trống đúng 7 ô, vừa đủ dùng cho chữ Việt.

    Hình 5a. Bản đồ quy hoạch không gian mã.
    Code:
          +-----------------------------------+
          |               s1 s2               |
          +--------+--------+--------+--------+
          |   00   |   01   |   10   |   11   |
    +--+--+--------+--------+--------+--------+
    |  |  |        |        |        |        |
    |  |00|                 |                 |
    |  |  |       hai       |   ký tự ASCII   |
    |  +--+-     ký tự     -+-  và byte đầu  -+
    |  |  |      ASCII      |  ký tự đa byte  |
    |  |01|                 |                 |
    |u1|  |        |        |        |        |
    |  +--+--------+--------+--------+--------+
    |u2|  |  chữ   |  chữ   |  chữ   |  chữ   |
    |  |10|  Việt     Việt     Việt     Việt  |
    |  |  |  0001  |  0000  |  1010  |  0010  |
    |  +--+--    --+--    --+--------+--    --+
    |  |  |  chữ   |  chữ   | 2 byte |  chữ   |
    |  |11|  Việt     Việt  |đầu k.tự|  Việt  |
    |  |  |  0101  |  0100  | UTF-8+ |  0110  |
    +--+--+--------+--------+--------+--------+
    Trong hình, mỗi ô chữ Việt được điền một chuỗi 4 bit, đó là giá trị v1 v2 t1 t2 của định dạng sơ khai. Vậy, công thức biến đổi từ định dạng sơ khai sang định dạng mới (để mã hóa) và công thức biến đổi ngược (để giải mã) lần lượt là
    Code:
    u1 u2 s1 s2 = v1 v2 t1 t2 == 1010 ? v1 v2 t1 t2 : ~v1 v2 t1 ~t2
    v1 v2 t1 t2 = u1 u2 s1 s2 == 1010 ? u1 u2 s1 s2 : ~u1 u2 s1 ~s2
    Đánh giá. Định dạng này không có khả năng tự đồng bộ như UTF-8: xâu mã phải được giải mã từ đầu về cuối; nếu "nhảy dù" vào giữa xâu, ta sẽ "lạc dấu" ký tự không biết đâu mà lần. Một phương án khác, tương thích với mọi phương thức mã hóa Unicode và bảo toàn khả năng tự đồng bộ, là đưa mỗi chữ Việt vào Unicode như một ký tự ở một dải private use area đủ lớn (cho phép mã hóa khoảng 65536 ký tự). Tuy nhiên, cách ấy làm hiệu quả giảm đi một nửa vì trong UTF-8, mỗi chữ Việt như thế sẽ có 4 byte, so với 2 byte trong định dạng của mình. Định dạng của mình có thể xem là UTF-8 mở rộng bằng cách hy sinh khả năng tự đồng bộ, đổi lấy hiệu quả cao. Một chữ Việt UTF-8 trước khi mã hóa dài khoảng 4 - 8 byte, nên hiệu quả đối với nội dung tiếng Việt là khoảng 2 đến 4 lần. Định dạng này hiệu quả như UTF-8 đối với nội dung khác.
    Đã được chỉnh sửa lần cuối bởi Ada : 23-01-2018 lúc 09:35 AM. Lý do: Đánh số các Bảng / Hình
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  3. #13
    Ngày gia nhập
    08 2017
    Bài viết
    4,085

    Bạn có giải pháp về những vấn đề liên quan, chẩn hóa, chuyển đổi (to upper / lower) tìm kiếm & sắp xếp cho pp mã hóa này.

    Trở ngại, trở kháng lớn nhất là thói quen. Thật khó hình dung khi chúng ta bỏ hệ thập phân (ISO) :
    - dùng hệ Hex (nó có những ưu điểm vượt trội trong KHMT)
    - dùng hệ Anh-Mỹ (tiền tệ, khối lượng, đo lường, ... với các ước số khác 10)

    Những đề xuất, cải cách chữ Quốc ngữ thất bại là minh chứng.

  4. #14
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    745

    Trích dẫn Nguyên bản được gửi bởi Monre Xem bài viết
    Bạn có giải pháp về những vấn đề liên quan, chẩn hóa, chuyển đổi (to upper / lower) tìm kiếm & sắp xếp cho pp mã hóa này.
    Mình không có giải pháp nào. Nhưng mình biết khoảng 10 năm trước, 2 đồng nghiệp dùng phương pháp của mình đã tự phát triển thuật toán mã hóa/giải mã và các thuật toán liên quan đủ dùng cho nhu cầu của họ. Một người dùng để mã hóa họ và tên người, người kia mã hóa các địa danh. Trong khi giao diện người dùng chỉ là truy vấn điểm (dùng phép so sánh ==, ví dụ, tìm tất cả những người có họ bắt đầu bằng chữ Nguyễn), thì ở API bên trong, việc lập index cho trường hợp tên người và inverse index cho trường hợp địa danh (ví dụ, tìm tất cả các báo cáo liên quan đến Hà Tiên, Hội AnPhong Nha) đòi hỏi cài đặt một thứ gần như là truy vấn khoảng (cần phép so sánh <).

    Theo mình biết, cả hai bạn đó đều gặp rắc rối khi so sánh hai chữ với hai phụ âm đầu đồng âm đồng mã. Ví dụ, so sánh ga, ghê, ghi. Giải pháp đề xuất của mình là không cần để ý đến sự khác biệt giữa hai phụ âm.

    Để ý rằng đối với âm vần đồng âm đồng mã thì vấn đề này không xảy ra. Còn một vấn đề gần nhưng khác, so sánh giữa hoaihuai hay giữa qoaiquai, thì bản chất của nó không phải là vấn đề hỗ trợ (so sánh) nữa, mà là vấn đề trung tâm: có cần mã hóa được cả hai phương án này hay không và, nếu có, thì làm cách nào. Mỗi đồng nghiệp đã giải quyết theo cách riêng của mình, bằng một thuật toán riêng. (Mình đã đề cập đến hiện tượng bất định này ở phần đầu của bài viết.) Xa hơn một chút là vấn đề so sánh giữa ghì, và lại một lần nữa, nó chỉ giải được khi đã có thuật toán mã hóa cụ thể.

    Cả hai trường hợp của đồng nghiệp mà mình nêu trên đều tương đối đơn giản vì nhu cầu chỉ giới hạn ở việc so sánh hai xâu thuần Việt (đã mã hóa). Nếu một xâu đã mã hóa cần so sánh với một xâu không mã hóa, hẳn là sẽ phức tạp hơn.

    Trích dẫn Nguyên bản được gửi bởi Monre Xem bài viết
    Trở ngại, trở kháng lớn nhất là thói quen. Thật khó hình dung khi chúng ta bỏ hệ thập phân (ISO) :
    - dùng hệ Hex (nó có những ưu điểm vượt trội trong KHMT)
    - dùng hệ Anh-Mỹ (tiền tệ, khối lượng, đo lường, ... với các ước số khác 10)

    Những đề xuất, cải cách chữ Quốc ngữ thất bại là minh chứng.
    Mình không có những ước vọng to tát như là dùng phương pháp này như một định dạng chuẩn để trao đổi thông tin giữa 2 tổ chức độc lập. Còn đối với việc dùng nó trong 1 cơ sở dữ liệu hay 1 ứng dụng đơn lẻ thì thói quen không phải là trở ngại. Những yêu cầu cao về băng thông, độ trễ, giới hạn phần cứng, khối lượng dữ liệu,... sẽ tạo áp lực buộc lập trình viên phải tìm đến mọi giải pháp, quen và cả không quen.

    Và thậm chí, như trong trường hợp mã hóa tiếng Việt này, giải pháp ấy là chưa có sẵn.
    Đã được chỉnh sửa lần cuối bởi Ada : 25-11-2017 lúc 12:10 AM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  5. #15
    Ngày gia nhập
    08 2017
    Bài viết
    4,085

    Ở trên tôi viết sai : chẩn hóa (chuẩn hóa).

    Với một người nghiên cứu, hoặc có nghề nghiệp đặc thù thì cái thói quen có thể hình thành nhờ luyện tập. Ví dụ điện tín viên, hoa tiêu.
    Với văn bản, lượng ký tự (text) thuần túy chiếm dung lượng không đáng kể, ở kỹ thuật truyền tin hiện nay, so với các thông tin khác (định dạng, Rtf, doc, pdf, ...) chứa tin.

    Cùng với kỹ thuật truyền thông tin, người ta có thể nén gói tin đó.

    Chỉ là sự trùng hợp, bạn xem hình chụp này:


    ở bài báo:
    https://thanhnien.vn/giao-duc/khi-tieng-viet-duoc-viet-thanh-tieq-viet-903068.html

    Tôi không có ý gán ghép tin trên báo với ý tưởng của bạn.

  6. #16
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    745

    Mặc định một phương pháp mã hóa tiếng Việt

    Mình vừa cập nhật định dạng 2017 (bài #12), chỉnh công thức biến đổi định dạng sơ khai thành định dạng hoàn thiện.

    Để không phải sửa chữa lại cả loạt bài này, vốn đã đăng từ nhiều năm trước, mình lưu ý thêm rằng trong loạt bài này, mình dùng từ "dạng sơ khai" như một định dạng trung gian (và chính tắc) hơn là một ý tưởng định dạng mơ hồ. Có thể ví nó như điểm mã (code point) trong Unicode, hoặc byte code/bit code trong các bộ biên dịch.

    @Monre: đề xuất cải biên cín' tả kuốk qữ mà bạn giới thiệu trên, về mặt kỹ thuật, có vài điểm đáng bàn. Nhưng mình sẽ không thảo luận trong topic này, vì không liên quan.
    Đã được chỉnh sửa lần cuối bởi Ada : 28-11-2017 lúc 09:38 PM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  7. #17
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    745

    Revision 2018. Bài này chỉnh lý và cải tiến phiên bản 2017 (xem #12).

    Định dạng sơ khai và hoàn thiện, về hình thức vẫn như trước, nhưng về ngữ nghĩa có thay đổi, nên để tránh nhầm lẫn mình gọi định dạng sơ khai mới là dạng chuẩn, còn định dạng hoàn thiện mới là dạng .

    Nhắc lại #12, dạng chuẩn là
    Code:
    v1 v2 v3 v4 v5 v6 v7 v8    t1 t2 t3 p1 p2 p3 p4 p5
    trong đó v1 - v8 là mã âm vần, t1 - t3 là mã thanh, p1 - p5 là mã phụ âm đầu. Và dạng mã là
    Code:
    u1 u2 v3 v4 v5 v6 v7 v8    s1 s2 t3 p1 p2 p3 p4 p5
    Điểm mới ở đây là công thức biến đổi giữa hai dạng:
    Code:
    u1 u2 s1 s2 = ~v1 ~v2 t1 ~t2
    Công thức mới đơn giản hơn hẳn trước. Sở dĩ thế là vì v1 = 0. Nói cách khác, dạng chuẩn thực chất chỉ có 15 bit. Làm sao được thế?

    Một cách vắn tắt, trong dạng chuẩn, 72 âm vần khép và 72 âm vần nửa khép sáp nhập với nhau thành 72 âm vần lưỡng tính, và 2 thanh nhập được tách ra khỏi 2 thanh khứ. Nhắc lại #3, sắcnặng được gọi chung là nhập trong các vần khép, gọi chung là khứ trong 3 loại vần còn lại. Nay, sắc được chia thành "sắng" và sắc, còn nặng thành nặng và "nặc". Vậy, dạng chuẩn chỉ còn 120 âm vần, nhưng lại có những 8 thanh. Bản đồ quy hoạch không gian (dạng chuẩn) vẫn có 7 ô, nhưng có dạng "đẹp" hơn, nghĩa là dễ mã hóa hơn.

    Dù 1 mã âm vần có thể xác định 2 âm vần (1 khép, 1 nửa khép), tính khép/nửa khép vẫn được xác định hoàn toàn bằng mã thanh. Nên mã vần (và do thế, cả mã chữ) là không nhập nhằng. Ví dụ, bắnbắt tuy cùng mã âm vần nhưng vẫn khác nhau ở mã thanh.


    Bảng 2b. Tám thanh
    Code:
    0     1     2     3     4     5     6     7     
    ------------------------------------------------
    ngang huyền hỏi   ngã   sắng  nặng  sắc   nặc   
    bằng  bằng  gãy   gãy   khứ   khứ   nhập  nhập
    phù   trầm  phù   trầm  phù   trầm  phù   trầm
    Bảng 3b. Tập hợp 120 âm vần
    Code:
        _0   _1   _2   _3   _4   _5   _6   _7   _8   _9   _A   _B   _C   _D   _E   _F
    ===================================================================================
    0_  a    oa   ơ    uơ   ưa   e    oe   ê    uê   ia   uya  o    ô    ua   u    ư
             ua                       ue
    
    1_  i    y    uy   ai   oai  ay   oay  ơi   uơi  ươi  ây   uây  oi   ôi   uôi  ui
                            uai       uay
    
    2_  ưi   ao   oao  au   oau  ươu  âu   uâu  eo   oeo  êu   uêu  iêu  ưu   iu   uyu
                  uao       uau                      ueo            yêu
    
    3_                                          uơm  uâm  oem  uym  uơng oeng uêng uyêng
                                                uơp  uâp  oep  uyp  uơc  oec  uêc  uyêc
    
    4_  an   oan  ăn   oăn  ơn   uơn  ươn  ân   uân  en   oen  ên   uên  iên  uyên on
        at   oat  ăt   oăt  ơt   uơt  ươt  ât   uât  et   oet  êt   uêt  iêt  uyêt ot
    
    5_  ôn   uôn  un   ưn   in   uyn  am   oam  ăm   oăm  ơm   ươm  âm   em   êm   uêm
        ôt   uôt  ut   ưt   it   uyt  ap   oap  ăp   oăp  ơp   ươp  âp   ep   êp   uêp
    
    6_  iêm  om   ôm   uôm  um   ưm   im   ang  oang ăng  oăng ơng  ương âng  uâng eng
        iêp  op   ôp   uôp  up   ưp   ip   ac   oac  ăc   oăc  ơc   ươc  âc   uâc  ec
    
    7_  iêng êng  ong  oong ông  uông ôông ung  ưng  ing  anh  oanh ênh  uênh inh  uynh
        iêc  êc   oc   ooc  ôc   uôc  ôôc  uc   ưc   ic   ach  oach êch  uêch ich  uych

    Hình 4b. Bản đồ quy hoạch không gian chuẩn (nửa trên, phóng to)
    Code:
          +-----------------------------------+
          |               t1 t2               |
          +--------+--------+--------+--------+
          |   00   |   01   |   10   |   11   |
    +--+--+--------+--------+--------+--------+
    |  |  |        |        |        |        |
    |  |  |    48 âm vần [nửa] mở    |        |   
    |  |00|       với 6 thanh        |        |
    |  |  |  bằng  |  gãy   |  khứ   |        |
    |  |  +--------+--------+--------+        |
    |v1|  +--------+--------+--------+--------+
    |  +--+        +        +        +        +
    |v2|  |        |        |        |        |
    |  |  |                                   |
    |  |01|       72 âm vần [nửa] khép        |
    |  |  |           với 8 thanh             |
    |  |  |                                   |
    |  |  |  bằng  |  gãy   |  khứ   |  nhập  |
    +--+--+--------+--------+--------+--------+
    Hình 5b. Bản đồ quy hoạch không gian mã
    Code:
          +-----------------------------------+
          |               s1 s2               |
          +--------+--------+--------+--------+
          |   00   |   01   |   10   |   11   |
    +--+--+--------+--------+--------+--------+
    |  |  |        |        |        |        |
    |  |00|                 |                 |
    |  |  |       hai       |   ký tự ASCII   |
    |  +--+-     ký tự     -+-  và byte đầu  -+
    |  |  |      ASCII      |  ký tự đa byte  |
    |  |01|                 |                 |
    |u1|  |        |        |        |        |
    |  +--+--------+--------+--------+--------+
    |u2|  |  chữ   |  chữ   |  chữ   |  chữ   |
    |  |10|  Việt     Việt     Việt     Việt  |
    |  |  |  0101  |  0100  |  0111  |  0110  |
    |  +--+--    --+--    --+--    --+--    --+
    |  |  |  chữ   |  chữ   |  chữ   |  chữ   |
    |  |11|  Việt     Việt     Việt     Việt  |
    |  |  |  0001  |  0000  |  0011  |  0010  |
    +--+--+--------+--------+- hoặc -+--------+
                      2 byte đầu ký tự UTF-8+

    Các chữ Việt tạo bởi 8 âm vần khép hiếm và 2 thanh nhập (v1 v2 t1 t2 = 0011) được mã hóa vào cùng một ô với [2 byte đầu] ký tự UTF-8+ (u1 u2 s1 s2 = 1110), nhưng không đụng độ với UTF-8. Thật vậy, chúng có mã [nhị phân] là 11111xxx 10xxxxxx, trong khi ký tự UTF-8+ chỉ có dạng 110xxxxx 10xxxxxx (ký tự 2 byte), 1110xxxx 10xxxxxx... (ký tự 3 byte), 11110xxx 10xxxxxx... (ký tự 4 byte). (Xem Hình 5c.) Nói rõ hơn, các chữ Việt như thế chiếm chỗ của ký tự UTF-8 bất hợp lệ, cụ thể là chỗ từng được dành cho [2 byte đầu] ký tự UTF-8+ dài 5 byte (111110xx 10xxxxxx...) hoặc 6 byte (1111110x 10xxxxxx...). Nhắc lại lịch sử, UTF-8 nguyên thủy được quy hoạch với độ dài từ 1 đến 6 byte, đủ cho Unicode đến 2^31 điểm mã. Sau này, khi Unicode được giới hạn với tối đa 2^21 điểm mã, UTF-8 cũng được giới hạn tương ứng với độ dài tối đa là 4 byte, còn các ký tự 5 byte và 6 byte, vốn chưa hề được định nghĩa, đã trở thành bất hợp lệ.

    Hình 5c. Bản đồ quy hoạch không gian mã (nửa dưới, phóng to)
    Code:
          +-----------------------------------+
          |               s1 s2               |
          +--------+--------+--------+--------+
          |   00   |   01   |   10   |   11   |
    +--+--+--------+--------+--------+--------+
    |  |  |        |        |        |        |
    |  |  |   64       64       64       64   |
    |  |  |  [nửa]   [nửa]     [nửa]   [nửa]  |
    |  |10|  khép     khép     khép     khép  |
    |  |  |  gãy      bằng     nhập     khứ   |
    |u1|  |        |        |        |        |
    |  +--+-      -+-      -+--------+-      -+
    |u2|  |   48   |   48   |        |   48   |
    |  |  |  [nửa]   [nửa]  | 2 byte | [nửa]  |
    |  |11|   mở       mở   |  đầu   |   mở   |
    |  |  |  gãy   |  bằng  | ký tự  |  khứ   |
    |  |  +--------+--------+ UTF-8+ +--------+
    |  |  +--------+--------+--------+--------+
    +--+--+----^---+----^---+----^---+---^----+
               |        |        |       |     
               8        8        8       8     
             [nửa]    [nửa]    [nửa]   [nửa]  
             khép     khép     khép     khép   
             gãy      bằng     nhập     khứ
    Việc cải tiến mã này nhằm đơn giản hóa, nghĩa là làm cho dạng mã bám sát dạng chuẩn, từ đó tăng tốc độ xử lý dữ liệu ở dạng mã hay dạng chuẩn (mà không cần giải mã thành xâu UTF-8). Nó vẫn hướng đến mục tiêu chung được đặt ra từ đầu là xử lý dữ liệu thật nhanh, mục đích tối hậu của việc mã hóa (hơn là nén nhờ một thuật toán vạn năng) tiếng Việt nói riêng và dữ liệu nói chung trong các hệ thống thông tin.
    Đã được chỉnh sửa lần cuối bởi Ada : 04-04-2021 lúc 04:02 PM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  8. #18
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    745

    Tư liệu (tham khảo)

    [1] Pham, Andrea Hoa: "The key phonetic properties of Vietnamese tones: a reassessment". Proceedings of 15th International Congress of Phonetic Sciences, Barcelona, Spain, 2003. CD-ROM, M. J. Sole, D. Recasens and J. Romeo (eds). https://www.internationalphoneticassociation.org/icphs-proceedings/ICPhS2003/papers/p15_1703.pdf
    Đã được chỉnh sửa lần cuối bởi Ada : 27-07-2019 lúc 11:23 AM. Lý do: Hoa Pham, Andrea -> Pham, Andrea Hoa
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  9. #19
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    745

    Dị bản. Có 2 người sử dụng bảng mã phụ âm đầu của mình ở dạng cải biên. Một bạn sáp nhập mã c với mã k thành 1 mã phụ âm đầu duy nhất. Một bạn khác loại bỏ 2 mã phụ âm đầu hiếm dz, y, thêm 2 mã gh, ngh (tách biệt với g, ng), và dùng mã g để mã hóa giêng, giêt (thành g-iêng, g-iêt hơn là gi-iêng, gi-iêt).

    Mục đích khá rõ ràng. Sáp nhập c với k làm gọn tập giá trị, để tăng tốc truy vấn điểm. Tách biệt g/gi, g/gh, ng/ngh làm đơn giản hóa việc tính độ dài, để tăng tốc truy vấn khoảng.

    Tuy thế, 2 di bản trên không phải là bắt buộc để thực thi những kỹ thuật mà mình sẽ viết trong vài bài sắp tới, vốn giải một bài toán phụ, nhưng đôi lúc cần. Đó là so sánh theo thứ tự chính tả hai chữ Việt với nhau mà không cần giải mã. Bài toán then chốt để thực hiện truy vấn khoảng.
    Đã được chỉnh sửa lần cuối bởi Ada : 13-05-2019 lúc 08:12 PM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  10. #20
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    745

    Mỗi chữ Việt có thể viết thành chuỗi 7 chữ cái theo sau là dấu thanh. (Nếu chữ ngắn hơn 7 chữ cái, thì viết thêm dấu trắng cho đủ 7.)

    Kể cả các chữ cái f j w z, bảng chữ cái Việt có 33 chữ cái. Thêm dấu trắng, thành 34. Nên có thể mã hóa một chữ cái bằng 6 bit. Thêm 3 bit cho dấu thanh. Vậy, một chữ Việt có thể mã hóa bằng 7*6+3 = 45 bit bảo toàn thứ tự chính tả.

    Một cách nôm na, có thể gọi mã này là số thứ tự của chữ Việt; nhưng để tránh gây hiểu lầm, mình sẽ gọi nó là một mã tự điển. "Số thứ tự" hàm ý một dãy số liên tục, còn "mã tự điển" thì không nhất thiết liên tục: chen giữa hai mã số, có thể có một hay nhiều số chẳng phải là mã của chữ nào.

    Để tiện tham chiếu, mình đặt cho mã này một tên riêng là mã A. Luôn tiện, dạng sơ khai (phiên bản 2010) và dạng chuẩn (phiên bản 2018) đã nêu ở các bài trước đây sẽ được gọi lần lượt là mã C và mã D.

    Trong nhiều ứng dụng thực tế, ta muốn mã tự điển là số nguyên có dấu. Mã A, muốn có dấu, cần 46 bit. Nó có thể chứa trọn trong một thanh ghi 64 bit.

    Mã A hết sức hữu hiệu (sẽ nói thêm sau). Song, dịch từ mã D hay mã C sang mã A, thực chất, đã là giải mã rồi.

    Mã A được giới thiệu để làm rõ nghĩa thế nào là "so sánh mà không giải mã". Đó là tìm một mã M sao cho:

    • M là một mã tự điển, nghĩa là M(x) < M(y) nếu và chỉ nếu x < y, với hai chữ Việt x, y bất kỳ.
    • M(x) có độ dài không quá 32 bit; và nếu giới hạn đó là 31 bit thì càng tốt.
    • Có thể dịch mã C (và do đó, cả D) sang M một cách hữu hiệu.


    Tính "hữu hiệu" có thể hiểu là băng thông cao (tốc độ trung bình lớn), độ trễ thấp (thời gian tối đa nhỏ), hoặc bảo mật (thời gian tính toán không tiết lộ nội dung của dữ liệu, nói cách khác, thời gian là hằng số). Các thuật toán có tính bảo mật cũng được xem là "hữu hiệu" bởi vì dù không nhanh, chúng dùng rất ít bộ nhớ và rất ít dùng bộ nhớ.

    - - - Nội dung đã được cập nhật ngày 01-06-2019 lúc 09:47 AM - - -

    Để so sánh hai mã chữ Việt với nhau mà không giải mã, cách dễ thấy nhất là so sánh hai số thứ tự của chúng trong tự điển. Nói một cách hình thức hơn, có thể so sánh D(x) với D(y) bằng cách so sánh D'(x) và D'(y), trong đó D'(x) là số thứ tự của chữ x, và cũng chính là số thứ tự của D(x), trong tự điển mọi chữ mã hóa được bằng mã D.

    D' thỏa mọi tính chất cần thiết cho mã M vừa nêu ở bài trên. Thật thế:

    • Do mã D có 32 phụ âm đầu, 48 âm vần với 6 thanh và 72 âm vần với 8 thanh, nó có cả thảy 32*(48*6 + 72*8) = 27 * 2^10 từ mã, nghĩa là số thứ tự của chúng, tức D'(x), có thể biểu diễn bằng một số nguyên 15 bit, không kể bit dấu;
    • Mã D có thể dịch sang D' bằng cách tra bảng (mảng), lấy D(x) làm khóa (chỉ số) và D'(x) làm giá trị (nội dung). Không cần nói thêm, phép tra bảng như thế là cực nhanh.


    Tuy nhiên, do D(x) có độ dài 15 bit, nghĩa là có những 2^15 giá trị tiềm năng, và D'(x) phải chứa trong 2 byte, mảng có kích cỡ 2^15*2 = 2^16 B = 64 KiB, quá to đối với một số ứng dụng thực tế, như lập trình nhúng.

    Mảng đó còn to hơn hẳn kích cỡ của bộ nhớ đệm (cache) L1 của một bộ xử lý thông thường trong điện thoại thông minh, máy tính bảng, máy tính xách tay, máy tính để bàn, và cả máy chủ. Thời gian tra bảng to thế trên bộ xử lý cao cấp thế không hằng, mà biến thiên rất rõ rệt theo giá trị của địa chỉ (chỉ số). Tóm lại, cách này không bảo mật.
    Đã được chỉnh sửa lần cuối bởi Ada : 19-03-2021 lúc 01:19 PM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

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. Tính thành tiền trong bảng hóa đơn từ bảng chi tiết hóa đơn
    Gửi bởi tuanvi261 trong diễn đàn Thắc mắc đại cương Database & Reporting
    Trả lời: 2
    Bài viết cuối: 06-05-2013, 08:32 PM
  3. Hóa chất làm giảm điện trở đất, bột than tiếp địa, cọc tiếp địa, cọc thép mạ đồng, kim thu sét ese
    Gửi bởi chong set 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: 18-04-2012, 12:33 PM
  4. Gọi hàm con.. tiến hóa khôn lường
    Gửi bởi luckyfor trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 5
    Bài viết cuối: 06-10-2011, 03:58 PM

Tags của đề tài này

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