Grudat 2003-12-09 Kurs forel [NADA, KTH]

Nada

Föreläsning 7: Bloomfilter, Googlesökning, prioritetskö

Om stavningskontroll, gästföreläsare professor Viggo Kann
Boolesk hashtabell
Bloomfilter

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 (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 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 i tab som innehåller sant (det vill säga 1).

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 exists(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) och i webben på http://www.nada.kth.se/stava/

Googles sökning

Google har webbspindlar som följer alla webblänkar och tar kopior på alla webbsidor. För att snabbt hitta alla sidor som innehåller ett visst ord hashar man varje ord på varje nyinläst sida och lägger där in dels ordets textomgivning, dels skivminnesadress till den sparade websidan. Resultatet av sökning på ett visst ord är alltså en lista av webbsidor.

Sökning på flera ord ger flera listor och då visas först träffar på alla sökorden. Men det som gjort Google till ledande sökmotor är dess förmåga att visa dom bästa länkarna först. Googles upphovsmän är två studenter vid Stanford (Page och Brin) och deras geniala begrepp kallas page rank. Här följer en matematisk beskrivning skriven av Matlabs skapare, Cleve Moler.

Låt W vara mängden av webbsidor som Google kommit åt och låt n vara antalet sidor i W. Just nu är n drygt tre miljarder. Let G be the n-by-n connectivity matrix of W, that is, g_i_j is 1 if there is a hyperlink from page i to page j and 0 otherwise. The matrix G is huge, but very sparse; its number of nonzeros is the total number of hyperlinks in the pages in W. Let c_j and r_i be the column and row sums of G.

c_j = _i g_i_j, r_i= _j g_i_j

The quantities c_k and r_k are the indegree and outdegree of the k-th page. Vi tänker oss en slumpvandring genom sidorna i W, där vi med sannolikhet p följer en länk till en ny sida och med sannolikhet 1-p hoppar till en på måfå vald sida i W. Google usually takes p = 0.85. Then 1-p is the fraction of time that an arbitrary page is chosen. Let A be the n-by-n matrix whose elements are

a_i_j = p g_i_j / c_j + (1-p) / n.

The matrix A is not sparse, but it is a rank one modification of a sparse matrix. Most of the elements of A are equal to the small constant (1-p) / n. När n = 2.7·10⁹ är (1-p) / n = 5.5·10^-11.

The matrix is the transition probability matrix of the Markov chain. Its elements are all strictly between zero and one and its column sums are all equal to one. An important result in matrix theory, the Perron-Frobenius Theorem, applies to such matrices. It tells us that the largest eigenvalue of A is equal to one and that the corresponding eigenvector, which satisfies the equation

x = Ax,

exists and is unique to within a scaling factor. When this scaling factor is chosen so that

_ix_i = 1

then x is the state vector of the Markov chain. The elements of x are Google?s PageRank.

If the matrix were small enough to fit in MATLAB, one way to compute the eigenvector x would be to start with a good approximate solution, such as the PageRanks from the previous month, and simply repeat the assignment statement

x = Ax

until successive vectors agree to within specified tolerance. This is known as the power method and is about the only possible approach for very large n.

Prioritetskö

När man poppar en stack får man ut det senast inpushade. När man tar ut något ur en vanlig kö får man tvärtom ut det som legat längst tid i kön. Man skulle kunna se det som att det som stoppas in tidsstämplas och att det påstämplade talet ger prioriteten för uthämtning.

I en prioritetskö stämplas en prioritet på varje objekt som stoppas in och vid uthämtning får man objektet med högst prioritet.

En abstrakt prioritetskö kan ha föjande anrop.

put(p,x): Stoppa in x med påstämplad prioritet p (oftast ett heltal).
x=get(): Hämta det som har högst prioritet.
isempty(): Undersök om prioritetskön är tom.

Om det man vill stoppar in i prioritetskön är ett tal kan man använda talet självt som prioritet och bara skriva put(x). Hur den då skiljer sej från en stack och från en vanlig kö ser man av följande exempel.

      pq.put(1)
      pq.put(3)
      pq.put(2)
      x = pq.get() # x blir 3

En kö hade skickat tillbaka det först instoppade talet 1; en stack hade skickat tillbaka det senast instoppade talet, 2; prioritetskön skickar tillbaka det bästa talet, 3. I denna prioritetskö betraktar vi största talet som bäst - vi har en så kallad maxprioritetskö. Det finns förstås också minprioritetsköer, där det minsta talet betraktas som bäst.

Prioritetsköer har många användningar. Man kan tänka sej en auktion där budgivarna stoppar in sina bud i en maxprioritetskö och auktionsförrättaren efter "första, andra, tredje" gör pq.get() för att få reda på det vinnande budet. För att han ska veta vem som lagt detta bud behövs förstås båda parametrarna i pq.put(p,x).

      pq.put(bud,person)   #person är ett objekt med budgivarens namn och bud
      winner = pq.get()    #budgivaren  med högst bud

Trappa

Den bästa implementationen av en prioritetskö är en trappa, (eng heap), som är en array tab tolkad som binärträd. HEAP

Roten är tab[1], dess båda söner är tab[2] och tab[3] osv. Allmänt gäller att tab[i] har sönerna tab[2*i] och tab[2*i+1]. Trappvillkoret är att pappa är bäst, dvs varje tal ligger på två sämre tal.

Ett nytt tal läggs alltid in sist i trappan. Om trappvillkoret inte blir uppfyllt, dvs om det är större än sin far, byter far och son plats och så fortgår det tills villkoret uppfyllts. Det här kallas upptrappning och kan i värsta fall föra det nya talet hela vägen upp till toppen, alltså tab[1]. För att se till att det i alla fall stannar där kan man från början lägga in ett jättestort tal i tab[0].

Man plockar alltid ut det översta talet ur trappan och fyller igen tomrummet med det sista talet i trappan. Då är inte trappvillkoret uppfyllt, så man får byta talet och dess störste son. Denna nedtrappning upprepas till villkoret åter gäller.

Både put och get har komplexitet log N om trappan har N element. Nackdelen med trappan är man måste bestämma arrayens storlek från början.

Heapsort

Om man stoppar in N tal i en trappa och sedan hämtar ut dom ett efter ett får man dom sorterade. Nästa föreläsning ägnas helt åt sortering.

Bästaförstsökning

Labb 4 behandlar problemet att finna kortaste vägen från FAN till GUD. Man har då ett problemträd med FAN som stamfar, på nivån därunder sönerna MAN, FIN, FAT osv, på nästa nivå fans sonsöner osv. Om man lägger sönerna i en kö kommer man att gå igenom problemträdet nivå för nivå, alltså breddenförst. Om man byter kön mot en stack blir sökningen djupetförst. Med en prioritetskö får man bästaförstsökning, dvs den mest lovande sonen prioriteras och får föda söner.

Exempel 1: Sök billigaste transport från Teknis till Honolulu. All världens resprislistor finns tillgängliga.
Problemträdets poster innehåller en plats, ett pris och en faderspekare. Överst i trädet står Teknis med priset noll. Sönerna är alla platser man kan komma till med en transport och priset, till exempel T-centralen, 9.50. Man söker en Honolulupost i problemträdet. Med breddenförstsökning får man den resa som har så få transportsteg som möjligt. Med bästaförstsökning får man den billigaste resan. Detta påstående är inte helt självklart utan man får tänka en del för att inse det.

Exempel 2: Sök effektivaste processen för att framställa en önskad substans från en given substans. All världens kemiska reaktioner finns tillgängliga med uppgift om utbytet i procent.
Problemträdets poster innehåller substansnamn och procenttal. Överst i trädet står utgångssubstansen med procenttalet 100. Sönerna är alla substanser man kan framställa med en reaktion och utbytet, till exempel C2H5OH, 96%. Med en max-prioritetskö får man fram den effektivaste process som leder till målet.

Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 11 december 2003
Tekniskt stöd: <webmaster@nada.kth.se>