TRE (コンピューティング)

フリー百科事典ウィキペディアより
ナビゲーションにジャンプ 検索にジャンプ
TRE
原作者ヴィル・ラウリカリ[1]
リポジトリ
で書かれているC
タイプおおよその文字列一致
ライセンス2 条項 BSD ライクなライセンス
Webサイトlaurikari .net /tre /

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

ライブラリ[4]Cで書かれており、入力テキスト行の検索に正規表現を使用できる関数を提供します。他の正規表現エンジンとの主な違いは、TRE が近似的な方法でテキスト フラグメントを照合できることです。つまり、テキストにいくつかのタイプミスがある可能性があると仮定します。

機能

TRE は、前のフラグメントを近似的に一致させるために「方向」を追加した拡張正規表現構文を使用します。そのような指示のそれぞれは、このフラグメントに許容されるタイプミスの数を指定します。

近似マッチング[5]は、レーベンシュタイン距離と同様の方法で実行されます。つまり、「認識される」タイプミスには 3 つのタイプがあります[6]。

打ち間違え データ
余分な文字の挿入 定期的な表現 エクストラl、エクストラe
パターンからの文字の欠落 定期便 欠落u、欠落r
一部の文字の置換 正規表現 uosz

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

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

近似一致には構文の拡張が必要ですが、この機能を使用しない場合、TRE は他のほとんどの正規表現一致エンジンと同様に機能します。この意味は

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

予測可能な時間とメモリ消費

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

その他

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

使用例

おおよその一致する方向は中括弧で指定され、反復量指定子と区別できる必要があります (おそらく左括弧の後にスペースを挿入します)。

  • (regular){~1}\s+(expression){~2}「regular」に 1 つ以下のタイプミスがあり、「expression」に 2 つ以下のタイプミスがあるフレーズ「regular expression」のバリアントに一致します。通常の正規表現と同様に、" \s+" は 1 つまたは複数の空白文字を意味します。つまり、
    定期的なエクスプレッション
    
    テストに合格します。
  • (expression){ 5i + 3d + 2s < 11}タイプミスの合計コストが 11 未満で、挿入コストが 5、削除が 3、文字の置換が 2 に設定されている場合、単語「expression」に一致します。つまりekspresson、コストは 10 です。

言語バインディング

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

短所

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

  • 一致したテキスト フラグメントを置換するための置換メカニズム ( sed文字列プロセッサや、 PerlまたはJavaに組み込まれている正規表現の多くの最新の実装など);
  • 別の近似マッチング アルゴリズム (レーベンシュタインのよりも) を使用してタイポ値の評価を向上させる (たとえば、Soundex )、または少なくともこのアルゴリズムを改善して、「スワップ」タイプのタイポを許可する ( Damerau–Levenshtein 距離を参照)。

も参照

参考文献

  1. ^ a b "R: 生のベクトルのパターン マッチング" . MIT.edu . _
  2. ^ 「Tre for Windows」 .
  3. ^ a b c 「tre-agrep であいまい検索を使用する」 . Linux マガジン
  4. ^ a b "tre 0.8.0-6 (x86_64)" . 2020 年 7 月 7 日。
  5. ^ アンドニ、アレクサンドル。クラウトゲーマー、ロバート。オナック、クシシュトフ (2010)。編集距離と非対称クエリの複雑さの多対数近似IEEE シンプ。コンピューター サイエンスの基礎 (FOCS)。arXiv : 1005.4033 . ビブコード: 2010arXiv1005.4033A . CiteSeerX 10.1.1.208.2079 . 
  6. ^ "TRE Web ページ - 正規表現構文" .
  7. ^ 「Tre-agrep は grep のすべての機能を備えていますが、あいまいまたはファジーも実行できます」
  8. ^ "TRE Web ページ - 概要" .
  9. ^ "TRE Web ページ - FAQ" .
  10. ^ "R で使用される正規表現" .
  11. ^ "タグ付き決定論的有限オートマトンと先読み" . 実用的な改善 .. Lurikari アルゴリズム、特に ..

外部リンク

さらに読む