Minta nagy házi

Ez az oldal egy nagy házi feladathoz hasonló programot mutat be. Mintaként szolgál a nagy házi feladathoz, és főleg az ahhoz tartozó dokumentációhoz.

Miről szól ez a részfeladat?

Valahogy így nézhet ki az a kezdeti feladatkiírás, amely a honlapról származik vagy egy hozott feladat. Ez az, amit a feladat kiválasztásaként elfogad a laborvezető.

Készíts programot, amely plágium detektálására használható! Olvasson be a program szövegfájlokat, és keresse meg közülük azokat a párokat, amelyek leginkább hasonlítanak egymásra! A programot parancssori felületről lehessen vezérelni, és meg lehessen neki adni azt is, hogy melyik szövegnek ki a szerzője. A kimenetben a hasonlóságok név szerint szerepeljenek. Találj ki valamilyen módszert, amellyel a hasonlóság vizsgálható!

Miről szól ez a részfeladat?

A pontosított specifikáció részletesen bemutatja azt, hogy mit fog tudni a program: milyen bemenetekkel rendelkezik, milyen kimeneteket állít elő, hogyan kell majd kezelni. Ebbe beletartozik a program által kezelt fájlok leírása is.

A pontosított specifikáció olyan írásmű, amelyet az iparban a program megrendelője és a programozó közösen állítanak össze. A megrendelőt azonban általában nem érdekli, hogyan működik a program; sőt ha nem ért a programozáshoz, akkor nem is érti a program belső felépítését. A specifikáció ezért semmiképp nem annak leírása, hogy hogyan fog működni a program – az már a megvalósítás része!

A specifikáció egy önálló, önmagában értelmezhető szöveg kell legyen. Ez azt jelenti, hogy a készülő program lényegét, feladatát részletesen el kell magyarázni, akkor is, ha közismert feladatról van szó. Nem elég annyit írni, hogy egy römi kártyajáték lesz, mert mindenki máshogy játssza azt: kell dobni vagy nem? mennyi legyen az elsőként lerakott sorok pontértéke minimálisan? van joker vagy nincs? kell-e dobni vagy nem? és így tovább.

Ennek az írásnak nem kell pont ugyanígy kinéznie, ugyanilyen felépítéssel rendelkeznie, mint az itt bemutatottnak. A plágiumkereső egy nem interaktív program (azaz indítása után már nem vezérelhető, hanem kiszámolja, amit kell, és befejeződik), tehát logikus a specifikációban arra helyezni a nagy hangsúlyt, hogy milyen bemenő adatokból milyen kimenő adatokat állít elő. Egy játéknál a pontosított specifikáció inkább a szabályokat rögzítené, és azt mutatná be, nagyjából hogyan fog kinézni a program: miket lehet választani a menüből, hogyan fog kinézni játék közben a pálya, mely gombokkal lehet irányítani a játékost stb.

A program célja

A feladat egy olyan program készítése, amely szövegfájlok (dolgozatok) között hasonlóakat keres. (Az összehasonlítás módszerét a program fejlesztése során ki kell majd találni.) Az összehasonlítás eredménye minden szövegpárra egy százalékos mutató, amelynek annál magasabbnak kell lennie, minél jobban hasonlít egymásra a két szöveg. Az összehasonlított szövegeket hasonlóság szerint sorba rendezve könnyen felfedezhető a plágium.

A program használata

A felhasználónak a program használatához össze kell gyűjtenie az összehasonlítandó szövegeket (.txt fájlok formájában), továbbá írnia kell egy vezérlőfájlt. A vezérlőfájl mutatja meg a program számára, hogy melyik fájlokban találja meg az összehasonlítandó szövegeket, és hogy melyik szövegnek ki a szerzője. Ezeket a vezérlőfájl soronként, szóközzel elválasztva tartalmazza:

fájlnév szerző_neve

A fájlnévben nem lehet szóköz, mert a szerző névtől egy szóköz választja el. Az utóbbi azonban több tagból is állhat. Pl.:

148.txt Csizma Dia
56.txt Olajos Alajos

Az így hivatkozott szövegfájlok tetszőleges folyó szöveget tartalmazhatnak. A program minden indításával egy vezérlőfájlt tud feldolgozni. Indításkor a vezérlőfájlt (és esetleg egy táblázatfájl nevét) parancssori paraméterként kell megadni a programnak:

plagkeres <vezérlőfájl> [táblázatfájl]

A második paraméter nem kötelező – ha adott, akkor abba kerül az Excel által is olvasható táblázat, amúgy pedig csak a szabványos kimenetre az első húsz hasonlóság adata.

A futás eredménye

