. Строка if (it == end_it) { return; }
нужна для прерывания рекурсии. Пустое выражение return
не делает ничего, что на первый взгляд кажется странным. Все операции вставки выполняются с привлечением выражения tries[*it]
. Оператор []
контейнера std::map
либо возвращает существующий элемент для заданного ключа, либо создает элемент с таким ключом. Связанное значение (соотнесенным типом в нашем примере является тип trie
) создается с помощью конструктора по умолчанию. Таким образом, при поиске не известных слов мы неявно создаем новую ветвь дерева.Поиск в поддереве выглядит более сложным, поскольку мы не можем выразить многие функции неявно:
template
optional>
subtrie(It it, It end_it) const {
if (it == end_it) { return ref(*this); }
auto found (tries.find(*it));
if (found == end(tries)) { return {}; }
return found->second.subtrie(next(it), end_it);
}
Данный код, по сути, строится вокруг выражения
auto found (tries.find(*it));
.Вместо того чтобы искать следующий по глубине узел дерева с помощью оператора (
[]
), мы применяем метод find
. Если бы мы использовали для поиска оператор []
, то дерево создавало бы отсутствующие элементы — совсем не то, что нужно! (Кстати, попробуйте сделать это. Метод класса является константным, вследствие чего такой подход невозможен. Это поможет вам избежать некоторых ошибок.)Еще одной непонятной деталью является возвращаемый тип
optional>
. В качестве оболочки мы выбрали std::optional
, поскольку есть вероятность, что такого поддерева во входной последовательности нет. Если мы передаем только последовательность "hello my friend"
, то последовательность "goodbye my friend"
не будет существовать. В таких случаях мы просто возвращаем {}
, что передает вызывающей стороне пустой необязательный объект. Это все еще не объясняет, почему мы используем reference_wrapper
вместо optional
. Идея заключается в том, что необязательному экземпляру, имеющему переменную-член с типом trie&
, нельзя повторно присвоить значение и поэтому код не скомпилируется. Реализация ссылки с помощью reference_wrapper
приведет к тому, что у вас появится возможность присваивать значения объектам повторно. Создаем генератор поисковых подсказок с помощью префиксных деревьев
Когда вы вводите некие символы в поисковик, интерфейс зачастую пытается определить, как будет выглядеть весь поисковый запрос. Эти догадки зачастую основываются на популярных запросах. Иногда подобные догадки выглядят довольно забавно, поскольку оказывается, что люди вводят в поисковик странные запросы (рис. 6.2).
В этом разделе мы используем класс
trie
, который реализовали в предыдущем примере, и создадим небольшой генератор подсказок, всплывающих при поиске.
Как это делается
В данном примере мы реализуем консольное приложение, которое принимает некие входные данные, а затем пробует определить, что именно пользователь хочет найти, основываясь на небольшой текстовой базе данных.
1. Как и всегда, сначала указываем, что включаем заголовочные файлы, а также объявляем об использовании пространства имен
std
:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
2. Воспользуемся реализацией из предыдущего примера:
template
class trie
{
map tries;
public:
template
void insert(It it, It end_it) {
if (it == end_it) { return; }
tries[*it].insert(next(it), end_it);
}
template
void insert(const C &container) {
insert(begin(container), end(container));
}
void insert(const initializer_list
&il) {
insert(begin(il), end(il));
}
void print(list&l) const {
if (tries.empty()) {
copy(begin(l), end(l), ostream_iterator{cout, " "});
cout << '\n';
}
for (const auto &p : tries) {
l.push_back(p.first);
p.second.print(l);
l.pop_back();
}
}
void print() const {
list l;
print(l);
}
template
optional>
subtrie(It it, It end_it) const {
if (it == end_it) { return ref(*this); }
auto found (tries.find(*it));
if (found == end(tries)) { return {}; }
return found->second.subtrie(next(it), end_it);
}
template
auto subtrie(const C &c) const {
return subtrie(begin(c), end(c));
}
};
3. Добавим небольшую вспомогательную функцию, которая выводит на экран строку, приглашающую пользователя ввести какой-нибудь текст:
static void prompt()
{
cout << "Next input please:\n > ";
}
4. В функции
main
открываем текстовый файл, который играет роль нашей текстовой базы данных. Мы считываем данный файл строка за строкой и передаем эти строки в дерево:
int main()
{
trie t;
fstream infile {"db.txt"};
for (string line; getline(infile, line);) {
istringstream iss {line};
t.insert(istream_iterator{iss}, {});
}
5. Теперь, когда мы создали дерево на основе содержимого текстового файла, нужно реализовать интерфейс, который позволит пользователю отправлять запросы. Приглашаем пользователя ввести какой-нибудь текст и ожидаем его действий:
prompt();
for (string line; getline(cin, line);) {
istringstream iss {line};
6. Имея введенный текст, мы делаем запрос к дереву, чтобы получить поддерево. Если у нас есть такая входная последовательность в текстовом файле, то можем вывести на экран возможное продолжение поискового запроса, как делают другие поисковики. При отсутствии соответствующего поддерева просто скажем об этом пользователю: