Расширенные структуры данных и алгоритмы: «Попытки»

Создание собственного Google с помощью Tries: давайте заглянем внутрь потенциальной реализации поисковой системы

Мы все привыкли встраивать какой-то поиск в наши веб-приложения, особенно если мы рассматриваем «создание», просто добавляя плагин Algolia в наш проект и вызывая их API с помощью их SDK.

Действительно, реализовать базовый поиск в веб-приложении уже не так сложно.

Но задумывались ли вы когда-нибудь о том, какие алгоритмы используются за этой «завесой» под названием API?

Сегодня мы рассмотрим то, что мне нравится называть «расширенной» структурой данных, которую можно использовать для выполнения текстового поиска в большом текстовом корпусе, она называется «Попытки».

Я лично не слышал о них до недавнего времени, так что я не удивлюсь, если это было и в вашем случае. Не волнуйтесь, они звучат неприятнее, чем есть на самом деле.

Давайте взломать!

Что такое попытки?

Первое, что нужно понять, это то, что Попытки — это особый вид Дерева. Мы все знаем деревья, это просто способ организации объектов Node, в котором каждый узел может иметь различное количество дочерних элементов Node. Если узел не имеет потомков, он называется «листовым узлом» (сохраняя аналогию с «деревом»).

Теперь попытки являются особенными в том смысле, что каждый узел может иметь до 26 дочерних элементов, отсортированных по алфавиту (имейте в виду, если вы хотите использовать другой алфавит, это число будет варьироваться, но все узлы будут иметь одинаковое максимальное количество дочерних элементов). .

Кроме того, слова вставляются «вертикально» (или уровнями) по всему дереву. Позвольте мне показать вам, как выглядит Trie:

Корень Trie всегда будет «нулевым», это одна из ключевых характеристик этой структуры данных. Вы можете видеть, что я добавил к нему 4 слова:

• Все
• Альт
• Кот
• Корова

Вы можете читать их по вертикали, это то, что я ранее имел в виду под «уровнями». Каждый уровень будет позицией в нашем слове. Последний узел каждого слова также будет помечен флагом «isFinal», чтобы обозначить тот факт, что слово на этом закончилось. Через минуту мы увидим, насколько актуален этот флаг.

Вы также можете отметить тот факт, что всякий раз, когда у узла есть несколько дочерних элементов, они сортируются в алфавитном порядке, потому что такая сортировка упростит алгоритмы, используемые для вставки данных и их последующего поиска. Помните, мы имеем дело с предположением, что мы работаем только с 26 буквами от «а» до «z» в нижнем регистре. Если вы хотите иметь больше гибкости, вы можете увеличить это число и найти правильный способ индексации ваших узлов.

Итак, давайте посмотрим, как мы могли бы реализовать две самые основные операции с Tries: вставка данных и их последующий поиск.

Понравилось ли вам то, что вы прочитали? Подпишитесь на мой БЕСПЛАТНЫЙ информационный бюллетень, где я делюсь со всеми своим 20-летним опытом работы в ИТ-индустрии. Присоединяйтесь к Бродяге старого разработчика!

Вставка данных в Trie

Основной алгоритм, необходимый для вставки данных в эту структуру данных, прост:

1. Слово, которое вы пытаетесь вставить, строчными буквами.
2. Найдите первую букву вашего слова внутри дочерних узлов корня.
3. Письмо находится на ожидаемом месте? Если она есть, перейдите к следующей букве вашего слова и найдите ее внутри дочерних элементов текущей буквы, которую вы только что нашли.
4. Письмо не найдено? Затем добавьте новый узел и перейдите к следующей букве вашего слова.

Вы будете продолжать, пока не закончатся буквы, в этом случае отметьте последнюю как «isFinal», и все готово.

Например, если вы добавляете слово «ALL» к пустому Trie, вы должны сделать:

1. Нижний регистр на «все»
2. Имеет ли корень «а» на первом дочернем узле? Нет, потому что он пуст, поэтому мы добавим новый узел в первый дочерний слот.
3. Теперь мы переходим к первому «l», которого нет на 12-м потомке «a», потому что последний был только что добавлен. Итак, мы добавим новый узел для «l» в 12-й дочерний слот.
4. Переходя к последней «л», делаем то же самое: ищем 12-й дочерний слот внутри предыдущей буквы (первой «л»), а так как она пуста, создадим новый Узел для последней «л». ». Единственная разница в том, что мы также пометим его как «isFinal».

Если мы сейчас хотим добавить в него слово «alt», мы обнаружим, что первые две буквы уже есть, поэтому мы просто пропустим часть, где мы добавляем эти узлы.

Давайте посмотрим на код, чтобы понять, как это переводится в JavaScript:

Узел очень просто структурировать, если честно, даже атрибут label является необязательным, поскольку фактическое положение узла будет определять букву, которую он представляет. Тем не менее, я думаю, что так легче понять, поэтому не стесняйтесь делать с ним все, что хотите.

Теперь реальный Trie выглядит так:

Как видите, при создании «корневой» узел инициализируется как null, а затем всякий раз, когда мы вставляем новое слово, мы начинаем с дочерних элементов корня и двигаемся оттуда.

Затем последний узел слова помечается isFinalLetter, чтобы мы знали, где слово закончилось. Это станет актуальным, как только мы увидим, как выполняется поиск.

Поиск данных внутри Trie

Поиск на самом деле очень похож на вставку, потому что мы должны пройти Trie по тем же алгоритмам, только если искомой буквы там нет, вместо ее добавления мы возвращаем false .

