Подтвердить что ты не робот

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

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

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

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

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

String compress(String original) throws Exception {

}

Update:

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

4b9b3361

Ответ 1

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

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

Ответ 2

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

char. Тип данных char - это один 16-разрядный символ Юникода. Он имеет минимальное значение '\ u0000' (или 0) и максимальное значение '\ uffff' (или 65535 включительно).

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

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

Ответ 3

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

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

Ответ 4

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

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

HashMap<String, String> toCompressed, toUncompressed;

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

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

Ответ 5

Huffman Coding может помочь, но только если у вас много частых символов в вашей маленькой String

Ответ 6

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

Сжатие основывается на двух факторах:

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

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

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

Ответ 7

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

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

Ответ 8

Если вы знаете, что ваши строки в основном 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);

Ответ 9

Вы не видите никакого сжатия для своей строки. Поскольку вам по крайней мере требуется несколько сотен байт для реального сжатия с использованием GZIPOutputStream или ZIPOutputStream. Ваша строка слишком мала (я не понимаю, зачем вам требуется сжатие для нее)

Завершите вывод из этого article:

В статье также показано, как сжимать и распаковывать данные "на лету" для снижения сетевого трафика и улучшить производительность вашего клиент/сервер приложений. Однако сжатие данных на лету, улучшает производительность клиент/сервер, только когда сжимаемые объекты больше чем пара сотен байт. Вы не сможет наблюдать повышение эффективности, если объекты, сжимаемые и переданы простые объекты String, например.

Ответ 10

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

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

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

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

Символьный код

a 0

s 10

e 110

m 111

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

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

Ответ 11

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

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

закрытое окончательное значение byte [];