A program az összehasonlított dolgozatokat csökkenő hasonlóság szerint listázza a szabványos kimenetére. A hasonlóságot százalékban adja meg, ahol 100% a teljesen egyforma dolgozatokat jelenti, 0% pedig a teljesen különbözőeket. A kimenet két formátumban jelenik meg. A szabványos kimeneten az első húsz legnagyobb hasonlóság adata jelenik meg, gyors áttekintést adva a futási eredményről. A formátum:

név (fájlnév) ↔ név (fájlnév), százalék%
Remek Elek (32.txt) ↔ Csizma Dia (148.txt), 64.58%

A másik kimenet fájlba íródik, és lényegében ugyanezek az adatok szerepelnek, de az összes dolgozatpárra. Az egyes mezőket pontosvessző választja el:

százalék;név1;fájlnév1;név2;fájlnév2
64.58;Remek Elek;32.txt;Csizma Dia;148.txt

Egy ilyen formátumú fájlt bármelyik táblázatkezelő program meg tud nyitni.

Ezt a részfeladatot a laborvezetővel kell egyeztetni; ő főleg azt fogja nézni és értékelni. Mintát erre nem igazán lehetne adni, mert minden feladat más jellegű. A lényeg, hogy legyen érdemi haladás, látszódjon a programon, hogy mi készül, bizonyos funkciói már működjenek.

A programozói dokumentáció célja az, hogy a program belső felépítését, működését bemutassa. A jó programozói dokumentáció egyik fő ismérve az, hogy azt elolvasva egy másik programozó hamar képet kap a program felépítéséről, és segítségével könnyen eligazodik az addig számára ismeretlen forráskódban. Ennek megfelelően legalább az alábbi részeket kell tartalmazza:

• A megvalósított módszerek áttekintő magyarázata. Jelen esetben ez azt a nem triviális eljárást mutatja be, amellyel a program összehasonlít két szöveget.
• A program adatszerkezeteinek magyarázata. Milyen adat hol tárolódik, és miért.
• A program moduljainak és függvényeinek magyarázata. Forrásfájlok, függvények, globális változók. Mi az egyes modulok és függvények feladata, és hogyan kell azokat használni.

A dolgozatok összehasonlítása

A plagizált szövegek leggyakrabban úgy keletkeznek, hogy a plágiumot elkövető szerző egy kiinduló szöveget több-kevesebb helyen átfogalmaz. A szöveg értelme meg kell maradjon, ezért a változtatás tagmondatok, szövegrészek cseréjéből, továbbá különböző töltelékszavak és szinonímák beillesztéséből áll.

A szövegek egyes szavait vizsgálva általában nem vonhatunk le automatikusan következtetést a plágiumra. Például bármelyik programozói dokumentáció jogosan tartalmazhatja a „ciklus”, „tömb”, „algoritmus” szavakat, ettől azok még teljesen különböző szövegek lehetnek. Azonban a két-, három- vagy többszavas sorozatok (kifejezések) egyezése plágiumra utalhat.

A program
program módszerének
módszerének lényege
lényege az
az hogy
hogy a
a beolvasott

A megírt program módszerének lényege az, hogy a beolvasott dolgozatokat szavakra bontja, és a szövegek szópárjait próbálja megtalálni a másik szövegekben. A szópárok vizsgálata azért elegendő, mert egy hármas szókapcsolat két egyező szópárként is felfogható, négyes kapcsolatok három párként, és így tovább. Ezeket a szópárokat a programban egyszerűen kifejezésnek nevezzük.

A program számára egy szöveg szópárok halmazaként jelenik meg. Egy összehasonlítás a halmazok metszését jelenti. Minél nagyobb a metszet halmaz a szöveg teljes terjedelméhez képest, annál erősebb a plágium gyanúja.

Az így definiált hasonlóság érdekessége, hogy nem szimmetrikus. Tegyük fel, hogy „A” dolgozat teljes egészében tartalmazza „B” dolgozatot, csak a végén szerepel még egy összefoglaló rész is. Ebben az esetben „B”-re azt mondhatjuk, hogy a benne lévő szöveg 100%-ban megtalálható „A”-ban, az „A” dolgozat szövege viszont nem 100%-ban „B”-ből származik. Ezért két hasonlóságot kell meghatározni minden szövegpárhoz. A program kiszámolja mindkét értéket, és a kettő maximumát veszi figyelembe.

Csak a teljesség kedvéért: ez hasonló az ún. Jaccard-féle hasonlósági mértékhez. Lásd még: átfedési együttható.

Adatszerkezetek választása

A program működésének két fő szereplője van. Egyik szereplő a dolgozat, amelynek tulajdonságai a szerző neve, a szövegfájl neve és a kifejezések halmaza. Másik szereplő pedig a hasonlóság, amely két dolgozatot köt össze: azt tárolja, hogy a két hivatkozott dolgozat milyen arányban hasonlít egymásra. Ezeket az adatokat a programnak tárolnia kell, amihez adatszerkezetet kell választani.

