Mini Search Engine

Generic, reusable, configurable, in-memory search engine untuk TypeScript

Mini Search Engine adalah library search engine in-memory yang dirancang sebagai library reusable dan schema-agnostic.

Engine tidak mengetahui bentuk data aplikasi secara native. Struktur data ditentukan oleh aplikasi melalui SearchField<T> dan extractor.

Dengan demikian engine yang sama dapat digunakan untuk:

• Product
• User
• Article
• Ticket
• Employee
• Customer
• Order
• Device
• Repository
• Log
• dan object domain lainnya.

Core engine hanya bergantung pada generic type T, konfigurasi field, analyzer, retrieval strategy, dan scoring.

Fitur Utama

Mini Search Engine v2 menyediakan:

• Generic type T
• Schema-independent indexing
• Configurable field extractor
• Exact search
• Prefix search
• Fuzzy search
• Typo tolerance
• Levenshtein distance
• Normalized Levenshtein similarity
• Damerau-Levenshtein distance
• Jaro similarity
• Jaro-Winkler similarity
• levenshteinSuggestions()
• BK-tree untuk fuzzy vocabulary lookup
• Prefix Trie untuk prefix lookup
• Configurable tokenizer
• Configurable token normalization
• Lowercase normalization
• Accent/diacritic folding
• Stop-word filtering
• Minimum token length
• Maximum token length
• Field weighting
• Exact/prefix/fuzzy scoring
• Phrase matching
• Phrase boost
• Coverage scoring
• Frequency scoring
• Custom scoring
• AND search
• OR search
• Arbitrary document filtering
• Result highlighting
• Pagination
• Result limit
• Offset
• Minimum score
• Candidate limit
• Suggestions
• Multi-token suggestions
• Custom ID resolver
• Custom stringify untuk structured value
• Add / update / remove
• Bulk indexing
• Clear
• Rebuild
• Optimize
• Search statistics
• Index lifecycle hooks
• Deterministic index lifecycle
• Tidak membutuhkan library search engine eksternal

Filosofi Desain

Prinsip utama engine adalah:

Search engine tidak boleh mengetahui domain model aplikasi.

Misalnya aplikasi memiliki:

type Product = {
  id: number;
  title: string;
  description: string;
  brand: {
    name: string;
  };
  categories: string[];
  metadata: {
    sku: string;
    color: string;
  };
  price: number;
  tags: Array<{
    name: string;
  }>;
};

Engine tidak perlu memiliki kode khusus untuk:

Product
brand
price
SKU
categories
tags

Aplikasi menentukan sendiri field mana yang searchable.

Generic Type

Engine menggunakan generic:

MiniSearchEngine<T>;

atau factory:

createSearchEngine<T>(config);

Contoh:

const productSearch = createSearchEngine<Product>({
  // configuration
});

Engine tidak memerlukan inheritance khusus dari Product.

Tidak diperlukan:

class ProductSearchDocument extends Product

atau schema khusus dari engine.

SearchField<T>

Field ditentukan menggunakan extractor:

{
  name: 'title',
  extract: product => product.title
}

Extractor menerima:

T;

dan mengembalikan value yang ingin di-index.

Contoh lengkap:

const productSearch = createSearchEngine<Product>({
  id: product => String(product.id),
  fields: [
    {
      name: 'title',
      weight: 5,
      extract: product => product.title
    },
    {
      name: 'brand',
      weight: 4,
      extract: product => product.brand.name
    },
    {
      name: 'description',
      weight: 1,
      extract: product => product.description
    },
    {
      name: 'categories',
      weight: 2,
      extract: product => product.categories
    },
    {
      name: 'tags',
      weight: 2,
      extract: product => product.tags.map(tag => tag.name)
    },
    {
      name: 'sku',
      weight: 6,
      extract: product => product.metadata.sku
    },
    {
      name: 'color',
      weight: 1,
      extract: product => product.metadata.color
    }
  ]
});

Dengan konfigurasi tersebut engine memahami field secara abstrak:

Product
  │
  ├── title
  ├── brand
  ├── description
  ├── categories
  ├── tags
  ├── sku
  └── color

tetapi tidak perlu mengetahui struktur Product.

Field Weight

Field dapat diberikan weight berbeda.

Contoh:

{
  name: 'title',
  weight: 5,
  extract: product => product.title
}

dan:

{
  name: 'description',
  weight: 1,
  extract: product => product.description
}

Artinya kecocokan pada title mempunyai pengaruh lebih besar terhadap ranking dibanding kecocokan pada description.

Contoh konfigurasi:

title        weight 5
brand        weight 4
sku          weight 6
categories   weight 2
tags         weight 2
description  weight 1
color        weight 1

Ini berguna ketika relevance bisnis menganggap beberapa field lebih penting daripada field lainnya.

Mengindeks Data

Single document:

productSearch.add(product);

Multiple documents:

productSearch.addMany(products);

Contoh:

const products: Product[] = [
  {
    id: 1,
    title: 'Mechanical Keyboard RGB',
    description: 'Professional mechanical keyboard for developers',
    brand: {
      name: 'Keychron'
    },
    categories: ['Keyboard', 'Mechanical'],
    metadata: {
      sku: 'K8-PRO',
      color: 'Black'
    },
    price: 120,
    tags: [{ name: 'developer' }, { name: 'office' }]
  },
  {
    id: 2,
    title: 'Wireless Gaming Mouse',
    description: 'High precision wireless gaming mouse',
    brand: {
      name: 'Logitech'
    },
    categories: ['Mouse', 'Gaming'],
    metadata: {
      sku: 'G-PRO-X',
      color: 'White'
    },
    price: 80,
    tags: [{ name: 'gaming' }]
  }
];
 
productSearch.addMany(products);

Result ID yang ter-index:

['1', '2'];

Analyzer

Analyzer bertanggung jawab mengubah text menjadi token yang dapat di-index dan dicari.

Contoh:

analyzer: {
  lowercase: true,
  foldAccents: true,
  minTokenLength: 2,
  stopWords: [
    'the',
    'and',
    'atau',
    'dan',
    'dengan'
  ]
}

Analyzer dapat menangani:

• lowercase
• accent folding
• tokenization
• stop words
• minimum token length
• maximum token length
• custom tokenizer
• custom token normalization