Теперь другая небольшая деталь о поиске заключается в том, что в конце слова, если мы нашли все буквы, нам также нужно будет проверить, помечен ли последний найденный узел как isFinalLetter. Если это так, это означает, что слово присутствовало в Trie, в противном случае это означает, что мы ищем подстроку вставленного слова, поэтому мы фактически получили «частичное» совпадение.

По сути, представьте, что в вашем Trie есть слово «Words».

1. Если вместо этого вы ищете «хочу», то к тому времени, когда мы доберемся до «а», мы не найдем его внутри дочерних элементов «w», поэтому его там нет.
2. Если вместо этого мы ищем «слово», мы доберемся до «d», но это «d» не будет помечено как isFinalLetter, поэтому мы будем знать, что «слово» находится не внутри Trie, а в каком-то другом слово, которое содержит это.

Давайте теперь посмотрим, как это выглядит в коде:

Это тот же класс, что и раньше, но с методом search, поэтому его легче читать.

Этот метод возвращает одно из трех значений:

• false если совпадений нет.
• full-match, если мы дойдем до последней буквы нашего слова, а последняя буква на самом деле помечена как isFinalLetter
• partial-match если мы дошли до конца, но последняя буква не помечена.

Обратите внимание, что в этом методе я заменил forEach на обычный for, потому что с последним я могу вернуться раньше с помощью простого оператора return, тогда как первый не отпускал меня, пока я не закончу чтение всего слова.

В следующем примере используется все, что мы видели до сих пор:

Результат, как и следовало ожидать, выглядит так:

Looking for 'fer':  full-match
Looking for 'angel':  null
Looking for 'fernando2':  null
Looking for 'federico':  full-match
Looking for 'fern':  partial-match

Но давайте сделаем еще один шаг вперед, потому что эксперимент интересный, но как мы можем использовать это в реальном приложении? Давайте посмотрим, как добавить это в приложение Next, не так ли?!

Использование нашего Trie-поиска внутри Next

Вы можете использовать любой фреймворк, какой захотите, я выбрал Next, потому что он также предоставляет хороший фреймворк API.

Я просто создам новое приложение с npx create-next-app@latest .

Внутри структуры папок нового приложения я создам следующие новые папки:

• /components куда я добавлю новый компонент Search.
• /utils, где я сохраню свою папку tries (с классами, которые я только что показал вам), и куда я добавлю новый файл search.js, который будет действовать как шлюз к нашему Trie.

Я оставлю службу поиска на сервере, поэтому мы будем взаимодействовать с ней через конечную точку API, которую мы добавим в папку pages/api/search.

К концу ваша структура папок должна выглядеть так:

Добавление конечной точки поиска

В этом примере конечная точка поиска будет очень простой. Мы обработаем все запросы и будем искать параметр запроса q, в котором будет храниться наша строка поиска.

Итак, весь код выглядит так:

Мы будем беспокоиться о функции getSearch через секунду, теперь все, что вам нужно знать о ней, это то, что она дает вам доступ к вашему экземпляру Trie.

Добавление компонента пользовательского интерфейса поиска

Нам также понадобится компонент пользовательского интерфейса, чтобы наши пользователи могли что-то искать и показывать им какую-то обратную связь.

В нашем случае отзыв будет «не найдено», «частичное совпадение» или «полное совпадение», но вы можете проявить творческий подход.

Код нашего компонента выглядит так:

Опять же, ничего особенного, просто компонент, выполняющий запрос Fetch к нашему новому API каждый раз, когда поле ввода изменяется. Возможно, вы сможете найти способы улучшить это и уменьшить количество запросов.

Вот как это выглядит после рендеринга (здесь нет стилей, так что будьте осторожны, это уродливо!):

Я же говорил!

Давайте теперь посмотрим на функцию getSearch, потому что она делает кое-что интересное.

Поисковый шлюз

Чтобы убедиться, что мы можем что-то искать, мы сначала должны вставить это «что-то» в наш Trie, так когда же мы это делаем?

Я решил загрузить «корпус» нашей поисковой системы первым поисковым запросом, а затем мы сохраним Trie в памяти и позаботимся о том, чтобы не перезаписать его, реализуя базовый одноэлементный шаблон, подобный этому. :

Как вы понимаете, я вызываю функцию loadIndex, которая добавляет несколько слов к нашему Trie, когда я впервые создаю фактический экземпляр Trie, затем все, что я делаю, — это возвращаю экземпляр, созданный в первый раз.

Это аккуратный способ сохранить один экземпляр на протяжении всего выполнения вашего приложения.

Если вы хотите просмотреть этот пример более подробно, вы можете получить код здесь. Получайте удовольствие!

Слышали ли вы раньше о Tries? Или даже лучше, вы использовали их для чего-нибудь? Поделитесь своим опытом в комментариях, мне будет интересно узнать, что вы сделали!

Создавайте приложения с повторно используемыми компонентами, такими как Lego.

Инструмент с открытым исходным кодом Bit помогает более чем 250 000 разработчиков создавать приложения с компонентами.

Превратите любой пользовательский интерфейс, функцию или страницу в компонент многократного использования — и поделитесь им со своими приложениями. Легче сотрудничать и строить быстрее.

→ Подробнее

Разделите приложения на компоненты, чтобы упростить разработку приложений, и наслаждайтесь наилучшими возможностями для рабочих процессов, которые вы хотите:

→ Микро-интерфейсы

→ Система дизайна

→ Совместное использование кода и повторное использование

→ Монорепо

Узнать больше