Wirklich einfache kurze String-Kompression

Question

Gibt es eine wirklich einfache Komprimierungstechnik für Zeichenketten bis zu einer Länge von etwa 255 Zeichen (ja, ich komprimiere URLs )?

Mir geht es nicht um die Stärke der Kompression - ich suche etwas, das sehr gut funktioniert und schnell zu implementieren ist. Ich möchte etwas, das einfacher ist als SharpZipLib : etwas, das mit ein paar kurzen Methoden umgesetzt werden kann.

Answer 1

Ich denke, die Schlüsselfrage lautet hier: " Warum wollen Sie URLs komprimieren? "

Versuchen Sie, lange URLs für die Adressleiste zu kürzen?

Es ist besser, die Original-URL irgendwo zu speichern (Datenbank, Textdatei ...) zusammen mit einem Hashcode des Nicht-Domain-Teils (MD5 ist in Ordnung). Sie können dann eine einfache Seite (oder ein HTTPModul, wenn Sie sich auffällig fühlen) einrichten, die den MD5-Code liest und die echte URL nachschlägt. So funktionieren TinyURL und andere.

Zum Beispiel:

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

Könnte kurzgeschlossen werden mit:

http://mydomain.com/2d4f1c8a

Die Verwendung einer Komprimierungsbibliothek wird nicht funktionieren . Die Zeichenkette wird in eine kürzere Binärdarstellung komprimiert, aber die Konvertierung dieser Zeichenkette in eine Zeichenkette, die als Teil einer URL gültig sein muss (z. B. Base64), macht alle Vorteile der Komprimierung zunichte.

Speichern Sie viele URLs im Speicher oder auf der Festplatte?

Verwenden Sie die eingebaute Komprimierungsbibliothek in System.IO.Compression oder die ZLib-Bibliothek, die einfach und unglaublich gut ist. Da Sie binäre Daten speichern werden, ist die komprimierte Ausgabe in Ordnung, so wie sie ist. Sie müssen sie dekomprimieren, um sie als URL zu verwenden.

Answer 2

Wie vorgeschlagen in die akzeptierte Antwort Die Datenkomprimierung funktioniert nicht, um URL-Pfade zu verkürzen, die bereits recht kurz sind.

DotNetZip hat eine DeflateStream-Klasse, die eine statische (Shared in VB) CompressString Methode. Es handelt sich um eine einzeilige Methode zur Komprimierung einer Zeichenkette mit DEFLATE ( RFC 1951 ). Die DEFLATE-Implementierung ist vollständig kompatibel mit System.IO.Compression.DeflateStream , aber DotNetZip komprimiert besser. Hier ist, wie Sie es verwenden können:

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

Mit diesem Code habe ich die folgenden Testergebnisse erzielt:

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

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

Sie sehen also, dass das "komprimierte" Byte-Array, wenn es in Hex dargestellt wird, länger ist als das Original, etwa doppelt so lang. Der Grund dafür ist, dass ein Hex-Byte eigentlich 2 ASCII-Zeichen sind.

Sie könnten dies etwas ausgleichen, indem Sie die Zahl zur Basis-62 anstatt zur Basis-16 (Hex) darstellen. In diesem Fall sind a-z und A-Z auch Ziffern, so dass Sie 0-9 (10) + a-z (+26) + A-Z (+26) = 62 Ziffern insgesamt erhalten. Das würde die Ausgabe erheblich verkürzen. Ich habe das noch nicht ausprobiert.

---

EDIT
Ok, ich habe den Base-62-Encoder getestet. Er verkürzt die Hex-Zeichenkette um etwa die Hälfte. Ich dachte, er würde sie auf 25% kürzen (62/16 =~ 4), aber ich glaube, ich verliere etwas durch die Diskretisierung. In meinen Tests ist die resultierende Base-62-kodierte Zeichenfolge ungefähr genauso lang wie die ursprüngliche URL. Also, nein, mit Kompression und dann Base-62-Codierung ist immer noch kein guter Ansatz. Sie wollen wirklich einen Hash-Wert.

Answer 3

Ich würde vorschlagen, in der Namespace System.IO.Compression . Es gibt ein Artikel auf CodeProject die helfen können.

Answer 4

Ich habe gerade ein Komprimierungsschema erstellt, das auf URLs abzielt und eine Komprimierung von etwa 50 % erreicht (im Vergleich zur base64-Darstellung des ursprünglichen URL-Textes).

siehe http://blog.alivate.com.au/packed-url/

---

Es wäre großartig, wenn jemand von einem großen Technologieunternehmen dies richtig ausbauen und für alle zur Verfügung stellen würde. Google hat sich für Protokollpuffer eingesetzt. Dieses Tool kann für jemanden wie Google eine Menge Speicherplatz sparen und ist dennoch durchsuchbar. Oder vielleicht der große Kapitän selbst? https://twitter.com/capnproto

Technisch gesehen würde ich dies als ein binäres (bitweises) Serialisierungsschema für die Daten bezeichnen, die einer URL zugrunde liegen. Behandeln Sie die URL als Textrepräsentation konzeptioneller Daten und serialisieren Sie dann dieses konzeptionelle Datenmodell mit einem speziellen Serialisierer. Das Ergebnis ist natürlich eine stärker komprimierte Version des Originals. Dies unterscheidet sich stark von der Funktionsweise eines allgemeinen Komprimierungsalgorithmus.

Answer 5

Was ist Ihr Ziel?

• Eine kürzere URL? Versuchen Sie es mit URL-Verkürzern wie http://tinyurl.com/ o http://is.gd/
• Speicherplatz? Schauen Sie sich System.IO.Compression an. (Oder SharpZipLib )