Comprimir 21 caracteres alfanuméricos en 16 bytes

Question

Estoy tratando de tomar 21 bytes de datos que identifican de forma única una operación y almacenarlos en una matriz de 16 bytes char. Tengo problemas para encontrar el algoritmo correcto para esto.

El ID de comercio, que estoy tratando de comprimir consta de 2 campos:

1. 18 caracteres alfanuméricos consistentes en los caracteres ASCII 0x20 a 0x7E, Incluido. (32-126)
2. una cadena numérica de 3 caracteres "000" a "999" clase

Así que un C++ que abarque estos datos tiene el siguiente aspecto:

class ID 
{ 
public: 
    char trade_num_[18]; 
    char broker_[3]; 
}; 

Este necesidades de datos que se almacena en una estructura de 16 char de datos, que se ve así:

class Compressed 
{ 
public: 
    char sku_[16];  
}; 

traté de aprovechar el hecho de que, dado que los personajes de trade_num_ son solo 0-127 había 1 bit sin usar en cada personaje. Del mismo modo, 999 en binario es 1111100111, que está a solo 10 bits - 6 bits menos que una palabra de 2 bytes. Pero cuando averiguo cuánto puedo exprimir esto, lo más pequeño que puedo hacer es 17 bytes; un byte demasiado grande.

¿Alguna idea? Por favor, trade_num_ es un nombre inapropiado. Puede contener letras y otros caracteres. Eso es lo que dice la especificación.

EDIT: Perdón por la confusión. El campo trade_num_ es de hecho 18 bytes y no 16. Después de publicar este hilo, mi conexión a Internet murió y no pude volver a este hilo hasta ahora.

EDIT2: Creo que es seguro hacer una suposición sobre el conjunto de datos. Para el campo trade_num_, podemos suponer que los caracteres ASCII no imprimibles 0-31 no estarán presentes. Tampoco lo harán los códigos ASCII 127 o 126 (~). Todos los demás pueden estar presentes, incluidas letras mayúsculas y minúsculas, números y signos de puntuación. Esto deja un total de 94 caracteres en el conjunto que comprenderá trade_num_, códigos ASCII 32 a 125, inclusive.

Answer 1

Si tiene 18 caracteres en el rango de 0 a 127 y un número en el rango de 0 a 999 y lo compacta tanto como sea posible, requerirá 17 bytes.

>>> math.log(128**18 * 1000, 256) 
16.995723035582763 

Es posible que pueda aprovechar el hecho de que es probable que algunos caracteres no se usen. En particular, es poco probable que haya caracteres por debajo del valor 32, y probablemente tampoco se use 127. Si puede encontrar un personaje más sin usar, primero puede convertir los caracteres en la base 94 y luego empacarlos en los bytes lo más cerca posible.

>>> math.log(94**18 * 1000, 256) 
15.993547951857446 

Este simplemente encaja en 16 bytes!

---

código Ejemplo

Aquí es un código de ejemplo escrito en Python (pero escrito en un estilo muy imprescindible para que fácilmente puede ser entendido por los programadores no Python). Supongo que no hay tildes (~) en la entrada. Si hay, debes sustituirlos por otro personaje antes de codificar la cadena.

def encodeChar(c): 
    return ord(c) - 32 

def encode(s, n): 
    t = 0 
    for c in s: 
     t = t * 94 + encodeChar(c) 
    t = t * 1000 + n 

    r = [] 
    for i in range(16): 
     r.append(int(t % 256)) 
     t /= 256 

    return r 

print encode('     ', 0) # smallest possible value 
print encode('abcdefghijklmnopqr', 123) 
print encode('}}}}}}}}}}}}}}}}}}', 999) # largest possible value 

Salida:

