Struktúra szerinti feldolgozás, struktúramegfeleltetés, tagolási konfliktus, összefonódási konfliktus, időszerűsítés, rendezés háttértáron. Szövegfeldolgozási feladatok (másolás, számlálás, szűrés, tömörítés, keresés). File-kezelés, szekvenciális file-ok feldolgozása.

Adatfeldolgozás

Adatfeldolgozási feladat (program): olyan feladat (program), amely input szekvenciális file-(ok)on van értelmezve, és output szekvenciális file-(ok)ra képez.

Elemi adatfeldolgozási feladatok:

File másolása: az input file elemeit – egyenként – az output file-ba mozgatjuk

Megjegyzés: Az elemmel, mint adategységgel csak „triviális”, legfeljebb konverziós változtatások történhetnek (in-/output file-ban, illetve memóriában lehetséges ábrázolásbeli különbségek miatt)

Szűrés (kiválogatás): csak bizonyos rekordokat kell másolni

Keresés: Bizonyos tulajdonságú elemek közül az első megkeresése.

Általánosított másolás: Azaz mind a bemeneti, mind a kimeneti file 0 elemű sorozat!

Az összes alaptételszerű, szekvenciális file-okra vonatkozó feladat ide tartozik

Szétválogatás : Különböző tulajdonságú elemek szétválogatása

Összefuttatás (Keverés vagy egymásutánírás, párosítás, összefésülés)

Időszerűsítés

Régi file módosítása egy módosító file alapján

Az új file szerkezetileg olyan, mint a régi (bázistípus azonos)

fileregi (metszet) filemodosito≠Ø (van közös mezőjük)

Megvalósítás: fileregi*filemodosito→fileuj

Rendezés: Az új file a régi file elemeit tartalmazza valamilyen szempont szerint rendezett sorrendben

Adatfeldolgozási feladatok:

Fentiek: alapfeladatok

Minden adatfeldolgozási feladat az alapfeladatokból épül fel, általában a fentiek egymásraépítésével (nem „tisztán”)

Következőkben: tisztán a programozási tételekre visszavezethető feladatok nem kerülnek elő, csak az újak

Elemenkénti feldolgozás: Z=F(X) tétel

Struktúra szerinti feldolgozás:

Az input és output file elemtípusai a struktúrának megfelelően négyféle lehet, ami alapján a feldolgozó program is négyféle lehet a következők szerint:

Adatstruktúra

Skalár

Direktszorzat

Unió

Iterált

Algoritmikus szerkezet

Egyszerű függvény, eljárás

Szekvencia

Elágazás

Ciklus

Struktúra megfeleltetés és típusfinomítás:

Típusfinomítás: A feladat (input/output) adatainak finomítása felülről lefelé haladva; a „főtípus” redukálása „komponenstípusokra”

Konfliktusok:

Nem mindig elemenként feldolgozható a feladat. Tipikus esetek:

1. Tagolási konfliktus:

A bemenet és kimenet fizikai elemhatárai ütköznek => virtuális típus specifikálása

2. Összefonódási konfliktus:

Az input több, összekeveredet sorozat elemeiből áll, a részsorozatok elemei a helyükön vannak
=> szétválogatás

3. Rendezetlenségi konfliktus

Az input és output elemei egyértelműen egymáshoz rendelhetők, de az elemek sorrendje ütközik a feldolgozás sorrendjével => rendezés

Időszerűsítés:

Adott X file és egy Y időszerűsítő file alapján állítsuk elő X frissített változatát a Z file-ban! Az X és Z file-ok teljesen megegyező szerkezetek és értelmezésűek, egy kis különbséggel az Y is; ennek van egy plusz mezője, mely a módosítás fajtáját határozza meg: elem törlése / javítása / beszúrása.

Nem minden esetben elemenként feldolgozható, mivel nem garantált, hogy a két input file és az output file logikailag összetartozó elemei keresztbehivatkozás nélkül egymás mellé helyezhetőek. Ahhoz, hogy elemenként feldolgozható legyen, a továbbiakban feltételezzük, hogy mindkét file kulcs szerint rendezett.

Megoldás a Z=F(X) tétel alapján

Rendezettség miatt következő hozzárendelés alapján elemenként feldolgozható feladattá alakul. Algoritmikus támogatás a hozzárendeléshez: üres elemmel is operálni képes olvasó és író eljárásra van szükségünk.

X	+ Y	→	Z

x	(törlés, x)	z = üres

x	(módosítás, x)	z = x’

x	(beszúrás, x)	z = x

x	üres	z = x

Megoldás összefuttatással

Az összefuttatás algoritmusa alapján, az algoritmus aktualizálásával, és előreolvasási technikát alkalmazva.

alapalgoritmusbeli utasítás	időszerűsítő algoritmus
i := 1	X első elemének előreolvasása
j := 1	Y első elemének előreolvasása
k := 0	Z := () Nyitás outputra
i ≤ N	nem Vége?(X)
j ≤ M	nem Vége?(Y)
X(i) R Y(j) (R {<, >, =})	X, Y akt. elemének relációba állítása, azok olvasása után
k := k + 1; Z(k) :=	Ír(Z, …)
i := i + 1	X következő elemének előreolvasása
j := j + 1	Y következő elemének előreolvasása

Szövegfeldolgozás

Szövegtípusok: karakter, szöveg, szövegfile. Szövegtípusok speciális feladatai:

Másolás: Szövegbeolvasás, szövegkiíratás

Számlálás: Szó, sor, lap

Szűrés: A szöveg a felesleges szóközeinek, vagy egyéb jeleinek elhagyása, szóközszűrés, szócsoport-szűrés. Megoldás szövegfile-ra:

