Metadata-Version: 2.4
Name: tandem-repeat
Version: 0.1.0
Classifier: Development Status :: 3 - Alpha
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: MacOS
Classifier: Operating System :: POSIX :: Linux
Classifier: Programming Language :: Python :: 3
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 :: Rust
Classifier: Typing :: Typed
Requires-Dist: cibuildwheel>=2.23,<3 ; python_full_version < '3.11' and extra == 'dev'
Requires-Dist: cibuildwheel>=3.0 ; python_full_version >= '3.11' and extra == 'dev'
Requires-Dist: maturin>=1.8,<2 ; extra == 'dev'
Requires-Dist: mypy>=1.15 ; extra == 'dev'
Requires-Dist: pre-commit>=4.0 ; extra == 'dev'
Requires-Dist: pytest>=8.0 ; extra == 'dev'
Requires-Dist: ruff>=0.9 ; extra == 'dev'
Requires-Dist: twine>=6.0 ; extra == 'dev'
Provides-Extra: dev
License-File: LICENSE
Summary: Rust-backed exact tandem-repeat detection for Python strings
Home-Page: https://github.com/dkajtoch/tandem-repeat
Author: Dariusz Kajtoch
License: MIT
Requires-Python: >=3.10
Description-Content-Type: text/markdown; charset=UTF-8; variant=GFM
Project-URL: Homepage, https://github.com/dkajtoch/tandem-repeat
Project-URL: Issues, https://github.com/dkajtoch/tandem-repeat/issues
Project-URL: Repository, https://github.com/dkajtoch/tandem-repeat

# tandem-repeat

Rust-backed Python package for exact tandem-repeat detection in Unicode text.

```python
from tandem_repeat import find, find_longest, find_primitive

find("abcabcabc")
# [TandemRepeat(start=0, end=9, substring='abc', repeats=3, ...), ...]

find("aaaaa")
# [TandemRepeat(start=0, end=5, substring='a', repeats=5, ...),
#  TandemRepeat(start=0, end=4, substring='aa', repeats=2, ...), ...]

find_primitive("aaaaa")
# [TandemRepeat(start=0, end=5, substring='a', repeats=5, ...)]

find_longest("xxabcabcabc")
# TandemRepeat(start=2, end=11, substring='abc', repeats=3, ...)
```

## API

```python
find(
    text: str,
    *,
    min_length: int = 1,
    min_repeats: int = 2,
    max_results: int | None = None,
) -> list[TandemRepeat]

find_primitive(
    text: str,
    *,
    min_length: int = 1,
    min_repeats: int = 2,
    max_results: int | None = None,
) -> list[TandemRepeat]

find_longest(
    text: str,
    *,
    min_length: int = 1,
    min_repeats: int = 2,
) -> TandemRepeat | None
```

`TandemRepeat` is a frozen dataclass:

```python
@dataclass(frozen=True, slots=True)
class TandemRepeat:
    start: int       # Python character offset, inclusive
    end: int         # Python character offset, exclusive
    substring: str   # repeated unit
    repeats: int     # number of consecutive copies
    period: int      # len(substring) in Python characters
    byte_start: int  # UTF-8 byte offset, inclusive
    byte_end: int    # UTF-8 byte offset, exclusive
```

The detector works on the exact input code points. It does not normalize text, so
precomposed and decomposed Unicode sequences are treated as different strings.

## Complexity

`find` returns a compact vocabulary-style representation, not every occurrence
position. This follows the distinction in Stoye and Gusfield's tandem repeat
work: the occurrence set can be quadratic, while the vocabulary of tandem repeat
types is linear-size. For example, `"aaaaa"` includes tandem types such as
`"a"` repeated five times and `"aa"` repeated twice, but it does not expand every
overlapping occurrence into separate Python objects.

`find_primitive` exposes the practical smaller-subunit view explicitly. It
normalizes each block to its smallest repeated unit, so `"aaaaa"` is represented
as `"a"` repeated five times.

The Rust scanner avoids the old all-periods-by-all-starts search for larger
inputs. It scans short periods directly and discovers longer-period candidates
from repeated fixed-width seeds, then verifies candidates exactly before
returning them. This gives near-linear scaling on sparse realistic text while
preserving exact compact blocks for emitted results. Dense fully periodic text
uses a separate linear fast path for `find_longest`.

`find_longest` returns one result and avoids result-set explosion. On sparse text
the benchmark suite now covers inputs up to 100k characters; on dense text it
covers 100k-character fully periodic inputs.

Reference:

- Jens Stoye and Dan Gusfield, "Linear time algorithms for finding and
  representing all the tandem repeats in a string", JCSS 2004.

## Development

This project uses `uv`, `maturin`, Rust, Ruff, mypy, and pre-commit.

```bash
uv sync --all-extras --dev
uv run maturin develop
uv run pre-commit run --all-files
cargo test
cargo clippy --all-targets -- -D warnings
cargo fmt --check
uv run pytest -q
uv run python benches/bench_scaling.py
uv run python benches/capture_scaling.py
```

For contribution rules, test expectations, and the release checklist, see
[CONTRIBUTING.md](CONTRIBUTING.md).

## Release

Releases are tag-driven and published by GitHub Actions with PyPI Trusted
Publishing. Configure the PyPI trusted publisher for repository
`dkajtoch/tandem-repeat`, workflow `.github/workflows/release.yaml`, and the
protected GitHub environment `pypi`.

```bash
git tag v0.1.0
git push origin v0.1.0
```

The workflow runs the full Python and Rust quality gates, builds an sdist plus
Linux and macOS wheels, validates artifacts with `twine check`, and publishes
from the protected `pypi` environment.

## Benchmarks

The benchmark scripts cover:

- scaling with text length,
- scaling with the number of inserted repeat blocks,
- dense periodic input such as `"a" * n`,
- multilingual Arabic, Hebrew, Hindi, CJK, emoji, and mixed-direction text.

The plotted scaling run writes artifacts to `bench-results/scaling.csv`,
`bench-results/summary.md`, and `bench-results/scaling.svg`.

Latest local scaling run:

- Python: 3.11.7
- Platform: macOS-26.4.1-arm64-arm-64bit
- Median of 3 trials where noted
- `find` and `find_primitive` capped at 50,000 returned blocks

| scenario | operation | 1k chars | 10k chars | 50k chars | 100k chars | 100k results | note |
| --- | --- | ---: | ---: | ---: | ---: | ---: | --- |
| sparse random text with one inserted repeat | `find` | 0.0050s | 0.0577s | 0.3145s | 0.6650s | 1,520 | compact vocabulary output |
| sparse random text with one inserted repeat | `find_longest` | 0.0050s | 0.0583s | 0.3134s | 0.6624s | 1 | same sparse scan, one result |
| dense single-character periodic text | `find_longest` | 0.00008s | 0.00070s | 0.00355s | 0.00686s | 1 | whole-text fast path |
| truncated periodic text: `("aab" * n)[:chars]` | `find_primitive` | 0.0073s | 0.1054s | 0.4404s | 0.9101s | 33,336 | output-sensitive primitive blocks |
| dense single-character periodic text | `find` | 0.0012s | 0.0881s | 2.0210s | timeout | - | many vocabulary blocks; 15s timeout |

These timings are machine-local measurements, not portable guarantees. The
right bound for result-returning methods is output-sensitive: `O(n + output)` is
the practical target for `find_primitive`, while `find` can return many compact
vocabulary blocks on low-entropy input. `find_longest` avoids result-set growth
because it returns only one block.

