Регулярное выражение для огромного блока данных

Question

Регулярное выражение для огромного блока данных

1

У меня была задача обработать большие rtf файлы,> 500Мб. Мне нужно было найти и извлечь части из этих больших файлов.

Это был рабочий прототип, написанный на Java, для демонстрационных целей.

Я создал регулярное выражение, которое работало для небольших файлов rtf (~ 10Мб) и пыталось применить это выражение для огромных файлов.

И я получаю ошибку "Переполнение стека" при выполнении этого регулярного выражения.

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

Правильно ли я понимаю причину?

Willem Van Onsem 10 июль 2014, в 13:19

Источник

3

Нам нужно увидеть ваше регулярное выражение с некоторыми примерами данных, чтобы лучше понять его.
anubhava 10 июль 2014, в 11:16
2

Вы используете язык или текстовый редактор? FWIW, если текстовый редактор EditPad Pro от гуру регулярных выражений Ян Гойваертс имеет замечательное регулярное выражение и обрабатывает файлы в гигабайтах.
zx81 10 июль 2014, в 11:16
0

@anubhava К сожалению, сейчас у меня нет доступа к исходному коду, извините.
user784540 10 июль 2014, в 11:22
0

@zx81 zx81 Я использовал java для создания рабочего прототипа в демонстрационных целях. И Java хорошо работал с небольшими файлами, но создавал переполнение стека на огромных файлах.
user784540 10 июль 2014, в 11:23
1

@RafaelOsipov Потенциально (пожалуйста, не принимайте это лично), ваше регулярное выражение было неэффективным и пропускает места, где могут использоваться атомные группы. PCRE хорошо справляется с оптимизацией своего движка.
Unihedron 10 июль 2014, в 11:25
0

@Unihedron Unihedron хорошая точка зрения, спасибо
user784540 10 июль 2014, в 11:25
1

@Unihedron: регулярное выражение не может быть неэффективным. Он может быть скомпилирован для работы за линейное время ... Здесь вы можете увидеть, как язык программирования обычно обрабатывает регулярные выражения: ivanzuzak.info/noam/webapps/fsm_simulator
Willem Van Onsem 10 июль 2014, в 11:26

Показать ещё 5 комментариев

Теги:

java

regex

1 ответ

Ещё вопросы

Нам нужно увидеть ваше регулярное выражение с некоторыми примерами данных, чтобы лучше понять его.
Вы используете язык или текстовый редактор? FWIW, если текстовый редактор EditPad Pro от гуру регулярных выражений Ян Гойваертс имеет замечательное регулярное выражение и обрабатывает файлы в гигабайтах.
@anubhava К сожалению, сейчас у меня нет доступа к исходному коду, извините.
@zx81 zx81 Я использовал java для создания рабочего прототипа в демонстрационных целях. И Java хорошо работал с небольшими файлами, но создавал переполнение стека на огромных файлах.
@RafaelOsipov Потенциально (пожалуйста, не принимайте это лично), ваше регулярное выражение было неэффективным и пропускает места, где могут использоваться атомные группы. PCRE хорошо справляется с оптимизацией своего движка.
@Unihedron Unihedron хорошая точка зрения, спасибо
@Unihedron: регулярное выражение не может быть неэффективным. Он может быть скомпилирован для работы за линейное время ... Здесь вы можете увидеть, как язык программирования обычно обрабатывает регулярные выражения: ivanzuzak.info/noam/webapps/fsm_simulator

Willem Van Onsem · Accepted Answer · 2014-07-10T09-26-00.000Z

Нет: регулярные выражения не имеют рекурсивного характера. Любой достойный язык просто преобразует такое выражение в конечный конечный автомат. Это означает, что для фильтрации файла размером 10 мегабайт или 500 мегабайт требуется такой же объем памяти (и, как следствие, размер стека). Кроме того, он масштабируется линейно по времени: можно ожидать, что в 50 раз больше времени, чтобы фильтровать файл размером 500 мегабайт, чем один из 10 MiB.

Что вы используете оценщик регулярных выражений? Для файлов grep/sed меньшие или большие файлы не являются проблемой.

Я использовал регулярное выражение в своем Java-коде, чтобы сделать быстрый-грязный рабочий прототип для демонстрационных целей.
Но тогда вы можете показать нам регулярное выражение и уверены, что оно как-то связано с регулярным выражением. Кроме того, конечно, регулярное выражение должно быть синтаксически правильным.
это было правильно и отлично работало с небольшими файлами. Но не удалось на огромных файлах.
Почему вы не можете показать нам регулярное выражение и трассировку стека? Спорить очень сложно без каких-либо данных ...
Это было давно, и сейчас у меня нет доступа к исходному коду. Просто хотел уточнить для себя. Было ли мое предположение правильным или нет. Спасибо :)
Как поклонник ANTLR, я знаю о конечных автоматах, о которых вы говорите, но в движке Java regex определенно есть рекурсия, потому что выполнение этого теста для огромного файла приводит к ошибке переполнения стека.