Java: читать содержимое ввода файла и фильтровать его, если найдены некоторые последовательности шаблонов строк

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

Итак, у меня есть входной файл, содержащий сотни тысяч строк. Если во входном файле встречается следующая последовательность из 3 строк:
A
B
C

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

Например:
Входной файл:

A
A
B
C
B
P
A
B
C
A
B
A
A
B
C
A

Выходной файл:
A
B
P
A
B
A
A

Уточнение:
A
A (пропущено)
B (пропущено)
C (пропущено)
B
P
A (пропущено)
B (пропущено)< br> C (пропущено)
A
B
A
A (пропущено)
B (пропущено)
C (пропущено)
A

Обратите внимание, что я могу пропустить последовательность строк (A, B, C), только если они идут последовательно. Все остальные строки, которые не пропущены, должны быть скопированы в выходной файл. Если я использую BufferedReader.nextLine(), я не могу вернуться к предыдущим строкам, если следующая строка не соответствует входному шаблону. Например, если я уже встречаю A, а следующая строка — это другая A (не B), тогда мне нужно скопировать первую A в выходной файл и снова начать фильтрацию со второй A, которую я не обработал, и проверьте следующую строку и так далее.

Один из способов, который я могу придумать, - это сначала сохранить содержимое входного текстового файла, чтобы я мог легко вернуться назад при просмотре содержимого входного файла, если он не соответствует шаблону, который я ищу. Однако это не решение для памяти. Есть ли какой-нибудь умный алгоритм для решения этого, желательно за один раз, т.е. сложности O (N)? Или, если это невозможно, какое решение было бы наиболее оптимальным, которое по-прежнему зависит от памяти? Некоторые примеры кодов C/Java будут действительно полезны.


person all_by_grace    schedule 08.02.2012    source источник
comment
@John3136 имеет правильный ответ. Если вы не понимаете, как работают конечные автоматы, я рекомендую вам изучить его пример. Конечные автоматы — действительно полезный паттерн для такого типа задач.   -  person Jim Garrison    schedule 08.02.2012
comment
Правильный стиль, но глючный ответ, как подробно описано после его ответа. При этом я поддерживаю вашу поддержку конечных автоматов для подхода к реализации - я просто хочу в равной степени поддержать практику написания решения сначала словами (как я сделал в своем ответе), чтобы четко определить подход, ЗАТЕМ двигаться к стилю реализации. Кроме того, он по своей сути обеспечивает идеальный текст для блока комментариев, описывающего ваш код, когда следующий разработчик проекта переписывает вашу последовательность «если-то-иначе» в конечный автомат или наоборот. ;-)   -  person DreadPirateShawn    schedule 08.02.2012


Ответы (3)


Вы можете сделать это с помощью массива из 3 элементов.

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

Всякий раз, когда вы сталкиваетесь с B, проверьте, пуст ли второй элемент массива, но заполнен ли первый элемент — если нет, сбрасывайте массив в выходной файл вместе с новым B. В противном случае (то есть, если первый элемент заполнен, но второй пуст), вы сохраните новый B как второй элемент массива.

Для C повторите логику для B, увеличив ее на единицу: всякий раз, когда вы сталкиваетесь с C, проверяйте, является ли третий элемент массива пустым, а второй элемент заполнен — если нет, сбрасывайте массив в выходной файл вместе с новый C. В противном случае (то есть, если 2-й элемент заполнен, а 3-й пуст), вы сохраните новый C как 3-й элемент массива.

Когда вы не встретите ни A, ни B, ни C, сбросьте все существующие элементы массива в выходной файл, а затем запишите новую строку непосредственно в выходной файл.

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

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

person DreadPirateShawn    schedule 08.02.2012

Я предполагаю, что ваши линии более сложны, чем просто «A», «B» и «C», но есть способ выбрать «A» из «B» из «C».

(Если это действительно A, B и C, вам не нужно ничего хранить)

Я бы сделал небольшую программу типа конечного автомата.

state = Base;
while(there are more lines)
{   
    line = read_a_line()
    switch(state) {
        case Base:
          if (line.isTypeA()) {
            storedLines.add(line);
            state = GotA;
          }
          else {
             ouput(line);
          }
          break;
        case GotA:
          if (line.isTypeB()) {
            storedLines.add(line);
            state = gotB;
          }
          else {
              output(storedLines);
              output(line);
              state = Base;
          }
          break;
        case GotB:
          if (line.isTypeC()) {
            storedLines.clear();
          }
          else {
              output(storedLines);
              output(line);
          }
          state = Base;
          break;
    }
    // TODO: special case handling to make sure you write everything at the end of the
    // file.
person John3136    schedule 08.02.2012
comment
+1 за государственную машину. Это ЕДИНСТВЕННЫЙ разумный способ решить эту общую проблему, которая не превращается в безумный беспорядок из предложений if-then-else. - person Jim Garrison; 08.02.2012
comment
Полностью согласен! Сначала я попытался решить эту проблему, используя if-else, но решение просто стало нечитаемым и совершенно трудным для понимания. Мне нравится эта идея государственной машины! - person all_by_grace; 08.02.2012
comment
Это решение почти правильное, но упускает некоторые условия тестирования. Когда вы уже ПОЛУЧИЛИ A, то, если следующая строка будет другой A, блок else в случае GOTA будет неправильным. В этом случае необходимо выполнить еще одну проверку состояния. Ответ от DreadPirateShawn, похоже, правильно решает проблему. - person all_by_grace; 08.02.2012
comment
Как отмечает all_by_grace, последовательность из двух As будет выводить сохраненный A, затем второй A и сбрасываться в базовое состояние, тогда как вместо этого он должен выводить первый сохраненный A и сохранять второй A, сохраняя при этом состояние GotA. Несмотря на то, что удалось избежать безумной путаницы с предложениями if-then-else, подход конечного автомата по-прежнему несет в себе ту же сложность и риск ошибки, хотя и более элегантно структурирован. - person DreadPirateShawn; 08.02.2012

Вы можете использовать mark и сбросьте в своем потоке «перемотку назад»

person Dylan Bijnagte    schedule 08.02.2012