обработка числовых данных в регулярном выражении: сопоставление серии чисел больше X

Question

Скажем, у меня есть такие данные:

number_stream = [0,0,0,7,8,0,0,2,5,6,10,11,10,13,5,0,1,0,...]

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

Представьте, что у меня есть собственный настроенный язык регулярных выражений для работы с числами, где [[> = 5]] представляет любое число> = 5. Я хочу захватить этот случай:

([[ >=5 ]]{3,})[[ <3 ]]{2,}

Другими словами, я хочу начать захват в любое время, когда я смотрю в будущее и вижу 3 или более значений> = 5 подряд, и прекращать захват в любое время, когда я смотрю в будущее и вижу значения 2+ <3. Поэтому мой вывод должен быть: </p>

>>> stream_processor.process(number_stream)
[[5,6,10,11,10,13,5],...]

Обратите внимание, что первый 7,8,... игнорируется, поскольку он недостаточно длинный, и что захват заканчивается до 0,1,0....

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

Я написал некоторый код, чтобы сделать это, но это было отвратительно и государственно, и я не могу не чувствовать, что упускаю что-то очевидное. Есть идеи сделать это чисто?

Answer 1

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

Действительно, я бы хотел начать с кода для реального движка RE (в исходниках PyPy есть код с Python, дерево ртути для которого здесь ), изменяя только «примитивы» (вам не нужны, например, \w или \s, но вам нужны <5, >3 и т. д.) и сохраните большую часть синтаксиса и реализации для *, + и т. д. Кстати, такой проект стоит того, чтобы с открытым исходным кодом.

Answer 2

Конечный автомат - подходящее решение здесь. Существует два распространенных способа реализации одного:

• Аппаратно реализован в виде набора взаимно-рекурсивных функций, где выполняемая функция представляет текущее состояние. Это может быть очень эффективным, но требует устранения хвостовых вызовов, батутов или goto.

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

Этот материал - хлеб с маслом функционального программирования. Вот элегантное решение вашей проблемы, написанное в прежнем стиле на F # и работающее на вашем собственном наборе данных:

> let rec skip = function
    | _, yss, [] -> yss
    | [_; _; _] as ys, yss, xs -> record ([], ys, yss, xs)
    | ys, yss, x::xs when x >= 5 -> skip (x::ys, yss, xs)
    | ys, yss, x::xs -> skip ([], yss, xs)
  and record = function
    | ys', ys, yss, [] -> (ys' @ ys) :: yss
    | [_; _], ys, yss, xs -> skip ([], ys :: yss, xs)
    | ys', ys, yss, x::xs when x < 3 -> record (x::ys', ys, yss, xs)
    | ys', ys, yss, x::xs -> record ([], x::ys' @ ys, yss, xs);;
val skip : int list * int list list * int list -> int list list
val record : int list * int list * int list list * int list -> int list list

> let run xs = skip([], [], xs) |> List.map List.rev |> List.rev;;
val run : int list -> int list list

> run [0;0;0;7;8;0;0;2;5;6;10;11;10;13;5;0;1;0];;
val it : int list list = [[5; 6; 10; 11; 10; 13; 5]]

и вот то же решение, написанное в последнем стиле:

> type 'a state =
    | Skip of 'a list
    | Record of 'a list * 'a list;;
type 'a state =
  | Skip of 'a list
  | Record of 'a list * 'a list

> let rec apply (state, yss) x =
    match state, yss with
    | Skip([_; _; _] as ys), yss -> apply (Record([], ys), yss) x
    | Skip ys, yss when x >= 5 -> Skip(x::ys), yss
    | Skip ys, yss -> Skip[], yss
    | Record([_; _], ys), yss -> apply (Skip[], ys :: yss) x
    | Record(ys', ys), yss when x < 3 -> Record (x::ys', ys), yss
    | Record(ys', ys), yss -> Record ([], x::ys' @ ys), yss;;
val apply : int state * int list list -> int -> int state * int list list

> let run xs =
    match List.fold apply (Skip [], []) xs with
    | Skip _, yss -> yss
    | Record(ys', ys), yss -> (ys' @ ys) :: yss
    |> List.map List.rev |> List.rev;;
val run : int list -> int list list

> run [0;0;0;7;8;0;0;2;5;6;10;11;10;13;5;0;1;0];;
val it : int list list = [[5; 6; 10; 11; 10; 13; 5]]

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