Esiste una tecnica di compressione davvero semplice per stringhe con una lunghezza massima di 255 caratteri (sì, sto comprimendo URLs)?Compressione semplice a stringa breve
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.
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.
Questa non è una risposta alla domanda. Cosa succede se non hai nessun posto dove riporre l'hashtable? – endolith
@endolith - Il punto è la compressione delle stringhe non ti aiuterà in questo caso, collegandolo solo a un hash o simile. Vedi la risposta di Cheeso per le compressioni di esempio del mondo reale più lunghe e altrettanto lunghe nell'originale quando vengono convertite in URL validi. Hai sempre "da qualche parte" per memorizzare un hash. Inseriscilo nel tuo codice di reindirizzamento URL se davvero non hai "nulla" per salvarlo! – badbod99
Non si ha sempre un posto dove archiviare un hashtable e non sempre rende l'URL più lungo. http://en.wikipedia.org/wiki/Data_URI_scheme, ad esempio – endolith
Qual è il tuo obiettivo?
Non riguarda la forza di compressione - Sono cercare qualcosa che funzioni molto bene e sia veloce da implementare. Puoi indicarmi base64? – cbp
Base64 non comprime nulla :) –
@ Jon Grant: corretto. Base64 era uno stupido suggerimento. Funzionerebbe solo dopo la compressione effettiva per ottenere qualcosa che (forse) è più piccolo, ma comunque ascii. Ho rimosso ogni traccia del suggerimento. – peSHIr
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 ....
io suggerirei di guardare in System.IO.Compression Namespace. C'è an article on CodeProject che può aiutare.
Hai provato a utilizzare solo gzip?
Nessuna idea se funzionasse efficacemente con stringhe così corte, ma direi che probabilmente è la soluzione migliore. biblioteca
L'open source SharpZipLib è facile da usare e vi fornirà strumenti di compressione
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.
L'utilizzo di hex è piuttosto stupido, non è affatto un formato denso. L'uso di base64 o anche di base85 e la sostituzione dei caratteri non validi con quelli corretti (la fuga di nuovo richiede spazio) ridurrà sicuramente l'output. Non come pretendi, la tua matematica è spenta. Ovviamente, più breve è l'URI, minore è la compressione che puoi aspettarti, e conta anche quale sia il contesto. –
È 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.
Perché? C'è probabilmente un modo migliore per fare quello che stai chiedendo. –
"Perché" è sicuramente una buona risposta. Tuttavia, come nota a margine, la codifica di Huffman funziona alla grande per la semplice compressione del testo senza dover ricorrere a librerie esterne e compressione LZW. –
possibile duplicato di [Miglior algoritmo di compressione per stringhe di testo brevi] (http://stackoverflow.com/questions/1138345/best-compression-algorithm-for-short-text-strings) –