A dolgozatok egy egyszerű, rendezetlen listában tárolhatóak. A listát a vezérlőfájl beolvasásakor állítja elő a program. Rendezettséget ebben nem szükséges fenntartani, mert az eredményeket nem a dolgozatok adatai, hanem a hasonlóságok alapján kell megjeleníteni. Egy dolgozat adatait tároló osztály:

class Dolgozat:
    def __init__(self, fajlnev, nev):
        self.fajlnev = fajlnev
        self.nev = nev
        self.kifejezesek = # ...

A hasonlóságok szintén listában tárolódnak. A meghatározásuk már azután történik, hogy az összes dolgozatot beolvastuk, és addigra azok száma ismert. N dolgozat esetén N×(N-1)/2 hasonlóságot kell tárolni, mivel mindegyik dolgozatot össze kell hasonlítani minden másikkal. A listát végül rendezni kell majd a hasonlóság szerint, de ez is csak akkor fog történni, amikor már az összes párt megvizsgálta a program, vagyis csak egyetlen egyszer, a futás végén. A hasonlóságot tároló objektum tartalmaz két referenciát is, amely alapján visszafelé is követhető, melyik dolgozatokra vonatkozik:

class Hasonlosag:
    def __init__(self, d1, d2):
        self.d1 = d1
        self.d2 = d2
        self.has = # ...

Mivel minden dolgozatot össze kell hasonlítani az összes többivel, és eközben két halmaz metszetét kell képezni, a futás sebességét erősen befolyásolja az, hogy a halmazhoz milyen adatszerkezetet használunk. A halmaz reprezentációja a következő adatszerkezetekkel történhet:

reprezentáció	beszúrás	eleme-e?	metszet
rendezetlen lista	O(1)	O(n)	O(n2)
bináris fa	O(log n)	O(log n)	O(n×log n)
rendezett lista	O(n)	O(n)	O(n)

Rendezetlen lista használata esetén a metszet képzésénél az összehasonlítás lépésszáma négyzetes, mivel az egyik halmaz minden eleménél meg kell vizsgálnunk, szerepel-e az a másik halmazban. A bináris fával reprezentált halmazok esetén ez O(n×log n) lépésre redukálódik, mivel egy adott elemről O(log n) lépésben meg tudjuk mondani, hogy szerepel-e a fában, de ezt még mindig meg kell tennünk az összes vizsgálandó elem esetén.

A rendezett listán mindez O(n) lépésből elvégezhető az összefésülés algoritmusát használva. Bár az „eleme-e?” művelet és a beszúrás is lassabb a bináris fáénál, mégis érdemes ezt választani. A beszúrás műveletét csak a dolgozatok beolvasásakor használjuk (dolgozatonként annyiszor, ahány szót tartalmaz a szöveg), a metszet képzését viszont dolgozatpáronként el kell végezni. A konkrét „eleme-e?” műveletre egyáltalán nincs is szükségünk a programban.

A program működését vezérlő fő osztályok és függvények:

class Dolgozat

Egy dolgozat adatait tárolja: fájlnév: fajlnev, név: nev és a kifejezések listája: kifejezesek.

dolgozat.vezerlofajl_beolvas(vezerlofajl)

Beolvassa a vezérlőfájlt, és létrehozza a dolgozatok listáját. Paramétere a vezérlőfájl neve, vissza pedig a dolgozat objektumok listáját adja. A dolgozatok szövegét a függvény nem olvassa be. Hiba esetén kivételt dob.

dolgozat.dolgozatok_beolvas(dolgozatok)

Beolvassa a szövegeket, és felépíti a halmazokat. A paramétere a lista, amely a dolgozat objektumok tartalmazza, és bennük a fájlok neveit is. A függvény a listát nem módosítja, hanem a halmazok jönnek létre minden dolgozat objektumban. Hiba esteén kivételt dob; ilyenkor előfordulhat, hogy csak a szövegek egy része van beolvasva.

class Hasonlosag

A Hasonlosag osztály két dolgozatot hivatkozik meg, és tárolja azok egymáshoz hasonlóságának mértékét is. Adattagja: d1 és d2 dolgozatra referenciák, és has a hasonlóság mértéke (0...1).

hasonlosag.halmaz_hasonlosag(halmaz1, halmaz2)

Megadja két halmaz metszetének méretét. A halmazoknak rendezve kell lenniük. A Hasonlosag osztály konstruktora használja.

hasonlosag.osszeset_hasonlit(dolgozatok)

Páronként összehasonlítja az összes szöveget, és előállítja a hasonlóság adatokat. Bemenő adata a dolgozatok listája, a kimenő adat pedig a hasonlóságok listája. A visszaadott lista mérete N×(N-1)/2 lesz, ahol N a dolgozatok lista hossza.

