advanced-text-search-matching

name	advanced-text-search-matching
description	Production-grade text search algorithms for finding and matching text in large documents with millisecond performance. Includes Boyer-Moore search, n-gram similarity, fuzzy matching, and intelligent indexing. Use when building search features for large documents, finding quotes with imperfect matches, implementing fuzzy search, or need character-level precision.

Advanced Text Search & Matching

Production-grade text search algorithms for finding and matching text in large documents with millisecond performance. Includes Boyer-Moore search, n-gram similarity, fuzzy matching, and intelligent indexing.

When to use this skill

• Building search features for large documents or transcripts
• Finding quotes or citations in text with imperfect matches
• Implementing fuzzy search that handles typos and variations
• Need character-level precision for highlighting
• Building citation systems or source verification
• Searching across segmented content (chapters, timestamps, etc.)
• Performance-critical text matching (100k+ character documents)

Core Algorithms

1. Boyer-Moore Search - O(n/m) exact substring matching
2. N-gram Similarity - Jaccard coefficient for fuzzy matching
3. Multi-Strategy Matching - Cascading exact → normalized → fuzzy
4. Document Indexing - Word and n-gram indices for fast lookup
5. Segment Mapping - Character-precise position tracking

Implementation

Step 1: Create Text Search Utilities

Create lib/text-search.ts:

// Configuration constants
const SEARCH_CONFIG = {
  FUZZY_MATCH_THRESHOLD: 0.85,
  MIN_FUZZY_SCORE: 0.7,
  N_GRAM_SIZE: 3,
  MIN_N_GRAM_OVERLAP: 0.5,
} as const;

// Text normalization utilities
export function normalizeWhitespace(text: string): string {
  return text
    .replace(/[\r\n]+/g, ' ') // Replace newlines with spaces
    .replace(/\s+/g, ' ')     // Collapse multiple spaces
    .trim();
}

