- Rust の正規表現ライブラリを改善・最適化してきた
regex crate の作者がいます。
regex crate の内部を別個の API として公開する regex-automata という新しい crate が作られました。- これは、別バージョンのライブラリとして内部をここまで公開する初の正規表現ライブラリです。
- この記事は、改善のために書き直した過程、問題の解決方法、そして
regex-automata の API に関する案内を提供します。
- 対象読者は Rust プログラマと、有限オートマトンによる正規表現エンジンの実装方法に興味のあるすべての人です。
- この記事は
regex crate とその開発の簡単な歴史を紹介します。
regex crate が直面していた問題には、設定、テスト、特定の API 要求、完全にコンパイル済みの DFA の必要性などが含まれます。- 書き直しはこれらの問題を解決し、より柔軟で最適化されたソリューションを提供します。
regex-automata を別の crate として公開することで、メインの regex crate を複雑にせずに追加 API の実験と開発が可能になります。- この記事は、
regex-automata を使う利点と、正規表現エンジン分野における潜在的な改善可能性を強調しています。
- この記事は、
regex crate API へのコマンドラインアクセスを提供する regex-cli プログラムについて説明しています。
- このプログラムには、コンパイル済み DFA をファイルにシリアライズしたり Rust コードを生成したりするユーティリティが含まれています。
- この記事は、正規表現パターンに Unicode が与える影響の例を示しています。
regex-cli プログラムは、regex crate エコシステム内のさまざまなデータ型をデバッグして出力できます。- キャプチャグループを使って複数パターン検索を実行できる
regex-cli find コマンドがあります。
- この記事は、パターン解析から NFA 構築まで、正規表現エンジン内を流れるデータフローを説明します。
- リテラル抽出は、
regex crate で使われている重要な最適化手法です。
- リテラル抽出とは、正規表現パターンからリテラルを抽出して、ヘイスタック内の候補一致をすばやく識別することを意味します。
- どのリテラルを検索するかを選ぶことは、偽陽性を最小化し待ち時間を減らすために重要です。
- リテラル抽出は、偽陽性とレイテンシへの影響を最小限にするためのヒューリスティックなプロセスです。
- リテラル抽出の指針は、より長いリテラルを優先し、極端に短いものや一般的すぎるものを避けることです。
- この記事は、正規表現におけるリテラル列の最適化について説明します。
- リテラル列とは、完全一致する文字列として扱われる文字列の連続です。
- 最適化の過程では、性能向上のために無限化できる列を特定します。
- この記事は、異なる正規表現が異なるリテラル列を生成しうる過程について説明します。
- この記事は、ヘイスタック内でリテラルを検索する過程についても論じています。
- 単一部分文字列検索と複数部分文字列検索では、異なるアルゴリズムが使われます。
- この記事は、NFA（非決定性有限オートマトン）の概念と、正規表現エンジンにおけるその役割を紹介します。
- NFA は他の型に変換でき、たとえば DFA（決定性有限オートマトン）の実装に使えます。
- この記事は、NFA の構成要素について詳しい例を挙げて説明します。
- この記事は、新しい NFA コンパイラで epsilon 遷移の使用を減らす最適化について触れています。
- 新しい NFA コンパイラは、複数のバイト範囲を含む疎な状態を使って NFA の表現を最適化します。
- この最適化はオーバーヘッドを減らし、epsilon 遷移の必要性を取り除きます。
- 以前のコンパイラで使われていたバイト指向 NFA は遅く、Unicode 用 NFA とバイト指向 NFA を別々にコンパイルする必要がありました。
- 新しい NFA コンパイラは、UTF-8 オートマトンをバイト指向 NFA に統合することで Unicode クラスを処理します。
- 新しいコンパイラは、Daciuk のアルゴリズムを使って、ソート済みで非重複な要素列から最小 DFA を計算します。
- 逆遷移は
range trie という特別なデータ構造を使って処理されます。
- 新しい NFA コンパイラは、以前のコンパイラに比べて状態数が少なく、epsilon 遷移のない NFA を生成します。
- 逆縮約最適化を使うことで NFA のサイズをさらに小さくできますが、ビルド時間は増加します。
- 全体として、新しい NFA コンパイラは性能を向上させ、正規表現における Unicode クラス処理を単純化します。
- この記事は、文字エンコーディングに関する技術的な問題について議論します。
- この問題は、疎な文字と異なるエンコーディング形式での表現に関係しています。
- この記事は、特定の文字とそのエンコーディングにおける頻度に言及しています。
- この記事は、文字エンコーディングの複雑さと潜在的な課題を強調しています。
- この記事は、文字エンコーディングを扱うソフトウェアエンジニアや開発者にとって興味深い内容かもしれません。
- この記事は、正規表現エンジンにおける NFA 最適化手法について論じています。
- Thompson NFA は epsilon 遷移のため拡張性に乏しいことで知られています。
- この記事は、リテラルの交替を制限することで epsilon 遷移を減らす NFA 最適化を紹介します。
- 新しい NFA コンパイラは、リテラルの trie を生成し、epsilon 遷移を最小化した NFA に変換します。
- この最適化は最左優先の優先順位を維持しつつ検索性能を向上させます。
- この記事は、Glushkov NFA や、NFA を単一の連続割り当てに格納する作業といった今後の課題についても触れています。
- Rust の
regex crate は、機能と検索性能のバランスを取るために複数の regex エンジンを使っています。
- PikeVM はこの crate で最も強力な regex エンジンであり、すべての regex 機能をサポートします。
- PikeVM は NFA をシミュ
1件のコメント
Hacker Newsの意見