F 26 feb Bloomfilter

Hashning i Språkteknologi

Hashning används i många olika sammanhang. Här betraktar vi ett exempel från ämnesområdet Språkteknologi, dvs behandling av naturliga språk (mänskliga språk, till skillnad från tex programmeringsspråk) med datorer.

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.

• Läs in ordlistan i en lämplig datastruktur.
• Öppna textfilen.
• Så länge filslut inte nåtts:
• Läs in nästa ord från filen.
• Slå upp ordet i ordlistan och skriv ut det på skärmen om det inte finns med.

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.

• Uppslagning måste gå jättesnabbt.
• Datastrukturen får inte ta så mycket minne (helst inte ens så mycket minne som orden i klartext).
• Orden måste vara kodade (eftersom ordlistan är köpt och inte får spridas till andra).
• Vi kan tillåta att uppslagningen gör fel någon gång ibland.

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 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 50% 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 f₀(ord),f₁(ord), f₂(ord),...,f₁₃(ord). Ett ord godkänns bara om alla dessa 14 hashfunktioner samtidigt ger index till platser itab som innehåller sant.

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

    for i in range(14):
       if not 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)¹⁴=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å webben på http://www.csc.kth.se/stava/ (Länkar till en externa sida.)Länkar till en externa sida. (hjälp finns via webbsidan (Länkar till en externa sida.)Länkar till en externa sida.)

För den som tycker det här verkar intressant finns kursen DD2418, Språkteknologi (Länkar till en externa sida.)Länkar till en externa sida..