std
по умолчанию:
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
2. Вся программа посвящена префиксному дереву, для которого нужно реализовать собственный класс. В нашей реализации данное дерево, по сути, является рекурсивным ассоциативным массивом, содержащим ассоциативные массивы. Каждый узел дерева содержит подобный массив, в котором соотносятся объект, имеющий тип
T
, и следующий узел префиксного дерева:
template class trie
{
map tries;
3. Код для добавления новых последовательностей элементов выглядит довольно просто. Пользователь предоставляет пару итераторов (начальный и конечный), и мы проходим по ним рекурсивно. Если он ввел данные
{1, 2, 3}
, то мы ищем значение 1
в поддереве, а затем ищем значение 2
в следующем поддереве, чтобы получить поддерево для значения 3
. Какое-то из этих поддеревьев, ранее не существовавшее, будет добавлено с помощью оператора []
контейнера std::map
.
public:
template
void insert(It it, It end_it) {
if (it == end_it) { return; }
tries[*it].insert(next(it), end_it);
}
4. Для удобства определим также отдельные функции, они дают пользователю возможность получить контейнер элементов, которые будут автоматически опрошены на предмет итераторов:
template
void insert(const C &container) {
insert(begin(container), end(container));
}
5. Чтобы позволить пользователю написать конструкцию
my_trie.insert({"a", "b", "c"});
, мы должны немного помочь компилятору вывести все типы из данной строки, поэтому добавляем функцию, которая перегружает интерфейс insert параметром типа initializer_list
:
void insert(const initializer_list&il) {
insert(begin(il), end(il));
}
6. Мы также хотим видеть содержимое дерева, поэтому нужна функция
print
. Для вывода содержимого дерева на экран можно выполнить поиск в глубину. На пути от корневого узла к первому листу мы записываем все элементы с полезной нагрузкой, которые мы уже встречали. Таким образом, мы получим полную последовательность, как только достигнем листа, и вывести ее на экран будет нетрудно. Мы видим, что достигли листа, когда функция tries.empty()
возвращает значение true
. После рекурсивного вызова функции print
мы снова выталкиваем последний элемент с полезной нагрузкой.
void print(vector&v) const {
if (tries.empty()) {
copy(begin(v), end(v), ostream
_iterator{cout, " "});
cout << '\n';
}
for (const auto &p : tries) {
v.push_back(p.first);
p.second.print(v);
v.pop_back();
}
}
7. Рекурсивная функция
print
передает ссылку на выводимый на экран список элементов, но пользователь должен вызывать ее без всяких параметров. Поэтому определяем функцию print
без параметров, в которой создается вспомогательный объект списка:
void print() const {
vector v;
print(v);
}
8. Теперь, когда мы научились создавать деревья и выводить их на экран, может понадобиться выполнить поиск по поддеревьям. Идея заключается в следующем: если дерево содержит последовательности наподобие
{a,b,c} {a,b,d,e}
и мы передаем ему последовательность {a,b}
для поиска, то поиск вернет поддерево, которое содержит части {c}
и {d, e}
. При обнаружении поддерева возвращаем ссылку const
на нее. Существует вероятность того, что такого поддерева не существует, если дерево не содержит искомой последовательности. В подобных случаях все равно нужно что-то вернуть. Здесь пригодится функция std::optional
, поскольку можно вернуть пустой необязательный объект при отсутствии совпадения.
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);
}
9. Аналогично методу
insert
предоставляем версию метода subtrie
с одним параметром, которая автоматически принимает итераторы из входного контейнера:
template
auto subtrie(const C &c) {
return subtrie(begin(c), end(c));
}
};
10. На этом все. Воспользуемся нашим новым классом
trie
в функции main
, создав экземпляр класса trie
, работающего с объектами класса std::string
, и заполнив его каким-нибудь содержимым:
int main()
{
trie t;
t.insert({"hi", "how", "are", "you"});
t.insert({"hi", "i", "am", "great", "thanks"});
t.insert({"what", "are", "you", "doing"});
t.insert({"i", "am", "watching", "a", "movie"});
11. Сначала выведем на экран все дерево:
cout << "recorded sentences:\n";
t.print();
12. Затем получим поддерево для всех входных предложений, которые начинаются со слова
"hi"
, и выведем их на экран:
cout << "\npossible suggestions after \"hi\":\n";
if (auto st (t.subtrie(initializer_list{"hi"}));
st) {
st->get().print();
}
}
13. Компиляция и запуск программы покажет, что мы действительно получим всего два предложения, начинающихся со слова
"hi "
, если запросим именно это поддерево:
$ ./trie
recorded sentences:
hi how are you
hi i am great thanks
i am watching a movie
what are you doing
possible suggestions after "hi":
how are you
i am great thanks
Как это работает
Что интересно, код для вставки последовательности слов выглядит короче и проще, чем код поиска заданного слова в поддереве. Поэтому сначала рассмотрим код вставки:
template
void trie::insert(It it, It end_it) {
if (it == end_it) { return; }
tries[*it].insert(next(it), end_it);
}
Пара итераторов
it
и end_it
представляет собой вставляемую последовательность слов. Элемент tries[*it]
выполняет поиск первого слова последовательности в поддереве, а затем с помощью конструкции .insert(next(it), end_it)
мы перезапускаем ту же функцию для найденного нижнего поддерева, переместив итератор на одно слово вперед