Cad atá i nBloom filter agus cén socrú a dhéanann sé?

Question

Accepted Answer

Is é **Bloom filter** ná struchtúr **dóchúlach** atá éifeachtach ó thaobh spáis de a fhreagraíonn ceistean ar bhallraíochta i tacar le cas amháin: is féidir go mbeidh **fálbhréaga** ann ach **ní bheidh fálbhréaga claonta ann riamh**. Tá "Cinnte nach bhfuil sé i láthair" cinnte; "B'fhéidir go bhfuil sé i láthair" de dhíth ar sheiceáil fíor.

## Conas a oibríonn sé

Eagar giotán de `m` giotáin agus `k` fheidhmeanna hash. Chun **a chur leis** rud, socraigh na `k` ghiotáin a scanntar sé. Chun **a iarraidh**, seiceáil na `k` ghiotáin sin — má tá ceann ar bith acu ina 0, tá an rud cinnte go bhfuil sé as láthair.

```text
bits: [0 0 0 0 0 0 0 0]
add "cat":  hash->bits 1,4,6  -> [0 1 0 0 1 0 1 0]
query "dog": hashes to 1,3,6 -> bit 3 is 0 -> DEFINITELY absent
query "cat": all of 1,4,6 set -> "probably present"
```

## Cód

```python
class BloomFilter:
    def __init__(self, m, hashes):
        self.bits = [0]*m
        self.m, self.hashes = m, hashes   # list of hash fns
    def add(self, x):
        for h in self.hashes:
            self.bits[h(x) % self.m] = 1
    def __contains__(self, x):            # False = certain; True = maybe
        return all(self.bits[h(x) % self.m] for h in self.hashes)
```

| Oibríochtaí | Am | Spás |
|---|---|---|
| add | O(k) | O(m) giotáin |
| query | O(k) | — |

Níl fálbhréaga claonta ann; foluain an ráta fálbhréaga ar aghaidh agus `m` (agus `k` intuigthe) fás.

## Socrúcháin

- **Láidreachtaí:** Marc cuimhne an-beag i gcomparáid le stóráil iarbhír na gcnaipe; oibríochtaí am tairbhiúil.
- **Laigí:** fálbhréaga; **ní féidir a dhíchur** (bloim-scagaire caighdeánach); ní féidir ba bhall a liostáil.

## Cén fáth a bhfuil sé tábhachtach

Gnáth-dhea-bhrí go bog ar scagairí bloom obair chostasach a sheachaint: bainc shonraí (m.sh. Cassandra, HBase) a úsáid chun a sheachaint a léamh ó dhiosca le haghaidh eochracha atá **cinnte** nach bhfuil siad ar dhiosca.

Tuaidh síad athrú clasaiceach an chórais — glacadh le ráta beag earráide i gcomhchosúint ar gheal-laghdú i cuimhne agus E/S.