Lập trình

4. 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

4.1.Động lực

Lý do chính đối với nhu cầu lattice trong thủ tục của Caseau là sự giới hạn rằng những bit mới  chỉ có thêm vào những nút gốc (những nút này chỉ có 1 cha) , và nu cầu này đã duy trì một sự kết hợp những vị trí mới này với những nút tương ứng của chúng. Xem xét 1 hệ đa cấp không có lattice được minh họa ở bên phía trái của hình 4. Nút b và c sẽ được chỉ định đầu tiên những vị trí bit mới, kết quả b là mã ‘1’ và c là mã ‘10’ . Mã chỉ định nút d và e cả hai đều là ‘11’. Đối với những lattice được hòan thành ở bên phải của hình, nút q được chỉ định mã là ‘11’, nút d và e còn lại được chỉ định vị trí bit mới, kết quả d mã là ‘111’ và e mã là ‘1011’

Một sự cố gắng để bỏ đi giới hạn lattice đòi hỏi có thể chỉ định vị trí bit mới như là nút. Thủ tục chung định nghĩa ở đây cho phép bất kỳ nút nào được chỉ định 1 vị trí bit mới. Trong hệ đa cấp ở bên trái của hình 4, nút d được chỉ định mã là ‘11’, nhị phân hoặc là mã cha của nó, nhưng sẽ tăng thành mã ‘111’ khi nút e được thêm vào. Sau đó nút e sẽ có mã là ‘1011’. Kết quả này giống với mã hóa của Caseau nhưng không có thêm nút q

Bây giờ hãy xem xét ví dụ mà đòi hỏi sự thay đổi các mã để làm hạn chế sự mâu thuẫn. Ở phần bên trái của hình 5, việc thêm vào nút gây ra 2 mâu thuẫn. Nếu i được chỉ định là nhị phân hay là mã của cha  nó là ‘1111’, điều này sẽ gây hiểu lầm mã của cả hai d và g. Vì vậy, ở bên phải của hình, những vị trí bit mới của e và f phải được thay đổi, kết quả mã mới của e là ‘100001’và của f là ‘10010’. Những thay đổi này cũng phải được lan truyền đến nút con của nó, có tên là h. Cuối cùng, nút i có thể được chỉ định nhị phân hay mã mới của nút cha của nó là ‘110011’

4.2 Phương pháp

Để biểu diễn mã hóa, các nút ở trên trong hệ đa cấp được chỉ định là mã 0.  Những nút con được tuần tự thêm vào hệ đa cấp được mã hóa bằng cách gọi hàm Encode cho mỗi nút. Việc mã hóa 1 nút được gọi là những nút gốc (những nút có 1 cha) thì không giống với những nút khác. Những nút căn bản được chỉ định mã của nút cha cộng với 1 bit mới mà không gây ra sự hiểu lầm. Những nút không là nút gốc phải được kiểm tra để bảo đảm rằng không tạo ra sự hiểu lầm. Những hàm thừa nhận sự tồn tại của hàm Parents và Ancestors, mà hàm trả về 1 bộ các nút cha trực tiếp và 1 bộ tất cả các nút, theo thứ tự:

Hàm Increment (Không được biểu diễn) đơn giản chỉ trả về mã của nút x_n bằng một bit số 1 thêm vào vị trí được cung cấp bởi lời gọi. Một bit có sẵn ở vị trí đầu tiên được sử dụng để phân biệt 1 mã với những mã khác không có định nghĩa sự hiểu lầm được tìm thấy bằng hàm FreeBit. Hàm này so sánh mã với tất cả các mã chỉ định hiện hành của những nút không thể so sánh được để quyết định vị trí bit của những nút này là không dùng được, và sau đó chọn 1 bit còn trống. SingleBitDiff (không được biểu diễn) trả về mã chứa chỉ bit này cho cặp mã, hoặc trả về NULL nếu không có mã nào tồn tại. FirstZero (cũng không được biểu diễn) trả về vị trí 0 nhỏ nhất của 1 mã

Một phần quan trọng nhất của thuật tóan là tránh phát hiện ra những sự hiểu lầm và thay đổi mà được áp dụng để giải quyết chúng. Một hiểu lầm xảy ra nếu mã mới chỉ định đến 1 mã tạo ra mã giống như các nút khác hay sự xuất hiện sự liên kết với nút không thể so sánh được. ResolveConflicts so sánh mã mới với tất cả các nút trong bộ không thể so sánh được. Bộ không thể so sánh được của 1 nút, được quyết định bằng IncSet (không được biểu diễn) , được hình thành bởi các lớp mà không phải là lớp con cũng không phải là siêu lớp của lớp

