# Minta nagy házi

Czirkos Zoltán · 2023.01.13.

A minta nagy házi, amely egy plágiumkereső program. Pontosított specifikáció, végleges program és dokumentációja.

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.

## 1. NHF 1. – Feladatkiírás

> ### 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ó!

## 2. NHF 2. – Pontosított specifikáció

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

## 3. NHF 3. – Félkész megoldás

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.

## 4. NHF 4. részfeladat – Programozói dokumentáció

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

## 5. NHF 4. részfeladat – Felhasználói dokumentáció

> 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

## 6. NHF 4. részfeladat – Forráskód

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