From c91c3afd8700138f8eb8a25a4ae422c2c9e46cea Mon Sep 17 00:00:00 2001 From: alex Date: Tue, 28 Jul 2026 17:37:06 +0200 Subject: refactored entire code base to be in the package core so i can later implement interfaces to interact with the engine --- core/analyzer/analyzer.go | 38 +++++++++++++++++++++++++ core/engine.go | 56 ++++++++++++++++++++++++++++++++++++ core/index/index.go | 68 ++++++++++++++++++++++++++++++++++++++++++++ core/ingest/ingest.go | 44 +++++++++++++++++++++++++++++ core/scoring/field.go | 10 +++++++ core/scoring/idf.go | 17 +++++++++++ core/search/search.go | 72 +++++++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 305 insertions(+) create mode 100644 core/analyzer/analyzer.go create mode 100644 core/engine.go create mode 100644 core/index/index.go create mode 100644 core/ingest/ingest.go create mode 100644 core/scoring/field.go create mode 100644 core/scoring/idf.go create mode 100644 core/search/search.go (limited to 'core') diff --git a/core/analyzer/analyzer.go b/core/analyzer/analyzer.go new file mode 100644 index 0000000..6a02541 --- /dev/null +++ b/core/analyzer/analyzer.go @@ -0,0 +1,38 @@ +package analyzer + +import ( + "strings" + "unicode" +) + +var stopWords = map[string]struct{}{ + "the": {}, "a": {}, "an": {}, "and": {}, "or": {}, "but": {}, + "is": {}, "are": {}, "was": {}, "were": {}, "in": {}, "on": {}, + "at": {}, "to": {}, "from": {}, "by": {}, "of": {}, +} + +func ProcessText(text string) []string { + text = strings.ToLower(text) + text = SanitizeText(text) + tokens := strings.Fields(text) + var cleanTokens []string + for _, token := range tokens { + _, exists := stopWords[token] + if !exists { + cleanTokens = append(cleanTokens, token) + } + } + + return cleanTokens +} + +func SanitizeText(s string) string { + var builder strings.Builder + + for _, char := range s { + if unicode.IsLetter(char) || unicode.IsNumber(char) || unicode.IsSpace(char) { + builder.WriteRune(char) + } + } + return builder.String() +} diff --git a/core/engine.go b/core/engine.go new file mode 100644 index 0000000..4b6b150 --- /dev/null +++ b/core/engine.go @@ -0,0 +1,56 @@ +package core + +import ( + "fmt" + "searchEngine/core/analyzer" + "searchEngine/core/index" + "searchEngine/core/ingest" + "searchEngine/core/search" + "sync" +) + +type Engine struct { + idx *index.InvertedIndex +} + +func NewEngine() *Engine { + return &Engine{ + idx: index.New(), + } +} + +func (e *Engine) Index() *index.InvertedIndex { + return e.idx +} + +func (e *Engine) IndexDump(filePath string, numWorkers int) error { + if numWorkers <= 0 { + numWorkers = 4 + } + + jobQueue := make(chan ingest.Page, 100) + var wg sync.WaitGroup + + for i := 0; i < numWorkers; i++ { + wg.Go(func() { + for page := range jobQueue { + tokens := analyzer.ProcessText(page.Text) + e.idx.Add(page.Id, page.Title, tokens) + } + }) + } + + err := ingest.IngestWikiDump(filePath, jobQueue) + close(jobQueue) + wg.Wait() + + if err != nil { + return fmt.Errorf("failed to ingest wiki dump: %w", err) + } + + return nil +} + +func (e *Engine) Search(query string) []string { + return search.Search(e.idx, query) +} diff --git a/core/index/index.go b/core/index/index.go new file mode 100644 index 0000000..59b315c --- /dev/null +++ b/core/index/index.go @@ -0,0 +1,68 @@ +package index + +import ( + "searchEngine/core/analyzer" + "sync" +) + +type Posting struct { + DocId int + BodyCount int + TitleCount int + BodyPositions []int + TitlePositions []int +} + +type InvertedIndex struct { + Mu sync.RWMutex + Data map[string][]Posting + DocNames map[int]string +} + +func New() *InvertedIndex { + return &InvertedIndex{ + Data: make(map[string][]Posting), + DocNames: make(map[int]string), + } +} + +func (idx *InvertedIndex) Add(docID int, title string, bodyTokens []string) { + titleTokens := analyzer.ProcessText(title) + + type fieldStats struct { + body int + bodyPositions []int + title int + titlePositions []int + } + docStats := make(map[string]fieldStats) + + for position, token := range titleTokens { + stats := docStats[token] + stats.title++ + stats.titlePositions = append(stats.titlePositions, position) + docStats[token] = stats + } + + for position, token := range bodyTokens { + stats := docStats[token] + stats.body++ + stats.bodyPositions = append(stats.bodyPositions, position) + docStats[token] = stats + } + + idx.Mu.Lock() + defer idx.Mu.Unlock() + + idx.DocNames[docID] = title + + for token, stats := range docStats { + idx.Data[token] = append(idx.Data[token], Posting{ + DocId: docID, + BodyCount: stats.body, + TitleCount: stats.title, + BodyPositions: stats.bodyPositions, + TitlePositions: stats.titlePositions, + }) + } +} diff --git a/core/ingest/ingest.go b/core/ingest/ingest.go new file mode 100644 index 0000000..d54ff9d --- /dev/null +++ b/core/ingest/ingest.go @@ -0,0 +1,44 @@ +package ingest + +import ( + "encoding/xml" + "io" + "os" +) + +type Page struct { + Title string `xml:"title"` + Text string `xml:"revision>text"` + Id int `xml:"id"` +} + +func IngestWikiDump(filePath string, jobQueue chan<- Page) error { + file, err := os.Open(filePath) + if err != nil { + return err + } + defer file.Close() + + decoder := xml.NewDecoder(file) + + for { + t, err := decoder.Token() + if err == io.EOF { + break + } + if err != nil { + return err + } + + switch se := t.(type) { + case xml.StartElement: + if se.Name.Local == "page" { + var p Page + if err := decoder.DecodeElement(&p, &se); err == nil { + jobQueue <- p + } + } + } + } + return nil +} diff --git a/core/scoring/field.go b/core/scoring/field.go new file mode 100644 index 0000000..89f6132 --- /dev/null +++ b/core/scoring/field.go @@ -0,0 +1,10 @@ +package scoring + +import "searchEngine/core/index" + +var TitleWeight = 5.0 +var BodyWeight = 1.0 + +func FieldScore(p index.Posting) float64 { + return (float64(p.TitleCount) * TitleWeight) + (float64(p.BodyCount) * BodyWeight) +} diff --git a/core/scoring/idf.go b/core/scoring/idf.go new file mode 100644 index 0000000..f5aaecd --- /dev/null +++ b/core/scoring/idf.go @@ -0,0 +1,17 @@ +package scoring + +import ( + "math" + "searchEngine/core/index" +) + +func CalculateIDF(totalDocs int, docFrequency int) float64 { + if docFrequency == 0 { + return 0.0 + } + return math.Log10(float64(totalDocs) / float64(docFrequency)) +} + +func ScoreTFIDF(p index.Posting, idf float64) float64 { + return FieldScore(p) * idf +} diff --git a/core/search/search.go b/core/search/search.go new file mode 100644 index 0000000..e159d43 --- /dev/null +++ b/core/search/search.go @@ -0,0 +1,72 @@ +package search + +import ( + "searchEngine/core/analyzer" + "searchEngine/core/index" + "slices" +) + +type Result struct { + DocID int + Score int +} + +func Search(idx *index.InvertedIndex, query string) []string { + tokenizedQuery := analyzer.ProcessText(query) + if len(tokenizedQuery) == 0 { + return nil + } + + idx.Mu.RLock() + defer idx.Mu.RUnlock() + + firstToken := tokenizedQuery[0] + basePostings, exists := idx.Data[firstToken] + if !exists { + return nil + } + + scores := make(map[int]int) + for _, p := range basePostings { + scores[p.DocId] = p.BodyCount + } + + for i := 1; i < len(tokenizedQuery); i++ { + token := tokenizedQuery[i] + nextPostings, exists := idx.Data[token] + if !exists { + return nil + } + + lookup := make(map[int]int) + for _, p := range nextPostings { + lookup[p.DocId] = p.BodyCount + } + + newScores := make(map[int]int) + for docID, currentScore := range scores { + if nextCount, found := lookup[docID]; found { + newScores[docID] = currentScore + nextCount + } + } + scores = newScores + } + + var results []Result + for docID, score := range scores { + results = append(results, Result{DocID: docID, Score: score}) + } + + slices.SortFunc(results, func(a, b Result) int { + return b.Score - a.Score + }) + + var titles []string + for _, res := range results { + if title, exists := idx.DocNames[res.DocID]; exists { + titles = append(titles, title) + } + } + + return titles +} -- cgit v1.2.3