Metadata-Version: 2.4
Name: search-string-overvaagning
Version: 0.6.0
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. Single `SearchString` objects compile their patterns lazily with the Rust `regex` crate. 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.13. 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.0 | Speedup |
|---|---:|---:|---:|
| create 10k SearchString objects | 2.0 ms | 1.1 ms | 2x |
| build collection (10k search strings) | 116.1 ms | 39.2 ms | 3x |
| collection.find_all: 1k articles (list of sentences) | 6.27 s | 55.4 ms | 113x |
| collection.find_all: 1k articles (one str each) | 340.6 ms | 32.6 ms | 10x |
| collection.find_all: 100-page doc (one str) | 31.8 ms | 2.7 ms | 12x |
| collection.find_all: 100-page doc (list of sentences) | 178.9 ms | 5.9 ms | 31x |
| collection.find_all_sliding_window: 100-page doc | 1.41 s | 62.0 ms | 23x |
| SearchString.find_all: 500 SS x 200 articles | 10.20 s | 126.3 ms | 81x |
| SearchString.match: 1 SS x ~1.7k sentences | 4.9 ms | 482 µs | 10x |
| SearchString.highlight: ~1.7k sentences | 7.2 ms | 1.4 ms | 5x |

| Memory (RSS increase) | mypyc 0.5.3 | Rust 0.6.0 |
|---|---:|---:|
| search string objects (10k) | 2.2 MB | 2.0 MB |
| collection index (10k) | 73.3 MB | 31.5 MB |
| after searching 100-page doc | 2.7 MB | 0.8 MB |

The collection memory is the peak while building it; once built, a collection of 10,000 search strings retains about 9 MB (vs. 73 MB before).

## 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.13, regular GIL build):

| Batch | Loop of `find_all_with_text` | `max_threads=8` | `max_threads=None` (18 cores) |
|---|---:|---:|---:|
| 2,000 articles (lists of sentences) | 110 ms | 17 ms (6.5x) | 9.0 ms (12x) |
| 2,000 articles (one str each) | 59 ms | 8.9 ms (6.6x) | 4.8 ms (12x) |
| 16 x 100-page documents | 42 ms | 7.3 ms (5.8x) | 4.1 ms (10x) |

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