Một sự thay đổi của nút x sử dụng nút y có nghĩa là bỏ đi bit mới mà được mở đầu cho nút y từ cha cao nhất của x mà chứa nó, cộng tất cả những con của cha , và thay thế nó với bit tự do đầu tiên cho x

 

Thủ tục truyền đề cập trong ResolveConflicts là đòi hỏi thêm một vị trí bit mới cho mã cho một nut hoặc tất cả các yếu tố liên quan.

Truyền( x: nut ; c: mã)

Với mỗi y<=x làm

Số gia (y;c)

Theo hệ đẳng cấp trong hình 1 và việc mã hoá trong cột được đánh nhãn ”vBW”.  Mã cho bảy ký tự đầu tiên (a-g) tình bày trong phần đầu của bảng minh hoạ kết quả sau không nhiều kế thừa và do vậy chỉ gọi đến hàm FreeBit. Chú ý rằng việc dùng lại vị trí bit thứ ba và thứ tư trong nut d thông qua g. Tiến tình này tiếp tục với nut h và I bằng việc thêm vào vị trí bit 5 và 6, tách biệt thứ tự, cho mã của nut cha d. Việc thêm nut j với mã ’1111’ sẽ gây ra mâu thuẫn đầu tiên, và dẫn đến sự biến đổi vị trí bit của e và f từ vị trí bit 4 và 3 đến 8 và 7, tách biệt thứ tự, dẫn đến mã ’11000011’ cho nut j. Nut k sẽ được ấn định  cùng mã, vì vậy FrêBit tìm đựơc vị trí 5, Số gia dẫn đến mã ’11010011’ cho nut k, FreeBit tìm được vị trí 6, và Truyền cập nhật mã của nut j thành ’11100011’. Việc thêm những nut còn lại và thêm nưa mâu thuẫn dẫn đến việc mã hổátng phần cuối của hình vẽ.

Sự so sánh của việc mã hoá này với việc mã hoá “Top-Down” trong hình là một bit sai lạc. mặc dù sự mã hoá này xuất hiện nhiều thoả thuận trong toàn thể, nó chỉ là kết quả của sự tổ chức của hệ đẳng cấp, và không do phương pháp mã hoá. Trong hệ đẳng cấp này, nhiều mã kết lại tình cờ xảy ra do sự khác biệt trong hai sự bổ sung khi và lúc sụ thay đổi vị trí được thực hiện. Một hệ thống khác nhỏ thể dễ dàng được tạo ra để làm cho kết quả mã hoá “Top-Down” trong mã ngắn. Cái quan trọng dường như là nhu cầu cho nut thêm vào trong sự hoàn thành lưới cho phương pháp “Top-Down”, và kích thứơc mã thông tin của nó, và dẫn đến nhu cầu lưu trữ lớn toàn diện.

 4.3 Sự chính xác

Bằng chứng của sự chính xác của giải thuật liên quan đến sự kiểm tra tình trạng của việc mã hoá sau khi thêm mỗi nut. Để làm đơn giản bằng chứng của sự chính xác, một loạt bổ đề hữu ích được trình bày.

Bổ đề 1 (Thay thế) .

Chứng minh. Bổ đề sau sự thật là  là đúng nếu và sự thay thế của số nhị phân hoặc.

Bổ đề 2. Nếu x thì

Chứng minh. Bằng chứng là bằng phương pháp quy nạp trên khoảng cách giữa x và y. Cho trường hợp căn bản, D(x,y)=0, x=y, và rõ ràng rằng . Giả thiết quy nạp cho rằng để D(x,z)=k, nếu  thì . Cho bước quy nạp, thừa nhận D(x,y)=k+1. Để z là nut tren đường dẫn của chiều dài k+1 từ x đến y chẳng hạn như y là con trực tiếp cảu z và . Rõ ràng, D(x,z)=k, và từ giả thuyết quy nạp, . Trong quá trình xây dựng, khi y được thêm như con của z, nó kế thừa mã của z.  Chuyện này xảy ra khi z chỉ là cha của y, trường hợp mà mã chỉ định y là số gia của mã của z, hoặc khi y có nhiều cha, trường hợp mà y được chỉ định số nhị phân hoặc mã của cha nó bao gồm mã của z. Mọi sự thay đổi mã của z sẽ được chuyển cho y. Mọi sự thay đổi với y sẽ chỉ xảy ra trong hàm Modify, mà trong trường hợp sự thay đổi sẽ là bit thêm và trong suốt một sự gia tăng, mà không ảnh hưởng đến những cái khác trong z. Theo đó  và bằng Bổ đề 1 (Thay thế) .

