Building a Full-Text Search Engine from Scratch

// Document collection
interface Document {
  id: number;
  title: string;
  body: string;
}
 
const documents: Document[] = [
  { id: 1, title: 'TypeScript Patterns', body: 'TypeScript generics enable reusable type-safe code' },
  { id: 2, title: 'Testing Guide', body: 'Testing TypeScript code requires proper type configuration' },
  { id: 3, title: 'React Performance', body: 'React memoization prevents unnecessary re-renders in code' },
];
 
// Forward index (what you have): document → words
// { 1: ['typescript', 'generics', 'enable', 'reusable', 'type-safe', 'code'] }
// { 2: ['testing', 'typescript', 'code', 'requires', 'proper', 'type', 'configuration'] }
// { 3: ['react', 'memoization', 'prevents', 'unnecessary', 're-renders', 'code'] }
 
// ✅ Inverted index (what you need): word → documents
// 'typescript' → [1, 2]
// 'code'       → [1, 2, 3]
// 'react'      → [3]
// 'testing'    → [2]
// 'generics'   → [1]

// Tokenizer: breaks text into searchable terms
function tokenize(text: string): string[] {
  return text
    .toLowerCase()                       // Normalize case
    .replace(/[^\w\s]/g, ' ')           // Remove punctuation
    .split(/\s+/)                        // Split on whitespace
    .filter((token) => token.length > 0); // Remove empty tokens
}
 
// Stop words: common words that add noise to search results
const STOP_WORDS = new Set([
  'the', 'a', 'an', 'is', 'are', 'was', 'were', 'be', 'been',
  'being', 'have', 'has', 'had', 'do', 'does', 'did', 'will',
  'would', 'could', 'should', 'may', 'might', 'in', 'on', 'at',
  'to', 'for', 'of', 'with', 'by', 'from', 'and', 'or', 'not',
  'it', 'this', 'that', 'these', 'those',
]);
 
function removeStopWords(tokens: string[]): string[] {
  return tokens.filter((token) => !STOP_WORDS.has(token));
}
 
// ❌ Indexing without normalization
// "TypeScript" and "typescript" become different index entries
// User searching "typescript" won't find documents with "TypeScript"
 
// ✅ Normalize before indexing AND before searching
const raw = 'TypeScript Generics enable reusable, type-safe code!';
const tokens = removeStopWords(tokenize(raw));
// Result: ['typescript', 'generics', 'enable', 'reusable', 'type', 'safe', 'code']

interface Posting {
  documentId: number;
  frequency: number;    // How many times the term appears in this doc
  positions: number[];  // Where in the document (for phrase queries)
}
 
type InvertedIndex = Map<string, Posting[]>;
 
function buildIndex(documents: Document[]): InvertedIndex {
  const index: InvertedIndex = new Map();
 
  for (const doc of documents) {
    const text = `${doc.title} ${doc.body}`;
    const tokens = removeStopWords(tokenize(text));
 
    // Track positions for phrase matching
    const termPositions = new Map<string, number[]>();
    tokens.forEach((token, position) => {
      if (!termPositions.has(token)) {
        termPositions.set(token, []);
      }
      termPositions.get(token)!.push(position);
    });
 
    // Add postings to the inverted index
    for (const [term, positions] of termPositions) {
      if (!index.has(term)) {
        index.set(term, []);
      }
      index.get(term)!.push({
        documentId: doc.id,
        frequency: positions.length,
        positions,
      });
    }
  }
 
  return index;
}
 
const idx = buildIndex(documents);
// idx.get('typescript') → [{ docId: 1, freq: 2, pos: [0, ...] }, { docId: 2, freq: 1, pos: [...] }]
// idx.get('code')       → [{ docId: 1, freq: 1, pos: [...] }, { docId: 2, freq: 1, pos: [...] }, { docId: 3, freq: 1, pos: [...] }]

// TF: How often the term appears in THIS document
// Higher frequency → more relevant (this doc talks about the term a lot)
function termFrequency(termCount: number, totalTerms: number): number {
  return termCount / totalTerms;
}
 
// IDF: How rare the term is across ALL documents
// Rarer terms → more discriminating → higher weight
function inverseDocumentFrequency(
  totalDocuments: number,
  documentsWithTerm: number
): number {
  return Math.log(totalDocuments / (1 + documentsWithTerm));
}
 
// TF-IDF score for a single term in a single document
function tfidf(
  termCount: number,
  totalTermsInDoc: number,
  totalDocuments: number,
  documentsWithTerm: number
): number {
  const tf = termFrequency(termCount, totalTermsInDoc);
  const idf = inverseDocumentFrequency(totalDocuments, documentsWithTerm);
  return tf * idf;
}
 
// Search function with TF-IDF ranking
function search(
  query: string,
  index: InvertedIndex,
  documents: Document[],
  docLengths: Map<number, number>
): Array<{ documentId: number; score: number }> {
  const queryTokens = removeStopWords(tokenize(query));
  const scores = new Map<number, number>();
 
  for (const token of queryTokens) {
    const postings = index.get(token);
    if (!postings) continue;
 
    const idf = inverseDocumentFrequency(documents.length, postings.length);
 
    for (const posting of postings) {
      const docLength = docLengths.get(posting.documentId) ?? 1;
      const tf = termFrequency(posting.frequency, docLength);
      const score = tf * idf;
 
      const current = scores.get(posting.documentId) ?? 0;
      scores.set(posting.documentId, current + score);
    }
  }
 
  return Array.from(scores.entries())
    .map(([documentId, score]) => ({ documentId, score }))
    .sort((a, b) => b.score - a.score);
}

// ❌ Treating multi-word queries as OR by default
// Query "TypeScript testing" returns ALL TypeScript docs AND all testing docs
// Most results aren't relevant to both topics
 
// ✅ Support explicit boolean operators
type BooleanOp = 'AND' | 'OR' | 'NOT';
 
interface QueryClause {
  term: string;
  operator: BooleanOp;
}
 
function parseQuery(query: string): QueryClause[] {
  const tokens = query.split(/\s+/);
  const clauses: QueryClause[] = [];
  let nextOp: BooleanOp = 'AND'; // Default to AND
 
  for (const token of tokens) {
    const upper = token.toUpperCase();
    if (upper === 'AND' || upper === 'OR' || upper === 'NOT') {
      nextOp = upper as BooleanOp;
      continue;
    }
    clauses.push({ term: token.toLowerCase(), operator: nextOp });
    nextOp = 'AND'; // Reset to default
  }
 
  return clauses;
}
 
function booleanSearch(
  query: string,
  index: InvertedIndex
): Set<number> {
  const clauses = parseQuery(query);
  let resultSet: Set<number> | null = null;
 
  for (const clause of clauses) {
    const postings = index.get(clause.term) ?? [];
    const matchingDocs = new Set(postings.map((p) => p.documentId));
 
    if (resultSet === null) {
      resultSet = matchingDocs;
      continue;
    }
 
    switch (clause.operator) {
      case 'AND':
        resultSet = new Set([...resultSet].filter((id) => matchingDocs.has(id)));
        break;
      case 'OR':
        matchingDocs.forEach((id) => resultSet!.add(id));
        break;
      case 'NOT':
        matchingDocs.forEach((id) => resultSet!.delete(id));
        break;
    }
  }
 
  return resultSet ?? new Set();
}
 
// "typescript AND code" → documents containing BOTH terms
// "typescript OR react" → documents containing EITHER term
// "typescript NOT testing" → TypeScript docs that don't mention testing

class SearchEngine {
  private index: InvertedIndex = new Map();
  private documents: Map<number, Document> = new Map();
  private docLengths: Map<number, number> = new Map();
 
  addDocument(doc: Document): void {
    this.documents.set(doc.id, doc);
    const text = `${doc.title} ${doc.body}`;
    const tokens = removeStopWords(tokenize(text));
    this.docLengths.set(doc.id, tokens.length);
 
    const termPositions = new Map<string, number[]>();
    tokens.forEach((token, pos) => {
      if (!termPositions.has(token)) termPositions.set(token, []);
      termPositions.get(token)!.push(pos);
    });
 
    for (const [term, positions] of termPositions) {
      if (!this.index.has(term)) this.index.set(term, []);
      this.index.get(term)!.push({
        documentId: doc.id,
        frequency: positions.length,
        positions,
      });
    }
  }
 
  search(query: string, limit = 10): Array<{ document: Document; score: number }> {
    const results = search(
      query,
      this.index,
      Array.from(this.documents.values()),
      this.docLengths
    );
 
    return results.slice(0, limit).map(({ documentId, score }) => ({
      document: this.documents.get(documentId)!,
      score,
    }));
  }
}
 
// Usage
const engine = new SearchEngine();
engine.addDocument({ id: 1, title: 'TypeScript Patterns', body: '...' });
engine.addDocument({ id: 2, title: 'Testing Guide', body: '...' });
const results = engine.search('typescript generics');