4

さらに、その言語で各単語が出現する単語頻度を含む、ある種の辞書を作成する必要があります。通常、これは std::unordered_map を使用して実装されますよね? ここにキャッチがあります...正規表現に準拠するすべての単語とその頻度を見つけたいのですが、パフォーマンスが私の最大の関心事です。

要素の範囲を繰り返し処理し、要素がパターンに一致するかどうかを要素ごとにチェックすることは避けられないと思います。したがって、マップの代わりにベクトルのペアを使用する方が賢明かもしれないと思いました。

using namespace std;
typedef vector<pair<string, double>> Dictionary
vector<Dictionary::const_iterator> index;
Dictionary dict;
...
for_each(index['d'], index['e'], DoSomething);

これにより、この場合は「d」で始まるすべての単語を効果的に反復処理できます。もちろん、これは、正規表現の最初の文字を既に知っている場合にのみ役立ちますが、そうではないことが多いと思います。また、不確実性なしで単語全体をすでに知っていて、その頻度を調べたいだけの場合は、それが見つかるまでセクション全体を反復する必要があります. 地図があればもっと早く調べることができます。たとえば、「deer」という単語を検索する場合

Dictionary::const_iterator it = 
    find_if(index['d'], index['e'], []    // Lambda
        (pair<string, double> const &pr)
        {
           return pr.first == "deer";
        });

まったく最適ではありません！解決策は、さまざまな状況で辞書のさまざまな実装を使用することかもしれません。メモリは大きな問題ではありませんが、これはばかげた回避策のように思えます。

助言がありますか？

4

2 に答える 2

1

あなたが考えていた線に沿って、 std::vector<std::pair<boost::regex, int> >おそらく最も効率的でしょう。一致するものを見つけることを繰り返します。

作業を行う場合は、キャプチャ（ほとんどの正規表現の演算子）を使用せずに、独自の正規表現クラスを実装することをお勧めします。キャプチャがないと、正規表現を純粋なDFAに(...)変換するのはかなり簡単です。また、正規表現に変換することも、正規表現ごとに異なる受け入れコードを返すこともできます。（これは、私自身の正規表現クラスの動作方法です。ほとんどのアプリケーションでは、キャプチャをサポートしていないため、Boostほど柔軟ではありません。ただし、次のようなことが可能です。

RegularExpression t1( expr1", 0 );
RegularExpression t2( expr2", 1 );
//  ...
RegularExpression t = t1 | t2 /* | t3 | t4 | ... */ ;

一致する場合、expr1が一致する場合は0を返し、expr2が一致する場合は1を返します。次に、一致IDをintのベクトルへのインデックスとして使用できます。（一致するものがない場合は-1を返します。）

このようにすると、検索時間は入力の長さに対して線形になります。一致させようとしている式の数に関係なく。（私のRegularExpressionクラスは、コンパイラのフロントエンドを生成するために20年以上前に設計されました。約15年前に、UTF-8を入力として処理するために再作成しました。）

何年もの間、コードはWebで入手できましたが、現在Webページを持っていないので、誰かが古いコピーを保持していない限り、そうではありません。喜んでお送りしますが、ライブラリはしばらくの間メンテナンスされていないため、最新のコンパイラでコンパイルするのは簡単ではないかもしれません。（元々は先行標準のC ++で記述されていましたが、Sun CC 4.xなどでコンパイルするための回避策がいくつか含まれています。）

于 2012-12-18T11:37:28.520 に答える
0

あなたの最良の選択は、 http://www.ims.uni-stuttgart.de/projekte/gramotron/SOFTWARE/SFST.htmlのような有限サテ変換器を使用することです。

あなたが言ったように、地図は多くのスペースを使います。

トランスデューサは 1 つの大きな正規表現として見ることができます (正規表現はコンパイルされたオートマトンです)。

于 2012-12-18T11:16:46.840 に答える