Bổ đề 3. Nếu thì

Chứng minh. Không mất tính phổ biến, thừa nhận x được thêm vào việc mã hoá sau nut y. Nếu x có một cha đơn, thì mã cho x là số gia của mã của cha với 1 bit tự do. Nếu kết quả là mã của y, thì bit không được tự do. Nếu x có nhiều cha, mà giải quyết mâu thuẫn sẽ bảo đảm rằng x không kết thúc với mã của một nut khác. Sụ thay đổi để mã hoá cho các nut sau không thể vi phạm tình trạng khi chúng cũng dựa trên các bit rãnh trong hệ đẳng cấp.

Bổ đề 4. Cho tất cả nut x, y thuộc P, hoặc (1)  hoặc  như  và

Chứng minh. Chọn bất kì hai nut x và y từ P. Nếu  thì bổ đề đúng. Bây giờ xem như x không  y. Nếu x>y,  bởi bổ đề 2, bởi bổ đề 3, và phải có một bit trong y mà không trong x, như vậy bổ đề là đúng. Mặt khác x và y không thể so sánh được. Nếu mã cho y chứa đựng một bit không được tìm thấy trong mã của x, bổ đề là đúng. Mặt khác, thừa nhận , và để LCS{x,y}={}. Trong những điều sau đây, điều này đã được chứng minh là sai bằng phản chứng.

Trước tiên xem tình trạng của mã một cách trực tiếp sau khi mã hoá x và y, bất cứ cái gì sau cùng. Bằng bổ đề 2, và  với mọi i,

Thừa nhận mã y được mã hoá sau x. Nếu y là một nut chính, thì mã cho y sẽ được tạo với một số gia của mã của cha nó, và được chỉ định một bit trống không được x sử dụng, một sự trái ngược. Nếu y không là chính, thì ResolveConflicts sẽ được gọi. Nếu mã cho y không chứa đựng một mã không có trong x, thì lúc gọi , và mã cho y sẽ được gia tăng với một bit không thuộc mã của x, một sự mâu thuẫn.

Bây giờ cho là nut x được mã hoá sau mã y. Nếu nut x là chính, mã của nó là do một số gia của mã của cha nó w. Rõ ràng, LCS({x,y})=LCS({w,y}). Có khả năng chứng minh rằng mã của cha nó không chứa đựng một bit được tìm thấy trong mã của y bởi vì việc mã hoá của x sẽ không cộng bit này vào mã của cha là một bit không dùng. Nếu y được mã hoá sau w, sự tranh luận ở trên giữ cho w. nếu y. Nếu , một cuộc gọi sẽ dẫn đến một trong những bit

Trong mã của y đang được chuyển từ mã của z. Bây giờ với tình trạng của mã sau khi tất cả các nut được thêm. Nếu x và y có thể so sánh, tranh luận ở trên cho những trường hợp này vẫn giữ sau khi thêm nut xa hơn. Vì vậy nó có khả năng để chấp nhận rằng x và y là không thể so sánh. Với những nut khác được thêm sau x và y, gọi xa hơn đến Modify, Increment, và Propagate không thể thêm bit riêng từ y đễn mã cho x bởi vì nó sẽ không tự do, và cũng không di chuyển bit riêng từ y mà không thêm một bit trống mới không có trong x, để mã x giữ nguyên sự khác biệt.

Bổ đề 5. Nếu  thì

Chứng mhinh. bằng chứng là bằng phương pháp quy nạp trên số nut được mã hoá bởi các hàm. Cho trường hợp căn bản, một nut đơn được mã hoá, và câu lệnh được giữ lại. Với giả thuyết quy nạp, thừa nhận câu lệnh giữ lại với một hệ đẳng cấp P với n-1 nut. Với bước quy nạp, thêm một nut mới với cha {} đến P, cho P’. Có nghia là việc mã hoá mới cho P’ như . Thừa nhận x và y là bất kỳ cặp nut nào trong P’ chẳng hạn như . Rõ ràng nếu x và y ở trong P thì bổ đề là đúng do quy nạp, khi Modify và Propagate sẽ không phát sinh ra bất cứ mối quan hệ nào trong mã không có trong hệ đẳng cấp. Nó theo sau  bởi vậy mà hoặc là x=a hặc y=a.

