Hoe een string in Java comprimeren?

Ik gebruik GZIPOutputStreamof ZIPOutputStreamom een ​​string te comprimeren (mijn string.length()is kleiner dan 20), maar het gecomprimeerde resultaat is langer dan de originele string.

Op een site vond ik dat een paar vrienden zeiden dat dit komt omdat mijn originele string te kort is, GZIPOutputStreamkan worden gebruikt om langere strings te comprimeren.

dus, kan iemand me helpen om een ​​string te comprimeren?

Mijn functie is als:

String compress(String original) throws Exception {
}

Bijwerken:

import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.util.zip.GZIPOutputStream;
import java.util.zip.*;
//ZipUtil 
public class ZipUtil {
    public static String compress(String str) {
        if (str == null || str.length() == 0) {
            return str;
        }
        ByteArrayOutputStream out = new ByteArrayOutputStream();
        GZIPOutputStream gzip = new GZIPOutputStream(out);
        gzip.write(str.getBytes());
        gzip.close();
        return out.toString("ISO-8859-1");
    }
    public static void main(String[] args) throws IOException {
        String string = "admin";
        System.out.println("after compress:");
        System.out.println(ZipUtil.compress(string));
    }
}

Het resultaat is:

alt-tekst


Antwoord 1, autoriteit 100%

Compressie-algoritmen hebben bijna altijd een vorm van ruimteoverhead, wat betekent dat ze alleen effectief zijn bij het comprimeren van gegevens die zo groot zijn dat de overhead kleiner is dan de hoeveelheid bespaarde ruimte.

Het comprimeren van een string die slechts 20 tekens lang is, is niet zo eenvoudig en niet altijd mogelijk. Als je herhalingen hebt, kan Huffman Coding of eenvoudige run-length codering misschien comprimeren, maar waarschijnlijk niet veel.


Antwoord 2, autoriteit 24%

Als je een String maakt, kun je het zien als een lijst met char’s, dit betekent dat je voor elk karakter in je String alle mogelijke waarden van char moet ondersteunen. Van de zon docs

char: het char-gegevenstype is een enkel 16-bits Unicode-teken. Het heeft een minimale waarde van ‘\u0000’ (of 0) en een maximale waarde van ‘\uffff’ (of 65.535 inclusief).

Als je een beperkte set tekens hebt die je wilt ondersteunen, kun je een eenvoudig compressie-algoritme schrijven, dat analoog is aan binaire->decimaal->hex radix-conversie. Je gaat van 65.536 (of hoeveel tekens je doelsysteem ook ondersteunt) naar 26 (alfabetisch) / 36 (alfanumeriek) enz.

Ik heb deze truc een paar keer gebruikt, bijvoorbeeld het coderen van tijdstempels als tekst (target 36+, source 10) – zorg er wel voor dat je voldoende unit-tests hebt!


Antwoord 3, autoriteit 20%

Als de wachtwoorden min of meer “willekeurig” zijn, heeft u pech, u kunt de grootte niet significant verkleinen.

Maar:Waarom moet u de wachtwoorden comprimeren? Misschien heb je geen compressie nodig, maar een soort hashwaarde? Als u alleen wilt controleren of een naam overeenkomt met een bepaald wachtwoord, hoeft u het wachtwoord niet op te slaan, maar kunt u de hash van een wachtwoord opslaan. Om te controleren of een ingetypt wachtwoord overeenkomt met een bepaalde naam, kunt u de hash-waarde op dezelfde manier opbouwen en vergelijken met de opgeslagen hash. Omdat een hash (Object.hashCode()) een int is, kun je alle 20 wachtwoord-hashes in 80 bytes opslaan.


Antwoord 4, autoriteit 15%

Je vriend heeft gelijk. Zowel gzip als ZIP zijn gebaseerd op DEFLATE. Dit is een algoritme voor algemene doeleinden en is niet bedoeld voor het coderen van kleine tekenreeksen.

Als je dit nodig hebt, is een mogelijke oplossing een aangepaste codering en decodering van HashMap<String, String>. Dit kan u toelaten om een ​​eenvoudige één-op-één mapping te doen:

HashMap<String, String> toCompressed, toUncompressed;
String compressed = toCompressed.get(uncompressed);
// ...
String uncompressed = toUncompressed.get(compressed);

