Выполнение регулярных выражений занимает очень много времени

Question

Я написал регулярное выражение, которое разбирает путь к файлу в другую группу (DRIVE, DIR, FILE, EXTENSION).

^((?<DRIVE>[a-zA-Z]):\\)*((?<DIR>[a-zA-Z0-9_]+(([a-zA-Z0-9_\s_\-\.]*[a-zA-Z0-9_]+)|([a-zA-Z0-9_]+)))\\)*(?<FILE>([a-zA-Z0-9_]+(([a-zA-Z0-9_\s_\-\.]*[a-zA-Z0-9_]+)|([a-zA-Z0-9_]+))\.(?<EXTENSION>[a-zA-Z0-9]{1,6})$))

Я сделал тест на C #.Когда путь, который я хочу проверить, является правильным.Результат очень быстрый, и это то, чего я хотел ожидать.

string path = @"C:\Documents and Settings\jhr\My Documents\Visual Studio 2010\Projects\FileEncryptor\Dds.FileEncryptor\Dds.FileEncryptor.csproj";

=> OK

Но когда я пытаюсь проверить путь, который, как я знаю, не будет совпадать, например,this:

string path = @"C:\Documents and Settings\jhr\My Documents\Visual Studio 2010\Projects\FileEncryptor\Dds.FileEncryptor\Dds.FileEncryptor?!??????";

=> BUG

Тест останавливается, когда я вызываю эту часть кода

Match match = s_fileRegex.Match(path);

Когда я смотрю в свой Process Explorer, я вижупроцесс QTAgent32.exe висит на 100% моего процессора.Что это значит?

Answer 1

Проблема, с которой вы сталкиваетесь, называется катастрофическим возвратом и связана с большим количеством способов, которыми регулярное выражение может сопоставить начало строки, что дает низкую производительность из-за механизма обратного отслеживания регулярного выраженияв .NET.

Я думаю, что вы используете * слишком часто в своем регулярном выражении.* не означает «конкатенация» - это означает «0 или более раз».Например, здесь не должно быть *:

((?<DRIVE>[a-zA-Z]):\\)*

Должна быть не более одной спецификации привода.Вместо этого вы должны использовать ?, иначе квантификатор вообще не требуется, если вы хотите, чтобы спецификация привода была обязательной.Точно так же в вашем регулярном выражении есть и другие места, где квантор неверен.

Answer 2

Марк Байерс прав в том, что причиной проблемы является катастрофическое возвращение назад , однако проблема возникает из-за последней части, а не бит, который соответствует букве диска.

Например, в

(?<FILE>
  ([a-zA-Z0-9_]+
    (
      ([a-zA-Z0-9_\s_\-\.]*[a-zA-Z0-9_]+)
    |
      ([a-zA-Z0-9_]+)
    )\.
    (?<EXTENSION>[a-zA-Z0-9]{1,6})
  $)
)

вы можете видеть, что

([a-zA-Z0-9_\s_\-\.]*[a-zA-Z0-9_]+)
|
([a-zA-Z0-9_]+)

может соответствовать одной и той же строке несколькими различными способами, которые будут экспоненциально увеличиваться с длиной имени файла.

Когда случается, что часть расширения регулярного выражения не совпадает, движок регулярного выражения возвращает и пробует другую перестановку для части имени файла, надеясь, что это позволяет части расширения соответствовать - что, конечно, никогда не будет, но двигатель регулярных выражений не может понять это. RegexBuddy , когда его просят проверить регулярное выражение по указанному вами пути, прерывает попытку сопоставления после 1.000.000 итераций. Движок регулярных выражений C # будет работать до тех пор, пока не исчерпает все перестановки, в течение этого времени процессор будет удерживать 100%.

Чтобы это исправить, как правило, необходимо избегать повторений повторяющихся элементов, избегать чередований, которые соответствуют одним и тем же вещам, и, возможно, заключать части совпадения в атомные группы , которые не будут возвращены, если более поздняя часть регулярного выражения терпит неудачу.

В вашем случае, однако, лучше использовать правильные инструменты для работы, и это функции манипуляции путями .NET.

Answer 3

Почему бы просто не использовать функции System.IO.Path?

• Привод: http://msdn.microsoft.com/en-us/library/system.io.path.getpathroot.aspx

• Справочник: http://msdn.microsoft.com/en-us/library/system.io.path.getdirectoryname.aspx минус что получено для Drive

• Имя файла: http://msdn.microsoft.com/en-us/library/system.io.path.getfilenamewithoutextension.aspx

• Расширение: http://msdn.microsoft.com/en-us/library/system.io.path.getextension.aspx

Answer 4

Я бы просто использовал классы FileInfo и Path для получения информации.

Если вы решите использовать регулярное выражение, затем обратите внимание, что регулярное выражение не соответствует всем допустимым именам файлов: в вашем регулярном выражении отсутствует целая куча допустимых маркеров имен файлов.