Skip to content
Docs
Reference
Tools

Tools

Tools

The rest of trex: indexes that let a tree scan skip files, scans of input that arrives in pieces, token grammars, byte-pair subword encoders, presence filters and the compressor. The flags and parameters are on the CLI and PowerShell pages.

Indexes

An index is one file, .trex-index, at a tree’s root, holding a summary of each file: the token kinds its lex made, a filter over the words it holds, the range its numbers span and the range its timestamps span. A scan of the tree skips any file every one of its patterns is refused by, which skips the read, the lex and the walk together. A summary says “cannot match” only where that is certain: the kind mask and the ranges are exact, the word filter’s only error is a false present, and an alternation or a P* requires nothing. An entry records its file’s length and modified time, and a file that differs, or that the index has never seen, is scanned. An index changes how long a scan takes and never what it reports.

Measured over trex’s own source in benches/index_pruning.rs (70 files, 3.2 MB): 50x for \E, 23x for \T, 12x for \I, 9x for \N{>=100000}, 2x for a rare word, and 0.99 to 1.02x for a pattern present everywhere. The index is 320 bytes a file, 0.0071x the tree it covers.

$ cat tree/logs/a.log
from 10.0.0.1 at 09:14
retry once
$ cat tree/logs/b.log
queue drained
nothing to report

$ trex index tree/logs/
tree/logs/: 2 files indexed

$ trex index tree/logs/ --list
tree/logs/.trex-index: 2 files indexed

$ trex scan '\I' tree/logs/
tree/logs/a.log:1:6: "10.0.0.1"

A scan of a tree holding an index uses it without being asked; --no-index reads none, and scan --index builds one as the scan reads the files. A file named on the command line is scanned whatever the index says, and -v, -L and --passthru read no index. A file changed since the index was built is scanned, so the report follows the tree:

$ cat tree/logs/b.log
queue drained at 10.0.0.9
nothing to report
$ trex scan '\I' tree/logs/
tree/logs/a.log:1:6: "10.0.0.1"
tree/logs/b.log:1:18: "10.0.0.9"

In Rust index::Index::build summarizes a tree’s files, save and load write and read .trex-index, and refuses answers for one file and one pattern.

Streams

A stream scanner takes input in chunks and gives back the matches no later chunk can change, and the rest when the stream ends, so the matches over the whole stream are those of one scan over all of it. A chunk ending inside a token holds its match until the token ends. With the standard input alone and the plain report, scan reads the stream as it arrives and prints each match the moment it commits, so tail -f app.log | trex scan '\T:t \W \T{>+1h:t}' reports a gap as soon as the line that closes it ends; --json on a stream prints one object a line.

$ printf 'mail bob@x.com\nand ann@y.org now\nthen ted@z.net\n' | trex scan '\E'
[5..14] "bob@x.com"
[19..28] "ann@y.org"
[38..47] "ted@z.net"

A pattern that cannot commit a match before the end of the stream is scanned when the stream ends, and the command says on the standard error how many bytes it retained: one with a content guard, a lookahead, a lookbehind reaching before its match, a field anchor or a whole-stream axis, and one with no bounded length that the set engine walks, such as a balanced group. An unbounded pattern the single-pass engine walks commits early, keeping only the bytes some attempt still running can reach back over. The stream cuts only just after a newline, so ^ and $ commit as their line ends. --chunk-size N feeds a file in N-byte chunks through the same scanner.

Several patterns stream as one set through one window, the most conservative member deciding what commits, each match naming its member:

let set = trex::PatternSet::new(vec![trex::parse(r"\E").expect("valid"), trex::parse(r"\I").expect("valid")]);
let mut scan = trex::StreamScanner::over_set(set);
scan.push(b"from 10.0.0.1 to bob@");
scan.push(b"x.com");
let found: Vec<(usize, usize)> = scan.finish_with_members().iter().map(|(m, s)| (*m, s.start())).collect();
assert_eq!(found, [(1, 5), (0, 17)]);

Grammars

A token grammar is named rules over the token stream, with no per-language parser. A rule is name := alt | alt, one a line: <name> references another rule, "lit" matches a token by its text, a kind keyword matches a token by its kind (number, ident, string, ip, url, email, time, punct), any symbol takes *, + or ?, ( a b | c ) is a group, and @p after an alternative weights it, 1 where absent. # starts a comment. A rule that begins with itself is left recursive, which is how an operator grammar writes precedence and associativity. The first rule is the start unless --start names another.

$ cat arith.grammar
expr   := <expr> "+" <term> | <expr> "-" <term> | <term>
term   := <term> "*" <factor> | <term> "/" <factor> | <factor>
factor := number | ident | "(" <expr> ")"