Het is duidelijk dat dit installatie vereist en alleen praktisch is voor een klein aantal strings.


Antwoord 5, autoriteit 10%

Huffman Codingkan helpen, maar alleen als u veel voorkomende tekens in je kleine string


Antwoord 6, autoriteit 10%

Het ZIP-algoritme is een combinatie van LZWen Huffman Trees. U kunt een van deze algoritmen afzonderlijk gebruiken.

De compressie is gebaseerd op 2 factoren:

  • de herhaling van substrings in je originele keten (LZW): als er veel herhalingen zijn, zal de compressie efficiënt zijn. Dit algoritme heeft goede prestaties voor het comprimeren van lange platte tekst, aangezien woorden vaak worden herhaald
  • het aantal van elk teken in de gecomprimeerde keten (Huffman): hoe meer de verdeling tussen tekens onevenwichtig is, hoe efficiënter de compressie zal zijn

In jouw geval moet je alleen het LZW-algoritme proberen. In principe gebruikt, kan de keten worden gecomprimeerd zonder meta-informatie toe te voegen: het is waarschijnlijk beter voor compressie van korte strings.

Voor het Huffman-algoritme moet de coderingsstructuur worden meegestuurd met de gecomprimeerde tekst. Dus voor een kleine tekst kan het resultaat vanwege de boom groter zijn dan de originele tekst.


Antwoord 7, autoriteit 10%

Huffman-codering is hier een verstandige optie. Gzip en vrienden doen dit, maar de manier waarop ze werken is om een ​​Huffman-boom voor de invoer te bouwen, die te verzenden en vervolgens de gegevens te verzenden die met de boom zijn gecodeerd. Als de boom groot is in verhouding tot de gegevens, kan er geen niet worden opgeslagen in grootte.

Het is echter mogelijk om het verzenden van een boom te vermijden: in plaats daarvan regelt u dat de zender en ontvanger er al een hebben. Het kan niet specifiek voor elke tekenreeks worden gebouwd, maar u kunt een enkele globale boomstructuur gebruiken om alle tekenreeksen te coderen. Als je het bouwt vanuit dezelfde taal als de invoerstrings (Engels of wat dan ook), zou je nog steeds een goede compressie moeten krijgen, hoewel niet zo goed als met een aangepaste boomstructuur voor elke invoer.


Antwoord 8, autoriteit 5%

Als je weet dat je strings voornamelijk ASCII zijn, kun je ze converteren naar UTF-8.

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

Dit kan de geheugencapaciteit met ongeveer 50% verminderen. U krijgt echter een bytearray en geen string. Als je het echter naar een bestand schrijft, zou dat geen probleem moeten zijn.

Om terug te converteren naar een string:

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

Antwoord 9

Je ziet geen compressie voor je String, aangezien je op zijn minst een paar honderd bytes nodig hebt om echte compressie te hebben met GZIPOutputStream of ZIPOutputStream. Je string is te klein. (Ik begrijp niet waarom je daarvoor compressie nodig hebt)

Controleer de conclusie van dit artikel:

Het artikel laat ook zien hoe te comprimeren
en decomprimeer gegevens on-the-fly in
om het netwerkverkeer te verminderen en
verbeter de prestaties van uw
client/server-toepassingen.
Gegevens on-the-fly comprimeren, maar
verbetert de prestaties van
client/server-applicaties alleen wanneer:
de objecten die worden gecomprimeerd zijn meer
dan een paar honderd bytes. Jij
zou niet kunnen observeren
prestatieverbetering als de
objecten die worden gecomprimeerd en
overgedragen zijn eenvoudige String-objecten,
bijvoorbeeld.


Antwoord 10

Bekijk het Huffman-algoritme.

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

Het idee is dat elk teken wordt vervangen door een reeks bits, afhankelijk van hun frequentie in de tekst (hoe vaker, hoe kleiner de reeks).

Je kunt je hele tekst lezen en een tabel met codes maken, bijvoorbeeld:

Symboolcode

een 0

s 10

e 110

m 111

Het algoritme bouwt een symboolboom op basis van de tekstinvoer. Hoe meer verschillende karakters je hebt, hoe slechter de compressie zal zijn.

Maar afhankelijk van je tekst kan het effectief zijn.

Other episodes