Lập trình

1.1Vấn đề

Xem xét poset (P, ≤). Để Anc(x) = { y P |y < x} và Desc(x) = { y P |y > x}. Một phần tử jX  được nói là giao không thể tối giản nếu tồn tại xX chẳng hạn xDesc(j) và Anc(j) Anc(x) {x}. Tương tự, chúng ta có thể xác định hội không thể tối giản. Để J(P) biểu hiện rõ những phần của tất cả các yếu tố giao không thể tối giản và M(P) biểu hiện rõ những phần  tất cả các yếu tố hợp không thể tối giản được. Markowsky [5] chỉ ra rằng mã hóa tối ưu chỉ dành cho những tóan tử giao (hội) đối với một lưới là những cái đó đạt được bằng liên kết số hay bit khác nhau đến mỗi yếu tố giao không thể tối giản (hội không thể tối giản)

Để (P, ≤) là một poset, và . Habib et al. [6] cung cấp những định nghĩa sau. Một mã hóa đơn giản là sự sắp xếp ^S với  như là  là một kết hợp từ P lên trên 2^S ; đó là, x _py iff . Sau đó vấn đề là quyết định sự thỏa thuận tốt nhất như là mã hóa. Thật không may mắn, Caseau et al. [7] chứng tỏ rằng mã hóa đơn giản là cân bằng đa thức đến  vẽ đồ thị màu và lần lượt, nó là một vấn đề NP-hard. Thật vậy, vấn đề mã hóa thường (cũng được biết như vấn đề hai  chiều) thì tìm thấy số k nhỏ nhất như là tồn tại một sự sắp xếp ^{1,…,k} như ^S  với là một kết hợp từ P lên trên 2^S ; đó là, x _py iff . Rõ ràng, đây cũng là một vấn đề NP-hard.

2.      Những phương pháp trước đây

Một số phương pháp đã được đề nghị để giải quyết phép tóan trên poset và lattice. Thật là không may mắn, mỗi phép tóan có giới hạn hoặc không hiệu quả hoặc kích thước hoặc giải quyết hệ đa cấp năng động và phép tóan lattice

2.1 Transitive closure

Một phương pháp thường để lưu trữ 1 poset bao gồm ma trận transitive closure của nó. Để cho x₁, x₂, …,x_n là phần tử của poset. Một ma trận transitive closure là một ma trận n x n của 0 và 1, mà phần tử thứ (i, j) của ma trận là 1 iff x_i là cha của x_j . Một ma trận liền kề đối xứng A₁ được định nghĩa là hợp của ma trận liền kề  A và ma trận định dạng n x n I­_nxn  nơi mà phần tử thứ (i, j) của ma trận liền kề là 1 iff x_i là cha của x_j . Ma trận transitive closure có thể đạt được bởi sự tuần tự của phép tóan ma trận được chỉ ra bởi

A₀ = I­_nxn,  

A₁ = A x A₀  ,

A_k =A_k-1  x  A_k-1 ,

cho đến khi A_k = A_k-1 = A^* . Sự tính tóan này hội tụ hầu hết tại phép nhân  của ma trận logic n x n

Phương pháp này đòi hỏi O(n²) bit để lưu trữ. Để tìm GLB hoặc LUB của 2 phần tử, thì cần O(n) phép tóan trên vectơ n bit, đúng với nỗ lực cần để tìm thấy phần tử nhỏ nhất của bộ [8]. Những người trong Ait-Kaci [9] đưa ra thuật tóan pidgin-code để để chỉ định những mã trancitive closure đến phần tử của hệ đa cấp bắt đầu phần tử ở bên dưới và tiến hành theo hướng đi lên từng lớp từng lớp một. Mỗi nút là 1 mã nhị phân hoặc mã con của nó và 2^p với p là số nút viếng thăm trong phạm vi.

Hai mẫu giải mã transitive closure được biểu diễn ở hình 1, bên dưới cột được đặt tên là “transitive”. Giải mã ở phía trên sử dụng tối thiểu 7 bit trên 1 mã  là đối với 7 phần tử đầu tiên của hệ đa cấp (a-g), hình thành  1 cấu trúc cây. Giải mã ở phía dưới đối với tất cả 15 phần tử của hệ đa cấp (ngọai trừ nút q , là 1 nút ảo thay thế cho giao của nút e và f cho giải mã sau này). Việc giải mã này đòi hỏi tối thiểu chiều dài của mã là 15 bit, hoặc tổng chiều dài là 120 bit nếu không chú ý đến những số 0 ở đầu

2.2Giải mã từ phía bên dưới lên

Những người trong Ait-Kaci [9] cải tiến thuật tóan pidgin-code transitive closure chỉ bằng cách tăng chiều dài của 1 nút khi cần thiết. Vịêc gia tăng này xảy ra trong thuật tóan mới của họ chỉ khi một nút là nút con đơn (để phân biệt với 2) và khi những mã phân biệt tính tóan có thể so sánh được với mã thuộc tính đến phần tử được biết như là không thể so sánh được. Đó là, 1 mã được làm tốt hơn tất cả và chỉ nhưng mã ràng buộc bên dưới của nó, trong khi không thể so sánh với mã của những phần tử không thể so sánh được.

Hai mẫu mã hóa được biểu diễn trong hình 1 bên dưới cột có tên là Bottom-Up. Việc mã hóa bên trên sử dụng tối đa là 4 bit trên 1 mã là 7 phần tử đầu tiên của hệ thống trong hình 1. Việc mã hóa bên dưới cho tất cả 15 phần tử của hệ thống đòi hỏi chiều dài mã tối đa là 10 bit, và quan trọng nhỏ hơn 15 đối với transitive closure. Tổng chiều dài của mã hóa là 18 bit nếu những bit 0 đầu được phớt lờ.

Mặc dù phương pháp này kết quả mã dày hơn transitive closure, nhưng nó vẫn tạo ra những mã dài. Thật vậy, đối với việc mã hóa 1 chuỗi (1 cây với chỉ 1 nhánh) chiều dài của mã vẫn là n-1 . Mỗi sự gia tăng của chiều dài 1 từ  thêm 1 vào chiều dài tất cả các bit mặc dù việc sử dụng lại các bit không gây ra bất cứ mâu thuẫn nào.

Một giải pháp để giải quyết vấn đề này được đề nghị bởi Ait-Kaci là điều chỉnh hệ thống; đó là, tạo ra những nhóm có các nút kết nối đặc hơn và chỉ có 1 vài liên kết kế thừa với nhóm khác. Sau đó, những nhóm sẽ được mã hóa 1 cách riêng biệt, và mã nhóm được chỉ định để phân biệt phần tử của nhóm khác. Điều này sử dụng lại vị trí bit giữa các nhóm, trong khi chỉ việc thêm 1 số bit cho mã nhóm.                                                                                   

Trường hợp tốt nhất có thể, không gian sử dụng bởi mã hóa được điều chỉnh là O(nlogn), khi hệ đa cấp hoàn toàn có thể mô hình hóa ở mỗi mức. Đối với hệ đa cấp không có cấu trúc mô hình, như là một chuỗi, mã hóa cần O(n²) bit. Nỗ lực thêm đòi hỏi điều chỉnh và không gian để lưu trữ cấu trúc của sự điều chỉnh không được phân tích, nhưng được tranh luận bởi Ganguly et al. [8] đòi hỏi O(n²) thời gian và O(nd) không gian, điều kiện d là độ lớn nhất của đồ thị của những nhóm.

Trong ví dụ hệ đa cấp ở hình 1, sự điều chỉnh là không thể, và không có sự tiết kiệm nào sẽ được chịu. Đối với 7 yếu tố đầu, sự tiết kiệm trong chiều dài mã bởi sự điều chỉnh sẽ chính xác là offset bởi nhu cầu cho mã nhóm.

2.3Giải mã từ trên xuống

Caseau [10] đề nghị 1 phiên bản từ trên xuống của giải mã từ dưới lên mà sử dụng lại vị trí các bit trong quá trình giải mã tăng lên của lattice. Khi một mã phải được phân biệt, thuật tóan sẽ tìm kiếm 1 bit có thể đã được sử dụng trước đó, nhưng ở vị trí này nó không gây ra bất cứ mâu thuẫn nào với các nút hiện hành. Thủ tục phức tạp này tạo ra các mã mà nó được kết lại chặt chẽ bằng với sự điều chỉnh cho những cây nhưng tốt hơn nhiều cho những hệ đa cấp phức tạp hơn[10]. Trong một thí nghiệm thực tế, người ta nhận ra rằng việc mã hóa  đạt được 50% hiệu quả trở lên của phép tóan lattice trên transitive closure. Thủ tục này được đại diện 1 kiểu gia tăng, đó là có thể thêm 1 nút mới như là nút con của nút lá, “mà đó là trường hợp của hầu hết các hệ thống lớp hướng đối tượng”

