Redundancia

Redundancia az információelméletben az információ- vagy üzenetátvitelre használt csatornán maximálisan egyszerre átvihető bitek számának és az aktuális információ vagy üzenet bitjei számának a különbsége. Az adattömörítés egy lehetséges mód a nem kívánt redundancia csökkentésére, a különféle ellenőrzőösszegek pedig hibajavítás céljából növelik a redundanciát, ha az átvitel egy zajos csatornán folyik, ahol a zaj csökkenti az átviteli kapacitást.

A redundancia (lat.) nyelvtudományi fogalma; 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

Az információelmélet szerint egy információ forrás rá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". Egy emlékezet né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ás abszolút rátája egyszerűen

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

az üzenet tér (például ábécé) számosságának logaritmusa. 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ú.

A redundancia tehá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 legnagyobb adattö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 a Kolmogorov-komplexitás alapjá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 adatok a priori való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. A magyar ábécé 40 vagy 44 betűt tartalmaz. Ha még a szavak elválasztására szolgáló szóköz karaktert 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ékony algoritmus lé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 a Data redundancy cí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.