bitoutput.java

一个自然语言处理的Java开源工具包。LingPipe目前已有很丰富的功能

	writeTrue();
    }


    /**
     * Writes the bits for the Elias gamma code for the specified
     * positive number.  The gamma code of the number <code>n</code>
     * is based on its binary representation <code>b[k-1],...,b[0]</code>:
     *
     * <blockquote><code>
     * gammaCode(b[k-1],...,b[0]) = unaryCode(k),b[k-1],...,b[0]
     * </code></blockquote>
     *
     * In words, the position of the most significant binary digit is
     * coded using a unary code, with the remaining digits making up
     * the rest of the gamma code.
     *
     * <P>The Following table provides an illustration of the gamma
     * coding of the first 17 positive integers.  Each row displays
     * the number being coded, its binary representation, and its
     * gamma code.  The gamma code is displayed as its unary coding of
     * the number of digits in the binary representation followed by a
     * space and then by the digits of the binary representation after
     * the first one.
     *
     * <blockquote><table border='1' cellpadding='5'>
     * <tr><td><i>Number</i></td>
     *     <td><i>Binary</i></td>
     *     <td><i>Gamma code</i></td></tr>
     * <tr><td>1</td><td>1</td><td>1</td></tr>
     * <tr><td>2</td><td>10</td><td>01 0</td></tr>
     * <tr><td>3</td><td>11</td><td>01 1</td></tr>
     * <tr><td>4</td><td>100</td><td>001 00</td></tr>
     * <tr><td>5</td><td>101</td><td>001 01</td></tr>
     * <tr><td>6</td><td>110</td><td>001 10</td></tr>
     * <tr><td>7</td><td>111</td><td>001 11</td></tr>
     * <tr><td>8</td><td>1000</td><td>0001 000</td></tr>
     * <tr><td>9</td><td>1001</td><td>0001 001</td></tr>
     * <tr><td>10</td><td>1010</td><td>0001 010</td></tr>
     * <tr><td>11</td><td>1011</td><td>0001 011</td></tr>
     * <tr><td>12</td><td>1100</td><td>0001 100</td></tr>
     * <tr><td>13</td><td>1101</td><td>0001 101</td></tr>
     * <tr><td>14</td><td>1110</td><td>0001 110</td></tr>
     * <tr><td>15</td><td>1111</td><td>0001 111</td></tr>
     * <tr><td>16</td><td>10000</td><td>00001 0000</td></tr>
     * <tr><td>17</td><td>10001</td><td>00001 0001</td></tr>
     * </table></blockquote>
     *
     * For more information on gamma coding, see:
     * 
     * <UL>
     * <LI> Witten, Ian H., Alistair Moffat, and Timothy C. Bell.
     * 1999. <i>Managing Gigabytes</i>. Academic Press.
     * <LI> <a href="http://en.wikipedia.org/wiki/Elias_gamma_coding"
     *       >Wikipedia: Elias gamma coding</a>
     * </UL>
     *
     * @param n Number to code.
     * @throws IOException If there is an I/O error writing to the
     * underlying stream.
     * @throws IllegalArgumentException If the number to be encoded is
     * zero or negative.
     */
    public void writeGamma(long n) throws IOException {
	validatePositive(n);
	if (n == 1l) {
	    writeTrue();
	    return;
	}
	int k = mostSignificantPowerOfTwo(n);
	writeUnary(k+1);
	writeLowOrderBits(k,n);
    }


    /**
     * Writes the bits for the Elias delta code for the specified
     * positive number.  The delta code of the number <code>n</code>
     * is based on its binary representation
     * <code>b[k-1],...,b[0]</code>:
     *
     * <blockquote><code>
     * deltaCode(b[k-1],...,b[0]) = gammaCode(k),b[k-1],...,b[0]
     * </code></blockquote>
     *
     * In words, the position of the most significant binary digit is
     * coded using a gamma code, with the remaining digits making up
     * the rest of the gamma code.  
     *
     * <P>The following table illustrates the delta codes for some
     * small numbers.  Each row lists the number, its binary
     * representation, and its delta code.  The delta code is
     * written as the initial gamma code of its most significant digit's
     * position and the remaining bits in the binary representation.
     * Note that the delta codes are longer for small numbers,
     * but shorter for large numbers.  
     *
     * <blockquote><table border='1' cellpadding='5'>
     * <tr><td><i>Number</i></td>
     *     <td><i>Binary</i></td>
     *     <td><i>Delta code</i></td></tr>
     * <tr><td>1</td><td>1</td><td>1</td></tr>
     * <tr><td>2</td><td>10</td><td>010 0</td></tr>
     * <tr><td>3</td><td>11</td><td>010 1</td></tr>
     * <tr><td>4</td><td>100</td><td>011 00</td></tr>
     * <tr><td>5</td><td>101</td><td>011 01</td></tr>
     * <tr><td>6</td><td>110</td><td>011 10</td></tr>
     * <tr><td>7</td><td>111</td><td>011 11</td></tr>
     * <tr><td>8</td><td>1000</td><td>00100 000</td></tr>
     * <tr><td>9</td><td>1001</td><td>00100 001</td></tr>
     * <tr><td>10</td><td>1010</td><td>00100 010</td></tr>
     * <tr><td>11</td><td>1011</td><td>00100 011</td></tr>
     * <tr><td>12</td><td>1100</td><td>00100 100</td></tr>
     * <tr><td>13</td><td>1101</td><td>00100 101</td></tr>
     * <tr><td>14</td><td>1110</td><td>00100 110</td></tr>
     * <tr><td>15</td><td>1111</td><td>00100 111</td></tr>
     * <tr><td>16</td><td>10000</td><td>00101 0000</td></tr>
     * <tr><td>17</td><td>10001</td><td>00101 0001</td></tr>
     * </table></blockquote>
     *
     * For more information on delta coding, see:
     * 
     * <UL>
     * <LI> Witten, Ian H., Alistair Moffat, and Timothy C. Bell.
     * 1999. <i>Managing Gigabytes</i>. Academic Press.
     * <LI> <a href="http://en.wikipedia.org/wiki/Elias_delta_coding"
     *       >Wikipedia: Elias delta coding</a>
     * </UL>
     *
     * @param n Number to code.
     * @throws IOException If there is an I/O error writing to the
     * underlying stream.
     * @throws IllegalArgumentException If the number to be encoded is
     * zero or negative.
     */
    public void writeDelta(long n) throws IOException {
	validatePositive(n);
	int numBits = mostSignificantPowerOfTwo(n); // 1 to 63
	if (numBits > 63) {
	    throw new IOException("numBits too large=" + numBits);
	}
	writeGamma(numBits+1);
	if (numBits > 0) 
	    writeLowOrderBits(numBits,n);
    }

    /**
     * Closes underlying output stream and releases any resources
     * associated with the stream.  This method first flushes the
     * output stream, which sets any remaining bits in the byte
     * currently being written to <code>0</code>.
     * 
     * <P>The close method calls the {@link OutputStream#close()}
     * method on the contained output stream.
     *
     * @throws IOException If there is an I/O exception writing the
     * next byte or closing the underlying output stream.
     */
    public void close() throws IOException {
	flush();
	mOut.close();
    }

    /** 
     * Flushes writes to the underlying output stream.  First, this
     * method sets any bits remaining in the current byte to
     * <code>0</code>.  It then calls {@link OutputStream#flush()} on
     * the underlying output stream.
     
     * @throws IOException If there is an exception writing to or
     * flushing the underlying output stream.
     */
    public void flush() throws IOException {
	if (mNextBitIndex < 7) {
	    mOut.write(mNextByte << mNextBitIndex); // shift to fill
	    reset();
	}
	mOut.flush();
    }
    
    /** 
     * Writes the specified bit.  The boolean <code>true</code> is
     * used for the bit <code>1</code> and <code>false</code> for
     * <code>0</code>.
     * 
     * @param bit Value to write.
     * @throws IOException If there is an exception writing to the
     * underlying output stream.
     */
    public void writeBit(boolean bit) throws IOException {
	if (bit) writeTrue();
	else writeFalse();
    }

    /** 
     * Writes a single <code>true</code> (<code>1</code>) bit.
     * 
     * @throws IOException If there is an exception writing to the
     * underlying output stream.
     */
    public void writeTrue() throws IOException {
	if (mNextBitIndex == 0) {
	    mOut.write(mNextByte | 1);
	    reset();
	} else {
	    mNextByte = (mNextByte | 1) << 1;
	    --mNextBitIndex;
	}
    }

    /** 
     * Writes a single <code>false</code> (<code>0</code>) bit.
     * 
     * @throws IOException If there is an exception writing to the
     * underlying output stream.
     */
    public void writeFalse() throws IOException {
	if (mNextBitIndex == 0) {
	    mOut.write(mNextByte);
	    reset();
	} else {
	    mNextByte <<= 1;
	    --mNextBitIndex;
	}
    }

    // writes out k lowest bits
    private void writeLowOrderBits(int numBits, long n) throws IOException {
	/* simple version that works:
	   while (--numBits >= 0)  
	   writeBit(((ONE << numBits) & n) != 0);
	*/

	// if fits without output, pack and return
	if (mNextBitIndex >= numBits) {
	    mNextByte 
		= ( (mNextByte << (numBits-1))
		    | (int) leastSignificantBits2(n,numBits))
		<< 1;
	    mNextBitIndex -= numBits;
	    return;
	}

	// pack rest of bit buffer and output
	numBits -= (mNextBitIndex + 1);
	mOut.write((mNextByte << mNextBitIndex) 
		   | (int) sliceBits2(n,numBits,mNextBitIndex+1));
           
	// write even numbers of bytes where available
	while (numBits >= 8) {
	    numBits -= 8;
	    mOut.write((int) sliceBits2(n,numBits,8));
	}

	// write remainder
	if (numBits == 0) {
	    reset();
	    return;
	}
	mNextByte = ((int) leastSignificantBits2(n,numBits)) << 1;
	mNextBitIndex = 7 - numBits;
    }

    private void reset() {
	mNextByte = 0;
	mNextBitIndex = 7;
    }

    private static final long ALL_ONES_LONG = ~0l;

    // not thread safe anyway, so might as well spend 800 bytes for class
    private static final boolean[] FIB_BUF 
	= new boolean[Math.FIBONACCI_SEQUENCE.length+1];

    private static final byte ZERO_BYTE = (byte) 0;
    

    /**
     * Returns the specified number of the least significant bits of
     * the specified long value as a long.  For example,
     * <code>leastSignificantBits(13,2) = 3</code>, because 13 is
     * <code>1011</code> in binary and the two least significant
     * digits are <code>11</code>. 
     * 
     * @param n Value whose least significant bits are returned.
     * @param numBits The number of bits to return.
     * @return The least significant number of bits.
     * @throws IllegalArgumentException If the number of bits is less than
     * 1 or greater than 64.
     */
    public static long leastSignificantBits(long n, int numBits) {
	if (numBits < 1 || numBits > 64) {
	    String msg = "Number of bits must be between 1 and 64 inclusive."
		+ " Found numBits=" + numBits;
	    throw new IllegalArgumentException(msg);
	}
	return leastSignificantBits2(n,numBits);
    }

    /**
     * Returns a slice of bits in the specified long value running
     * from the specified least significant bit for the specified
     * number of bits.  The bits are indexed in increasing order of
     * significance from 0 to 63.  So for the binary <code>110</code>,
     * the bit indexed 0 is 0, the bit indexed 1 is 1 and the bit
     * indexed 2 is 1.  For example, <code>sliceBits(57,2,3) =
     * 6</code>, because 57 is <code>111001</code> in binary and the
     * three bits extending to the left from position 2 are
     * <code>110</code>, which is 2.
     *
     * @param n Value to be sliced.
     * @param leastSignificantBit Index of least significant bit in
     * the result.
     * @param numBits Number of bits including least significant bit
     * to return.
     * @throws IllegalArgumentException If the number of bits is less
     * than zero or greater than 64, or if the least significant bit
     * index is less than 0 or greater than 63.
     */
    public static long sliceBits(long n, int leastSignificantBit, 
				 int numBits) {
	if (leastSignificantBit < 0 || leastSignificantBit > 63) {
	    String msg = "Least significant bit must be between 0 and 63."
		+ " Found leastSignificantBit=" + leastSignificantBit;
	    throw new IllegalArgumentException(msg);
	}
	if (numBits < 1 || numBits > 64) {
	    String msg = "Number of bits must be between 1 and 64 inclusive."
		+ " Found numBits=" + numBits;
	    throw new IllegalArgumentException(msg);
	}
	return sliceBits2(n,leastSignificantBit,numBits);
    }

    static long leastSignificantBits2(long n, int numBits) {
	return (ALL_ONES_LONG >>> (64-numBits)) & n;
    }

    static long sliceBits2(long n, int leastSignificantBit, int numBits) {
	return leastSignificantBits2(n >>> leastSignificantBit,
				     numBits);
    }

    /**
     * Returns the index of the most significant bit filled for the
     * specified long value.  For example, 
     *
     * <blockquote><pre>
     * mostSignificantPowerOfTwo(1) = 0
     * mostSignificantPowerOfTwo(2) = 1
     * mostSignificantPowerOfTwo(4) = 2
     * mostSignificantPowerOfTwo(8) = 3
     * </pre></blockquote>
     *
     * @param n The specified value.
     * @return The most significant power of 2 of the specified value.
     */
    public static int mostSignificantPowerOfTwo(long n) {
	int sum = (n >> 32 != 0) ? 32 : 0;
	if (n >> (sum | 16) != 0) sum = (sum | 16);
	if (n >> (sum | 8) != 0) sum = (sum | 8);
	if (n >> (sum | 4) != 0) sum = (sum | 4);
	if (n >> (sum | 2) != 0) sum = (sum | 2);
	return (n >> (sum | 1) != 0) ? (sum | 1) : sum;
    }

    static int mostSigFibonacci(long[] fibs, long n) {
	int low = 0;
	int high = fibs.length-1;
	while (low <= high) {
	    int mid = (low + high) / 2;
	    if (fibs[mid] < n)
		low = (low == mid) ? mid+1 : mid;
	    else if (fibs[mid] > n)
		high = (high == mid) ? mid-1 : mid;
	    else return mid;
	}
	return low-1;
    }

    static void validateNumBits(int numBits) {
	if (numBits > 0) return;
	String msg = "Number of bits must be positive."
	    + " Found numBits=" + numBits;
	throw new IllegalArgumentException(msg);
    }

    static void validatePositive(long n) {
	if (n > 0) return;
	String msg = "Require number greater than zero."
	    + " Found n=" + n;
	throw new IllegalArgumentException(msg);
    }

    static void validateNonNegative(long n) {
	if (n >= 0) return;
	String msg = "Require non-negative number."
	    + " Found n=" + n;
	throw new IllegalArgumentException(msg);
    }


}