Самый быстрый поиск подстроки. Префиксные и суффиксные деревья. (Prefix/Suffix trees, trie)

Подробнее о видео

#DevJungles #dotnet #ityoutubers

Telegram канал Dev Jungles -

Поддержать канал можно:
- Спонсорством на YouTube
- Переводом на карту или пополнением банки монобанка:
Dev Jungles YouTube Channel Fund


Номер карты банки:
5375 4112 0230 1466

- Или криптой:
BTC - 18C3jsFYwviN5FvzpAt4uMWRfUeVKvdWxy
ETH - 0x2903f63ba9009732272e91a299053b9d7b623216

USDT on ERC20 - 0x2903f63ba9009732272e91a299053b9d7b623216
USDT on TRC20 - TSmS5RzQKbWdxZkoM2oRo9HK8FYBaq744T

LTC - LN3CkrnvZLZTXDUhqTy1gUKMVpLjEPA4G2

DOGE - DPwon439jf3axVSBwyuXso6z7CivuJF655
AAVE - 0x2903f63ba9009732272e91a299053b9d7b623216
Waves - 3P8D57Zw7CrqW2o7dHpvZR2UzAzQRFA2kZd

Нам очень часто нужно искать содержит ли одна строка указанную(Contains), часто нужно проверять начинается ли строка с заданной(StartsWith), а изредка проверять заканчивается ли (EndsWith). Если строк не очень много, а искать нужно не часто, то решение в лоб, может себя отлично показать, но иногда его не хватает.
В прошлом() видео рассказывал про полнотекстовый индекс(Full Text Index) и поиск(Full Text Search), эта концепция включает в себя целый ворох алгоритмов и структур данных. О части из них я рассказал, но часть осталась за кадром или была упомянута лишь вскольз. Одна из них, мне кажется интереснее прочих и о ней хочу рассказать, и закодить вживую(livecoding).

Префиксные и суффиксные деревья (Prefix/Suffix trees) это такая структура данных в которой строки раскладываются так, что бы поиск по ним занимал не O(n), а ~O(1). Ну по крайней мере не зависел бы от количества строк по которым нужно искать, а зависел бы только от их длины.

Материалы из видео и датасет:


Таймкоды:

0:00 Вступление
3:26 Постановка проблемы
8:34 Проверка на существование заданной строки в массиве
11:21 Benchmark: проверка полного вхождения
16:08 Тюнинг с использованием HashSet
23:58 Сравнение результатов
26:06 Построение и визуализация префиксного дерева
32:40 Метод добавления слов в дерево
40:43 Реализация поиска по дереву
48:57 Benchmark: Поиск слова в тексте: Array vsHashSet vs SortedSet vs PrefixTree
53:16 Реализация алгоритма StartsWith для всех тестируемых коллекций
1:19:02 Создание бенчмарка для StartsWith
1:29:46 Разгоняем префиксное дерево
1:32:08 Алгоритм ContainsSubstring и Суффиксные деревья
1:46:59 Профилировка памяти