tre
TRE 0.9.0
このプロジェクトはメンテナーを探しています。まず第一に、いくつかのプルリクエストがレビューを待っています。
ステップアップしたい場合は、[email protected]でお知らせください！
TREは、軽量で堅牢で効率的なPOSIX準拠のRegexpマッチングライブラリで、おおよそ（ファジー）マッチングなどのエキサイティングな機能を備えています。
TREで使用される一致するアルゴリズムは、検索されるテキストの長さの線形最悪の時間、および使用される正規表現の長さの二次最悪の時間を使用します。
言い換えれば、アルゴリズムの時間の複雑さはo（m^2n）であり、mは正規表現の長さ、nはテキストの長さです。使用済みのスペースは、正規表現の長さについても二次的ですが、検索された文字列に依存しません。この二次挙動は、おそらく実際には非常にまれな病理学的症例でのみ発生します。
このコードの操作方法は次のとおりです。
システムに次のツールをインストールする必要があります。
まず、木を準備します。ソースディレクトリのルートに変更して実行します
./utils/autogen.sh
これにより、前提条件ツールを使用してさまざまなものが再生され、構築可能なツリーが表示されます。
この後、Configureスクリプトを実行して、通常どおりTREを作成できます。
./configure
make
make check
make install
準備されたツリーで、このコマンドはソースコードTarballを作成します。
./configure && make dist
または、実行することもできます
./utils/build-sources.sh
ソースコードパッケージを構築し、それらをdistサブディレクトリに配置します。このスクリプトには、動作するzipコマンドが必要です。
TREは、さらに別のregexpマッチャーではありません。 TREには、ほとんどの無料のPOSIX互換性のある実装には存在しないいくつかの機能があります。これらの機能のほとんどは、非フリーの実装にも存在しません。
おおよそのパターンマッチングにより、一致を概算することができます。つまり、一致を何らかの尺度の近さの下で検索されたパターンに近づけることができます。 TREは、正確な一致を取得するために、検索されたテキストに文字を挿入、削除、または置換できる編集距離測定（Levenshtein距離とも呼ばれます）を使用します。
各挿入、削除、または置換により、試合の距離またはコストが追加されます。 TREは、指定されたしきい値よりも低いコストを持つ一致を報告できます。 TREは、最低コストで一致を検索するためにも使用できます。
TREには、GREPのスタイルでの概算の正体の一致のためのAgrep（概算Grep）コマンドラインツールのバージョンが含まれています。アリゾナ大学のSun WuやUdi Manberのような他のAGREP実装とは異なり、TRE Agrepは、任意の長さ、任意の数の誤差、および挿入、削除、および代替の不均一なコストの完全な正規表現を許可します。
POSIXは、regexp関数の動作を正確に定義します。 TREは、これらの仕様に可能な限り厳密に準拠しようとします。たとえば、TREは常にSubpatternsの正しい一致を返します。これを正しく行う他の実装はほとんどありません。実際、TRE以外の唯一の他の実装は、（無料であろうとなかろうと）Tom LordによるRx、John MaddockのRegex ++、Glenn FowlerとDoug McIlroyのAT＆T Ast regexです。
標準のTREは、IEEE STD 1003.1-2001、または一般に「POSIX」と呼ばれるオープングループベース仕様問題6に準拠しようとします。関連する部分は、正規表現（および理論的根拠）の基本仕様とregcomp() APIの説明です。
POSIX Regexpマッチャーに関する優れた調査については、AT＆T Labs ResearchのGlenn FowlerのTestRegexページを参照してください。
TREで使用される一致するアルゴリズムのため、 regexec()呼び出しによって最大時間が消費される最大時間は、常に検索された文字列の長さに直接比例します。 1つの例外があります。バック参照を使用すると、文字列の長さとともに指数関数的に成長するマッチング時間がかかる場合があります。これは、バック参照を一致させることがNPの完全な問題であり、最悪の場合に一致するために指数関数的な時間をほぼ確実に必要とするためです。
regexec()呼び出しは、ヒープからメモリを割り当てることはありません。 TREは、 regcomp()呼び出し中に必要なすべてのメモリを割り当て、 regexec()呼び出しの期間中、スタックフレームから一時的な作業スペースを割り当てます。必要な一時的なスペースの量は一致する間は一定であり、検索された文字列に依存しません。リーズナブルなサイズのREGEXPSの場合、 regcomp()コール中に5万5万件未満の動的に割り当てられたメモリ、コンパイルされたパターンバッファーの場合は20k未満、 regexec()コール中にスタックフレームから2キロバイト未満の一時的な作業スペースが必要です。時間 /メモリトレードオフはありません。 TREはコードサイズも小さいです。 TREで静的にリンクすると、実行可能ファイルサイズが30K未満（GCC-3.2、X86、GNU/Linux）が増加します。
TREはマルチバイト文字セットをサポートします。これにより、たとえば日本の地域でレジックスをシームレスに使用することができます。 TREは、幅広い文字APIも提供します。
TREは、regexpsと検索された文字列の両方でバイナリゼロ文字を可能にするAPIを提供します。標準のAPIは、たとえば、バイナリデータから印刷可能な単語を検索するために簡単に使用できません（ハッキングでは可能ですが）。標準APIでは、埋め込まれたバイナリゼロを含むパターンの検索はまったく不可能です。
TREは完全に糸が安全です。エクスポートされたすべての関数は再入力されており、複数のコンテキストで単一のコンパイルされたRegexpオブジェクトを同時に使用できます。たとえば、 main()と信号ハンドラー、またはマルチスレッドアプリケーションの多くのスレッド。
TREは、複数のプラットフォームでポータブルです。以下は、TREの開発とテストに使用されるプラットフォームとコンパイラのテーブルです。
| プラットフォーム | コンパイラ |
|---|---|
| FreeBSD 14.1 | Clang 18 |
| Ubuntu 22.04 | GCC 11 |
| macOS 14.6 | Clang 14 |
| Windows 11 | Microsoft Visual Studio 2022 |
TREは、ほとんどの最新のPOSIXのようなプラットフォームで変更なしでコンパイルし、ホストされたC実装を使用して任意のプラットフォームに簡単に移植できるようにする必要があります。
プラットフォームによっては、Libutf8をインストールして、幅広いキャラクターとマルチバイトの文字セットサポートを取得する必要がある場合があります。
TREは、NetBSDで使用される「2句」BSDスタイルのライセンスと本質的に同じライセンスの下でリリースされます。詳細については、ファイルライセンスを参照してください。
現在、100％POSIXコンプライアンスから欠落している要素の照合に関連する2つの機能があります。これらは：
照合要素のサポート（ [[.<X>.]] 、 <X>は照合要素です）。 Posixは、文字シーケンスがマルチキャラクター照合要素であるかどうかを判断する方法を定義しないため、マルチキャラクター照合要素を携帯的にサポートすることはできません。
たとえば[[=<X>=]]など、同等のクラスのサポート、 <X>は照合要素です。等価クラスは、 <X>と同じ一次照合重量を持つ任意の文字と一致します。繰り返しますが、POSIXは、照合要素の一次照合重量を決定するためのポータブルメカニズムを提供しません。
他のポータブルRegexp実装も照合要素をサポートしていないことに注意してください。単一の例外はRegex ++です。これには、さまざまな場所の要素を照合するための独自のデータベースが付属しています。照合要素と同等のクラスのサポートは広く要求されておらず、現時点ではTODOリストではそれほど高くありません。
これらは私が今すぐに実際に実装することを計画している他の機能です：
[[:<:]]や[[:>:]]など、GNU Regexで有効になっているすべての欠落しているGNU拡張機能。
最長の試合ではなく、最短の試合を返すためのREG_SHORTEST regexec()フラグ。
Perl互換的な構文：
[:^class:]クラスのキャラクター以外は何でも一致します。 [^[:class:]]すでに機能していることに注意してください。これは単なる速記に過ぎないことに注意してください。
A文字列の開始時にのみ一致します。
Z文字列の端でのみ、または最後にnewlineの前に一致します。
z文字列の端でのみ一致します。
l低ケース次の文字（VIを考えてください）。
u大文字次の文字（VIを考えてください）。
L低ケースまでE （VIを考えてください）。
U大文字までE （viを考えてください）。
(?=pattern)ゼロ幅ポジティブな見た目のアサーション。
(?!pattern)ゼロ幅の否定的な見た目アサーション。
(?<=pattern)ゼロ幅ポジティブルックビハインドアサーション。
(?<!pattern)ゼロ幅の否定的な見た目のアサーション。
特に、おおよそのマッチングなどのTREの非標準機能に関するドキュメントは、使用する拡張機能を見つけたい場合は、 include/tre/tre.hヘッダーを読み取りたい場合は、進行中の作業です。 Cソースコードに満足している場合は、追加のヒントを提供する場合があります。
