Komprimering via primtalsfaktorisering?

Utan att egentligen veta vad primtalsfaktorering handlar om eller vad su egentligen föreslår så kan jag med säkerhet säga: Du är totalt ute och cyklar. Du kan aldrig göra en komprimering som är effektiv oavsett indata. All komprimering bygger på att indatat har någon form av återupprepningar, förutsägbarhet, eller mönster.

Du kan altså aldrig göra en algoritm som komprimerar oavsett data. Om din ide skulle ha den egenskapen så kommer den inte hålla. Det är som när man har lyckats komma fram till en evighetsmaskin.När vi ndå är inne på ämnet kan jag också tipsa om att man aldrig kan slå odds som är emot en. Med andra ord så kan man aldrig långsiktigt vinna på roulette.

Om man resonerade på detta sätt så skulle man ju kunna komprimera data rekursivt, dvs när du fått ihop en gigabyte med komprimerad data så är det ju bara att köra komprimeringen igen för att få det till ett antal bytes. Då skulle man kunna säga att all data som någonsin kommer finnas skulle kunna representeras med ett antal bytes, vilket är omöjligt.

Visst skulle man på något sätt kunna utnyttja primtalsfaktorisering till komprimering, men inte i närheten av sådana komprimeringsgrader.

En liknande sak var uppe i en tråd för ett tag sen, om att använda en slumptalsgenerator för att komprimera data och endast spara seeden:
http://forum.sweclockers.com/showthread.php?s=&threadid=49279...

Här är en bra sida där det står varför det inte fungerar:

http://www.dogma.net/markn/FAQ.html#Q19

Hur gör man med talet 231 då? 231/255=~0.9. Ska man då låta biten vara ettställd 90% av tiden och nollställd resten?
Eller ska man dividera med 231 så 231/231=1, då gäller det bara att komma ihåg att man diverade med 231 där..
Eller är det jag som är inte fattar vad du menar.. hehe
Eller betyder denna något..
*edit2*
Syftade du på ex att 1472 går att skriva som 46 *32? Men att bara spara talen 46=0b101110och 32=0b100000, tar mer plats än talet 1472=0b10111000000.

*edit*
cochese: Jag har också funderat lite smått om komprimering med hjälp av vanlig matematik. Men som problemet ser ut idag så det prestandan som är den mest kritisk vid våra datorer.

cochese: Du kan ju testa o köra din komprimeringsalgoritm på alla tal mellan 10 och 99, eller mellan 1000 och 1099, då borde du märka problemet själv tror jag.

