Metadata-Version: 2.4
Name: search-string-overvaagning
Version: 0.6.1
Classifier: License :: OSI Approved :: MIT License
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 :: Python :: 3.14
Classifier: Programming Language :: Python :: 3.15
Classifier: Programming Language :: Python :: Free Threading :: 3 - Stable
Classifier: Programming Language :: Python :: Implementation :: CPython
Classifier: Programming Language :: Rust
Classifier: Topic :: Software Development :: Libraries
Classifier: Typing :: Typed
License-File: LICENSE
Summary: SearchString is a custom implementation for searching strings for km24.dk.
Author-email: Soeren Mulvad <shmulvad@km24.dk>
Requires-Python: >=3.10
Description-Content-Type: text/markdown; charset=UTF-8; variant=GFM
Project-URL: Changelog, https://github.com/km24-dk/search-string/blob/main/CHANGELOG.md
Project-URL: Documentation, https://github.com/km24-dk/search-string/
Project-URL: Github, https://github.com/km24-dk/search-string
Project-URL: Homepage, https://github.com/km24-dk/search-string/
Project-URL: Issues, https://github.com/km24-dk/search-string/issues
Project-URL: Source, https://github.com/km24-dk/search-string

# Search String

![GitHub Workflow Status (branch)](https://github.com/kaas-mulvad/search-string/workflows/CI/badge.svg)
[![PyPI - Version](https://img.shields.io/pypi/v/search-string-overvaagning)][pypi]
![PyPI - Python Version](https://img.shields.io/pypi/pyversions/search-string-overvaagning)

## Installation

You can install `search-string` from [PyPI][pypi]:

```bash
$ pip install search-string-overvaagning
```

The package is supported on CPython 3.10 to 3.15, including the free-threaded builds (3.14t, 3.15t). Since version 0.6.0 the matching engine is written in Rust and exposed to Python with [PyO3]. Pre-built wheels are published for Linux (x86_64, aarch64) and macOS (x86_64, arm64). Installing from the source distribution requires a [Rust toolchain](https://rustup.rs/).

### Development

You need [uv](https://docs.astral.sh/uv/) and a [Rust toolchain](https://rustup.rs/). All Python tools (ruff, pyright, pytest, prek) are pinned in `uv.lock`, and CI uses the same versions.

```bash
$ uv sync                     # create .venv, install the tools and build the extension
$ uv run pytest               # Python tests, incl. differential tests against v0.5.3
$ uv run pyright              # type checking
$ cargo test                  # Rust unit tests
$ uv run prek install         # run ruff, pyright, cargo fmt and more on every commit
```

After changing Rust code, run `uv sync --reinstall-package search-string-overvaagning` (or `uv run maturin develop --release`) to rebuild the extension.

## About

This package implements the search string object that is used across [km24.dk](https://km24.dk/) for different types of surveillance.

It is used for searching a text. For something to be deemed a match, the text must match the `first_str` and if the `second_str` is not empty, the text must also match the `second_str`. If the `not_str` is not empty, the text must _not_ match the `not_str`. A logical AND is used between the three conditions. The three strings can each be a collection of strings separated by semicolons wherein a match is deemed by logical OR. You can use '~' to make a word boundary. Finally, you can use `!global` at the end of a string to signal that that part should check globally.

Quick examples:

```python
>>> ss = SearchString('example;hello', 'text', 'elephant', data=None)
>>> ss.match('This is an example text')
True
>>> ss.match('This text says hello')
True
>>> ss.match('This is just an example')
False
```

## Usage

### Creating Search Strings

Start by importing the `SearchString` class:

```python
>>> from search_string import SearchString
```

Construct a new search string by supplying the `first_str`, `second_str`, `not_str` and any `data` that can be useful to refer back to later, such as an ID:

```python
>>> ss = SearchString('first', '', '', data=2)
```

Optionally, you can also supply a `third_str` that works in the same was as `first_str` and `not_str` but _has_ to be supplied as a keyword argument:

```python
>>> ss = SearchString('first', '', '', data=2, third_str='third')
```

### Matching text

If you just need to find out whether a given search string matches a text, you can use the method `.match` on a `SearchString` instance.

Often, what you want to do, is to match a collection of search strings across a list of text, e.g. sentences. You can do that the following way:

```python
>>> from search_string import SearchString
>>> search_strings = [
...    SearchString('kan', '', 'ritzau', data=1),
...    SearchString('kan', '', 'ritzau!global', data=2)
... ]
>>> sentences = [
...    'Du kan skrive din tekst her.',
...    'Den kan bestå af flere sætninger.',
...    'Dig og Ritzau kan bestemme hvordan det skal være.',
...    'Nogle kan være lange, andre kan være korte.'
... ]
>>> res = SearchString.find_all(sentences, search_strings)
>>> res
[SearchString(kan, -, ritzau, data=1)]
```

For each of the matched search strings (in the above example, only one), you can extract the data and the matched text as follows:

```python
>>> res[0].data
1
>>> res[0].matched_text
'Du kan skrive din tekst her. Den kan bestå af flere sætninger. (...) Nogle kan være lange, andre kan være korte.'
>>> res[0].matched_text_highligthed
'Du <b>kan</b> skrive din tekst her. Den <b>kan</b> bestå af flere sætninger. (...) Nogle <b>kan</b> være lange, andre <b>kan</b> være korte.'
```

### Creating search strings that match everything

If you construct a completely empty search string, it will match everything (even the empty string), but the matched text will always be the empty string. This is to allow for "catch-all" search strings:

```python
>>> ss = SearchString('', '', '', data=1)
>>> ss.match('')
True
>>> ss.match('Some random text')
True
>>> ss.matched_text
''
```

### SearchStringCollection - Matching when you have many search strings

If you have a problem where you repeatedly will be matching new texts against the same collection of search strings, it is highly advised to use the `SearchStringCollection` which behind the scenes uses an [Aho-Corasick] automaton for efficient search when many search strings are present. There is some initial cost in building the automaton. Thus, it is recommended that you initialize the collection once and then continue to use it.

The most important method on `SearchStringCollection` is `find_all`, which takes a sentence (`str`) or list of sentences (`list[str]`) and returns the matched search strings, very similar to the familiar `SearchString.find_all`.

```python
>>> from search_string import SearchString, SearchStringCollection
>>> search_strings = [
...    SearchString('kan', '', 'ritzau', data=1),
...    SearchString('kan', '', 'ritzau!global', data=2)
... ]
>>> sentences = ...  # Same as before
>>> ss_collection = SearchStringCollection(search_strings)
>>> res = ss_collection.find_all()
>>> res
[SearchString(kan, -, ritzau, data=1)]
```

Importantly, `SearchStringCollection` relies on the `data` variable being set on the collection of search strings. If it is set to `None` or multiple search strings have the same value, a `ValueError` is raised.

## Performance

The Rust engine compiles all parts of all search strings in a `SearchStringCollection` into a single [Aho-Corasick] automaton, so a text is scanned once regardless of how many search strings there are. The automaton is a hybrid built for this workload: the shallow states, where a scan spends nearly all of its time, are stored as fully resolved DFA rows (one table lookup per byte, no failure transitions), while the long tail of deep states stays sparse so that the whole automaton fits in cache. Since each lookup depends on the previous one, the engine steps four independent parts of the input (chunks of a long text, or different sentences) through the automaton in the same loop, which lets the CPU overlap the lookups. Single `SearchString` objects match their alternatives as plain substrings of the lowercased text with SIMD multi-substring search, checking word boundaries (`~`) explicitly; the Rust `regex` crate is only used to highlight text outside Latin-1. Large inputs are scanned without holding the GIL.

Benchmark against the previous mypyc-compiled version (0.5.3), on a synthetic corpus of 10,000 search strings, 1,000 articles (~3 KB each) and a ~300 KB document (about 100 pages). Apple M5 Pro, CPython 3.14t. Reproduce with `python benchmarks/build_mypyc_baseline.py && python benchmarks/bench.py`. Both versions are checked to return identical matches.

| Scenario | mypyc 0.5.3 | Rust 0.6.1 | Speedup |
|---|---:|---:|---:|
| create 10k SearchString objects | 2.0 ms | 1.1 ms | 2x |
| build collection (10k search strings) | 66.6 ms | 15.5 ms | 4x |
| collection.find_all: 1k articles (list of sentences) | 5.81 s | 24.1 ms | 241x |
| collection.find_all: 1k articles (one str each) | 401.2 ms | 20.3 ms | 20x |
| collection.find_all: 100-page doc (one str) | 37.6 ms | 1.4 ms | 27x |
| collection.find_all: 100-page doc (list of sentences) | 158.5 ms | 2.2 ms | 72x |
| collection.find_all_sliding_window: 100-page doc | 1.37 s | 26.6 ms | 51x |
| SearchString.find_all: 500 SS x 200 articles | 9.92 s | 33.6 ms | 296x |
| SearchString.match: 1 SS x ~1.7k sentences | 4.9 ms | 177 µs | 28x |
| SearchString.highlight: ~1.7k sentences | 7.0 ms | 726 µs | 10x |

Compared to 0.6.0 (the first Rust version, same machine), the collection scenarios are 1.6-2.7x faster, `SearchString.find_all` 3.7x, `match` 2.7x and `highlight` 2.1x; creating search strings is bound by the Python call overhead and unchanged.

| Memory (RSS increase) | mypyc 0.5.3 | Rust 0.6.1 |
|---|---:|---:|
| search string objects (10k) | 2.7 MB | 2.8 MB |
| collection index (10k) | 76.5 MB | 40.1 MB |
| after searching 100-page doc | 3.1 MB | 1.6 MB |

The collection memory is the peak while building it; once built, a collection of 10,000 search strings retains about 19 MB for its automata (vs. 73 MB in 0.5.3 and 9 MB in 0.6.0, which traded that memory for speed).

## Thread safety

`SearchString` and `SearchStringCollection` can be shared between threads, also on free-threaded Python: concurrent searches, attribute changes and building collections never crash, deadlock or corrupt state, and a collection releases the GIL while scanning large inputs, so threads can search in parallel.

However, `find_all`, `find_one`, `find_all_sliding_window` and `SearchString.match` store the matched text on the `SearchString` objects themselves (`matched_sentences`, `matched_text`, ...). If two threads search with the same search strings at the same time, one thread can read the matched text of the other thread's search. The returned list of search strings is always correct.

For multi-threaded code, use `SearchStringCollection.find_all_with_text` (or `find_all_sliding_window_with_text`). It returns `SearchStringMatch` objects that carry the matched text themselves and leaves the search strings untouched, so one collection can be shared by all threads. It is as fast as `find_all`:

```python
>>> results = ss_collection.find_all_with_text(sentences)
>>> [(m.data, m.matched_text) for m in results]
[(1, 'Du kan skrive din tekst her. Den kan bestå af flere sætninger. (...) Nogle kan være lange, andre kan være korte.')]
>>> results[0].search_string
SearchString('kan', '', 'ritzau', data=1)
>>> results[0].matched_text_highlighted
'Du <b>kan</b> skrive din tekst her. Den <b>kan</b> bestå af flere sætninger. (...) Nogle <b>kan</b> være lange, andre <b>kan</b> være korte.'
```

### Searching many texts in parallel

To search a batch of texts, `find_all_many` returns one list of `SearchStringMatch` results per text (each text is a `str` or a list of sentences). With `max_threads` it searches the texts in parallel inside the extension, without holding the GIL, so it is faster even on regular Python and from a single Python thread. The default `max_threads=1` is as fast as calling `find_all_with_text` in a loop; `max_threads=None` uses one thread per CPU core. Small batches automatically use fewer threads, so opting in never makes a call slower.

```python
>>> results = ss_collection.find_all_many(list_of_articles, max_threads=None)
>>> for article, matches in zip(list_of_articles, results):
...     print([m.data for m in matches])
```

With 10,000 search strings (Apple M5 Pro, CPython 3.14t):

| Batch | Loop of `find_all_with_text` | `max_threads=8` | `max_threads=None` (18 cores) |
|---|---:|---:|---:|
| 2,000 articles (lists of sentences) | 47.7 ms | 8.1 ms (5.9x) | 4.8 ms (10x) |
| 2,000 articles (one str each) | 33.6 ms | 5.3 ms (6.4x) | 3.0 ms (11x) |
| 16 x 100-page documents | 35.8 ms | 7.1 ms (5.0x) | 4.3 ms (8x) |

## Changes in 0.6.1 (faster engine)

No interface changes. The engine was reworked for speed (see [Performance](#performance)): a custom Aho-Corasick automaton with resolved rows for the shallow states and interleaved scanning, and substring search instead of regular expressions for single search strings. Two things to be aware of:

- Single `SearchString` matching now runs on the lowercased text (`str.lower()`, as substring-only parts always did) instead of a case-insensitive regular expression. The results are identical for normal text; only Unicode case-folding corner cases can differ (e.g. `ſ` no longer matches `s`). Highlighting of text outside Latin-1 still uses the regex crate.
- A collection keeps more memory for its automata (about 19 MB for 10,000 search strings, vs. 9 MB before), in exchange for faster searching. The budget for the dense part is a constant (`DENSE_BUDGET`) in `src/collection.rs`.

## Changes in 0.6.0 (Rust rewrite)

The Python interface is unchanged except for the following:

- `SearchStringCollection` no longer takes a `trie` argument, and the `trie` attribute and the `Trie` class are gone. The collection is still picklable (it is rebuilt from its search strings when unpickled).
- Two bugs in `SearchStringCollection` were fixed, so that it now agrees with `SearchString.match`:
  - Search strings with uppercase letters (including `!GLOBAL`) never matched in a collection; patterns are now lowercased like the text.
  - A `!global` part that matched both globally and in a sentence was counted twice, which made e.g. `SearchString('x!global', '', '')` match the sentences *without* `x`.
- `SearchStringCollection.find_all` returns the matches in collection order (followed by catch-all search strings) instead of an arbitrary order.
- New: `SearchStringCollection.find_all_with_text` and `find_all_sliding_window_with_text`, which return the matched text in `SearchStringMatch` result objects instead of storing it on the search strings (see [Thread safety](#thread-safety)).
- New: `SearchStringCollection.find_all_many` searches a batch of texts, optionally on several threads (see [Searching many texts in parallel](#searching-many-texts-in-parallel)).
- `matched_sentences` returns a new list on each access: assign to it instead of mutating it in place.
- `first_str_raw`, `second_str_raw`, `third_str_raw` and `not_str_raw` are read-only.
- Pickled search strings now also keep `match_extract_max_sentences`.
- Private helpers of the old implementation were removed (except `_escape_pattern`, `_raw_parts` and `_get_inner`).
- Regular expressions are evaluated by the Rust `regex` crate instead of Python's `re`. They behave the same for normal text, but Unicode corner cases of `~` (word boundary) and case-insensitivity can differ (e.g. combining marks or `ß`).
- There is no pure-Python fallback any more.
- Python 3.9 is no longer supported.

[pypi]: https://pypi.org/project/search-string-overvaagning/
[PyO3]: https://pyo3.rs/
[Aho-Corasick]: https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm

