专栏首页林德熙的博客C# 对 byte 数组进行模式搜索

C# 对 byte 数组进行模式搜索

本文告诉大家几个方法从 byte 数组找到对应的相同序列的数组

最简单的方法是进行数值判断,但是代码最少是使用Linq ,效率比较高是使用 Boyer-Moore 算法,下面就告诉大家几个算法的代码

判断数值

    class ByteArrayRocks
    {
        public static IEnumerable<int> IndexOf(byte[] source, int start, byte[] pattern)
        {
            if (IsEmptyLocate(source, start, pattern))
            {
                yield break;
            }

            for (int i = start; i < source.Length; i++)
            {
                if (!IsMatch(source, i, pattern))
                {
                    continue;
                }

                yield return i;
            }
        }

        private static readonly int[] Empty = new int[0];

        private static bool IsMatch(byte[] array, int position, byte[] candidate)
        {
            if (candidate.Length > (array.Length - position))
            {
                return false;
            }

            for (int i = 0; i < candidate.Length; i++)
            {
                if (array[position + i] != candidate[i])
                {
                    return false;
                }
            }

            return true;
        }

        private static bool IsEmptyLocate(byte[] array, int start, byte[] candidate)
        {
            return array == null
                   || candidate == null
                   || array.Length == 0
                   || array.Length < start
                   || candidate.Length == 0
                   || candidate.Length + start > array.Length;
        }
    }

这是最简单的方法,参见 https://stackoverflow.com/a/283648/6116637

linq

这个方法的代码最少

    class LinqArraySearch
    {
        public static IEnumerable<int> IndexOf(byte[] source, int start, byte[] pattern)
        {
            for (int i = start; i < source.Length; i++)
            {
                if (source.Skip(i).Take(pattern.Length).SequenceEqual(pattern))
                {
                    yield return i;
                }
            }
        }
    }

Boyer-Moore-Horspool 搜索

这是最快的方法

    class BoyerMooreHorspool
    {
        public static IEnumerable<long> IndexesOf(byte[] source, int start, byte[] pattern)
        {
            if (source == null)
            {
                throw new ArgumentNullException(nameof(source));
            }

            if (pattern == null)
            {
                throw new ArgumentNullException(nameof(pattern));
            }

            long valueLength = source.LongLength;
            long patternLength = pattern.LongLength;

            if ((valueLength == 0) || (patternLength == 0) || (patternLength > valueLength))
            {
                yield break;
            }

            var badCharacters = new long[256];

            for (var i = 0; i < 256; i++)
            {
                badCharacters[i] = patternLength;
            }

            var lastPatternByte = patternLength - 1;

            for (long i = 0; i < lastPatternByte; i++)
            {
                badCharacters[pattern[i]] = lastPatternByte - i;
            }

            long index = start;

            while (index <= valueLength - patternLength)
            {
                for (var i = lastPatternByte; source[index + i] == pattern[i]; i--)
                {
                    if (i == 0)
                    {
                        yield return index;
                        break;
                    }
                }

                index += badCharacters[source[index + lastPatternByte]];
            }
        }
    }

参见:https://stackoverflow.com/q/16252518/6116637

测试了三个方法的性能,请看下面

BenchmarkDotNet=v0.10.14, OS=Windows 10.0.17134
Intel Core i7-6700 CPU 3.40GHz (Skylake), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=2.1.202
  [Host]     : .NET Core 2.0.9 (CoreCLR 4.6.26614.01, CoreFX 4.6.26614.01), 64bit RyuJIT
  DefaultJob : .NET Core 2.0.9 (CoreCLR 4.6.26614.01, CoreFX 4.6.26614.01), 64bit RyuJIT

Method

Mean

Error

StdDev

Linq

13,332.8 us

251.782 us

466.694 us

ByteArrayRocks

371.3 us

7.327 us

14.462 us

BoyerMooreHorspool

108.3 us

1.153 us

1.079 us

其他方法请看下面

使用不安全代码的 Boyer Moore 算法 C# High Performance Boyer Moore Byte Array Search Algorithm


本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 软件设计 白话依赖注入

    有很多小伙伴来问依赖注入和如何做一个框架,我说了好久想到下面的故事,所以就写下来。

    林德熙
  • WPF 隐藏系统窗口菜单

    林德熙
  • C# dotnet 将 Stream 保存到文件的方法

    这里的 inputStream.Seek(0, SeekOrigin.Begin); 不一定需要,请根据你自己的需求,如你只需要将这个 Stream 的从第10...

    林德熙
  • java获取当前时间和前一天日期

    似水的流年
  • java获取当前时间和前一天日期

    String basePath = request.getScheme()+"://"+request.getServerName()+":"+request....

    似水的流年
  • java获取当前时间和前一天日期

    String basePath = request.getScheme()+"://"+request.getServerName()+":"+request....

    似水的流年
  • Python日历模块总结

    calendar模块的函数都是日历相关的,提供了对日期的一些操作方法,和生成日历的方法.

    py3study
  • java根据身份证号或生日计算年龄

    有的人可能会问采用异常来处理非法年龄,我在这简单说明,在工作中,我一般会尽量避免异常的发生,毕竟出现了崩溃不是什么好事,特别是在Android开发中。

    JarvanMo
  • 快速了解Electron:新一代基于Web的跨平台桌面技术

    本文引用了作者“ ConardLi”的《用JS开发跨平台桌面应用,从原理到实践》一文部分内容,原文链接:segmentfault.com/a/119000001...

    JackJiang
  • SCI规范作图(Matlab)+简洁干货+源代码+免费

    折线走势图是所有文章必不可少的数据分析直观展现方式,本文以上图为例,以小见大来说明如何用Matlab画出SCI投稿专用单栏图片:线形、标记点、线宽、坐标...

    梁佐佐

扫码关注云+社区

领取腾讯云代金券