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.

 \( \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). 

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. 

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. 

Foreslå endringer i tekst

Foreslå bilder til artikkelen

Kommentarer

Har du spørsmål om artikkelen? Skriv her, så får du svar fra fagansvarlig eller redaktør.

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