Analyzer Pipeline

Secara konseptual pipeline analyzer adalah:

Raw Text
   │
   ▼
Text Normalization
   │
   ├── lowercase
   └── accent folding
   │
   ▼
Tokenizer
   │
   ▼
Token Normalization
   │
   ▼
Stop-word filtering
   │
   ▼
Minimum / Maximum length filtering
   │
   ▼
Indexed Tokens

Contoh:

"Mechanical KEYBOARD"

dengan:

lowercase: true;

menjadi:

["mechanical", "keyboard"]

Lowercase

Default analyzer dapat dibuat case-insensitive melalui:

analyzer: {
  lowercase: true;
}

Contoh:

KEYBOARD
Keyboard
KeYbOaRd

dapat dinormalisasi menjadi:

keyboard

Jika:

lowercase: false;

maka case dapat dipertahankan.

Hal ini juga berarti bahwa API vocabulary harus dipahami sebagai hasil indexing/analyzer, bukan daftar raw string dari document.

Contohnya pada konfigurasi case-sensitive, vocabulary dapat mengandung:

Mechanical

bukan:

mechanical

Jangan mengasumsikan getVocabulary() selalu lowercase; behavior tersebut mengikuti konfigurasi analyzer.

Accent Folding

Accent/diacritic folding memungkinkan variasi:

café
résumé
naïve
São Paulo
über

dipetakan menjadi bentuk yang lebih mudah dicari:

cafe
resume
naive
Sao Paulo
uber

Ini berguna untuk search yang tidak ingin membedakan:

é
e

atau karakter beraksen lainnya.

Dapat dinonaktifkan jika aplikasi membutuhkan exact linguistic distinction.

Stop Words

Stop words dapat dikonfigurasi:

analyzer: {
  stopWords: ['the', 'and', 'atau', 'dan', 'dengan'];
}

Contoh:

"keyboard dan mouse"

dapat menghasilkan token:

keyboard
mouse

Stop words juga dapat diberikan secara khusus pada query jika API search mendukung konfigurasi tersebut.

Token Length

Analyzer dapat membatasi ukuran token.

Contoh:

analyzer: {
  minTokenLength: 3;
}

Dengan demikian token terlalu pendek tidak akan masuk index.

Ini juga penting untuk fuzzy search karena typo tolerance pada token sangat pendek cenderung menghasilkan false positive.

Custom Tokenizer

Tokenizer dapat dikustomisasi apabila aplikasi mempunyai aturan tokenisasi khusus.

Contoh kebutuhan:

K8-PRO
AB-CD
v1.2.3
foo_bar

Tidak semua domain cocok dengan tokenizer default.

Custom tokenizer memungkinkan aplikasi menentukan token boundary sendiri.

normalizeToken() — batas penting

normalizeToken() bekerja terhadap token yang sudah dihasilkan tokenizer.

Contoh:

normalizeToken: token => token.replace(/-/g, '');

Tidak berarti tokenizer akan menggabungkan:

AB-CD

menjadi:

ABCD

jika tokenizer sebelumnya sudah menghasilkan:

['AB', 'CD'];

Pipeline-nya adalah:

AB-CD
  ↓
Tokenizer
  ↓
["AB", "CD"]
  ↓
normalizeToken()
  ↓
["AB", "CD"]

Jadi:

normalizeToken() dapat mengubah isi token, tetapi tidak bertanggung jawab mengubah token boundaries.

Jika aplikasi membutuhkan:

AB-CD → ABCD

maka preprocessing atau custom tokenizer perlu digunakan pada tahap yang sesuai.

Exact Search

Exact search mencari token yang sama dengan query setelah melewati analyzer.

productSearch.search('keyboard');

dapat menemukan:

Mechanical Keyboard RGB

Demikian juga:

productSearch.search('mouse');

menemukan document mouse.

Exact matching mempunyai score lebih tinggi daripada fuzzy matching terhadap term yang sama.

Prefix Search

Prefix search memungkinkan query yang belum lengkap.

Contoh:

productSearch.search('mou');

dapat menemukan:

mouse

Query:

key

dapat menemukan:

keyboard

Prefix matching berbeda dari substring matching.

Misalnya token:

keyboard

memiliki prefix:

key
keyb
keybo
keyboa

tetapi query substring arbitrer seperti:

boa

tidak otomatis berarti exact token match.

Fuzzy Search

Fuzzy search menangani typo.

Contoh:

productSearch.search('keybard');

dapat memetakan:

keybard
   ↓
keyboard

Dengan:

distance = 1
similarity = 0.875

Contoh lain:

productSearch.search('moue');

dapat memetakan:

moue
  ↓
mouse

Dengan:

distance = 1
similarity = 0.8

Konfigurasi Fuzzy

Contoh:

fuzzy: {
  enabled: true,
  maxDistanceRatio: 0.34,
  minTokenLength: 3,
  maxSuggestions: 5,
  enablePrefix: true,
  similarityBoost: 1
}

Parameter utamanya:

enabled

Mengaktifkan atau menonaktifkan fuzzy matching.

maxDistanceRatio

Menentukan batas relatif typo terhadap panjang token.

minTokenLength

Menghindari fuzzy matching terhadap token yang terlalu pendek.

maxSuggestions

Membatasi jumlah kandidat fuzzy.

enablePrefix

Mengaktifkan prefix retrieval.

similarityBoost

Mengatur pengaruh similarity fuzzy terhadap score.

BK-tree

Fuzzy search tidak harus membandingkan query dengan setiap vocabulary term secara brute-force.

Engine menggunakan BK-tree sebagai struktur auxiliary untuk vocabulary fuzzy lookup.

Secara konseptual:

Vocabulary
    │
    ▼
 BK-tree
    │
    ├── keyboard
    ├── mouse
    ├── mechanical
    ├── wireless
    └── ...

Ketika query:

keybard

masuk:

keybard
   │
   ▼
BK-tree
   │
   ▼
keyboard

kemudian vocabulary term tersebut digunakan untuk mengambil posting dari inverted index.

BK-tree terutama berguna untuk memperkecil ruang pencarian fuzzy pada vocabulary yang lebih besar.

Prefix Trie

Prefix search menggunakan Prefix Trie.

