Quiero tomar una cadena arbitraria de texto ASCII, como "Hola mundo", y comprimirla en una versión con menos caracteres (el menor número posible), pero de forma que pueda descomprimirse. La versión comprimida debe estar compuesta solo por caracteres ascii. ¿Hay alguna manera de lograr esto, especialmente en Ruby?¿Cómo se puede comprimir de forma reversible un poco de texto en menos caracteres ASCII?
Si sabe que solo se usarán caracteres ASCII, es decir, los 7 bits de orden inferior de cada byte. Con la manipulación de bits, puede mezclar cada 8 bytes en 7 (12.5% de ahorro). Si puede obtener un rango menor (64 caracteres válidos solamente), puede soltar otro byte.
Sin embargo, porque desea que la forma comprimida para contener a sólo caracteres ASCII, que pierde un byte - que se remonta al punto de partida a menos que su entrada puede ser restringido a 64 caracteres (por ejemplo, la compresión con pérdida sustitución de algunos caracteres con los demás , almacenando solo en minúsculas, etc.).
Si sus cadenas no son grandes (> 1k), hay un ahorro mínimo con gzip/bzip2, etc. debido al tamaño de los encabezados. Si tenía un diccionario predefinido para usar como una tabla de Huffman, puede obtener cierta compresión, pero en otros casos, puede hincharse contra el texto original.
discusión previa sobre SO An efficient compression algorithm for short text strings
La pregunta, mientras la leo, es sobre la compresión de texto donde el resultado también es de 7 bits ASCII. Eliminar el bit alto no va a funcionar como compresión en ese caso. –
Actualización notada, respuesta votada. ;) –
Hay muchos buenos algoritmos de compresión de texto como Huffman encoding o LZW que son buenos en la compresión de cadenas de texto en cadenas de bits con muchos menos bits que la codificación ASCII estándar. Una vez que tenga dicha codificación, siempre puede dividir la cadena de bits en grupos de siete bits para empacarlos en caracteres ASCII estándar. Estoy seguro de que hay bibliotecas por ahí que hacen esto, pero yo no soy muy codificador de Ruby y no conozco ninguno de los que están fuera de mi cabeza.
A menos que use una tabla Huffman fija, el tamaño de la tabla en sí probablemente se "comprimirá" en un tamaño mayor en cadenas cortas. – RichardTheKiwi
La forma más simple de hacer esto sería comprimirlo usando un algoritmo estándar, luego base64 codifica el resultado. Sin embargo, es probable que esto no ayude en una cadena tan corta como 'Hola mundo': a ese tamaño, hay muy poco que podrías hacer para disminuir el tamaño, a menos que todas tus cadenas tengan un juego de caracteres restringido similar, o patrones que como la codificación Huffman puede aprovechar.
Si su idioma es el inglés, por ejemplo, puede alejarse dejando caracteres comunes si su palabra permanece inequívoca. Por ejemplo, "Hello world" podría convertirse en "Hll wrld" si su diccionario solo contiene Hello para que coincida con Hll y world para que coincida con wrld. Los idiomas semíticos como el árabe en realidad no tienen voz en su lenguaje escrito, y la gente todavía logra leerlos. Además, otras reglas como cuando se supone que una palabra es mayúscula se pueden usar para reducir el conjunto de caracteres a caracteres en minúscula (suponiendo que un texto dado sigue estas reglas). También, aunque la compresión byte-wise funciona bien para textos, el lenguaje natural real puede comprimirse mucho mejor si codifica palabras completas, porque el tamaño del vocabulario es muy limitado (incluso más limitado si observa un conjunto restringido de textos).) Pero esa no era la pregunta, me estoy saliendo de tema aquí.
¿Desea comprimir texto en un alfabeto que se compone de 'a-zA-Z' en un alfabeto que se compone de' a-zA-Z'? No creo que eso sea posible. Para reducir la longitud, necesita aumentar los caracteres disponibles. Si su alfabeto de entrada está limitado a, por ejemplo, 'a-zA-Z' y su salida puede contener todos los 255 puntos de código ASCII, puede estar en algo ... – deceze
Cuando dice que la versión comprimida debe estar compuesta solo de ascii personajes, ¿quieres decir que los caracteres 0x00-0x19 no están permitidos? Si quitas los posibles caracteres de A-Za-z0-9, es posible que puedas obtener 5 caracteres/int.Pero ya no será una cadena ASCII, aunque – Waneck
@deceze Si no se puede hacer, los archivos binarios no se pueden comprimir (ya que ya son 8 bits). Se puede hacer, pero obtendrás una salida más corta que la entrada solo si tienes (una cantidad considerable de) repeticiones y, por lo tanto, un diccionario te ayuda. –