Chcę napisać program, który w założniu ma skrócić dowolny łańcuch znakowy do krótszej postaci, o minimum 1 znak. Jaki rodzaj kompresji jest najefektywniejszy. Chodzi mi o taki rodzaj kompresji w którym zachowam kontekst łańcucha i zmniejszę jego faktyczną długość o jak najwięcej. Dodam że łańcuch może składać się tylko z dużych liter alfabetu łacińskiego. Implementacja w C++
0
0
Nie wydaje mi się, żeby istniał algorytm, który zagwarantuje, że skompresowane dane będą na pewno (za każdym razem) mniejsze. Z pewnością nie istnieje taki algorytm dla każdych danych, być może istnieje taki dla tekstu, jako dla konkretnych danych. Poczytaj tutaj: http://matt.might.net/articles/why-infinite-or-guaranteed-file-compression-is-impossible/
O kompresji zacznij czytać tutaj: http://en.wikipedia.org/wiki/Lossless_data_compression albo zaczekaj aż wypowie się @Wibowit, on się na tym zna.
0
Przy założeniu że rozkład prawdopodobieństwa występowania symboli jest różny to wystarczy ci kodowanie huffmana.
0
Dokładnie. Nie ma algorytmu, który skompresowałby wszystko. Krótki dowód jest na http://mattmahoney.net/dc/dce.html#Section_11 :
This is proved by the counting argument. Suppose there were a compression algorithm that could compress all strings of at least a certain size, say, n bits. There are exactly 2n different binary strings of length n. A universal compressor would have to encode each input differently. Otherwise, if two inputs compressed to the same output, then the decompresser would not be able to decompress that output correctly. However there are only 2n - 1 binary strings shorter than n bits.
Poza tym można zaargumentować inaczej (i prościej):
Jeżeli mielibyśmy algorytm, który kompresowałby wszystko co ma więcej niż n bitów, to w szczególności byłby w stanie skompresować wszystko do n bitów.
Mówiąc bardziej obrazowo: jeśli algorytm byłby w stanie skompresować wszystko co nie zmieści się na dyskietkę, to w szczególności mógłby skompresować cały Internet tak aby zmieścił się na dyskietce.
0
letterB0MB napisał(a):
łańcuch może składać się tylko z dużych liter alfabetu łacińskiego
W takim razie potrzebujesz 26 różnych wartości na znak czyli można to zmieścić na 5 bitach zamiast na 8. Czyli każdy taki łańcuch powyżej 2 znaków da się w ten sposób skrócić o przynajmniej 1 bajt.