1. Зачем нужен индекс
Если вы только начинаете программировать, «поиск» часто выглядит так: берём все книги, идём по очереди и проверяем, подходит ли каждая. Это понятный и честный подход: мы буквально делаем то, что делает человек, когда смотрит на полку и читает корешки. Проблема в том, что компьютер умеет делать это быстро… но не бесконечно быстро.
Представьте, что в библиотеке 10 книг — всё отлично. 1000 книг — уже «ну ладно». 100 000 книг — и вот вы внезапно начинаете задумчиво смотреть в окно, пока программа ищет «Swift». А если поиск вызывается часто (например, пользователь делает 20 запросов подряд), то каждый раз снова «прочёсывать всю базу» — это как каждый раз заново раскладывать весь шкаф, чтобы найти носок.
Индекс — это идея из реальной жизни: у библиотек есть не только книги, но и каталог. Каталог говорит: «слово ‘swift’ встречается в таких-то карточках → вот ID книг». Мы строим такой каталог в памяти, чтобы повторные запросы обрабатывались быстро.
В Swift мы реализуем индекс в виде:
Dictionary<Token, Set<BookID>>
То есть: токен (слово поиска) → множество идентификаторов книг, где это слово встречается. Такую структуру удобно собирать и очень удобно использовать для поиска через пересечение множеств (intersection). А Dictionary в Swift как раз хорош в роли «быстрой таблицы по ключу», и у него есть полезная штука dict[key, default: ...], которая сильно упрощает код «добавь, если ключа ещё нет».
2. Модель индекса
Когда вы впервые видите Dictionary<Token, Set<BookID>>, мозг может честно спросить: «А почему так сложно? Почему не Dictionary<String, [Book]>?» Вопрос нормальный: мозг вообще любит простые решения. Но мы сейчас аккуратно разложим эту конструкцию на смысловые кирпичи.
Token — нормализованное слово
Под Token мы будем понимать строку после нормализации. Нормализация — это «привести к единому виду», чтобы поиск был предсказуемым. Например, Swift, swift и SWIFT должны стать одним и тем же токеном swift. Иначе поиск внезапно становится «капризным»: нашёл одно, не нашёл другое.
Обычно в нашем учебном проекте достаточно такого правила: привести к нижнему регистру и разбить по пробелам. Это не лингвистика уровня «поиск Google», но зато это детерминированно: один и тот же текст всегда превращается в один и тот же набор токенов.
Почему Set<BookID>, а не [BookID]
Если у книги в названии слово «swift» встретилось дважды (да, бывают названия в стиле «Swift: Swift Swift»), то в индексе мы не хотим хранить ID два раза. Нам нужно «присутствует / не присутствует», а не «сколько раз встречается». Это как список приглашённых на вечеринку: если Вася записан три раза, он всё равно один Вася (и пиццу он тоже съест один… ну почти).
Set гарантирует уникальность элементов и даёт удобные операции множеств, например пересечение (intersection). Это важный момент: «поиск по нескольким словам» мы будем делать именно через пересечение множеств. И это стандартная операция Set в Swift.
Почему BookID должен быть Hashable
И Dictionary, и Set работают на хешировании. Это означает: ключи словаря и элементы множества должны соответствовать протоколу Hashable. Именно поэтому BookID мы делаем Hashable, а Token у нас — это String, который уже Hashable «из коробки».
Swift умеет синтезировать Hashable (и Equatable) автоматически для многих типов, и это реально спасает новичков от ручного написания хеша (потому что ручной хеш — это как ручной парашют: сделать можно, но лучше не надо без опыта).
Небольшая табличка, чтобы «уложить» структуру в голове:
| Сущность | Тип | Зачем нужна |
|---|---|---|
|
|
Нормализованное «слово поиска» |
|
|
Стабильный идентификатор книги |
|
|
Уникальные книги для одного токена + пересечения |
|
|
Быстро: по слову получить кандидатов |
3. Токенизация
Токенизация — это тот этап, где программист часто попадает в ловушку «сделаю идеально». Хочется учитывать знаки препинания, дефисы, кавычки, эмодзи, китайский, клингонский… и вот вы уже пишете свою поисковую систему, вместо того чтобы закончить репозиторий. Поэтому в учебном проекте мы выбираем простые правила и фиксируем их как контракт.
Главное в токенизации для индекса — не «идеальность», а одинаковость. Одинаковость означает: мы используем одну и ту же функцию токенизации и для данных (когда строим индекс по книгам), и для запроса (когда пользователь вводит «swift basics»). Если правила расходятся, индекс превращается в красивую, но бесполезную декоративную штуку.
Начнём с очень простого правила: привести строку к нижнему регистру, убрать лишние пробелы по краям и разбить по любому whitespace.
import Foundation
typealias Token = String
func tokenize(_ text: String) -> [Token] {
let normalized = text
.lowercased()
.trimmingCharacters(in: .whitespacesAndNewlines)
return normalized
.split(whereSeparator: { $0.isWhitespace })
.map { String($0) }
}
Обратите внимание: это маленький, читаемый код. Здесь нет магии. И да, он не убирает запятые и точки — но зато он стабилен. Если вы хотите «слегка лучше» (без погружения в сложные темы), можно аккуратно выкинуть пунктуацию и оставить только буквы/цифры — но тогда правило должно быть таким же и для индекса, и для запроса.
Вот вариант «чуть аккуратнее», но всё ещё короткий:
import Foundation
typealias Token = String
func tokenize(_ text: String) -> [Token] {
let lowered = text.lowercased()
let cleaned = lowered.map { ch in
ch.isLetter || ch.isNumber ? ch : " "
}
return String(cleaned)
.split(whereSeparator: { $0.isWhitespace })
.map { String($0) }
}
Здесь мы заменяем «не буква и не цифра» на пробел. Это делает токены более предсказуемыми для названий вроде Swift, 6.2!. При этом правило всё равно детерминированное: один вход → один выход.
4. Строим индекс из booksByID
Теперь — самая приятная часть: мы берём наш источник правды booksByID и строим по нему индекс. Важно прямо проговорить: индекс не является источником правды. Источник правды — это booksByID, потому что там хранится «полная» книга. Индекс — производная структура, оптимизация.
Сначала зафиксируем доменные типы (упрощённо, как в нашем учебном проекте):
import Foundation
struct BookID: Hashable, Codable {
let rawValue: UUID
}
struct Book: Codable {
let id: BookID
var title: String
}
Теперь функция построения индекса. Мы делаем Dictionary<Token, Set<BookID>>, а наполнение делаем через index[token, default: []].insert(id). Эта форма сабскрипта — стандартная возможность Swift для словаря: «дай значение по ключу, а если его нет — используй дефолт».
import Foundation
typealias SearchIndex = [Token: Set<BookID>]
func buildIndex(booksByID: [BookID: Book]) -> SearchIndex {
var index: SearchIndex = [:]
for book in booksByID.values {
let tokens = tokenize(book.title)
for token in tokens {
index[token, default: []].insert(book.id)
}
}
return index
}
Обратите внимание на пару вещей.
Во-первых, мы итерируемся по booksByID.values, потому что booksByID — источник правды, и мы хотим индекс строить из истины, а не из чего-то вторичного.
Во-вторых, мы храним в индексе только ID, а не сами Book. Это экономит память и сильно упрощает поддержку консистентности: у Book может измениться название, а индекс можно пересобрать или обновить отдельно. Если бы мы хранили внутри индекса целые Book, мы бы получили два места, где живёт одна и та же сущность — а это прямой путь к багам «почему поиск отдаёт старое название?».
5. Поиск по индексу
AND по словам через пересечение множеств
Самый вкусный трюк этого дня: если пользователь вводит несколько слов, например swift basics, мы хотим найти книги, где встречаются оба слова. Это логика «AND». В индексной модели это превращается в пересечение множеств:
- берём множество книг по swift
- берём множество книг по basics
- делаем intersection
И получаем книги, которые есть и там, и там.
Set.intersection — это стандартная операция множеств в Swift.
Сначала напишем функцию, которая на вход получает токены запроса и индекс, а на выход — Set<BookID> кандидатов:
import Foundation
func idsMatchingAllTokens(
_ tokens: [Token],
in index: SearchIndex
) -> Set<BookID> {
guard let first = tokens.first else { return [] }
var result = index[first] ?? []
for token in tokens.dropFirst() {
let next = index[token] ?? []
result = result.intersection(next)
}
return result
}
Здесь важно поведение для крайних случаев.
Если токенов нет (пустой запрос, или запрос состоял из одних пробелов), мы возвращаем пустой результат. Это бизнес-решение: иногда делают «пустой запрос → все книги», но тогда вы внезапно превращаете поиск в «показать всё», и UI/CLI-слой должен быть к этому готов. В этом курсе безопаснее считать, что пустой запрос не несёт смысла.
Если какого-то токена нет в индексе, index[token] будет nil, и мы заменим это на пустое множество. Пересечение с пустым множеством даёт пустое множество — то есть «нет книг, где встречаются все слова». Логика прозрачная и математически честная.
Резолвим BookID обратно в Book
Индекс даёт нам ID, но пользователю нужны книги. Поэтому следующий шаг: «зарезолвить» найденные ID через booksByID.
import Foundation
func resolveBooks(
ids: Set<BookID>,
booksByID: [BookID: Book]
) -> [Book] {
return ids.compactMap { id in
booksByID[id]
}
}
Здесь compactMap делает полезную вещь: если вдруг ID есть в индексе, но книги в booksByID нет, мы просто не добавим nil в результат. В нормальной жизни такого быть не должно (мы же следим за консистентностью), но аккуратная обработка не ломает код, а добавляет устойчивости.
Если хотите, можно сделать сортировку, чтобы результаты выглядели стабильнее:
import Foundation
func resolveBooksSortedByTitle(
ids: Set<BookID>,
booksByID: [BookID: Book]
) -> [Book] {
let books = ids.compactMap { booksByID[$0] }
return books.sorted(by: { a, b in a.title < b.title })
}
6. Компонент BookSearchIndex и связь с репозиторием
Чтобы код не превращался в «россыпь функций по проекту», удобно собрать логику индекса в отдельный тип. Это не «архитектура ради архитектуры», а просто способ держать ответственность в одном месте: «вот компонент, который умеет строить индекс и искать ID».
Сделаем класс (или struct — можно и так, и так). В учебном проекте часто удобно final class, потому что индекс — это изменяемое состояние (мы его строим, а затем используем).
import Foundation
final class BookSearchIndex {
private var index: SearchIndex = [:]
func rebuild(from booksByID: [BookID: Book]) {
index = buildIndex(booksByID: booksByID)
}
func searchIDs(query: String) -> Set<BookID> {
let tokens = tokenize(query)
return idsMatchingAllTokens(tokens, in: index)
}
}
Теперь репозиторий может выглядеть концептуально так: у него есть booksByID (источник правды) и searchIndex (ускоритель). А поиск работает в два шага: получить IDs из индекса, затем получить книги из booksByID.
Например:
import Foundation
final class InMemoryBookRepository {
private var booksByID: [BookID: Book] = [:]
private let searchIndex = BookSearchIndex()
func search(query: String) -> [Book] {
let ids = searchIndex.searchIDs(query: query)
return resolveBooksSortedByTitle(ids: ids, booksByID: booksByID)
}
}
Да, тут остаётся вопрос: «когда вызывать rebuild?» Но это уже про жизненный цикл индекса и поддержку при add/update/remove. Сейчас наша цель — понять, как устроена структура индекса и как выполняется запрос. А момент, когда и как индекс обновляется, мы аккуратно решаем отдельно, чтобы не смешивать две разные темы в один комок.
7. Схема потока поиска
Иногда проще один раз увидеть схему, чем пять раз перечитать код. Ниже «конвейер поиска» в терминах нашей модели:
flowchart TD
Q[query: String] --> T["tokenize(query)"]
T --> TOKENS["tokens: [Token]"]
TOKENS --> I[SearchIndex: Dictionary<Token, Set<BookID>>]
I --> IDS[ids: Set<BookID>]
IDS --> R[resolve through booksByID]
R --> BOOKS["result: [Book]"]
Смысл схемы простой: индекс — это не магия, а всего лишь ускоренная «дорога» от токена к набору ID. А потом мы возвращаемся к источнику правды, чтобы получить полноценные сущности.
8. Типичные ошибки
Ошибка №1: разные правила токенизации для индекса и для запроса.
Очень легко сделать так: при построении индекса вы разбили названия по пробелам, а в запросе ещё убрали пунктуацию или сделали другой lowercased(). В итоге пользователь вводит то же самое слово, а индекс «не узнаёт» его. Лечится просто: одна функция tokenize, один набор правил, один источник истины.
Ошибка №2: хранить в индексе массивы вместо множеств.
Если вместо Set<BookID> вы используете [BookID], то у вас появляются дубликаты, а операция «найти книги, где есть все слова» превращается в ручной ад с вложенными циклами. Set здесь не украшение, а смысловая часть решения: уникальность плюс пересечение как готовая операция множеств.
Ошибка №3: пытаться хранить в индексе целые Book.
Кажется, что так «удобнее»: сразу достал список книг и вернул. Но вы получаете два хранилища одной сущности: booksByID и индекс. Они легко расходятся при любом изменении, и вы начинаете ловить призраков: «почему поиск показывает старое название?». Индекс должен хранить только ID, а книги нужно доставать из источника правды.
Ошибка №4: забыть, что Set и Dictionary требуют Hashable.
Новички иногда делают struct BookID без Hashable, а потом удивляются ошибке компиляции. Это нормальная ошибка: компилятор буквально говорит «я не умею хранить это в хеш-таблице». Решение: сделать BookID : Hashable (обычно это синтезируется автоматически), и помнить, что ключи словаря и элементы множества должны быть хешируемыми.
Ошибка №5: не зафиксировать поведение пустого запроса.
Если query == "", что должен вернуть поиск? Пусто? Все книги? Ошибку? Любой вариант возможен, но его нужно выбрать и держаться его последовательно. Иначе UI/CLI слой будет вести себя странно: иногда пустая строка — это «покажи всё», иногда — «ничего не найдено». В этой лекции мы выбрали простое и безопасное правило: пустой запрос даёт пустой результат.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