hasonlosag.hasonlosag_rendez(hasonlosagok)

Sorba rendezi a hasonlóság objektumokat csökkenő hasonlóság szerint.

A halmazok előállítása, a halmaz metszése és az elemszám használata

A program működésének leglényegesebb részei a kifejezések halmazának előállítása, a halmazok metszése, és az elemszámok viszonyítása a halmazok teljes méretéhez. Ezekhez a program az alábbi algoritmusokat alkalmazza.

# DOLGOZAT BEOLVASÁSA
elozo = ""
kifejezesek = []
with open(fajlnev) as f:
    for sor in f:
        for szo in sor.rstrip("\n").split():
            szo = szo.strip(string.punctuation)
            if szo == "":   # ha csak írásjel lett volna
                continue
            kifejezesek.append(elozo + " " + szo)
            elozo = szo
kifejezesek.sort()

A fenti programrész a kifejezesek_fajlbol() függvény része. Ez a beolvasás közben mindig emlékszik az előző beolvasott szóra. Azt és az aktuálisan beolvasott szót összefűzi, és az kerül a listába. Az egyes beolvasott szavakat megszabadítja az elejükön és a végükön lévő írásjelektől.

# KÉT HALMAZ METSZETÉNEK MÉRETE
metszet = 0
i1 = 0
i2 = 0
while i1 < len(halmaz1) and i2 < len(halmaz2):
    if halmaz1[i1] < halmaz2[i2]:
        i1 += 1
    elif halmaz1[i1] > halmaz2[i2]:
        i2 += 1
    else:
        i1 += 1
        i2 += 1
        metszet += 1

return max(metszet / len(halmaz1), metszet / len(halmaz2))

Ez a kódrészlet határozza meg meg két halmaz metszetének elemszámát. Az algoritmus működése kifejezetten arra épül, hogy a halmazok rendezett listában tárolódnak. A halmaz1 és halmaz2 listákon végiglépked az i1 és i2 indexekkel. A működése hasonló, mint az összefésülő rendezés kapcsán tanult:

• A ciklus addig fut, amíg valamelyik indexszel végig nem ért az ahhoz tartozó listán. Ha ilyen történik, akkor nem lesz több egyező elem.
• Ha az első halmaz elején kisebb szám van, mint a második elején, akkor az előbbi szám nem lehet az utóbbi halmazban, és ezért i1-gyel lép tovább. Fordított esetben az i2 indexet növeli.
• Ha a listák elején két egyforma elem van, akkor az része a metszetnek is. Ilyenkor a darabszámot növelni kell eggyel, és mindkét indexet léptetni a listák következő elemeire.

A hasonlóság meghatározása ezek után úgy történik, hogy a metszet méretét viszonyítjuk az egész halmazok méretéhez.

A felhasználói dokumentáció, ahogy a neve is mutatja, már nem programozóknak szól, hanem azoknak, akik a programot használni fogják. Itt kell bemutatni azt, hogy mit tud a program, és hogy hogyan kell az egyes funkcióit aktiválni és használni.

A plagkeres program arra való, hogy szöveges fájlok közt megkeressük az egymáshoz hasonlókat. Az összehasonlítás azon alapszik, hogy a beolvasott szövegekben szereplő kétszavas kifejezéseket hasonlítja össze páronként az összes szövegben. Az összehasonlítások után az egyes szövegpárokat a program csökkenő hasonlóság szerinti sorba rendezi, és a szabványos kimeneten megjeleníti a legerősebben hasonlító párokat. Az összes hasonlóság adata egy olyan fájlba is kiíratható, amelyben a mezőket pontosvessző választja el, és így az táblázatkezelővel (pl. Excel) megnyitható.

A program parancsorból indítható:

plagkeres <vezérlőfájl> [kimenet.csv]

Az első paramétere egy vezérlőfájlt ad meg, amely az összehasonlítandó szövegfájlok neveit, és azok szerzőinek neveit tartalmazza. A második paraméter opcionális; ha az szerepel, akkor a megadott nevű fájlba írja az összehasonlítások adatait.

A vezérlőfájl formátuma a következő kell legyen:

fájlnév szerző neve

A fájlnévben nem lehet szóköz, a névtől viszont egy szóköz választja el. A szerző neve több szóból is állhat. Pl.:

148.txt Csizma Dia
56.txt Olajos Alajos

A képernyőn megjelenő kimenet a legnagyobb hasonlóságokat mutatja az alábbi formátumban:

Remek Elek (32.txt) ↔ Csizma Dia (148.txt), 64.58%

A kiírt eredményfájl formátuma egy példával:

százalék;név1;fájlnév1;név2;fájlnév2
64.58;Remek Elek;32.txt;Csizma Dia;148.txt

A program teljes forráskódja és a tesztadatok letölthetőek innen: mintanhf.zip.