Поиск файла для последовательности байтов (C #) - PullRequest
Новая
       2

Поиск файла для последовательности байтов (C #)

2 голосов
/ 25 ноября 2010

Я пишу приложение на C #, в котором мне нужно найти в файле (может быть очень большой) последовательность байтов, и я не могу использовать какие-либо библиотеки для этого.Итак, мне нужна функция, которая принимает байтовый массив в качестве аргумента и возвращает позицию байта после данной последовательности.Функция не должна быть быстрой, она просто должна работать.Любая помощь будет принята с благодарностью:)

Ответы [ 3 ]

3 голосов
/ 25 ноября 2010

Если вам не нужно быть быстрым, вы можете использовать это: 

int GetPositionAfterMatch(byte[] data, byte[]pattern)
{
  for (int i = 0; i < data.Length - pattern.Length; i++)
  {
    bool match = true;
    for (int k = 0; k < pattern.Length; k++)
    {
      if (data[i + k] != pattern[k])
      {
        match = false;
        break;
      }
    }
    if (match)
    {
      return i + pattern.Length;
    }
  }
}

Но я действительно рекомендую вам использовать алгоритм Кнута-Морриса-Пратта, этот алгоритм в основном используется как основаМетоды IndexOf для строк.Приведенный выше алгоритм будет работать очень медленно, за исключением небольших массивов и небольших шаблонов.

1 голос
/ 25 ноября 2010

Вот фрагмент кода, который я использовал для поиска типа Бойера-Мура. Это значит работать с файлами pcap, поэтому он работает по принципу «запись за записью», но его должно быть достаточно легко изменить, чтобы он подходил только для поиска длинного двоичного файла. Это что-то извлеченное из некоторого тестового кода, так что я надеюсь, что у меня есть все для вас, чтобы следовать. Также поищите в поисках Бойера-Мура в Википедии, поскольку именно на этом она основана. 

int[] badMatch = new int[256];
byte[] pattern;  //the pattern we are searching for

//badMath is an array of every possible byte value (defined as static later).
//we use this as a jump table to know how many characters we can skip comparison on
//so first, we prefill every possibility with the length of our search string
for (int i = 0; i < badMatch.Length; i++)
{
  badMatch[i] = pattern.Length;
}

//Now we need to calculate the individual maximum jump length for each byte that appears in my search string
for (int i = 0; i < pattern.Length - 1; i++)
{
  badMatch[pattern[i] & 0xff] = pattern.Length - i - 1;
}

// Place the bytes you want to run the search against in the payload variable
byte[] payload = <bytes>

// search the packet starting at offset, and try to match the last character
// if we loop, we increment by whatever our jump value is
for (i = offset + pattern.Length - 1; i < end && cont; i += badMatch[payload[i] & 0xff])
{
  // if our payload character equals our search string character, continue matching counting backwards
  for (j = pattern.Length - 1, k = i; (j >= 0) && (payload[k] == pattern[j]) && cont; j--)
  {
    k--;
  }
// if we matched every character, then we have a match, add it to the packet list, and exit the search (cont = false)
  if (j == -1)
  {
    //we MATCHED!!!
    //i = end;
    cont = false;
  }
}
1 голос
/ 25 ноября 2010

Прямой подход, как указывает Туррау, работает, и для ваших целей он, вероятно, достаточно хорош, поскольку вы говорите, что он не должен быть быстрым - тем более, что для большинства практических целей алгоритм намного быстрее худшего случай O (n * m). (В зависимости от вашего рисунка, я думаю).

Для оптимального решения вы также можете проверить алгоритм Кнута-Морриса-Пратта , который использует частичные совпадения, которые в итоге равны O (n + m).

...