0

我想在流上实现搜索和替换算法，我将在其中创建一个将源流作为输入的流类，并且 who's read 方法将根据需要从源流中读取并作为流执行搜索/替换正在阅读。这将减轻整个数据集一次加载到内存中的情况，并在非常大的数据集上启用搜索和替换。

为此，我想我将从现有的搜索算法开始，将其调整为流方法，然后调整替换功能。

下面是我改编自在线示例的 Knuth Morris Pratt 实现。有没有人将这样的东西适应流方法？我需要考虑跨读取边界的搜索，我不确定我会怎么做。

/// <summary>
/// The KMP matching algorithm uses degenerating property (SearchPattern having same sub-SearchPatterns appearing more than once in the SearchPattern) 
/// of the SearchPattern and improves the worst case complexity to O(n). The basic idea behind KMP’s algorithm is: whenever we 
/// detect a mismatch (after some matches), we already know some of the characters in the text of the next window. We take 
/// advantage of this information to avoid matching the characters that we know will anyway match. 
/// </summary>
/// <seealso cref="https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/"/>
public class KMPSearch
{
    /// <summary>
    /// Pattern we are looking for
    /// </summary>
    readonly string sSearchPattern_m;

    /// <summary>
    /// Text we are looking in
    /// </summary>
    readonly string sData_m;

    /// <summary>
    /// Index for text
    /// </summary>
    private int iDataPosition_m;
    private int iDataLength_m;

    /// <summary>
    /// Index for search pattern
    /// </summary>
    private int iSearchPatternPosition_m;

    /// <summary>
    /// A proper prefix is prefix with whole string not allowed. For example, prefixes of “ABC” are “”, “A”, “AB” and “ABC”. 
    /// Proper prefixes are “”, “A” and “AB”. Suffixes of the string are “”, “C”, “BC” and “ABC”.
    /// </summary>
    readonly int[] lstLongestProperPrefix_m;

    public KMPSearch(string sSearchPattern, string sData)
    {
        this.sSearchPattern_m = sSearchPattern;
        this.sData_m = sData;
        this.iDataLength_m = sData.Length;

        // create lps that will hold the longest prefix suffix values for SearchPattern             
        this.lstLongestProperPrefix_m = new int[sSearchPattern.Length];

        // Pre-process the SearchPattern (calculate lps array) 
        this.ComputeLPSArray();

        this.iDataPosition_m = 0; // index for txt 
        this.iSearchPatternPosition_m = 0; // index for pat
    }

    /// <summary>
    /// Find next match
    /// </summary>
    /// <returns></returns>
    public int Next()
    {
        int iMatchIndex = -1;

        //We start comparison of pat[iSearchPatternPosition_m] with iSearchPatternPosition_m = 0 with characters of current window of text.
        //We keep matching characters txt[iDataPosition_m] and pat[iSearchPatternPosition_m] and keep incrementing iDataPosition_m and iSearchPatternPosition_m while 
        //pat[iSearchPatternPosition_m] and txt[iDataPosition_m] keep matching.
        while (iDataPosition_m < this.iDataLength_m)
        {
            if (this.sSearchPattern_m[iSearchPatternPosition_m] == this.sData_m[iDataPosition_m])
            {
                iSearchPatternPosition_m++;
                iDataPosition_m++;
            }

            if (iSearchPatternPosition_m == sSearchPattern_m.Length)
            {
                //Console.WriteLine("Found SearchPattern at index %d ", iDataPosition_m - iSearchPatternPosition_m);
                iMatchIndex = iDataPosition_m - iSearchPatternPosition_m;

                iSearchPatternPosition_m = this.lstLongestProperPrefix_m[iSearchPatternPosition_m - 1];
            }

            // mismatch after j matches 
            else if (iDataPosition_m < this.iDataLength_m && this.sSearchPattern_m[iSearchPatternPosition_m] != this.sData_m[iDataPosition_m])
            {
                //When we see a mismatch
                //* We know that characters pat[0..iSearchPatternPosition_m - 1] match with txt[iDataPosition_m-iSearchPatternPosition_m..iDataPosition_m - 1] 
                //  (Note that iSearchPatternPosition_m starts with 0 and increment it only when there is a match).
                //* We also know (from above definition) that lps[iSearchPatternPosition_m - 1] is count of characters of pat[0…iSearchPatternPosition_m - 1] 
                //  that are both proper prefix and suffix.
                //* From above two points, we can conclude that we do not need to match these lps[iSearchPatternPosition_m - 1] characters with 
                //  txt[iDataPosition_m  -iSearchPatternPosition_m..iDataPosition_m - 1] because we know that 
                //  these characters will anyway match. Let us consider above example to understand this.

                // Do not match lps[0..lps[iSearchPatternPosition_m - 1]] characters, 
                // they will match anyway 
                if (iSearchPatternPosition_m != 0)
                {
                    iSearchPatternPosition_m = this.lstLongestProperPrefix_m[iSearchPatternPosition_m - 1];
                }
                else
                {
                    iDataPosition_m = iDataPosition_m + 1;
                }
            }

            if (iMatchIndex > -1)
            {
                return iMatchIndex;
            }
        }
        return iMatchIndex;
    }

    /// <summary>
    /// A proper prefix is prefix with whole string not allowed. For example, prefixes of “ABC” are “”, “A”, “AB” and “ABC”. 
    /// Proper prefixes are “”, “A” and “AB”. Suffixes of the string are “”, “C”, “BC” and “ABC”.
    /// Fills lps for given pattern pat[0..M-1] 
    /// lps[i] = the longest proper prefix of pat[0..i] which is also a suffix of pat[0..i]. 
    /// </summary>
    private void ComputeLPSArray()
    {
        // length of the previous longest prefix suffix 
        int len = 0;

        this.lstLongestProperPrefix_m[0] = 0; // lps[0] is always 0 

        // the loop calculates lps[i] for i = 1 to M-1 
        int i = 1;
        while (i < this.sSearchPattern_m.Length)
        {
            if (this.sSearchPattern_m[i] == this.sSearchPattern_m[len])
            {
                len++;
                this.lstLongestProperPrefix_m[i] = len;
                i++;
            }
            else // (pat[i] != pat[len]) 
            {
                // This is tricky. Consider the example. 
                // AAACAAAA and i = 7. The idea is similar 
                // to search step. 
                if (len != 0)
                {
                    len = this.lstLongestProperPrefix_m[len - 1];

                    // Also, note that we do not increment 
                    // i here 
                }
                else // if (len == 0) 
                {
                    this.lstLongestProperPrefix_m[i] = 0;
                    i++;
                }
            }
        }
    }
}

然后我采用上述算法并将其改装为 Stream。作为概念证明，每次找到搜索模式时，流都会在其 read 方法期间引发一个事件。它目前具有无法跨读取边界进行搜索的限制。所以如果一次读取1024字节，源流的长度为2048字节，则执行两次读取，读取整个流。问题是，如果搜索模式从索引 1000 开始并且长度为 40 字节，则不会找到它。我认为一旦解决了这个问题，实际的替换功能就不会那么困难了。我正在寻找有关如何跨读取边界实现搜索的建议。它可能涉及缓存先前读取的部分。有人知道类似于此的流式实现或建议吗？

public class KMPSearchStream : Stream
{
    public override bool CanRead { get { return true; } }

    public override bool CanSeek => throw new NotImplementedException();

    public override bool CanWrite => throw new NotSupportedException();

    public override long Length => throw new NotSupportedException();

    public override long Position { get => throw new NotImplementedException(); set => throw new NotImplementedException(); }

    public class PatternFoundEventArgs
    {
        public int Index { get; internal set; }
    }

    public delegate void PatternFoundEvent(PatternFoundEventArgs e);

    private Stream strSource_m;

    /// <summary>
    /// Pattern we are looking for
    /// </summary>
    private byte[] searchPattern_m;

    /// <summary>
    /// Text we are looking in
    /// </summary>
    private byte[] data_m;

    /// <summary>
    /// Index for text
    /// </summary>
    private int iDataPosition_m;
    private int iDataLength_m;

    /// <summary>
    /// Index for search pattern
    /// </summary>
    private int iSearchPatternPosition_m;

