Есть ли более быстрый способ поиска в огромном файле без его загрузки в память?

Question

У меня есть огромные файлы, которые я не могу позволить себе загружать в память и последовательность байтов, которые мне нужно найти внутри.

Это то, что я использую сейчас:

public static byte[] GetRangeFromStream(ref FileStream fs, long start_index, long count) 
{ 
    byte[] data = new byte[count]; 
    long prev_pos = fs.Position; 
    fs.Position = start_index; 
    fs.Read(data, 0, data.Length); 
    fs.Position = prev_pos; 
    return data; 
} 

public static long GetSequenceIndexInFileStream(byte[] seq, ref FileStream fs, long index, bool get_beginning = true) 
{ 
    if (index >= fs.Length) 
     return -1; 

    fs.Position = index; 

    for (long i = index; i < fs.Length; i++) 
    { 
     byte temp_byte = (byte)fs.ReadByte(); 

     if (temp_byte == seq[0] && IsArraysSame(seq, GetRangeFromStream(ref fs, i, seq.Length))) //compare just first bytes and then compare seqs if needed 
      return i; 
    } 

    return -1; 
} 

Answer 1

Предлагаю использовать модифицированную версию Knuth Moriss Pratt algorithm. алгоритм kmp_search: вход: поток символов, S (текст для поиска) массив символов, W (слово искать) выход: целое (положение с нуля в S, при котором W найден)

define variables: 
    an integer, m ← 0 (the beginning of the current match in S) 
    an integer, i ← 0 (the position of the current character in W) 
    an array of integers, T (the table, computed elsewhere) 

while m + i < length(S) do 
    if W[i] = S[m + i] then 
     if i = length(W) - 1 then 
      return m 
     let i ← i + 1 
    else 
     if T[i] > -1 then 
      let m ← m + i - T[i], i ← T[i] 
     else 
      let m ← m + 1, i ← 0 

(if we reach here, we have searched all of S unsuccessfully) 
return the length of S 

текстовая строка может быть струился, потому что алгоритм KMP не отступиться в тексте. (Это еще одно улучшение по сравнению с наивным алгоритмом, который, естественно, не поддерживает потоковое вещание.) Если потоковая передача, то время амортизации для обработки входящего символа равно Ɵ (1), но наихудшее время - Ɵ (min (m, n ')), где n '- количество текстовых символов, видимых до сих пор. Source

Referecne реализации (Java) можно найти here

package com.twitter.elephantbird.util; 

import java.io.IOException; 
import java.io.InputStream; 
import java.util.Arrays; 

/** 
* An efficient stream searching class based on the Knuth-Morris-Pratt algorithm. 
* For more on the algorithm works see: http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm. 
*/ 
public class StreamSearcher { 

    protected byte[] pattern_; 
    protected int[] borders_; 

    // An upper bound on pattern length for searching. Results are undefined for longer patterns. 
    public static final int MAX_PATTERN_LENGTH = 1024; 

    public StreamSearcher(byte[] pattern) { 
    setPattern(pattern); 
    } 

    /** 
    * Sets a new pattern for this StreamSearcher to use. 
    * @param pattern 
    *   the pattern the StreamSearcher will look for in future calls to search(...) 
    */ 
    public void setPattern(byte[] pattern) { 
    pattern_ = Arrays.copyOf(pattern, pattern.length); 
    borders_ = new int[pattern_.length + 1]; 
    preProcess(); 
    } 

    /** 
    * Searches for the next occurrence of the pattern in the stream, starting from the current stream position. Note 
    * that the position of the stream is changed. If a match is found, the stream points to the end of the match -- i.e. the 
    * byte AFTER the pattern. Else, the stream is entirely consumed. The latter is because InputStream semantics make it difficult to have 
    * another reasonable default, i.e. leave the stream unchanged. 
    * 
    * @return bytes consumed if found, -1 otherwise. 
    * @throws IOException 
    */ 
    public long search(InputStream stream) throws IOException { 
    long bytesRead = 0; 

    int b; 
    int j = 0; 

    while ((b = stream.read()) != -1) { 
     bytesRead++; 

     while (j >= 0 && (byte)b != pattern_[j]) { 
     j = borders_[j]; 
     } 
     // Move to the next character in the pattern. 
     ++j; 

     // If we've matched up to the full pattern length, we found it. Return, 
     // which will automatically save our position in the InputStream at the point immediately 
     // following the pattern match. 
     if (j == pattern_.length) { 
     return bytesRead; 
     } 
    } 

    // No dice, Note that the stream is now completely consumed. 
    return -1; 
    } 

    /** 
    * Builds up a table of longest "borders" for each prefix of the pattern to find. This table is stored internally 
    * and aids in implementation of the Knuth-Moore-Pratt string search. 
    * <p> 
    * For more information, see: http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm. 
    */ 
    protected void preProcess() { 
    int i = 0; 
    int j = -1; 
    borders_[i] = j; 
    while (i < pattern_.length) { 
     while (j >= 0 && pattern_[i] != pattern_[j]) { 
     j = borders_[j]; 
     } 
     borders_[++i] = ++j; 
    } 
    } 
} 

Похожий вопрос: Efficient way to search a stream for a string

Answer 2

Оптимальный способ сделать это, чтобы прочитать файл поток байт в байтах, глядя только на первые байты строки, которую вы ищете. Когда вы получаете матч, вы знаете, что у вас есть возможный удар. Прочитайте следующие N байтов (где N - длина искомой строки) и сравните массив с содержимым байтов, считанных из файла, и искомыми байтами.

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

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

Если файл действительно большой, и вы не I/O Bound, то вы могли бы рассмотреть возможность создания нескольких Задачи назначают библиотеку задач .net, каждая из которых начинается в другом месте в потоке файлов, и корректирует результаты каждой задачи после завершения всех задач.

Answer 3

Вы можете проверить file mapping. Это позволяет по существу обрабатывать большие файлы, как если бы они были буферами памяти, что позволяло использовать любой API на основе памяти на дисковый файл. Никаких проблем с явным файловым вводом-выводом.

MSDN:

отображения файла является объединением содержимого файла с частью виртуального адресного пространства процесса. Система создает объект сопоставления файлов (также известный как объект раздела) для поддержания этой связи. Файл представляет собой часть виртуального адресного пространства, которое процесс использует для доступа к содержимому файла. Сопоставление файлов позволяет процессу использовать как случайные входные и выходные данные (I/O), так и последовательный ввод-вывод.Он также позволяет процессу эффективно работать с большим файлом данных, таким как база данных, без необходимости отображать весь файл в память. Несколько процессов могут также использовать файлы с отображением памяти для обмена данными .... tell me more...