Быстрое регулярное выражение, которое проверяет, сколько раз символ появляется в строке в Vim?

829
drapkin11

Предположим, у меня есть текстовый файл с разделителями. Я подозреваю, что один из столбцов может иметь встроенный символ канала ('|'). Я знаю, что в файле 8 столбцов, и в каждой строке должны быть 8-1 = 7символы канала. Следовательно, мне нужно найти все строки, которые имеют 8 или более '|' персонажи.

Следующее регулярное выражение должно найти все такие случаи, но это займет слишком много времени, чтобы вернуться в мой файл с 200 000 записей:

^\(.*|.*\)\$ 

Есть ли более быстрое регулярное выражение, которое я должен использовать вместо этого? Под слишком длинным я подразумеваю больше, чем я ожидал - по крайней мере, несколько минут. Это не такой большой файл (200К записей), поэтому я предполагаю, что само регулярное выражение просто неэффективно.


Некоторые примеры данных:

SAMPLE_ID|GROUPS|ADDRESSSTRING|LATITUDE|LONGITUDE|COUNTRYCODE|LANGUAGECODE|ISO_2_LTR_CODE 7304094||Rhein-Galerie;Baden-Württemberg|49.48334|8.45007|DEU|ger|DE 7303851||Steigenberger Insel;Baden-Württemberg|47.69005|9.18812|DEU|ger|DE 7303850||Si-Suites;Baden-Württemberg|48.72309|9.16138|DEU|ger|DE 

(Я запускаю gVim на WinXP)

1
[Крис Джонсен] (http://superuser.com/questions/264213/fast-regular-expression-that-checks-the-number-of-times-a-character-appears-on-a/264292#264292) ' Регулярное выражение s возвращает совпадения за 1 секунду. [Celebdor] (http://superuser.com/questions/264213/fast-regular-expression-that-checks-the-number-of-times-a-character-appears-on-a/264225#264225) 'ы регулярное выражение возвращает совпадения через 1 минуту. Мое оригинальное регулярное выражение вернулось * значительно * позже. drapkin11 13 лет назад 0

2 ответа на вопрос

2
Chris Johnsen

Ваше регулярное выражение склонно сталкиваться с некоторым O (N ^ 2) поведением движка регулярных выражений «backtracking», используемого в Vim (и многих других языках и средах).

К счастью, есть способы написать эквивалентные выражения, которые не вызывают чрезмерного возврата. Например:

/^\([^|]*|\)\.*$ 

Как правило, вам не нужно сопоставлять «восемь или более», поскольку, если вы уже знаете, строка является проблематичной, если у нее восемь (независимо от того, имеет она больше или нет).

Если вам действительно нужно сопоставить всю строку (например, потому что она является частью :sоперации), то вам нужно будет оставить последнюю часть ( .*$); если вы просто используете регулярное выражение, чтобы найти «восемь или более» строк, то вы можете оставить .*$конец.

Кроме того, я советую только пытаться сопоставить одну «сторону» трубы внутри группы, которую вы повторяете. Это упрощает как размышления о том, как регулярное выражение сопоставляет строки, так и о том, как выполняется сам механизм регулярного выражения (это устраняет источник обратного отслеживания).


Теперь, чтобы объяснить немного о «возврате». Предположим, у вас есть строка с восемью символами канала:

aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh 

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

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

 aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* | 

Самое последнее «сжатое» совпадение отбрасывает биты своего совпадения и снова пытается выполнить остальное регулярное выражение. Это происходит по одному символу за раз в этом случае (так как .будет соответствовать любому отдельному символу). Этот возврат продолжается до тех пор, пока не совпадет остальная часть выражения (или пока он не вернется к началу - это единственный способ узнать, что строка не соответствует выражению!).

 aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.* )(.*| 

Таким образом, первый .*отступил достаточно, чтобы позволить остальным групповым матчам, но не было ничего для второй группы, чтобы соответствовать. Пора отступить еще немного.

 aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.* )(.*| 

Отступление нашло новую точку «остановки», но теперь второй .*в первой группе делает жадное сопоставление. Вторая группа не соответствует. Откат второго .*в первой группе начинается.

 aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.*)(.*|.* )(.*| 

Вторая группа нашла совпадение, но третья группа не совпала. Снова вернитесь назад, начиная с более позднего матча. Второй .*из второй группы отступает, чтобы вернуться ни к чему. Первая .*из второй группы отступает ни к чему. Второй .*из первой группы отступает ни к чему. Первый .*из первой группы возвращается успешно.

 aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.* )(.*| 

Но опять же, вторая .*жадная, поэтому она не оставляет ничего для второй группы.

 aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.* )(.*|.* )(.*| aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.*)(.*|.*)(.*|.* )(.*| 

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

 aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.* )(.*| aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.* )(.*|.* )(.*| aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.* )(.*|.*)(.*|.* )(.*| aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.*)(.*|.*)(.*|.*)(.*|.* )(.*| 

Вы можете видеть, как это сжигает много времени (на диаграммах даже пропускается обратный отбор за символом, который на самом деле происходит; только «высокие точки» показаны выше). Проблема возникает из-за того, что более ранний фрагмент регулярного выражения жадно сопоставляется с чем-то, что в конечном итоге должна будет соответствовать более поздняя часть регулярного выражения, чтобы получить правильное количество повторений группы.

В моем выражении каждый repetition ( [^|]*) никогда не совпадает ни с чем, что бы соответствовал следующему элементу ( |), поэтому обратное отслеживание является чисто линейным. Как только обратное отслеживание начинается для каждого «сжатого» совпадения, оно (в линейное время) обнаружит, что не существует более ранних мест, где может соответствовать следующее выражение; это вынуждает вернуться к предыдущему «усадочному» совпадению, пока ничто не совпадет, и вся линия не будет решена как несоответствующая.

Вместо «ноль или более не труба, а труба» ( [^|]*|) также можно использовать .с явно не жадным повторением ( \{-}в Vim, но оно варьируется; другие языки регулярного выражения используют *?).

^\(.\{-}|\)\.*$ 
Это отличное объяснение - спасибо! drapkin11 13 лет назад 0
1
celebdor

Ну, в моем компьютере это быстрее:

:%s/\(|.\{-}\)\//n 
Да, то же самое на моем компьютере. Это регулярное выражение делает феноменально лучшую работу. drapkin11 13 лет назад 0

Похожие вопросы