# Lokalne indeksy trigramowe Cursor przyspieszają wyszukiwanie regex w dużych repozytoriach
W Cursor wprowadzono lokalne indeksy do wyszukiwania regex bezpośrednio w IDE. Rozwiązuje to problem wolnego skanowania dużych monorepo, gdzie klasyczny ripgrep zużywa 15+ sekund na wywołanie, a agent AI generuje dziesiątki takich zapytań.
Technologia opiera się na inwertowanym indeksie trigramowym z 1993 roku. Tekst jest dzielony na wszystkie 3-znakowe sekwencje (trigramy), które służą jako klucze w słowniku. Każdy klucz odpowiada liście plików zawierających tę sekwencję. Zapytanie regex jest dekomponowane na zestaw trigramów, listy postingów są przecinane w celu wybrania kandydatów. Następnie grep jest stosowany tylko do kilkunastu plików zamiast tysięcy.
Sparse n-grams do precyzyjnego scopingu
Na bazowym indeksie dodano sparse n-grams. Długość każdego n-gram jest obliczana deterministycznie: poprzez wagi par znaków na podstawie crc32 lub tabeli częstotliwości zbudowanej na terabajtach kodu open-source.
Podczas indeksowania generowane są wszystkie możliwe n-grams, podczas wyszukiwania — minimalny pokrywający zbiór. To zmniejsza liczbę lookupów i zwiększa precyzję filtrowania.
// Przykład dekómpozycji regex w n-grams
regex: \w+@\w+\.com
n-grams: ['@', 'w+', '.c', 'com', ...] // sparse pokrycie
candidates = intersect(postings(ngrams))Lokalne przechowywanie i powiązanie z commitem
Indeks jest przechowywany lokalnie na maszynie użytkownika w dwóch plikach mmap. Powody:
- Agent AI i tak czyta pliki lokalnie do ostatecznej weryfikacji.
- Sieciowe roundtripy niszczą zysk w prędkości.
Indeks jest powiązany z konkretnym git-commitem. Niekompletnie zmiany są nakładane na wierzch bez przebudowy.
- Zalety mmap: zerowy overhead na załadowanie, szybka nawigacja po listach postingów.
- Aktualizacja: wyzwalana przez git pull/push lub ręczną przebudowę.
- Rozmiar: proporcjonalny do codebase, dla 10M LoC — ~500MB.
Porównanie wydajności
| Podejście | Czas na zapytanie (10k plików) | Kandydaci dla grep |
|--------------------|--------------------------------|--------------------|
| ripgrep | 15–20 s | 10k |
| Indeks Cursor | 50–200 ms | 10–50 |
W rzeczywistych scenariuszach z 100+ zapytaniami od agenta całkowite przyspieszenie osiąga 100x.
Trigramy zapewniają pełność (recall=1 dla dokładnych podciągów), sparse n-grams dodają precyzję bez fałszywych pozytywów.
Co ważne
- Indeks trigramowy redukuje kandydatów z tysięcy do kilkunastu plików.
- Sparse n-grams minimalizują lookupy poprzez minimalny pokrywający zbiór.
- Lokalne przechowywanie mmap eliminuje opóźnienia sieciowe.
- Powiązanie z git-commitem z overlayem niekompletnie zmian.
- Przyspieszenie wyszukiwania regex o 100x dla agentów AI w dużych monorepo.
— Editorial Team
Brak komentarzy.