Metadata-Version: 2.4
Name: search-string-overvaagning
Version: 0.6.2
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. Patterns are the lowercased alternatives with their `~` removed, and a candidate reported by the automaton is verified against the word boundaries the `~` asked for, with the same check that single search strings use, so a collection returns exactly what `SearchString.match` would. 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`. The benchmark checks that the Rust collection returns what `SearchString.find_all` returns on a sample of the articles, and that both versions' single-`SearchString` methods return identical results (collection results can differ from 0.5.3 since 0.6.2, see below).

| 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.2 (collection word boundaries)

No interface changes. One bug fix in `SearchStringCollection`, present since the first trie-based collection (0.5.x) and also in 0.6.0 and 0.6.1:

- `~` was a wildcard for *one* character from a fixed list of word-break characters (space, punctuation, ...) instead of a zero-width word boundary as in `SearchString.match`. The collection now parses parts with the same code as `SearchString` and checks boundaries with the same `\b` definition (Python's `\w`), so for every search string and text a collection returns exactly what `SearchString.match` / `SearchString.find_all` returns. The visible differences, all now resolved in favour of `SearchString.match`:
  - `~` inside a part: `lars ~lokke` now matches "Lars Løkke Rasmussen" in a collection (it did not before), and `lars~lokke` no longer does (there is no word boundary between `s` and `l`).
  - `~` next to a non-word character outside the old list: `~arla~` now matches "#arla", "arla&co" and "arla–mejeri" (en dash) in a collection, as it always did with `SearchString.match`.
  - Spaces around `;` are part of the alternative (`a ; b` matches `a ` and ` b`), a space before `!global` stays in the literal (`x !global` is still global but matches `x ` with the trailing space, not `x`), a part consisting only of `~` is empty, and sentences are no longer padded with newlines, so an alternative ending in `\n` does not match at the end of a sentence.
- The differential tests now compare `SearchStringCollection` against `SearchString.find_all` (the reference semantics) instead of against the old trie implementation.
- Speed and memory are unchanged or slightly better: without the wildcard, the automaton works on the exact lowercased bytes, so punctuation no longer produces candidates that a check has to reject (collection scans are 10-30% faster on the benchmark corpus, and the collection index for 10,000 search strings takes about 35 MB instead of 40 MB to build).

## 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

