Comment compresser une chaîne en Java?

Les algorithmes de compression ont presque toujours une forme de surcharge d’espace, ce qui signifie qu’ils ne sont efficaces que lors de la compression de données suffisamment volumineuses pour que la surcharge soit inférieure à la quantité d’espace enregistré.

Compresser une chaîne de seulement 20 caractères n’est pas facile, et ce n’est pas toujours possible. Si vous avez des répétitions, Huffman Coding ou un simple encodage de longueur peut être compressé, mais probablement pas beaucoup.

Lorsque vous créez une chaîne, vous pouvez la considérer comme une liste de caractères, ce qui signifie que pour chaque caractère de votre chaîne, vous devez prendre en charge toutes les valeurs possibles de char. Du soleil docs

char : le type de données char est un caractère Unicode 16 bits unique. Il a une valeur minimale de ‘\ u0000’ (ou 0) et une valeur maximale de ‘\ uffff’ (ou 65,535 inclus).

Si vous souhaitez prendre en charge un ensemble réduit de caractères, vous pouvez écrire un algorithme de compression simple, analogue à la conversion binary-> décimal-> hexadécimale. Vous passez de 65 536 (ou toutefois du nombre de caractères pris en charge par votre système cible) à 26 (alphabétique) / 36 (alphanumérique), etc.

J’ai utilisé cette astuce à quelques resockets, par exemple en encodant des horodatages en tant que texte (cible 36 +, source 10) – assurez-vous simplement d’avoir de nombreux tests unitaires!

Si les mots de passe sont plus ou moins “aléatoires”, vous n’avez pas de chance, vous ne pourrez pas obtenir une réduction significative de la taille.

Mais: pourquoi avez-vous besoin de compresser les mots de passe? Peut-être que ce dont vous avez besoin n’est pas une compression, mais une sorte de valeur de hachage? Si vous avez juste besoin de vérifier si un nom correspond à un mot de passe donné, vous n’avez pas besoin d’enregistrer le mot de passe, mais vous pouvez enregistrer le hachage d’un mot de passe. Pour vérifier si un mot de passe saisi correspond à un nom donné, vous pouvez créer la valeur de hachage de la même manière et la comparer au hachage enregistré. En tant que hachage (Object.hashCode ()) est un int, vous pourrez stocker tous les 20 mots de passe dans 80 octets).

Votre ami a raison Gzip et ZIP sont tous deux basés sur DEFLATE . Ceci est un algorithme à usage général, et n’est pas destiné à coder de petites chaînes.

Si vous en avez besoin, une solution possible est un codage et un décodage personnalisés HashMap . Cela peut vous permettre de faire un mappage simple:

 HashMap toCompressed, toUncompressed; Ssortingng compressed = toCompressed.get(uncompressed); // ... Ssortingng uncompressed = toUncompressed.get(compressed); 

De toute évidence, cela nécessite une configuration et n’est pratique que pour un petit nombre de chaînes.

Huffman Coding pourrait vous aider, mais seulement si vous avez beaucoup de personnages fréquents dans votre petite chaîne.

L’algorithme ZIP est une combinaison de LZW et de Huffman Trees . Vous pouvez utiliser l’un de ces algorithmes séparément.

La compression est basée sur 2 facteurs:

• la répétition de sous-chaînes dans votre chaîne d’origine (LZW): s’il y a beaucoup de répétitions, la compression sera efficace. Cet algorithme a de bonnes performances pour compresser un texte en clair, car les mots sont souvent répétés
• le numéro de chaque caractère de la chaîne compressée (Huffman): plus la répartition entre les caractères est déséquilibrée, plus la compression sera efficace

Dans votre cas, vous ne devriez essayer que l’algorithme LZW. Utilisée à la base, la chaîne peut être compressée sans append de méta-informations: c’est probablement mieux pour la compression de courtes chaînes.

Pour l’algorithme de Huffman, l’arbre de codage doit être envoyé avec le texte compressé. Donc, pour un petit texte, le résultat peut être plus grand que le texte original, à cause de l’arbre.

Le codage Huffman est une option judicieuse ici. Gzip et ses amis le font, mais la façon dont ils fonctionnent est de construire une arborescence Huffman pour l’entrée, de l’envoyer, puis d’envoyer les données encodées avec l’arborescence. Si l’arborescence est volumineuse par rapport aux données, il se peut que la taille ne soit pas économisée.

Cependant, il est possible d’éviter l’envoi d’un arbre: à la place, vous vous assurez que l’expéditeur et le destinataire en ont déjà un. Il ne peut pas être construit spécifiquement pour chaque chaîne, mais vous pouvez avoir un seul arbre global utilisé pour encoder toutes les chaînes. Si vous le construisez à partir du même langage que les chaînes d’entrée (en anglais ou autre), vous devriez toujours avoir une bonne compression, même si elle n’est pas aussi bonne qu’avec une arborescence personnalisée pour chaque entrée.

Si vous savez que vos chaînes sont principalement en ASCII, vous pouvez les convertir en UTF-8.

 byte[] bytes = ssortingng.getBytes("UTF-8"); 

Cela peut réduire la taille de la mémoire d’environ 50%. Cependant, vous obtiendrez un tableau d’octets et non une chaîne. Si vous l’écrivez dans un fichier, cela ne devrait pas poser de problème.

Pour reconvertir en chaîne:

 private final Charset UTF8_CHARSET = Charset.forName("UTF-8"); ... Ssortingng s = new Ssortingng(bytes, UTF8_CHARSET); 

Vous ne voyez pas de compression se produire pour votre chaîne, car vous avez au moins deux cents octets pour avoir une compression réelle à l’aide de GZIPOutputStream ou ZIPOutputStream. Votre chaîne est trop petite (je ne comprends pas pourquoi vous avez besoin de la même compression)

Vérifiez la conclusion de cet article :

L’article montre également comment compresser et décompresser les données à la volée afin de réduire le trafic réseau et d’améliorer les performances de vos applications client / serveur. La compression des données à la volée améliore toutefois les performances des applications client / serveur uniquement lorsque les objects compressés dépassent quelques centaines d’octets. Vous ne pourriez pas observer d’amélioration des performances si les objects compressés et transférés sont des objects Ssortingng simples, par exemple.

Jetez un coup d’œil à l’algorithme de Huffman.

https://codereview.stackexchange.com/questions/44473/huffman-code-implementation

L’idée est que chaque caractère est remplacé par une séquence de bits, en fonction de leur fréquence dans le texte (le plus fréquent, plus la séquence est petite).

Vous pouvez lire l’intégralité de votre texte et créer une table de codes, par exemple:

Code de symbole

un 0

s 10

e 110

m 111

L’algorithme construit un arbre de symboles basé sur la saisie de texte. La plus grande variété de caractères que vous avez, le pire de la compression sera.

Mais selon votre texte, cela pourrait être efficace.