Эффективный способ поиска потока для строки

Question

Давайте предположим, что у вас есть поток текста (или Reader на Java), который я хотел бы проверить на наличие определенной строки. Поток текста может быть очень большим, поэтому, как только строка поиска будет найдена, я хотел бы вернуть значение true, а также попытаться избежать сохранения всего ввода в памяти.

Наивно, я мог бы попытаться сделать что-то вроде этого (на Java):

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
    char[] buffer = new char[1024];
    int numCharsRead;
    while((numCharsRead = reader.read(buffer)) > 0) {
        if ((new String(buffer, 0, numCharsRead)).indexOf(searchString) >= 0)
            return true;
    }
    return false;
}

Конечно, это не может обнаружить данную строку поиска, если это происходит на границе буфера 1k:

Поиск текста: "stackoverflow"
Потоковый буфер 1: «abc ......... стек»
Потоковый буфер 2: «переполнение ....... xyz»

Как я могу изменить этот код так, чтобы он правильно находил заданную строку поиска через границу буфера, но без загрузки всего потока в память?

Редактировать: Обратите внимание, что при поиске строки для потока мы пытаемся минимизировать количество операций чтения из потока (чтобы избежать задержки в сети / диске) и сохранить постоянную загрузку памяти независимо от объема данных в потоке. Фактическая эффективность алгоритма сопоставления строк является вторичной, но, очевидно, было бы неплохо найти решение, которое использовало бы один из наиболее эффективных из этих алгоритмов.

Answer 1

Реализация раздвижного окна. Переместите свой буфер, переместите все элементы в буфере на один шаг вперед и введите один новый символ в буфер в конце. Если буфер равен вашему искомому слову, он содержится.

Конечно, если вы хотите сделать это более эффективным, вы можете найти способ предотвратить перемещение всех элементов в буфере, например, с помощью циклического буфера и представления строк, которые "циклически повторяются" как это делает буфер, так что вам нужно только проверить на равенство содержимого. Это сохраняет перемещение всех элементов в буфере.

Answer 2

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

Answer 3

У меня также была похожая проблема: пропуск байтов из InputStream до указанной строки (или байтового массива). Это простой код, основанный на круговом буфере. Это не очень эффективно, но работает для моих нужд:

  private static boolean matches(int[] buffer, int offset, byte[] search) {
    final int len = buffer.length;
    for (int i = 0; i < len; ++i) {
      if (search[i] != buffer[(offset + i) % len]) {
        return false;
      }
    }
    return true;
  }

  public static void skipBytes(InputStream stream, byte[] search) throws IOException {
    final int[] buffer = new int[search.length];
    for (int i = 0; i < search.length; ++i) {
      buffer[i] = stream.read();
    }

    int offset = 0;
    while (true) {
      if (matches(buffer, offset, search)) {
        break;
      }
      buffer[offset] = stream.read();
      offset = (offset + 1) % buffer.length;
    }
  }

Answer 4

Если вы ищете постоянную подстроку, а не регулярное выражение, я бы порекомендовал Бойера-Мура. В Интернете много исходного кода.

Кроме того, используйте кольцевой буфер, чтобы не слишком задумываться о границах буфера.

Mike.

Answer 5

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