Magasin séquence binaire dans le tableau d'octets?

J'ai été déçu avec toutes les solutions que j'ai trouvé à la conversion de chaînes de bits à des tableaux d'octets, et vice-versa -- tous ont été buggy (même les BigInteger solution ci-dessus), et très peu sont aussi efficaces qu'ils devraient l'être.

Je me rends compte que l'OP été intéressée uniquement par une chaîne de bits dans un tableau de deux octets, ce qui le BitInteger approche semble bien fonctionner pour. Cependant, depuis ce poste est actuellement le premier résultat de recherche lors de la recherche de "chaîne de bits de tableau d'octets java" dans Google, je vais poster ma solution générale à ce problème pour les personnes atteintes d'énormes chaînes de caractères et/ou des tableaux d'octets.

Remarque que ma solution ci-dessous est la seule solution que j'ai couru qui passe tous mes cas de test -- de nombreuses solutions en ligne pour cette relativement simple problème ne fonctionnent tout simplement pas.

Code

/**
* Zips (compresses) bit strings to byte arrays and unzips (decompresses)
* byte arrays to bit strings.
*
* @author ryan
*
*/
public class BitZip {
private static final byte[] BIT_MASKS = new byte[] {1, 2, 4, 8, 16, 32, 64, -128};
private static final int BITS_PER_BYTE = 8;
private static final int MAX_BIT_INDEX_IN_BYTE = BITS_PER_BYTE - 1;
/**
* Decompress the specified byte array to a string.
* <p>
* This function does not pad with zeros for any bit-string result
* with a length indivisible by 8.
*
* @param bytes The bytes to convert into a string of bits, with byte[0]
*              consisting of the least significant bits in the byte array.
* @return The string of bits representing the byte array.
*/
public static final String unzip(final byte[] bytes) {
int byteCount = bytes.length;
int bitCount = byteCount * BITS_PER_BYTE;
char[] bits = new char[bitCount];
{
int bytesIndex = 0;
int iLeft = Math.max(bitCount - BITS_PER_BYTE, 0);
while (bytesIndex < byteCount) {
byte value = bytes[bytesIndex];
for (int b = MAX_BIT_INDEX_IN_BYTE; b >= 0; --b) {
bits[iLeft + b] = ((value % 2) == 0 ? '0' : '1');
value >>= 1;
}
iLeft = Math.max(iLeft - BITS_PER_BYTE, 0);
++bytesIndex;
}
}
return new String(bits).replaceFirst("^0+(?!$)", "");
}
/**
* Compresses the specified bit string to a byte array, ignoring trailing
* zeros past the most significant set bit.
*
* @param bits The string of bits (composed strictly of '0' and '1' characters)
*             to convert into an array of bytes.
* @return The bits, as a byte array with byte[0] containing the least
*         significant bits.
*/
public static final byte[] zip(final String bits) {
if ((bits == null) || bits.isEmpty()) {
//No observations -- return nothing.
return new byte[0];
}
char[] bitChars = bits.toCharArray();
int bitCount = bitChars.length;
int left;
for (left = 0; left < bitCount; ++left) {
//Ignore leading zeros.
if (bitChars[left] == '1') {
break;
}
}
if (bitCount == left) {
//Only '0's in the string.
return new byte[] {0};
}
int cBits = bitCount - left;
byte[] bytes = new byte[((cBits) / BITS_PER_BYTE) + (((cBits % BITS_PER_BYTE) > 0) ? 1 : 0)];
{
int iRight = bitCount - 1;
int iLeft = Math.max(bitCount - BITS_PER_BYTE, left);
int bytesIndex = 0;
byte _byte = 0;
while (bytesIndex < bytes.length) {
while (iLeft <= iRight) {
if (bitChars[iLeft] == '1') {
_byte |= BIT_MASKS[iRight - iLeft];
}
++iLeft;
}
bytes[bytesIndex++] = _byte;
iRight = Math.max(iRight - BITS_PER_BYTE, left);
iLeft = Math.max((1 + iRight) - BITS_PER_BYTE, left);
_byte = 0;
}
}
return bytes;
}
}

Performance

Je m'ennuyais au travail alors j'ai fait quelques tests de performance de comparer par rapport à la accepté de répondre ici pour lorsque N est grand. (En feignant d'ignorer le fait que la BigInteger approche posté ci-dessus ne fonctionne même pas correctement comme une approche générale.)

C'est en cours d'exécution avec une chaîne de bits aléatoires de taille de 5M et un tableau d'octets aléatoires de taille 1M:

String -> byte[] -- BigInteger result: 39098ms
String -> byte[] -- BitZip result:     29ms
byte[] -> String -- Integer result:    138ms
byte[] -> String -- BitZip result:     71ms

Et le code:

  public static void main(String[] argv) {
int testByteLength = 1000000;
int testStringLength = 5000000;
//Independently random.
final byte[] randomBytes = new byte[testByteLength];
final String randomBitString;
{
StringBuilder sb = new StringBuilder();
Random rand = new Random();
for (int i = 0; i < testStringLength; ++i) {
int value = rand.nextInt(1 + i);
sb.append((value % 2) == 0 ? '0' : '1');
randomBytes[i % testByteLength] = (byte) value;
}
randomBitString = sb.toString();
}
byte[] resultCompress;
String resultDecompress;
{
Stopwatch s = new Stopwatch();
TimeUnit ms = TimeUnit.MILLISECONDS;
{
s.start();
{
resultCompress = compressFromBigIntegerToByteArray(randomBitString);
}
s.stop();
{
System.out.println("String -> byte[] -- BigInteger result: " + s.elapsed(ms) + "ms");
}
s.reset();
}
{
s.start();
{
resultCompress = zip(randomBitString);
}
s.stop();
{
System.out.println("String -> byte[] -- BitZip result:     " + s.elapsed(ms) + "ms");
}
s.reset();
}
{
s.start();
{
resultDecompress = decompressFromIntegerParseInt(randomBytes);
}
s.stop();
{
System.out.println("byte[] -> String -- Integer result:    " + s.elapsed(ms) + "ms");
}
s.reset();
}
{
s.start();
{
resultDecompress = unzip(randomBytes);
}
s.stop();
{
System.out.println("byte[] -> String -- BitZip result:     " + s.elapsed(ms) + "ms");
}
s.reset();
}
}
}

OriginalL'auteur Ryan