Contoh vocabulary:

keycap
keyboard
keyboardist
keychron

Prefix:

key

akan menemukan seluruh term tersebut.

Trie merupakan auxiliary structure untuk prefix lookup.

Ordering hasil Trie sebaiknya dianggap sebagai implementation detail kecuali API secara eksplisit menjanjikan ordering tertentu.

levenshteinDistance()

Utility dasar:

levenshteinDistance('kitten', 'sitting');

menghasilkan:

3

Contoh:

levenshteinDistance('keyboard', 'keybard');

menghasilkan:

1

Distance berarti jumlah minimum operasi edit:

• insertion
• deletion
• substitution

normalizedLevenshtein()

Normalized Levenshtein memberikan nilai similarity antara:

0;

dan:

1;

Contoh:

normalizedLevenshtein('mouse', 'moue');

menghasilkan similarity sesuai normalized edit distance.

Secara umum:

1 = identical
0 = completely dissimilar

Utility ini berguna ketika aplikasi ingin bekerja dengan similarity daripada raw edit distance.

Damerau-Levenshtein

Damerau-Levenshtein memperhitungkan transposition.

Contoh typo:

teh
the

dapat dipahami sebagai pertukaran posisi karakter.

Utility:

damerauLevenshteinDistance('teh', 'the');

berguna untuk typo keyboard-style seperti character transposition.

Jaro Similarity

Engine v2 juga dapat menggunakan:

jaroSimilarity('martha', 'marhta');

Jaro cocok untuk mengukur kemiripan string dengan perhatian pada posisi karakter.

Jaro-Winkler Similarity

Jaro-Winkler memberikan perhatian tambahan pada shared prefix.

Contoh:

jaroWinklerSimilarity('martha', 'marhta');

Utility ini berguna untuk eksperimen atau strategi ranking fuzzy yang lebih sophisticated.

Utility similarity tersebut tidak harus digunakan oleh scoring default engine dan dapat dipakai sebagai building block untuk strategi custom.

levenshteinSuggestions()

Utility ini dapat digunakan tanpa membuat search engine.

import { levenshteinSuggestions } from '@repo/engine-mini-search';
 
const suggestions = levenshteinSuggestions('javasript', ['javascript', 'typescript', 'java', 'python', 'rust'], {
  maxDistanceRatio: 0.34,
  limit: 5
});

Hasilnya berbentuk suggestion object:

[
  {
    term: 'javascript',
    distance: 1,
    similarity: 0.9
  }
];

Utility ini cocok untuk:

• autocomplete correction
• spell correction
• search suggestion
• command suggestion
• dictionary matching
• independent fuzzy matching

suggest()

Engine menyediakan API khusus term suggestion:

productSearch.suggest('keybord');

Contoh hasil:

[
  {
    term: 'keyboard',
    distance: 1,
    similarity: 0.875,
    source: 'fuzzy'
  }
];

Untuk:

productSearch.suggest('mou');

hasil dapat berupa:

[
  {
    term: 'mouse',
    distance: 0,
    similarity: 0.6,
    source: 'prefix'
  }
];

Exact Suggestion

Secara default suggestion API dapat mengecualikan exact match.

Misalnya:

productSearch.suggest('keyboard');

dapat menghasilkan:

[];

karena:

keyboard → keyboard

bukan suggestion yang diperlukan.

Jika aplikasi ingin exact term tetap muncul, gunakan konfigurasi yang menyediakan includeExact.

Konsepnya:

productSearch.suggest('keyboard', {
  includeExact: true
});

dapat menghasilkan:

[
  {
    term: 'keyboard',
    distance: 0,
    similarity: 1
  }
];

Ini memungkinkan UI membedakan:

No correction needed

dengan:

Did you mean...?

Prefix Suggestion

Suggestion juga dapat berasal dari prefix.

productSearch.suggest('mou');

dapat menghasilkan:

[
  {
    term: 'mouse',
    distance: 0,
    similarity: 0.6,
    source: 'prefix'
  }
];

Perhatikan:

distance = 0

di sini tidak berarti mou identik dengan mouse.

Distance fuzzy tidak selalu cukup untuk merepresentasikan prefix relation; source dan similarity harus diperhatikan.

suggestQuery()

Untuk query multi-token:

productSearch.suggestQuery('mechnaical keybord');

dapat menghasilkan mapping per query token:

{
  mechnaical: [
    {
      term: 'mechanical',
      distance: 1,
      similarity: 0.9
    }
  ],
  keybord: [
    {
      term: 'keyboard',
      distance: 1,
      similarity: 0.875
    }
  ]
}

Ini cocok untuk UI seperti:

Did you mean:
 
mechanical keyboard

atau correction per token.

search() dan suggest() mempunyai tujuan berbeda

Ini penting.

search()

Tujuan:

query → documents

Contoh:

productSearch.search('moue');

hasil:

Product #2

suggest()

Tujuan:

query → vocabulary terms

Contoh:

productSearch.suggest('moue');

hasil:

mouse

Jadi:

search();

menghasilkan document result, sedangkan:

suggest();

menghasilkan vocabulary suggestion.

Search Result

Search result v2 menyediakan informasi lebih kaya daripada hanya document dan score.

Secara konseptual:

{
  (id, data, score, matchedTokens, queryTokens, coverage, matches, suggestions, highlights);
}

Contoh:

{
  id: '1',
  data: product,
  score: 11.89,
  matchedTokens: 1,
  queryTokens: 1,
  coverage: 1,
  matches: [
    {
      queryToken: 'keyboard',
      matchedToken: 'keyboard',
      type: 'exact',
      distance: 0,
      similarity: 1,
      fieldContributions: [
        {
          field: 'title',
          weight: 5,
          termFrequency: 1,
          fieldLength: 3,
          averageFieldLength: 3,
          bm25: 0.69,
          multiplier: 2.06,
          score: 7.17
        }
      ]
    }
  ]
}

Detail numerik score bergantung pada konfigurasi dan isi index.

Match Type

Match dapat diklasifikasikan sebagai:

exact
prefix
fuzzy

Contoh:

keyboard → keyboard

adalah:

exact

Sedangkan:

mou → mouse

adalah:

prefix

Dan:

moue → mouse

adalah:

fuzzy

