Compressione semplice a stringa breve

Question

Esiste una tecnica di compressione davvero semplice per stringhe con una lunghezza massima di 255 caratteri (sì, sto comprimendo URLs)?

Non mi interessa la forza della compressione: sto cercando qualcosa che funzioni molto bene e sia veloce da implementare. Vorrei qualcosa di più semplice di SharpZipLib: qualcosa che può essere implementato con un paio di metodi brevi.

Answer 1

Penso che la domanda chiave qui è "Perché si vuole comprimere gli URL?"

Cercando di abbreviare gli URL lunghi per la barra degli indirizzi?

È meglio memorizzare l'URL originale da qualche parte (database, file di testo ...) insieme a un codice hash della parte non di dominio (MD5 va bene). Puoi quindi avere una pagina semplice (o un modulo HTTP se ti senti vistosa) per leggere l'MD5 e cercare l'URL reale. Ecco come funzionano TinyURL e gli altri.

Ad esempio:

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

potrebbe subire un cortocircuito a:

http://mydomain.com/2d4f1c8a 

Utilizzo di una libreria di compressione per questo non funzionerà. La stringa verrà compressa in una rappresentazione binaria più breve, ma convertirla in una stringa che deve essere valida come parte di un URL (ad esempio Base64) annullerà qualsiasi vantaggio ottenuto dalla compressione.

Memorizzazione di molti URL in memoria o su disco?

Utilizzare la libreria di compressione integrata in System.IO.Compression o nella libreria ZLib che è semplice e incredibilmente buona. Dato che memorizzerai dati binari, l'output compresso andrà bene così com'è.Dovrai decomprimerlo per usarlo come URL.

Answer 2

Qual è il tuo obiettivo?

• Un URL più breve? Prova gli abbreviazioni URL come http://tinyurl.com/ o http://is.gd/
• Spazio di archiviazione? Controlla System.IO.Compression. (O SharpZipLib)

Answer 3

Vorrei iniziare provando una delle librerie esistenti (gratuite o open source), ad es. http://www.icsharpcode.net/OpenSource/SharpZipLib/

Zip dovrebbe funzionare bene per le stringhe di testo, e io non so se vale la pena di implementare un algoritmo di compressione yourserlf ....

Answer 4

io suggerirei di guardare in System.IO.Compression Namespace. C'è an article on CodeProject che può aiutare.

Answer 5

Hai provato a utilizzare solo gzip?

Nessuna idea se funzionasse efficacemente con stringhe così corte, ma direi che probabilmente è la soluzione migliore. biblioteca

Answer 6

L'open source SharpZipLib è facile da usare e vi fornirà strumenti di compressione

Answer 7

Come suggerito in the accepted answer, l'utilizzo della compressione dei dati non funziona per abbreviare i percorsi URL che sono già piuttosto brevi.

DotNetZip dispone di una classe DeflateStream che espone un metodo statico (Shared in VB) CompressString. È un modo a riga singola per comprimere una stringa utilizzando DEFLATE (RFC 1951). L'implementazione DEFLATE è completamente compatibile con System.IO.Compression.DeflateStream, ma DotNetZip si comprime meglio. Ecco come si potrebbe usarlo:

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

Utilizzando quel codice, qui sono i miei risultati dei test:

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

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

Così si può vedere l'array di byte "compresso", quando rappresentato in esadecimale, è più lungo l'originale, circa il doppio del tempo. Il motivo è che un byte esadecimale è in realtà 2 caratteri ASCII.

È possibile compensare un po 'per quello utilizzando la base-62, anziché la base-16 (esadecimale) per rappresentare il numero. In questo caso anche a-z e A-Z sono cifre, dandoti 0-9 (10) + a-z (+26) + A-Z (+26) = 62 cifre totali. Ciò ridurrebbe significativamente la produzione. Non l'ho provato ancora.

---

EDIT
Ok ho provato l'encoder Base-62. Accorcia la stringa esadecimale di circa la metà. Ho pensato che sarebbe tagliato al 25% (62/16 = ~ 4) Ma penso di perdere qualcosa con la discretizzazione. Nei miei test, la risultante stringa codificata in base 62 ha all'incirca la stessa lunghezza dell'URL originale. Quindi, no, usare la compressione e quindi la codifica base-62 non è ancora un buon approccio. vuoi davvero un valore hash.

Answer 8

È possibile utilizzare sgonfiare algoritmo direttamente, senza alcun checksum intestazioni o piè di pagina, come descritto in questa domanda: Python: Inflate and Deflate implementations

Questo riduce un URL 4100 personaggio a 1270 caratteri base64, nel mio test, permettendogli di adattarsi all'interno Limite 2000 di IE.

Ed ecco un esempio di 4000-character URL, che non può essere risolto con una tabella hash poiché l'applet può esistere su qualsiasi server.