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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
#include "keyword_matcher.hpp"
#include "indexer/search_delimiters.hpp"
#include "indexer/search_string_utils.hpp"
#include "base/stl_add.hpp"
#include "std/algorithm.hpp"
namespace search
{
KeywordMatcher::KeywordMatcher()
{
Clear();
}
void KeywordMatcher::Clear()
{
m_keywords.clear();
m_prefix.clear();
}
void KeywordMatcher::SetKeywords(StringT const * keywords, size_t count, StringT const & prefix)
{
m_keywords.assign(keywords, keywords + count);
m_prefix = prefix;
}
KeywordMatcher::ScoreT KeywordMatcher::Score(string const & name) const
{
return Score(NormalizeAndSimplifyString(name));
}
KeywordMatcher::ScoreT KeywordMatcher::Score(StringT const & name) const
{
buffer_vector<StringT, MAX_TOKENS> tokens;
SplitUniString(name, MakeBackInsertFunctor(tokens), Delimiters());
// Some names can have too many tokens. Trim them.
return Score(tokens.data(), tokens.size());
}
KeywordMatcher::ScoreT KeywordMatcher::Score(StringT const * tokens, size_t count) const
{
count = min(count, size_t(MAX_TOKENS));
vector<bool> isQueryTokenMatched(m_keywords.size());
vector<bool> isNameTokenMatched(count);
uint32_t sumTokenMatchDistance = 0;
int8_t prevTokenMatchDistance = 0;
bool bPrefixMatched = true;
for (int i = 0; i < m_keywords.size(); ++i)
for (int j = 0; j < count && !isQueryTokenMatched[i]; ++j)
if (!isNameTokenMatched[j] && m_keywords[i] == tokens[j])
{
isQueryTokenMatched[i] = isNameTokenMatched[j] = true;
int8_t const tokenMatchDistance = i - j;
sumTokenMatchDistance += abs(tokenMatchDistance - prevTokenMatchDistance);
prevTokenMatchDistance = tokenMatchDistance;
}
if (!m_prefix.empty())
{
bPrefixMatched = false;
for (int j = 0; j < count && !bPrefixMatched; ++j)
if (!isNameTokenMatched[j] &&
StartsWith(tokens[j].begin(), tokens[j].end(), m_prefix.begin(), m_prefix.end()))
{
isNameTokenMatched[j] = bPrefixMatched = true;
int8_t const tokenMatchDistance = int(m_keywords.size()) - j;
sumTokenMatchDistance += abs(tokenMatchDistance - prevTokenMatchDistance);
}
}
uint8_t numQueryTokensMatched = 0;
for (size_t i = 0; i < isQueryTokenMatched.size(); ++i)
if (isQueryTokenMatched[i])
++numQueryTokensMatched;
ScoreT score;
score.m_bFullQueryMatched = bPrefixMatched && (numQueryTokensMatched == isQueryTokenMatched.size());
score.m_bPrefixMatched = bPrefixMatched;
score.m_numQueryTokensAndPrefixMatched = numQueryTokensMatched + (bPrefixMatched ? 1 : 0);
score.m_nameTokensMatched = 0;
score.m_nameTokensLength = 0;
for (size_t i = 0; i < count; ++i)
{
if (isNameTokenMatched[i])
score.m_nameTokensMatched |= (1 << (MAX_TOKENS-1 - i));
score.m_nameTokensLength += tokens[i].size();
}
score.m_sumTokenMatchDistance = sumTokenMatchDistance;
return score;
}
KeywordMatcher::ScoreT::ScoreT()
: m_sumTokenMatchDistance(0), m_nameTokensMatched(0), m_nameTokensLength(0),
m_numQueryTokensAndPrefixMatched(0), m_bFullQueryMatched(false), m_bPrefixMatched(false)
{
}
bool KeywordMatcher::ScoreT::operator < (KeywordMatcher::ScoreT const & s) const
{
if (m_bFullQueryMatched != s.m_bFullQueryMatched)
return m_bFullQueryMatched < s.m_bFullQueryMatched;
if (m_numQueryTokensAndPrefixMatched != s.m_numQueryTokensAndPrefixMatched)
return m_numQueryTokensAndPrefixMatched < s.m_numQueryTokensAndPrefixMatched;
if (m_bPrefixMatched != s.m_bPrefixMatched)
return m_bPrefixMatched < s.m_bPrefixMatched;
if (m_nameTokensMatched != s.m_nameTokensMatched)
return m_nameTokensMatched < s.m_nameTokensMatched;
if (m_sumTokenMatchDistance != s.m_sumTokenMatchDistance)
return m_sumTokenMatchDistance > s.m_sumTokenMatchDistance;
return false;
}
bool KeywordMatcher::ScoreT::LessInTokensLength(ScoreT const & s) const
{
if (m_bFullQueryMatched)
{
ASSERT(s.m_bFullQueryMatched, ());
return m_nameTokensLength > s.m_nameTokensLength;
}
return false;
}
string DebugPrint(KeywordMatcher::ScoreT const & score)
{
ostringstream out;
out << "KeywordMatcher::ScoreT(";
out << "FQM=" << score.m_bFullQueryMatched;
out << ",nQTM=" << static_cast<int>(score.m_numQueryTokensAndPrefixMatched);
out << ",PM=" << score.m_bPrefixMatched;
out << ",NTM=";
for (int i = MAX_TOKENS-1; i >= 0; --i)
out << ((score.m_nameTokensMatched >> i) & 1);
out << ",STMD=" << score.m_sumTokenMatchDistance;
out << ")";
return out.str();
}
} // namespace search
|
