Індекс для пошуку: Dictionary<Token, Set<BookID>>

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) автоматично для багатьох типів, і це справді рятує новачків від ручного написання хеша (бо ручний хеш — це як ручний парашут: зробити можна, але без досвіду краще не треба).

Невелика таблиця, щоб краще впорядкувати структуру в голові:

Token

String

BookID

struct, Hashable

Set<BookID>

множина

Dictionary<Token, Set<BookID>>

словник

3. Токенізація

Токенізація — це той етап, де програміст часто потрапляє в пастку «зроблю ідеально». Хочеться врахувати розділові знаки, дефіси, лапки, емодзі, китайську, клінгонську… і ось ви вже пишете власну пошукову систему, замість того щоб завершити репозиторій. Тому в навчальному проєкті ми обираємо прості правила й фіксуємо їх як контракт.

Головне в токенізації для індексу — не ідеальність, а однаковість. Однаковість означає: ми використовуємо одну й ту саму функцію токенізації і для даних (коли будуємо індекс за книгами), і для запиту (коли користувач вводить «swift basics»). Якщо правила розходяться, індекс перетворюється на красиву, але марну декоративну річ.

Почнемо з дуже простого правила: привести рядок до нижнього регістру, прибрати зайві пробіли по краях і розбити за будь-яким пробільним символом.

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[запит: String] --> T["tokenize(query)"]
    T --> TOKENS["токени: [Token]"]
    TOKENS --> I[SearchIndex: Dictionary<Token, Set<BookID>>]
    I --> IDS[ID: Set<BookID>]
    IDS --> R[зіставити через booksByID]
    R --> BOOKS["результат: [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-шар поводитиметься дивно: інколи порожній рядок — це «покажи все», інколи — «нічого не знайдено». У цій лекції ми обрали просте й безпечне правило: порожній запит дає порожній результат.