Differential D13747 Diff 36811 src/engine/fuzzysearch.cpp

Changeset View

Standalone View

src/engine/fuzzysearch.cpp

This file was added.

1		#include "fuzzysearch.h"
2
3		#include <algorithm>
4
5		using namespace Baloo;
6
7
8		FuzzySearch::FuzzySearch(int tolerance)
9		: m_tolerance(tolerance)
10		{
11		}
12
13
14		QList<FuzzyFeature> FuzzySearch::word_to_features(const QString& term)
15		{
16		QList<FuzzyFeature> grams;
17		if (term.size() < 2) {
18		return grams;
19		}
20		grams.reserve(term.size() - 1);
21
22		// TODO: use QTextBoundaryFinder to get correct graphemes
23		for (int i = 1; i < term.size(); i += 1) {
24		grams.append(term.mid(i - 1, 2).toLower().toUtf8());
25		}
26		return grams;
27		}
28
29
30		QMap<FuzzyFeature, FuzzyDataList> FuzzySearch::features(quint64 id, QStringList terms)
31		{
32		QMap<FuzzyFeature, FuzzyDataList> output;
33		quint8 wid = 0;
34
35		for (const QString& word : terms) {
36		// Get the features for every word
37		QList<QByteArray> features = FuzzySearch::word_to_features(word);
38		// Create an inverted index of the features
39		for (const QByteArray& feature : features) {
40		// make the associated data
41		FuzzyData data;
42		data.id = id;
43		data.wid = wid;
44		data.len = word.size();
45
46		// make this feature linked to the data it came from
47		auto existing = output.find(feature);
48
49		if (existing == output.end()) {
50		// `feature` not used before, make a new one and insert
51		FuzzyDataList list;
52		list.m_datalist.append(data);
53		output.insert(feature, list);
54		}
55		else {
56		// found existing `feature`, add this id and word size to it
57		existing->m_datalist.append(data);
58		}
59		}
60		if (wid < 255) {
61		wid += 1;
62		}
63		}
64		return output;
65		}
66
67
68		QList<quint64>
69		FuzzySearch::search(const QString& query, const FuzzyDataGetter getter)
70		{
71		QList<FuzzyFeature> features = this->word_to_features(query);
72		QMap<FuzzyData, int> scores;
73
74		// Calculate how close each term is to query, the higher score the better
75		for (const FuzzyFeature& feature : features) {
76		// Get all documents of each feature
77		const FuzzyDataList& documents = getter(feature);
78		for (const FuzzyData& doc : documents.m_datalist) {
79		// Keep track of the score of each document and its length
80		auto score = scores.find(doc);
	brunsUnsubmitted Not Done You are matching for document and term here, I don't think thats what you want. bruns: You are matching for document and term here, I don't think thats what you want.
81		if (score == scores.end()) {
82		scores.insert(doc, 1);
83		}
84		else {
85		*score += 1;
86		}
87		}
88		}
89
90		// Remove based on threshold
91		QList<QPair<FuzzyData, int>> passing;
92		for (auto i = scores.begin(); i != scores.end(); ++i) {
93		if (i.value() + this->m_tolerance >= features.size()) {
94		passing.append(qMakePair(i.key(), i.value()));
95		}
96		}
97
98		// Sort based on best score & shortest word
99		std::sort(passing.begin(), passing.end(),
100		[](const QPair<FuzzyData, int>& a, const QPair<FuzzyData, int>& b) {
101		if (a.second == b.second) {
102		return a.first.len < b.first.len;
103		}
104		return a.second > b.second;
105		});
106
107		// Shed metadata and return only IDs
108		QList<quint64> ids;
109		ids.reserve(passing.size());
110		for (const QPair<FuzzyData, int>& a : passing) {
111		ids.append(a.first.id);
112		}
113
114		return ids;
115		}
116
117
118		QByteArray FuzzyDataList::into_bytes()
119		{
120		return QByteArray(); // TODO:
121		}
122
123
124		FuzzyData FuzzyDataList::from_bytes()
125		{
126		return FuzzyData(); // TODO:
127		}
128
129		bool FuzzyDataList::operator==(const FuzzyDataList &other) const
130		{
131		return other.m_datalist == m_datalist;
132		}
133
134		bool FuzzyData::operator==(const FuzzyData &other) const
135		{
136		return id == other.id && wid == other.wid && len == other.len;
137		}
138
139		bool FuzzyData::operator<(const FuzzyData &other) const
140		{
141		if (id == other.id) {
142		return wid < other.wid;
143		}
144		return id < other.id;
145		}