Блог ·
Поиск без индекса
Большинство поисковых систем строят индекс — таблицу, где каждому слову сопоставлены документы, в которых оно встречается. У Блокнотика индекса нет. Каждый раз, когда вы печатаете букву в строке поиска, он просматривает полный текст каждой заметки. Звучит расточительно, поэтому вот доводы и цифры.
Во что обошёлся бы индекс
Индекс — это вторая копия заметок в другом виде. Его нужно построить при первом запуске, обновлять при каждом сохранении и держать в согласии с файлами, которые другие программы меняют у него за спиной: программа синхронизации, Git, редактор на другом компьютере. Когда они расходятся, получается худший вид ошибки: заметка есть, а найти её нельзя.
Индекс на диске — это ещё и лишний файл в папке с заметками, а Блокнотик старается не класть туда ничего, чего вы не писали сами.
Что Блокнотик делает вместо этого
При запуске и всякий раз, когда что-то могло измениться, Блокнотик обходит папку с заметками. Для каждого файла .md он сравнивает размер и время изменения с тем, что уже знает, и перечитывает только изменившиеся. В памяти лежат две версии каждой заметки: текст как есть и «свёрнутая» копия — строчными буквами, с е вместо ё и ss вместо ß.
Запрос разбирается на части — слова, фразы в кавычках, -исключения, фильтры tag: — и сворачивается так же. Затем для каждой заметки:
- каждая обычная часть запроса должна встречаться в свёрнутом тексте (простой поиск подстроки);
- ни одна исключённая встречаться не должна;
- фильтры по тегам сверяются со списком тегов заметки.
Подходящие заметки получают оценку: много — за слово в названии, понемногу — за каждое вхождение в тексте (не больше десяти на слово, чтобы одна огромная заметка не заслонила всё остальное), а при равенстве выигрывает более свежая. Первые 200 возвращаются с отрывком вокруг первого совпадения.
Цифры
В тестах есть замер: 5000 заметок примерно по 300 слов (2 КБ) каждая, всего 10 МБ текста, и запрос rye starter -invoice. На мини-ПК, где разрабатывается Блокнотик, — четырёхъядерной плате x86, ничем не быстрой, — один поиск занимает около 20 миллисекунд. Это меньше, чем можно заметить во время набора. Несколько сотен заметок — около миллисекунды.
Время растёт линейно вместе с объёмом текста. На 100 МБ заметок поиск занял бы примерно 200 мс, и это уже чувствуется. Вряд ли многие держат столько текста в личных заметках, но если вы из таких, Блокнотик вам пока не подходит, и лучше сказать это прямо.
Что теряется без индекса
- Нет морфологии и правил языка. Поиск подстроки покрывает большинство окончаний (
ржаннаходит ржаная и ржаной), но не знает, что люди — это множественное число от человек. - Нет терпимости к опечаткам.
закавскане найдёт ничего. - Нет «умного» ранжирования. Оценка простая и предсказуемая — название, частота, свежесть, — и нам так больше нравится.
Что выигрываем
Результаты поиска всегда в точности соответствуют тому, что лежит на диске прямо сейчас. Нечего перестраивать, нечему портиться, а весь поиск — около 250 строк на Go, которые читаются за десять минут (search.go в архиве с исходниками).