Olyan algoritmus kerestetik (a honorárium legyen mondjuk egy sör), amelyik lehetőleg gyorsan fut, és egy adott (véletlenszerűen generált) memóriaterületet átkódol úgy, hogy biztosan ne forduljon elő benne 0 értékű byte (és hogy az átkódolt adatból az eredetit egyértelműen vissza lehessen fejteni), mindezt minimális méretnövekedés mellett.

Ami eddig eszembe jutott az az, hogy a memóriaterületet felbontom 1415 byte-os* blokkokra, majd az így kapott (256 alapú számrendszerben) 1415 jegyű számokat átírom 255-alapú számrendszerbeli számokra, végül az így kapott szám mindegyik számjegyéhez hozzáadok 1-et. Így egy legfeljebb (256-alapú számrendszerben) 1416 jegyű számot kapok, ezt eltárolom egy 1416 byte-os blokkban, és készen vagyok. A visszafejtés nyilván egyértelmű, és így csak 1/1416-oddal nő meg az eredeti adatmennyiség, ami nem egy túl nagy növekedés.

Ha esetleg valaki tud arra jó algoritmust, hogy hogyan lehet egy nagyméretű számot az egyik számrendszerből a másikba konvertálni, már azzal is irtó sokat segítenétek. Köszi!


* Azért pont 1415-jegyű számok, mert az (n+1) alapú számrendszerben k helyiértéken összesen (n+1)k szám tárolható. Ha szeretném megtalálni azt a legnagyobb k-t, amire az n alapú számrendszerben biztosan elég (k+1) helyiértéket használnom az előbbi szám tárolására, akkor a nk+1 ≥ (n+1)k feltételnek eleget tevő legynagyobb k-t kell megadni. n = 255 esetén (hacsak el nem számoltam) kmax = 1415.
Utoljára módosította SAdam 2009.III.07 17:51-n
Bejegyzés módosítása | PermaLink
Votes disabled.

Hozzászólások (8)

SAdam hozzászólása 2009-03-07 20:48-kor

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.


UPi hozzászólása 2009-03-07 21:04-kor

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).

UPi hozzászólása 2009-03-07 21:11-kor

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.


SAdam hozzászólása 2009-03-08 01:59-kor

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.


SAdam hozzászólása 2009-03-08 02:26-kor

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).


UPi hozzászólása 2009-03-08 08:55-kor

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


SAdam hozzászólása 2009-03-08 10:04-kor

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.


SAdam hozzászólása 2009-03-08 11:41-kor

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. :-)

Tagek: