代码之家 › 专栏 › 技术社区 › Mu Mind hora

regex数值数据处理:匹配一系列大于x的数字

regex python

Mu Mind hora · 技术社区 · 15 年前

假设我有这样的数据:

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

我想处理它,寻找符合某种模式的“凸起”。

假设我有自己定制的regex语言来处理数字,其中[>=5]]表示任何数字>=5。我想抓住这个案子:

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

换言之,我想开始捕捉我向前看的任何时间,并在一行中看到3个或更多的值>=5,停止捕捉我向前看的任何时间,并看到2个以上的值<3。所以我的输出应该是:

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

注意第一个 7,8,... 被忽略,因为它不够长,捕获结束之前这个 0,1,0... .

我也喜欢 stream_processor 对象i可以在随后的 process 调用,并在完成时返回捕获的块。

我已经写了一些代码来做这件事,但它是可怕的,是国家机器,我禁不住觉得我错过了一些明显的东西。有什么好办法吗?

2 回复 | 直到 14 年前

Mu Mind hora 14 年前

状态机(由于regex可以匹配比fsms可以匹配的语言范围更广,因此它富含相当多的额外功能)是实现正则表达式引擎的典型方法,所以为什么不应该在寻找所需的“regex-like”构造的良好实现时出现类似的方法呢?

实际上,我会考虑从实际的re引擎的代码开始(pypy源代码中有一个python代码,其mercurial树是 here ,只更改“原语”(您不需要例如 \w 或 \s 但你需要 <5 , >3 等),并保留大多数语法和实现 * , + 等等。顺便说一下,这样的项目很值得公开采购。

J D 15 年前

状态机是这里合适的解决方案。有两种常见的实现方法:

以一组相互递归的函数的形式硬连线,其中正在运行的函数表示当前状态。这可能非常有效,但需要消除尾叫、蹦床或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 最后的半食状态必须在返回前被适当地消耗掉。