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
148
149
|
#pragma once
#include "geocoder/hierarchy.hpp"
#include "geocoder/index.hpp"
#include "geocoder/result.hpp"
#include "geocoder/types.hpp"
#include "base/beam.hpp"
#include "base/geo_object_id.hpp"
#include "base/stl_helpers.hpp"
#include "base/string_utils.hpp"
#include <cstddef>
#include <string>
#include <thread>
#include <unordered_map>
#include <utility>
#include <vector>
namespace geocoder
{
// This class performs geocoding by using the data that we are currently unable
// to distribute to mobile devices. Therefore, the class is intended to be used
// on the server side.
// On the other hand, the design is largely experimental and when the dust
// settles we may reuse some parts of it in the offline mobile application.
// In this case, a partial merge with search/ and in particular with
// search/geocoder.hpp is possible.
//
// Geocoder receives a search query and returns the osm ids of the features
// that match it. Currently, the only data source for the geocoder is
// the hierarchy of features, that is, for every feature that can be found
// the geocoder expects to have the total information about this feature
// in the region subdivision graph (e.g., country, city, street that contain a
// certain house). This hierarchy is to be obtained elsewhere.
//
// Note that search index, locality index, scale index, and, generally, mwm
// features are currently not used at all.
class Geocoder
{
public:
// A Layer contains all entries matched by a subquery of consecutive tokens.
struct Layer
{
Type m_type = Type::Count;
std::vector<Index::DocId> m_entries;
};
// This class is very similar to the one we use in search/.
// See search/geocoder_context.hpp.
class Context
{
public:
struct BeamKey
{
BeamKey(base::GeoObjectId osmId, Type type, std::vector<Type> const & allTypes, bool allTokensUsed)
: m_osmId(osmId)
, m_type(type)
, m_allTypes(allTypes)
, m_allTokensUsed(allTokensUsed)
{
base::SortUnique(m_allTypes);
}
base::GeoObjectId m_osmId;
Type m_type;
std::vector<Type> m_allTypes;
bool m_allTokensUsed;
};
Context(std::string const & query);
void Clear();
std::vector<Type> & GetTokenTypes();
size_t GetNumTokens() const;
size_t GetNumUsedTokens() const;
Type GetTokenType(size_t id) const;
std::string const & GetToken(size_t id) const;
void MarkToken(size_t id, Type type);
// Returns true if |token| is marked as used.
bool IsTokenUsed(size_t id) const;
// Returns true iff all tokens are used.
bool AllTokensUsed() const;
void AddResult(base::GeoObjectId const & osmId, double certainty, Type type,
std::vector<Type> const & allTypes, bool allTokensUsed);
void FillResults(std::vector<Result> & results) const;
std::vector<Layer> & GetLayers();
std::vector<Layer> const & GetLayers() const;
void SetHouseNumberBit() { m_surelyGotHouseNumber = true; }
private:
Tokens m_tokens;
std::vector<Type> m_tokenTypes;
size_t m_numUsedTokens = 0;
// Sticky bit that records a heuristic check whether
// the current query contains a house number.
// The rationale is that we must only emit buildings in this case
// and implement a fallback to a more powerful geocoder if we
// could not find a building.
bool m_surelyGotHouseNumber = false;
// The highest value of certainty for a fixed amount of
// the most relevant retrieved osm ids.
base::Beam<BeamKey, double> m_beam;
std::vector<Layer> m_layers;
};
explicit Geocoder(std::string const & pathToJsonHierarchy, unsigned int loadThreadsCount = 1);
explicit Geocoder(std::istream & jsonHierarchy, unsigned int loadThreadsCount = 1);
void ProcessQuery(std::string const & query, std::vector<Result> & results) const;
Hierarchy const & GetHierarchy() const;
Index const & GetIndex() const;
private:
explicit Geocoder(Hierarchy && hierarchy, unsigned int loadThreadsCount);
void Go(Context & ctx, Type type) const;
void FillBuildingsLayer(Context & ctx, Tokens const & subquery, Layer & curLayer) const;
void FillRegularLayer(Context const & ctx, Type type, Tokens const & subquery,
Layer & curLayer) const;
// Returns whether any of the paths through |layers| can be extended
// by appending |e|.
bool HasParent(std::vector<Geocoder::Layer> const & layers, Hierarchy::Entry const & e) const;
Hierarchy m_hierarchy;
Index m_index;
};
} // namespace geocoder
|