Trước tiên, cho là a là một nut chính (i=1). Việc mã hoá cho nó mã của cha nó cộng với một bit đơn tự do, i.e. , và không mã nào thay đổi.

Nếu y=a, và khi  là một bit tự do, , một mâu thuẫn với giả định.

Nếu x=a, , , nơi . Khi y. Trước hết thừa nhận . Sau đó  bằng giả thuyết quy nạp, và . Bây giờ thừa nhận . Sau đó với bổ đề 4, cả , trong trường hợp , hoặc là tồn tại một q chẳng hạn  và. Khi mã cho  không chứa bit tương ứng với q và r nhưng mã cho y thì có, mã cho x chứa tất cả các bit của mã cho y, và mã cho x chỉ chứa một bit nhiều hơn mã cho , thì q=r, và chỉ có một như q. Khi x không  y,  không là bit tự do trong , mâu thuẫn.

Bây giờ, giả định rằng a không là nut chính (i>1). Việc mã hoá đầu tiên cho a số nhị phân hoặc của mã của cha nó, và rồi giải quyết mâu thuẫn.

Nếu  và , thì nếu , và  bởi giả thuyết quy nạp, hoặc là do thay đổi  và/ hoặc là do thay đổi bởi ResolveConflicts hoặc Modify. Cả trong trường hợp, FreeBit sẽ không cho phép thay đổi bit mà dẫn đến mối liên hệ không đúng.

Nếu  và y=a, thì  trừ khi , bởi vì ResolveConflicts sẽ không  cho phép điều đó.

Nếu x=a, thì theo bổ đề 4, cả  hoặc tồn tại một q chẳng hạn như  và . Theo đó, , mâu thuẫn với giả định.

Định lý 6 (Gộp chung). Với việc mã hoá  của một hệ đẳng cấp,  nếu

Chứng minh. Xảy ra  trực tiếp từ bổ đề 2 và 5.

4.4 Năng  suất.

Chìa khoá cho sự bổ sung có hiệu quả của giải thuật này không chỉ tạo ra hiệu quả của việc mã hoá, mà còn trong việc lưu trữ ít nhất số lượng thông tin về hệ đẳng cấu bên ngoài lưu trữ trong chính mã của chúng. Giả định được tạo nên trong phân tích hiệu quả là không thông tin nào được lưu trữ bên ngoài của việc mã hoá.

Ranh giới dấu cách tốt nhất đòi hỏi bởi việc mã hoá là O(log n) bit một nut, nơi mà n là số lượng nut trong hệ đẳng cấu, cho một ranh giới toàn bộ của O(n log n). Điều này xảy ra khi hệ đẳng cấp là lưới hoàn toàn và được mã hóa bề ngang trước, và một nut tồn tại cho mỗi mã nhị phân có thể. Trong trường hợp xấu nhất, việc mã hoá đòi hỏi O(n) bit mỗi nut, hoặc toàn bộ O(), cái mà xảy ra khi hệ đẳng cấp là một loạt nhánh hoặc đơn nhánh, hoặc khi nó chỉ có một mức độ.

Hàm chiếm ưu thế cho thời gian mã hoá cho mỗi nut là hàm ResolveConflicts. Tính toán tập hợp vô song cho một nut đòi hỏi kiểm tra tất cả các nut khác cho sự liên quan. Cho mỗi nut trong tập hợp, mà có thể bao gồm hầu hết tất cả các nut khác, cả hàm FreeBit hoặc hàm Modify sẽ được gọi. FreeBit đòi hỏi phân tích vị trí bit, cái mà đòi hỏi viẹc kiểm tra lại với n bit. Modify yêu cầu kiểm trakiểm tra vị trí bit qua FreeBit, và sau đó kiểm tra cho phân lớp phổ biến lớn nhất của hình thức nguyên thuỷ của nut, một thao tác yêu cầu O() thao tác. Vì vậy toàn bộ thời gian chạy của ReosolveConflicts, và theo cách của Encode, là O() mỗi nut, hoặc O() toàn bộ.

