4

先日、これを聞いてみましたが、確かに最初はよくフレーズや郵便番号が出なかったので、答えは締め切られました。正直なところ、これは私を非常に迅速に狂わせているので、ここで私は再試行しています。:)

私はこのアドレスパーサーを実装しようとしています。これは元々コンソールベースのc#プログラムです。TextBoxこれを、入力用Button、解析をアクティブ化するため、およびTextBlock結果を表示するためだけで構成されるスタンドアロンのWPFプログラムに正常に変換しました。これを書いているときに、出力をメインプログラムで必要になるものに切り捨てましたが、それでも正常に機能します。以下に、このためのコード全体を含めました。

次のステップは、これをメインプログラムに移植することでした。これは、文字通りコピー/貼り付けを使用して行いました。ただし、これを実行すると、ボタンを押した後にプログラムがハングします。最終的に、VSは、メッセージを出力せずにプロセスが長すぎるというエラーを出し、TaskManagerのメモリ使用量が約70kから3,000,000に徐々に増加します。これに応えてParsing、メインプロセスの作業負荷を軽減することを期待して、このメソッドをバックグラウンドワーカーに割り当てました。これはプログラムのフリーズを解決しましたが、バックグラウンドスレッドは同じことを行い、RAM使用量を増やし、何も返しませんでした。

だから今、私はちょっと行き詰まっています。コードのすべての行にブレークポイントを使用する場合、これが最後に発生するため、問題はvar result = parser.ParseAddress(input);ステートメントのどこかにあることを私は知っています。しかし、基本的に、これが1つのWPFプログラムで問題を引き起こし、別のWPFプログラムでは問題を引き起こさない理由を理解するのに迷っています。

必要に応じて、メインプログラムの完全なソースコードをどこかに投稿できれば幸いですが、ここに最大20の異なるクラスファイルとプロジェクトに相当するコードを投稿するのは良い考えではありません。:)

スタンドアロンのWPFアプリ

namespace AddressParseWPF
{
    /// <summary>
    /// Interaction logic for MainWindow.xaml
    /// </summary>
    public partial class MainWindow : Window
    {
        public MainWindow()
        {
            InitializeComponent();
        }

        public void Execute()
        {
            AddressParser.AddressParser parser = new AddressParser.AddressParser();
            var input = inputTextBox.Text;

            var result = parser.ParseAddress(input);

            if (result == null)
            {
                outputTextBlock.Text = "ERROR. Input could not be parsed.";
            }
            else
            {
                outputTextBlock.Text = (result.StreetLine + ", " + result.City + ", " + result.State + "  " + result.Zip);
            }
        }

        private void actionButton_Click(object sender, RoutedEventArgs e)
        {
            Execute();
        }
    }
}

パーサーを移植するメインプログラム

public void ExecuteAddressParse()
{
    AddressParser.AddressParser parser = new AddressParser.AddressParser();
    var input = inputTextBox.Text;

    var result = parser.ParseAddress(input);

    if (result == null)
    {
        outputTextBlock.Text = "ERROR. Input could not be parsed.";
    }
    else
    {
        outputTextBlock.Text = (result.StreetLine + ", " + result.City + ", " + result.State + "  " + result.Zip);
    }
}       

private void actionButton_Click(object sender, RoutedEventArgs e)
{
    ExecuteAddressParse();
}

ParseAddressメソッド

public AddressParseResult ParseAddress(string input)
{
    if (!string.IsNullOrWhiteSpace(input))
    {
        var match = addressRegex.Match(input.ToUpperInvariant());
        if (match.Success)
        {
            var extracted = GetApplicableFields(match);
            return new AddressParseResult(Normalize(extracted));
        }
    }

    return null;
}

RegExMatchメソッド

