TRE（コンピューティング）

TREは、テキスト内のパターンマッチングのためのオープンソース ライブラリです。 ^{[2]これは、}近似文字列マッチング機能を備えた正規表現エンジンのように機能します。^{[3]これは、Ville Laurikari [1]}によって開発され、 2条項BSDライクなライセンスの下で配布されています。

ライブラリ^[4]はC言語で書かれており、正規表現を使用して入力テキスト行を検索できる関数を提供します。他の正規表現エンジンとの主な違いは、TREはテキストにいくつかのタイプミスがある可能性があると想定して、テキストの断片を近似的に一致させることができることです。

TRE は、先行するフラグメントを近似的に一致させるための「方向」を追加した拡張正規表現構文を使用します。各方向は、このフラグメントに対して許容される入力ミスの数を指定します。

近似マッチング^[5]はレーベンシュタイン距離に似た方法で実行され、3種類のタイプミスが「認識」されることを意味します。^[6]

TRE では、3 つのタイプミス タイプごとに コストを個別に指定できます。

このプロジェクトには、 agrepの再実装であるコマンドライン ユーティリティが付属しています。

近似マッチングにはある程度の構文拡張が必要ですが、この機能を使用しない場合、TREは他のほとんどの正規表現マッチングエンジンと同様に動作します。つまり、

• 厳密なマッチングのために書かれた通常の正規表現を実装している。^{[3] [7]}
• POSIXスタイルの正規表現^[4]に精通したプログラマーは、TREを使用するために多くの勉強をする必要はありません。^[3]

ライブラリの作者は^[8]、マッチングにかかる​​時間は入力テキストの長さの増加に比例して増加するが、マッチング中のメモリ要件は一定であり、入力に依存せずパターンのみに依存すると述べています。

ほとんどの正規表現エンジンに共通するその他の機能は、正規表現エンジンの比較表や Web ページの TRE 機能リストで 確認できます。

近似一致方向は中括弧で指定され、繰り返しの量指定子と区別できる必要があります (開き括弧の後にスペースを挿入することもできます)。

• (regular){~1}\s+(expression){~2}は、「regular」に1つ以上のタイプミスがなく、「expression」に2つ以上のタイプミスがない「regular expression」というフレーズのバリエーションに一致します。通常の正規表現と同様に、「\s+」は1つ以上のスペース文字を意味します。つまり、

  発音
  

  テストに合格するだろう。
• (expression){ 5i + 3d + 2s < 11}挿入コストが 5、削除コストが 3、文字の置換コストが 2 に設定され、タイプミスの合計コストが 11 未満の場合、単語「expression」と一致します (つまり、ekspressonコストは 10 になります)。

C以外にも、TREはPerl、Python、Haskellのバインディングを通じて使用可能です。^[9]これはRのデフォルトの正規表現エンジンです。^[10]ただし、プロジェクトがクロスプラットフォームである場合は、対象プラットフォームごとに個別のインターフェースが必要になります。

他の正規表現エンジンは通常、近似マッチング機能を提供しないため、TREと比較できる並行実装はほとんどありません。しかし、プログラマーが将来のリリースで実装されることを望むものがいくつかあります。^[11]

• 一致したテキストフラグメントを置き換えるための置換メカニズム（sed文字列プロセッサや、 PerlやJavaに組み込まれているものを含む多くの最新の正規表現の実装と同様）。
• より優れたタイプミス値評価のために、別の近似マッチングアルゴリズム（Levenshtein のもの以外）を使用する機会（たとえばSoundex）、または少なくともこのアルゴリズムを改良して「スワップ」タイプのタイプミスを許可する機会（Damerau–Levenshtein 距離を参照）。

• レーベンシュタインオートマトン
• 正規表現エンジンの比較
• アグレップ

• TRE - 無料でポータブルな近似正規表現マッチングライブラリ

• ナバロ、ゴンサロ (2001 年 3 月)、「近似文字列マッチングのガイド ツアー」、ACM コンピューティング調査、33 (1): 31–88、CiteSeerX  10.1.1.452.6317、doi :10.1145/375360.375365、S2CID  207551224