    /// <summary>
    /// A proper prefix is prefix with whole string not allowed. For example, prefixes of “ABC” are “”, “A”, “AB” and “ABC”. 
    /// Proper prefixes are “”, “A” and “AB”. Suffixes of the string are “”, “C”, “BC” and “ABC”.
    /// </summary>
    readonly int[] lstLongestProperPrefix_m;

    public KMPSearchStream(Stream strSource, byte[] searchPattern)
    {
        if (strSource == null)
        {
            throw new ArgumentNullException(nameof(strSource), "Source stream is null.");
        }
        if (searchPattern == null || searchPattern.Length == 0)
        {
            throw new ArgumentNullException(nameof(searchPattern), "Pattern to find is null or empty.");
        }

        this.strSource_m = strSource;
        this.searchPattern_m = searchPattern;

        // create lps that will hold the longest prefix suffix values for SearchPattern             
        this.lstLongestProperPrefix_m = new int[searchPattern.Length];

        // Pre-process the SearchPattern (calculate lps array) 
        this.ComputeLPSArray();

        this.iDataPosition_m = 0; // index for txt 
        this.iSearchPatternPosition_m = 0; // index for pat
    }

    public event PatternFoundEvent OnPatternFound;

    public override void Flush()
    {
        throw new NotSupportedException();
    }

    public override long Seek(long offset, SeekOrigin origin)
    {
        throw new NotSupportedException();
    }

    public override void SetLength(long value)
    {
        throw new NotSupportedException();
    }

    public override void Write(byte[] buffer, int offset, int count)
    {
        throw new NotSupportedException();
    }

    public override int Read(byte[] buffer, int offset, int count)
    {
        int iRead = this.strSource_m.Read(buffer, offset, count);

        this.iDataPosition_m = 0; // index for txt 
        this.iSearchPatternPosition_m = 0; // index for pat

        this.data_m = buffer;
        this.iDataPosition_m = offset;
        this.iDataLength_m = iRead;

        int iIndex;

        while ((iIndex = this.Next()) > -1)
        {
            this.OnPatternFound(new PatternFoundEventArgs()
            {
                Index = iIndex
            });
        }
        return iRead;
    }

    /// <summary>
    /// A proper prefix is prefix with whole string not allowed. For example, prefixes of “ABC” are “”, “A”, “AB” and “ABC”. 
    /// Proper prefixes are “”, “A” and “AB”. Suffixes of the string are “”, “C”, “BC” and “ABC”.
    /// Fills lps for given pattern pat[0..M-1] 
    /// lps[i] = the longest proper prefix of pat[0..i] which is also a suffix of pat[0..i]. 
    /// </summary>
    private void ComputeLPSArray()
    {
        // length of the previous longest prefix suffix 
        int len = 0;

        this.lstLongestProperPrefix_m[0] = 0; // lps[0] is always 0 

        // the loop calculates lps[i] for i = 1 to M-1 
        int i = 1;
        while (i < this.searchPattern_m.Length)
        {
            if (this.searchPattern_m[i] == this.searchPattern_m[len])
            {
                len++;
                this.lstLongestProperPrefix_m[i] = len;
                i++;
            }
            else // (pat[i] != pat[len]) 
            {
                // This is tricky. Consider the example. 
                // AAACAAAA and i = 7. The idea is similar 
                // to search step. 
                if (len != 0)
                {
                    len = this.lstLongestProperPrefix_m[len - 1];

                    // Also, note that we do not increment 
                    // i here 
                }
                else // if (len == 0) 
                {
                    this.lstLongestProperPrefix_m[i] = 0;
                    i++;
                }
            }
        }
    }

