Java: Как найти строковые шаблоны в БОЛЬШОМ двоичном файле?

Question

Я пытаюсь написать программу, которая будет читать ОЧЕНЬ БОЛЬШОЙ двоичный файл и попытаться найти вхождение 2 разных строк, а затем распечатать индексы, соответствующие шаблонам. Для примера давайте предположим, что последовательности символов [H,e,l,l,o] а также [H,e,l,l,o, ,W,o,r,l,d],

Я смог закодировать это для небольших двоичных файлов, потому что я читал каждый символ как байт, а затем сохранял его в Arraylist, Затем, начиная с начала ArraylistЯ сравнивал byte arraylist(byte[] data) с byte[] pattern,

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

Любые предложения о том, как этого можно достичь? Спасибо всем заранее.

Answer 1

Гугл "Конечный автомат".

Или, прочитайте файл по одному байту за раз, если байт просто не соответствует первому символу поискового запроса, переходите к следующему байту. Если он совпадает, теперь вы ищете следующий символ в последовательности. То есть, ваше состояние изменилось с 0 на 1. Если ваше состояние равно (или превышает) длину строки поиска, вы ее нашли!

Реализация / отладка оставлена ​​читателю.

Answer 2

Похоже, вы действительно ищете алгоритм сопоставления строк Aho-Corasick.

Алгоритм строит автомат из заданного вами словаря, а затем позволяет находить совпадения, используя одно сканирование вашей входной строки.

Статья в Википедии ссылается на эту реализацию Java

Answer 3

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

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

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

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

Answer 4

Использовать FileInputStream завернутый в BufferedInputStream и сравнить каждый байт. Сохраните в буфере длину последовательности, которую вы ищете, чтобы вы вернулись, если она не совпадает в какой-то момент. Если искомая последовательность слишком велика, вы можете сохранить смещение и заново открыть файл для чтения.

• Работа с потоками: http://docs.oracle.com/javase/tutorial/essential/io/
• Алгоритмы сопоставления строк: http://en.wikipedia.org/wiki/String_searching_algorithm

Или, если вы просто хотите что-то скопировать и вставить, вы можете посмотреть на этот ТАК вопрос.