Redundancia

Redundanciaazinformációelméletbenaz információ- vagy üzenetátvitelre használt csatornán maximálisanegyszerre átvihetőbitek számának és azaktuálisinformáció vagy üzenet bitjei számának akülönbsége.Azadattömörítésegy lehetséges mód a nem kívántredundanciacsökkentésére, a különféleellenőrzőösszegekpedighibajavításcéljából növelik a redundanciát, ha az átvitel egyzajos csatornán folyik, ahol a zaj csökkenti az átvitelikapacitást.

Aredundancia(lat.)nyelvtudományifogalma; a közlésben az egyértelmű megértéshez elegendő minimumon felüli, ezért fölösleges többlet. Terjengős kifejezések alkalmazása egyszerűbb szavak helyett, pl. javasol - javaslatot tesz. Előfordul, hogy van jelentésbeli vagy stilisztikai funkciója, pl. az ellentét kifejezője egyszersmind archaizáló.

Mennyiségi meghatározása

Azinformációelméletszerint egy információ forrásrátája(a legáltalánosabb esetben)

$r=\mathbb {E} H(M_{t}|M_{t-1},M_{t-2},M_{t-3},\cdots ),$

ami az üzenet várt, vagy átlagos, feltételes üzenetenkénti entrópiáját ( időegységre eső) adja az előző üzenetek vonatkozásában. Ismert az információelméletből, hogy egy nyelvnek is létezik "rátája" vagy "entrópiája". Egyemlékezetnélküli forrás rátája egyszerűen$H(M)$,ami a definíció alapján azt jelenti, hogy nincsen kapcsolat az egymást követő üzenetek között egy emlékezet nélküli forrás esetén.

Egy nyelv vagy forrásabszolút rátájaegyszerűen

$R=\log |M|,\,$

az üzenet tér (például ábécé)számosságánaklogaritmusa.Ez az üzenet maximális valószínűségi rátája, ha az adott ábécét használva küldjük el. Az abszolút ráta akkor, és csakis akkor egyezik meg a rátával, ha a forrás emlékezet nélküli és egyenletes eloszlású.

Aredundanciatehát meghatározható, mint

$D=R-r,\,$

azaz a abszolút ráta és a ráta közötti különbség.

A${\frac {D}{R}}$mennyiséget tekinthetjük, mint relatív redundanciát, és megadja a lehetséges legnagyobbadattömörítési arányt,ha százalékosan fejezik ki, ami azt mutatja meg, hogy egy fájl hossza mennyire csökkenthető. (Ha úgy fejezzük ki, mint a tömörített fájlhossz és az eredeti fájlhossz aránya, akkor az$R:r$mennyiség az elérhető legnagyobb tömörítési arányt adja meg.) Egy emlékezet nélküli, egyenletes eloszlású forrás redundanciája nulla, és nem tömöríthető.

Meg kell jegyezni, hogy aKolmogorov-komplexitásalapján meghatározott maximális tömörítési valószínűség eltér az előzőek szerint számított maximális tömörítési valószínűségtől, mivel itt azt feltételeztük, hogy az adatoka priorivalószínűségi eloszlása ismert, és előre kódoltak az adatok.

Példák

Tételezzük fel, hogy magyar nyelvű szöveget szeretnénk egy 8 bites bináris csatornán továbbítani, azaz a csatorna bitjeinek száma 8. Amagyar ábécé40 vagy 44 betűt tartalmaz. Ha még a szavak elválasztására szolgálószóközkaraktert is figyelembe vesszük, akkor tehát 41 vagy 45 karakterről van szó. Ha még hozzávesszük a 10 számot, és az írásjeleket, akkor sincs szükségünk több, mint 63 átvivendő karakterre. A 63 karaktert 6 biten lehet kódolni, így az üzenet bitjeinek száma legyen 6. Ebben az esetben a redundancia 2, azaz minden üzenet esetében 2 felesleges vagy kihasználatlan bitet kell átvinnünk a kommunikációs csatornán.

Ez a 2 bites redundancia esetünkben most veszteségként jelentkezik.

Okok a redundáns adattárolásra

Két okból lehet érdemes redundanciát bevezetni az adatok tárolásában.

Hibák kiszűrése

A különböző adattároló eszközöknél, mint például a HDD,DVD,illetve az adatok továbbítása közben az adatok különböző okokból sérülni tudnak. A sérült bitek korrigálásának érdekében redundanciát alkalmaznak a tárolt információban, a legegyszerűbb példa erre, ha két példányban tároljuk a megfelelő adatokat, de több, hatékonyalgoritmuslétezik, amelyek minél kisebb redundanciát bevezetve próbálják lehetővé tenni a hibás bitek észlelését és helyreállítását.

Redundancia az adatbázisoknál

Ha egy relációs adatbázisban egy érték többször is előfordul, mint például egy felhasználónév, akkor azt az adatbázist normalizálatlannak nevezzük. Ebben az esetben egy új táblában tárolhatnánk a felhasználóneveket a felhasználók számazonosítójához társítva, és más helyeken már elég lenne a megfelelő azonosítókat elmenteni, így jelentős tárhelyet spórolhatunk. Egy esetben viszont hasznos lehet ezt a redundanciát bevezetni, ha gyorsítani szeretnénk egy bizonyos lekérdezés idején. Ekkor az adatbázismotornak nem kell összekapcsolnia egy másik tábla adataival az adott sort, így időt spórolhatunk.

Források

• B. Schneier,Applied Cryptography: Protocols, Algorithms, and Source Code in C.New York: John Wiley & Sons, Inc. 1996.ISBN 0471117099
• Alice és Bob - 4. rész: Alice és Bob félreérti egymást

Fordítás

Ez a szócikk részben vagy egészben aData redundancycímű angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.