Föreläsning 20: Stava.

Stavningskontroll

Ett stavningskontrollprogram ska läsa en text och markera alla ord som är felstavade. Om man har tillgång till en ordlista som innehåller alla riktiga svenska ord kan man använda följande enkla algoritm för att stavningskontrollera en text. Enda problemet är hur man ska välja datastruktur för lagring av ordlistan. Svenska akademiens ordlista innehåller ungefär 200000 ord. Förutom dessa ord finns en hel del böjningsformer och oändligt många tänkbara sammansättningar. Låt oss bortse från detta och anta att vi har köpt en ordlista med dom 200000 vanligaste orden i svenskan. Om vi snabbt ska kunna stavningskontrollera en stor text med en normal persondator måste följande krav på datastrukturen vara uppfyllda. Den sista punkten är inte ett krav utan en egenskap hos vårt problem som vi kan utnyttja. Det är nämligen inte hela världen om programmet missar något enstaka felstavat ord i en jättestor text.

Vanliga datastrukturer (sorterad array, sökträd, hashtabell) faller alla på något av kraven ovan.

Försök med datastruktur: boolesk hashtabell

Låt oss först försöka med hashning där vi inte lagrar själva orden och inte tar hand om eventuella krockar. Vi har en hashfunktion f(ord)=index som för varje ord anger en position i en boolesk hashtabell tab. Den booleska variabeln tab[f(ord)] låter vi vara sann (1) då ord ingår i ordlistan. Detta ger en snabb, minnessnål och kodad datastruktur, men den har en stor brist: Om det råkar bli så att hashfunktionen antar samma värde för ett ord i ordlistan som för ett felstavat ord så kommer det felstavade ordet att godkännas. Om hashtabellen exempelvis är fylld till häften med ettor så är sannolikheten för att ett felstavat ord ska godkännas ungefär 0.5 vilket är alldeles för mycket.

Bloomfilter

Lösningen är att använda många hashfunktioner som alla ger index i samma hashtabell tab. I Viggos stavningskontrollprogram Stava används till exempel 14 olika hashfunktioner f0(ord), f2(ord),...,f13(ord). Ett ord godkänns bara om alla dessa 14 hashfunktioner samtidigt ger index till platser i tab som innehåller sant (det vill säga 1).

Uppslagning av ett ord kan då ske på följande sätt:

    for (int i = 0; i < 14; ++i) 
        if(!tab[f(i, ord)])
            return false;
    return true;
Om hashtabellen är till hälften fylld med ettor blir sannolikheten för att ett felstavat ord godkänns så liten som (1/2)14=0.006%.

Denna datastruktur kallas bloomfilter efter en datalogiforskare vid namn Bloom. Ett abstrakt bloomfilter har bara två operationer: insert(x) som stoppar in x i datastrukturen och isIn(x) som kollar ifall x finns med i datastrukturen.

Programmet Stava kan köras på Nadas Unixdatorer med kommandot

stava filnamn

(hjälp finns här). Stava kan också köras från webben: http://www.nada.kth.se/stava/


^ Upp till kurssidan.


Sidansvarig: <vahid@nada.kth.se>
Senast ändrad 9 februari 2005
Tekniskt stöd: <webmaster@nada.kth.se>