bitvektor

Bitvektor er en endimensjonal tabell av bit som er lagret i påfølgende dataord. Hvert bit i dataordet lagrer en logisk verdi 0 eller 1, sant eller ikke sant, ja eller nei. Bitene identifiseres ved sin posisjon fra \(1\) til \(n\). Antall dataord som brukes for å lagre \(n\) bit er \(\lceil n/b \rceil \) når \(b\) er antall bit per dataord.

Faktaboks

Også kjent som

filter, bitfilter og bitmap (eng.)

\( \begin{array}{rlll} &\texttt{Eksempelvektor} & & \\ \texttt{pos} & 1& 17 & 33 \\ \texttt{bit} & {00001111\,01010000} & {00000100\,11100001} & {00100100\,10100000} \end{array} \)

Eksempelet viser en bitvektor som er lagret i 16-bits dataord. Bitvektor er en effektiv lagringsform, og data fra flere bitvektorer kan kombineres gjennom logiske operasjoner (boolske operasjoner).

Bruk

Bitvektor er en generell type datastruktur. Den er særlig nyttig internt i databaseprogrammer og programmer for informasjonsgjenfinning. En bitvektor kalles da ofte et filter. Den brukes for å filtrere vekk søking etter verdier som ikke finnes, det vil si verdier som ikke er lagret i databasen.

Eksempel

Vi kan bruke bitvektor for å effektivisere kontroll av bankkortnummer. Databasen inneholder ugyldige nummer. Hvert ugyldig nummer som er lagret har laget et spor i en bitvektor. Alle bit har verdien 0 ved start. Etter hvert som ugyldige nummer lagres settes bit nummer \( i=hash (nummer, N) \) i filteret. Hash er en funksjon som beregner et tall mellom \(0\) og \(N-1\) basert på kortnummeret. \(N\) er et tall som er noen ganger (8 til 20) større enn antall kortnummer som blir lagret i databasen.

Når en senere skal kontrollere om et kortnummer er gyldig vil en først beregne hashverdien til kortnummeret. Hvis tilhørende bit i filteret er 0 betyr det at aktuelt kortnummer ikke finnes i databasen. Hvis beregnet bit er satt (har verdien 1), må en kontrollere videre i databasen om det faktisk er aktuelt kortnummer som har ført til at bit er satt. Hvis filteret er 10 ganger større enn antall verdier i databasen er det \(1/10\) sannsynlighet for at "uskyldig" nummer slipper gjennom filteret. Men en kan la en lagret post (kortnummer) sette spor i to filtre. Hvis begge filtrene er 10 ganger større enn antall lagrede verdier, er sannsynligheten bare 1% for at uskyldige poster skal gå gjennom begge filtrene. De to hashformlene for å beregne bitposisjon må være uavhengige av hverandre.

Bitvektorer er relativt små datastrukturer som kan få tilnærmet permanent plass i arbeidslager under drift. Med en fornuftig dimensjonerig av filtre kan en avgjøre mer enn 99% av alle søk uten å slå opp i selve databasen. Det betinger at mindre enn 1% av kortbruken gjøres med ugyldige kort.

Les mer i Store norske leksikon

Kommentarer

Kommentarer til artikkelen blir synlig for alle. Ikke skriv inn sensitive opplysninger, for eksempel helseopplysninger. Fagansvarlig eller redaktør svarer når de kan. Det kan ta tid før du får svar.

Du må være logget inn for å kommentere.

eller registrer deg

Fagansvarlig for Databaseteknologi

Tore Mallaug
Universitetslektor, NTNU – Norges teknisk-naturvitenskapelige universitet