Một giới hạn của thủ tục này đòi hỏi hệ thống phải được hình thành từ lattice. Điều này được giải quyết bởi 1 thuật tóan hòan thành lattice của Caseau, mà được khẳng định chạy trên thời gian đa thức. Thật không may mắn, sự hòan thành thêm những nút mới vào hệ đa cấp, và những điều này cũng phải được mã hóa và lưu trữ. Điều này thêm trên đầu thời gian và không gian đòi hỏi mà hóa thành một hệ đa cấp kế thừa bội thường. Xem xét hệ đa cấp 11 nút lá trong hình 2. Hoàn thành lưới trên nút lá đòi hỏi thêm 20 nút. 14 nút lá sẽ đòi hỏi thêm 50 nút. Nói chung, n nút lá là chiều cao hai poset (P, ≤) với   P={a₁,…,a_n}{b₁,…,b_n} điều kiện a_ib_j trong P, for i, j=1, 2,…, n. Như là một cấu trúc đòi hỏi trật tự của 2ⁿ nút được thêm vào cho việc hòan thành lưới.

Trường hợp tốt nhất trong cây cân bằng, khỏang trống được sử dụng bởi việc mã hóa từ trên xuống là O( nlogn ). Điều này làm giảm đến O(n²) bit cho những hệ đa cấp, nơi mà không có việc chia xẻ bit xảy ra, chẳng hạn như 1 chuỗi. Tất cả các ký tự trắng mã hóa cũng dựa trên một số nút trong lattice hòan tòan, chứ không phải trên hệ đa cấp gốc.

Hai mẫu mã hóa được biểu diễn trong hình 1 bên dưới cột Top-Down. Khi mã hóa Bottom-Up, việc mã hóa ở trên của 1 cấu trúc cây đòi hỏi tối đa 4 bit trên mã. Việc mã hóa bên dưới là 16 phần tử của hệ đa cấp bao gồm nút q được tạo bởi thuật tóan hòan thành lattice. Việc mã hóa này đòi hỏi chiều dài mã tối đa là 10 bit, hay là tổng chiều dài là 114 bit nếu những số không đầu bị phớt lờ. Điều này hơn Bottom-Up sau đó 3 lý do. Trước tiên, những nút thêm được yêu cầu. Thứ hai, rất ít khi sử dụng lại vị trí các bit vì thiếu cấu trúc cây trong hệ đa cấp. Cuối cùng, sự thay đổi vị trí bit của các nút vì kế thừa bội dẫn đến các mã dài hơn đối với những phần tử ớ gần phía trên của hệ đa cấp mà chúng được kế thừa bởi lớp con của chúng

2.4Mã hóa tĩnh

Phương pháp mã hóa thứ ba được đưa ra bởi Ganguly, liên quan đến sự xuyên suốt hệ đa cấp từ dưới lên được theo bởi 1 lộ trình từ trên xuống. Kết quả độ phức tạp thời gian là O(n+e), với e là số cạnh của hệ đa cấp, và kết quả kinh nghiệm là chỉ ra rằng có 1 khỏang trắng lưu trên những sư biến thiên. Thật không may mắn, khi thuật tóan này cũng yêu cầu cấu trúc lattice và nó không gia tăng, có nghĩ rằng khi thêm một nút vào hệ đa cấp thì phải tính tóan lại tòan bộ mã hóa

Sự phát triển kích thước trong việc mã hóa thì dựa trên 1 số lượng tối đa của những nút có cùng nút cha và số nút với cha bội ở tại mỗi mức của hệ thống. Kết quả này thì không cần thiết trong việc gia tăng kích thước mã đối với những lọai cố định của hệ thống, chẳng hạn như hệ thống 22 nút trong hình 3. Mã hóa tĩnh tạo ra chiều dài của mã là 12 bit, nhưng ngược lại mã hóa top-down chỉ cần có  bit. Một cấu trúc tương tự với 46 nút đòi hỏi 22 bit, được so sánh như là 8 bit của top-down. Nói chung, lưu trữ tòan bộ đòi hỏi mã hóa tĩnh phát triển trên tình tự n² , với n là số nút, ngược lại mã hóa top-down thì trên trình tự nlogn .