    /// <summary>
    /// Find next match
    /// </summary>
    /// <returns></returns>
    public int Next()
    {
        int iMatchIndex = -1;

        //We start comparison of pat[iSearchPatternPosition_m] with iSearchPatternPosition_m = 0 with characters of current window of text.
        //We keep matching characters txt[iDataPosition_m] and pat[iSearchPatternPosition_m] and keep incrementing iDataPosition_m and iSearchPatternPosition_m while 
        //pat[iSearchPatternPosition_m] and txt[iDataPosition_m] keep matching.
        while (iDataPosition_m < this.iDataLength_m)
        {
            if (this.searchPattern_m[iSearchPatternPosition_m] == this.data_m[iDataPosition_m])
            {
                iSearchPatternPosition_m++;
                iDataPosition_m++;
            }

            if (iSearchPatternPosition_m == searchPattern_m.Length)
            {
                //Console.WriteLine("Found SearchPattern at index %d ", iDataPosition_m - iSearchPatternPosition_m);
                iMatchIndex = iDataPosition_m - iSearchPatternPosition_m;

                iSearchPatternPosition_m = this.lstLongestProperPrefix_m[iSearchPatternPosition_m - 1];
            }

            // mismatch after j matches 
            else if (iDataPosition_m < this.iDataLength_m && this.searchPattern_m[iSearchPatternPosition_m] != this.data_m[iDataPosition_m])
            {
                //When we see a mismatch
                //* We know that characters pat[0..iSearchPatternPosition_m - 1] match with txt[iDataPosition_m-iSearchPatternPosition_m..iDataPosition_m - 1] 
                //  (Note that iSearchPatternPosition_m starts with 0 and increment it only when there is a match).
                //* We also know (from above definition) that lps[iSearchPatternPosition_m - 1] is count of characters of pat[0…iSearchPatternPosition_m - 1] 
                //  that are both proper prefix and suffix.
                //* From above two points, we can conclude that we do not need to match these lps[iSearchPatternPosition_m - 1] characters with 
                //  txt[iDataPosition_m  -iSearchPatternPosition_m..iDataPosition_m - 1] because we know that 
                //  these characters will anyway match. Let us consider above example to understand this.

                // Do not match lps[0..lps[iSearchPatternPosition_m - 1]] characters, 
                // they will match anyway 
                if (iSearchPatternPosition_m != 0)
                {
                    iSearchPatternPosition_m = this.lstLongestProperPrefix_m[iSearchPatternPosition_m - 1];
                }
                else
                {
                    iDataPosition_m = iDataPosition_m + 1;
                }
            }

            if (iMatchIndex > -1)
            {
                return iMatchIndex;
            }
        }
        return iMatchIndex;
    }

}
4

1 回答 1

0

如果我理解正确，目标是扫描正在进行的流并用替换值替换所有出现的掩码，然后再将其转发到输出流。

如果是这样，对系统有一些要求：

  • 只能转发可以证明它不是完整掩码一部分的数据
  • 必须尽快转发数据以将拥塞降至最低

摘要：
本质上，您在转发之前缓冲所有数据。
在每个字符之后，您测试缓冲区是否可以成为掩码的一部分。
如果它不能成为掩码的一部分，则从缓冲区中一个接一个地释放（写入输出）字符，直到缓冲区为空，或者缓冲区可以再次匹配掩码。

代码：
我创建了一个辅助类，基本上就是这样做的。
我不知道它是否实现了你的算法，这只是我编造的。
根据我的测试，它有效，但我不能保证任何事情。
您可以在流类中使用它，只需转发呼叫并接收回调。
通过 Write([...]) 方法转发输入数据，通过输出回调获取输出并定义掩码和替换字符串。它支持刷新和重置。 

using System;
using System.Collections.Generic;

/// <summary>
/// Class that handles replacement of string occurrences that match a mask in a string stream. 
/// </summary>
public class StreamReplacement
{
    private Action<char> output;

    private string mask;

    private string replacement;

    // Buffer for unverified characters
    private readonly List<char> buffer;

    // Current index on the mask for the next character added
    private int maskPosition;

    /// <summary>
    /// All verified characters will be passed to the output
    /// </summary>
    /// <exception cref="System.ArgumentNullException">The output cannot be null.</exception>
    public Action<char> Output
    {
        get => output;
        set => output = value ?? throw new ArgumentNullException();
    }

    /// <summary>
    /// Gets or sets the mask to test for.
    /// </summary>
    /// <exception cref="System.ArgumentException">The mask must contain at least one character.</exception>
    public string Mask
    {
        get => this.mask;
        set
        {
            if (string.IsNullOrEmpty(mask))
            {
                throw new ArgumentException("The mask must contain at least one character.");
            }

            this.mask = value;

            // Clean buffer and throw out characters that can't be part of the mask anymore.
            WriteVerifiedCharactersFromBuffer();
        }
    }

