nthderivative.go (3483B)
1 // Copyright 2017 Google Inc. All rights reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 package s2 16 17 // nthDerivativeCoder provides Nth Derivative Coding. 18 // (In signal processing disciplines, this is known as N-th Delta Coding.) 19 // 20 // Good for varint coding integer sequences with polynomial trends. 21 // 22 // Instead of coding a sequence of values directly, code its nth-order discrete 23 // derivative. Overflow in integer addition and subtraction makes this a 24 // lossless transform. 25 // 26 // constant linear quadratic 27 // trend trend trend 28 // / \ / \ / \_ 29 // input |0 0 0 0 1 2 3 4 9 16 25 36 30 // 0th derivative(identity) |0 0 0 0 1 2 3 4 9 16 25 36 31 // 1st derivative(delta coding) | 0 0 0 1 1 1 1 5 7 9 11 32 // 2nd derivative(linear prediction) | 0 0 1 0 0 0 4 2 2 2 33 // ------------------------------------- 34 // 0 1 2 3 4 5 6 7 8 9 10 11 35 // n in sequence 36 // 37 // Higher-order codings can break even or be detrimental on other sequences. 38 // 39 // random oscillating 40 // / \ / \_ 41 // input |5 9 6 1 8 8 2 -2 4 -4 6 -6 42 // 0th derivative(identity) |5 9 6 1 8 8 2 -2 4 -4 6 -6 43 // 1st derivative(delta coding) | 4 -3 -5 7 0 -6 -4 6 -8 10 -12 44 // 2nd derivative(linear prediction) | -7 -2 12 -7 -6 2 10 -14 18 -22 45 // --------------------------------------- 46 // 0 1 2 3 4 5 6 7 8 9 10 11 47 // n in sequence 48 // 49 // Note that the nth derivative isn't available until sequence item n. Earlier 50 // values are coded at lower order. For the above table, read 5 4 -7 -2 12 ... 51 type nthDerivativeCoder struct { 52 n, m int 53 memory [10]int32 54 } 55 56 // newNthDerivativeCoder returns a new coder, where n is the derivative order of the encoder (the N in NthDerivative). 57 // n must be within [0,10]. 58 func newNthDerivativeCoder(n int) *nthDerivativeCoder { 59 c := &nthDerivativeCoder{n: n} 60 if n < 0 || n > len(c.memory) { 61 panic("unsupported n. Must be within [0,10].") 62 } 63 return c 64 } 65 66 func (c *nthDerivativeCoder) encode(k int32) int32 { 67 for i := 0; i < c.m; i++ { 68 delta := k - c.memory[i] 69 c.memory[i] = k 70 k = delta 71 } 72 if c.m < c.n { 73 c.memory[c.m] = k 74 c.m++ 75 } 76 return k 77 } 78 79 func (c *nthDerivativeCoder) decode(k int32) int32 { 80 if c.m < c.n { 81 c.m++ 82 } 83 for i := c.m - 1; i >= 0; i-- { 84 c.memory[i] += k 85 k = c.memory[i] 86 } 87 return k 88 }