Быстрый поиск набора элементов

Question

Я пытаюсь найти кучу файлов на жестком диске для двоичного шаблона.Я пытался найти какой-то способ сделать это с помощью встроенного в .net, но я не могу найти ничего, что позволило бы мне искать набор данных вместо одного байта данных, если я не преобразовал свойсначала бинарные данные в строку и использую String.IndexOf(string value).

Я на полпути к написанию собственного алгоритма поиска потока Бойера-Мура, но я подумал, что сначала я должен проверить здесь, если я пропустил способ сделатьэто эффективно.

Вот мой текущий метод поиска только по тексту, он работает достаточно хорошо, я просто не знаю, что делать с двоичными образцами

private string _string;
private byte[] _array;

private void backgroundWorker1_DoWork(object sender, DoWorkEventArgs e)
{
    Parallel.ForEach(Directory.EnumerateFiles(_folder, _filter, SearchOption.AllDirectories)
        , Search);
}

private void Search(string filePath)
{

    if (numbers)
    {
        var fileBinary = File.ReadAllBytes(filePath);
        if (fileBinary.MagicFunctionToDoContains(_array)) //Need help here
        {
            lbResults.BeginInvoke(new Action<string>(AddResult), filePath);
        }
    }
    else
    {
        var fileText = File.ReadAllText(filePath, Encoding.ASCII);
        if (fileText.IndexOf(_string, StringComparison.OrdinalIgnoreCase) >= 0)
        {
            lbResults.BeginInvoke(new Action<string>(AddResult), filePath);
        }
    }
}

Байтмассивы не должны превышать 8 байт в самом большом размере, при этом общий случай составляет 4 байта, если это влияет на рекомендацию.

Есть ли что-то встроенное в .net или предварительно написанный пример, который я мог быиспользовать для этого?

Answer 1

Кодирование алгоритма Бойера-Мура должно быть простым.Тем не менее, для таких коротких шаблонов (4-8 байт) я сомневаюсь, что вы видите значительное повышение производительности по сравнению с побайтовым поиском.

Что вы можете сделать, чтобы повысить производительность, это использовать арифметику указателей с помощью unsafe и fixed ключевых слов, поскольку индексатор массива будет проверять ваши индексные переменные каждый раз, когда вы обращаетесь к массиву fileBinary .

Answer 2

Хотите ли вы искать файлы в том виде, в каком они есть на диске, или вы хотите создать индекс, а затем выполнить поиск по этому индексу?

• Если первый случай таков, я не вижу причины, по которой Бойера-Мура нельзя было реализовать с помощью байтовых "символов".
• Если последним является случай, вам понадобится специальная структура данных, такая как дерево суффиксов.

Кстати, загрузка содержимого всего файла может быть не самой лучшей идеей в отношении производительности - что, если вам случится столкнуться с видеофайлом объемом несколько ГБ? Поскольку все, что вы делаете, - это линейный обход содержимого файла, вы можете загружать его по частям.

Для действительно производительной реализации разделите поиск и загрузку чанка на параллельные потоки (или, еще лучше, TPL Task s) с очередью (чанков) между ними. Может даже быть несколько преимуществ параллельного чтения нескольких файлов для использования собственной очереди команд , реализованной в большинстве современных дисковых контроллеров (но только для механических дисков, SSD не получают преимущества от NCQ).

Answer 3

Я не знаю ничего в .Net Framework, которое будет делать то, что вы пытаетесь сделать, используя byte []. Но я думаю, что простым решением было бы преобразовать каждый байт в char, а затем char [] в строку; поэтому вы должны преобразовать filedata в char [], а затем в строку, а также в данные, которые вы ищете, и затем использовать алгоритмы поиска строк, встроенные в .Net. Это сэкономило бы время на то, чтобы развернуть собственный алгоритм поиска по шаблону, плюс, если данные не велики, издержки должны быть незначительными.