Search String

Installation

You can install search-string from PyPI:

$ 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.

Development

You need uv and a Rust toolchain. All Python tools (ruff, pyright, pytest, prek) are pinned in uv.lock, and CI uses the same versions.

$ 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 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:

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

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

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

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

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

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

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

>>> 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).

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.

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:

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

>>> 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):

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): 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).
• New: SearchStringCollection.find_all_many searches a batch of texts, optionally on several threads (see 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.