Genkendelse af tegn

Opgaven består i at skrive et program som kan genkende tegn.

Detaljer

Hvert tegn i det tegnsæt, dit program skal kunne genkende, er beskrevet som et billede der består af 20 linjer hver med 20 cifre. Hvert ciffer er ‘0’ eller ‘1’. Se figur 1a.

Filen FONT.DAT indeholder definitioner af 27 sådanne tegnbilleder i denne rækkefølge:

abcdefghijklmnopqrstuvwxyz

Ovenstående linje er altså navnene på de tegnbilleder som er defineret i FONT.DAT. For at mellemrumstegnet skal kunne ses på tryk, er det ovenfor vist som . I outputfilen skal mellemrumstegn ikke udskiftes med .

Filen IMAGE.DAT indeholder et eller flere tegnbilleder som kan være fejlbehæftede.

Et tegnbillede kan være fejlbehæftet på følgende måder:

en linje er blevet gentaget (og de to udgaver af linjen står i så fald lige efter hinanden)
en linje er forsvundet
nogle nuller et blevet til ettaller
nogle ettaller er blevet til nuller

Fejl af typerne (a) og (b) kaldes her for linjefejl.
Fejl af typerne (c) og (d) kaldes her for punktfejl.

For datafilen IMAGE.DAT gælder følgende:

Intet tegnbillede har fået mere end een linje gentaget.
Intet tegnbillede har mistet mere end een linje.
Intet tegnbillede har både mistet en linje og fået en linje gentaget.

En eller begge udgaver af en gentaget linje kan indeholde punktfejl. De to linjer er derfor ikke nødvendigvis ens.

Tegnbillederne indeholder højst 30% punktfejl.>

Opgave

Skriv et program som genkender den fejlbehæftede tegnsekvens i filen IMAGE.DAT, idet det sammenligner med den font som er defineret i filen FONT.DAT .

Genkend et tegnbillede ved at vælge det fontbillede som afviger fra tegnbilledet med færrest mulige punktfejl. Ved optællingen af punktfejl korriger man for linjefejl på en sådan måde at antallet af punktfejl bliver mindst. Specielt skal man i tilfælde af linjegentagelse kun tælle punktfejl i den mindst fejlbehæftede udgave af den dublerede linje.

Alle tegnbilleder i de anvendte evalueringsdatafiler kan genkendes et for et af et velskrevet program.

Der findes én og kun én bedste løsning for ethvert sæt af de anvendte evalueringsdatafiler.

Et korrekt program bruger hele indholdet af IMAGE.DAT

Input

Begge inputfiler begynder med et heltal N (19£N£ 1200) som angiver antallet af efterfølgende linjer:

N
(ciffer1)(ciffer2)…(ciffer20)
(ciffer1)(ciffer2)…(ciffer20)
…

Hver linje med data er 20 cifre lang. Der er ikke mellemrum mellem ettallerne og nullerne.

Filen FONT.DAT definerer fonten. FONT.DAT indeholder altid 541 linjer. FONT.DAT er ikke nødvendigvis den samme ved de forskellige sæt af evalueringsdatafiler.

Output

Dit program skal til filen IMAGE.OUT skrive en enkelt streng af de genkendte tegn. Filens format er en enkelt linje med ASCII-tekst. Programmets output må ikke indeholde skilletegn. Hvis programmet ikke genkender et bestemt tegn, skal der i stedet udskrive et ‘?’ på det tilsvarende sted i outputfilen.
Pas på: Outputformatet som er beskrevet ovenfor overholder ikke de generelle regler for output. I de generelle regler specificeres det at blanktegn (mellemrum) anvendes som skilletegn i output. I denne opgave er eventuelle blanktegn en del af outputdata.

Pointgivning

Der gives et procenttal som angiver hvor stor en del af tegnene der er blevet korrekt genkendt.

Eksempler på datafiler

Eksempel på inputfiler

Herunder ses begyndelsen af FONT.DAT (nemlig definitionen af de to første tegn, mellemrum og ‘a’).

Herunder ses IMAGE.DAT, som viser en meget kort sekvens, nemlig et enkelt fejlbehæftet ‘a’ .