munin/internal/search/index.go

// Package search implementiert einen In-Memory-Volltextindex mit BM25-Ranking.
//
// # Was ist BM25?
//
// BM25 (Best Match 25) ist der Standardalgorithmus moderner Suchmaschinen —
// er steckt hinter Elasticsearch, Solr, Lucene und den meisten anderen Systemen.
// Er verbessert das ältere TF-IDF durch zwei wichtige Korrekturen:
//
//  1. Sättigungsfaktor (k1): Ein Begriff der 10x so oft vorkommt wie ein anderer
//     ist nicht 10x so relevant. Ab einem gewissen Punkt "sättigt" der Nutzen —
//     das 20. Vorkommen eines Worts bringt kaum mehr Relevanz als das 10.
//
//  2. Längennormalisierung (b): Kurze Dokumente sollen keinen unfairen Vorteil haben.
//     "Deployment" in einem 50-Wort-Artikel ist relevanter als dasselbe Wort
//     in einem 2000-Wort-Dokument, in dem es nur am Rand auftaucht.
//
// # Wie funktioniert ein invertierter Index?
//
// Statt für jeden Suchbegriff alle Dokumente zu lesen, dreht ein invertierter Index
// die Beziehung um:
//
//	Normaler Index:   Dokument → enthaltene Begriffe
//	Invertierter Index: Begriff → Dokumente die ihn enthalten
//
// Beispiel:
//
//	"deployment" → ["server-setup" (3x), "pipeline" (1x)]
//	"nginx"      → ["server-setup" (5x), "reverse-proxy" (2x)]
//
// Bei einer Suche wird nur noch in dieser Map nachgeschlagen — kein Dateisystem-Zugriff,
// keine Schleife über alle Dokumente. Das macht die Suche sehr schnell.
//
// # Implementierungsdetails
//
// Der Index ist komplett im Arbeitsspeicher (kein Dateisystem).
// Beim Serverstart wird er aus der Datenbank aufgebaut.
// Titel-Treffer werden mit Faktor 3 höher gewichtet als Body-Treffer.
// Tags werden mit Faktor 2 gewichtet.
//
// Der Index kennt keine Einträge, sondern nur Dokument-IDs — dadurch bleibt er
// unabhängig vom Datenmodell und ließe sich ohne Änderung auch für etwas anderes
// verwenden. Die Zuordnung ID → Eintrag macht der Aufrufer.
package search

import (
	"math"
	"sort"
	"strings"
	"sync"
	"unicode"
)

// BM25-Tuning-Parameter — Standardwerte aus der Originalliteratur (Robertson et al. 1994).
const (
	// bm25K1 steuert die Sättigungskurve der Termhäufigkeit.
	// Typischer Bereich: 1.2–2.0. Höher = längere Sättigungskurve.
	bm25K1 = 1.2

	// bm25B steuert die Längennormalisierung.
	// 0.0 = keine Normalisierung, 1.0 = vollständige Normalisierung.
	// 0.75 ist der Standardwert.
	bm25B = 0.75

	// titleBoost: Treffer im Titel gelten als 3x relevanter als im Body.
	// Technisch umgesetzt durch Vervielfältigung der Titel-Tokens beim Indexieren.
	titleBoost = 3

	// tagsBoost: Treffer in Tags gelten als 2x relevanter als im Body.
	tagsBoost = 2
)

// posting speichert wie oft ein Term in einem konkreten Dokument vorkommt.
// Es ist der Grundbaustein des invertierten Index.
type posting struct {
	docID string // Kennung des Dokuments — hier der Slug eines Eintrags
	freq  int    // Häufigkeit des Terms in diesem Dokument
}

// docMeta speichert die Metadaten die BM25 pro Dokument benötigt.
type docMeta struct {
	length int     // Anzahl der Terme (nach Tokenisierung und Boost)
	title  string  // Titel für die Ergebnisanzeige
	boost  float64 // Faktor auf den Endwert, 1 = neutral (siehe IndexWithBoost)
}

// Result ist ein einzelnes Suchergebnis mit BM25-Score.
type Result struct {
	DocID string  // Kennung des Dokuments — hier der Slug eines Eintrags
	Score float64 // BM25-Relevanz-Score — nur für internes Ranking, kein fester Wertebereich
}

