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 available to 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.

The separate ``tests/test_jellyfish_shim.py`` differential battery
imports Jellyfish when available because that module explicitly
targets Jellyfish API compatibility.

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

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.

Striped SIMD alignment kernels
==============================

The striped-profile layout and the lazy-F (Farrar-style) horizontal-gap
correction in stride-align's SIMD Smith-Waterman / Needleman-Wunsch kernels
(``src/cpp/backends/*.hpp``) are informed by the architecture of parasail
(https://github.com/jeffdaily/parasail), a BSD-3-Clause SIMD pairwise
alignment library by Jeff Daily. The striped inner-loop structure and the
lazy-F correction pass were studied from parasail's source for algorithmic
ideas; the kernels here are original C++ and no parasail source was copied.
The academic citation lives in the README "References" section:

  Daily, Jeff. (2016). Parasail: SIMD C library for global, semi-global, and
  local pairwise sequence alignments. BMC Bioinformatics, 17(1), 1-11.
  doi:10.1186/s12859-016-0930-z

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 and compatibility references
=========================================

The third-party phonetic libraries listed under
``[project.optional-dependencies].phonetic-compat`` are optional
cross-check oracles. ``metaphone`` and ``pyphonetics`` remain
test-time references only. Jellyfish is also the API and behavioural
reference for ``src/stride_align/jellyfish.py``; its compatibility
rule variants are adapted under the following MIT licence. TheFuzz
and RapidFuzz are the behavioural references for
``src/stride_align/thefuzz/`` and its optional differential tests;
their compatibility conventions are adapted under the MIT licences
retained below.

Jellyfish compatibility facade
==============================

The Jellyfish 1.2.1 compatibility rule variants in
``src/stride_align/jellyfish.py`` are adapted from Jellyfish:
https://codeberg.org/jpt/jellyfish

MIT License

Copyright (c) 2015 James Turk

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

TheFuzz compatibility facade
============================

The public adapter structure and legacy compatibility conventions in
``src/stride_align/thefuzz/`` are adapted from TheFuzz 0.22.1:
https://github.com/seatgeek/thefuzz

MIT License

Copyright (c) 2014 SeatGeek

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

RapidFuzz sequence compatibility
================================

The generic-sequence normalization, token-set arithmetic order, and
unrounded-score ranking conventions retained by the TheFuzz facade were
cross-checked against RapidFuzz 3.14.5's MIT-licensed Python implementation:
https://github.com/rapidfuzz/RapidFuzz

Copyright © 2020-present Max Bachmann
Copyright © 2011 Adam Cohen

Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

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

Keyboard typo / confusion matrices (data)
=========================================

The optional keyboard substitution matrices — built by
``tools/build_keyboard_matrices.py`` and loaded through the
``stride_align.matrices.keyboard`` namespace — are derived, with the
authors' permission, from the Aalto University "136 Million Keystrokes"
dataset:

    Vivek Dhakal, Anna Maria Feit, Per Ola Kristensson, Antti Oulasvirta.
    "Observations on Typing from 136 Million Keystrokes." Proceedings of
    the 2018 CHI Conference on Human Factors in Computing Systems
    (CHI '18), 2018. https://doi.org/10.1145/3173574.3174220
    Dataset: https://userinterfaces.aalto.fi/136Mkeystrokes/

stride-align bundles a small number of example keyboard substitution
matrices derived from this dataset. The dataset authors granted explicit
permission to build and publish these derived matrices under stride-align's
Apache-2.0 licence; only the derived matrices are distributed — the raw
keystroke data is not. Retain the citation above as attribution. See
docs/keyboard-matrix-external-sources.md for the provenance and the scope of
the permission.
