Changeset View
Changeset View
Standalone View
Standalone View
src/engine/fuzzydb.cpp
- This file was added.
1 | #include "fuzzydb.h" | ||||
---|---|---|---|---|---|
2 | #include "documentdb.h" | ||||
3 | #include "postingdb.h" | ||||
4 | #include "postingcodec.h" | ||||
5 | #include <QtDebug> | ||||
6 | | ||||
7 | #include <QTextBoundaryFinder> | ||||
8 | | ||||
9 | using namespace Baloo; | ||||
10 | | ||||
11 | class OwningPostingIterator : public PostingIterator { | ||||
12 | public: | ||||
13 | OwningPostingIterator(); | ||||
14 | quint64 docId() const override; | ||||
15 | quint64 next() override; | ||||
16 | | ||||
17 | void push(quint64 id); | ||||
18 | | ||||
19 | private: | ||||
20 | QVector<quint64> m_vec; | ||||
21 | int m_pos; | ||||
22 | }; | ||||
23 | | ||||
24 | | ||||
25 | FuzzyDB::FuzzyDB(MDB_dbi dbi, MDB_txn* txn) | ||||
26 | : m_txn(txn) | ||||
27 | , m_dbi(dbi) | ||||
28 | { | ||||
29 | Q_ASSERT(txn != nullptr); | ||||
30 | Q_ASSERT(dbi != 0); | ||||
31 | } | ||||
32 | | ||||
33 | FuzzyDB::~FuzzyDB() | ||||
34 | { | ||||
35 | } | ||||
36 | | ||||
37 | MDB_dbi FuzzyDB::create(MDB_txn* txn) | ||||
38 | { | ||||
39 | MDB_dbi dbi; | ||||
40 | int rc = mdb_dbi_open(txn, "fuzzydb", MDB_CREATE, &dbi); | ||||
41 | Q_ASSERT_X(rc == 0, "FuzzyDB::create", mdb_strerror(rc)); | ||||
42 | | ||||
43 | return dbi; | ||||
44 | } | ||||
45 | | ||||
46 | MDB_dbi FuzzyDB::open(MDB_txn* txn) | ||||
47 | { | ||||
48 | MDB_dbi dbi; | ||||
49 | int rc = mdb_dbi_open(txn, "fuzzydb", 0, &dbi); | ||||
50 | if (rc == MDB_NOTFOUND) { | ||||
51 | qDebug() << "fuzzy open failed"; | ||||
52 | return 0; | ||||
53 | } | ||||
54 | Q_ASSERT_X(rc == 0, "FuzzyDB::open", mdb_strerror(rc)); | ||||
55 | | ||||
56 | return dbi; | ||||
57 | } | ||||
58 | | ||||
59 | void FuzzyDB::put(const QByteArray& bigram, const PostingList& list) | ||||
60 | { | ||||
61 | Q_ASSERT(!bigram.isEmpty()); | ||||
62 | Q_ASSERT(!list.isEmpty()); | ||||
63 | | ||||
64 | MDB_val key; | ||||
65 | key.mv_size = bigram.size(); | ||||
66 | key.mv_data = static_cast<void*>(const_cast<char*>(bigram.constData())); | ||||
67 | | ||||
68 | PostingCodec codec; | ||||
69 | QByteArray arr = codec.encode(list); | ||||
70 | | ||||
71 | MDB_val val; | ||||
72 | val.mv_size = arr.size(); | ||||
73 | val.mv_data = static_cast<void*>(arr.data()); | ||||
74 | | ||||
75 | int rc = mdb_put(m_txn, m_dbi, &key, &val, 0); | ||||
76 | Q_ASSERT_X(rc == 0, "FuzzyDB::put", mdb_strerror(rc)); | ||||
77 | } | ||||
78 | | ||||
79 | QByteArray FuzzyDB::raw_get(const QByteArray& bigram) | ||||
80 | { | ||||
81 | Q_ASSERT(!bigram.isEmpty()); | ||||
82 | | ||||
83 | MDB_val key; | ||||
84 | key.mv_size = bigram.size(); | ||||
85 | key.mv_data = static_cast<void*>(const_cast<char*>(bigram.constData())); | ||||
86 | | ||||
87 | MDB_val val; | ||||
88 | int rc = mdb_get(m_txn, m_dbi, &key, &val); | ||||
89 | if (rc == MDB_NOTFOUND) { | ||||
90 | return QByteArray(); | ||||
91 | } | ||||
92 | Q_ASSERT_X(rc == 0, "FuzzyDB::get", mdb_strerror(rc)); | ||||
93 | | ||||
94 | return QByteArray::fromRawData(static_cast<char*>(val.mv_data), val.mv_size); | ||||
95 | } | ||||
96 | | ||||
97 | PostingList FuzzyDB::get(const QByteArray& bigram) | ||||
98 | { | ||||
99 | QByteArray arr = this->raw_get(bigram); | ||||
100 | PostingCodec codec; | ||||
101 | return codec.decode(arr); | ||||
102 | } | ||||
103 | | ||||
104 | void FuzzyDB::sync_terms(const DocumentDB& filename_terms) | ||||
105 | { | ||||
106 | // get all words (inefficient just for the proof-of-concept) | ||||
107 | QMap<quint64, QVector<QByteArray>> terms = filename_terms.toTestMap(); | ||||
108 | | ||||
109 | // create an inverted index for bigram -> list of ids | ||||
110 | for (auto i = terms.constBegin(); i != terms.constEnd(); ++i) { | ||||
111 | | ||||
112 | for (const QByteArray& term : i.value()) { | ||||
113 | QString sterm = QString::fromUtf8(term); | ||||
114 | if (sterm.startsWith('F')) continue; | ||||
115 | | ||||
116 | QStringList bigrams = this->into_bigrams(sterm); | ||||
117 | | ||||
118 | for (const QString& bigram : bigrams) { | ||||
119 | QByteArray bytes = bigram.toUtf8(); | ||||
120 | PostingList ids = this->get(bytes); | ||||
121 | | ||||
122 | if (!ids.contains(i.key())) { | ||||
123 | ids.append(i.key()); | ||||
124 | this->put(bytes, ids); | ||||
125 | } | ||||
126 | } | ||||
127 | } | ||||
128 | } | ||||
129 | } | ||||
130 | | ||||
131 | PostingIterator* FuzzyDB::iter(const QByteArray& term) | ||||
132 | { | ||||
133 | qDebug() << "FuzzyDB::iter" << term; | ||||
134 | QMap<quint64, int> scores; | ||||
135 | QStringList bigrams = this->into_bigrams(term); | ||||
136 | | ||||
137 | // Score all possible results | ||||
138 | for (const QString& bigram : bigrams) { | ||||
139 | const QByteArray ids = this->raw_get(bigram.toUtf8()); | ||||
140 | | ||||
141 | for (int i = 0; i < ids.size(); i += sizeof(quint64)) { | ||||
142 | quint64 id = *((quint64*)(ids.constData() + i)); | ||||
143 | int bump = scores.value(id, 0) + 1; | ||||
144 | scores[id] = bump; | ||||
145 | } | ||||
146 | } | ||||
147 | | ||||
148 | OwningPostingIterator* found = new OwningPostingIterator(); | ||||
149 | | ||||
150 | // Filter away bad matches | ||||
151 | for (auto i = scores.constBegin(); i != scores.constEnd(); ++i) { | ||||
152 | if (i.value() + 2 >= bigrams.size()) { | ||||
153 | found->push(i.key()); | ||||
154 | } | ||||
155 | } | ||||
156 | | ||||
157 | return found; | ||||
158 | } | ||||
159 | | ||||
160 | QStringList FuzzyDB::into_bigrams(const QString& term) | ||||
161 | { | ||||
162 | QStringList grams; | ||||
163 | grams.reserve(term.size() - 1); | ||||
164 | | ||||
165 | // Get all the individual characters into `list` | ||||
166 | // TODO: use QTextBoundaryFinder to get bigrams | ||||
167 | | ||||
168 | // Generate bigrams here | ||||
169 | for (int i = 1; i < term.size(); i += 1) { | ||||
170 | grams.append(term.mid(i - 1, 2)); | ||||
171 | } | ||||
172 | return grams; | ||||
173 | } | ||||
174 | | ||||
175 | // OwningPostingIterator | ||||
176 | | ||||
177 | OwningPostingIterator::OwningPostingIterator() | ||||
178 | : m_vec() | ||||
179 | , m_pos(0) | ||||
180 | { | ||||
181 | } | ||||
182 | | ||||
183 | quint64 OwningPostingIterator::docId() const | ||||
184 | { | ||||
185 | if (m_pos < 0 || m_pos >= m_vec.size()) { | ||||
186 | return 0; | ||||
187 | } | ||||
188 | | ||||
189 | return m_vec[m_pos]; | ||||
190 | } | ||||
191 | | ||||
192 | quint64 OwningPostingIterator::next() | ||||
193 | { | ||||
194 | if (m_pos >= m_vec.size() - 1) { | ||||
195 | m_pos = m_vec.size(); | ||||
196 | return 0; | ||||
197 | } | ||||
198 | | ||||
199 | m_pos++; | ||||
200 | return m_vec[m_pos]; | ||||
201 | } | ||||
202 | | ||||
203 | void OwningPostingIterator::push(quint64 id) | ||||
204 | { | ||||
205 | this->m_vec.append(id); | ||||
206 | } |