Man kan ju komprimera det oändligt långa talet PI till:
pi = summan mellan i=0 oo ( 1/(16^i) * ( 4/(8i + 1) - 2/(8i + 4) - 1/(8i + 5) - 1/(8i + 6) )

(Bailey-Borwein-Plouffes algoritm)

Det kallar jag bra komprimering..

Om stor == oändlig så håller jag med, om det inte vore för 0 och 00 vill säga, observera också att man aldrig går i mer vinst än grundinsatsen:
1 :1
12 :3
124 :7
1248 :15
Säg att vi vinner på 16, då har du satsat totalt 15 och vunnit 16. 16-15=1.

Klart man kan vinna långsiktigt på roulette. Bara man har en otrolig tur. Naturligtvis är det förväntade värdet mindre än noll, men det innebär inte att man förlorar bara för att man spelar i oändligheten.

TechGuru, han hade en idé om att göra om det till decimal form först.
Alltså ta ett program fil på 1 MegaByte och tänker det som ett enda binärt tal, gör till decimal form och "trixar" med det där.
I decimal form blir ju talet från ungefär 2 till 90 gånger större om man lägger till en valfri siffra framför och det kan man väl utnyttja (kanske?).
Jag vill försvarar inte teorin men ville bara påpeka det som du missade tror jag.

Precis Aqualize, finns ju inget som säger att man måste hålla sig till ints, bytes mm. Jag kan lätt tänka ut ett talsystem som förutom en fast overhead ökar med 1 bit per tal. Blir såklart väldigt ineffektivt för små tal, men för stora så skulle det funka bra om det var bytes-representationen som var problemet.

cochese: Det lättaste sättet o se att det inte funkar är att tänka på hur den ska veta vilket tal den ska dekomprimera till. Låt säga att du har komprimerat en hög filer, där varje kombination av 10^100 1or o 0or är i var sin fil. Nu kommer själva problemet, nämligen att din komprimering gjort filerna lite mindre. Men hur har det gått till? Eftersom filerna är mindre så får inte alla kombinationer av 1or o 0or längre plats, vilket betyder att några av filerna nu ser identiska ut. Alltså skiter det sig

Ett litet exempel på alla kombinationer för 2 bitar:
11
01
10
00

Det går inte o spara alla kombinationerna med mindre än 2 bitar, eftersom det bara finns 2 olika kombinationer av 1 bit (1 o 0), men 4 för 2 bitar.

En grundläggande tanke i informationsteorin är att man bara måste sända (i det här fallet spara på disk och 'sända' till framtiden) det man inte redan känner till på andra sidan.
Att byta talbas är ingen komprimering, bara ett annat sätt att representera samma information. Till exempel kan man gå från binär till hexadecimal form och därmed "korta" av datat till 1/4, fast det är ganska lätt att inse att ingen egentlig komprimering har skett.

Om du skulle ge mig talet 2^30*3^11 och be mig komprimera det så skulle det inte vara några problem, jag slänger bort talet och använda 0 byte av mitt dyrbara minne. Sen när du kommer nästa gång och ber mig hämta talet du bad mig komprimera så frågar jag dig, vilket tal? Och du svarar 2^30*3^11. Då kan jag komprimera upp talet utan att ha använt något utrymme alls, eftersom du redan visste vilket tal som låg där. Snacka om komprimering va

Det finns en (bevisat) optimal algoritm för förlustfri komprimering, Huffmann-algoritmen. Den är lätt att förstå och det finns en himla massa sidor på tha Internet att titta på.

Huffman kodning eller har Huffman hittat på flera?
Jag känner till den men är den generellt optimal för godtycklig data. Men det borde väl finnas specialfall där annan kodning kan vara bättre? Typ om symbolerna har exakt lika frekvens.

Uppenbarligen, annars skulle ju inte PNG och Flac göra någon nytta, vi skulle kunna använda huffman för allt?

Ja, men det är ju det vi gör nästan

PNG använder deflate vilket i sin tur är en kombination av LZ77 och huffman:

DEFLATE is a lossless data compression algorithm that uses a combination of the LZ77 algorithm and Huffman coding. It was originally defined by Phil Katz for version 2 of his PKZIP archiving tool, and was later specified in RFC 1951.

http://en.wikipedia.org/wiki/DEFLATE_%28algorithm%29

FLAC:

... To do this, FLAC takes advantage of the fact that the error signal generally has a Laplacian (two-sided geometric) distribution, and that there are a set of special Huffman codes called Rice codes that can be used to efficiently encode these kind of signals quickly and without needing a dictionary.

http://flac.sourceforge.net/documentation.html#format

TechGuru: Ok, kanske inte formulerade mig så bra ser jag nu, om det alls var rätt tänkt Det jag menade var att man talsystemet inte spelar ngn roll (utan att jag testade om det skulle bli längre i just det här fallet med bytes). Låt säga att du gör komprimeringen på papper istället, om man har 1-9 samt "mellanslag" som sina tecken, och det kommer ändå inte hjälpa oavsett vilken komprimeringsalgo du använder. Aja, vi är uppenbarligen överens om att det inte funkar i vilket fall

Aqualize: Nej,
http://en.wikipedia.org/wiki/Huffman_coding
"Huffman coding is optimal when the probability of each input symbol is a negative power of two"

Nu har jag inte läst allt, men ganska många tal är ju faktiskt primtal, dem kan du ju inte komprimera alls med denna "algoritmen".