Informasi ini tersedia melalui matches.

Coverage

coverage menunjukkan seberapa banyak query token yang berhasil mendapatkan match.

Misalnya:

query:
mechanical keyboard

mempunyai:

2 query tokens

Jika keduanya match:

matchedTokens = 2
queryTokens = 2
coverage = 1

Jika hanya satu yang match:

matchedTokens = 1
queryTokens = 2
coverage = 0.5

Coverage berguna untuk membedakan:

complete query match

dengan:

partial query match

AND Search

Mode:

productSearch.search('mechanical keyboard', {
  mode: 'and'
});

mengharuskan seluruh query token memiliki match yang memenuhi aturan retrieval.

Secara konseptual:

mechanical ✓
keyboard  ✓
 
→ document eligible

Sedangkan:

mechanical ✓
keyboard   ✗
 
→ document excluded

OR Search

Mode:

productSearch.search('mechanical keyboard', {
  mode: 'or'
});

memungkinkan document yang hanya cocok dengan sebagian query token.

Contoh:

mechanical ✓
keyboard   ✗

tetap dapat menjadi candidate.

Ranking kemudian menentukan seberapa relevan document tersebut.

OR search cocok untuk:

• broad search
• autocomplete
• exploratory search
• partial query

Phrase Matching

Engine dapat mendeteksi phrase.

Misalnya:

mechanical keyboard

muncul sebagai phrase pada field.

Phrase matching dapat memberikan boost:

scoring: {
  phrase: 2;
}

Sehingga document yang memiliki phrase lebih dekat dapat memperoleh ranking lebih tinggi dibanding document yang hanya memiliki kedua token secara terpisah.

Scoring

Scoring configurable.

Contoh:

scoring: {
  exact: 1,
  prefix: 0.5,
  fuzzy: 0.7,
  phrase: 2,
  coverage: 1,
  frequency: 0.25
}

Secara konseptual ranking mempertimbangkan:

exact match
    +
prefix match
    +
fuzzy similarity
    +
field weight
    +
phrase boost
    +
coverage
    +
term frequency
    +
custom score

Tujuan utamanya adalah menghasilkan relevance score, bukan sekadar boolean match.

Exact vs Fuzzy Ranking

Exact match harus mempunyai relevance lebih tinggi daripada fuzzy match terhadap term yang sama, jika komponen scoring dikonfigurasi demikian.

Contoh:

keyboard

lebih relevan terhadap:

keyboard

daripada:

keybard

Walaupun keduanya dapat mengarah ke document yang sama.

Field Contributions

Setiap match dapat membawa kontribusi per field:

fieldContributions: [
  {
    field: 'title',
    weight: 5,
    termFrequency: 1,
    fieldLength: 3,
    averageFieldLength: 3,
    bm25: 0.69,
    multiplier: 2.06,
    score: 7.17
  }
];

Ini sangat berguna untuk debugging relevance.

Aplikasi dapat mengetahui mengapa sebuah document memperoleh score tertentu.

Custom Scoring

Business relevance sering tidak dapat direpresentasikan hanya dengan text relevance.

Misalnya:

sales
popularity
rating
stock
freshness
priority

Engine menyediakan custom scoring hook.

Konsep:

customScore: ({ document, baseScore }) => {
  // business-specific score
};

Contoh:

customScore: ({ document }) => {
  if (document.metadata.color === 'Black') {
    return 0.25;
  }
 
  return 0;
};

Custom score kemudian dapat digunakan sebagai tambahan terhadap text relevance.

Pisahkan Retrieval dan Business Ranking

Arsitektur yang direkomendasikan:

Text Retrieval
      │
      ▼
Candidate Documents
      │
      ▼
Text Relevance
      │
      ▼
Business Score
      │
      ▼
Final Ranking

Jangan memasukkan seluruh business logic ke analyzer.

Analyzer seharusnya fokus pada:

text → tokens

Search/retrieval fokus pada:

query → candidates

Scoring fokus pada:

candidates → relevance

Business scoring fokus pada:

relevance + domain signals

Filtering

Filter dibuat generic karena engine tidak mengetahui domain model.

Contoh:

productSearch.search('keyboard', {
  filter: product => product.price <= 200 && product.brand.name === 'Keychron'
});

Engine tidak perlu memahami:

price
brand
tenant
permission
availability
status
category

Semua merupakan tanggung jawab aplikasi.

Filtering dan Retrieval

Filter idealnya dipahami sebagai:

query
  │
  ▼
search candidates
  │
  ▼
filter
  │
  ▼
ranking
  │
  ▼
pagination

Implementasi internal dapat mengoptimalkan urutannya selama contract publik tetap dipertahankan.

Structured Object

Field dapat mengambil structured object.

Contoh:

{
  name: 'metadata',
  weight: 1,
  extract: product => product.metadata,
  stringify: value => {
    const metadata = value as Product['metadata'];
    return [metadata.sku, metadata.color].join(' ');
  }
}

Ini membuat object:

{
  sku: 'K8-PRO',
  color: 'Black'
}

dapat menjadi:

K8-PRO Black

untuk indexing.

Mengapa Tidak JSON.stringify() Semua Object?

Engine tidak seharusnya secara membabi buta melakukan:

JSON.stringify(value);

terhadap seluruh structured object.

Alasannya:

• field internal mungkin tidak relevan;
• metadata sensitif mungkin ikut ter-index;
• nested object dapat menghasilkan noise;
• array/object semantics dapat tidak sesuai kebutuhan search;
• ukuran vocabulary dapat membesar;
• representation JSON bukan selalu representation searchable yang baik.

Custom stringify memberikan kontrol penuh kepada aplikasi.

Array Field

Extractor dapat mengembalikan array.

Contoh:

{
  name: 'categories',
  extract: product => product.categories
}

atau:

{
  name: 'tags',
  extract: product => product.tags.map(tag => tag.name)
}

Engine akan memproses nilai tersebut sesuai semantics field/indexer.

search() Query Options

Contoh:

productSearch.search('mechnaical keybord', {
  mode: 'or',
  limit: 10
});

Search options dapat mencakup fitur seperti:

mode
filter
limit
offset
minScore
fuzzy configuration
phrase boost
prefix/fuzzy enablement
custom scoring

