advanced code snippet search

Posted By

DrPepper on 09/20/11


Tagged


Versions (?)

[CISP 430 ] Succinct encodings

 / Published in: C++
 

string型データ structure は最終的に 2n + 1 bit になるにすぎない。ここで n は内部ノードの数である。structure型データの長さすら記録する必要がない。次の関数を実行すれば、情報が全く失われていないことがわかるだろう。これはstring型データから二分木を再構築する: inside of string node will be 2n + 1 bit therefore, you don't have to calculate a length of string data. the benefit of using following code is that you don't loose any data.

Expand | Embed | Plain Text 
  1. function EncodeSuccinct(node n, bitstring structure, array data) {
  2.     if (n = nil)// then
  3.        // structure ���� 0 �追���
  4.        // add 0 at end of structure 
  5.  
  6.     else         
  7.       //   structure ���� 1 �追��� -> add 1 at end of structure 
  8.       //  data ���� n.data �追��� -> addn.data at end of data 
  9.         EncodeSuccinct(n.left, structure, data)
  10.         EncodeSuccinct(n.right, structure, data)
  11. }
  12.  
  13. // string type 
  14. // remake a tree from string type data structure
  15.  
  16. function DecodeSuccinct(bitstring structure, array data) {
  17.  //   structure ������������������� b ����
  18.  //   remove the first bit and then put the first bit at b
  19.  
  20.    if ( b = 1 ) then
  21. //        ������ n ���
  22. //        make n from new node 
  23. //        data�����素���������素� n.data ����
  24. //        remove first element of data and put it in n.data 
  25.         n.left = DecodeSuccinct(structure, data)
  26.         n.right = DecodeSuccinct(structure, data)
  27. //        n ���
  28.     else
  29. //        nil ���
  30. //        return nil; 
  31.  
  32. }

Report this snippet  

You need to login to post a comment.