Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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:

s12.pas

s12_tesztadatok.zip


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