оригинал:Говоря о принципе регулярных выражений | AlloyTeam
автор:TAT.liberty
Регулярные выражения могут использоваться большинством людей, но каждый при использовании регулярных выражений не задумывался о принципах, лежащих в основе, или, когда я говорю вам, что регулярное выражение может привести к проблемам с производительностью, повесить линию, вы не будете особенно удивлены ?
Давайте сначала рассмотрим пример онлайн-аварии в начале июля из-за регулярного выражения.
blog.cloudflare.com/details-of-…
Проще говоря, это регулярное выражение с проблемами производительности, вызывающее катастрофический возврат, вызывающий полную загрузку ЦП.
Регулярное выражение для проблем с производительностью
Сначала рассмотрим проблему
Ключевой частью, вызывающей проблемы с производительностью, является.*(?:.*=.*), здесь мы игнорируем незахватывающую группу и рассматриваем регулярность проблемы производительности как.*.*=.*.
в.Указывает на совпадение с любым символом, кроме символа новой строки (многие делают здесь ошибку, что чревато ошибками),.*Указывает на жадное совпадение любого символа любое количество раз.
что такое откат
При использовании жадного сопоставления или ленивого сопоставления или сопоставления для входа в выбор пути сопоставления возникает неудачный сопоставление пути и предпринимается попытка выбрать другой совпадающий путь.Это поведение называется поиском с возвратом.
Это можно понимать как пройти лабиринт, пройти одну дорогу до конца и обнаружить, что пути нет, затем вернуться к последней развилке и выбрать другую дорогу.
отступление
// 性能问题正则
// 将下面代码粘贴到浏览器控制台运行试试
const regexp = `[A-Z]+\\d+(.*):(.*)+[A-Z]+\\d+`;
const str = `A1:B$1,C$1:D$1,E$1:F$1,G$1:H$1`
const reg = new RegExp(regexp);
start = Date.now();
const res = reg.test(str);
end = Date.now();
console.log('常规正则执行耗时:' + (end - start))
Теперь давайте посмотрим, что происходит с возвратом
Допустим, у нас есть обычный(.*)+\d, на этот раз входная строкаabcd, обратите внимание, что в данный момент вводится только строка длины 4, давайте проанализируем процесс сопоставления бэктрекинга:
Выше показан процесс сопоставления с возвратом, примерно описывающий первые три раунда сопоставления.
Уведомление(.*)+Здесь это можно расценивать как множественные казни на данный момент..*.(.*){1,}
первый матч, потому что.*Может соответствовать любому количеству символов любое количество раз, затем вы можете выбрать соответствие пустым, a, ab, abc, abcd, потому что*жадное свойство , поэтому.*прямое соответствиеabcd4 персонажа,+Потому что позади нет других персонажей, так что просто посмотрите на.*съестьabcdПосле этого не совпадает, запишите сюда+равно 1, то\dНичего не совпадает, поэтому совпадение завершается ошибкой, и выполняется первый возврат.
Второе совпадение, потому что был выполнен поиск с возвратом, поэтому, когда был выбран последний совпадающий путь, последний раз.*Спичкиabcd, а дорога не работает, так что на этот раз можно только попытаться сопоставитьabc, на этот раз есть еще один в концеd, то его можно понимать как.*первый матчabc, то потому что(.*)+причина,.*Второй матч можно сделать, здесь.*Может совпадатьd, записано здесь+равно 2, то\dНичего не совпадает, поэтому совпадение не удается, и происходит второй возврат.
Для третьего совпадения, поскольку был выполнен возврат, когда был выбран последний совпадающий путь, первый.*Спичкиabc,второй.*Спичкиdи дорога заблокирована, поэтому вот вторая.*Не совпадают, на этот раз один в концеd,\dа такжеdСопоставление не удается, и выполняется третий возврат.
Как уменьшить или избежать возврата
- Оптимизация регулярных выражений: помните о влиянии на производительность, вызванном поиском с возвратом.
- Регулярные выражения с использованием регулярного механизма DFA
Что такое штатный двигатель DFA
Традиционные регулярные движки делятся на NFA (недетерминированные конечные автоматы) и DFA (детерминированные конечные автоматы).
DFA
Для любого заданного состояния и входного символа DFA будет переходить только в определенное состояние. А DFA не позволяет переходить между состояниями без входных символов.
Например, в состоянии 0, когда вводится символ А, есть только одна конечная точка, и достигается только состояние 1.
NFA
Для любого входного символа и состояния переход состояния может быть NFA непустым набором.
Например, в состоянии 0, когда вводится символ А, может быть несколько конечных точек, то есть он может перейти в состояние 1 или состояние 0.
Отличие штатного двигателя DFA от NFA
Итак, после стольких разговоров, в чем разница между обычными двигателями DFA и NFA? Или как DFA и NFA реализуют обычные двигатели?
DFA
Механизм DFA в регулярном выражении фактически преобразует регулярное выражение в список смежности графа, а затем оценивает, соответствует ли строка регулярному выражению в форме списка пропуска.
// 大概模拟一下
function machine(input) {
if (typeof input !== 'string') {
console.log('输入有误');
return;
}
// 比如正则：/abc/ 转换成DFA之后
// 这里我们定义了4种状态，分别是0,1,2,3，初始状态为0
const reg = {
0: {
a: 1,
},
1: {
b: 3,
},
2: {
isEnd: true,
},
3: {
c: 2,
},
};
let status = 0;
for (let i = 0; i < input.length; i++) {
const inputChar = input[i];
status = reg[status][inputChar];
if (typeof status === 'undefined') {
console.log('匹配失败');
return false;
}
}
const end = reg[status];
if (end && end.isEnd === true) {
console.log('匹配成功');
return true;
} else {
console.log('匹配失败');
return false;
}
}
const input = 'abc';
machine(input);
Преимущества: каким бы плохим ни было регулярное выражение, скорость сопоставления очень высока.
Минусы: расширенные функции, такие как захват групп и утверждений, не поддерживаются.
NFA
Механизм NFA в регулярке на самом деле представляет собой ориентированный граф, построенный в процессе разбора грамматики. Затем путем глубокого перебора выполняется рекурсивная попытка пути и пути.
Преимущества: Мощные, могут получить соответствующую контекстную информацию, поддерживать различные функции, такие как Group Group Assertion
Недостатки: необходимо обратить внимание на высокие требования к регулярным навыкам разработки и проблемы с производительностью, вызванные возвратом.
Суммировать
Теперь вернемся к началу проблемы, давайте посмотрим, почему у его регуляра проблемы с производительностью.
- Во-первых, его регулярность использует обычный движок NFA (обычный движок большинства языков — NFA, как и js, так что обратите внимание на влияние проблем с производительностью)
- Он писал регулярные выражения с проблемами производительности, склонными к катастрофическим возвратам.
Если вы хотите избежать таких проблем, вы можете либо повысить осведомленность разработчиков о проблемах производительности регуляризации, либо вместо этого использовать механизм регуляризации DFA (быстрый, слабый, без захвата групповых утверждений и т. д.).
Меры предосторожности
При написании регулярных выражений пишите меньше нечетких сопоставлений, и чем точнее, тем лучше. Нечеткое сопоставление, жадное сопоставление и ленивое сопоставление принесут проблемы с возвратом. Хорошо выбрать метод, который оказывает как можно меньшее влияние. Просто имейте в виду проблемы с производительностью при написании регулярных выражений.
Советы: раньше я использовал js для написания обычного движка dfa, заинтересованные студенты могут посмотреть:GitHub.com/liberty найти…
AlloyTeam приглашает отличных друзей присоединиться к нам.
Возобновление доставки:Alloyteam@qq.com
Для получения подробной информации, нажмитеTencent AlloyTeam набирает веб-дизайнеров (социальный набор)