1

値を定義する頭字語のリスト (例: AB1、DE2、CC3) があり、文字列値 (例: "Happy:DE2|234") をチェックして、頭字語が文字列内にあるかどうかを確認する必要があるとします。頭字語の短いリストについては、通常、区切り記号 (例: (AB1|DE2|CC3) ) を使用する単純な RegEx を作成し、一致するものを探すだけです。

しかし、照合する頭字語が 30 を超える場合、どのように対処すればよいでしょうか? 同じ手法を使用するのは理にかなっていますか (醜い)、またはこのタスクを達成するためのより効率的で洗練された方法はありますか?

例の頭字語リストと例の文字列は、私が使用している実際のデータ形式ではなく、単に私の課題を表現する方法であることに注意してください。

ところで、私は SO関連の質問を読みましたが、それが私が達成しようとしていたことに当てはまるとは思いませんでした。

編集:一致した値をキャプチャする必要があることを含めるのを忘れていたため、正規表現を使用することを選択しました...

4

5 に答える 5

4

個人的には、正規表現で 30 が特に大きいとは思わないので、すぐに除外することはできません。1 行のコードで正規表現を作成できます。

var acronyms = new[] { "AB", "BC", "CD", "ZZAB" };
var regex = new Regex(string.Join("|", acronyms), RegexOptions.Compiled);
for (var match = regex.Match("ZZZABCDZZZ"); match.Success; match = match.NextMatch())
    Console.WriteLine(match.Value);
// returns AB and CD

そのため、コードは比較的エレガントで保守しやすいものになっています。頭字語の数の上限がわかっている場合は、正規表現エンジンに既に組み込まれている最適化の種類を知っている人は、いくつかのテストを行います。また、将来の正規表現エンジンの最適化を無料で利用できるようになります。パフォーマンスが問題になると信じる理由がない限り、単純にしてください。

一方、正規表現には他の制限がある場合があります。たとえば、デフォルトで頭字語 AB、BC、および CD がある場合、"ABCD" の一致としてこれらのうち 2 つだけが返されます。したがって、頭字語があることを伝えるのは得意ですが、複数の一致をキャッチすることに注意する必要があります。

パフォーマンスが問題になったとき (> 10,000 項目)、「頭字語」を HashSet に入れ、テキストの各部分文字列を検索しました (頭字語の最小長から頭字語の最大長まで)。ソーステキストが非常に短いので、これは私にとっては問題ありませんでした。以前は聞いたことがありませんでしたが、最初は、あなたが参照している質問で言及されている Aho-Corasick アルゴリズムが、この問題に対するより良い一般的な解決策のように見えます。

于 2009-01-31T05:39:41.050 に答える
0

正規表現のアプローチは、効率的でエレガントなようです。もちろん、式を作成するときはエスケープされていない文字に注意する必要があります。または、複雑さやサイズの制限のために式をコンパイルできない場合もあります。

これを行う別の方法は、すべての頭字語を表すトライデータ構造を構築することです（これは、正規表現マッチャーが実行していることと多少重複する可能性があります）。文字列内の各文字をステップスルーするときに、トライのルートへの新しいポインターを作成し、既存のポインターを適切な子（存在する場合）に進めます。いずれかのポインタがリーフに到達すると、一致が得られます。

于 2009-01-31T05:26:49.017 に答える
0

これが私が思いついたものです。あなたが提供できる建設的な批判をいただければ幸いです...

まず、私の頭字語のそれぞれを保持する列挙型を作成します。

enum acronym
{ AB1,DE2,CC3 }

次に、列挙型の文字列配列を作成します。

string[] acronyms = Enum.GetNames(typeof(acronym));

最後に、文字列配列をループして、regex.matchメソッドを実行します。

foreach (string a in acronyms)
{
    Match aMatch = Regex.Match(input, a.ToString(), RegexOptions.None);
    if (aMatch.Success)
    {
        ...<do something>...
        break;
    }
}

何か問題がありますか？

于 2009-01-31T05:30:29.523 に答える
0

頭字語のサイズが固定されている場合 (上記の例のように)、それらすべてのハッシュを計算し (アプリケーションの有効期間ごとに 1 回実行できます)、文字列をそのような重複部分に分割して、それらのハッシュも計算できます。次に、ある配列から別の配列への値を検索するだけです。

おそらく頭字語から接尾辞/接頭辞ツリーまたは類似のものを作成し、この情報を使用して検索することができます.Wikipediaにはそれを行うためのアルゴリズムがたくさんあります.

頭字語ごとに決定論的オートマトンを作成することもできますが、前のアプローチと非常によく似ています。

于 2009-01-31T04:37:11.300 に答える
0

単純に文字列を分割して、返されたリストを比較してみませんか? この場合、REGEX を使用するのは不必要なオーバーヘッドのようです。フォーマットが異なる場合があることは承知していますが、次のことができるようです。

  • 「タイトルセパレーター」に基づいて文字列を分割します。あなたの場合はコロンです:
  • 結果の 2 番目の半分である頭字語文字列を取得し、頭字語区切り文字 (この場合はパイプ |) に基づいて分割します。
  • 最後に、新たに分割された頭字語のリストを繰り返し処理し、ネストされた for ループを使用してそれぞれを候補のリストと比較します

編集:特定の頭字語または頭字語のセットが文字列内に存在するかどうかだけを知る必要がある場合は、.Match() の代わりに .Search() メソッドを使用します。

于 2009-01-31T04:42:08.593 に答える