アプリケーションルートのデータ構造

Question

Webフレームワークは、要求パスを一連の正規表現と照合することによって、着信要求をエンドポイントにルーティングします。それでは、リクエストパス（ワイルドカード付き）を格納するための良い/最良のデータ構造は何でしょうか。

そして、そのようなパッケージが（任意の言語で）あれば？

Answer 1

正規表現は、ワイルドカードよりもはるかに多くをサポートします。 trieは通常、プレフィックスが一意である限り一致させることができますが、代替リストの論理和を一致させるには、Aho-Corasick algorithmのようなものを探します。

しかし、これらのアルゴリズム/データ構造は、参照の静的部分、すなわち予測可能な文字列と一致するもののみを考慮に入れている。ワイルドカードマッチングの場合、任意のバックトラッキングを許可すると、病理学的なパフォーマンスが得られる可能性があります。つまり、パスルーターで完全正規表現システムを使用すると、サービス拒否につながる可能性があるため、

Goは正規表現を（制限された形式であっても）Thmopson's constructionを使用してNFAに変換する方法についてはthis write upをチェックしてください。