Metadata-Version: 2.4
Name: nmd
Version: 0.1.0
Summary: A string similarity measure based on the Earth Mover's Distance
Author-email: Avery Khoo <averykhoo@gmail.com>
Requires-Python: >=3.10
Description-Content-Type: text/markdown
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
License-File: LICENSE
Project-URL: Home, https://github.com/averykhoo/ngram-movers-distance

# N-gram Mover's Distance

**Fuzzy lookup for short strings: spelling correction, and dictionary, name or code lookup.**

A string similarity measure based on the Earth Mover's Distance, plus an index built around it.
It answers *"which entries in my list is this typo closest to?"* for strings of roughly under 20
characters, where the errors are edits -- transpositions, dropped letters, phonetic guesses.

On that job it is the best of the systems measured below: +0.07 to +0.28 test MAP over the best
baseline on all five such tasks, at 1-7 ms/query, and ~100x faster than the brute-force
edit-distance scan that is the honest alternative. On records and on prose it is not; see
[what this is good for](https://github.com/averykhoo/ngram-movers-distance#what-this-is-good-for-and-what-it-is-not) before reaching for it.

```bash
pip install nmd  # no dependencies, python >= 3.10
```

```python
from nmd import WordList

word_list = WordList((2, 4), filter_n=0)
for word in ('photographer', 'cartographer', 'choreographer', 'photography'):
    word_list.add_word(word)

word_list.lookup('fotografer')
# [('photographer', (9.9, 13.87)), ('cartographer', (7.95, 11.92)),
#  ('photography', (7.76, 9.73)), ('choreographer', (5.91, 9.86))]
```

Code: [ngram-movers-distance](https://github.com/averykhoo/ngram-movers-distance)

## Why another string matching algorithm?

* Edit distance really wasn't cutting it when I needed to look up a dictionary for a misspelled word
    * With an edit distance of 1 or 2, the results are not useful since the target word isn't found
    * With a distance >=5, the results are meaningless since it contains half the dictionary
    * Same goes for Damerau-Levenshtein
    * concretely, for `fotografer` over the 41.5k words of `experiments/words_en.txt`:
      Damerau-Levenshtein finds **nothing** within distance 2, and **65 words** within
      distance 5. nmd ranks `photographer` first (measured 2026-09-17)
* Also, edit distance is pretty slow when looking up long words in a large dictionary
    * Even after building a finite state automaton or using a trie to optimize lookup
    * NMD was designed with indexing in mind
        * A simpler index could be used for Jaccard or cosine similarity over ngrams
* EMD (and hence NMD) can be optimized to run really fast with some constraints
    * Values are 1-dimensional scalars
    * Values are always quantized

## What this is good for, and what it is not

Measured against char-BM25, token BM25, tf-idf cosine and brute-force Damerau-Levenshtein over
17 retrieval tasks, tune/test halves, every system tuned on its own grid
(`docs/bow-plan.md` part 10, measured 2026-09-06):

| your data | verdict |
|---|---|
| **short strings** -- spelling correction, dictionary / name / code lookup, roughly under 20 characters, where the error model is edits | **use it.** Best system measured: +0.07 to +0.28 test MAP over the best baseline on all five such tasks, at 1-7 ms/query, and ~100x faster than the brute-force edit-distance scan that is the honest alternative |
| **records** -- product titles, citations, addresses, 50-300 characters | **probably not.** Within +/-0.02 MAP of char-BM25 or tf-idf cosine on nine of ten tasks and 0.057 behind on the tenth, at 5-10x the query cost. Worth it only if one index has to serve both regimes |
| **documents** -- 100+ characters of prose | **no.** Behind BM25 (nDCG@10 0.650 vs 0.679 on scifact), and only that close with `normalize=False` and `n=(4,)`; at the library defaults it scores 0.029 |

Nor is it a useful *complement* to a text-search engine: as a reranker over BM25's top-50, an
RRF partner, or a tuned interpolation, it never adds more than +0.005 MAP -- one query. Treat it
as a replacement for an edit-distance scan, not as a general text-search ranker.

# Installation and dependencies

```bash
pip install nmd
```

Requires python 3.10 or newer.

**`nmd` itself has no dependencies, and is meant to stay that way.** `import nmd` gives you
the two things that are pure python, and pulls in nothing third-party:

```python
from nmd import ngram_movers_distance  # the metric
from nmd import WordList               # the dictionary index
```

Everything else is a deliberate opt-in: the extra modules are *not* exported from the `nmd`
namespace, so installing the package never obliges you to install their dependencies. Import
them by their full path and install what they need yourself:

| import | needs | what it is for |
|---|---|---|
| `nmd.nmd_index_v7.ApproxWordListV7` | `numpy` | same index as `WordList`, ~14-16x faster lookups on ~10x less memory (measured 2026-09-18, table below) |
| `nmd.nmd_bow.bow_ngram_movers_distance` | `scipy` | compare two sequences of tokens |
| `nmd.nmd_segments.segment_movers_distance` | `scipy`, `numpy` | as above, but tolerant of split / merged words |
| `nmd.nmd_word_set.WordSet` | `pyroaring`, `regex` | a mutable, set-like container (`add` / `discard` / `in`) with unicode normalization |

This is why `pyproject.toml` declares no `dependencies` and no extras. If you want the fast
index, `pip install numpy` alongside `nmd`.

# Usage

## `ngram_movers_distance()`

* string distance metric, use this to compare two strings

```python
from nmd import ngram_movers_distance

# n-gram mover's distance
print(ngram_movers_distance(f'hello', f'yellow'))

# n=1 compares character multisets by position, with no adjacency information
# on typo correction it beats every larger n, see docs/bow-plan.md part 7
print(ngram_movers_distance(f'hello', f'yellow', n=1))

# similarity (inverted distance)
print(ngram_movers_distance(f'hello', f'yellow', invert=True))

# distance, normalized to the range 0 to 1 (inclusive of 0 and 1)
print(ngram_movers_distance(f'hello', f'yellow', normalize=True))

# similarity, normalized to the range 0 to 1 (inclusive of 0 and 1)
print(ngram_movers_distance(f'hello', f'yellow', invert=True, normalize=True))
```

## `WordList`

* use this for dictionary lookups of words

```python
from nmd import WordList

# get words from a text file
with open(f'dictionary.txt', encoding=f'utf8') as f:
    words = set(f.read().split())

# index words
# combined 2- and 4-grams seem to work best as index keys; note that for *scoring* alone,
# n=(1,2) beats (2,4) by 11 points of hit@1 on typo correction (docs/bow-plan.md part 7),
# but unigrams have almost no selectivity as a filter, so they are not useful for the index
word_list = WordList((2, 4), filter_n=0)
for word in words:
    word_list.add_word(word)

# lookup a word -- returns [(word, (index score, recomputed nmd)), ...], best first
# over the 41.5k words of experiments/words_en.txt:
print(word_list.lookup(f'fotografer'))   # -> [('photographer', (9.90, 13.87)), ...]
print(word_list.lookup(f'beaurocracy'))  # -> [('bureaucracy', (11.73, 17.45)), ...]
```

## `ApproxWordListV7`

* WARNING: requires `numpy`, so it's not available by default in the `nmd` namespace
* same idea as `WordList`, but the lookup is vectorised instead of looping in python
* the index score is the *exact* nmd similarity, not an approximation of it: there is no
  pruning pass and no prefilter, so every posting of every query n-gram is scored and the
  top k is guaranteed to equal an exhaustive scan, with ties broken alphabetically

measured against `WordList` (`ApproxWordListV6`, `filter_n=3`) with `n=(2, 4)`, on
2026-09-18 by [experiments/v6_vs_v7_bench.py](https://github.com/averykhoo/ngram-movers-distance/blob/master/experiments/v6_vs_v7_bench.py), which regenerates this
table. index size is a walk of the index object graph, not process memory; lookup is the
minimum over 3 repeats of 20 corrupted queries, `top_k=10`:

| vocabulary | build | index size | lookup |
|------------|-------|------------|----------|
| 41.6k, V6  | 0.8s  | 159.7 MB   | 10.1 ms  |
| 41.6k, V7  | 0.5s  | 17.1 MB    | 0.7 ms   |
| 250k, V6   | 13.2s | 1087.6 MB  | 214.3 ms |
| 250k, V7   | 4.9s  | 105.2 MB   | 13.5 ms  |

so ~14x the lookup speed at 41.6k and ~16x at 250k, on ~10x less memory. the memory figures
are deterministic; the timings were taken on a shared laptop and the V6 column in particular
moves run to run, so treat the speed ratio as "more than 10x", not as three digits. V6 loops
in python over every word touched by any shared n-gram, and that set grows with the
vocabulary, which is why its lookup column grows faster than V7's

```python
from nmd.nmd_index_v7 import ApproxWordListV7

word_list = ApproxWordListV7((2, 4))  # combined 2- and 4-grams seem to work best
word_list.add_words(words)  # or add_word() one at a time

# optionally weight rare n-grams more heavily: idf(gram) ** idf_exponent
# 0.0 (the default) is unweighted and takes the original code path bit-for-bit.
# helps on product names, HURTS on typo correction -- see docs/bow-plan.md parts 6-7
weighted = ApproxWordListV7((2, 4), idf_exponent=2.0)

# lookup returns [(word, score), ...], most similar first
print(word_list.lookup(f'fotografer'))  # -> [('photographer', 0.437), ...]
print(word_list.lookup(f'fotografer', top_k=3))

# two more scoring knobs, both defaulting to the plain nmd behaviour:
#   position_weight  how much of the positional displacement to charge for, in [0, 1].
#                    1.0 (default) is nmd exactly; 0.0 discards position and leaves dice
#                    over n-gram multisets, which is BETTER on product names and worse on
#                    typos (docs/bow-plan.md part 9)
#   denominator      'dice' (default) normalizes by total_query + total_word;
#                    'geo' by 2 * sqrt(total_query * total_word), which softens a length
#                    mismatch instead of charging the full difference
print(word_list.lookup(f'sony camera dsc123', position_weight=0.0, denominator='geo'))
```

### which parameters to use

`docs/bow-plan.md` part 9 searched a 432-point grid over six retrieval benchmarks. The tasks
split into two clusters that disagree on **every** knob, so there is no single best setting:

| your data looks like | `n` | `idf_exponent` | `dim` | `normalize` | `position_weight` | `denominator` |
|---|---|---|---|---|---|---|
| short strings, typos | `(1, 2)` | 0.0-0.5 | 2 | `True` | 1.0 | either |
| product names, records | `(2, 4)` | 3.0 | 1 | `True` | 1.0 | `'geo'` |
| long text (100+ chars) | `(2, 4)` | 3.0 | 1 | `True` | 1.0 | `'geo'` |
| unknown / mixed | `(2, 4)` | 1.0 | 2 | `True` | 1.0 | `'geo'` |

Every row wants `normalize=True` and `position_weight=1.0`; the clusters differ only on `n`,
`idf_exponent` and `dim`.

⚠ `denominator='geo'` is worth **+0.099 MAP** on long documents (helping 90 of 90 paired
comparisons) and +0.016 on product names, while being roughly neutral on typo correction. It
softens the penalty for a length mismatch instead of charging the full difference, so it helps
most where candidate lengths vary and costs little where they do not.

⚠ `normalize` and `idf_exponent` substitute for each other -- both counteract length bias, so
turning both up over-corrects. On product names `normalize=True` is worth **+0.145** MAP at
`idf_exponent=0` and **-0.079** at `idf_exponent=3`.

⚠ `n=(1, 2)` scores best on every typo benchmark but is a poor *index key*: unigrams have no
selectivity, and on 138-character documents `n=(1,)` scores MAP 0.008. Use it for short strings
only.

* differences from `WordList` (`ApproxWordListV6`):
    * `lookup()` returns a plain float score per word instead of a tuple of
      (index score, recomputed nmd) -- the index score already is the exact nmd similarity,
      so V6's second value only ever repeated the first (to within float noise)
    * words with identical scores come back in alphabetical order rather than in
      posting-list insertion order, so results are reproducible run to run
    * there is no `filter_n` prefilter: it existed to keep the python candidate loop short,
      and once that loop is vectorised it costs more than it saves
    * a query too short to survive `WordList`'s `filter_n` prefilter returns nothing at
      all from it, and is still scored here -- `WordList((2, 4)).lookup("h")` is `[]`
      where this returns matches. (It no longer *raises*: the `ZeroDivisionError` that
      short queries used to hit was fixed in V6 on 2026-09-05, see below)
    * `lookup()` takes an `invert` flag at all: `WordList.lookup()` has no such parameter
      and always reports a similarity. (The frozen `ApproxWordListV5` did have one, and
      with `invert=False` returned `normalize - score`, i.e. a negative number)
    * ⚠ **`normalize` defaults to `True` here**, where `WordList` and
      `ngram_movers_distance()` both default to `False`. An un-normalized score is a raw
      similarity sum, so it grows with candidate length and biases ranking toward long
      entries; turning it on gained MAP on all six benchmarks in `docs/bow-plan.md` part 9,
      from +0.050 on Malay typo correction to +0.339 on long documents

## `bow_ngram_movers_distance()`

* WARNING: requires `scipy.optimize`, so it's not available by default in the `nmd` namespace
* use this to compare sequences of tokens (not necessarily unique)
* note that this does not merge or split words, so if you're matching `["pineapple"]` and `["pine", "apple"]` the
  similarity will be low. consider just using nmd in this case.

```python
from nmd.nmd_bow import bow_ngram_movers_distance

text_1 = f'Clementi Sports Hub'
text_2 = f'sport hubs clemmeti'
print(bow_ngram_movers_distance(bag_of_words_1=text_1.casefold().split(),
                                bag_of_words_2=text_2.casefold().split(),
                                invert=True,  # invert: return similarity instead of distance
                                normalize=True,  # return a score between 0 and 1
                                ))
```

## `segment_movers_distance()`

* WARNING: requires `scipy.optimize` and `numpy`, so it's not available by default in the `nmd` namespace
* like `bow_ngram_movers_distance` but tolerant of split / merged words (`["pineapple"]` matches `["pine", "apple"]`
  perfectly) and optionally preferring in-order matches. reference implementation, not optimized.
* see [docs/bow-plan.md](https://github.com/averykhoo/ngram-movers-distance/blob/master/docs/bow-plan.md) for the design and an evaluation on product names

```python
from nmd.nmd_segments import align_segments, explain_alignment, segment_movers_distance

a = 'sony black earbud style headphones mdrex55bk'.split()
b = 'ex series earbuds black mdr ex55/blk'.split()
print(segment_movers_distance(a, b, lam=0.0, min_sim=0.2, invert=True, normalize=True))

# introspect the matching: which segments were paired, with what similarity and positional shift
print(explain_alignment(a, b, align_segments(a, b, lam=0.0, min_sim=0.2)))
```

# Testing

The project includes a test suite using pytest. To run the tests:

```bash
pytest
```

For more details about the tests, see the [tests/README.md](https://github.com/averykhoo/ngram-movers-distance/blob/master/tests/README.md) file.

# known bugs in the older index classes

`ApproxWordListV3` and `ApproxWordListV5` are **frozen**: they are kept unchanged for
comparison against the versions that replaced them, and their bugs are documented rather than
fixed. `ApproxWordListV6` (the shipped `WordList`) and `ApproxWordListV7` are not frozen, and
have none of these.

still present, in the frozen classes only:

* `ApproxWordListV3.vocabulary` is `return sorted(self.vocabulary)` -- infinite recursion,
  `RecursionError` on any access
* `ApproxWordListV5.lookup(invert=False)` returns `normalize - match_score`, i.e. bool
  arithmetic, so distances come out negative and sorted worst-first. it also returns
  `top_k * 2` results instead of `top_k`
* `ApproxWordListV5.lookup()` raises `ZeroDivisionError` for a query of length `n - 2`, as V6
  used to (below)
* `num_grams()` disagrees with `get_n_grams()` in two places: it over-counts by 2 at `n=1`
  (adding START/END flags that `get_n_grams` omits for 1-grams), and it returns a negative
  count once the word is shorter than `n - 3`. it is still called by V3 and V5;
  `num_n_grams()` is the corrected version, and is what V6 and V7 use

fixed 2026-09-05 in `ApproxWordListV6`, i.e. in `WordList` (see `tests/test_index_v6.py`):

* `lookup()` raised `ZeroDivisionError` for any query of length `n - 2` (e.g. a 2-character
  query when 4-grams are indexed), because that produces exactly one n-gram and the location
  denominator `len(n_grams) - 1` is zero. `add_word()` had always handled this case; only the
  lookup path had not
* normalization used the `num_grams()` above, so at `n=1` every denominator was 2 too large
  (a word matched against itself scored 0.714 rather than 1.0)

neither fix changes any score on the documented `n=(2, 4)` default, where `num_grams()` and
`num_n_grams()` agree for every non-empty word.

