Integration of a Edit-Distance Service

[plc-dev]

Possible candidates:

• Text-Edit-Distance
• Graph-Edit-Distance

Two different kinds of edit-distances:

• text edit distance (e.g., levenshtein, etc.)
• graph edit distance (e.g., GED, etc.)

Input-Formats:

• Text - can just be a string (as a JSON-parameter)
• Graph - adjacency matrix (or list) or general graph formats for labeled property graphs (GraphML, DOT, networkx, etc...)
  => Ask LLM for sensible serialized graph-format

The wrapper should expose an

• OpenAPI-Spec,
  • by virtue of that, a REST-API
  • and preferably a mirroring CLI,
• be distributed as a Docker-Image
• and - if required - state its minimal hardware requirements.

The code should be added as a subdirectory within the /services/-directory and should adhere to the defined contracts of the repository. Namely, the Makefile targets and the inclusion of a Github CI workflow.

As the above candidates are tested already, units regarding the functionality of the embedded library may be omitted.

[synapp009]

Edit-Distance Libraries - Unified API Reference

Details

# Edit-Distance Libraries — Comparison

Overview of existing libraries for embedding text edit distance and graph edit distance (GED) algorithms into a containerized microservice with a unified API. Compiled via web research; dates reflect the latest confirmed release/commit as of mid-2026.

Summary — Text Edit Distance Libraries

Library	Language	Public repository	Latest release / maintained	Algorithms covered
RapidFuzz (+ Levenshtein, JaroWinkler)	C++ core / Python, Rust, JS bindings	https://github.com/rapidfuzz/RapidFuzz	v3.14.5 (Apr 2026), very active	Levenshtein, Damerau-Levenshtein, Hamming, Jaro, Jaro-Winkler, Indel, LCSseq, OSA, prefix/postfix, plus fuzzy ratios
textdistance	Pure Python (optional C accelerators)	https://github.com/life4/textdistance	actively maintained, 30+ algorithms	Levenshtein, Damerau-Levenshtein, Hamming, Jaro(-Winkler), Needleman-Wunsch, Gotoh, Smith-Waterman, LCS, Jaccard, Sørensen-Dice, Tversky, Cosine, MRA, NCD, Editex, etc.
jellyfish	Python (Rust core since v1.0)	https://github.com/jamesturk/jellyfish	actively maintained	Levenshtein, Damerau-Levenshtein, Jaro, Jaro-Winkler, Hamming, Match Rating Comparison + phonetic codes (Soundex, Metaphone, NYSIIS)
edlib	C/C++ core, Python bindings	https://github.com/Martinsos/edlib	v1.3.9 (2024, still maintained)	Levenshtein (global/prefix/infix modes), banded/bit-vector alignment, CIGAR output
strsim-rs	Rust (+ Python/Node ports)	https://github.com/rapidfuzz/strsim-rs	actively maintained	Levenshtein, Damerau-Levenshtein, Jaro, Jaro-Winkler, Hamming, Sørensen-Dice
Apache Commons Text	Java	https://github.com/apache/commons-text	actively maintained (Apache)	Levenshtein, Damerau-Levenshtein (CosineDistance, JaccardSimilarity, JaroWinklerSimilarity, LongestCommonSubsequenceDistance, HammingDistance)
java-string-similarity	Java	https://github.com/tdebatty/java-string-similarity	last major activity ~2020s, low churn but usable	Levenshtein, Damerau-Levenshtein, Jaro-Winkler, NGram, QGram, Cosine, Jaccard, Sorensen-Dice, OSA, LCS
diff-match-patch	Java/Python/JS/C++/Dart/Go ports	https://github.com/google/diff-match-patch	Google-maintained reference impl, ports vary in freshness	Myers diff / edit-script based text diffing (not pure numeric edit distance, but produces edit operations)
python-Levenshtein (alias)	C, Python wrapper	https://github.com/rapidfuzz/Levenshtein	actively maintained (now a thin wrapper around RapidFuzz's C++ core)	Levenshtein distance/ratio, median string, Hamming, Jaro/Jaro-Winkler

Summary — Graph Edit Distance Libraries

Library	Language	Public repository	Latest release / maintained	Notes
NetworkX (similarity module)	Pure Python	https://github.com/networkx/networkx	v3.6.x (2026, actively maintained)	Exact and approximate GED (A*-based), optimal edit paths, generator-based anytime approximation
GEDLIB	C++ (header-only/shared)	https://github.com/dbblumenthal/gedlib	actively maintained (LGPL, academic project)	Reference research library with the widest catalog of exact and heuristic GED algorithms (bipartite, IPFP, refinement, blackbox/MIP, ML-based)
gedlibpy	Python bindings to GEDLIB	https://github.com/Ryurin/gedlibpy	maintained fork, less active than core GEDLIB	Exposes GEDLIB's method catalog to Python
GMatch4py	Python + Cython	https://github.com/jacquesfize/GMatch4py	maintained but slow-moving (last significant activity ~2020s)	GED (Munkres-based approximate), plus other graph-similarity measures (graph kernels, MCS, embeddings) — works directly on networkx.Graph
ged4py (predecessor)	Python	https://github.com/jacquesfize/ged4py	archived — author redirects to GMatch4py	Superseded; kept only for historical reference

Below are the per-library details with algorithm names, signatures, and types.

---

Text Edit Distance — Details

RapidFuzz (Python) — fastest general-purpose engine

Repo: https://github.com/rapidfuzz/RapidFuzz · Latest: v3.14.5 (Apr 2026) · Core in C++, bindings for Python/Rust/JS.

Each metric is exposed both as a free function (module rapidfuzz.distance.<Metric>) and as a class with .distance()/.similarity()/.normalized_distance()/.normalized_similarity().

Algorithm	Signature	Returns
Levenshtein	rapidfuzz.distance.Levenshtein.distance(s1: Sequence, s2: Sequence, *, weights=(1,1,1), processor=None, score_cutoff=None) -> int	int
Damerau-Levenshtein	rapidfuzz.distance.DamerauLevenshtein.distance(s1, s2, *, processor=None, score_cutoff=None) -> int	int
Optimal String Alignment (OSA)	rapidfuzz.distance.OSA.distance(s1, s2, *, processor=None, score_cutoff=None) -> int	int
Hamming	rapidfuzz.distance.Hamming.distance(s1, s2, *, pad=True, processor=None, score_cutoff=None) -> int	int
Jaro	rapidfuzz.distance.Jaro.similarity(s1, s2, *, processor=None, score_cutoff=None) -> float	float
Jaro-Winkler	rapidfuzz.distance.JaroWinkler.similarity(s1, s2, *, prefix_weight=0.1, processor=None, score_cutoff=None) -> float	float
Indel (LCS-based)	rapidfuzz.distance.Indel.distance(s1, s2, *, processor=None, score_cutoff=None) -> int	int
LCS sequence	rapidfuzz.distance.LCSseq.distance(s1, s2, *, processor=None, score_cutoff=None) -> int	int
Prefix/Postfix	rapidfuzz.distance.Prefix.similarity(s1, s2, ...) -> int, rapidfuzz.distance.Postfix.similarity(...) -> int	int
Fuzzy ratio (composite)	rapidfuzz.fuzz.ratio(s1, s2, *, processor=None, score_cutoff=None) -> float	float (0–100)

textdistance (Python) — broadest catalog, pure Python

Repo: https://github.com/life4/textdistance · pure-Python with optional external-lib acceleration.

All algorithms are exposed as both a module-level callable and a class instance; classes take qval (n-gram size) and other algorithm-specific params in __init__.

