Регулярные выражения RE2 в потоках?

Можно ли использовать Google RE2 с потоками? Некоторые входные литералы, которые мы должны обрабатывать с помощью регулярных выражений, потенциально могут быть слишком большими для хранения в памяти.


person Community    schedule 24.10.2013    source источник
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
comment
Хорошая идея, но что, если регулярное выражение хочет сопоставить, если оно начинается с этого символа и заканчивается этим символом, например. /^[x-y](\w*)[x-z]$/ ? - person ; 26.10.2013
comment
Поставьте ограничение диапазона на середину, даже если она большая. /^[x-y](\w{0,400})[x-z]$/ - person Markus Jarderot; 26.10.2013
comment
Проблема в том, что регулярные выражения генерируются пользователями, поэтому мы не можем предсказать, какие совпадения им нужны. Думаю, единственным способом решить эту проблему будет потоково-ориентированный процессор регулярных выражений. Спасибо хоть. - person ; 26.10.2013
comment
Ваше решение может давать совпадения, длина которых превышает установленную нами максимальную длину. Нам нужно проверить длину совпадения и уменьшить фрагмент, пока мы не найдем совпадение, длина которого не превышает максимальную длину для него. Алгоритм для этого не кажется тривиальным. Существуют механизмы регулярных выражений, которые поддерживают потоковую передачу. Я думаю, что это возможно без максимальной длины, поскольку все, что вам нужно хранить в памяти, — это начало совпадения и следующая часть шаблона, которая должна быть сопоставлена. Я не думаю, что таким образом можно поддерживать откат, но все же лучше, чем ничего. github.com/google/re2/issues/251 - person inf3rno; 20.03.2020