Действительно простое сжатие коротких строк

Существует ли действительно простая техника сжатия строк длиной до 255 символов (да, я сжимаю URL-адреса)?

Меня не интересует сила сжатия - я ищу что-то, что работает очень хорошо и быстро реализуется. Я хотел бы что-то более простое, чем SharpZipLib: что-то, что может быть реализовано с помощью нескольких коротких методов.

Источник

9 ответов

Решение

Я думаю, что ключевой вопрос здесь: "Почему вы хотите сжать URL-адреса?"

Пытаетесь сократить длинные URL-адреса для адресной строки?

Вам лучше хранить исходный URL где-нибудь (база данных, текстовый файл...) вместе с хеш-кодом не доменной части (MD5 в порядке). После этого вы можете создать простую страницу (или какой-нибудь HTTPModule, если вы чувствуете себя кричащим), чтобы прочитать MD5 и найти реальный URL. Так работают TinyURL и другие.

Например:

http://mydomain.com/folder1/folder2/page1.aspx

Может быть закорочен на:

http://mydomain.com/2d4f1c8a

Использование библиотеки сжатия для этого не будет работать. Строка будет сжата в более короткое двоичное представление, но преобразование ее обратно в строку, которая должна быть действительной как часть URL-адреса (например, Base64), сведет на нет все преимущества, которые вы получили от сжатия.

Хранить много URL-адресов в памяти или на диске?

Используйте встроенную библиотеку сжатия в System.IO.Compression или библиотеку ZLib, которая проста и невероятно хороша. Поскольку вы будете хранить двоичные данные, сжатый вывод будет в порядке как есть. Вам нужно будет распаковать его, чтобы использовать его в качестве URL.

Источник

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

DotNetZip имеет класс DeflateStream, который предоставляет статический метод (Shared in VB) CompressString. Это однострочный способ сжатия строки с использованием DEFLATE ( RFC 1951). Реализация DEFLATE полностью совместима с System.IO.Compression.DeflateStream, но DotNetZip сжимает лучше. Вот как вы можете использовать это:

string[] orig = {
    "folder1/folder2/page1.aspx",
    "folderBB/folderAA/page2.aspx",
};
public void Run()
{
    foreach (string s in orig)
    {
        System.Console.WriteLine("original    : {0}", s);
        byte[] compressed = DeflateStream.CompressString(s);
        System.Console.WriteLine("compressed  : {0}", ByteArrayToHexString(compressed));
        string uncompressed = DeflateStream.UncompressString(compressed);
        System.Console.WriteLine("uncompressed: {0}\n", uncompressed);
    }
}

Используя этот код, вот мои результаты теста:

original    : folder1/folder2/page1.aspx
compressed  : 4bcbcf49492d32d44f03d346fa0589e9a9867a89c5051500
uncompressed: folder1/folder2/page1.aspx

original    : folderBB/folderAA/page2.aspx
compressed  : 4bcbcf49492d7272d24f03331c1df50b12d3538df4128b0b2a00
uncompressed: folderBB/folderAA/page2.aspx

Таким образом, вы можете увидеть, что сжатый байтовый массив, представленный в шестнадцатеричном формате, длиннее исходного, примерно в 2 раза длиннее. Причина в том, что шестнадцатеричный байт - это на самом деле 2 символа ASCII.

Вы могли бы несколько компенсировать это, используя base-62 вместо base-16 (hex) для представления числа. В этом случае az и AZ также являются цифрами, давая вам 0-9 (10) + az (+26) + AZ (+26) = 62 цифры. Это значительно сократило бы результат. Я не пробовал это. еще.

РЕДАКТИРОВАТЬ
Хорошо, я тестировал энкодер Base-62. Сокращает шестнадцатеричную строку примерно вдвое. Я полагал, что это сократит его до 25% (62/16 =~ 4), но я думаю, что теряю что-то с дискретизацией. В моих тестах результирующая строка в кодировке base-62 имеет ту же длину, что и исходный URL. Так что нет, использование сжатия, а затем кодирования base-62 все еще не очень хороший подход. Вы действительно хотите хэш-значение.

Источник

Я бы посоветовал поискать в пространстве имен System.IO.Compression. На CodeProject есть статья, которая может помочь.

Источник

Я только что создал схему сжатия, которая нацелена на URL и обеспечивает сжатие около 50% (по сравнению с представлением base64 исходного текста URL).

см. http://blog.alivate.com.au/packed-url/

Источник

Какова твоя цель?

  • Более короткий URL? Попробуйте сократить URL-адреса, например http://tinyurl.com/ или http://is.gd/
  • Место для хранения? Проверьте System.IO.Compression. (Или SharpZipLib)
Источник

Вы можете использовать алгоритм deflate напрямую, без каких-либо контрольных сумм или нижних колонтитулов, как описано в этом вопросе: Python: реализации Inflate и Deflate

В моем тесте это сокращает URL-адрес 4100 символов до 1270 символов base64, что позволяет ему соответствовать пределу 2000 IE.

И вот пример 4000-символьного URL, который не может быть решен с помощью хеш-таблицы, поскольку апплет может существовать на любом сервере.

Источник

Я бы начал с того, чтобы попробовать одну из существующих (бесплатных или открытых) zip-библиотек, например, http://www.icsharpcode.net/OpenSource/SharpZipLib/

Zip должен хорошо работать для текстовых строк, и я не уверен, стоит ли реализовывать алгоритм сжатия yourserlf....

Источник

Библиотека с открытым исходным кодом SharpZipLib проста в использовании и предоставит вам инструменты сжатия

Источник

Вы пробовали просто использовать gzip?

Не знаю, будет ли это эффективно работать с такими короткими струнами, но я бы сказал, что это, вероятно, ваш лучший выбор.

Источник
Другие вопросы по тегам