    /// <summary>
    /// Gets or sets the replacement string to output when the mask has been encountered.
    /// </summary>
    public string Replacement
    {
        get => replacement;
        set => replacement = value ?? string.Empty;
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="StreamReplacement"/> class.
    /// </summary>
    /// <param name="output">The output.</param>
    /// <param name="mask">The mask.</param>
    /// <param name="replacement">The replacement string for mask encounters.</param>
    /// <exception cref="System.ArgumentNullException">Output cannot be null.</exception>
    /// <exception cref="System.ArgumentException">The mask must contain at least one character.</exception>
    public StreamReplacement(Action<char> output, string mask, string replacement)
    {
        this.output = output ?? throw new ArgumentNullException(nameof(output));
        this.mask = string.IsNullOrEmpty(mask) ? throw new ArgumentException("The mask must contain at least one character.") : mask;
        this.replacement = replacement ?? string.Empty;
        this.buffer = new List<char>(mask.Length);
    }

    /// <summary>
    /// Writes a single character to the stream.
    /// </summary>
    public void Write(char c)
    {
        WriteCharacter(c);
    }

    /// <summary>
    /// Writes the specified text to the stream.
    /// </summary>
    public void Write(string text)
    {
        if (string.IsNullOrEmpty(text))
        {
            return;
        }

        foreach (var c in text)
        {
            WriteCharacter(c);
        }
    }

    /// <summary>
    /// Writes the specified characters to the stream.
    /// </summary>
    /// <param name="characters">The characters.</param>
    public void Write(params char[] characters)
    {
        if (characters == null)
        {
            return;
        }

        foreach (var c in characters)
        {
            WriteCharacter(c);
        }
    }

    /// <summary>
    /// Flushes all buffered characters, even if they could be part of the mask.<br/>
    /// Starts from scratch after flushing.
    /// </summary>
    public void Flush()
    {
        foreach (var c in buffer)
        {
            output(c);
        }

        buffer.Clear();
        maskPosition = 0;
    }

    /// <summary>
    /// Clears the buffer without writing any buffered data to the output stream.
    /// </summary>
    public void Reset()
    {
        buffer.Clear();
        maskPosition = 0;
    }

    /// <summary>
    /// Writes the character either to the buffer or output stream and handles masking.
    /// </summary>
    private void WriteCharacter(char c)
    {
        if (mask[maskPosition] == c)
        {
            AddUnverifiedCharacter(c);
        }
        else
        {
            buffer.Add(c);
            WriteVerifiedCharactersFromBuffer();
        }
    }

    /// <summary>
    /// Stores a character in the buffer that could be part of the mask.
    /// </summary>
    private void AddUnverifiedCharacter(char c)
    {
        buffer.Add(c);
        maskPosition++;

        if (maskPosition == mask.Length)
        {
            buffer.Clear();
            maskPosition = 0;

            foreach (var repChar in replacement)
            {
                output(repChar);
            }
        }
    }

    /// <summary>
    /// Writes characters that cannot be part of the mask to the output.
    /// </summary>
    private void WriteVerifiedCharactersFromBuffer()
    {
        // Find possible new start position in buffer
        var newStart = 0;

        for (; newStart < buffer.Count; newStart++)
        {
            if (IsBufferPartOfMask(newStart))
            {
                WritePartOfBuffer(newStart);
                buffer.RemoveRange(0, newStart);
                maskPosition = buffer.Count;
                return;
            }
        }

        WritePartOfBuffer(buffer.Count);
        buffer.Clear();
        maskPosition = 0;
    }

    /// <summary>
    /// Determines whether the buffer content can be part of the mask, starting at the given index.
    /// </summary>
    private bool IsBufferPartOfMask(int offset)
    {
        for (var i = 0; i < buffer.Count - offset; i++)
        {
            var c = buffer[offset + i];
            if (c != mask[i])
            {
                return false;
            }
        }

        return true;
    }

    /// <summary>
    /// Writes the beginning part of buffer to the output
    /// </summary>
    private void WritePartOfBuffer(int count)
    {
        for (var i = 0; i < count; i++)
        {
            output(buffer[i]);
        }
    }
}
于 2019-07-23T20:56:50.333 回答