Bemenet: jelek sorozata

Jel: szóköz, nem szóköz

Kimenet: jelek sorozata

Jel: üres, nem szóköz

Tömörítés: ez is szűrés, de visszaalakítható

Huffman-kód

Ha a szövegben az egyes jelek eltérő gyakorisággal fordulnak elő (pl. az 'a' betű gyakoribb, mint az 'x'), akkor a fix hosszúságú karakterkódokról változó hosszúra térünk át. A gyakoriakat rövid, a ritkákat hosszú kódokkal reprezentáljuk. (pl. a=l, x=00000l)

Megjegyzés: Egyik önálló kód sem lehet egy másik kód kezdőrészlete!

TAB karakterek

Szóközcsoportok helyettesítése TAB karakterrel, majd képernyőre ill. nyomtatóra íráskor a TAB karakterek visszahelyettesítése megfelelő számú szóközzel.

Karaktercsoportok kódolása (futamhosszban) – Token

Több egymást követő megegyező karaktert helyettesítjük a karakterrel és annak darabszámával. Speciális karakter (ált. Esc.) jelzi, hogy kódolt, és nem valódi karakter következik. Pl. képek kódolása (pcx file)

Szövegminta-kódolás (jelkombinációk Token-es helyettesítése)

Jelkombinációkat helyettesít kódokkal. A kódtábla a szövegmintákat és a kódokat is tartalmazza; azt nem kell csatolni, mert az algoritmus ismeri.

e) LZW-kód: menet közben építi fel a kódtáblát

Keresés

A feladat a következő: adott egy s szöveg, amelyben meg kell keresni egy sminta szöveg első elhelyezkedésének s-beli pozícióját. A Miben(i+j-1) = Mit(j) hasonlítást ugyanis rossz esetben túl sokszor kell végezni. Megoldások:

Knuth-Morris-Pratt

Egy minta prefix függvénye megadja, hogy hogyan illeszkedik a minta önmaga eltoltjára.

Boyer-Moore

Hosszú minta és sok jelből álló jelkészlet esetén a leghatékonyabb kereső algoritmus. Az illesztést jobbról-balra végzi, az eltolást pedig a nem illeszkedő jel helye és a jó szuffix heurisztika maximuma alapján veszi, így rengeteg felesleges hibás hasonlítást kiküszöböl.

Pl. Szöveg = ’…notice…’; Minta=’reminiscence’

						n	o	t	i	c	e		i	s
r	e	m	i	n	i	s	c	e	n	c	e			

Ekkor a rossz jel heurisztika a ’notice’ – ’reminiscence’ ’i’-párosításokra 4 egységnyi eltolást ad, míg a jó szuffix heurisztika a ’notice’ – ’reminiscence’ ’ce’-párosításokra 3-at, ennek alapján a maximum 4, tehát 4-el fogja eltolni.

Rabin-Karp

A mintához egy A-beli számrendszerbeli számhoz rendel (hosszú szöveg esetén nagy A), amit mod prímszám vesz. A d hosszú minta esetén a szövegben is d hosszú szöveghez számolja ki a hozzárendelt számot, szintén mod prímszámmal. Egyező számértékek esetén még ellenőrzi a szöveget is, mert nem feltétlenül egyezik minden esetben!

File kezelés

File szervezési módok

- szekvenciális file: rákövetkezéses hozzáférés (mágnesszalag elérési lehetősége alapján)

- direkt file: indexelt hozzáférés (mágneslemez elérése alapján)

asszociatív file: tartalomelemzéses hozzáférés

Reprezentációjuk

I/O szekvenciális file:	hagyományos file (elem típus)

Direkt file:	majdnem tömb (elem típus), de a hossza változhat!

Asszociatív file:	tömb (kulcs:elem)

Műveleteik

Input szekvenciális file:	Megnyit, Lezár, Olvas, Vége?

Output szekvenciális file:	Megnyit, Lezár, Ír

Direkt file:	Megnyit, Lezár, Olvas, Ír, Hossz, Töröl, Vége?

Asszociatív file:	Megnyit, Lezár, Olvas, Ír, Töröl, Vége?

Input szekvenciális file axiómái:

Megnyitni csak már korábban létrehozott és meg nem nyitott file-t lehet

Megnyitás után az első elem lesz az aktuális , vége után nem lehet olvasni

Olvasás után a következő elem lesz az aktuális vagy a végére érünk

Output szekvenciális file axiómái:

Megnyitni csak még nem létező file-t lehet, csak lezárással válik létezővé

Megnyitás után az első elem lesz az aktuális, írás után a következő elem lesz az aktuális

Direkt file axiómái:

Ha a megnyitandó file nem létezik, akkor 0 hosszal jön létre. Ha létezik, akkor hossz=elemszám

Nyitás után bármely elem elérhető, s értéke az, amit utoljára kapott (vagy nem definiált)

Az utolsó utáni elem írásakor a file hossza nő. Ha nem közvetlenül az utolsó mögé írok, akkor a köztes elemek nem definiált értékűek lesznek.

Törléskor az adott elem nem definiált értékű lesz, a hossz csökkenhet.

Asszociatív file axiómái:

Ha a megnyitandó file nem létezik, akkor 0 elemű file jön létre.

Nyitás után bármely elem elérhető a kulcsával vagy szekvenciális olvasással (-> első elem)

Törléskor az adott elem nem definiált értékűvé válik

Már létező elem írása nem definiált

Informatika tanári szak államvizsga tételek	4. Programozási módszertan – adatfeldolgozás

Bálint Gergely Illés, 2002	5

Peter Szamoskozi

2004-06-21T17:29:11