melon-strings 🍈

Readable and fast string matching for Python.

melon-strings is two libraries in one package:

1. melon.pure — the explainable half. Dependency-free, heavily commented reference implementations of the entire Charras–Lecroq "Exact String Matching Algorithms" catalog (35 algorithms), plus a classic Aho–Corasick automaton. Written to be read — every module explains the idea and the complexity in plain English.
2. melon.fast — the optimized half. A hand-written C++ trie engine (built with pybind11) powering a keyword extractor/replacer that matches or beats flashtext, with an automatic pure-Python fallback when the extension isn't compiled.

Copyright 2026 alvations. Licensed under Apache-2.0.

Install

pip install melon-strings          # builds the C++ backend if a compiler exists

From a checkout:

pip install -e .

If no C++ compiler is available the install still succeeds and the library transparently uses the pure-Python engine (melon.fast.is_native_available() tells you which backend is active).

Keyword extraction & replacement (the flashtext-style API)

from melon import KeywordProcessor          # auto-selects the C++ backend

kp = KeywordProcessor()
kp.add_keyword("New York", "NYC")           # keyword -> clean name
kp.add_keyword("machine learning")

kp.extract_keywords("machine learning jobs in New York")
# ['machine learning', 'NYC']

kp.replace_keywords("machine learning jobs in New York")
# 'machine learning jobs in NYC'

kp.extract_keywords("the cat sat", span_info=True)
# [('cat', 4, 7)]         # exact character spans

What it does that flashtext does — and more

# One-ups
kp.replace_keywords("cat cat", return_count=True)     # ('cat cat', 2)
KeywordProcessor(word_boundary=False)                 # match substrings anywhere
KeywordProcessor(unicode=True)                        # Unicode-aware boundaries

Pick a backend explicitly if you like:

from melon.pure.keyword import KeywordProcessor as PureKP   # always pure Python
from melon.fast import KeywordProcessor as FastKP           # C++ (falls back to pure)

The exact-matching algorithm zoo (melon.pure.exact)

Every algorithm exposes the same interface, so they're drop-in interchangeable:

from melon.pure.exact import boyer_moore, ALGORITHMS

boyer_moore.search("abracadabra", "abra")     # [0, 7]  -> all start indices
list(boyer_moore.finditer("abracadabra", "abra"))  # lazy iterator

# Iterate over the whole catalog:
for name, module in ALGORITHMS.items():
    assert module.search("banana", "ana") == [1, 3]

All 35 algorithms from the Charras–Lecroq catalog are implemented and validated against a brute-force oracle on thousands of random cases. See docs/algorithms.md for the full annotated list.

from melon.pure.multi import AhoCorasick     # multi-pattern, all occurrences
ac = AhoCorasick(["he", "she", "his", "hers"])
[(m.start, m.end, m.keyword) for m in ac.finditer("ushers")]
# [(1, 4, 'she'), (2, 4, 'he'), (2, 6, 'hers')]

Command line

melon extract --keywords keywords.txt document.txt      # or: python -m melon ...
melon extract --keywords keywords.txt --spans doc.txt   # with char offsets
melon replace --keywords map.txt --count doc.txt        # key=clean lines
melon search  --algorithm boyer_moore --pattern cat doc.txt
melon algorithms                                        # list every algorithm

Development

pip install -e ".[test]"
python scripts/validate.py           # brute-force oracle over every algorithm
pytest -q                            # full test suite
pytest --doctest-modules src/melon   # the docstring examples are runnable
python benchmarks/benchmark.py       # pure vs C++ vs flashtext vs regex

License

Apache License 2.0 — see LICENSE and NOTICE. The melon.pure algorithms are educational reimplementations based on Charras & Lecroq's descriptions; the keyword API is inspired by flashtext / flashtext2.