> ## Documentation Index
> Fetch the complete documentation index at: https://docs.myspellchecker.com/llms.txt
> Use this file to discover all available pages before exploring further.

# N-gram Algorithm

> The N-gram algorithm provides context-aware spell checking by analyzing word sequence probabilities.

N-gram models capture the likelihood of word sequences, enabling detection of "real-word errors" where a correctly spelled word is used incorrectly in context.

## Overview

N-gram models capture the likelihood of word sequences, enabling detection of "real-word errors": correctly spelled words used incorrectly in context.

## How It Works

### Bigram Model (2-gram)

Calculates the probability of word pairs:

```python theme={null}
P(w2 | w1) = count(w1, w2) / count(w1)

# Example
P("စား" | "ထမင်း") = count("ထမင်း စား") / count("ထမင်း")
                    = 8500 / 10000
                    = 0.85
```

### Trigram Model (3-gram)

Extends to word triplets for richer context:

```python theme={null}
P(w3 | w1, w2) = count(w1, w2, w3) / count(w1, w2)
```

### 4-gram and 5-gram Models

Higher-order N-grams provide deeper context for detecting errors in longer phrases:

```python theme={null}
P(w4 | w1, w2, w3) = count(w1, w2, w3, w4) / count(w1, w2, w3)
P(w5 | w1, w2, w3, w4) = count(w1, w2, w3, w4, w5) / count(w1, w2, w3, w4)
```

These are stored in `fourgrams` and `fivegrams` database tables and configured via `fourgram_threshold` and `fivegram_threshold` in `NgramContextConfig` (both default to `0.0001`). The context checker uses backoff: if a 5-gram probability is available it takes precedence, falling back to 4-gram, trigram, then bigram.

## Smoothing Strategies

The library supports multiple smoothing strategies for handling unseen N-grams:

### Stupid Backoff (Default)

Fast and effective for most use cases:

```python theme={null}
P_backoff(w2 | w1) =
    P(w2 | w1)              if count(w1, w2) > 0
    α * P(w2)               otherwise

# Where α is the backoff weight (default: 0.4)
```

### Add-K (Laplace) Smoothing

Adds constant k to all counts:

```python theme={null}
P_smooth(w2 | w1) = (count(w1, w2) + k) / (count(w1) + k * V)

# Where V is vocabulary size, k is smoothing constant
```

### No Smoothing

Returns raw probabilities (for pre-smoothed data):

```python theme={null}
P(w2 | w1) = count(w1, w2) / count(w1)
# Returns 0 for unseen pairs
```

## Configuration

```python theme={null}
from myspellchecker.algorithms.ngram_context_checker import (
    NgramContextChecker,
    SmoothingStrategy,
)
from myspellchecker.core.config import NgramContextConfig

# All thresholds and weights are configured via NgramContextConfig
config = NgramContextConfig(
    bigram_threshold=0.0001,           # Probability threshold for flagging bigram errors
    trigram_threshold=0.0001,          # Probability threshold for flagging trigram errors
    fourgram_threshold=0.0001,         # 4-gram error threshold
    fivegram_threshold=0.0001,         # 5-gram error threshold
    smoothing_strategy="stupid_backoff",
    backoff_weight=0.4,
    add_k_smoothing=0.0,              # For ADD_K strategy (0.0 = disabled by default)
    edit_distance_weight=0.6,
    probability_weight=0.4,
)

checker = NgramContextChecker(
    provider=provider,
    config=config,           # NgramContextConfig (optional, uses defaults if None)
    symspell=symspell,       # SymSpell instance for candidate generation (optional)
    pos_unigram_probs=None,  # POS unigram probabilities (optional)
    pos_bigram_probs=None,   # POS bigram probabilities (optional)
)
```

<Note>
  When using `SpellCheckerConfig` (recommended), `NgramContextConfig` is created automatically from your config and passed to the checker. The values shown above are the defaults. Individual threshold parameters are **not** accepted as constructor kwargs; they must go through `NgramContextConfig`.
</Note>

## Error Detection

The checker uses a two-path detection strategy based on raw trigram availability:

1. **Trigram path**: When a raw trigram probability exists in the corpus (`P_raw(w3|w1,w2) > 0`), the checker uses the trigram-specific threshold (`trigram_threshold`, default `0.0001`) to determine if the word is an error. This avoids false positives from smoothed backoff values.