Algorithm	Signature	Returns
Levenshtein	textdistance.levenshtein(s1: Sequence, s2: Sequence) -> int (class: Levenshtein(qval=1, external=True))	int
Damerau-Levenshtein	textdistance.damerau_levenshtein(s1, s2) -> int	int
Hamming	textdistance.hamming(s1, s2) -> int	int
Jaro / Jaro-Winkler	textdistance.jaro(s1, s2) -> float, textdistance.jaro_winkler(s1, s2, winklerize=True) -> float	float
Needleman-Wunsch	textdistance.needleman_wunsch(s1, s2) -> float (class allows custom gap_cost, sim_func)	float
Gotoh	textdistance.gotoh(s1, s2) -> float	float
Smith-Waterman	textdistance.smith_waterman(s1, s2) -> float	float
Longest Common Subsequence	textdistance.lcsseq(s1, s2) -> str (via .similarity() / .distance() for scalar)	str/int
Jaccard / Sørensen-Dice / Tversky	textdistance.jaccard(s1, s2) -> float, textdistance.sorensen(s1, s2) -> float, textdistance.tversky(s1, s2) -> float	float
Cosine	textdistance.cosine(s1, s2) -> float	float
Normalized Compression Distance	textdistance.ncd(s1, s2) -> float (class: NCD(qval=1, compressor='zlib'))	float
Common interface (any algorithm class)	.distance(*sequences) -> number, .similarity(*sequences) -> number, .normalized_distance(*sequences) -> float [0,1], .normalized_similarity(*sequences) -> float [0,1], .maximum(*sequences) -> number	varies

jellyfish (Python, Rust core)

Repo: https://github.com/jamesturk/jellyfish · actively maintained.

Algorithm	Signature	Returns
Levenshtein distance	jellyfish.levenshtein_distance(s1: str, s2: str) -> int	int
Damerau-Levenshtein	jellyfish.damerau_levenshtein_distance(s1: str, s2: str) -> int	int
Jaro similarity	jellyfish.jaro_similarity(s1: str, s2: str) -> float	float
Jaro-Winkler similarity	jellyfish.jaro_winkler_similarity(s1: str, s2: str, long_tolerance: bool=False) -> float	float
Hamming distance	jellyfish.hamming_distance(s1: str, s2: str) -> int	int
Match Rating Comparison	`jellyfish.match_rating_comparison(s1: str, s2: str) -> bool	None`
Phonetic codes	jellyfish.soundex(s: str) -> str, jellyfish.metaphone(s: str) -> str, jellyfish.nysiis(s: str) -> str	str

edlib (C/C++ core, Python bindings) — best for long/similar sequences

Repo: https://github.com/Martinsos/edlib · v1.3.9 (2024).