private static void InitializeRegex()
{
    var suffixPattern = new Regex(
        string.Join(
            "|",
            new [] {
                string.Join("|", suffixes.Keys), 
                string.Join("|", suffixes.Values.Distinct())
            }),
        RegexOptions.Compiled);

    var statePattern = 
        @"\b(?:" + 
        string.Join(
            "|",
            new [] {
                string.Join("|", states.Keys.Select(x => Regex.Escape(x))),
                string.Join("|", states.Values)
            }) +
        @")\b";

    var directionalPattern =
        string.Join(
            "|",
            new [] {
                string.Join("|", directionals.Keys),
                string.Join("|", directionals.Values),
                string.Join("|", directionals.Values.Select(x => Regex.Replace(x, @"(\w)", @"$1\.")))
            });

    var zipPattern = @"\d{5}(?:-?\d{4})?";

    var numberPattern =
        @"(
            ((?<NUMBER>\d+)(?<SECONDARYNUMBER>(-[0-9])|(\-?[A-Z]))(?=\b))    # Unit-attached
            |(?<NUMBER>\d+[\-\ ]?\d+\/\d+)                                   # Fractional
            |(?<NUMBER>\d+-?\d*)                                             # Normal Number
            |(?<NUMBER>[NSWE]\ ?\d+\ ?[NSWE]\ ?\d+)                          # Wisconsin/Illinois
          )";

    var streetPattern =
        string.Format(
            CultureInfo.InvariantCulture,
            @"
                (?:
                  # special case for addresses like 100 South Street
                  (?:(?<STREET>{0})\W+
                     (?<SUFFIX>{1})\b)
                  |
                  (?:(?<PREDIRECTIONAL>{0})\W+)?
                  (?:
                    (?<STREET>[^,]*\d)
                    (?:[^\w,]*(?<POSTDIRECTIONAL>{0})\b)
                   |
                    (?<STREET>[^,]+)
                    (?:[^\w,]+(?<SUFFIX>{1})\b)
                    (?:[^\w,]+(?<POSTDIRECTIONAL>{0})\b)?
                   |
                    (?<STREET>[^,]+?)
                    (?:[^\w,]+(?<SUFFIX>{1})\b)?
                    (?:[^\w,]+(?<POSTDIRECTIONAL>{0})\b)?
                  )
                )
            ",
            directionalPattern,
            suffixPattern);

    var rangedSecondaryUnitPattern =
        @"(?<SECONDARYUNIT>" +
        string.Join("|", rangedSecondaryUnits.Keys) +
        @")(?![a-z])";
    var rangelessSecondaryUnitPattern =
        @"(?<SECONDARYUNIT>" +
        string.Join(
            "|",
            string.Join("|", rangelessSecondaryUnits.Keys)) +
        @")\b";
    var allSecondaryUnitPattern = string.Format(
        CultureInfo.InvariantCulture,
        @"
            (
                (:?
                    (?: (?:{0} \W*)
                        | (?<SECONDARYUNIT>\#)\W*
                    )
                    (?<SECONDARYNUMBER>[\w-]+)
                )
                |{1}
            ),?
        ",
         rangedSecondaryUnitPattern,
         rangelessSecondaryUnitPattern);

    var cityAndStatePattern = string.Format(
        CultureInfo.InvariantCulture,
        @"
            (?:
                (?<CITY>[^\d,]+?)\W+
                (?<STATE>{0})
            )
        ",
        statePattern);
    var placePattern = string.Format(
        CultureInfo.InvariantCulture,
        @"
            (?:{0}\W*)?
            (?:(?<ZIP>{1}))?
        ",
        cityAndStatePattern,
        zipPattern);

    var addressPattern = string.Format(
        CultureInfo.InvariantCulture,
        @"
            ^
            # Special case for APO/FPO/DPO addresses
            (
                [^\w\#]*
                (?<STREETLINE>.+?)
                (?<CITY>[AFD]PO)\W+
                (?<STATE>A[AEP])\W+
                (?<ZIP>{4})
                \W*
            )
            |
            # Special case for PO boxes
            (
                \W*
                (?<STREETLINE>(P[\.\ ]?O[\.\ ]?\ )?BOX\ [0-9]+)\W+
                {3}
                \W*
            )
            |
            (
                [^\w\#]*    # skip non-word chars except # (eg unit)
                (  {0} )\W*
                   {1}\W+
                (?:{2}\W+)?
                   {3}
                \W*         # require on non-word chars at end
            )
            $           # right up to end of string
        ",
        numberPattern,
        streetPattern,
        allSecondaryUnitPattern,
        placePattern,
        zipPattern);
    addressRegex = new Regex(
        addressPattern,
        RegexOptions.Compiled | 
        RegexOptions.Singleline | 
        RegexOptions.IgnorePatternWhitespace);
}
4

3 に答える 3

6

RegexOptions.Compiledフラグを省略しても正規表現は機能しますか?

返事はイエスでした。

なぜ?

Regex コンパイラは (いくつかの?) 大きなパターンで遅いようです。

それはあなたがしなければならないトレードオフです。

于 2012-05-21T16:07:25.990 に答える
1

正規表現の部分式の一部は不適切です (@Justin Morgan が言及しているように)。
これは通常、再利用可能な断片化された正規表現に参加した結果であり、
私はうんざりします.

ただし、このアプローチを使用/実行する場合は、
構築後に実際の正規表現を出力することをお勧めします。そして、それをフォーマットした後、サンプルに対してテストし
、メイン プログラムから独立して実行します。そのように修正する方が簡単です。
疑わしい部分式が見つかった場合は、その時点で失敗するようにするか
、一般的にはサンプルの最後近くに失敗を挿入してみてください。
失敗するのに瞬き 以上かかる場合は、大幅に後戻りします。

逆走も悪くないけど。大きな利点があります。それがなければ、いくつかのこと
が一致しません。秘訣は、周囲のものと比較して結果に影響を与えない部分式を分離
し、バックトラッキングを制限することです。

私は USPS のサイトに行き
、住所の正規表現を生成するのに十分なサンプルの状態/サフィックス/方向/セカンダリ サンプルを入手しました。
以下は、コードから生成された正規表現のクリーンアップされたバージョンです。

幸運を!

 ^
   # Special case for APO/FPO/DPO addresses
   (
      [^\w\#]*
      (?<STREETLINE> .+? )
      (?<CITY> [AFD] PO )
      \W+
      (?<STATE> A [AEP] )
      \W+
      (?<ZIP> \d{5} (?: -? \d{4} )? )
      \W*
   )
 |         
   # Special case for PO boxes
   (
      \W*
      (?<STREETLINE> ( P [\.\ ]? O [\.\ ]? \  )? BOX \  [0-9]+ )
      \W+
      (?:
          (?:
              (?<CITY> [^\d,]+? )
              \W+
              (?<STATE>
                 \b
                 (?:AL|AK|AS|AZ|AR|Alabama|Alaska|American Samoa|Arizona|Arkansas)
                 \b
              )
          )
          \W*
      )?
      (?:
          (?<ZIP> \d{5} (?: -? \d{4} )? )
      )?
      \W*
   )
 |          
   (
       [^\w\#]*    # skip non-word chars except # (eg unit)
       (
         (
              (
                (?<NUMBER> \d+ )
                (?<SECONDARYNUMBER> (-[0-9]) | (\-?[A-Z]) )
                (?=\b)
              )                                                  # Unit-attached
           |          
             (?<NUMBER> \d+ [\-\ ]? \d+ \/ \d+ )                 # Fractional
           |
             (?<NUMBER> \d+ -? \d* )                             # Normal Number
           |
             (?<NUMBER>[NSWE]\ ?\d+\ ?[NSWE]\ ?\d+)              # Wisconsin/Illinois
         )
       )
       \W*

       (?:
           # special case for addresses like 100 South Street
           (?:
               (?<STREET>North|East|South|West|Northeast|Southeast|Northwest|Southwest|N|E|S|W|NE|SE|NW|SW|N\.|E\.|S\.|W\.|N\.E\.|S\.E\.|N\.W\.|S\.W\.)
               \W+
               (?<SUFFIX>ALLEY|ALY|ALLY|ALLEE|ALLEY|ALY)
               \b
           )
         |
           (?:
               (?<PREDIRECTIONAL>North|East|South|West|Northeast|Southeast|Northwest|Southwest|N|E|S|W|NE|SE|NW|SW|N\.|E\.|S\.|W\.|N\.E\.|S\.E\.|N\.W\.|S\.W\.)
               \W+
           )?
           (?:
                (?<STREET> [^,]* \d )
                (?:
                   [^\w,]*
                   (?<POSTDIRECTIONAL>North|East|South|West|Northeast|Southeast|Northwest|Southwest|N|E|S|W|NE|SE|NW|SW|N\.|E\.|S\.|W\.|N\.E\.|S\.E\.|N\.W\.|S\.W\.)
                   \b
                )
             |
                (?<STREET> [^,]+ )
                (?:
                    [^\w,]+
                    (?<SUFFIX>ALLEY|ALY|ALLY|ALLEE|ALLEY|ALY)
                    \b
                )
                (?:
                    [^\w,]+
                    (?<POSTDIRECTIONAL>North|East|South|West|Northeast|Southeast|Northwest|Southwest|N|E|S|W|NE|SE|NW|SW|N\.|E\.|S\.|W\.|N\.E\.|S\.E\.|N\.W\.|S\.W\.)
                    \b
                )?
             |
                (?<STREET> [^,]+? )
                (?:
                    [^\w,]+
                    (?<SUFFIX>ALLEY|ALY|ALLY|ALLEE|ALLEY|ALY)
                    \b
                )?
                (?:
                    [^\w,]+
                    (?<POSTDIRECTIONAL>North|East|South|West|Northeast|Southeast|Northwest|Southwest|N|E|S|W|NE|SE|NW|SW|N\.|E\.|S\.|W\.|N\.E\.|S\.E\.|N\.W\.|S\.W\.)
                    \b
                )?
           )
       )           

       \W+        

       (?:      
           (
               (
                  :?
                  (?:
                      (?:
                         (?<SECONDARYUNIT>APT|BLDG|DEPT|FL|HNGR|LOT|PIER|RM|SLIP|SPC|STOP|STE|TRLR|UNIT)
                         (?! [a-z] )
                         \W*
                       )
                    |
                       (?<SECONDARYUNIT> \# )
                       \W*
                  )
                  (?<SECONDARYNUMBER> [\w-]+ )
               )
             |
               (?<SECONDARYUNIT>BSMT|FRNT|LBBY|LOWR|OFC|PH|REAR|SIDE|UPPR)
               \b
           )
           ,?
           \W+
       )?

       (?:
           (?:
               (?<CITY> [^\d,]+? )
               \W+
               (?<STATE>
                  \b
                  (?:AL|AK|AS|AZ|AR|Alabama|Alaska|American Samoa|Arizona|Arkansas)
                  \b
               )
           )
           \W*
       )?

       (?:
           (?<ZIP> \d{5} (?: -? \d{4} )? )
       )?

       \W*         # require on non-word chars at end
   )
 $           # right up to end of string

C# コード

   public static void InitializeRegex()
    {
        Dictionary<string, string> suffixes = new Dictionary<string, string>()
        {
          {"ALLEY",  "ALLEE"},
          {"ALY",  "ALLEY"},
          {"ALLY",  "ALY"},
        };

        var suffixPattern = new Regex(
            string.Join(
                "|",
                new[] {
            string.Join("|", suffixes.Keys.ToArray()), 
            string.Join("|", suffixes.Values.Distinct().ToArray())
        }),
            RegexOptions.Compiled);

        //Console.WriteLine("\n"+suffixPattern);

        Dictionary<string, string> states = new Dictionary<string, string>()
        {
           {"AL", "Alabama"},
           {"AK", "Alaska"},
           {"AS",  "American Samoa"},
           {"AZ",  "Arizona"},
           {"AR", "Arkansas"}
        };

        var statePattern =
            @"\b(?:" +
            string.Join(
                "|",
                new[] {
            string.Join("|", states.Keys.Select(x => Regex.Escape(x)).ToArray()),
            string.Join("|", states.Values.ToArray())
        }) +
            @")\b";

        //Console.WriteLine("\n" + statePattern);

        Dictionary<string, string> directionals = new Dictionary<string, string>()
        {
           {"North", "N" },
           {"East", "E" },
           {"South", "S" },
           {"West", "W" },
           {"Northeast", "NE" },
           {"Southeast", "SE" },
           {"Northwest", "NW" },
           {"Southwest", "SW" }
        };

        var directionalPattern =
            string.Join(
                "|",
                new[] {
            string.Join("|", directionals.Keys.ToArray()),
            string.Join("|", directionals.Values.ToArray()),
            string.Join("|", directionals.Values.Select(x => Regex.Replace(x, @"(\w)", @"$1\.")).ToArray())
        });

        //Console.WriteLine("\n" + directionalPattern);

        var zipPattern = @"\d{5}(?:-?\d{4})?";

        //Console.WriteLine("\n" + zipPattern);

        var numberPattern =
            @"(
                ((?<NUMBER>\d+)(?<SECONDARYNUMBER>(-[0-9])|(\-?[A-Z]))(?=\b))    # Unit-attached
                |(?<NUMBER>\d+[\-\ ]?\d+\/\d+)                                   # Fractional
                |(?<NUMBER>\d+-?\d*)                                             # Normal Number
                |(?<NUMBER>[NSWE]\ ?\d+\ ?[NSWE]\ ?\d+)                          # Wisconsin/Illinois
             )";

        //Console.WriteLine("\n" + numberPattern);

        var streetPattern =
            string.Format(
                CultureInfo.InvariantCulture,
                @"
                    (?:
                      # special case for addresses like 100 South Street
                      (?:(?<STREET>{0})\W+
                         (?<SUFFIX>{1})\b)
                      |
                      (?:(?<PREDIRECTIONAL>{0})\W+)?
                      (?:
                        (?<STREET>[^,]*\d)
                        (?:[^\w,]*(?<POSTDIRECTIONAL>{0})\b)
                       |
                        (?<STREET>[^,]+)
                        (?:[^\w,]+(?<SUFFIX>{1})\b)
                        (?:[^\w,]+(?<POSTDIRECTIONAL>{0})\b)?
                       |
                        (?<STREET>[^,]+?)
                        (?:[^\w,]+(?<SUFFIX>{1})\b)?
                        (?:[^\w,]+(?<POSTDIRECTIONAL>{0})\b)?
                      )
                    )
                ",
                directionalPattern,
                suffixPattern);

        //Console.WriteLine("\n" + streetPattern);


        Dictionary<string, string> rangedSecondaryUnits = new Dictionary<string, string>()
        {
            {"APT",  "APARTMENT"},
            {"BLDG", "BUILDING"}, 
            {"DEPT", "DEPARTMENT"}, 
            {"FL",   "FLOOR"}, 
            {"HNGR", "HANGAR"}, 
            {"LOT",  "LOT"}, 
            {"PIER", "PIER"}, 
            {"RM",   "ROOM"}, 
            {"SLIP", "SLIP"}, 
            {"SPC",  "SPACE"}, 
            {"STOP", "STOP"}, 
            {"STE",  "SUITE"}, 
            {"TRLR", "TRAILER"}, 
            {"UNIT", "UNIT"} 
        };
        var rangedSecondaryUnitPattern =
            @"(?<SECONDARYUNIT>" +
            string.Join("|", rangedSecondaryUnits.Keys.ToArray()) +
            @")(?![a-z])";

        //Console.WriteLine("\n" + rangedSecondaryUnitPattern);


        Dictionary<string, string> rangelessSecondaryUnits = new Dictionary<string, string>()
        {
            {"BSMT", "BASEMENT"},
            {"FRNT", "FRONT"},
            {"LBBY", "LOBBY"},
            {"LOWR", "LOWER"},
            {"OFC",  "OFFICE"},
            {"PH",   "PENTHOUSE"},
            {"REAR", "REAR"},
            {"SIDE", "SIDE"},
            {"UPPR", "UPPER"}
        };

        var rangelessSecondaryUnitPattern =
            @"(?<SECONDARYUNIT>" +
            string.Join("|", rangelessSecondaryUnits.Keys.ToArray()) +
            @")\b";

        //Console.WriteLine("\n" + rangelessSecondaryUnitPattern);

        var allSecondaryUnitPattern = string.Format(
            CultureInfo.InvariantCulture,
            @"
                (
                    (:?
                        (?: (?:{0} \W*)
                            | (?<SECONDARYUNIT>\#)\W*
                        )
                        (?<SECONDARYNUMBER>[\w-]+)
                    )
                    |{1}
                ),?
            ",
             rangedSecondaryUnitPattern,
             rangelessSecondaryUnitPattern);

        //Console.WriteLine("\n" + allSecondaryUnitPattern);

        var cityAndStatePattern = string.Format(
            CultureInfo.InvariantCulture,
            @"
                (?:
                    (?<CITY>[^\d,]+?)\W+
                    (?<STATE>{0})
                )
            ",
            statePattern);

        //Console.WriteLine("\n" + cityAndStatePattern);

        var placePattern = string.Format(
            CultureInfo.InvariantCulture,
            @"
                (?:{0}\W*)?
                (?:(?<ZIP>{1}))?
            ",
            cityAndStatePattern,
            zipPattern);

        //Console.WriteLine("\n" + placePattern);

        var addressPattern = string.Format(
            CultureInfo.InvariantCulture,
            @"
                ^
                # Special case for APO/FPO/DPO addresses
                (
                    [^\w\#]*
                    (?<STREETLINE>.+?)
                    (?<CITY>[AFD]PO)\W+
                    (?<STATE>A[AEP])\W+
                    (?<ZIP>{4})
                    \W*
                )
                |
                # Special case for PO boxes
                (
                    \W*
                    (?<STREETLINE>(P[\.\ ]?O[\.\ ]?\ )?BOX\ [0-9]+)\W+
                    {3}
                    \W*
                )
                |
                (
                    [^\w\#]*    # skip non-word chars except # (eg unit)
                    (  {0} )\W*
                       {1}\W+
                    (?:{2}\W+)?
                       {3}
                    \W*         # require on non-word chars at end
                )
                $           # right up to end of string
            ",
            numberPattern,
            streetPattern,
            allSecondaryUnitPattern,
            placePattern,
            zipPattern);

        Console.WriteLine("\n-----------------------------\n\n" + addressPattern);

        var addressRegex = new Regex(
            addressPattern,
            RegexOptions.Compiled |
            RegexOptions.Singleline |
            RegexOptions.IgnorePatternWhitespace);

    }
于 2012-05-22T22:09:36.667 に答える
0

このようにリソースの使用量を徐々に増やしていくと、壊滅的なバックトラッキングが発生します。基本的に、たとえば、この部分のようなものがある場合:

(?<CITY>[^\d,]+?)\W+

...その場合、入力のどの部分がパターンのどの部分に一致するかについてあいまいさが生じます。一致するほとんどすべてのものは、 に\Wも一致する可能性があり[^\d,]ます。最初のパスで入力が一致しない場合、エンジンは戻ってこれら 2 つのグループの異なる順列を試行し、リソースを消費します。

たとえば、入力の「都市」部分の後にたくさんの空白があるとします。[^\d,]+?空白の長い文字列は と の両方に一致する\W+ため、CITY グループに空白が含まれているかどうかは明確ではありません。これらの量指定子の怠惰/貪欲な動作に基づいて、エンジンは都市名のみを に、すべてのスペースをに入れようとします。次に進み、残りの入力と一致させようとします。[^\d,]+?\W+

最初の試行で残りの入力が一致する場合は、問題ありません。しかし、一致が失敗した場合は、戻って再試行する必要があります。今度は、スペースの 1 つが一致し[^\d,]+?、CITY グループの一部としてキャプチャされます。それが失敗すると、2 つのスペースで再試行されます。

通常、これは入れ子になった量指定子 (たとえば のようなもの) で問題になることがわかります([ABC]+)*string.Formatそれが起こっているあなたのパターンには何も見えませんが、すべての呼び出しで何かを逃した可能性があります。私の推測では、これは非常に長いパターンであり、バックトラックする量指定子とオルタネータが非常に多く (および保存するグループが非常に多く) あるため、単一レベルの反復でさえあなたを殺していると思います。ほとんどのパターンに一致する長い入力文字列で最大のパフォーマンス ヒットが得られるに違いありませんが、すべてのパターンには一致しません。

この場合、正規表現をコンパイルするとおそらく役立つので、コンパイルする必要があります。しかし、アプリで一度に 1000 (またはそれ以上) のヒットが発生した場合、それで済むとは思えません。また、多くのバックトラッキングを引き起こし、パフォーマンス面でより大きな打撃を与える特定の入力文字列もあります。私の最大の提案は、パターンのあいまいさを見つけて解決することです。

お互いに似ている*、または近くにある量指定子がたくさんある場所を見つけ、それらの間に明確でオプションではない区切り文字があることを確認します (たとえば、 NUMBER グループからは、 のように、またはより良いパフォーマンスが得られます)。最後に、区切り文字がその隣のトークンと一致しないことを確認してください。でっち上げの例として、空白の長い文字列を入力すると、次のようなものがドラッグされます。+\d+-?\d*\d+(-\d*)?\d+(-\d+)?\b\W+\ \W+

于 2012-05-21T16:42:27.953 に答える