Megyjegyzés. Az már nekem is eszembe jutott, hogy ha 7 biten tárolok minden byte-ot (és a levágott 1 biteket minden 7. byte után egy külön byte-ba kiírom), akkor a probléma megoldható. Tehát olyan algoritmus kerestetik, ami ennél kisebb méretnövekedés mellett oldja meg az eredeti problémát.

Az átszámolás természetesen optimális abban az értelemben, hogy kicsit nő csak tőle az adattömeg. Én egy másik megoldást ajánlok, ami nem optimális, viszont sokkal gyorsabb, mert nem kell 1415 jegyű 256-os számrendszerbeli számokkal számolni hozzá.

Először a dekódoló algoritmust írom le, mert annak alapján egyértelmű lesz, hogy mi a csízió:

1. Vedd az első szót (16 bites számot), és vedd az egyes komplemensét. Jelöljük ezt a számot N-nel.
2. Vedd a következő N byte-ot, és másold a kimenetbe.
3. Ha nincs több dekódolandó adat, STOP.
4. Vedd a következő byte-ot, és vedd az egyes komplemensét. Jelöljük ezt a számot Z-vel.
5. Írj Z darab 0 byte-ot a kimenetbe.
6. Ha nincs több dekódolandó adat, STOP.
7. Vissza az 1. lépéshez.

Azt hiszem, a kódoló algoritmus ezek alapján egyértelmű; csak néhány finomságra hívnám fel a figyelmet:

• Ha 0-val kezdődik a bemenet, akkor az első szó 0xFFFF.
• Ha a nem-nulla sorozat hossza hexadeximálisan 0xFF00-nál több, vagy modulo-256 0xFF, akkor két darabban kell kiírni, 0xFF-fel elválasztva (ami a 0-hosszú nullsorozat kódja).

Ja, az algoritmus legrosszabbul akkor működik, ha nullák és nemnullák felváltva vannak a bemenetben. Ebben az esetben a kimenet hossza a bemenet 2,5-szöröse lesz.

Az előnye az, hogy O(0) memóriaterületet használ, és a legtöbb gépen a "másolj n összefüggő byte-ot" és az "írj n nullát" művelet nagyon gyors.

Alapvetően szép ötlet, de valami nem teljesen világos: miért célszerűbb szavakkal kódolni a nulla/nem nulla sorozatok hosszát, miért nem jók a szimpla byte-ok? Elvileg 1/256 az esélye annak, hogy jön egy nullkarakter, tehát ha byte-okon számlálok, akkor (legalábbis a hasraütés nálam azt mondja, hogy) várhatóan kevesebbszer fog előfordulni az, hogy "feleslegesen" szúrtam be számláló karaktert, mint az, hogy elhasználtam két byte-ot egy olyan számra, amit egyetlen byte-on is ábrázolhatnék. Van valami oka annak, hogy inkább szavakat kelljen használni?

A másik, amit sajnos nem értek annyira, az az egyes komplemens ábrázoláshoz kapcsolódik. Ha jól értem, azért kell a komplemenst képezni, hogy ha mondjuk valahol N=0 vagy Z=0 lenne, akkor ne nullkarakter kódolódjon. Viszont a második "finomság" sajnos nem teljesen világos, mint ahogy az sem teljesen az, hogy ha mondjuk 0xFF00 lenne egy nem-nulla sorozat hossza, akkor annak az egyes komplemense 0x00FF (ha jól értem, hogy mit jelent az egyes komplemens ábrázolás), viszont ennek a felső byte-ja nullkarakter, vagyis hibát okozna. Illetve javíts ki, ha nem így kell egyes komplemenst képezni. (Sajnos ezeket a dolgokat sosem tanították meg igazán jól, és ezeddig nem nagyon volt szükségem arra, hogy ezt tudjam, illetve mélyebben megértsem...)

Amúgy végül kiderülhet, hogy nem csak a nullkaraktereket kell kihagynom, hanem más, speciális karaktereket is (kicsit szkeptikus vagyok, hogy vajon az a program, ami felé a kimeneti adatsort kommunikálni kell, hogyan birkózik meg pl. a kocsivissza, vagy a tabulátor, meg hasonlóaknak az ASCII-karaktereivel). A közölt algoritmus szépsége, hogy a 4-5 pontok enyhe átírásával könnyen illeszthető az esetleges módosuló problémához is.

