Заинтересовались? Да, мы построим алгоритм для создания собственной поисковой системы.
Для этого необходимо выполнить несколько шагов. Во-первых, мы сделаем веб-скреппинг и проиндексируем полученные данные, чтобы сохранить их в базе данных в осмысленном формате. Однако здесь мы не будем этим заниматься. Мы будем искать то, что вам нужно, по этим проиндексированным данным. Итак, давайте приступим.
Проблема под рукой
Вам вдруг захотелось создать свой собственный поиск в Google. Ваш друг помогает вам на начальном этапе, но он очень туп, когда дело доходит до алгоритмов. Итак, вам нужно построить алгоритм, который может эффективно искать слово из заданного списка строк.
Здесь мы сделаем несколько предположений. Во-первых, мы предположим, что строки будут уникальными и будут состоять из одного слова каждая. Кроме того, символы строк будут от a-z.
ПРИМЕЧАНИЕ: Эти предположения нужны только для вывода алгоритма. Алгоритм, который мы будем строить, может работать со всеми символами, а также со строками из нескольких слов. Эти предположения просто позволят нам легко вывести алгоритм, а затем мы сможем обобщить наш алгоритм путем небольших модификаций.
Интуиция
Давайте сначала попробуем подумать, что мы можем сделать в этом случае.
Один из простых вариантов — хэшировать каждую строку до значения и использовать строку по мере обращения к ней. Однако в этом методе есть две проблемы. Нам нужно хранить одну и ту же часть строки дважды. Например, рассмотрим эти два случая:
[ "app", "apple" ]
Здесь очевидно, что хранение app и apple отдельно приведет к тому, что мы будем использовать больше памяти по сравнению с хранением одного из них. Поэтому возникает вопрос: можем ли мы сделать лучше?
Ответ: да, можем, однако этот метод имеет некоторые недостатки.
Мы можем использовать то, что называется триэ.
Трии — это эффективные структуры данных для поиска информации. Мы можем использовать их для получения данных более эффективно, чем массивы (однако они не имеют временной сложности O(1)).
И знаете что?
Триеры занимают меньше памяти, чем хэшмапы.
Решение
Итак, давайте реализуем нашу тройку. Прежде чем мы начнем, я хотел бы дать вам базовую структуру TrieNode (в основном это узел или вершина в тройке).
struct Node{
char val;
Node* next;
};
class TrieNode{
unordered_map<char, Node*> children;
bool endOfWord;
public:
TrieNode() {
for(char c='a'; c<='z'; c++)
children[c] = NULL;
endOfWord = false;
}
};
Вот как выглядит базовый узел трие. Здесь я принял информацию в каждом узле за символ. Это может быть что угодно — от персонажа до сложных объектов. Карта дочерних элементов будет содержать все символы в диапазоне (здесь a-z) в качестве ключей и узел для данных этого символа в качестве значения.
Итак, когда мы все это получили, настало время построить нашу тройку.
Первый шаг — понять, как она будет работать. По сути, у нас будет начальный узел (назовем его символом подстановки). Этот узел будет пустым TrieNode с нулевыми указателями в качестве всех дочерних узлов и endOfWord как false.
Теперь мы продолжаем добавлять строки в нашу тройку. Для каждой строки мы добавляем один символ в дочерние элементы тройки со значением соответствующего узла. Мы повторяем это до тех пор, пока строка не закончится. Как только она закончилась, мы помечаем endOfWord этого узла тройки как true.
void insert(string word) {
Node* curr = root;
for(char c : word) {
if(curr->children.find(c) == curr->children.end()) {
curr->children[c] = new Node();
curr = curr->children[c];
}
}
curr->endOfWord = true;
}
Мы делаем это для каждой полученной строки, и в конце концов наша тройка будет завершена.
Хорошо, теперь у нас есть наши данные. Но как нам запросить их?
Если вы поняли это до сих пор, вы уже должны были догадаться. Однако, если вы тупой (как я), то подождите. Давайте обсудим это до конца.
Итак, запрос выполняется довольно просто. Для запрашиваемого слова мы выполняем аналогичную логику и ищем символ за символом. Если в какой-то момент мы увидим, что символ, который нужен для завершения текущего слова, отсутствует, мы можем сделать вывод, что слово отсутствует в тройке и нужно идти дальше. (Случай I)
Если вы нашли все слово, но последний символ, к которому вы обратились, не имеет значения endOfWord, то, опять же, искомого слова не существует. Во всех остальных случаях вы можете найти искомое слово. (Случай II)
Рассмотрим следующий пример для случая I:
*
/
a b
| |
p e
| |
p a
| |
l r
|
e
Итак, в нашей тройке есть слова «яблоко» и «медведь». Теперь, скажем, вы ищете слово «лодка».
Вы видите, что у нас есть буква «b», но, подождите, у нас нет буквы «о» после «b». Следовательно, «лодка» не существует в нашей тройке. Теперь, допустим, вы добавите к нему «лодку». Это будет выглядеть примерно так:
*
/
a b
| /
p o e
| | |
p a a
| | |
l t r
|
e
Теперь, если вы выполните поиск по слову «boat», вы увидите, что получите все символы, а у ‘t’ также будет значение endOfWord как true.
Рассмотрим следующий пример для случая I:
*
/
a b
| /
p o e
| | |
p a a
| | |
l t r
|
e
Теперь, допустим, вы ищете слово «app». Вы заметили, что присутствует ‘a’, затем присутствует ‘p’ и следующее ‘p’ также присутствует. Однако у этого «p» endOfWord не установлен в true. Следовательно, «app» не присутствует в нашей тройке. Теперь, если вы добавите «app» в нашу тройку, она будет выглядеть примерно так.
*
/
a b
| /
p o e
| | |
p a a
| | |
l t r
|
e
Как вы можете видеть, мы пометили p значением endOfWord true и в вышеприведенном случае.
Вот как это реализовать в коде:
bool search(string word) {
Node* curr = root;
for(char c : word) {
if(curr->children.find(c) == curr->children.end()) {
return false;
}
curr = curr->children[c];
}
return curr->endOfWord;
}
Также давайте обсудим одну бонусную вещь, которую можно сделать с помощью try. Вы можете даже предсказывать слова (или символы в данном случае), которые пользователь собирается набрать следующими. Это работает по той же логике, что и выше, с небольшими изменениями.
Здесь мы просто говорим, начинается ли слово с префиксной строки. Чтобы сделать из этого функцию автоподсказки, достаточно поместить слова в массив и возвращать его вместо true (также измените тип возврата функции lol).
bool startsWith(string prefix) {
Node* curr = root;
for(char c : prefix) {
if(curr->children.find(c) == curr->children.end()) {
return false;
}
curr = curr->children[c];
}
return true;
}
На этом моя лекция закончена. Но теперь вы спросите: «Подождите! Вы упомянули, что это лучше, чем хэшмапы, и начали читать лекцию, даже не спросив, интересно ли мне это. Так действительно ли это эффективнее, чем хэшмапы?».
Так что давайте попробуем ответить на этот вопрос.
Здесь мы обходим всю тройку и посещаем каждый узел в ветви ровно один раз. Таким образом, временная сложность в худшем случае будет O(h), где h — высота тройки. Если известно, что тройка имеет N узлов, то можно даже сказать, что это займет O(logN) времени (Ура, меньше линейного!!!).
Занимаемое пространство почти постоянно, так как каждый узел имеет фиксированное число (26 в данном случае) детей. Если высота дерева равна h, то занимаемое пространство равно O(26*h) ~ O(h), что также можно интерпретировать как O(logN), если количество узлов равно N.
Как вы можете себе представить, это довольно эффективно по сравнению с наивным способом использования хэшмапы для хранения данных. Конечно, мы получили бы время поиска O(1), но заняли бы много памяти, а также отказались бы от функции автопредложения xP.
Ну что ж, вы успешно спланировали алгоритм для создания следующего поиска Google. Чего вы ждете? Иди и создай его! Не заставляйте своего друга ждать после того, как он проделал всю эту тяжелую работу по начальной индексации для вас.
Спасибо, что дочитали до конца и следите за новыми удивительными материалами, подобными этому!