1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
/*
* Copyright (C) 2012 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef LATINIME_BLOOM_FILTER_H
#define LATINIME_BLOOM_FILTER_H
#include <stdint.h>
#include "defines.h"
namespace latinime {
// This bloom filter is used for optimizing bigram retrieval.
// Execution times with previous word "this" are as follows:
// without bloom filter (use only hash_map):
// Total 147792.34 (sum of others 147771.57)
// with bloom filter:
// Total 145900.64 (sum of others 145874.30)
// always read binary dictionary:
// Total 148603.14 (sum of others 148579.90)
class BloomFilter {
public:
BloomFilter() {
ASSERT(BIGRAM_FILTER_BYTE_SIZE * 8 >= BIGRAM_FILTER_MODULO);
}
// TODO: uint32_t position
AK_FORCE_INLINE void setInFilter(const int32_t position) {
const uint32_t bucket = static_cast<uint32_t>(position % BIGRAM_FILTER_MODULO);
mFilter[bucket >> 3] |= static_cast<uint8_t>(1 << (bucket & 0x7));
}
// TODO: uint32_t position
AK_FORCE_INLINE bool isInFilter(const int32_t position) const {
const uint32_t bucket = static_cast<uint32_t>(position % BIGRAM_FILTER_MODULO);
return (mFilter[bucket >> 3] & static_cast<uint8_t>(1 << (bucket & 0x7))) != 0;
}
private:
// Size, in bytes, of the bloom filter index for bigrams
// 128 gives us 1024 buckets. The probability of false positive is (1 - e ** (-kn/m))**k,
// where k is the number of hash functions, n the number of bigrams, and m the number of
// bits we can test.
// At the moment 100 is the maximum number of bigrams for a word with the current
// dictionaries, so n = 100. 1024 buckets give us m = 1024.
// With 1 hash function, our false positive rate is about 9.3%, which should be enough for
// our uses since we are only using this to increase average performance. For the record,
// k = 2 gives 3.1% and k = 3 gives 1.6%. With k = 1, making m = 2048 gives 4.8%,
// and m = 4096 gives 2.4%.
// This is assigned here because it is used for array size.
static const int BIGRAM_FILTER_BYTE_SIZE = 128;
static const int BIGRAM_FILTER_MODULO;
uint8_t mFilter[BIGRAM_FILTER_BYTE_SIZE];
};
} // namespace latinime
#endif // LATINIME_BLOOM_FILTER_H
|