Az esetleges kíváncsiaknak leírom, hogy tulajdonképp ez az egész mihez kell. Szóval létezik egy Max nevű moduláris rendszer (a fejlesztői szeretik programozási környezetnek nevezni, de azért ez a jelző szerintem kicsit erős), úgy működik, hogy adottak előre lefordított beépülők, és ezeket lehet egymással összekombinálni (van egy nyílt forrású "klónja" PureData néven, ez fut Linuxon is – szemben a Max-szel, ami csak Macen és – nemrég óta – Winen megy). Az egész rendszer audiovizuális felhasználás céljából született, így az objektumok általában vagy valamilyen audio-, vagy videoműveletet végeznek, továbbá vannak olyan objektumok is, amik a vezérelhetőséget biztosítják (pl. kommunikáció külső MIDI eszközökkel meg ilyesmi), de tény és való, hogy a cucc kellően általános ahhoz, hogy ha az ember bármilyen modult leprogramoz magának, akkor tetszőleges célra használható (legfeljebb nem túl hatékonyan, bár tény, hogy én már pl. mérésiadat-generálásra is használtam a Max-et, de a nyilvános listákon elérhető kezdetleges web-browser, vagy python-interpreter, meg számos egyéb "finomság" is).

Az egyik ismerősöm kért meg, hogy csináljak egy olyan modult a Max-hez, ami tetszőleges beérkező üzenet(ek)et tömörít, illetve kitömörít (ugyan szerintem konkrétan arra, amit az illető szeretne csinálni, totálisan felesleges tömörítést alkalmaznia, mégis azért vállaltam be, mert a Max-et eléggé sokan használják, és hátha valakinek még szüksége lehet egy tömörítőre – bárki publikussá teheti a Max-es listákon az általa írt kiegészítőket –, szóval akár még értelme is lehet a dolognak). Magát a tömörítést az LZO algoritmussal csinálom (mivel ez nyílt forráskódú, de amúgy ide várom a kommenteket, ha bárki tud ennél jobb hatásfokú, gyors, egyszerű és ingyenes, C/C++ alatt írt tömörítőt).

Na és itt jön a probléma. A Max világában gyakorlatilag csak négy adattípus létezik (egész és lebegőpontos számok, lista és nullvégződésű karakterlánc), ezzel kell megoldani mindent. Mivel a tömörítésem végeredményét ebbe a világba kell visszaküldenem, ezért értelemszerűen nem küldhetek ki egy egyszerű bináris adathalmazt, mert az első nullánál levágná. És ami még rosszabb (ezt sajnos nem tudom biztosan, majd a próbálgatás során kiderül), nem kizárt, hogy bizonyos speciális karaktereket a Max nem fog elfogadni a karakterláncban (ez azért lehetséges, mert mivel az egyes objektumok semmit nem tudnak egymásról, ezért az objektumom kimenetének formailag olyannak kell lennie, mintha az bármilyen más tetszőleges objektumból is jöhetett volna).

Ha ezt leírtad volna, akkor sokkal kézenfekvőbb és feladatra illeszkedőbb megoldást mondtam volna neked: WikiPedia:Uuencode

Köszi a tippet. Megnéztem, de az a baj, hogy ez eléggé megnöveli az adatméretet. Ne felejtsd, elvileg az egész cuccnak az lenne a lényege, hogy tömörítőként működjön, és lehet, hogy a Max megbízhatóan átviszi az alsó harminckét ASCII kódot is (kivéve a null-t). Erről nincs rendes dokumentáció, és sajnos napközben nem lesz időm kipróbálni.

Nem hagyott nyugodni a dolog, úgyhogy kipróbáltam, szerencsére a Max megfelelően továbbítja a speciális ASCII karaktereket, így tényleg csak a nullákat kell kiszűrni. Végül annyi módosítással implementáltam az algoritmust, hogy defaultból úgy veszem, hogy az N hosszúságú blokk után mindig jön egy null karakter, így azt nem kell külön kódolni (a Z=1 esetnek ugyanis lényegesen nagyobb a valószínűsége, mint a Z > 1 esetnek, ezért várhatóan kevésbé növekszik az adatsor ezzel a feltételezéssel – hátrányba az eredetileg javasolt algoritmussal szemben akkor kerülök, ha az adatsorban sok olyan blokk van, ahol egymás utáni helyeken nulla van).

A sört megnyerted. :-)