Exact shape mengikuti exported TypeScript API v2.

Pagination

Search mendukung:

{
  limit: 20,
  offset: 40
}

Konsep:

offset = 40
limit  = 20

berarti mengambil result:

41 ... 60

Jika offset negatif, engine menormalkannya sesuai contract v2.

limit juga dibatasi oleh:

maxLimit;

untuk mencegah query meminta result yang tidak masuk akal.

maxLimit

Contoh:

maxLimit: 100;

mencegah consumer meminta:

limit: 1000000;

secara tidak sengaja.

Ini merupakan guardrail penting untuk in-memory engine.

maxCandidates

Fuzzy search dapat menghasilkan candidate vocabulary dalam jumlah besar.

Konfigurasi:

maxCandidates: 50_000;

membatasi candidate pool.

Ini berbeda dari:

limit;

karena:

maxCandidates

mengontrol jumlah candidate yang diproses internal, sedangkan:

limit

mengontrol jumlah result yang dikembalikan ke caller.

searchOne()

Jika aplikasi hanya membutuhkan satu result:

const result = productSearch.searchOne('keyboard');

Jika tidak ada match:

null;

API ini berguna untuk use case seperti:

• lookup
• best match
• command resolution
• single-result autocomplete

Highlighting

Search result dapat menyediakan:

result.highlights;

Contoh:

{
  title: 'Mechanical <mark>Keyboard</mark> RGB',
  description: 'Professional mechanical <mark>keyboard</mark>'
}

Highlight mempertahankan source text sehingga casing asli dapat tetap dipertahankan.

Highlighting dan Security

Highlight HTML harus dianggap sebagai untrusted output apabila source data berasal dari:

• user
• external API
• CMS
• database yang tidak sepenuhnya trusted

Jangan menganggap:

result.highlights.title;

selalu aman untuk:

<div
  dangerouslySetInnerHTML={{
    __html: result.highlights.title
  }}
/>

Jika source text tidak trusted, pendekatan yang lebih aman adalah melakukan rendering token/highlight secara terstruktur di UI daripada memasukkan HTML mentah.

Update

Update mengganti searchable representation document.

Contoh:

productSearch.update('1', {
  id: 1,
  title: 'Mechanical Keyboard Pro',
  description: 'Professional keyboard',
  brand: {
    name: 'Keychron'
  },
  categories: ['Keyboard'],
  metadata: {
    sku: 'K8-PRO',
    color: 'Black'
  },
  price: 140,
  tags: []
});

Update harus memperbarui seluruh auxiliary state yang relevan.

Term lama tidak boleh terus membuat document dapat ditemukan apabila term tersebut memang sudah tidak ada pada document baru.

Remove

Hapus document:

productSearch.remove('1');

Kemudian:

productSearch.has('1');

harus menunjukkan document sudah tidak berada di index.

Remove juga harus membersihkan postings dan vocabulary yang tidak lagi memiliki document.

Term yang masih digunakan document lain harus tetap dipertahankan.

Shared vs Unique Vocabulary

Misalnya:

Document 1:
keyboard
mechanical
 
Document 2:
keyboard
mouse

Setelah remove document 1:

keyboard

harus tetap ada karena masih digunakan document 2.

Sedangkan:

mechanical

dapat dihapus dari vocabulary jika tidak digunakan document lain.

Ini merupakan salah satu invariant penting index lifecycle.

clear()

Untuk menghapus seluruh index:

productSearch.clear();

Setelah clear():

documents = 0
vocabulary = []
search() = []
suggest() = []

Engine juga harus tetap reusable.

Contoh:

productSearch.clear();
 
productSearch.add(product);
 
productSearch.search('keyboard');

harus kembali berfungsi normal.

Re-add

Lifecycle berikut harus valid:

add
 ↓
remove
 ↓
add

Document dapat ditambahkan kembali tanpa meninggalkan stale index state.

Untuk production, sequence yang lebih agresif juga idealnya diuji:

add
remove
add
remove
add
update
remove
add

Custom ID Resolver

Engine tidak mengasumsikan nama property ID.

Contoh:

id: product => String(product.id);

Untuk domain lain:

id: user => user.userId;

atau:

id: article => article.slug;

Dengan demikian engine tidak mengharuskan:

document.id;

sebagai satu-satunya convention.

Missing ID Resolver

Jika engine membutuhkan ID resolver tetapi konfigurasi tidak menyediakannya, operasi add() dapat gagal secara eksplisit.

Ini lebih aman daripada engine mencoba menebak:

id
_id
uuid
key
slug

secara implisit.

Library reusable sebaiknya deterministic.

Hooks

Engine menyediakan lifecycle hooks untuk kebutuhan aplikasi.

Contoh konsep:

onIndexed;
onRemoved;

Hook berguna untuk:

• logging
• metrics
• cache invalidation
• observability
• event integration
• audit
• debugging

Hook sebaiknya tidak menjadi bagian dari retrieval logic.

Statistics

Engine menyediakan statistik index:

productSearch.stats();

Informasi statistik dapat mencakup:

documents
vocabularySize
indexedTokens
fields

serta informasi auxiliary seperti average field lengths sesuai API v2.

Contoh:

{
  documents: 2,
  vocabularySize: 9,
  indexedTokens: 9,
  fields: 2
}

Statistics berguna untuk:

• monitoring
• debugging
• test invariant
• memory estimation
• observability

Vocabulary

Untuk inspeksi vocabulary:

productSearch.getVocabulary();

Contoh:

['gaming', 'high', 'keyboard', 'mechanical', 'mouse', 'precision', 'professional', 'rgb', 'wireless'];

Vocabulary merupakan vocabulary hasil indexing/analyzer.

Karena itu casing, normalization, stop-word removal, dan tokenization dapat memengaruhi hasilnya.

Jangan menganggap vocabulary sebagai daftar raw words dari source document.

Rebuild

rebuild() digunakan untuk membangun ulang auxiliary/index structures berdasarkan document state yang tersedia.

Tujuan utama:

documents
   ↓
rebuild
   ↓
indexes
BK-tree
Trie
statistics

Rebuild berguna setelah operasi maintenance atau ketika implementasi internal membutuhkan reconstruction.

Behavior search seharusnya tetap konsisten sebelum dan sesudah rebuild.