// Index kapselt den invertierten Index und alle dazugehörigen Daten.
// Er ist threadsicher durch eine RWMutex (mehrere Leser gleichzeitig erlaubt,
// aber nur ein Schreiber auf einmal).
type Index struct {
	mu sync.RWMutex

	// invertedIndex ist der Kern: Term → Liste aller Dokumente mit Häufigkeit.
	// map[string][]posting: "nginx" → [{"server-setup", 5}, {"reverse-proxy", 2}]
	invertedIndex map[string][]posting

	// docMeta speichert Metadaten je Dokument — für BM25-Berechnungen nötig.
	docs map[string]docMeta

	// docTerms ist ein Rückwärts-Index: Dokument → Liste seiner Terme.
	// Er macht das Aktualisieren/Löschen effizient:
	// ohne ihn müsste man beim Löschen den gesamten invertedIndex durchsuchen.
	docTerms map[string][]string

	// totalTerms ist die Summe der Dokumentlängen — für die Durchschnittslänge.
	totalTerms int
}

// NewIndex erstellt einen leeren, einsatzbereiten Index.
func NewIndex() *Index {
	return &Index{
		invertedIndex: make(map[string][]posting),
		docs:          make(map[string]docMeta),
		docTerms:      make(map[string][]string),
	}
}

// Index fügt ein Dokument hinzu oder aktualisiert es.
// Falls docID bereits existiert, wird der alte Eintrag zuerst entfernt.
//
// title, body und tags werden getrennt übergeben um unterschiedliche
// Boost-Faktoren anwenden zu können.
func (s *Index) Index(docID, title, body string, tags []string) {
	s.IndexWithBoost(docID, title, body, tags, 1)
}

// IndexWithBoost indiziert wie Index, gibt dem Dokument aber einen Faktor
// mit, mit dem sein Endwert bei jeder Suche malgenommen wird.
//
// Damit lassen sich Dokumente bei sonst gleicher Relevanz bevorzugen, ohne
// dass der Index wissen muss, warum. Die Registry nutzt das für kuratierte
// Einträge (siehe curatedBoost in registry.go). Ein Faktor von 1 ist neutral;
// Werte ≤ 0 werden als 1 behandelt, damit kein Dokument aus Versehen
// unauffindbar wird.
func (s *Index) IndexWithBoost(docID, title, body string, tags []string, boost float64) {
	if boost <= 0 {
		boost = 1
	}

	s.mu.Lock()
	defer s.mu.Unlock()

	// Zuerst alten Eintrag entfernen falls vorhanden (Update-Logik).
	s.removeUnsafe(docID)

	// Tokens aus allen Quellen mit Boost-Gewichtung sammeln.
	// Boost durch Wiederholung: "nginx" im Titel → 3x "nginx" in der Tokenliste.
	// Das erhöht die Termhäufigkeit (TF) künstlich für Titel-Treffer.
	var allTokens []string
	allTokens = append(allTokens, repeatTokens(tokenize(title), titleBoost)...)
	allTokens = append(allTokens, tokenize(body)...)
	allTokens = append(allTokens, repeatTokens(tokenize(strings.Join(tags, " ")), tagsBoost)...)

	if len(allTokens) == 0 {
		return
	}

	// Termhäufigkeit pro Token zählen: "nginx" vorkommt 5x → {nginx: 5}
	termFreq := make(map[string]int, len(allTokens))
	for _, t := range allTokens {
		termFreq[t]++
	}

	// Invertierter Index aufbauen: für jeden Term einen Posting-Eintrag hinzufügen.
	termList := make([]string, 0, len(termFreq))
	for term, freq := range termFreq {
		s.invertedIndex[term] = append(s.invertedIndex[term], posting{
			docID: docID,
			freq:  freq,
		})
		termList = append(termList, term)
	}

	// Metadaten und Rückwärts-Index speichern.
	s.docs[docID] = docMeta{length: len(allTokens), title: title, boost: boost}
	s.docTerms[docID] = termList
	s.totalTerms += len(allTokens)
}

