Sept.2012.ppt

Sept. 2012 Yangjun Chen ACS-3902 * Compression of bitmaps Run-length encoding: Run in a bit vector: a sequence of i 0’s followed by a 1. 000000010001 Run compression: a run r is represented as another bit string r’ composed of two parts. part 1: i expressed as a binary number, denoted as b1(i). part 2: Assume that b1(i) is j bits long. Then, part 2 is a sequence of (j – 1) 1’s followed by a 0, denoted as b2(i). r’ = b2(i)b1(i). This bit vector contains two runs. Sept. 2012 Yangjun Chen ACS-3902 * Compression of bitmaps Run-length encoding: Run in a bit vector s: a sequence of i 0’s followed by a 1. 000000010001 r’ = b2(i)b1(i). This bit vector contains two runs. r1 =b11 = 7 = 111, b12 = 110 r2 = 0001 b11 = 3 = 11, b12 = 10 r1’ = 110111 r2’ = 1011 Sept. 2012 Yangjun Chen ACS-3902 * 000000010001 r1’ r2’ = 1101111011 Decoding a compressed sequence s’: 1. Scan s’ from the beginning to find the first 0. 2. Let the first 0 appears at position j. Check the next j bits. The corresponding value is a run. 3. Remove all these bits from s’. Go to (1). Starting at the beginning, find the first 0 at the 3rd bit, so j = 3. The next 3 bits are 111, so we determine that the first integer is 7. In the same way, we can decode1011. Sept. 2012 Yangjun Chen ACS-3902 * Inverted files An inverted file - A list of pairs of the form: key word, pointer cat dog … the cat is fat … was raining cats and dogs … … Fido the Dogs … a bucket of pointers Sept. 2012 Yangjun Chen ACS-3902 * Inverted files When we use “buckets” of pointers to occurrences of each word, we may extend the idea to include in the bucket array some information about each occurrence. cat dog … the cat is fat … was raining cats and dogs … … Fido the Dogs … title header anchor text 5 10 3 57 type position … … … … Sept. 2012 Yangjun Chen ACS-3902 * Hierarchical database schema - hierarchical schema - record type, PCR type - virtual PCR: virtual child, virtual parent D