$ trex grammar arith.grammar --text '2 + 3 * 4'
(expr 2 + (term 3 * 4))

$ trex grammar arith.grammar --text '2 - 3 - 4'
(expr (expr 2 - 3) - 4)

--count prints the number of derivations, which says how ambiguous the grammar is over the input; --best the probability of the most probable one under the @p weights, and --prob the total over all of them. A count or a probability of zero exits non-zero.

$ trex grammar --grammar-text 'expr := <expr> "+" <expr> | number' --text '1 + 2 + 3 + 4' --count
5

$ trex grammar --grammar-text 'expr := <expr> "+" <expr> @0.5 | number @0.5' --text '1 + 2 + 3' --best
0.03125

$ trex grammar --grammar-text 'expr := <expr> "+" <expr> @0.5 | number @0.5' --text '1 + 2 + 3' --prob
0.0625

Segmentation

--segment TEXT --dict FILE reads a run-together string over the words of a dictionary, every way it tiles into them, and parses each tiling: --count counts the tilings the grammar accepts and --best gives the most probable.

$ cat words.txt
a
b
ab

$ trex grammar --grammar-text 's := <s> ident | ident' --segment abab --dict words.txt --count
4

$ trex grammar --grammar-text 's := "ab" <s> | "ab"' --segment abab --dict words.txt --count
1

Byte-pair encoders

A byte-pair encoder is learned from a corpus: it merges the most frequent adjacent pair of symbols, a given number of times, and splits text into the subwords those merges make, </w> marking the end of a word. A model is one merge a line, its two symbols separated by a tab.

$ cat corpus.txt
the cat sat at the mat at the hat

$ trex bpe train corpus.txt --merges 5
trex bpe: learned 5 merges from 34 bytes in 0.0s
a	t
at	</w>
e	</w>
h	e</w>
t	he</w>

bpe encode --model M splits text with a model bpe train printed, and --max-bytes N trains on a sample of the corpus. In PowerShell ConvertTo-TrexBpe writes each subword, and Import-TrexBpe reads a model either surface wrote.

Prefilters

A presence filter over a corpus’s n-grams answers whether a literal might occur in it without scanning it: a literal it rejects is absent, and one it passes might be present, which an exact search confirms. A literal shorter than one n-gram is never rejected. The filters are a Bloom filter (the default), a cuckoo filter and an xor filter.

$ trex prefilter --text 'the quick brown fox ERROR here' --literal ERROR --literal MISSING
bloom: "ERROR" -> might occur; present (confirmed)
bloom: "MISSING" -> ABSENT (rejected with no corpus scan)

--filter bloom|cuckoo|xor picks the filter; --verify probes every filter’s contract over the corpus - no literal present is ever rejected - and exits non-zero where one is broken. In PowerShell New-TrexPrefilter writes the filter as an object with a MightContain method, and Test-TrexPrefilter -Verify writes each filter’s probes.

Compression

compress comes with the compress feature, the one trex feature outside the default build; a default binary leaves out the coder and the 21.6 MB prior it reads, and answers the command with the build that has it:

cargo build --release --features compress

It reports the code length the default context-mixing model, a logistic mix with the orbit model using the baked prior, gives the input: the size is that length in bits rounded up to bytes. No compressed stream is written and nothing decodes one.

$ trex compress --text 'the quick brown fox jumps over the lazy dog the quick brown fox jumps'
trex compress: 69 bytes -> 15 bytes  (1.626 bits/byte, 21.7% of original)
  coder: logistic mix + orbit + baked prior   0.00 MB/s   (--compare for the full table)

--compare prints every coder’s bits per byte and encode speed, the BPE baseline included; --no-baked runs with no prior. Decoding the prior costs every run about 1.9 s and a gigabyte of memory before the first byte is coded; --prior-cache DIR writes it once into DIR as the coder’s own tables (1.4 GB for the shipped prior, 2.4 s on PC2) and maps them on every later run in under a millisecond, coding to the same bits. A read of a mapped table costs 1.4-1.7x a decoded one, so the cache pays on inputs under roughly 7-10 MB and the decode pays above.

Three parallel backends trade ratio for speed. --chunks N slices the input across N cores (0 for every logical core), each chunk seeded from the baked prior; --gpu runs the device coder, one CUDA thread per chunk, with TREX_GPU_CHUNK and TREX_GPU_OVERLAP setting its chunk size and warmup; --hybrid runs the CPU and the device at once on a head and tail split. The sequential CPU coder gives the best ratio, which is why none of the three is the default; the choose a backend how-to compares them.

Pattern files