// Remove entfernt ein Dokument vollständig aus dem Index.
func (s *Index) Remove(docID string) {
	s.mu.Lock()
	defer s.mu.Unlock()
	s.removeUnsafe(docID)
}

// removeUnsafe entfernt ein Dokument ohne Lock — nur aus internen Methoden aufrufen
// die bereits einen Lock halten.
func (s *Index) removeUnsafe(docID string) {
	meta, exists := s.docs[docID]
	if !exists {
		return
	}

	// Alle Postings für dieses Dokument aus dem invertierten Index entfernen.
	// Wir nutzen docTerms um zu wissen welche Terme betroffen sind —
	// viel schneller als den gesamten Index zu scannen.
	for _, term := range s.docTerms[docID] {
		postings := s.invertedIndex[term]
		filtered := postings[:0] // wiederverwendet das bestehende Slice (kein Speicher-Allokierung)
		for _, p := range postings {
			if p.docID != docID {
				filtered = append(filtered, p)
			}
		}
		if len(filtered) == 0 {
			delete(s.invertedIndex, term)
		} else {
			s.invertedIndex[term] = filtered
		}
	}

	s.totalTerms -= meta.length
	delete(s.docs, docID)
	delete(s.docTerms, docID)
}

// Search führt eine BM25-Suche für den übergebenen Suchbegriff durch.
// Die Ergebnisse sind absteigend nach Relevanz sortiert (bester Treffer zuerst).
// limit begrenzt die Anzahl der zurückgegebenen Ergebnisse.
//
// Neben exakten Treffern findet Search auch Wortanfänge, Wörter mit anderer
// Endung und zusammengesetzte Wörter (siehe variants.go). Tippfehler
// gleicht Search nicht aus — dafür gibt es SearchFuzzy.
func (s *Index) Search(queryStr string, limit int) []Result {
	return s.search(queryStr, limit, false)
}

// SearchFuzzy sucht wie Search, findet aber zusätzlich Wörter mit Tippfehlern
// — allerdings nur für Suchwörter, die sonst gar nichts treffen.
//
// # Warum nicht immer?
//
// Gedacht ist das für Menschen in der Weboberfläche. Agenten machen kaum
// Tippfehler; bei ihnen brächte die Toleranz vor allem zusätzliche, unsichere
// Treffer. Deshalb nutzt das MCP-Werkzeug recall weiterhin Search.
func (s *Index) SearchFuzzy(queryStr string, limit int) []Result {
	return s.search(queryStr, limit, true)
}

// search ist die gemeinsame Umsetzung von Search und SearchFuzzy.
func (s *Index) search(queryStr string, limit int, typo bool) []Result {
	s.mu.RLock()
	defer s.mu.RUnlock()

	queryTokens := withoutStopwords(tokenize(queryStr))
	if len(queryTokens) == 0 || len(s.docs) == 0 {
		return nil
	}

	// Gesamtanzahl Dokumente und Durchschnittslänge für BM25 berechnen.
	N := float64(len(s.docs))
	avgDocLen := float64(s.totalTerms) / N

	// scores sammelt den BM25-Score je Dokument über alle Query-Terme.
	// map[docID]score
	scores := make(map[string]float64)

	for _, term := range queryTokens {
		// Je Dokument zählt für dieses Suchwort nur die beste Variante —
		// ein exakter Treffer wird also nicht durch denselben Treffer als
		// Wortanfang noch einmal aufgewertet.
		best := make(map[string]float64)

		for _, v := range s.variantsFor(term, typo) {
			// IDF (Inverse Document Frequency):
			// Seltene Terme sind aussagekräftiger als häufige (z.B. "und", "der").
			// Formel: log((N - nq + 0.5) / (nq + 0.5) + 1)
			// nq = Anzahl der Dokumente die diesen Term enthalten
			nq := float64(len(v.postings))
			idf := math.Log((N-nq+0.5)/(nq+0.5) + 1)

			for _, p := range v.postings {
				meta := s.docs[p.docID]
				docLen := float64(meta.length)

				// BM25-Termgewicht:
				// Zähler: tf * (k1 + 1)  — gibt bei tf=0 den Wert 0
				// Nenner: tf + k1 * (1 - b + b * |D| / avgdl) — beugt Übergewichtung vor
				tf := float64(p.freq)
				tfNorm := tf * (bm25K1 + 1) / (tf + bm25K1*(1-bm25B+bm25B*docLen/avgDocLen))

				value := v.weight * idf * tfNorm
				if value > best[p.docID] {
					best[p.docID] = value
				}
			}
		}

		for docID, value := range best {
			scores[docID] += value
		}
	}

	if len(scores) == 0 {
		return nil
	}

	// Ergebnisse in eine sortierbare Liste umwandeln — dabei den Faktor des
	// Dokuments anwenden (siehe IndexWithBoost).
	results := make([]Result, 0, len(scores))
	for docID, score := range scores {
		results = append(results, Result{DocID: docID, Score: score * s.docs[docID].boost})
	}

	// Absteigend nach Score sortieren (bester Treffer zuerst).
	sort.Slice(results, func(i, j int) bool {
		return results[i].Score > results[j].Score
	})

	// Auf limit begrenzen.
	if limit > 0 && len(results) > limit {
		results = results[:limit]
	}

	return results
}