[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 
[ 59, 118, 192, 166, 108, 50, 131, 135, 174, 93, 87, 215, 177, 56, 170, 172] 
[255, 255, 159, 243, 182, 100, 36, 102, 214, 109, 171, 77, 211, 183, 0, 247] 

Este algoritmo utiliza la capacidad de Python para manejar números muy grandes. Para convertir este código a C++, puede usar una gran biblioteca de enteros.

Por supuesto, necesitará una función de descodificación equivalente, el principio es el mismo: las operaciones se realizan en orden inverso.

Answer 2

Eso hace (18 * 7 + 10) = 136 bits, o 17 bytes. Usted escribió trade_num es alfanumérico? Si eso significa el conjunto habitual de caracteres [a-zA-Z0-9_], entonces tendría solo 6 bits por carácter, necesitando (18 * 6 + 10) = 118 bit = 15 bytes para todo el asunto.

Suponiendo 8 bits = 1 byte

O, procedente de otra dirección: Usted tiene 128 bits de almacenamiento, lo que necesita ~ 10 bits para el número de pieza, por lo que hay 118 queda para la trade_num. 18 caracteres significa 118/18 = 6.555 bits por caracteres, esto significa que puede tener solo el espacio para codificar 2 6.555 = 94 caracteres diferentes ** a menos que haya una estructura oculta en trade_num que podamos explotar para guardar más bits.

Answer 3

Si solo puede contener letras, entonces tiene menos de 64 posibilidades por carácter (26 mayúsculas, 26 minúsculas, dejándole 12 para espacio, terminador, guión bajo, etc.). Con 6 bits por personaje, debes llegar allí, con 15 caracteres. Suponiendo que no admite caracteres especiales.

Answer 4

Puede hacerlo en ~~ 15bytes (14 bytes y 6 bits).

Para cada caracter de trace_num_ puede ahorrar 1 bit si desea guardar ascii en 7 bits.

• Entonces usted tiene 2 bytes libres y 2 bits de , debe tener 5.

Vamos a obtener información del número, cada carbón puede ser uno de los diez valores (0 a 9). Luego debes tener 4 bits para guardar este personaje, para guardar el número debes tener 1 byte y 4 bits, luego guardas la mitad de esto.

• Ahora usted tiene 3 bytes libres y 6 bits, debe tener 5.

Si desea utilizar sólo qwertyuioplkjhgfdsazxcvbnmQWERTYUIOPLKJHGFDSAZXCVBNM1234567890[] Puede guardar cada caracter en 6 bits. Luego tienes los siguientes 2 bytes y 2 bits.

• Ahora usted tienen 6 bytes a la izquierda, y la cadena se puede salvar en 15 bytes + nulltermination = 16 bytes.

Y si guarda su número en número entero en 10 bytes. Puede ajustar esto en 14 bytes y 6 bits.

Answer 5

Las preguntas claves son:

Parece haber cierta contradicción en su puesto si el número comercio es de 16 o 18 caracteres. Necesitas aclarar eso. Usted dice que el total es 21 que consiste en 16 + 3. :-(

Usted dice que los caracteres numéricos comerciales están en el rango 0x00-0x7f. ¿Pueden realmente ser cualquier carácter en ese rango, incluyendo tabulación, nueva línea, control-C, etc.? ¿O están limitados a caracteres imprimibles? ?, o tal vez incluso a alfanuméicos

¿la salida de 16 bytes tienen que ser los caracteres imprimibles, o es básicamente un número binario

EDITAR, después de cambios a post original:?

En ese caso, si la salida puede ser cualquier carácter en el conjunto de caracteres, es posible. Si solo puede ser caracteres imprimibles, no lo es.

La demostración de la posibilidad matemática es bastante simple. Hay 94 valores posibles para cada uno de los 18 caracteres, y 10 valores posibles para cada uno de 3. Número total de combinaciones posibles = 94^18 * 10^3 ~ = 3.28E35. Esto requiere 128 bits. 2^127 ~ = 1.70e38, que es demasiado pequeño, mientras que 2^128 ~ = 3.40e38, que es lo suficientemente grande. 128 bits tiene 16 bytes, por lo que apenas encajará si podemos usar todas las combinaciones de bits posibles.

Dado el ajuste, creo que la forma más práctica de generar el valor es pensarlo como un número doble largo, y luego ejecutar la entrada a través de un algoritmo para generar un entero único para cada entrada posible.

Conceptualmente, imaginemos que tenemos un tipo de datos "entero enorme" que tiene 16 bytes de longitud. El algoritmo sería algo como esto:

huge out; 
for (int p=0;p<18;++p) 
{ 
    out=out*94+tradenum[p]-32; 
} 
for (int p=0;p<3;++p) 
{ 
    out=out*10+broker[p]-'0'; 
} 

// Convert output to char[16] 
unsigned char[16] out16; 
for (int p=15;p>=0;--p) 
{ 
    out16[p]=huge&0xff; 
    huge=huge>>8; 
} 

return out16; 

Por supuesto que no tienen un "enorme" tipo de datos en C. ¿Está utilizando C o C++ puro? ¿No hay algún tipo de gran cantidad de clases en C++? Lo siento, no he hecho C++ en mucho tiempo. Si no, podríamos crear fácilmente una pequeña biblioteca para implementar una gran.

Answer 6

Utilice los primeros 10 bits para la cadena numérica de 3 caracteres (codifique los bits como si representaran un número y luego rellene con ceros, según corresponda, al decodificar).

De acuerdo, esto le deja con 118 bits y 16 caracteres alfanuméricos para almacenar.

0x00 a 0x7F (si se refiere inclusivo) comprende 128 caracteres posibles para representar. Eso significa que cada personaje puede ser identificado por una combinación de 7 bits. Propón un índice que corre cada número que esos 7 bits pueden representar para el personaje real. Para representar 16 de sus caracteres "alfanuméricos" de esta manera, necesita un total de 112 bits.

Ahora tenemos 122 bits (o 15.25 bytes) que representan nuestros datos. Agregue un huevo de Pascua para completar los bits restantes sin usar y tendrá su matriz de 16 caracteres.

Answer 7

Esto es algo que debería funcionar, suponiendo que solo necesita caracteres de allowedchars, y hay como mucho 94 caracteres allí. Esto es python, pero está escrito tratando de no usar atajos sofisticados, para que pueda traducirlo a su idioma de destino más fácilmente. Sin embargo, asume que la variable number puede contener números enteros de hasta 2 ** 128 - en C++ debe usar algún tipo de clase de números grande.

allowedchars=' !"#$%&\'()*+,-./:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}' 
alphabase = len(allowedchars) 

def compress(code): 
    alphanumeric = code[0:18] 
    number = int(code[18:21]) 

    for character in alphanumeric: 
     # find returns index of character on the allowedchars list 
     number = alphabase*number + allowedchars.find(character) 

    compressed = '' 
    for i in xrange(16): 
     compressed += chr(number % 256) 
     number = number/256 

    return compressed 

def decompress(compressed): 
    number = 0 

    for byte in reversed(compressed): 
     number = 256*number + ord(byte) 

    alphanumeric = '' 
    for i in xrange(18): 
     alphanumeric = allowedchars[number % alphabase] + alphanumeric 
     number = number/alphabase 

    # make a string padded with zeros 
    number = '%03d' % number 

    return alphanumeric + number 

Answer 8

Hay caracteres entre el espacio (0x20) y tilde (0x7E). (Las 94 en otras respuestas sufren de error de apagado-a-1).

Por lo tanto el número de ID distintos es 95 × 1000 = 3,97 .

Pero esa estructura comprimido sólo puede contener (2) = 3.40 valores distintos.

Por lo tanto, es imposible representar todos los ID de esa estructura, a menos que:

• Hay 1 carácter no utilizado en 15 o más dígitos de trade_num_, o
• Hay ≥ 14 caracteres utilizados en 1 dígito trade_num_, o
• sólo hay ≤856 corredores, o
• que utiliza es un PDP-10, que tiene una 9-bit char.