搜索在C＃中的字节数组最长模式 [英] Search longest pattern in byte array in C#

问题描述

我需要编写搜索字节数组给定的模式有效和快捷的方法。
我把它写这样一来，你怎么想，如何改善？而且它有一个缺陷，它无法与长度返回匹配1。

I need to write effective and quick method to search byte array for given pattern. I write it this way, what do you think , how to improve? And it has one bug, it cannot return match with length 1.

public static bool SearchByteByByte(byte[] bytes, byte[] pattern)
    {
        bool found = false;
        int matchedBytes = 0;
        for (int i = 0; i < bytes.Length; i++)
        {
            if (pattern[0] == bytes[i] && bytes.Length - i >= pattern.Length)
            {
                for (int j = 1; j < pattern.Length; j++)
                {
                    if (bytes[i + j] == pattern[j])
                    {
                        matchedBytes++;
                        if (matchedBytes == pattern.Length - 1)
                        {
                            return true;
                        }
                        continue;
                    }
                    else
                    {
                        matchedBytes = 0;
                        break;
                    }
                }
            }
        }
        return found;
    }

有什么建议？

推荐答案

这是grep的使用是pretty高效，并获得更长更复杂的尺寸更高效的博耶-Moore算法。我是pretty相信你可以使它成为一个字节数组工作，没有太多的困难，而其的维基百科页面在Java中的实现，应该很容易地移植到C＃。

The Boyer-Moore algorithm that is used in grep is pretty efficient, and gets more efficient for longer pattern sizes. I'm pretty sure you could make it work for a byte array without too much difficulty, and its wikipedia page has an implementation in Java that should be fairly easy to port to C#.

更新：

下面是的博耶-Moore算法在C＃中的字节数组的一个简化版本的实现。它仅使用完整算法的第二跳表。根据你说的（干草堆：2000000字节，针：10个字节）的数组大小，它比简单的字节快约5-8倍字节算法

Here's an implementation of a simplified version of the Boyer-Moore algorithm for byte arrays in C#. It only uses the second jump table of the full algorithm. Based on the array sizes that you said (haystack: 2000000 bytes, needle: 10 bytes), it's about 5-8 times faster than a simple byte by byte algorithm.

    static int SimpleBoyerMooreSearch(byte[] haystack, byte[] needle)
    {
        int[] lookup = new int[256];
        for (int i = 0; i < lookup.Length; i++) { lookup[i] = needle.Length; }

        for (int i = 0; i < needle.Length; i++)
        {
            lookup[needle[i]] = needle.Length - i - 1;
        }

        int index = needle.Length - 1;
        var lastByte = needle.Last();
        while (index < haystack.Length)
        {
            var checkByte = haystack[index];
            if (haystack[index] == lastByte)
            {
                bool found = true;
                for (int j = needle.Length - 2; j >= 0; j--)
                {
                    if (haystack[index - needle.Length + j + 1] != needle[j])
                    {
                        found = false;
                        break;
                    }
                }

                if (found)
                    return index - needle.Length + 1;
                else
                    index++;
            }
            else
            {
                index += lookup[checkByte];
            }
        }
        return -1;
    }

这篇关于搜索在C＃中的字节数组最长模式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！