thomaxz.tc Ответов: 1

Функция Бойера Мура по c# - байт, поиск массива более Бойер возвращается в маленький результат


Я реализовал класс BoyerMooore отсюда https://stackoverflow.com/questions/37500629/find-byte-sequence-within-a-byte-array

но это не дает ожидаемых результатов
вот исходный код:

Что я уже пробовал:

Update: one flaw it reads the entire buffer, no matter who much was read with gave to much result, now i get correct 120 on pattern "00" but still only 5 on the 16 bytes pattern which should be 10

Update2: but change a line i get correct for the 16 bytes pattern, and all for 1 - to 16 except the 15 bytes, which I only get 5 from, but should be 10 also.

using System;
using System.Collections.Generic;

namespace Test
{
    /// <summary>
    /// Description of Boyer.
    /// </summary>

    public sealed class BoyerMoore
    {
    readonly byte[] needle;
    readonly int[] charTable;
    readonly int[] offsetTable;

    public BoyerMoore(byte[] needle)
    {
        this.needle = needle;
        this.charTable = makeByteTable(needle);
        this.offsetTable = makeOffsetTable(needle);
    }

    public IEnumerable<int> Search(byte[] haystack,bytesRead) //send with how much was read
    {
        if (needle.Length == 0)
            yield break;

        for (int i = needle.Length - 1; i < bytesRead;) //changed here
        {
            int j;

            for (j = needle.Length - 1; needle[j] == haystack[i]; --i, --j)
            {
                if (j != 0)
                    continue;

                yield return i;
                i += needle.Length - 1;
                break;
            }

            i += Math.Max(offsetTable[needle.Length - 1 - j], charTable[haystack[i]]);
        }
    }

    static int[] makeByteTable(byte[] needle)
    {
        const int ALPHABET_SIZE = 256;
        int[] table = new int[ALPHABET_SIZE];

        for (int i = 0; i < table.Length; ++i)
            table[i] = needle.Length;

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

        return table;
    }

    static int[] makeOffsetTable(byte[] needle)
    {
        int[] table = new int[needle.Length];
        int lastPrefixPosition = needle.Length;

        for (int i = needle.Length - 1; i >= 0; --i)
        {
            if (isPrefix(needle, i + 1))
                lastPrefixPosition = i + 1;

            table[needle.Length - 1 - i] = lastPrefixPosition - i + needle.Length - 1;
        }

        for (int i = 0; i < needle.Length - 1; ++i)
        {
            int slen = suffixLength(needle, i);
            table[slen] = needle.Length - 1 - i + slen;
        }

        return table;
    }

    static bool isPrefix(byte[] needle, int p)
    {
        for (int i = p, j = 0; i < needle.Length; ++i, ++j)
            if (needle[i] != needle[j])
                return false;

        return true;
    }

    static int suffixLength(byte[] needle, int p)
    {
        int len = 0;

        for (int i = p, j = needle.Length - 2; i >= 0 && needle[i] == needle[j]; --i, --j) //cahnge for -1 to -2
            ++len;

        return len;
    }
}

}

Heres the code where make the pattern, save pattern of different length in a jagged array, no error here, pattern saved as intended.

    for(xtel=(bytesRead-1);xtel>=0;xtel--)
    {
        buffz+=buffer[xtel].ToString();
        if(ytel==0)
        {
            Array.Resize(ref pattern,ytel+1);
            pattern[ytel]=new byte[] {buffer[xtel]};
        }
        else
        {
            Array.Resize(ref pattern,ytel+1);
            pattern[ytel]=pattern[ytel-1];
            Array.Resize(ref pattern[ytel],pattern[ytel].Length+1);
            pattern[ytel][(pattern[ytel].Length-1)]=buffer[xtel];


            if(pattern[ytel].Length==31)
            {
                break;
            }
        }
        ytel++;
    }

Since IEnumerable does not have any count it should be count every time:

heres the code where loop through the jagged array and search

      Array.Resize(ref pregz,pattern.Length);

    for(xtel=0;xtel<pattern.Length;xtel++)
    {
        Array.Reverse(pattern[xtel]);

        var searcher = new BoyerMoore(pattern[xtel]);

        foreach (int index in searcher.Search(buffer))
        {
            pregz[xtel]++;
     }
    }


но мой результат гораздо меньше, чем если бы я посчитал в hexeditor проверил, чтобы увидеть шаблон, и этот шаблон был правильным.

Результат, который я получаю из 16 байт скороговорки в методе, равен 41, но при проверке шестнадцатеричным я считаю 82, так что где-то есть ошибка.

Я также проверил, сделав новый файл с примером:

00 00 00 01 00 00 0f a0 00 00 00 03 00 00 00 00

затем скопировал 10 раз в

00 00 00 01 00 00 0f a0 00 00 00 03 00 00 00 00 00 00 00 01 00 00 0f a0 00 00 00 03 00 00 00 00 00 00 00 01 00 00 0f a0 00 00 00 03 00 00 00 00 00 00 00 01 00 00 0f a0 00 00 00 03 00 00 00 00 00 00 00 01 00 00 0f a0 00 00 00 03 00 00 00 00 00 00 00 01 00 00 0f a0 00 00 00 03 00 00 00 00 00 00 00 01 00 00 0f a0 00 00 00 03 00 00 00 00 00 00 00 01 00 00 0f a0 00 00 00 03 00 00 00 00 00 00 00 01 00 00 0f a0 00 00 00 03 00 00 00 00 00 00 00 01 00 00 0f a0 00 00 00 03 00 00 00 00

но получаю странные результаты

как 2008 год для паттерна 00

причем должно быть всего 120

и только 5 для оригинального рисунка который должен быть 10

но исправьте для этого паттерна 10 когда он должен быть 10 03 00 00 00 00

BillWoodruff

Почему бы не опубликовать свои результаты и вопрос в потоке StackOverflow ?

1 Ответов

Рейтинг:
1

Patrice T

Вот пара статей, которые могут представлять интерес:
Объединение поиска строк Бойера-Мура с регулярными выражениями | Dr Dobb's[^]
Более быстрый поиск строк | Dr Dobb's[^]
Бойер-Мур и связанные с ним точные алгоритмы сопоставления строк[^]
Эффективный поиск Бойера-Мура в строках Юникода[^]

Совет: чтобы помочь помощникам, рекомендуется опубликовать фрагмент кода, который является автономным (с основной функцией) и демонстрирует проблему, чтобы мы могли выполнить ваш код.


BillWoodruff

+5

Patrice T

Спасибо.