// tokenize zerlegt einen Text in Terme für die Indizierung.
// Es werden nur Buchstaben und Ziffern behalten, alles andere gilt als Trennzeichen.
// Einzeichen-Tokens werden ignoriert (kaum aussagekräftig).
//
// Umlaute und ß werden dabei vereinheitlicht — siehe foldUmlauts.
func tokenize(text string) []string {
	text = strings.ToLower(text)
	var tokens []string
	var current strings.Builder

	for _, r := range text {
		if unicode.IsLetter(r) || unicode.IsDigit(r) {
			current.WriteString(foldUmlauts(r))
		} else {
			if current.Len() > 1 {
				tokens = append(tokens, current.String())
			}
			current.Reset()
		}
	}
	// Letztes Token nicht vergessen
	if current.Len() > 1 {
		tokens = append(tokens, current.String())
	}

	return tokens
}

// foldUmlauts bildet Umlaute und ß auf ihre Grundform ab.
//
// # Wozu?
//
// Ohne das findet „prufung" den Eintrag „Prüfung" nicht — es sind für den Index
// zwei verschiedene Wörter. Genau so tippt aber, wer auf einer fremden Tastatur
// sitzt oder es eilig hat. Bei einem Menschen ist das ärgerlich, bei einer
// KI-Anfrage ein stiller Fehltreffer: Sie bekommt kein Ergebnis und erfährt
// nicht, dass es eines gäbe.
//
// Die Faltung greift, weil tokenize sowohl beim Indizieren als auch beim Suchen
// verwendet wird — beide Seiten landen also auf derselben Form.
//
// # Was sie abdeckt und was nicht
//
//	prüfung  → prufung   ✓ und „prufung" findet es
//	größe    → grosse    ✓ und „grosse" findet es
//	prüfung  → prufung   ✗ „pruefung" findet es NICHT
//
// Die Umschreibung mit e (ue, oe, ae) bleibt außen vor. Sie ließe sich nur
// abdecken, indem man auch „ue" zu „u" zusammenzieht — dann würde aber aus
// „neue" ein „nu" und aus „Steuer" ein „Stur". Der Schaden wäre größer als der
// Nutzen. Die Punkte wegzulassen ist die weit häufigere Schreibweise.
//
// Alle anderen Zeichen bleiben unverändert; für lateinische Buchstaben und
// Ziffern kostet die Funktion nur einen Vergleich.
func foldUmlauts(r rune) string {
	switch r {
	case 'ä':
		return "a"
	case 'ö':
		return "o"
	case 'ü':
		return "u"
	case 'ß':
		return "ss"
	default:
		return string(r)
	}
}

// repeatTokens wiederholt eine Tokenliste n-mal — damit wird Boost durch
// erhöhte Termhäufigkeit (TF) simuliert, ohne die BM25-Formel zu verändern.
func repeatTokens(tokens []string, n int) []string {
	if n <= 1 {
		return tokens
	}
	result := make([]string, 0, len(tokens)*n)
	for i := 0; i < n; i++ {
		result = append(result, tokens...)
	}
	return result
}