Optimize

optimize() ditujukan untuk merapikan/mengefisienkan internal index structures tanpa mengubah contract search.

Prinsip penting:

search(before optimize)
        ≈
search(after optimize)

Terutama:

• exact retrieval tetap benar;
• prefix retrieval tetap benar;
• fuzzy retrieval tetap benar;
• vocabulary stale tidak muncul;
• document tidak hilang.

Ranking detail tidak seharusnya diasumsikan identik jika implementation optimization memang mengubah internal candidate ordering, kecuali API secara eksplisit menjanjikan deterministic ranking.

Rebuild vs Optimize

Keduanya bukan konsep yang sama.

rebuild()

Fokus:

reconstruct index state

optimize()

Fokus:

compact / improve existing index structures

Keduanya harus menjaga correctness public API.

Index Architecture

Secara konseptual engine terdiri dari beberapa layer:

                    Application Data
                           │
                           ▼
                    Field Extractor
                           │
                           ▼
                     Token Analyzer
                           │
             ┌─────────────┼─────────────┐
             │             │             │
         normalize      tokenize      filtering
             │             │             │
             └─────────────┼─────────────┘
                           │
                           ▼
                    Indexed Tokens
                           │
              ┌────────────┼────────────┐
              │            │            │
              ▼            ▼            ▼
        Inverted Index   PrefixTrie   BK-tree
              │            │            │
              │            │            │
              └────────────┼────────────┘
                           │
                           ▼
                    Candidate Retrieval
                           │
                           ▼
                         Scoring
                           │
             ┌─────────────┼─────────────┐
             │             │             │
           exact         prefix        fuzzy
             │             │             │
             └─────────────┼─────────────┘
                           │
                     phrase boost
                           │
                       coverage
                           │
                       frequency
                           │
                    custom business score
                           │
                           ▼
                    Ranked Results
                           │
                           ▼
                filtering / pagination
                           │
                           ▼
                     SearchResult[]

Contoh End-to-End

Konfigurasi:

import { createSearchEngine } from '@repo/engine-mini-search';
 
const productSearch = createSearchEngine<Product>({
  id: product => String(product.id),
  fields: [
    {
      name: 'title',
      weight: 5,
      extract: product => product.title
    },
    {
      name: 'brand',
      weight: 4,
      extract: product => product.brand.name
    },
    {
      name: 'description',
      weight: 1,
      extract: product => product.description
    },
    {
      name: 'categories',
      weight: 2,
      extract: product => product.categories
    },
    {
      name: 'tags',
      weight: 2,
      extract: product => product.tags.map(tag => tag.name)
    },
    {
      name: 'sku',
      weight: 6,
      extract: product => product.metadata.sku
    },
    {
      name: 'color',
      weight: 1,
      extract: product => product.metadata.color
    }
  ],
  analyzer: {
    lowercase: true,
    foldAccents: true,
    minTokenLength: 2,
    stopWords: ['the', 'and', 'atau', 'dan', 'dengan']
  },
  fuzzy: {
    enabled: true,
    maxDistanceRatio: 0.34,
    minTokenLength: 3,
    maxSuggestions: 5,
    enablePrefix: true,
    similarityBoost: 1 // for v1
  },
  scoring: {
    exact: 1, // for v1
    prefix: 0.5, // for v1
    fuzzy: 0.7, // for v1
    phrase: 2, // for v1
    coverage: 1, // for v1
    frequency: 0.25 // for v1
  },
  maxCandidates: 50_000,
  maxLimit: 100
});

Index:

productSearch.addMany(products);

Search exact:

productSearch.search('keyboard');

Search fuzzy:

productSearch.search('keybord');

Search prefix:

productSearch.search('mou');

Multi-token fuzzy:

productSearch.search('mechnaical keybord', {
  mode: 'or',
  limit: 10
});

Suggestion:

productSearch.suggest('keybord');

Query suggestion:

productSearch.suggestQuery('mechnaical keybord');

Contoh Fuzzy Search moue

Query:

productSearch.search('moue');

Pipeline konseptual:

"moue"
   │
   ▼
Analyzer
   │
   ▼
["moue"]
   │
   ▼
BK-tree
   │
   ▼
"mouse"
   │
   ▼
Inverted Index
   │
   ▼
Document #2
   │
   ▼
Scoring
   │
   ▼
SearchResult[]

Match:

queryToken  = moue
matchedToken = mouse
type         = fuzzy
distance     = 1
similarity   = 0.8

Jadi fuzzy search bukan sekadar:

replace typo

melainkan:

query
 → vocabulary candidate
 → document postings
 → relevance scoring

Exact, Prefix, dan Fuzzy Secara Bersamaan

Sebuah query dapat melewati beberapa retrieval strategy.

Secara konseptual:

query token
    │
    ├── exact lookup
    │
    ├── prefix lookup
    │
    └── fuzzy lookup

Kemudian candidate digabungkan dan diberi score.

Contoh:

keyboard

lebih kuat:

exact

daripada:

keybord → keyboard

Sedangkan:

mou → mouse

dapat diperoleh melalui:

prefix

dan:

moue → mouse

melalui:

fuzzy

Contract suggest() yang Penting

Suggestion bukan document search.

Contoh:

productSearch.suggest('keyboard');

dapat menghasilkan:

[];

karena exact term biasanya tidak perlu disarankan.

Sedangkan:

productSearch.suggest('keybord');

menghasilkan:

[
  {
    term: 'keyboard',
    distance: 1,
    similarity: 0.875,
    source: 'fuzzy'
  }
];

Dan:

productSearch.suggest('mou');

dapat menghasilkan:

[
  {
    term: 'mouse',
    distance: 0,
    similarity: 0.6,
    source: 'prefix'
  }
];

Query yang Tidak Ditemukan

Jika query tidak memiliki candidate yang memenuhi threshold:

productSearch.search('completely-unrelated-term');

hasilnya:

[];

Demikian juga suggestion dapat:

[];

jika tidak ada vocabulary term yang memenuhi threshold.

Fuzzy search tidak berarti setiap typo pasti mempunyai result.

Threshold tetap harus dipenuhi.

Fuzzy Matching Bukan Unlimited Correction

Dengan:

maxDistanceRatio: 0.34;

engine hanya menerima candidate dalam batas tertentu.

Contoh:

mouse

dapat match:

moue

tetapi string yang terlalu jauh tidak boleh dipaksakan menjadi:

mouse

Hal ini penting untuk menghindari false positives.

Mengapa minTokenLength Penting?

Fuzzy search terhadap token pendek sangat berisiko.

Misalnya:

a
an
id
to
in

memiliki ruang kemungkinan yang sangat kecil.

Dengan:

minTokenLength: 3;

engine dapat menghindari fuzzy correction terhadap token pendek yang tidak reliable.

Deterministic Index Behavior

Engine v2 sebaiknya mempertahankan invariant bahwa correctness tidak bergantung pada insertion order.

Contoh:

insert A → B → C → D

dan:

insert D → C → B → A

harus tetap menghasilkan fuzzy retrieval yang benar.

Ini sangat penting khususnya untuk BK-tree karena bentuk tree dipengaruhi insertion order.

Lifecycle Invariants

Beberapa invariant penting:

Remove

Document yang sudah di-remove tidak boleh muncul kembali dalam search.

Update

Term lama yang unik tidak boleh tetap searchable setelah update.

Shared vocabulary

Term yang masih digunakan document lain tidak boleh ikut terhapus.

Clear

Semua searchable state harus dibersihkan.

Re-add

Document yang ditambahkan kembali harus searchable.

Optimize

Fuzzy, prefix, dan exact search harus tetap benar.

Rebuild

Search behavior harus tetap valid setelah rebuild.

Testing Strategy

Engine v2 sebaiknya diuji pada beberapa level.

Utility tests

stripDiacritics
normalizeText
levenshteinDistance
normalizedLevenshtein
damerauLevenshteinDistance
jaroSimilarity
jaroWinklerSimilarity

Data structure tests

BK-tree
PrefixTrie

Analyzer tests

tokenization
normalization
stopwords
length filtering
custom tokenizer
custom normalization

Engine tests

exact search
prefix search
fuzzy search
suggestions
ranking
filtering
highlighting
phrase matching
pagination

Lifecycle tests

add
update
remove
clear
rebuild
optimize
re-add

Regression tests

insertion order
stale vocabulary
stale BK-tree
stale Trie
update isolation

Production Test Invariants

Untuk test suite yang matang, jangan hanya menguji contoh:

expect(engine.search('keyboard')[0]?.id).toBe('1');

Tetapi juga invariant.

Contoh:

for (const term of engine.getVocabulary()) {
  const results = engine.search(term);
 
  expect(results.length).toBeGreaterThan(0);
}

Ini menguji hubungan:

vocabulary
     ↕
inverted index
     ↕
documents

Vocabulary Integrity

Untuk setiap vocabulary term:

term
 ↓
posting list
 ↓
document IDs
 ↓
existing documents

Tidak boleh ada posting ke document yang sudah tidak ada.

Secara konseptual:

for (const result of allResults) {
  expect(engine.has(result.id)).toBe(true);
}

Ini membantu mendeteksi stale posting.

Update Isolation

Update satu document tidak boleh mengubah searchable content document lain.

Misalnya:

Document 1 → keyboard
Document 2 → mouse

setelah:

engine.update('1', newDocument);

document 2 harus tetap dapat ditemukan melalui:

mouse

dan tidak boleh memperoleh term baru milik document 1.

Repeated Lifecycle Test

Production test juga sebaiknya menguji:

add
remove
add
remove
add
update
remove
add

berulang kali.

Tujuannya menemukan:

• memory leak
• stale postings
• duplicate postings
• stale vocabulary
• stale BK-tree nodes
• stale Trie terminals
• incorrect document frequency

Configuration Example Minimal

Untuk penggunaan sederhana:

const search = createSearchEngine<{
  id: string;
  title: string;
}>({
  id: item => item.id,
  fields: [
    {
      name: 'title',
      extract: item => item.title
    }
  ]
});

Kemudian:

search.add({
  id: '1',
  title: 'Mechanical Keyboard'
});
 
search.search('keyboard');

Configuration Example dengan Fuzzy

const search = createSearchEngine<{
  id: string;
  title: string;
}>({
  id: item => item.id,
  fields: [
    {
      name: 'title',
      weight: 5,
      extract: item => item.title
    }
  ],
  fuzzy: {
    enabled: true,
    maxDistanceRatio: 0.34,
    minTokenLength: 3
  }
});

Kemudian:

search.search('keybord');

dapat menemukan:

Mechanical Keyboard

Configuration yang Lebih Lengkap

Contoh production-oriented:

const search = createSearchEngine<Product>({
  id: product => String(product.id),
  fields: [
    {
      name: 'title',
      weight: 5,
      extract: product => product.title
    },
    {
      name: 'brand',
      weight: 4,
      extract: product => product.brand.name
    },
    {
      name: 'description',
      weight: 1,
      extract: product => product.description
    },
    {
      name: 'categories',
      weight: 2,
      extract: product => product.categories
    },
    {
      name: 'sku',
      weight: 6,
      extract: product => product.metadata.sku
    }
  ],
  analyzer: {
    lowercase: true,
    foldAccents: true,
    minTokenLength: 2,
    stopWords: ['the', 'and', 'atau', 'dan']
  },
  fuzzy: {
    enabled: true,
    maxDistanceRatio: 0.34,
    minTokenLength: 3,
    maxSuggestions: 5,
    enablePrefix: true,
    similarityBoost: 1 // for v1
  },
  scoring: {
    exact: 1, // for v1
    prefix: 0.5, // for v1
    fuzzy: 0.7, // for v1
    phrase: 2, // for v1
    coverage: 1, // for v1
    frequency: 0.25 // for v1
  },
  maxCandidates: 50_000,
  maxLimit: 100
});

Kapan Menggunakan Exact, Prefix, atau Fuzzy?

Exact

Gunakan ketika:

query sudah lengkap

Contoh:

keyboard

Prefix

Gunakan ketika:

user sedang mengetik

Contoh:

keyb

Fuzzy

Gunakan ketika:

user kemungkinan typo

Contoh:

keybord

Practical search UI biasanya memanfaatkan ketiganya secara bersamaan.

Contoh Search UI