Thử nghiệm trước [12] đã phân tích sự thực hiện của nhiều phương thức mã hoá khác nhau trên một hệ đẳng cấp thế giới thực, cụ thể là hệ đẳng cấp lớp 300-đối tượng LAURE [13]. Khi ứng dụng vào hệ đẳng cấp này, phương thức mã hoá thấp nhất trong bài này đòi hỏi 860 byte lưu trữ cho mã, với mã dài nhất là 32 bit. So sánh này rất thuận lợi cho việc mã hoá của AitKaci [9], cái mà đồi hỏi 5280 byte và đưa ra mã dài nhất 281 bit, thừa nhận không điều biến. Với sự điều biến, việc mã hoá đòi hỏi 1452 byte, với mã dai nhất 120 bit, sử dụng 30 nhóm. Phương pháp nén dãy băng của Agrawal. [11] đòi hỏi 1336 byte cho hệ đẳng cấp giống nhau này. Ngay cả phương pháp mã hoá của riêng Caseau đòi hỏi 1014 byte, với mã dài nhất 33 bit. Như trước, mặc dù kích thước mã tương tự nhau (phụ thuộc vào tính tự nhiên của hệ đẳng cấp), nhiều lưu trữ toàn bộ hơn được yêu cầu để hoàn thành lưới. Thử nghiệm xa hơn được hướng dẫn để xác định nếu trật tự của việc thêm nut với số sau cùng của con đầu tiên (của những nut ma cha đã được mã hoá) dẫn đến sự gia tăng trong kich thước toàn bộ của việc mã hoá thành 1098 byte của việc sự lưu trữ, với một mã lớn nhất 34 bit. Hầu hết con đầu tiên giảm bớt sự lưu trữ 848 byte, với mỗi 32 bit lớn nhất.

Để kiểm tra quan điểm về việc mã hoá nut với hầu hết các con đầu tiên, xem như hệ đẳng cấp H1 của n+1 nut chẳng hạn như nut trên cùng r có n-x nut con, A={}, với không có con, và một “sự hoàn thành đỉnh” của x nut, B={} như những nut con khác của nó. Chú ý rằng chiều dài của mã dài nhất của nut trong một “sự hoàn thành đỉnh” là chiều dài l=logx +1 và tổng các bit cần để mã hoá nó là x(logx +1). Nó theo sau tổng các bit cần để mã hoá H1 là ngang bằng với x(logx+1) + (l+1)+…+(l+(n-x)) nếu nut trong sự hoàn thành đỉnh đựoc mã hoá trứơc tiên, và nó ngang bằng với (1+2+…+(n-x))+ x(n-x+1)+x(logx+1) nếu các nut trong A được mã hoá trước tiên. Rõ ràng, tốt hơn là mã hoá những nut trong B trước tiên. Sự khác biệt lớn nhất xảy ra khi x. Trong trường hợp này, một cái sẽ mã hoá nut với hầu hết nut con trước tiên. Một ví dụ của hệ đẳng cấp được cung cấp trong hình 6, với 2 việc mã hoá khác nhau đã chỉ ra.

Tuy nhiên, trật tự mã hoá không quan trọng nếu chúng ta thay “ sự hoàn thành đỉnh ” bằng một đồ thị chia đôi đầy đủ với  nut trong mỗi tập hợp được chia. Trong trường hợp này, toàn bộ kích thước mã hoá là giống nhau. Điều này được minh hoạ trong hình 7.

Hơn nữa, tốt hơn không mã hoá nut có nhiều con cháu đầu tiên cho hệ đẳng cấp theo sau. Để thuận lợi, chúng ta giả định rằng  nơi . Để H2 là hệ đẳng cấp của n+2 nut chảng hạn như nut cao nhất r có  con và chúng tất cả đều có con chung mà có  con khác, và nut cao nhất cũng có một “đỉnh đầy đủ” của n nut như con khác của nó. Sự khác biệt là  nếu là lớn. Một ví dụ của tác động này được thể hiện trong hình 8.

4.5 Thao tác lưới

