正則表達式數字數據處理：匹配一串數字比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.所以我的輸出應爲：

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

請注意，第一個​​3210被忽略，因爲它不是l足夠了，並且捕獲結束之前0,1,0...。

我還想要一個stream_processor對象我可以遞增地將更多數據傳遞到後續的process調用中，並在完成時返回捕獲的塊。

我已經寫了一些代碼來做到這一點，但它是醜陋的和機器狀態的，我不禁感到我失去了明顯的東西。任何想法做到這一點乾淨？

Answer 1

狀態機（由於正則表達式可以匹配比FSM更廣泛的語言）是一種實現正則表達式引擎的典型方法，所以爲什麼在尋找好的實現時不應該出現類似的方法你想要的「正則表達式」構造？事實上，我會考慮從一個實際的RE引擎的代碼開始（在PyPy源代碼中有一個Python編碼的代碼，它的here的mercurial樹），只改變了「基元」（你不需要需要例如\w或\s，但是您需要<5,>3等）並且保留大多數語法和實現*,+等等。順便說一下，這樣一個項目非常值得開源。

Answer 2

狀態機在這裏是合適的解決方案。有兩種常用的方法來實現一個：

• 硬接線在一組相互遞歸函數，其中，在運行該函數表示當前狀態的形式。這可能非常有效，但需要尾部呼叫消除，蹦牀或跳轉。

• 以表示當前狀態和該狀態的函數以及更新狀態的新輸入數據的數據結構的形式進行仿真。

這東西是功能性編程的麪包和黃油。這裏是一個優雅的解決方案寫在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，並且最終的半食用狀態必須在返回之前適當地消耗。