stride-align
Copyright 2025-2026 Adam DePrince

This product includes software developed by The Apache Software Foundation
(http://www.apache.org/).

----------------------------------------------------------------------

Phonetic encoder ports
======================

The following phonetic encoder implementations are derivative works of
Apache Commons Codec (https://commons.apache.org/proper/commons-codec/),
licensed under the Apache License, Version 2.0. The algorithmic
structure of the ports follows the corresponding Apache Commons Codec
classes; the C++ port is original code.

  * include/stride_align/soundex.hpp
    Reference: org.apache.commons.codec.language.Soundex

  * include/stride_align/metaphone.hpp
    Reference: org.apache.commons.codec.language.Metaphone

  * include/stride_align/double_metaphone.hpp
    Reference: org.apache.commons.codec.language.DoubleMetaphone

  * include/stride_align/nysiis.hpp
    Reference: org.apache.commons.codec.language.Nysiis

  * include/stride_align/match_rating.hpp
    Reference: org.apache.commons.codec.language.MatchRatingApproachEncoder

  * include/stride_align/caverphone.hpp
    Reference: org.apache.commons.codec.language.Caverphone2

  * include/stride_align/cologne_phonetic.hpp
    Reference: org.apache.commons.codec.language.ColognePhonetic

  * include/stride_align/daitch_mokotoff.hpp
    Reference: org.apache.commons.codec.language.DaitchMokotoffSoundex
    The rule table is derived directly from the Apache Commons Codec
    resource file ``dmrules.txt`` (see
    ``docs/upstream/apache-commons-codec-dmrules.txt``).

  * include/stride_align/beider_morse.hpp
    src/cpp/beider_morse_impl.cpp
    Reference: org.apache.commons.codec.language.bm.*
    Stride-align ships the GENERIC name-type rules only. The vendored
    rule files live in ``src/stride_align/bmpm_data/`` (loaded at
    runtime via ``importlib.resources``); each file preserves its
    original ASF Apache 2.0 header. The first-codepoint-bucket rule
    lookup, predicate classifier, arena allocator, and parser in
    ``beider_morse_impl.cpp`` are original C++.

Algorithmic structure and named test vectors of each encoder were
cross-checked against the canonical Apache Commons Codec test cases
during development. The third-party Python libraries listed in
``[project.optional-dependencies].phonetic-compat`` — jellyfish
(MIT), the ``metaphone`` PyPI package (BSD), and pyphonetics (MIT) —
are provided for downstream users who want their own cross-checks;
stride-align's own tests (``tests/test_phonetic.py``,
``tests/test_beider_morse.py``) import only ``pytest`` and
``stride_align`` and use hand-pinned expected values.

----------------------------------------------------------------------

Algorithmic inspiration
=======================

The multi-word bit-parallel Indel / LCSseq kernel in
``include/stride_align/indel.hpp`` (the ``indel_distance_k2_u8`` and
related K-specialised paths, plus the fused per-block recurrence in
``indel_distance_multi_word_u8``) is informed by the architecture of
rapidfuzz-cpp (https://github.com/rapidfuzz/rapidfuzz-cpp,
licensed MIT, Max Bachmann and contributors). Specifically:

  * The fused single-step Hyyrö per-block update
    ``U = S & PEQ[c]; sum = addc64(S, U, carry);
    S = sum | (S - U)`` — one fused expression per K block
    rather than four separate K-sized passes — was adopted from
    the rapidfuzz-cpp Indel / LCSseq design.
  * The observation that the per-block ``S - U`` term needs no
    borrow chain across blocks (the Hyyrö invariant ``U <= S``
    bitwise) was likewise inherited from their implementation.
  * Compile-time template specialisation of K = 1 through 8 paths
    with a runtime ``switch`` dispatch on block count, so the
    compiler sees N as a constant and pins state in registers
    across the entire text loop.
  * Stack-resident ``S[N]`` state for K <= 8 (no heap traffic per
    call).
  * The Ukkonen-style diagonal-band early-exit shape for the
    ``score_cutoff`` path.

No source code, header comments, identifier names, file layouts,
struct field orderings, or close-paraphrased structural elements
were copied from rapidfuzz-cpp. The architectural ideas above were
extracted by a delegated investigation that reported back algorithm
structure in its own prose, while the code-authoring agent did not
read the rapidfuzz-cpp source. See
``docs/phase-D-external-sources.md`` §3a and §4c for the full
provenance trail.

A consolidated source audit covering every phonetic encoder lives at
``docs/phonetic-encoder-external-sources.md``. The BMPM-specific
audit (Apache Commons Codec rule data, vendored resources, explicit
GPL-port exclusions) lives at ``docs/bmpm-external-sources.md``.

----------------------------------------------------------------------

Test oracles
============

The third-party phonetic libraries listed under
``[project.optional-dependencies].phonetic-compat`` (jellyfish,
metaphone, pyphonetics) are runtime extras only — none of their
source is included in or distributed with stride-align, and none is
imported by any file under ``tests/`` or ``src/``. Their licences
(MIT and BSD) are Apache-2.0 compatible.
