Как сжать строку в Java? - PullRequest
Новая
       35

Как сжать строку в Java?

51 голосов
/ 06 сентября 2010

Я использую GZIPOutputStream или ZIPOutputStream для сжатия строки (my string.length() меньше 20), но сжатый результат длиннее исходной строки.

На каком-то сайте я обнаружил, что некоторые друзья говорили, что это потому, что моя исходная строка слишком короткая, GZIPOutputStream может использоваться для сжатия более длинных строк.

Итак, кто-нибудь может мне помочь сжать строку?

Моя функция похожа на: 

String compress(String original) throws Exception {

}

Обновление: 

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));
    }
}

Результат:

alt text

Ответы [ 11 ]

37 голосов
/ 06 сентября 2010

Алгоритмы сжатия почти всегда имеют некоторую форму пространственных накладных расходов, что означает, что они эффективны только при сжатии данных, достаточно больших, чтобы накладные расходы были меньше, чем количество сэкономленного пространства.

Сжать строку длиной всего 20 символов не так просто, и это не всегда возможно. Если у вас есть повторение, кодирование Хаффмана или простое кодирование длин серий может сжимать, но, вероятно, не очень.

9 голосов
/ 06 сентября 2010

Когда вы создаете строку, вы можете думать о ней как о списке символов, это означает, что для каждого символа в вашей строке вам необходимо поддерживать все возможные значения символа. От солнца документы

char : тип данных char представляет собой один 16-битный символ Unicode. Он имеет минимальное значение «\ u0000» (или 0) и максимальное значение «\ uffff» (или 65 535 включительно).

Если у вас сокращенный набор символов, которые вы хотите поддерживать, вы можете написать простой алгоритм сжатия, который аналогичен двоичному -> десятичному -> шестнадцатеричному разговору. Вы переходите с 65 536 (или сколько символов поддерживает целевая система) на 26 (алфавитный) / 36 (буквенно-цифровой) и т. Д.

Я использовал этот трюк несколько раз, например, для кодирования временных меток в виде текста (цель 36+, источник 10) - просто убедитесь, что у вас достаточно юнит-тестов!

8 голосов
/ 06 сентября 2010

Если пароли более или менее «случайны», вам не повезло, вы не сможете получить значительное уменьшение в размере.

Но: Зачем вамсжать пароли?Может быть, вам нужно не сжатие, а какое-то хеш-значение?Если вам просто нужно проверить, соответствует ли имя заданному паролю, вам не нужно сохранять пароль, но вы можете сохранить хэш пароля.Чтобы проверить, соответствует ли введенный пароль указанному имени, вы можете создать значение хеша таким же образом и сравнить его с сохраненным хешем.Поскольку хэш (Object.hashCode ()) является целым числом, вы сможете хранить все 20 хэшей паролей в 80 байтах).

6 голосов
/ 06 сентября 2010

Ваш друг прав. И gzip, и ZIP основаны на DEFLATE . Это алгоритм общего назначения, и он не предназначен для кодирования небольших строк.

Если вам это нужно, возможное решение - пользовательская кодировка и декодирование HashMap<String, String>. Это может позволить вам сделать простое сопоставление один к одному: 

HashMap<String, String> toCompressed, toUncompressed;

String compressed = toCompressed.get(uncompressed);
// ...
String uncompressed = toUncompressed.get(compressed);

Понятно, что это требует настройки и применимо только для небольшого числа строк.

4 голосов
/ 06 сентября 2010

Кодировка Хаффмана является разумным вариантом здесь.Gzip и друзья делают это, но они работают, чтобы построить дерево Хаффмана для ввода, отправить его, а затем отправить данные, закодированные с помощью дерева.Если дерево велико по отношению к данным, может не произойти сбережения по размеру.

Однако можно избежать отправки дерева: вместо этого вы договариваетесь, чтобы отправитель и получатель уже имели его.Он не может быть создан специально для каждой строки, но у вас может быть одно глобальное дерево, используемое для кодирования всех строк.Если вы строите его на том же языке, что и строки ввода (английский или любой другой), вы все равно должны получить хорошее сжатие, хотя и не так хорошо, как с настраиваемым деревом для каждого ввода.

4 голосов
/ 06 сентября 2010

Алгоритм ZIP представляет собой комбинацию LZW и Деревья Хаффмана .Вы можете использовать один из этих алгоритмов отдельно.

Сжатие основано на 2 факторах:

  • повторение подстрок в вашей исходной цепочке (LZW): если есть многоповторений, сжатие будет эффективным.Этот алгоритм обладает хорошими характеристиками для сжатия длинного простого текста, поскольку слова часто повторяются
  • количество каждого символа в сжатой цепочке (Хаффман): чем больше разбивка между символами не сбалансирована, тем больше будет эффективность сжатия

В вашем случае вам следует попробовать только алгоритм LZW.В принципе, цепочка может быть сжата без добавления метаинформации: вероятно, она лучше подходит для сжатия коротких строк.

Для алгоритма Хаффмана дерево кодирования должно отправляться со сжатым текстом.Поэтому для небольшого текста результат может быть больше исходного текста из-за дерева.

4 голосов
/ 06 сентября 2010

Кодирование Хаффмана может помочь, но только в том случае, если в вашей маленькой строке * много5 часто встречающихся символов

2 голосов
/ 08 мая 2017

Если вы знаете, что ваши строки в основном ASCII, вы можете преобразовать их в UTF-8. 

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

Это может уменьшить объем памяти примерно на 50%.Однако вы получите массив байтов, а не строку.Если вы записываете его в файл, это не должно быть проблемой.

Чтобы преобразовать обратно в строку: 

private final Charset UTF8_CHARSET = Charset.forName("UTF-8");
...
String s = new String(bytes, UTF8_CHARSET);
0 голосов
/ 07 июня 2019

Компактное улучшение строки доступно из коробки в Java 9 https://openjdk.java.net/jeps/254

java.lang.String теперь имеет:

личное конечное значение байта [];

0 голосов
/ 05 февраля 2015

Взгляните на алгоритм Хаффмана.

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

Идея состоит в том, что каждый символ заменяется последовательностью битов в зависимости от их частоты в тексте (чем чаще, чем меньше последовательность).

Вы можете прочитать весь текст и создать таблицу кодов, например:

Код символа

a 0

s 10

e 110

m 111

Алгоритм строит дерево символов на основе ввода текста.Чем больше у вас символов, тем хуже будет сжатие.

Но в зависимости от вашего текста оно может быть эффективным.

Страница:
...