TRE (computing)

---

title: "TRE (computing)" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["computer-libraries", "regular-expressions", "software-using-the-bsd-license"] description: "Open-source library for pattern matching in text" topic_path: "general/computer-libraries" source: "https://en.wikipedia.org/wiki/TRE_(computing)" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Open-source library for pattern matching in text ::

::data[format=table title="Infobox software"]

Field	Value
name	TRE
author	Ville Laurikari{{cite web
url	http://web.mit.edu/r/current/arch/i386_linux26/lib/R/library/base/html/grepRaw.html
title	R: Pattern Matching for Raw Vectors}}
latest preview date
frequently updated
programming language	C
genre	Approximate string matching
license	2-clause BSD-like license
website
::

| name = TRE | logo = | screenshot = | caption = | collapsible = | author = Ville Laurikari{{cite web |website=MIT.edu |url=http://web.mit.edu/r/current/arch/i386_linux26/lib/R/library/base/html/grepRaw.html |title=R: Pattern Matching for Raw Vectors}} | developer = | released = | latest release version = | latest release date = | latest preview version = | latest preview date = | frequently updated = | programming language = C | operating system = | platform = | size = | language = | status = | genre = Approximate string matching | license = 2-clause BSD-like license | website = TRE is an open-source library for pattern matching in text,{{cite web |url=https://gnuwin32.sourceforge.net/packages/tre.htm |title=Tre for Windows}} which works like a regular expression engine with the ability to do approximate string matching.{{cite magazine |magazine=Linux Magazine |url=https://www.linux-magazine.com/Issues/2016/186/Command-Line-tre-agrep/(offset)/3 |title=Using fuzzy searches with tre-agrep}} It was developed by Ville Laurikari and is distributed under a 2-clause BSD-like license.

The library{{cite web |url=https://www.archlinux.org/packages/community/x86_64/tre |title=tre 0.8.0-6 (x86_64) |date=July 7, 2020}} is written in C and provides functions which allow using regular expressions for searching over input text lines. The main difference from other regular expression engines is that TRE can match text fragments in an approximate way, that is, supposing that text could have some number of typos.

Features

TRE uses extended regular expression syntax with the addition of "directions" for matching preceding fragment in approximate way. Each of such directions specifies how many typos are allowed for this fragment.

Approximate matching{{cite conference |last1=Andoni |first1=Alexandr |first2=Robert |last2=Krauthgamer |first3=Krzysztof |last3=Onak |title=Polylogarithmic approximation for edit distance and the asymmetric query complexity |conference=IEEE Symp. Foundations of Computer Science (FOCS) |year=2010 |citeseerx=10.1.1.208.2079 |arxiv=1005.4033|bibcode=2010arXiv1005.4033A }} is performed in a way similar to Levenshtein distance, which means that there are three types of typos 'recognized': ::data[format=table]

Typo	Example	Data
insertion of an extra character	regullar experession	extra l, extra e
missing a character from pattern	reglar expession	missing u, missing r
replacement of some character	regolar exprezsion	u → o, s → z
::

TRE allows specifying of cost for each of three typos type independently.

The project comes with a command-line utility, a reimplementation of agrep.

Though approximate matching requires some syntax extension, when this feature is not used, TRE works like most of other regular expression matching engines. This means that

• it implements ordinary regular expressions written for strict matching;
• programmers familiar with POSIX-style regular expressions need not do much study to be able to use TRE.

Predictable time and memory consumption

The library's author states that time spent for matching grows linearly with increasing of input text length, while memory requirement is constant during matching and does not depend on the input, only on the pattern.

Other

Other features, common for most regular expression engines could be checked in regex engines comparison tables or in list of TRE features on its web-page.

Usage example

Approximate matching directions are specified in curly brackets and should be distinguishable from repetitive quantifiers (possibly with inserting a space after opening bracket):

• (regular){~1}\s+(expression){~2} would match variants of phrase "regular expression" in which "regular" have no more than one typo and "expression" no more than two; as in ordinary regular expressions "" means one or more space characters i.e. rogular ekspression would pass test;
• `(expression){ 5i + 3d + 2s

Language bindings

Apart from C, TRE is usable through bindings for Perl, Python and Haskell. It is the default regular expression engine in R. However, if the project should be cross-platform, each target platform would need a separate interface.

Disadvantages

Since other regular expression engines usually do not provide approximate matching ability, there is almost no concurrent implementation with which TRE could be compared. However, there are a few things which programmers may wish to see implemented in future releases:{{cite arXiv |quote=practical improvements .. Lurikari algorithm, notably .. |title=Tagged Deterministic Finite Automata with Lookahead |eprint=1907.08837 |last1=Trofimovich |first1=Ulya |year=2019 |class=cs.FL

• a replacement mechanism for substituting matched text fragments (like in sed string processor and many modern implementations of regular expressions, including built into Perl or Java);
• opportunity to use another approximate matching algorithm (than Levenshtein's) for better typo value assessment (for example Soundex), or at least this algorithm to be improved to allow typos of the "swap" type (see Damerau–Levenshtein distance).

References

References

1. "TRE web-page - Regex Syntax".
2. "Tre-agrep has all of grep's functionality but can also do ambiguous or fuzzy"
3. "TRE web-page - About".
4. "TRE web-page - FAQ".
5. "Regular Expressions as used in R".

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::