Föreläsning 16: Sortering.

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/

Damerna först

Den enklaste sorteringsuppgiften är att sortera om en personarray med damerna först och den smarta algoritmen kallas damerna-först-sortering.
  1. Sätt ett pekfinger i var ände av arrayen!
  2. Rör fingrarna mot varandra tills vänstra fingret fastnat på en herre och högra fingret på en dam!
  3. Låt damen och herren byta plats!
  4. Upprepa från 2 tills fingrarna korsats!
Idén används i Quicksort, som är den snabbaste av alla sorteringsalgoritmer för normalt bruk.

Distributionsräkning (Distribution count)

Damerna-först utmärker sej genom att det bara finns två olika nyckelvärden. Om man vet att det bara finns ett litet antal nyckelvärden, till exempel 100 olika, är distributionsräkning oslagbart snabbt. Det kräver att talen som sorteras in i vektorn hämtas från en annan vektor eller fil. Komplexiteten blir O(N).

Quicksort

Damerna-först-algoritmen med två pekfingrar används i Quicksort. Först bestämmer man vilka (små) nyckelvärden som ska kallas damer. Resten kallas herrar och så utför man algoritmen. Vektorn delas alltså i två segment, det första med små värden, det andra med stora värden. Nu behöver man bara sortera segmenten var för sej. Det här är en rekursiv tanke!

Komplexiteten blir i allmänhet O(N log N). Det beror på att man kan dela vektorn på mitten log N gånger. Exakt hur snabb den är beror på hur man avgör vilka värden som ska vara damer. Ofta tar man det första talet i vektorn och utnämner det och alla mindre tal till damer. Då blir Quicksort mycket långsam för redan nästan sorterade vektorer! Det bästa är att ta ut tre tal - det första, det sista och något i mitten - och låta det mellersta värdet bestämma vad som är damer. Det kallas median-of-three i läroboken. Man kan visa att komplexiteten då blir 1.4 N log N i genomsnitt.

Samsortering (Merge sort)

Om man har flera sorterade småfiler är det lätt att samsortera dom till en fil. Det här kan man också göra med en vektor om man har extrautrymme för att kopiera den till två andra hälften så långa vektorer. Det här ger en rekursiv tanke! Komplexiteten blir O(N log N), lika snabb som quicksort men kräver extra minnesutrymme.

^ Upp till kurssidan.


Sidansvarig: <efo@nada.kth.se>
Senast ändrad 29 januari 2001
Tekniskt stöd: <webmaster@nada.kth.se>