Query:

keybord

Engine dapat menghasilkan:

Candidate:
keyboard

UI dapat menampilkan:

Showing results for "keyboard"

atau:

Did you mean "keyboard"?

Sementara query:

key

dapat memanfaatkan prefix suggestion:

keyboard
keychron
keycap

Schema Independence

Engine yang sama dapat digunakan untuk:

createSearchEngine<User>(...);
 
createSearchEngine<Product>(...);
 
createSearchEngine<Article>(...);
 
createSearchEngine<Ticket>(...);
 
createSearchEngine<Customer>(...);
 
createSearchEngine<Device>(...);

Tanpa mengubah core implementation.

Yang berubah hanya:

ID resolver
field extractor
field weights
analyzer configuration
business filtering
business scoring

Recommended Architecture

Application:

Domain Model
     │
     ▼
Search Configuration
     │
     ├── ID resolver
     ├── field extractor
     ├── analyzer
     ├── fuzzy config
     └── scoring
     │
     ▼
Mini Search Engine
     │
     ├── Analyzer
     ├── Inverted Index
     ├── BK-tree
     ├── Prefix Trie
     ├── Ranking
     └── Lifecycle
     │
     ▼
SearchResult<T>

Dengan separation ini, core engine tetap reusable.

In-Memory dan Production

Mini Search Engine v2 adalah:

production-oriented in-memory search engine

Artinya engine dapat digunakan dalam aplikasi production, tetapi storage modelnya tetap in-memory.

Production-oriented tidak berarti:

distributed search cluster

atau:

Lucene replacement

Engine ini lebih tepat digunakan ketika:

• index dapat disimpan di memory;
• dataset masih manageable;
• query latency rendah diperlukan;
• deployment sederhana lebih disukai;
• aplikasi membutuhkan embedded search;
• tidak ingin menjalankan external search cluster.

Estimasi Skala

Ukuran yang dapat ditangani bukan hanya berdasarkan jumlah document.

Faktor yang lebih penting:

number of documents
×
average indexed fields
×
average tokens/document
×
vocabulary size
×
posting list size
×
query rate
×
memory budget

Karena itu:

10K
100K
1M

tidak dapat dianggap sebagai batas absolut.

Aplikasi harus melakukan benchmark terhadap:

• document size;
• token count;
• vocabulary;
• fuzzy query rate;
• concurrent requests;
• memory;
• indexing frequency.

Kapan Beralih ke Search Infrastructure?

Jika requirement sudah menjadi:

10M+ documents

atau membutuhkan:

multi-node distributed index
replication
sharding
durable persistence
WAL
horizontal scaling
distributed query execution
faceted aggregation
geo search
advanced BM25/Lucene relevance

maka embedded in-memory engine bukan lagi pilihan arsitektur utama.

Pertimbangkan search infrastructure khusus seperti:

Elasticsearch
OpenSearch
Apache Solr
Lucene-based systems

atau search service lain sesuai kebutuhan.

Arsitektur Saat Skala Membesar

Pada skala besar, application architecture dapat berubah menjadi:

                  Search API
                      │
                      ▼
                 Query Parser
                      │
                      ▼
                 Search Service
                      │
        ┌─────────────┼─────────────┐
        │             │             │
        ▼             ▼             ▼
   Exact Index   Fuzzy Index   Persistent Store
        │             │             │
        └─────────────┼─────────────┘
                      │
                      ▼
                 Ranking Layer
                      │
                      ▼
                 Search Results

Mini Search Engine dapat tetap menjadi inspiration atau embedded component untuk service tertentu, tetapi distributed persistence bukan tujuan core v2.

Performance Considerations

Beberapa hal yang paling memengaruhi performa:

Vocabulary size

Semakin besar vocabulary:

BK-tree
Trie

semakin penting.

Number of indexed tokens

Lebih banyak token berarti:

larger inverted index

Fuzzy search

Fuzzy search lebih mahal daripada exact lookup.

Number of candidates

maxCandidates menjadi guardrail penting.

Field count

Semakin banyak searchable fields, semakin banyak extraction dan indexing work.

Document updates

Update biasanya membutuhkan maintenance terhadap index state.

Fuzzy Search Should Be Used Deliberately

Fuzzy search sebaiknya tidak selalu diperlakukan sebagai fallback tanpa batas.

Untuk production:

Exact
  ↓
Prefix
  ↓
Fuzzy

dapat digunakan sebagai mental model.

Exact merupakan signal terkuat.

Prefix cocok untuk incomplete input.

Fuzzy digunakan untuk typo tolerance.

Threshold terlalu longgar dapat menghasilkan:

false positives

sedangkan threshold terlalu ketat dapat menghasilkan:

false negatives

Relevance Tuning

Jika result yang benar tidak berada pada posisi pertama, jangan langsung mengubah fuzzy algorithm.

Periksa secara berurutan:

1. field extraction
2. analyzer
3. field weights
4. match type
5. fuzzy threshold
6. phrase boost
7. coverage
8. frequency
9. custom score

Search relevance merupakan gabungan beberapa signal.

Debugging Search Result

matches dan fieldContributions sangat berguna untuk debugging.

Jika:

result.score

terlihat terlalu tinggi/rendah, lihat:

matches
  ↓
matchedToken
  ↓
match type
  ↓
fieldContributions
  ↓
field weight
  ↓
BM25/frequency
  ↓
multiplier

Dengan demikian tuning dapat dilakukan berdasarkan evidence, bukan trial-and-error semata.

Search Contract vs Implementation Detail

API publik sebaiknya hanya menjamin behavior yang memang diperlukan.

Contoh yang aman dijadikan contract:

exact query menemukan exact term
fuzzy typo yang memenuhi threshold dapat ditemukan
prefix yang memenuhi prefix rule dapat ditemukan
removed document tidak muncul
updated content menggantikan old searchable content

Sedangkan detail seperti:

urutan traversal BK-tree
urutan traversal Trie
internal node structure
internal posting representation

sebaiknya tidak menjadi public contract kecuali memang diperlukan.

Summary API

Secara konseptual API v2 dapat dikelompokkan menjadi:

Engine

createSearchEngine<T>();

Lifecycle

add();
addMany();
update();
remove();
clear();
rebuild();
optimize();