Hai mẫu mã hóa được biểu diễn trong hình 1 bên dưới cột có tên là Static. Mã hóa bên dưới đối với 16 phần tử của hệ thống vì nhu cầu lattice. Việc mã hóa này đòi hỏi chiều dài tối đa 11 bit, hoặc tổng chiều dài là 144 bit nếu những bit 0 ở đầu bị phớt lờ. Tổng chiều dài thì lớn vì sự chỉ định vị trí của những bit cao đến phần tử ở phía trên hệ thống trong lần duyệt qua lần đầu và sau đó được kế thừa bởi con của chúng trong lần duyệt qua lần hai

2.5Mã hóa khỏang thời gian

Agrawal đã đưa ra 1 phương pháp khác giải quyết transitive closure của mối liên hệ mà cho phép việc cập nhật gia tăng. Chúng đặt tên 1 nút với những con số thời gian bao gồm con số postorder của nó và số postorder nhỏ nhất trong số những con của nó. Kế thừa bội đòi hỏi việc thêm những khỏang thời gian thứ yếu đối với những nút tương ứng với những cách thêm vào xuống hệ đa cấp.

Trong trường hợp xấu nhất, mã hóa thời gian cần O(n²) độ phức tạp. Nói chung, nhu cầu việc lưu trữ phụ thuộc  phụ thuộc vào kích thước lưu trữ đối với những số mà đang được sử dụng trong mỗi khỏang thời gian. Trong một hệ đa cấp trên 256 nút, giá trị 16 bit có thể được sử dụng và lưu trữ mỗi nút nhảy thì cần ít nhất 32 bit đối với 1 khỏang thời gian đơn, cộng thêm khỏang trắng thêm vào đối với những khỏang thời gian thứ yếu

Hai mẫu mã hóa được biểu diễn ở hình 1 bên dưới cột có tên là Interval. Việc mã hóa ở trên thì chỉ cần 1 khỏang thời gian trên 1 nút vì cấu trúc cây của 7 phần tử đầu tiên của hệ đa cấp. Việc mã hóa ở dưới đối với 15 phần tử của hệ đa cấp, đòi hỏi 1 vài khỏang thời gian cho 1 vài nút. Chiều dài được tính bởi cho phép chỉ 4 bit trên 1 tổng thể trong những khỏang thời gian, vì giá trị lớn nhất là 15. Điều này đưa ra chiều dài mã dài nhất đối với 2 nút với 3 khỏang thời gian, 2 tổng thể trên 1 khỏang thời gian đối với 24 bit. Chiều dài tổng cộng của tất cả là 192 bit. Một nút nữa trong hệ đa cấp sẽ đòi hỏi việc gia tăng chiều dài lớn hơn, vì số bit trên tổng thể sẽ nhảy lên 5

3.      Thuật tóan mã hóa vBW

Đối với tài liệu này, mục đích của mã hóa là trình bày hiệu quả 1 hệ đa cấp kế thừa bội sử dụng lược đồ mã, cho phép tính tóan nhanh GCS và LCS, trong khi cho phép cập nhật gia tăng hệ đa cấp trong 1 ứng dụng lâu năm. Để đạt được mục đích này, lược đồ mã hóa của Caseau được sửa đổi để duy trì phương pháp top-down của việc chia xẻ bit, nhưng bỏ đi những nhu cầu trong sự hòan thành lattice

Những nghiên cứu trước [12] trong việc so sánh phương pháp mã hóa thử nghiệm với phương pháp top-down của phương pháp mã hóa Ait –Kaci , nhưng thất bại trong việc lạm dụng phương pháp chia xẻ bit của Caseau. Nghiên cứu này trước đây thuyết trình rằng phương pháp top-down, ngay cả với sự biến thiên, chỉ biểu diễn tốt chung với hệ đa cấp nhỏ (<300nút). Những phương pháp hiện tại với việc chia xẻ bit đạt được mã hóa nhỏ hơn nhiều trong thực hành, và sẽ được so sánh những kết quả này.

Mã hóa được xem như là bản đồ từ 1 hệ đa cấp đại diện cho poset (P, ≤, LCS, GCS) đến lattice (L,) với L chứa những từ nhị phân. Hai mã c₁ và c₂ được liên kết bởi c₁   c₂ nếu và chỉ nếu đối với mỗi vị trí bit chứa 1 bit 1 trong mã c₂ và trong mã c₁ cũng chứa 1 bit 1 ở vị trí đó. Chú ý rằng c₁ chỉ được phép chứa hơn bit 1 ở những vị trí khác. Phép tóan c₁  c₂ vàc₁  c₂  thì tương đương với tóan tử nhị phân and và or