 |
Az S. 12. feladat (2005. november) |
S. 12. Gyakran előfordul, hogy egy szöveg gépelése közben egy billentyű helyett véletlenül két, egymás mellettit ütünk le. Írjunk programot az ilyen gépelési hibák automatikus javítására szótár és egy billentyűzet-kiosztást tartalmazó táblázat alapján.
A szöveg kizárólag az angol ábécé kisbetűiből áll, maximális hossza 1 000 000 szó. A szavakat szóközök választják el egymástól, sortörés nincs. Egy szó maximális hossza 30 karakter (hibák nélkül), és egy szóban legfeljebb 5 hiba szerepelhet. A hibáknál a jó és a véletlenül leütött betűk sorrendje nincs meghatározva, de mindenképpen egymás mellett szerepelnek. Szóközt nem üt félre a gépelő. Ha egy szót többféleképpen is ki lehet javítani, akkor azt válasszuk, ami a legkevesebb betű elhagyását igényli; ha ezek után is több lehetőségünk van, akkor a betűrendben legelső helyes szót válasszuk.
A szótárat és a billentyűzetkiosztást egyetlen fájl tartalmazza. A fájl elején a billentyűzetkiosztás szerepel. Minden sor első betűjét a klaviatúrán vele szomszédos billentyűk követik, szóközzel elválasztva. A kiosztást egy üres sor zárja. Ezt követi a szótár, melynek minden sorában 1 szó található, ábécé sorrendbe szedve. A szavak maximális száma 1 000 000.
A program a parancssorban kapja a bemeneti fájlok nevét, először a szövegét, utána a szótárét. A kimenetet is egy fájlba írja, melynek neve a program harmadik paramétere.
Példa:
(10 pont)
A beküldési határidő 2005. december 15-én LEJÁRT.
Megoldás. A feladatot sokféleképpen meg lehet oldani, éppen ezért a teljesség igénye nélkül egy viszonylag kevés megfontolást igénylő, szinte egyértelmű algoritmust mutatunk be.
A feladat ezen megoldásában nem használunk külön memória-kezelő algoritmusokat, mivel az túlmutatna a verseny célkitűzésein: egyszerűen előre lefoglaljuk a feladat által definiált maximális memóriaterületet (ami a teljes szótár eltárolásához szükséges kb. 30 MB -- egyszerűség kedvéért 256MB) mivel ennyi memóriával a legtöbb mai számítógép rendelkezik.
Ekkora memóriát a DOS-os rendszerekben megszokott Turbo Pascal, Borland C++ vagy más fordítóprogramokkal nem tudnánk lefoglalni, ezért Free Pascalt használunk a kód lefordításához. (C/C++ esetén GCC vagy Visual C++ )
Megfontolások a program megtervezése előtt
Vegyük észre, hogy a szöveg szavai nem befolyásolják egymás kijavítását, így eltárolásukra nincs szükség. A bemeneti szövegfile-t és a kimeneti file-t egyszerre írjuk, és olvassuk. További megfigyelés, hogy egy szó hossza csak csökkenhet a javítás során. Így elég csak a szó hosszával megegyező, illetve a nála rövidebb szótári szavakkal történő összehasonlításokat elvégezni.
Mivel a legkevesebb -- feltételezett -- hiba kijavításával kapott szótári szavak között ábécé sorrendben az elsőt kell megadni, így kézenfekvőnek tűnik a szótárat először szóhossz szerinti csökkenő sorrendbe rendezni, majd ezen belül ábécé sorrendbe. Így a listán sorbamenve, az első lehetséges szó lesz a megfelelő kijavítás, adott javítandó szóra nézve.
A program működési elve
A szövegből beolvassuk a soron következő szót, majd a fentieknek megfelelő módon rendezett szótárból, a javítandó szó hosszától kezdődően elkezdjük végigpróbálgatni a szavakat. A két szót az elejéről kezdve összehasonlítjuk. Amennyiben egy olyan betűhöz érünk, mely nem egyezik meg a két szóban, megvizsgáljuk, hogy eredményezhett-e aez a félregépelés.
Félregépelés akkor történhetett, hogy ha az eltérő betű billentyűszomszédja vagy az előtte, vagy az utána következő betűnek, és a helyes betű megtalálható a szóban, a hibás betűtől maximum 2 betűnyire. (akkor van 2 betűnyire, ha az utolsó megegyező betű leütésekor került a helyes betű után egy hiba, és a következő helyes betű leütése előtt is.) Amennyiben a szó végén vagyunk, ez a hibás karakter a hibás szó utolsó betűje.
Előfordulhat olyan eset, mikor egyezőnek találunk egy elgépelt betűt. Ez akkor fordulhat elő, ha az elgépelt és a soron következő betű megegyezik. Ilyenkor természetes, hogy az elgépelt betű a helyes után következik. Viszont amint más karakter jön a helyes szóban, hibát detektálunk, amely nem ott keletkezett, hanem több betűvel ezelőtt.
Pl.: eredeti szó: abcdsssef; hibás szó:abcdssssef
Ennek a problémának a kezelésére megjegyezzük, hogy a hibás szóban hol kezdődött egy azonos karakterekből álló rész, és ott nézzük meg hogy szomszédosak-e a billentyűzeten a betűk. (A példában az e-s-nél felmerülő problémára a választ a d-s-nél keressük.)
Az így felfedezett hibákat javítjuk (kihagyjuk a hibásan leütött karaktert) majd a vizsgálatot újrakezdjük, ugyanis újabb problémát okozna az azonos karakterekből álló részen belüli újabb hiba. (a példában mondjuk a 2. s betű után egy "a" betű leütése)
Amennyiben a hibák kijavításával megkapjuk az eredeti szót, ez lesz a helyes, tehát kiírjuk a kimeneti file-ba, majd beolvassuk a következő hibás szót. Ha nem, a szótár következő szavát próbáljuk.
A megvalósítással kapcsolatos megjegyzések
Beolvasás
A filenevek belolvasásával többeknek volt problémája. Főként a parancssori argumentumok kezelésével.
Parancssori argumentum, pl: s12.exe szoveg.txt szotar.txt ki.txt
Pascalban ezeket a paramétereket a ParamStr( integer ) : string; függvénnyel lehet elérni, a paraméterek számát pedig a ParamCount : integer; adja vissza.
C/C++ -ban a main függvény paramétereiként lehet megkapni a parancssori argumentumokat: int main(int argc, char *argv[]) ahol az argc a paraméterek száma, a *argv[] pedig a paraméter stringeket tartalmazó tömb.
A billentyűzetkiosztást érdemes egy 26*26-os boolean (true,false) mátrixban tárolni. Ezzel direkt módon tudjuk lekérdezni két betűről, hogy szomszédosak-e a billentyűzeten.
A beolvasás többi részéhez nem fűznék további megjegyzéseket, mivel aki eddig eljutott, annak nem okozott gondot a beolvasás.
A szótár sorbarendezése
Kihasználhatjuk, hogy a szótár szavait eleve betűrendben kapjuk. 30-szor végignézzük a beolvasott szótárat, és a 30,29,28...2,1 hosszú szavakat kigyűjtjük egy új listába, vagy eleve ebbe olvassuk be a file-ból a szavakat. Utóbbi esetben 30-szor kell végigolvasni a file ezen részét.
Az egyes szóblokkok kezdőindexét eltároljuk, így oldjuk meg, hogy fölöslegesen ne nézzük végig a javítandó szóbnál hosszabb szótári szavakat.
Engedy István
Letölthető file-ok:
Statisztika:
12 dolgozat érkezett. 10 pontot kapott: Engedy Balázs, Grósz Dániel, Nikházy László. 8 pontot kapott: 1 versenyző. 5 pontot kapott: 1 versenyző. 4 pontot kapott: 1 versenyző. 3 pontot kapott: 1 versenyző. 0 pontot kapott: 5 versenyző.
A KöMaL 2005. novemberi informatika feladatai