2. **Bigram fallback path**: When no raw trigram is found, the checker falls back to bigram probabilities with bidirectional context checking, unigram backoff for common words, and typo neighbor detection via SymSpell.

This design ensures that smoothed backoff values (which are always > 0) do not gate the checker into the trigram path, keeping the bigram heuristics reachable.

```python theme={null}
# Input: "ထမင်းသွား" (rice go)
# P("သွား" | "ထမင်း") = 0.0001  # Very low
# P("စား" | "ထမင်း") = 0.85    # High

# → Flag "သွား", suggest "စား"
```

## Suggestion Generation

Suggestions are generated by:

1. Finding words with higher conditional probability
2. Filtering by edit distance (max 2)
3. Ranking by combined probability and distance score

```python theme={null}
suggestions = checker.suggest(
    prev_word="ထမင်း",
    current_word="သွား",
    max_edit_distance=2,
    next_word="ပြီ",
)
```

## Performance

| Operation             | Complexity | Typical Time         |
| --------------------- | ---------- | -------------------- |
| Bigram lookup         | O(1)       | \<1ms                |
| Trigram lookup        | O(1)       | \<1ms                |
| Context analysis      | O(n)       | \~100ms for avg text |
| Suggestion generation | O(k)       | \~50ms               |

## Database Schema

N-gram data is stored in SQLite using INTEGER foreign keys referencing the `words` table (not TEXT columns):

```sql theme={null}
-- Bigrams (word IDs reference words.id)
CREATE TABLE bigrams (
    id INTEGER PRIMARY KEY AUTOINCREMENT,
    word1_id INTEGER,
    word2_id INTEGER,
    probability REAL DEFAULT 0.0,
    count INTEGER DEFAULT 0,
    FOREIGN KEY(word1_id) REFERENCES words(id),
    FOREIGN KEY(word2_id) REFERENCES words(id),
    UNIQUE(word1_id, word2_id)
);

-- Trigrams (word IDs reference words.id)
CREATE TABLE trigrams (
    id INTEGER PRIMARY KEY AUTOINCREMENT,
    word1_id INTEGER,
    word2_id INTEGER,
    word3_id INTEGER,
    probability REAL DEFAULT 0.0,
    count INTEGER DEFAULT 0,
    FOREIGN KEY(word1_id) REFERENCES words(id),
    FOREIGN KEY(word2_id) REFERENCES words(id),
    FOREIGN KEY(word3_id) REFERENCES words(id),
    UNIQUE(word1_id, word2_id, word3_id)
);
```

To query bigrams for a specific word, use a JOIN:

```sql theme={null}
SELECT w1.word, w2.word, b.probability
FROM bigrams b
JOIN words w1 ON b.word1_id = w1.id
JOIN words w2 ON b.word2_id = w2.id
WHERE w1.word = 'ထမင်း'
ORDER BY b.probability DESC;
```

## NgramContextChecker Methods

| Method                                                  | Description                                                  |
| ------------------------------------------------------- | ------------------------------------------------------------ |
| `get_smoothed_bigram_probability(w1, w2)`               | Smoothed P(w2 \| w1)                                         |
| `get_smoothed_trigram_probability(w1, w2, w3)`          | Smoothed P(w3 \| w1, w2)                                     |
| `get_smoothed_fourgram_probability(w1, w2, w3, w4)`     | Smoothed P(w4 \| w1, w2, w3)                                 |
| `get_smoothed_fivegram_probability(w1, w2, w3, w4, w5)` | Smoothed P(w5 \| w1, w2, w3, w4)                             |
| `get_best_left_probability(prev_words, candidate)`      | Best left-context probability across available N-gram orders |
| `get_best_right_probability(candidate, next_words)`     | Best right-context probability                               |
| `is_contextual_error(prev_word, current_word, ...)`     | Check if word is contextually unlikely                       |
| `check_word_in_context(word, prev_words, next_words)`   | Full context check with suggestions                          |
| `compare_contextual_probability(w1, w2, context)`       | Compare probabilities between two candidates                 |
| `suggest(prev_word, current_word, ...)`                 | Generate context-aware suggestions                           |
| `clear_context_cache()`                                 | Clear all internal probability caches                        |

## See Also

* [Context Checking](/features/context-checking) - Feature documentation
* [SymSpell Algorithm](/algorithms/symspell) - Word-level suggestions
* [Semantic Checking](/algorithms/semantic) - AI-powered context analysis
* [Performance Tuning](/guides/performance-tuning) - Optimization