export function normalizeForMatching(text: string): string {
  return text
    .toLowerCase()
    // Remove most punctuation for robust matching
    .replace(/[.,?"""''!—…–]/g, '')
    // Normalize whitespace
    .replace(/\s+/g, ' ')
    .trim();
}

// Fast n-gram based similarity (returns 0-1)
export function calculateNgramSimilarity(str1: string, str2: string): number {
  if (str1.length === 0 || str2.length === 0) return 0;

  const ngrams1 = new Set<string>();
  const ngrams2 = new Set<string>();

  // Generate 3-grams
  const clean1 = str1.replace(/\s+/g, '');
  const clean2 = str2.replace(/\s+/g, '');

  for (let i = 0; i <= clean1.length - 3; i++) {
    ngrams1.add(clean1.substring(i, i + 3));
  }

  for (let i = 0; i <= clean2.length - 3; i++) {
    ngrams2.add(clean2.substring(i, i + 3));
  }

  if (ngrams1.size === 0 || ngrams2.size === 0) {
    // Fallback to simple substring check for very short strings
    return clean1.includes(clean2) || clean2.includes(clean1) ? 0.8 : 0;
  }

  // Calculate Jaccard similarity
  let intersection = 0;
  for (const ngram of ngrams1) {
    if (ngrams2.has(ngram)) intersection++;
  }

  const union = ngrams1.size + ngrams2.size - intersection;
  return intersection / union;
}

// Boyer-Moore-Horspool substring search
export function boyerMooreSearch(text: string, pattern: string): number {
  if (pattern.length === 0) return 0;
  if (pattern.length > text.length) return -1;

  // Build bad character table
  const badChar = new Map<string, number>();
  for (let i = 0; i < pattern.length - 1; i++) {
    badChar.set(pattern[i], pattern.length - 1 - i);
  }

  let i = pattern.length - 1;
  while (i < text.length) {
    let j = pattern.length - 1;
    let k = i;
    while (j >= 0 && k >= 0 && text[k] === pattern[j]) {
      if (j === 0) return k; // Match found!
      k--;
      j--;
    }
    const skip = (i < text.length && badChar.has(text[i]))
      ? badChar.get(text[i])!
      : pattern.length;
    i += skip;
  }

  return -1; // Not found
}

Step 2: Create Document Index System

// Document segment interface
export interface DocumentSegment {
  text: string;
  start: number;  // Optional: timestamp or position
  duration?: number;
}

// Comprehensive document index
export interface DocumentIndex {
  fullText: string;
  normalizedText: string;
  segmentBoundaries: Array<{
    segmentIdx: number;
    startPos: number;
    endPos: number;
    text: string;
    normalizedText: string;
  }>;
  wordIndex: Map<string, number[]>; // word -> [segment indices]
  ngramIndex: Map<string, Set<number>>; // 3-gram -> segment indices
}

// Build index for fast searching
export function buildDocumentIndex(segments: DocumentSegment[]): DocumentIndex {
  const segmentBoundaries: <{
    : ;
    : ;
    : ;
    : ;
    : ;
  }> = [];

   fullText = ;
   normalizedText = ;
   wordIndex =  <, []>();
   ngramIndex =  <, <>>();

  segments.( {
     (idx > ) {
      fullText += ;
      normalizedText += ;
    }

     segmentStartPos = fullText.;
     segmentNormalized = (segment.);

    fullText += segment.;
    normalizedText += segmentNormalized;

    
     words = segmentNormalized.();
    words.( {
       (word. > ) {
         positions = wordIndex.(word) || [];
        positions.(idx);
        wordIndex.(word, positions);
      }
    });

    
     cleanText = segmentNormalized.(, );
     ( i = ; i <= cleanText. - ; i++) {
       ngram = cleanText.(i, i + );
       (!ngramIndex.(ngram)) {
        ngramIndex.(ngram,  ());
      }
      ngramIndex.(ngram)!.(idx);
    }

    segmentBoundaries.({
      : idx,
      : segmentStartPos,
      : fullText.,
      : segment.,
      : segmentNormalized
    });
  });

   {
    fullText,
    normalizedText,
    segmentBoundaries,
    wordIndex,
    ngramIndex
  };
}

Step 3: Intelligent Multi-Strategy Search

export interface SearchResult {
  found: boolean;
  startSegmentIdx: number;
  endSegmentIdx: number;
  startCharOffset: number;
  endCharOffset: number;
  matchStrategy: 'exact' | 'normalized' | 'fuzzy-ngram';
  similarity: number;
  confidence: number;
}

export function findText(
  segments: DocumentSegment[],
  targetText: string,
  index: DocumentIndex,
  options: {
    minSimilarity?: number;
    maxSegmentWindow?: number;
  } = {}
): SearchResult | null {
  const {
    minSimilarity = SEARCH_CONFIG.FUZZY_MATCH_THRESHOLD,
    maxSegmentWindow = 30
  } = options;

  // Strategy 1: Try exact match (fastest)
  const exactMatch = boyerMooreSearch(index.fullText, targetText);
  if (exactMatch !== -1) {
    const result = mapMatchToSegments(exactMatch, targetText.length, index);
     (result) {
       {
        ...result,
        : ,
        : ,
        : 
      };
    }
  }

  
   normalizedTarget = (targetText);
   normalizedMatch = (index., normalizedTarget);
   (normalizedMatch !== -) {
     result = (
      normalizedMatch,
      normalizedTarget,
      index
    );
     (result) {
       {
        ...result,
        : ,
        : ,
        : 
      };
    }
  }

  
   targetWords = (targetText)
    .()
    .( w. > );

   (targetWords. > ) {
    
     segmentScores =  <, >();

     ( word  targetWords) {
       segmentIndices = index..(word) || [];
       ( segIdx  segmentIndices) {
        segmentScores.(segIdx, (segmentScores.(segIdx) || ) + );
      }
    }

    
     scoredSegments = .(segmentScores.())
      .( b[] - a[])
      .(, );

     ( [candidateIdx, score]  scoredSegments) {
      
       windowStart = .(, candidateIdx - );
       windowEnd = .(segments. - , candidateIdx + maxSegmentWindow);

       combinedText = ;
       ( i = windowStart; i <= windowEnd; i++) {
         (i > windowStart) combinedText += ;
        combinedText += segments[i].;

         normalizedCombined = (combinedText);
         similarity = (
          (targetText),
          normalizedCombined
        );

         (similarity >= minSimilarity) {
           {
            : ,
            : windowStart,
            : i,
            : ,
            : segments[i]..,
            : ,
            similarity,
            : score / targetWords.
          };
        }
      }
    }
  }

   ;
}


 (): <,  |  | > |  {
   matchEnd = matchStart + matchLength;
   startSegmentIdx = -;
   endSegmentIdx = -;
   startCharOffset = ;
   endCharOffset = ;

   ( boundary  index.) {
    
     (startSegmentIdx === - && matchStart >= boundary. && matchStart < boundary.) {
      startSegmentIdx = boundary.;
      startCharOffset = matchStart - boundary.;
    }

    
     (matchEnd > boundary. && matchEnd <= boundary.) {
      endSegmentIdx = boundary.;
      endCharOffset = matchEnd - boundary.;
      ;
    }   (matchEnd > boundary.) {
      endSegmentIdx = boundary.;
      endCharOffset = boundary..;
    }
  }

   (startSegmentIdx !== - && endSegmentIdx !== -) {
     {
      : ,
      startSegmentIdx,
      endSegmentIdx,
      startCharOffset,
      endCharOffset
    };
  }

   ;
}


 (): <,  |  | > |  {
   matchEnd = normalizedMatchIdx + normalizedTargetText.;
   currentNormPos = ;
   startSegmentIdx = -;
   endSegmentIdx = -;
   startCharOffset = ;
   endCharOffset = ;

   ( boundary  index.) {
     segmentNormLength = boundary..;
     segmentNormEnd = currentNormPos + segmentNormLength;

     (startSegmentIdx === - && normalizedMatchIdx >= currentNormPos && normalizedMatchIdx < segmentNormEnd) {
      startSegmentIdx = boundary.;
       normOffsetInSegment = normalizedMatchIdx - currentNormPos;
      startCharOffset = .(normOffsetInSegment, boundary.. - );
    }

     (matchEnd > currentNormPos && matchEnd <= segmentNormEnd) {
      endSegmentIdx = boundary.;
       normOffsetInSegment = matchEnd - currentNormPos;
      endCharOffset = .(normOffsetInSegment, boundary..);
      ;
    }

    currentNormPos = segmentNormEnd + ;
  }

   (startSegmentIdx !== - && endSegmentIdx !== -) {
     {
      : ,
      startSegmentIdx,
      endSegmentIdx,
      startCharOffset,
      endCharOffset
    };
  }

   ;
}

Usage Examples

Example 1: Search Video Transcript

import { buildDocumentIndex, findText } from '@/lib/text-search';

// Video transcript segments
const transcript = [
  { text: "Welcome to this tutorial on React hooks.", start: 0, duration: 3 },
  { text: "Today we'll learn about useState and useEffect.", start: 3, duration: 4 },
  { text: "These are the most commonly used hooks.", start: 7, duration: 3 }
];

// Build index once
const index = buildDocumentIndex(transcript);

// Search for exact quote
const result1 = findText(transcript, "useState and useEffect", index);
// { found: true, matchStrategy: 'exact', similarity: 1.0, ... }

// Search with typo - fuzzy match
const result2 = findText(transcript, "usestate and useefect", index);
// { found: true, matchStrategy: 'fuzzy-ngram', similarity: 0.92, ... }

// Use result to highlight
if (result1) {
  const segment = transcript[result1.startSegmentIdx];
  const beforeMatch = segment.text.substring(0, result1.startCharOffset);
  const match = segment..(result1., result1.);
   afterMatch = segment..(result1.);

  .();
  
}

---

Example 2: Citation Verification System

import { buildDocumentIndex, findText, calculateNgramSimilarity } from '@/lib/text-search';

// Verify AI-generated citations against source
function verifyCitation(
  citation: string,
  sourceSegments: DocumentSegment[],
  index: DocumentIndex
): {
  verified: boolean;
  confidence: number;
  location?: { segment: number; timestamp: number };
} {
  const result = findText(sourceSegments, citation, index, {
    minSimilarity: 0.8 // Lower threshold for citations
  });

  if (result) {
    return {
      verified: true,
      confidence: result.confidence,
      location: {
        segment: result.startSegmentIdx,
        timestamp: sourceSegments[result.startSegmentIdx].start
      }
    };
  }

  return { verified: false, confidence: 0 };
}

// Usage
const aiResponse = "The React team recommends using functional components with hooks";
const verification = verifyCitation(aiResponse, transcript, index);

 (verification.) {
  .();
  .();
}

---

Example 3: Search Suggestions

// Find similar segments based on query
function findSimilarSegments(
  query: string,
  segments: DocumentSegment[],
  index: DocumentIndex,
  limit: number = 5
): Array<{ segment: DocumentSegment; similarity: number; index: number }> {
  const normalizedQuery = normalizeForMatching(query);
  const results: Array<{ segment: DocumentSegment; similarity: number; index: number }> = [];

  segments.forEach((segment, idx) => {
    const normalizedSegment = normalizeForMatching(segment.text);
    const similarity = calculateNgramSimilarity(normalizedQuery, normalizedSegment);

    if (similarity > 0.3) {
      results.push({ segment, similarity, index: idx });
    }
  });

  return results
    .sort((a, b) => b.similarity - a.similarity)
    .slice(, limit);
}


 query = ;
 similar = (query, transcript, index);

similar.( {
  .();
});

---

Example 4: Highlight Multiple Matches

// Find all occurrences of a phrase
function findAllMatches(
  pattern: string,
  segments: DocumentSegment[],
  index: DocumentIndex
): SearchResult[] {
  const matches: SearchResult[] = [];
  let searchText = index.fullText;
  let offset = 0;

  while (true) {
    const matchPos = boyerMooreSearch(searchText, pattern);
    if (matchPos === -1) break;

    const absolutePos = offset + matchPos;
    const result = mapMatchToSegments(absolutePos, pattern.length, index);

    if (result) {
      matches.push({
        ...result,
        matchStrategy: 'exact',
        similarity: 1.0,
        confidence: 1.0
      });
    }

    // Continue searching after this match
    offset += matchPos + pattern.length;
    searchText = searchText.substring(matchPos + pattern.length);
  }

  return matches;
}

---

Example 5: Performance Benchmark

// Measure search performance
function benchmarkSearch(segments: DocumentSegment[]) {
  console.time('Build Index');
  const index = buildDocumentIndex(segments);
  console.timeEnd('Build Index');

  const searches = [
    "exact phrase match",
    "fuzzy aproximate match",
    "very long search query with multiple words to test performance"
  ];

  searches.forEach(query => {
    console.time(`Search: "${query}"`);
    const result = findText(segments, query, index);
    console.timeEnd(`Search: "${query}"`);
    console.log(`  Strategy: ${result?.matchStrategy}, Similarity: ${result?.similarity}`);
  });
}

// Typical results for 10K word document:
// Build Index: 15ms
// Search: "exact phrase match": 0.2ms
// Search: "fuzzy aproximate match": 1.5ms

---

Advanced Patterns

Pattern 1: Autocomplete with Fuzzy Matching

function autocomplete(
  prefix: string,
  words: string[],
  limit: number = 10
): Array<{ word: string; similarity: number }> {
  const normalizedPrefix = normalizeForMatching(prefix);

  return words
    .map(word => ({
      word,
      similarity: calculateNgramSimilarity(
        normalizedPrefix,
        normalizeForMatching(word)
      )
    }))
    .filter(({ similarity }) => similarity > 0.4)
    .sort((a, b) => b.similarity - a.similarity)
    .slice(0, limit);
}

---

Pattern 2: Duplicate Detection

function findDuplicates(
  segments: DocumentSegment[],
  threshold: number = 0.9
): Array<[number, number]> {
  const duplicates: Array<[number, number]> = [];

  for (let i = 0; i < segments.length; i++) {
    for (let j = i + 1; j < segments.length; j++) {
      const similarity = calculateNgramSimilarity(
        normalizeForMatching(segments[i].text),
        normalizeForMatching(segments[j].text)
      );

      if (similarity >= threshold) {
        duplicates.push([i, j]);
      }
    }
  }

  return duplicates;
}

---

Best Practices

1. Build index once - Reuse for multiple searches
2. Choose appropriate similarity threshold - 0.85 for strict, 0.7 for lenient
3. Limit segment window - Prevent runaway fuzzy matches
4. Cache normalized text - Don't normalize repeatedly
5. Use Boyer-Moore first - Always try exact match before fuzzy
6. Monitor performance - Index build time scales with document size

---

Common Pitfalls

1. Not normalizing consistently - Use same normalization for index and query
2. Too aggressive fuzzy matching - Set minimum similarity threshold
3. Rebuilding index on every search - Build once, search many
4. Ignoring character offsets - Needed for precise highlighting
5. Not handling multi-segment matches - Quotes can span segments
6. Case-sensitive exact match - Normalize for matching

---

Performance Characteristics

Operation	Time Complexity	Notes
Build Index	O(n)	n = total characters
Exact Search (Boyer-Moore)	O(n/m) average	m = pattern length
Fuzzy Search	O(k*w)	k = candidates, w = window
N-gram Similarity	O(n+m)	n, m = string lengths

Benchmarks (10,000 word document):

• Index build: ~15ms
• Exact search: ~0.2ms
• Fuzzy search: ~1-3ms

---

Testing

describe('Text Search', () => {
  test('exact match', () => {
    const segments = [{ text: "The quick brown fox", start: 0 }];
    const index = buildDocumentIndex(segments);
    const result = findText(segments, "quick brown", index);

    expect(result?.found).toBe(true);
    expect(result?.matchStrategy).toBe('exact');
    expect(result?.similarity).toBe(1.0);
  });

  test('fuzzy match with typo', () => {
    const segments = [{ text: "The quick brown fox", start: 0 }];
    const index = buildDocumentIndex(segments);
    const result = findText(segments, "quik brwon", index);

    expect(result?.found).toBe(true);
    expect(result?.matchStrategy).toBe('fuzzy-ngram');
    (result?.).();
  });

  (,  {
     segments = [{ : , :  }];
     index = (segments);
     result = (segments, , index);

    (result?.).();
    (result?.).();
  });
});

---

Next Steps

After implementing this skill:

1. Add caching for frequently searched documents
2. Implement parallel search for very large documents
3. Add spell-correction using n-gram similarity
4. Create search result ranking algorithm
5. Build autocomplete with prefix trees
6. Add support for regex patterns

Related Skills

• Type-Safe Form Validation - Validate search queries
• Resilient Async Operations - Handle search in background
• AI Model Cascade - Enhance search with AI

---

Built from production text search in TLDW citation system