Với một hệ đẳng cấp kế thừa với một cấu trúc lưới, các thao tác lưới của việc sắp xếp, GLB, và LUB có liên quan. Chẳng hạn như hệ đẳng cấp, nó có lợi nếu việc mã hoá c có thể đảo ngược, hoặc là một dồng hình lưới. Khi hệ đẳng cấp mã hoá bởi các hàm đưa ra trong bài viết này không đòi hỏi phải là lưới, việc mã hoá không dễ thay đổi, và nhiều nổ lực đòi hỏi để quyết định lớp hoặc tập hợp các lớp được bao phủ bởi mã. Đây là đúng nhất nếu kết quả của thao tác GCS hoặc LCS là một tập hợp các lớp, phụ thuộc vào tính không lưới của hệ đẳng cấp. Thao tác sau minh họa tác động này

 

 

 

Xem như thao tác GLB(h,m) trên hệ đẳng cấp trong hình 1 Thao tác điện toán

dễ dàng xác định rằng GLB(h,m)=o. Tương tự, với LUB(f,g),

Với những thao tác phức tạp hơn GCS({d,g}), thao tác điện toán

mà là mã của lớp đơn. Việc sử dụng sự sắp xếp kiểm tra , và việc tìm thấy tất cả mã được sắp xếp bởi mã , cho tập hợp các mã {100101111,100011011}, và tìm thấy tập mã tối thiểu trong phần kiểm tra mà sắp xếp những cái khác cho cùng tập hợp, Việc trình bày mã cảu lớp n và o, GCS cho lớp d và g.

Trong khi đúng là việc xác định lớp chính xác bao gồm trong thao tác GCS hoặc LCS là một quá trình tương đối tốn kém, nó nên được ghi chú rằng các quá trình hiếm khi giữ nguyên ứng dụng đích.

Ví dụ như, xem hệ thống cơ sở dữ liệu dựa trên các đối tượng phức tạp nơi mà các đối tượng thuộc về một lớp đơn. Nếu có sự xác nhận đựơc thực hiện trong một hệ thống mà một đối tượng được biết tồn tại trong hai hay nhiều lớp, nó sẽ phải được xác định lớp nào là thực trong lớp mà nó thật sự thuộc về, có thể xã định với thao tác GCS. Để xác định lớp thật sự, mã đạt được phải được giải mã, Thật ra, việc giải mã có thể không phải được làm hết, như mã đạt được của thao tác GCS nhiều thông tin, hoặc thậm chí nhiều hơn, như là thông tin được biết về lớp thật sự của đối tượng , và vì vậy có thể lưu trữ với đối tuợng .

Phương pháp lưu mã này cho phép sự xác nhận xa hơn như lớp của một đối tượng là dễ dàng giải quyết. Theo đó trong đối tượng ứng dụng cơ sở dữ liệu liên tục có thể được kết hợp với mã của chúng, và không với tên lớp. Có thể nói tương tự với kiển thức trên cơ sở hệ thống.  Điều này giảm xa hơn việc lưu trữ tonà bộ chỉ có mã phải kết hợp với lớp, không tập hợp các định nghĩa lớp có thể. Vì thế ngay cả suy nghĩ về lưu trữ mã độ dài biến số đòi hỏi nhiều lưu trữ hơn con trỏ lớp đơn, nó không đòi hỏi nhiều hơn có thể khi đôid tượng không thể giải quyết với một lớp đơn, và do vậy phải lưu trữ với một tập hợp các lớp con trỏ.

Tóm tắt

Giải thuật space-and-time-efficient mã hoá một lưới thành tập hợp vec tơ nhị phân được đề xuất, và giải thuật có hiêu quả cho việc tính toán GLB, LUB, và mối liên hệ giữa hai nut là nét chính. Giải thuật, cho phép chức năg thêm một lớp mới với sự thay đổi tối thiểu sự tồn tại của mã, đòi hỏi O() thời gian và tệ nhất O() không gian cho việc mã hoá một hệ đẳng cấp toàn bộ, và cho phép thao tác điện toán lưới có hiệu quả. Dựa vào kết quả minh hoạ sự liên quan của phương pháp.

Ứng dụng liên tục chẳng hạn như cơ sớ dữ liệu và kiến thức tren cơ sở hệ thống đòi hỏi hiệu quả việc mã hoá cho phép thay đổi để được thực hiện hệ đẳng cấp với sự biên tập lại của việc mã hoá ít nhất. Lưu trữ mã đơn cho đối tượng chỉ được nhận ra tồn tại trong một tập hợp lớp cha cải tiến xa hơn việc lưu trữ toàn bộ đòi hỏi nhiều hệ thống nơi mà lớp thật sự của đối tượng chưa được giải quyết.