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
|
#include "search/v2/locality_scorer.hpp"
#include "search/v2/token_slice.hpp"
#include "std/algorithm.hpp"
namespace search
{
namespace v2
{
// static
size_t const LocalityScorer::kDefaultReadLimit = 100;
namespace
{
bool IsAlmostFullMatch(NameScore score)
{
return score == NAME_SCORE_FULL_MATCH_PREFIX || score == NAME_SCORE_FULL_MATCH;
}
} // namespace
// LocalityScorer::ExLocality ----------------------------------------------------------------------
LocalityScorer::ExLocality::ExLocality() : m_numTokens(0), m_rank(0), m_nameScore(NAME_SCORE_ZERO)
{
}
LocalityScorer::ExLocality::ExLocality(Geocoder::Locality const & locality)
: m_locality(locality)
, m_numTokens(locality.m_endToken - locality.m_startToken)
, m_rank(0)
, m_nameScore(NAME_SCORE_ZERO)
{
}
// LocalityScorer ----------------------------------------------------------------------------------
LocalityScorer::LocalityScorer(QueryParams const & params, Delegate const & delegate)
: m_params(params), m_delegate(delegate)
{
}
void LocalityScorer::GetTopLocalities(size_t limit, vector<Geocoder::Locality> & localities) const
{
vector<ExLocality> ls;
ls.reserve(localities.size());
for (auto const & locality : localities)
ls.emplace_back(locality);
RemoveDuplicates(ls);
LeaveTopByRank(std::max(limit, kDefaultReadLimit), ls);
SortByName(ls);
if (ls.size() > limit)
ls.resize(limit);
localities.clear();
localities.reserve(ls.size());
for (auto const & l : ls)
localities.push_back(l.m_locality);
}
void LocalityScorer::RemoveDuplicates(vector<ExLocality> & ls) const
{
sort(ls.begin(), ls.end(), [](ExLocality const & lhs, ExLocality const & rhs)
{
if (lhs.GetId() != rhs.GetId())
return lhs.GetId() < rhs.GetId();
return lhs.m_numTokens > rhs.m_numTokens;
});
ls.erase(unique(ls.begin(), ls.end(),
[](ExLocality const & lhs, ExLocality const & rhs)
{
return lhs.GetId() == rhs.GetId();
}),
ls.end());
}
void LocalityScorer::LeaveTopByRank(size_t limit, vector<ExLocality> & ls) const
{
if (ls.size() <= limit)
return;
for (auto & l : ls)
l.m_rank = m_delegate.GetRank(l.GetId());
sort(ls.begin(), ls.end(), [](ExLocality const & lhs, ExLocality const & rhs)
{
if (lhs.m_rank != rhs.m_rank)
return lhs.m_rank > rhs.m_rank;
return lhs.m_numTokens > rhs.m_numTokens;
});
ls.resize(limit);
}
void LocalityScorer::SortByName(vector<ExLocality> & ls) const
{
vector<string> names;
for (auto & l : ls)
{
names.clear();
m_delegate.GetNames(l.GetId(), names);
auto score = NAME_SCORE_ZERO;
for (auto const & name : names)
{
score = max(score, GetNameScore(name, v2::TokenSlice(m_params, l.m_locality.m_startToken,
l.m_locality.m_endToken)));
}
l.m_nameScore = score;
}
sort(ls.begin(), ls.end(), [](ExLocality const & lhs, ExLocality const & rhs)
{
if (IsAlmostFullMatch(lhs.m_nameScore) && IsAlmostFullMatch(rhs.m_nameScore))
{
// When both localities match well, e.g. full or full prefix
// match, the one with larger number of tokens is selected. In
// case of tie, the one with better score is selected.
if (lhs.m_numTokens != rhs.m_numTokens)
return lhs.m_numTokens > rhs.m_numTokens;
if (lhs.m_nameScore != rhs.m_nameScore)
return lhs.m_nameScore > rhs.m_nameScore;
}
else
{
// When name scores differ, the one with better name score is
// selected. In case of tie, the one with larger number of
// matched tokens is selected.
if (lhs.m_nameScore != rhs.m_nameScore)
return lhs.m_nameScore > rhs.m_nameScore;
if (lhs.m_numTokens != rhs.m_numTokens)
return lhs.m_numTokens > rhs.m_numTokens;
}
// Okay, in case of tie we select the one with better rank. This
// is a quite arbitrary decision and definitely may be improved.
return lhs.m_rank > rhs.m_rank;
});
}
} // namespace v2
} // namespace search
|
