Problem S. 12. (November 2005)
S. 12. A typical mistyping occurs when we hit two adjacent keys on the keyboard instead of the required one. Write a program to automatically correct these errors using a dictionary and a keyboard-layout.
The text will consist of lower-case letters of the English alphabet, with maximal length of 1 000 000 words. Words are separated by spaces, but there is no line break. The maximal length of a word is 30 characters (without mistypings), and each word can contain at most 5 mistypings. The order of the correct and unwanted letters in a mistyped word is not specified, all we know is that these letters are adjacent. Spaces are not mistyped. If a word can be corrected in more than one way, your program should choose that version which requires deleting the least number of letters. (If there is still more than one possibility, choose the first appropriate word in the alphabet.)
The dictionary and the keyboard layout are contained in a single file. The first part of the file contains the keyboard layout: the first letter in each row is followed by its neighbouring letters on the keyboard, separated by a space. The layout ends in an empty line. Next comes the dictionary, having a single word in each row in alphabetical order. The maximal number of words is 1 000 000.
Names of the input files will be given in the command line, first the file name containing the actual text, then the dictionary. The output of your program should be written to a file whose name is the given third parameter.
Example:
(10 pont)
Deadline expired on December 15, 2005.
Sorry, the solution is available only in Hungarian. Google translation
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:
Statistics:
12 students sent a solution. 10 points: Engedy Balázs, Grósz Dániel, Nikházy László. 8 points: 1 student. 5 points: 1 student. 4 points: 1 student. 3 points: 1 student. 0 point: 5 students.
Problems in Information Technology of KöMaL, November 2005