if (auto st (t.subtrie(istream_iterator{iss}, {}));
st) {
cout << "Suggestions:\n"; st->get().print();
} else {
cout << "No suggestions found.\n";
}
7. Затем снова выведем текст приглашения и подождем следующей строки от пользователя. На этом все.
cout << "----------------\n";
prompt();
}
}
8. Прежде чем запустить программу, следует чем-то заполнить файл
db.txt
. В нем может быть все что угодно, его даже не нужно сортировать. Каждая строка текста будет одной последовательностью дерева.
do ghosts exist
do goldfish sleep
do guinea pigs bite
how wrong can you be
how could trump become president
how could this happen to me
how did bruce lee die
how did you learn c++
what would aliens look like
what would macgiver do
what would bjarne stroustrup do
...
9. До запуска программы нужно создать файл
db.txt
. Его содержимое может выглядеть следующим образом:
hi how are you
hi i am great thanks
do ghosts exist
do goldfish sleep
do guinea pigs bite
how wrong can you be
how could trump become president
how could this happen to me
how did bruce lee die
how did you learn c++
what would aliens look like
what would macgiver do
what would bjarne stroustrup do
what would chuck norris do
why do cats like boxes
why does it rain
why is the sky blue
why do cats hate water
why do cats hate dogs
why is c++ so hard
10. Компиляция и запуск программы с последующим вводом некоторых входных данных будут выглядеть так:
$ ./word_suggestion
Next input please:
> what would
Suggestions:
aliens look like
bjarne stroustrup do
chuck norris do
macgiver do
----------------
Next input please:
> why do
Suggestions:
cats hate dogs
cats hate water
cats like boxes
----------------
Next input please:
>
Как это работает
Принцип работы префиксного дерева был показан в предыдущем примере, но способ его заполнения и создания запросов к нему выглядит несколько странно. Давайте подробнее рассмотрим фрагмент кода, который заполняет пустое дерево на основе содержимого текстовой базы данных:
fstream infile {"db.txt"};
for (string line; getline(infile, line);) {
istringstream iss {line};
t.insert(istream_iterator{iss}, {});
}
Цикл заполняет строку
line
содержимым текстового файла строка за строкой. Затем мы копируем строку в объект istringstream
. Из этого объекта можно создать итератор istream_iterator
, который нам еще пригодится, поскольку наше дерево принимает не только экземпляр контейнера для поиска поддеревьев, но и итераторы. Таким образом, нет нужды создавать вектор или список слов и можно непосредственно принять строку. Избежать последней части ненужных выделений памяти позволит перемещение содержимого строки в iss
. К сожалению, объект типа std::istringstream
не предоставляет конструктор, который принимает перемещаемые значения типа std::string
. Тем не менее он скопирует свою входную строку.При чтении пользовательских входных данных, которые нужно найти в дереве, мы применяем точно такую же стратегию, но не задействуем файловый поток ввода. Вместо этого мы прибегаем к
std::cin
. В нашем случае это сработает аналогично, поскольку trie::subtrie
работает для итераторов точно так же, как и trie::insert
.
Дополнительная информация
Можно добавить в каждый узел дерева переменные-счетчики. Это позволит определить, как часто префикс встречается в некоторых входных данных. На основе этой информации можно отсортировать предположения по частоте их встречаемости, что и делают поисковики. Подсказки, возникающие при наборе текста на смартфоне, также реализованы подобным образом.
Предлагаю вам создать этот вариант генератора подсказок в качестве самостоятельного упражнения.
Реализуем формулу преобразования Фурье с применением численных алгоритмов STL
Преобразование Фурье — это очень важная и очень известная формула в области обработки сигналов. Она была открыта примерно 200 лет назад, но с появлением компьютеров количество вариантов ее использования значительно увеличилось. Она применяется при сжатии аудио/изображений/видео, в аудиофильтрах, медицинских устройствах отображения, приложениях для телефонов, которые определяют, какая песня сейчас играет, и т.д.
Поскольку количество возможных вариантов применения данной формулы довольно велико (и не только преобразования Фурье), STL разрабатывалась так, чтобы приносить пользу и при выполнении вычислений. Преобразование Фурье — лишь один из многих примеров подобных вычислений, при этом не самый простой. Сама формула выглядит так (рис. 6.3):
Преобразование, описываемое этой формулой, по сути, описывает сумму. Каждый элемент суммы является произведением точки графика вектора входного сигнала и выражения
exp(-2*i*...)
. Вычисления, стоящие за даннойформулой, могут озадачить всех, кто незнаком с комплексными числами (и тех, кому просто не нравится математика), но освоить пример можно и не понимая эту формулу полностью. Если взглянуть на нее поближе, то увидим, что все точки графика сигнала (N
элементов) суммируются с помощью переменной цикла j
. Переменная k
— еще одна переменная цикла, поскольку преобразование Фурье вычисляет не одно значение, а целый вектор. В данном векторе каждая точка графика представляет собой интенсивность и фазу определенной частоты повторяющейся волны. При реализации этой формулы с помощью циклов получится примерно такой код:
csignal fourier_transform(const csignal &s) {
csignal t(s.size());
const double pol {-2.0 * M_PI / s.size()};
for (size_t k {0}; k < s.size(); ++k) {
for (size_t j {0}; j < s.size(); ++j) {
t[k] += s[j] * polar(1.0, pol * k * j);
}
}
return t;
}
Тип
csignal
может быть вектором, содержащим комплексные числа. Для работы с такими числами в STL существует класс std::complex
. Функция std::polar
, по сути, выполняет часть exp(–i*2*...).Эта версия работает хорошо, но давайте реализуем преобразование Фурье с помощью инструментов, доступных в STL.
Как это делается
В данном примере мы реализуем преобразование Фурье, а затем трансформируем с его помощью некоторые сигналы.