Можно ли использовать Google RE2 с потоками? Некоторые входные литералы, которые мы должны обрабатывать с помощью регулярных выражений, потенциально могут быть слишком большими для хранения в памяти.
Регулярные выражения RE2 в потоках?
comment
Я так не думаю. Однако, поскольку это с открытым исходным кодом, взломайте его, чтобы поддерживать это :)
- person mvp   schedule 25.10.2013
Ответы (1)
Если существует максимальная длина совпадения, вы можете считывать данные блоками как минимум вдвое большей длины. Если совпадение не удается или начинается меньше, чем это количество символов с конца, обрежьте текущую строку и добавьте еще один блок.
Длина строки соответствия никогда не будет превышать длину блока + максимальную длину совпадения.
Пример на C#:
public static IEnumerable<StreamMatch> MatchesInStream(
this Regex pattern, TextReader reader,
int maxMatchLength, int blockLength)
{
if (maxMatchLength <= 0)
{
throw new ArgumentException("Must be positive", "maxMatchLength");
}
if (blockLength < maxMatchLength)
{
throw new ArgumentException("Must be at least as long as maxMatchLength", "blockLength");
}
char[] buffer = new char[blockLength];
string chunk = "";
int matchOffset = 0;
// Read one block, and append to the string
int charsRead = reader.ReadBlock(buffer, 0, blockLength);
chunk += new string(buffer, 0, charsRead);
while (charsRead > 0 && chunk.Length > maxMatchLength)
{
int cutPosition = 0;
foreach (Match match in pattern.Matches(chunk))
{
if (match.Index > chunk.Length - maxMatchLength)
{
// The match could possibly have matched more characters.
// Read another block before trying again.
break;
}
yield return new StreamMatch(matchOffset, match);
cutPosition = match.Index + match.Length;
}
cutPosition = Math.Max(cutPosition, chunk.Length - maxMatchLength);
matchOffset += cutPosition;
chunk = chunk.Substring(cutPosition);
charsRead = reader.ReadBlock(buffer, 0, blockLength);
chunk += new string(buffer, 0, charsRead);
}
// Stream has ended. Try to match the last remaining characters.
foreach (Match match in pattern.Matches(chunk))
{
yield return new StreamMatch(matchOffset, match);
}
}
public class StreamMatch
{
public int MatchOffset { get; private set; }
public Match Match { get; private set; }
public StreamMatch(int matchOffset, Match match)
{
MatchOffset = matchOffset;
Match = match;
}
}
// One horrible XML parser
var reader = new StreamReader(stream);
var pattern = new Regex(@"<(/?)([\w:-]{1,15})([^<>]{0,50}(?<!/))(/?)>");
foreach (StreamMatch match in pattern.MatchesInStream(reader, 69, 128))
{
Console.WriteLine(match.Match.Value);
}
person
Markus Jarderot
schedule
25.10.2013
Хорошая идея, но что, если регулярное выражение хочет сопоставить, если оно начинается с этого символа и заканчивается этим символом, например.
/^[x-y](\w*)[x-z]$/
?
- person ; 26.10.2013
Поставьте ограничение диапазона на середину, даже если она большая.
/^[x-y](\w{0,400})[x-z]$/
- person Markus Jarderot; 26.10.2013
Проблема в том, что регулярные выражения генерируются пользователями, поэтому мы не можем предсказать, какие совпадения им нужны. Думаю, единственным способом решить эту проблему будет потоково-ориентированный процессор регулярных выражений. Спасибо хоть.
- person ; 26.10.2013
Ваше решение может давать совпадения, длина которых превышает установленную нами максимальную длину. Нам нужно проверить длину совпадения и уменьшить фрагмент, пока мы не найдем совпадение, длина которого не превышает максимальную длину для него. Алгоритм для этого не кажется тривиальным. Существуют механизмы регулярных выражений, которые поддерживают потоковую передачу. Я думаю, что это возможно без максимальной длины, поскольку все, что вам нужно хранить в памяти, — это начало совпадения и следующая часть шаблона, которая должна быть сопоставлена. Я не думаю, что таким образом можно поддерживать откат, но все же лучше, чем ничего. github.com/google/re2/issues/251
- person inf3rno; 20.03.2020