Algorithm	Signature	Returns
Global/prefix/infix edit distance	edlib.align(query: Sequence, target: Sequence, mode: str="NW", task: str="distance", k: int=-1, additionalEqualities=None) -> dict (mode ∈ {"NW","SHW","HW"}, task ∈ {"distance","locations","path"})	dict with keys editDistance: int, alphabetLength: int, locations: list[tuple], `cigar: str
Nice alignment rendering	edlib.getNiceAlignment(result: dict, query: str, target: str, gapSymbol: str="-") -> dict	dict with query_aligned, matched_aligned, target_aligned strings
C API core	EdlibAlignResult edlibAlign(const char* query, int queryLength, const char* target, int targetLength, const EdlibAlignConfig config)	EdlibAlignResult struct (editDistance, endLocations, alignment buffer)

strsim-rs (Rust, with Python/Node ports)

Repo: https://github.com/rapidfuzz/strsim-rs · actively maintained.

Algorithm	Signature	Returns
Levenshtein	fn levenshtein(a: &str, b: &str) -> usize	usize
Damerau-Levenshtein	fn damerau_levenshtein(a: &str, b: &str) -> usize	usize
Jaro	fn jaro(a: &str, b: &str) -> f64	f64
Jaro-Winkler	fn jaro_winkler(a: &str, b: &str) -> f64	f64
Hamming	fn hamming(a: &str, b: &str) -> Result<usize, StrSimError>	Result<usize, _>
Sørensen-Dice	fn sorensen_dice(a: &str, b: &str) -> f64	f64

Apache Commons Text (Java)

Repo: https://github.com/apache/commons-text · actively maintained under the Apache Software Foundation. Package org.apache.commons.text.similarity.

Algorithm	Signature	Returns
Levenshtein distance	new LevenshteinDistance(Integer threshold).apply(CharSequence left, CharSequence right) -> Integer	Integer
Damerau-Levenshtein	LevenshteinDistance variants with custom cost, or HammingDistance for equal-length strings	Integer
Jaro-Winkler	new JaroWinklerSimilarity().apply(CharSequence left, CharSequence right) -> Double	Double
Hamming distance	new HammingDistance().apply(CharSequence left, CharSequence right) -> Integer	Integer
Jaccard similarity	new JaccardSimilarity().apply(CharSequence left, CharSequence right) -> Double	Double
Cosine similarity/distance	new CosineDistance().apply(CharSequence left, CharSequence right) -> Double	Double
Longest Common Subsequence	new LongestCommonSubsequence().apply(CharSequence left, CharSequence right) -> Integer, LongestCommonSubsequenceDistance	Integer

diff-match-patch (Google, multi-language reference implementation)

Repo: https://github.com/google/diff-match-patch · Google-maintained core; language ports (Java, Python, JS, C++, Dart, Go, C#) vary in recency.

Algorithm	Signature (Python port)	Returns
Myers diff (edit script)	dmp.diff_main(text1: str, text2: str, checklines: bool=True, deadline=None) -> list[(int, str)]	list of (op, text) tuples, op ∈ {-1,0,1}
Levenshtein-style edit distance (from diff)	dmp.diff_levenshtein(diffs: list[(int,str)]) -> int	int
Patch generation	dmp.patch_make(text1: str, text2: str) -> list[Patch]	list[Patch]

---

Graph Edit Distance — Details

NetworkX (networkx.algorithms.similarity) — reference implementation

Repo: https://github.com/networkx/networkx · v3.6.x (2026). Pure Python; A*-based exact/approximate GED.

Algorithm	Signature	Returns
Exact/heuristic GED (best-effort, anytime)	`graph_edit_distance(G1: Graph, G2: Graph, node_match=None, edge_match=None, node_subst_cost=None, node_del_cost=None, node_ins_cost=None, edge_subst_cost=None, edge_del_cost=None, edge_ins_cost=None, roots=None, upper_bound=None, timeout=None) -> float	None`
Anytime approximation generator	optimize_graph_edit_distance(G1, G2, node_match=None, edge_match=None, node_subst_cost=None, node_del_cost=None, node_ins_cost=None, edge_subst_cost=None, edge_del_cost=None, edge_ins_cost=None, upper_bound=None) -> Iterator[float]	generator of improving float upper bounds
Optimal edit paths + cost	optimal_edit_paths(G1, G2, node_match=None, edge_match=None, node_subst_cost=None, node_del_cost=None, node_ins_cost=None, edge_subst_cost=None, edge_del_cost=None, edge_ins_cost=None, upper_bound=None) -> tuple[list[tuple[dict, dict]], float]	(list_of_edit_paths, cost)
Anytime edit-path generator	optimize_edit_paths(G1, G2, ..., upper_bound=None, strictly_decreasing=True, timeout=None) -> Iterator[tuple[dict, dict, float]]	generator of (node_edit_path, edge_edit_path, cost)
Similarity ratio (normalized)	derived manually as `1 - ged / max(	V1

GEDLIB (C++) — widest catalog of GED algorithms

Repo: https://github.com/dbblumenthal/gedlib · header-only C++, LGPL, actively maintained by academic authors.

Workflow: build a ged::GEDEnv<UserNodeID, UserNodeLabel, UserEdgeLabel>, load graphs, set edit costs, select a method, run it.

Step	Signature (C++ API, ged::GEDEnv)	Returns
Load graph (GXL or API)	ged::GEDGraph::GraphID GEDEnv::load_gxl_graph(const std::string& dir, const std::string& file, ...) -> GEDGraph::GraphID	graph ID (std::size_t)
Set edit costs	void GEDEnv::set_edit_costs(Options::EditCosts edit_costs, std::vector<double> edit_cost_constants={})	void
Select method	void GEDEnv::set_method(Options::GEDMethod method, const std::string& options="") (methods incl. BIPARTITE, IPFP, REFINE, ANCHOR_AWARE_GED, BRANCH, NODE, RING, SUBGRAPH, WALKS, exact F2 / BLP_NO_EDGE_LABELS via MIP)	void
Init method	void GEDEnv::init_method()	void
Run method on a graph pair	void GEDEnv::run_method(GEDGraph::GraphID g_id, GEDGraph::GraphID h_id)	void (populates internal result)
Retrieve results	double GEDEnv::get_upper_bound(GraphID g_id, GraphID h_id) const, double GEDEnv::get_lower_bound(...) const, NodeMap GEDEnv::get_node_map(...) const, double GEDEnv::get_runtime(...) const	double / NodeMap

gedlibpy — Python bindings for GEDLIB

Repo: https://github.com/Ryurin/gedlibpy · thinner, function-based wrapper around the same C++ engine.

Step	Signature	Returns
Load graphs	gedlibpy.load_GXL_graphs(graph_dir: str, collection_file: str) -> None	None
List graph IDs	gedlibpy.get_all_graph_ids() -> list[int]	list[int]
Set cost model	gedlibpy.set_edit_cost(cost_name: str) -> None (e.g. "CHEM_1")	None
Init environment	gedlibpy.init() -> None	None
Select & init method	gedlibpy.set_method(method_name: str, options: str="") -> None, gedlibpy.init_method() -> None	None
Run & retrieve	gedlibpy.run_method(g_id: int, h_id: int) -> None; then gedlibpy.get_upper_bound(g_id, h_id) -> float, gedlibpy.get_lower_bound(g_id, h_id) -> float, gedlibpy.get_node_map(g_id, h_id) -> dict, gedlibpy.get_runtime(g_id, h_id) -> float	float / dict

GMatch4py (Python + Cython) — works natively on networkx.Graph

Repo: https://github.com/jacquesfize/GMatch4py · maintained but slow-moving; last significant activity in the early 2020s, still installable/functional.

Each algorithm is a class taking edit-cost parameters at construction and exposing a compare() method over a list of graphs.

Algorithm	Signature	Returns
GED (Munkres/Hausdorff-approx.)	gm.GraphEditDistance(node_del: float, node_ins: float, edge_del: float, edge_ins: float).compare(graph_list: list[nx.Graph], selected: list[int]=None) -> np.ndarray	numpy.ndarray (pairwise distance matrix)
Hausdorff edit distance (bounded)	gm.HED(node_del: float, node_ins: float, edge_del: float, edge_ins: float).compare(graph_list, selected=None) -> np.ndarray	numpy.ndarray
Greedy edit distance	gm.GreedyEditDistance(node_del, node_ins, edge_del, edge_ins).compare(graph_list, selected=None) -> np.ndarray	numpy.ndarray
Bipartite/Riesen-Bunke GED	gm.BP2(node_del, node_ins, edge_del, edge_ins).compare(graph_list, selected=None) -> np.ndarray	numpy.ndarray

ged4py (archived predecessor of GMatch4py)

Repo: https://github.com/jacquesfize/ged4py · archived; the author explicitly redirects users to GMatch4py. Included only for completeness/history — do not build on this for new work.

Algorithm	Signature	Returns
GED (Munkres)	ged4py.algorithm.graph_edit_dist.compare(g1: nx.Graph, g2: nx.Graph) -> float	float

---

Recommendations for a unified microservice

• Text edit distance engine: pair RapidFuzz (fast, C++-backed, broad metric coverage, active) with textdistance as a fallback for the long tail of algorithms (Needleman-Wunsch, Gotoh, Smith-Waterman, NCD, Tversky, etc.) that RapidFuzz doesn't implement. Add edlib specifically when the workload involves very long/near-identical sequences (bioinformatics-style alignment) since its banded/bit-vector approach dramatically outperforms quadratic DP there.
• Graph edit distance engine: NetworkX's similarity module as the default/pure-Python fallback (zero native-build overhead, good for small-to-medium graphs), with GEDLIB (via gedlibpy) as the high-performance/production backend — it has by far the richest catalog of exact and heuristic GED algorithms and is purpose-built for this problem, at the cost of a C++ build step in the container. GMatch4py is worth wrapping only if you specifically want Hausdorff/greedy/bipartite variants operating directly on networkx.Graph objects without touching GXL files or the GEDLIB build chain.
• Skip ged4py — it's explicitly unmaintained and superseded.

Design implication for the unified API

These libraries disagree on conventions just as much as the graph-generation libraries did:

• Input representation: raw strings/sequences (text libs) vs. networkx.Graph (NetworkX, GMatch4py) vs. GXL files or a native GEDEnv graph ID (GEDLIB).
• Cost model: most text libraries are cost-free (unit cost per edit op) or take a weights tuple; graph-ED libraries require explicit node/edge insertion/deletion/substitution cost functions or constants.
• Return shape: scalar int/float (most text libs) vs. (cost, edit_path) tuples (NetworkX, GEDLIB) vs. a full distance matrix (GMatch4py, batch-oriented).
• Exactness/anytime behavior: GED is NP-hard, so some backends (NetworkX, GEDLIB) expose generators for anytime approximation with a timeout/upper_bound, while others return a single best-effort value.

A normalization layer should map a canonical algorithm name (e.g. levenshtein, damerau_levenshtein, jaro_winkler, ged_exact, ged_bipartite, ged_hed) plus a canonical parameter set (weights or edit-cost constants, timeout) to each backend's specific call, and standardize the output (e.g. {"distance": float, "normalized": float, "edit_path": [...] | null, "exact": bool}) regardless of the underlying library.

Optimal Library Selection for a Edit-Distance Microservice

Details

This document uses the data from edit-distance-libraries-comparison.md to solve a
weighted maximum-coverage / set-cover problem twice — once for text edit
distance and once for graph edit distance (GED) — since the two are served by
disjoint library ecosystems and should be treated as two independent optimizations
feeding into the same unified API. The goal in both cases: select the smallest set of
libraries that covers the largest number of distinct algorithm families, while
minimizing redundant overlap between selected libraries, and favoring libraries that
are actively maintained and expose an API style that is easy to unify behind a single
microservice interface.

1. Problem formalization

Let:

• A = {a_1, ..., a_n} — the universe of distinct algorithm families (canonical
  categories, not individual function signatures; e.g. "Jaro-Winkler" is one category
  even though 5 libraries implement it with different signatures).
• L — candidate libraries for the given domain (text or graph). Libraries that are
  thin wrappers or forks reusing the same underlying engine as an already-listed
  library are excluded a priori, since they add a redundant runtime with zero net
  new coverage (see §3.4 and §4.4 for the specific exclusions).
• cover(l) ⊆ A — the set of algorithm families implemented by library l.
• Q(l) = freshness(l) × api_compat(l) — a quality weight in [0, 1] per library.
  We choose S ⊆ L minimizing |S|, such that ⋃_{l∈S} cover(l) is as close to A
  as possible, while maximizing:

score(S) = Σ_{l∈S} Q(l) × |new(l, S)|

where new(l, S) is the set of algorithm families l adds that were not already
covered by libraries already chosen in S — this is what enforces "minimal overlap":
each added library must justify its inclusion mainly through new coverage, not
duplicate coverage.

This is the classic weighted maximum coverage problem (NP-hard in general); we solve
it with the standard greedy approximation (pick, at each step, the library maximizing
Q(l) × |new(l, S)|), which is known to be within a (1 − 1/e) factor of optimal.

Assumed target runtime for the microservice: Python-first, containerized, one
process per domain. This directly shapes api_compat below (native Python object
in/out, prebuilt wheels, and functional/class-based common interfaces score highly;
JVM-only or build-heavy C++-only libraries score low).

---

PART A — Text Edit Distance

A.2 Algorithm family universe

#	Algorithm family
1	Levenshtein distance
2	Damerau-Levenshtein distance (transposition-aware)
3	Hamming distance
4	Jaro / Jaro-Winkler similarity
5	Optimal String Alignment (OSA)
6	Indel (LCS-based edit distance)
7	Longest Common Subsequence (extraction/similarity)
8	Needleman-Wunsch (global alignment, custom substitution/gap cost)
9	Gotoh (affine-gap alignment)
10	Smith-Waterman (local alignment)
11	Token/set similarity bundle (Jaccard, Sørensen-Dice, Tversky, Cosine)
12	Normalized Compression Distance (NCD)
13	Phonetic encoding + Match Rating Comparison (Soundex, Metaphone, NYSIIS, MRC)
14	Edit-script / diff (Myers) + patch application
15	Long-sequence banded/bit-vector alignment with alignment modes + CIGAR output

A.3 Coverage matrix

✓ = implemented, – = not implemented (or only reachable via a generic/manual construction).

#	Family	RapidFuzz	textdistance	jellyfish	edlib	strsim-rs	Commons Text	diff-match-patch
1	Levenshtein	✓	✓	✓	✓	✓	✓	✓ (derived from diff)
2	Damerau-Levenshtein	✓	✓	✓	–	✓	–	–
3	Hamming	✓	✓	✓	–	✓	✓	–
4	Jaro / Jaro-Winkler	✓	✓	✓	–	✓	✓	–
5	OSA	✓	–	–	–	–	–	–
6	Indel (LCS distance)	✓	✓	–	–	–	–	–
7	LCS (extraction)	–	✓	–	–	–	✓	–
8	Needleman-Wunsch	–	✓	–	✓	–	–	–
9	Gotoh (affine gap)	–	✓	–	–	–	–	–
10	Smith-Waterman	–	✓	–	–	–	–	–
11	Token/set similarity	–	✓	–	–	✓ (Dice only)	✓	–
12	NCD	–	✓	–	–	–	–	–
13	Phonetic + MRC	–	–	✓	–	–	–	–
14	Diff / patch (Myers)	–	–	–	–	–	–	✓
15	Long-sequence banded alignment + CIGAR	–	–	–	✓	–	–	–
Raw coverage count		6	11	5	3	5	5	2

A.4 Quality weights

A.4.1 Freshness (0–1)

Library	Latest release	Freshness
RapidFuzz	v3.14.5, Apr 2026, very active	1.00
textdistance	actively maintained, pure Python	0.90
jellyfish	actively maintained (Rust core)	0.90
Apache Commons Text	actively maintained (ASF)	0.90
strsim-rs	actively maintained	0.85
edlib	v1.3.9 (2024), lower commit velocity	0.55
diff-match-patch	Google core stable but low churn; ports vary in freshness	0.55

A.4.2 API compatibility for a Python-first microservice (0–1)

Library	Paradigm	Packaging	api_compat
RapidFuzz	Functional + class API, scalar int/float return	Prebuilt wheels, trivial pip install	1.00
textdistance	Common .distance()/.similarity() interface across all algorithms, pure Python	Trivial pip install, no native build	0.90
jellyfish	Functional API, scalar return	Prebuilt wheels (Rust core)	0.85
strsim-rs	Native Rust; Python access only via community bindings	Requires a separate binding crate/wheel, not first-class Python	0.35
edlib	dict-based result object, distinct alignment-mode semantics (NW/SHW/HW)	C/C++ build dependency	0.55
diff-match-patch	Returns an edit-script (list of ops), not a scalar distance — needs an adapter layer	Pure Python port available, easy to install	0.50
Apache Commons Text	Java, object-oriented (new X().apply(...))	Requires a JVM sidecar inside a Python-first container	0.25

A.4.3 Combined weight Q(l)

Library	Freshness	api_compat	Q(l)
RapidFuzz	1.00	1.00	1.000
textdistance	0.90	0.90	0.810
jellyfish	0.90	0.85	0.765
strsim-rs	0.85	0.35	0.298
diff-match-patch	0.55	0.50	0.275
edlib	0.55	0.55	0.303
Apache Commons Text	0.90	0.25	0.225

A.5 Greedy weighted maximum-coverage run

Step 1 — pick the library maximizing Q(l) × |cover(l)|:

Library	|cover(l)|	Q(l)	Score
textdistance	11	0.810	8.91 ← selected
RapidFuzz	6	1.000	6.00
jellyfish	5	0.765	3.83
strsim-rs	5	0.298	1.49
Apache Commons Text	5	0.225	1.13
diff-match-patch	2	0.275	0.55
edlib	3	0.303	0.91

→ Selected: textdistance (covers families 1,2,3,4,6,7,8,9,10,11,12 → 11/15, 73%)

Step 2 — recompute new(l, S) against the remaining 4 families {5, 13, 14, 15}:

Library	New families covered	|new|	Q(l)	Score
RapidFuzz	5 (OSA)	1	1.000	1.00 ← selected
jellyfish	13 (phonetic + MRC)	1	0.765	0.765
edlib	15 (long-sequence alignment)	1	0.303	0.303
diff-match-patch	14 (diff/patch)	1	0.275	0.275
strsim-rs	— (all already covered)	0	0.298	0.00
Apache Commons Text	— (all already covered)	0	0.225	0.00

→ Selected: RapidFuzz (adds OSA → 12/15, 80%)

Step 3 — remaining families {13, 14, 15}:

Library	New families covered	|new|	Q(l)	Score
jellyfish	13	1	0.765	0.765 ← selected
edlib	15	1	0.303	0.303
diff-match-patch	14	1	0.275	0.275

→ Selected: jellyfish (adds phonetic encoding + MRC → 13/15, 87%)

Step 4 — remaining families {14, 15}:

Library	New families covered	|new|	Q(l)	Score
edlib	15	1	0.303	0.303 ← selected
diff-match-patch	14	1	0.275	0.275

→ Selected: edlib (adds long-sequence banded alignment + CIGAR → 14/15, 93%)

Step 5 — remaining family {14}:

Library	New families covered	|new|	Q(l)	Score
diff-match-patch	14	1	0.275	0.275 ← only remaining contributor

→ Selected: diff-match-patch (adds Myers diff/patch → 15/15, 100%)

No further library adds coverage: strsim-rs and Apache Commons Text are now fully
subsumed by the chosen set, so the algorithm terminates.

A.6 Recommendation

Tier 1 — Minimal core set (recommended default)

Rank	Library	New families added	Cumulative coverage	Q(l)
1	textdistance	11	11/15 (73%)	0.810
2	RapidFuzz	1 (OSA)	12/15 (80%)	1.000
3	jellyfish	1 (phonetic + MRC)	13/15 (87%)	0.765

This 3-library set reaches 87% family coverage with zero mutual overlap (each was
selected specifically for the families it uniquely adds) and consists exclusively of
libraries with a native Python functional API, prebuilt wheels, and no JVM or heavy
native toolchain. RapidFuzz is the natural default engine for the hot path
(Levenshtein/Damerau/Jaro family — highest freshness and API fit), with
textdistance as the fallback for the long tail (Needleman-Wunsch, Gotoh,
Smith-Waterman, NCD, token/set measures), and jellyfish added purely for phonetic
matching, a distinct capability none of the others provide.

Tier 2 — Extended coverage

Rank	Library	New families added	Cumulative coverage	Q(l)
4	edlib	1 (long-sequence banded alignment + CIGAR)	14/15 (93%)	0.303
5	diff-match-patch	1 (Myers diff/patch)	15/15 (100%)	0.275

Add edlib only if the service must handle very long, highly similar sequences
(genome-scale or large-document alignment) where its banded/bit-vector approach gives
a real performance advantage over quadratic DP. Add diff-match-patch only if the
product needs an actual edit-script/patch output (e.g. "show me the diff") rather than
a numeric distance — its diff_levenshtein is derived from a line-level diff, not a
true DP matrix, so it should not be used as the canonical source for family 1; keep
RapidFuzz/textdistance as the authoritative Levenshtein implementation.

Explicitly excluded

Library	Reason for exclusion
python-Levenshtein	Now a thin wrapper around RapidFuzz's own C++ core (same maintainers/org); adds zero net-new coverage over RapidFuzz.
java-string-similarity	Coverage is a near-total subset of Apache Commons Text + jellyfish-equivalent metrics; a second Java library would only add a redundant JVM runtime with no unique family.
strsim-rs	After textdistance + RapidFuzz + jellyfish are selected, contributes zero new families; its Rust-native paradigm also requires a non-first-class Python binding.
Apache Commons Text	Fully subsumed after step 3 (all its families already covered by textdistance/RapidFuzz/jellyfish); would additionally require a JVM sidecar purely for redundant coverage.

A.7 Residual gaps

Even at 100% family coverage, some depth-within-family differences remain (same
family, different fidelity — not a missing family):

• RapidFuzz's OSA/Indel implementations are optimized C++ variants; textdistance's
  pure-Python LCS-based distance is more transparent/customizable but slower.
• diff-match-patch's derived Levenshtein count is diff-based and can differ slightly
  from a canonical DP-based Levenshtein on certain inputs — treat family 14 (diff/patch)
  as its sole authoritative contribution, not family 1.
• edlib's Needleman-Wunsch-equivalent ("NW" mode) is tuned for near-identical,
  long sequences; for short, dissimilar strings, textdistance's more general
  needleman_wunsch (custom substitution/gap functions) is more flexible.
  These are acceptable trade-offs given the goal of minimizing the number of embedded
  libraries.

A.8 Final answer (Text ED)

Recommended library set: RapidFuzz + textdistance + jellyfish (87% family
coverage, minimal overlap, highest aggregate quality weight per family covered).

If 100% coverage is a hard requirement: add edlib (long-sequence alignment)
and diff-match-patch (diff/patch output) as two further, narrowly-scoped
components (100% family coverage).

---

PART B — Graph Edit Distance

B.2 Algorithm family universe

#	Algorithm family
1	Exact/optimal GED (branch-and-bound / A*)
2	Anytime approximate GED (generator-based, improving upper bound)
3	Edit-path / node-mapping retrieval
4	Bipartite (Riesen-Bunke / LSAP) heuristic
5	IPFP (Integer Projected Fixed Point) heuristic
6	Refinement heuristic (local search over a bipartite result)
7	Lower-bound heuristic family (anchor-aware, branch, node, ring, subgraph, walks)
8	Exact GED via MIP / blackbox optimizer (ILP formulation)
9	Hausdorff Edit Distance (HED, bounded approximation)
10	Greedy edit distance

B.3 Coverage matrix

ged4py is excluded a priori: its own author has archived it and explicitly
redirects users to GMatch4py, so it carries zero net-new coverage and only adds a
second, unmaintained code path.

#	Family	NetworkX	GEDLIB (via gedlibpy)	GMatch4py
1	Exact/optimal GED	✓	✓	–
2	Anytime approximate GED	✓	✓	–
3	Edit-path / node-mapping retrieval	✓	✓	–
4	Bipartite heuristic	–	✓	✓
5	IPFP heuristic	–	✓	–
6	Refinement heuristic	–	✓	–
7	Lower-bound heuristic family	–	✓	–
8	Exact via MIP/blackbox	–	✓	–
9	Hausdorff Edit Distance	–	–	✓
10	Greedy edit distance	–	–	✓
Raw coverage count		3	7	3

B.4 Quality weights

B.4.1 Freshness (0–1)

Library	Latest release	Freshness
NetworkX	v3.6.x, 2026, continuously released	1.00
GEDLIB (core)	actively maintained academic project, but infrequent major releases	0.65
GMatch4py	last significant activity ~early 2020s, low commit velocity	0.45

B.4.2 API compatibility for a Python-first microservice (0–1)

Library	Paradigm	Packaging	api_compat
NetworkX	Pure Python, native networkx.Graph in/out, scalar or (path, cost) return	Trivial pip install, no native build	1.00
GMatch4py	Cython, native networkx.Graph in/out, batch distance-matrix return	Cython build required but pip-installable, no external file format	0.80
GEDLIB (via gedlibpy)	C++ core, environment/handle-based stateful API (load → set_method → init → run → get_*), GXL file format expected	Header-only C++ build + a community Python binding fork; heavier container image	0.40

B.4.3 Combined weight Q(l)

Library	Freshness	api_compat	Q(l)
NetworkX	1.00	1.00	1.000
GMatch4py	0.45	0.80	0.360
GEDLIB (via gedlibpy)	0.65	0.40	0.260

B.5 Greedy weighted maximum-coverage run

Step 1 — pick the library maximizing Q(l) × |cover(l)|:

Library	|cover(l)|	Q(l)	Score
NetworkX	3	1.000	3.00 ← selected
GEDLIB	7	0.260	1.82
GMatch4py	3	0.360	1.08

→ Selected: NetworkX (covers families 1, 2, 3 → 3/10, 30%)

Step 2 — recompute new(l, S) against the remaining 7 families {4,5,6,7,8,9,10}:

Library	New families covered	|new|	Q(l)	Score
GEDLIB	4, 5, 6, 7, 8	5	0.260	1.30 ← selected
GMatch4py	4, 9, 10	3	0.360	1.08

→ Selected: GEDLIB (adds bipartite, IPFP, refinement, lower-bound-heuristic
family, and MIP/blackbox-exact → 8/10, 80%)

Step 3 — remaining families {9, 10} — only GMatch4py covers them (family 4 is
now already covered by GEDLIB):

Library	New families covered	|new|	Q(l)	Score
GMatch4py	9, 10	2	0.360	0.72 ← only remaining contributor

→ Selected: GMatch4py (adds Hausdorff Edit Distance and greedy edit distance →
10/10, 100%)

No further library adds coverage; the algorithm terminates at full coverage with
exactly three libraries and no wasted overlap.

B.6 Recommendation

Tier 1 — Minimal core set (recommended default)

Rank	Library	New families added	Cumulative coverage	Q(l)
1	NetworkX	3	3/10 (30%)	1.000
2	GEDLIB (via gedlibpy)	5	8/10 (80%)	0.260

NetworkX should be the default/fallback backend — zero native-build overhead, good
for small-to-medium graphs, and it is the only candidate with a fully idiomatic
Python object API. GEDLIB should be the performance/production backend, isolated
in its own container image (its GXL-oriented, stateful C++ API and heavier
dependency chain make it a poor fit to bundle directly alongside NetworkX), fronted
by the same normalization layer so callers don't see the difference.

Tier 2 — Complete-coverage extension

Rank	Library	New families added	Cumulative coverage	Q(l)
3	GMatch4py	2 (Hausdorff Edit Distance, greedy edit distance)	10/10 (100%)	0.360

Add GMatch4py only if Hausdorff Edit Distance or plain greedy-assignment GED are
actually required (e.g. as a cheap upper-bound pre-filter before invoking the more
expensive GEDLIB exact/heuristic methods on a shortlist of candidate pairs) — a common
and genuinely useful pattern, since it operates natively on networkx.Graph with no
extra file-format conversion.

Explicitly excluded

Library	Reason for exclusion
ged4py	Archived by its own author, who redirects users to GMatch4py; zero net-new coverage, unmaintained.

B.7 Residual gaps

At 100% family coverage, one depth-within-family nuance remains: GMatch4py's
bipartite GED (BP2) and GEDLIB's BIPARTITE method both implement the same family
(Riesen-Bunke/LSAP-based assignment) but with different edit-cost parameterizations
and no shared node-mapping output format — GMatch4py returns only a distance matrix,
while GEDLIB exposes the full node map via get_node_map(). If a caller needs the
explicit mapping and wants GMatch4py's simpler native-networkx interface, GEDLIB's
BIPARTITE method (not GMatch4py's BP2) should be the canonical implementation
used behind the unified API for that request.

B.8 Final answer (Graph ED)

Recommended library set: NetworkX + GEDLIB (via gedlibpy) (80% family coverage,
minimal overlap, highest aggregate quality weight per family covered).

If 100% coverage is a hard requirement: add GMatch4py as a third, isolated
component for Hausdorff/greedy pre-filtering (100% family coverage), at the cost of a
third code path with a lower freshness score.

---

Summary across both domains

Domain	Minimal recommended set	Coverage	Full-coverage set	Coverage
Text edit distance	RapidFuzz + textdistance + jellyfish	13/15 (87%)	+ edlib + diff-match-patch	15/15 (100%)
Graph edit distance	NetworkX + GEDLIB (gedlibpy)	8/10 (80%)	+ GMatch4py	10/10 (100%)

In both domains the same pattern emerges: one broad, pure-language, easy-to-embed
library forms the core (textdistance / NetworkX), one fast, narrowly-focused,
highest-Q(l) library is added for its top-priority families (RapidFuzz / GEDLIB),
and any remaining niche families are covered only by isolating a lower-freshness or
heavier-dependency library behind the same normalization layer rather than baking it
into the primary container image.

Unified REST API Specification for the Edit-Distance Service

Details

This document defines a unified REST API for embedding the selected edit-distance
libraries behind a single interface, using discriminated unions to keep the number
of distinct endpoints minimal while preserving full parameter fidelity per algorithm
and per backend implementation.

Because text edit distance and graph edit distance (GED) are served by
disjoint library ecosystems with fundamentally different input/output shapes (scalar
distances vs. NP-hard graph comparisons with edit paths), they are specified as two
independent API surfaces (Part A / Part B), each provided in two variants matching
the two library selections from edit-distance-library-selection.md:

• Spec A — Tier 1 core set (minimal, highest quality-weight-per-family)
• Spec B — Tier 2 complete set (Tier 1 + the remaining niche families)
  Both variants of a given part share the same endpoints and envelope structure — only
  the discriminated-union catalog of algorithm/backend combinations differs.

1. Design principles

• One compute endpoint per domain, not one endpoint per algorithm. All algorithm
  families are exposed through a single POST call whose body is a discriminated
  union, keyed first by algorithm (the canonical family) and, where more than one
  backend implements that family, keyed second by backend. This avoids a
  combinatorial explosion of endpoints (algorithm × backend × library) while still
  exposing each backend's exact, strongly-typed parameter set.
• Backend is a first-class, explicit field, not hidden — different backends can
  produce numerically different results even for the "same" named algorithm (e.g.
  RapidFuzz's Levenshtein.distance(weights=(1,1,1)) vs. textdistance's
  Levenshtein(qval=1) vs. edlib's banded NW mode with a k-bounded cutoff).
  Hiding this would silently change results between calls. A backend can be omitted,
  in which case the service auto-selects a sensible default (documented per
  algorithm).
• Discovery endpoint (GET /v1/.../algorithms) exposes the full catalog and JSON
  Schemas of the discriminated union at runtime, so clients (and OpenAPI/JSON Schema
  tooling, code generators) never need to hardcode the union.
• Result shape varies by algorithm, so the response is itself a discriminated
  union — a scalar distance (Levenshtein), a bounded/anytime distance with an edit
  path (GED), a batch distance matrix, a phonetic code, or a diff/patch object are
  all different resultTypes inside one shared envelope, rather than forcing a
  lossy lowest-common-denominator "just return a number" contract.
• Uniform error/validation semantics. Because every algorithm variant is a member
  of one JSON Schema union, standard 400 validation errors
  (RFC 9457 application/problem+json) apply identically regardless of backend.
• Batching is a body shape, not a separate endpoint. Both domains accept either a
  single pair/graph-pair or an array of pairs in the same request, keeping the total
  endpoint count minimal.

---

PART A — Text Edit Distance API

A.2 Shared endpoint set (identical for Spec A and Spec B)

#	Method & path	Purpose
1	GET /v1/text/algorithms	Discovery: list all algorithm/backend combinations, each with its JSON Schema, canonical family, and metadata (result type, cost/parameter model, determinism).
2	POST /v1/text/compare	Compute a distance/similarity/transform for one pair or a batch of pairs. Body = discriminated union (algorithm [+ backend] + params + inputs). Synchronous; text-domain algorithms are fast enough that no async/resource-storage pattern is needed.

Text edit distance requires no GET/DELETE resource-lifecycle endpoints: unlike
generated graphs, comparison results are cheap to recompute and are not persisted
server-side — the client receives the full result inline in the response to POST /v1/text/compare.

Optional, non-essential convenience route (purely additive sugar, can be omitted):
GET /v1/text/algorithms/{algorithm} (schema for one family only).

A.3 Shared envelope & discriminated-union pattern

A.3.1 Request envelope (POST /v1/text/compare)

{
  "algorithm": "damerau_levenshtein",
  "backend": "rapidfuzz",
  "params": {
    "processor": null,
    "score_cutoff": null
  },
  "inputs": [
    { "id": "pair-1", "a": "kitten", "b": "sitting" },
    { "id": "pair-2", "a": "flaw",   "b": "lawn" }
  ]
}

inputs always accepts an array (length ≥ 1), so a single comparison and a batch use
the identical request shape.

A.3.2 JSON Schema discriminated union (OpenAPI 3.1 style)

CompareTextRequest:
  oneOf:
    - $ref: '#/components/schemas/LevenshteinRequest'
    - $ref: '#/components/schemas/DamerauLevenshteinRequest'
    - $ref: '#/components/schemas/HammingRequest'
    - $ref: '#/components/schemas/JaroWinklerRequest'
    - $ref: '#/components/schemas/OsaRequest'
    - $ref: '#/components/schemas/IndelRequest'
    # ... one member per canonical algorithm family
  discriminator:
    propertyName: algorithm
    mapping:
      levenshtein: '#/components/schemas/LevenshteinRequest'
      damerau_levenshtein: '#/components/schemas/DamerauLevenshteinRequest'
      hamming: '#/components/schemas/HammingRequest'
      jaro_winkler: '#/components/schemas/JaroWinklerRequest'
      osa: '#/components/schemas/OsaRequest'
      indel: '#/components/schemas/IndelRequest'
      # ...
 
# Second-level union, only for families with >1 backend:
DamerauLevenshteinRequest:
  type: object
  required: [algorithm, backend, inputs]
  properties:
    algorithm: { const: damerau_levenshtein }
    backend: { enum: [rapidfuzz, textdistance, jellyfish] }
    params:
      oneOf:
        - $ref: '#/components/schemas/DamerauLevenshteinRapidFuzzParams'
        - $ref: '#/components/schemas/DamerauLevenshteinTextdistanceParams'
        - $ref: '#/components/schemas/DamerauLevenshteinJellyfishParams'
      discriminator:
        propertyName: backend    # resolved via sibling `backend` field

A.3.3 Response envelope

The response is itself a discriminated union on resultType, since not every
algorithm produces a scalar distance:

{
  "algorithm": "damerau_levenshtein",
  "backend": "rapidfuzz",
  "resultType": "scalar_distance",
  "results": [
    { "id": "pair-1", "value": 3, "normalized": 0.4286 },
    { "id": "pair-2", "value": 2, "normalized": 0.5 }
  ],
  "meta": { "computeTimeMs": 2 }
}

Other resultType variants used by families that don't return a plain scalar:

// resultType = "sequence" (e.g. LCS extraction)
{ "id": "pair-1", "value": "kt", "length": 2 }
 
// resultType = "phonetic_code" (family 13)
{ "id": "word-1", "codes": { "soundex": "J412", "metaphone": "JLFX", "nysiis": "JALYF" } }
 
// resultType = "edit_script" (family 14, diff-match-patch)
{ "id": "pair-1", "diffs": [[0, "The "], [-1, "quick "], [1, "slow "], [0, "fox"]], "levenshtein": 11 }
 
// resultType = "alignment" (family 15/8, edlib / Needleman-Wunsch)
{ "id": "pair-1", "editDistance": 3, "locations": [[null, 8]], "cigar": "3=1I4=" }

Errors use application/problem+json (RFC 9457) with an additional
invalidParams: [{ name, reason }] array, so a single schema serves every backend.

A.4 Spec A — Tier 1 (RapidFuzz + textdistance + jellyfish)

A.4.1 Algorithm catalog → backend/function mapping

All rows use POST /v1/text/compare with the given algorithm (+ backend)
discriminator.

algorithm tag	Canonical family	backend options	Underlying function
levenshtein	Levenshtein distance	rapidfuzz (default)	Levenshtein.distance(s1, s2, weights, processor, score_cutoff)
		textdistance	levenshtein(s1, s2)
damerau_levenshtein	Damerau-Levenshtein	rapidfuzz (default)	DamerauLevenshtein.distance(s1, s2, processor, score_cutoff)
		textdistance	damerau_levenshtein(s1, s2)
		jellyfish	damerau_levenshtein_distance(s1, s2)
hamming	Hamming distance	rapidfuzz (default)	Hamming.distance(s1, s2, pad, processor, score_cutoff)
		textdistance	hamming(s1, s2)
		jellyfish	hamming_distance(s1, s2)
jaro_winkler	Jaro / Jaro-Winkler	rapidfuzz (default)	JaroWinkler.similarity(s1, s2, prefix_weight, ...) / Jaro.similarity(...) (variant sub-field)
		textdistance	jaro_winkler(s1, s2, winklerize) / jaro(s1, s2) (variant sub-field)
		jellyfish	jaro_winkler_similarity(s1, s2, long_tolerance) / jaro_similarity(s1, s2) (variant sub-field)
osa	Optimal String Alignment	rapidfuzz (only)	OSA.distance(s1, s2, processor, score_cutoff)
indel	Indel (LCS-based distance)	rapidfuzz (default)	Indel.distance(s1, s2, processor, score_cutoff)
		textdistance	.distance() on the LCS-distance class
lcs	Longest Common Subsequence (extraction)	textdistance (only)	lcsseq(s1, s2) — returns resultType: sequence
needleman_wunsch	Global alignment, custom cost	textdistance (only)	needleman_wunsch(s1, s2, gap_cost, sim_func) — returns resultType: alignment
gotoh	Affine-gap alignment	textdistance (only)	gotoh(s1, s2)
smith_waterman	Local alignment	textdistance (only)	smith_waterman(s1, s2)
token_set_similarity	Jaccard / Sørensen-Dice / Tversky / Cosine bundle	textdistance (only)	jaccard(s1, s2) / sorensen(s1, s2) / tversky(s1, s2) / cosine(s1, s2) (selected via metric sub-field)
ncd	Normalized Compression Distance	textdistance (only)	NCD(qval, compressor).distance(s1, s2)
phonetic_encoding	Phonetic code + Match Rating Comparison	jellyfish (only)	soundex(s) / metaphone(s) / nysiis(s) / match_rating_comparison(s1, s2) (selected via scheme sub-field) — returns resultType: phonetic_code

13 algorithm tags cover the 13 families of Tier 1 (some families are folded together
as a variant/metric/scheme sub-discriminator inside one tag, e.g.
jaro_winkler, token_set_similarity, phonetic_encoding) — matching the "minimal
number of distinct endpoints" goal while still routing every underlying function 1:1
via (algorithm, backend, variant).

A.4.2 Example: multi-backend discriminated union for damerau_levenshtein

// backend = rapidfuzz
{
  "algorithm": "damerau_levenshtein",
  "backend": "rapidfuzz",
  "params": { "processor": null, "score_cutoff": null },
  "inputs": [{ "id": "p1", "a": "jellyfish", "b": "jellyfihs" }]
}
 
// backend = textdistance (different parameter surface — supports qval n-gram tokenization)
{
  "algorithm": "damerau_levenshtein",
  "backend": "textdistance",
  "params": { "qval": 1, "external": true },
  "inputs": [{ "id": "p1", "a": "jellyfish", "b": "jellyfihs" }]
}
 
// backend = jellyfish (simplest surface, no tunables)
{
  "algorithm": "damerau_levenshtein",
  "backend": "jellyfish",
  "params": {},
  "inputs": [{ "id": "p1", "a": "jellyfish", "b": "jellyfihs" }]
}

All three validate against the same top-level algorithm: damerau_levenshtein union
member but resolve to distinct params schemas via the nested backend
discriminator — this preserves full fidelity to each library's native signature
instead of forcing a lossy lowest-common-denominator parameter set.

A.5 Spec B — Tier 2 (Tier 1 + edlib + diff-match-patch)

Spec B reuses both endpoints and all 13 tags from Spec A unchanged, and adds:

• 2 new algorithm tags exclusive to edlib/diff-match-patch (families not covered
  by Tier 1),
• edlib as an additional backend option on the existing levenshtein tag, where
  it offers a performance-oriented alternative implementation.

A.5.1 New tags

algorithm tag	Canonical family	backend	Underlying function
long_sequence_alignment	Banded/bit-vector alignment for long sequences, with mode + CIGAR	edlib (only)	edlib.align(query, target, mode, task, k, additionalEqualities) — selected mode sub-field (NW|SHW|HW); returns resultType: alignment
diff_patch	Myers diff / edit-script + patch	diff_match_patch (only)	diff_main(text1, text2, checklines, deadline) + diff_levenshtein(diffs) — returns resultType: edit_script

A.5.2 Backend extension on an existing tag

algorithm tag	Added backend	Underlying function	Rationale
levenshtein	edlib	edlib.align(query, target, mode="NW", task="distance")	edlib's banded/bit-vector implementation gives a real performance advantage for long, highly similar sequences (e.g. genome-scale or large-document comparison) even though it computes the same canonical family; exposed as an extra backend rather than a new tag to avoid duplicating the family.

A.5.3 Discovery endpoint delta

GET /v1/text/algorithms for Spec B returns the same 13 entries as Spec A plus the 2
new tags above, and the 1 extended backend enum — the discriminated union schema is a
strict superset, so any client written against Spec A remains valid against Spec B
(backward-compatible extension).

A.5.4 Deployment note

diff_match_patch's diff_levenshtein is derived from a line/character-level diff,
not a canonical DP matrix, and can diverge slightly from the levenshtein tag's
value on certain inputs; the API surface keeps these as two separate resultTypes
(scalar_distance vs. edit_script) precisely so clients never conflate them. edlib
requires a native C/C++ build; it should be bundled in the primary image only if the
service targets long-sequence workloads, otherwise isolated behind a feature flag or
sidecar like graph-tool in the graph-generation service.

A.6 Summary — Part A

	Spec A (Tier 1)	Spec B (Tier 2)
Endpoints	2 (GET /v1/text/algorithms, POST /v1/text/compare)	Same 2
Backends	rapidfuzz, textdistance, jellyfish	+ edlib, diff_match_patch
Algorithm tags	13	15
Family coverage	13/15 (87%)	15/15 (100%)
Deployment	Single container	Primary container (+ optional edlib native-build layer)

---

PART B — Graph Edit Distance API

B.2 Shared endpoint set (identical for Spec A and Spec B)

GED computation on large graphs or with exact/MIP-based methods can be
computationally expensive (NP-hard), so — unlike text comparison — this domain
follows the same async-resource pattern as the graph-generation service.

#	Method & path	Purpose
1	GET /v1/graphs/ged/algorithms	Discovery: list all algorithm/backend/method combinations, each with its JSON Schema, canonical family, and metadata (exactness, worst-case complexity, whether an edit path/node map is returned).
2	POST /v1/graphs/ged/compute	Compute the edit distance between one pair (or a batch of pairs) of graphs. Body = discriminated union (algorithm [+ backend [+ method]] + params + graphs). Returns 202 Accepted (async, with Location) for exact/MIP or large-graph computations, or 201 Created with the result inline for small/fast ones — both cases return a GedResult resource envelope.
3	GET /v1/graphs/ged/{resultId}	Retrieve a previously computed result's metadata and (via ?include=) its edit path / node mapping, streamed for large mappings.
4	DELETE /v1/graphs/ged/{resultId}	Release a stored result resource.

Graphs to compare can be supplied either inline (nodes/edges payload) or by
reference to an existing resource from the companion graph-generation service
(graphRef: "/v1/graphs/grf_9f1c2e..."), avoiding duplicate graph transport when the
two services are deployed together.

Optional, non-essential convenience route (purely additive sugar, can be omitted):
GET /v1/graphs/ged/algorithms/{algorithm} (schema for one family only).

B.3 Shared envelope & discriminated-union pattern

B.3.1 Request envelope (POST /v1/graphs/ged/compute)

{
  "algorithm": "ged_heuristic",
  "backend": "gedlib",
  "params": {
    "method": "BIPARTITE",
    "editCosts": { "nodeIns": 1, "nodeDel": 1, "nodeSubst": 1, "edgeIns": 1, "edgeDel": 1, "edgeSubst": 1 },
    "timeoutMs": 5000
  },
  "graphs": [
    { "id": "pair-1", "g1": { "graphRef": "/v1/graphs/grf_9f1c2e..." }, "g2": { "graphRef": "/v1/graphs/grf_a02b7f..." } }
  ],
  "output": { "includeNodeMap": true }
}

graphs always accepts an array, so a single comparison and a batch (e.g. computing
a full pairwise distance matrix over a graph collection) use the identical request
shape.

B.3.2 JSON Schema discriminated union (OpenAPI 3.1 style)

ComputeGedRequest:
  oneOf:
    - $ref: '#/components/schemas/GedAStarRequest'
    - $ref: '#/components/schemas/GedHeuristicRequest'
    - $ref: '#/components/schemas/GedHausdorffRequest'
    - $ref: '#/components/schemas/GedGreedyRequest'
  discriminator:
    propertyName: algorithm
    mapping:
      ged_astar: '#/components/schemas/GedAStarRequest'
      ged_heuristic: '#/components/schemas/GedHeuristicRequest'
      ged_hausdorff: '#/components/schemas/GedHausdorffRequest'
      ged_greedy: '#/components/schemas/GedGreedyRequest'
 
# Second-level union, for the tag with >1 backend:
GedAStarRequest:
  type: object
  required: [algorithm, backend, graphs]
  properties:
    algorithm: { const: ged_astar }
    backend: { enum: [networkx, gedlib] }
    params:
      oneOf:
        - $ref: '#/components/schemas/GedAStarNetworkXParams'
        - $ref: '#/components/schemas/GedAStarGedlibParams'
      discriminator:
        propertyName: backend

B.3.3 Response envelope (GedResult resource)

{
  "id": "ged_7c2a1e...",
  "status": "completed",
  "algorithm": "ged_heuristic",
  "backend": "gedlib",
  "params": { "...": "echoed request params" },
  "results": [
    {
      "id": "pair-1",
      "upperBound": 4.0,
      "lowerBound": 4.0,
      "exact": false,
      "nodeMap": [[0, 0], [1, 2], [2, 1]],
      "runtimeMs": 312
    }
  ],
  "_links": {
    "self": "/v1/graphs/ged/ged_7c2a1e...",
    "nodeMap": "/v1/graphs/ged/ged_7c2a1e...?include=nodeMap"
  }
}

Errors use application/problem+json (RFC 9457) with an additional
invalidParams: [{ name, reason }] array, so a single schema serves every
backend/method combination.

B.4 Spec A — Tier 1 (NetworkX + GEDLIB via gedlibpy)

B.4.1 Algorithm catalog → backend/method mapping

All rows use POST /v1/graphs/ged/compute with the given algorithm (+ backend
[+ method]) discriminator; retrieval is always via GET /v1/graphs/ged/{resultId}.

algorithm tag	Canonical family (folded)	backend	method sub-field	Underlying function
ged_astar	Exact/optimal GED · anytime approximate GED · edit-path retrieval (families 1, 2, 3)	networkx (default)	mode: exact | anytime | path	graph_edit_distance(...) / optimize_graph_edit_distance(...) / optimal_edit_paths(...) selected via mode
		gedlib	mode: exact_mip	set_method("F2" | "BLP_NO_EDGE_LABELS") → run_method → get_upper_bound / get_lower_bound / get_node_map (also folds in family 8, exact-via-MIP)
ged_heuristic	Bipartite · IPFP · refinement · lower-bound heuristic family (families 4, 5, 6, 7)	gedlib (only)	method: BIPARTITE | IPFP | REFINE | ANCHOR_AWARE_GED | BRANCH | NODE | RING | SUBGRAPH | WALKS	set_method(method, options) → init_method → run_method → get_upper_bound / get_node_map

2 algorithm tags cover the 8 families of Tier 1 (families are folded together via
mode/method sub-discriminators, matching the "minimal number of distinct
endpoints" goal) while still routing every underlying method 1:1 via (algorithm, backend, mode/method).

B.4.2 Example: multi-backend discriminated union for ged_astar

// backend = networkx
{
  "algorithm": "ged_astar",
  "backend": "networkx",
  "params": {
    "mode": "anytime",
    "nodeSubstCost": null, "nodeDelCost": null, "nodeInsCost": null,
    "edgeSubstCost": null, "edgeDelCost": null, "edgeInsCost": null,
    "upperBound": null, "timeoutMs": 5000
  },
  "graphs": [{ "id": "pair-1", "g1": { "graphRef": "..." }, "g2": { "graphRef": "..." } }]
}
 
// backend = gedlib (different parameter surface, same folded family)
{
  "algorithm": "ged_astar",
  "backend": "gedlib",
  "params": {
    "mode": "exact_mip",
    "method": "F2",
    "editCostModel": "CHEM_1",
    "timeoutMs": 30000
  },
  "graphs": [{ "id": "pair-1", "g1": { "graphRef": "..." }, "g2": { "graphRef": "..." } }]
}

Both validate against the same top-level algorithm: ged_astar union member but
resolve to distinct params schemas via the nested backend discriminator — this
preserves full fidelity to each library's native workflow (NetworkX's direct
function calls vs. GEDLIB's stateful GEDEnv handle) instead of forcing a lossy
lowest-common-denominator parameter set.

B.5 Spec B — Tier 2 (Tier 1 + GMatch4py)

Spec B reuses all 4 endpoints and both tags from Spec A unchanged, and adds:

• 2 new algorithm tags exclusive to GMatch4py (families not covered by Tier 1),
• GMatch4py as an additional backend option on the existing ged_heuristic tag,
  where it offers a native-networkx.Graph alternative for the bipartite variant
  specifically.

B.5.1 New tags (GMatch4py exclusive)

algorithm tag	Canonical family	backend	Underlying function
ged_hausdorff	Hausdorff Edit Distance (bounded approximation)	gmatch4py (only)	HED(node_del, node_ins, edge_del, edge_ins).compare(graph_list, selected) — batch-native, returns a distance matrix
ged_greedy	Greedy edit distance	gmatch4py (only)	GreedyEditDistance(node_del, node_ins, edge_del, edge_ins).compare(graph_list, selected)

Because GMatch4py's native output is a pairwise distance matrix rather than a single
pair result, these two tags' response results array is populated pairwise across
the full graphs input list in one call — well suited as a cheap pre-filter over a
graph collection before invoking the more expensive ged_astar/ged_heuristic tags
on a shortlist of candidates.

B.5.2 Backend extension on an existing tag

algorithm tag	Added backend	method value	Underlying function	Rationale
ged_heuristic	gmatch4py	BIPARTITE (only — GMatch4py does not implement IPFP/refine/ring/etc.)	GraphEditDistance(node_del, node_ins, edge_del, edge_ins).compare(graph_list, selected)	Operates natively on networkx.Graph with no GXL conversion, useful when graphs already live in the companion generation service and a quick bipartite estimate is enough; GEDLIB remains the canonical choice when an explicit node map is required (see residual-gap note below).

B.5.3 Discovery endpoint delta

GET /v1/graphs/ged/algorithms for Spec B returns the same 2 entries as Spec A plus
the 2 new tags above, and the 1 extended backend/method combination — the
discriminated union schema is a strict superset, so any client written against Spec A
remains valid against Spec B (backward-compatible extension).

B.5.4 Deployment note

Because GEDLIB has materially worse container/dependency ergonomics than NetworkX
(GXL-oriented, stateful C++ handle, heavier build), Spec B's implementation should
isolate the gedlib backend in its own service/sidecar behind the same POST /v1/graphs/ged/compute contract (routed internally based on backend == "gedlib"),
rather than bundling it into the primary NetworkX/GMatch4py image — mirroring the
graph-tool isolation pattern from the graph-generation service. gmatch4py's Cython
build is comparatively lightweight and can stay in the primary image.

GMatch4py's BIPARTITE-equivalent (GraphEditDistance/BP2) returns only a distance
matrix, not an explicit node mapping — if a caller requests output.includeNodeMap: true on a ged_heuristic request with backend: gmatch4py, the service should
either reject the combination with a 422 (application/problem+json,
invalidParams: [{ name: "backend", reason: "gmatch4py does not expose a node map for this method; use backend=gedlib" }]) or transparently re-route to backend: gedlib, method: BIPARTITE — this should be a documented, explicit service behavior, not silent.

B.6 Summary — Part B

	Spec A (Tier 1)	Spec B (Tier 2)
Endpoints	4 (GET /v1/graphs/ged/algorithms, POST /v1/graphs/ged/compute, GET /v1/graphs/ged/{resultId}, DELETE /v1/graphs/ged/{resultId})	Same 4
Backends	networkx, gedlib	+ gmatch4py
Algorithm tags	2	4
Family coverage	8/10 (80%)	10/10 (100%)
Deployment	Primary container (networkx) + isolated gedlib sidecar	Primary container (networkx + gmatch4py) + isolated gedlib sidecar

---

Overall summary

	Part A: Text ED — Spec A	Part A: Text ED — Spec B	Part B: Graph ED — Spec A	Part B: Graph ED — Spec B
Endpoints	2	2	4	4
Algorithm tags	13	15	2	4
Family coverage	87%	100%	80%	100%
Async/resource pattern	No (synchronous)	No (synchronous)	Yes (202/{resultId})	Yes (202/{resultId})
Isolation needed	No	Optional (edlib native build)	Yes (gedlib sidecar)	Yes (gedlib sidecar)

Both domains follow the same core pattern established for the graph-generation
service: a single, discovery-backed compute endpoint per domain, algorithm as the
primary discriminator, backend as an explicit secondary discriminator, and any
family too niche or dependency-heavy to justify a new endpoint folded in as an
additional backend or a mode/method/variant sub-field instead.