Поиск на основе триграмм

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

Microsoft выпустила tgrep — инструмент для очень быстрого поиска текста по большим кодовым базам. Он уже используется внутри GitHub Copilot CLI.

Главное отличие tgrep от обычного grep или ripgrep в том, что он использует предварительно построенный индекс.

Обычный поиск при каждом запросе проходит по файлам проекта и проверяет их содержимое. ripgrep делает это очень эффективно и быстро, но принцип остаётся тем же: файлы нужно просмотреть при выполнении поиска.

tgrep сначала индексирует проект. Во время индексации он анализирует содержимое файлов и создаёт специальный триграммный индекс. Триграмма — это последовательность из трёх символов. Для каждой такой последовательности индекс хранит информацию о том, в каких файлах она встречается.

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

Например, если в репозитории 500 тысяч файлов, поиск не обязательно будет читать все 500 тысяч. Индекс может показать, что подходящие файлы находятся, например, среди нескольких сотен — и проверить нужно уже их.

При этом индекс не остаётся статичным. tgrep может работать в режиме сервера, который отслеживает изменения в проекте и обновляет индекс при изменении файлов.

Именно поэтому основное преимущество tgrep проявляется при повторных поисках в очень больших репозиториях.

В тестах Microsoft поиск по Firefox занимал у ripgrep около 33 секунд, а у tgrep — около 643 миллисекунд. Для Chromium результаты составляли примерно 41 секунду против 2,6 секунды, а для Linux — 5,4 секунды против 256 миллисекунд.

То есть в зависимости от проекта поиск может ускоряться в несколько, десятки и даже больше раз.

При этом tgrep не является безусловной заменой ripgrep. Для небольших проектов предварительная индексация может быть просто не нужна. Если нужно один раз найти что-то в нескольких тысячах файлов, обычный ripgrep зачастую будет проще.

tgrep имеет смысл там, где кодовая база очень большая, а поиск выполняется постоянно.

По сути, его основная идея довольно простая: не искать одно и то же по всему проекту заново при каждом запросе, а заранее создать индекс и использовать его для следующих поисков.

Для агентных ИИ такая система поиска тоже может быть очень полезна. Агенту часто приходится много раз искать по исходному коду: находить функции, классы, места использования переменных, похожие участки кода или конкретные реализации. Если проект большой, использование индексированного поиска позволяет выполнять такие операции значительно быстрее и не тратить время на повторное сканирование всей кодовой базы.

В RAG-системах принцип похожий. Вместо того чтобы каждый раз просматривать весь набор документов или файлов, можно использовать индекс для быстрого определения релевантных документов, а уже затем передавать найденное содержимое модели. При этом tgrep не заменяет векторный поиск: это другой подход. Его сильная сторона — очень быстрый точный поиск по содержимому, который можно использовать как отдельный этап retrieval или вместе с семантическим поиском.

#indexsearch

📟 Прилетело из @solidityset