Scala：リスト/シーケンスの正規表現

Question

任意のシーケンスでサブシーケンスパターンを検索する体系的な方法はありますか？ある意味では正規表現と似ていますが、要素の順序は同じです。

具体的には、我々は、以下の入力およびターゲットパターンのためにたとえば、この機能

def findPattern(seq: Seq[String], Seq[String]): Seq[Int] = { 
    // find the indices of seq which matches the input pattern. 
    // if the pattern is not found, return Seq.empty. 
} 

を完了したい：

seq: Seq[String] = Seq("NNS", "VBG", "JJ", "NNS", "IN", "NNP", "NNP") 
pattern: String = Seq("VBG", "JJ") 

所望の出力は次のようになります。

Seq(1, 2) 

同じ別の例seq：

pattern: String = Seq("VBG", "?", "NNS") 

所望の出力は

Seq(1, 2, 3) 

もう一つの例のようになります。

pattern: String = Seq("VBG", "*", "IN") 

になる必要があります。

Seq(1, 2, 3, 4) 

サイドノート：1を作ることができます存在を収容するために出力Seq[Seq[Int]]複数のパターン。私は、パーサがよりマッチパターンを見つけるための意味を作るべきだと思う

Answer 1

は、このための実装があり、希望に満ち、それはあなたのために便利です：

def findPattern(list: List[String], pattern: List[String]): List[List[Int]] = { 
    def nextPattern(lt: Option[List[(String, Int)]], ps: List[String]): Option[List[(String, Int)]] = { 
     ps match { 
     //if only have "*" should return all 
     case List("*") => lt 
     //filter whether first str match head, if not return None 
     case List(head) => 
      lt.filter(_.nonEmpty).filter(_.head._1 == head).map(r => { 
      List(r.head) 
      }) 
     //minimum match for wildcard for first str 
     case "*" :: List(last) => 
      lt.filter(_.nonEmpty).flatMap(t => { 
      t.find(_._1 == last).map(i => { 
       t.takeWhile(_._1 != last) :+ i 
      }) 
      }) 
     case "*" :: last :: l => 
      nextPattern(lt, List("*", last)).flatMap(j => { 
      nextPattern(lt.map(_.drop(j.size)), l).map(i => { 
       j ++ i 
      }) 
      }) 
     //skip fist str 
     case "?" :: l => 
      lt.filter(_.nonEmpty).flatMap(r => { 
      nextPattern(Some(r.tail), l).map(j => { 
       r.head :: j 
      }) 
      }) 
     //match the list first str 
     case head :: l => 
      lt.filter(_.nonEmpty).filter(_.head._1 == head).flatMap(r => { 
      nextPattern(Some(r.tail), l).map(j => { 
       r.head :: j 
      }) 
      }) 
     } 
    } 
    //if any is empty, return None 
    list.isEmpty || pattern.isEmpty match { 
     case true => List.empty 
     case false => 
     val relevantIndices = list.zipWithIndex.filter(_._1 == pattern.head).map(_._2) 
     val relevantSublists = relevantIndices.map(list.zipWithIndex.drop) 
     relevantSublists.map{ sublist => 
      nextPattern(Some(sublist), pattern).map(_.map(_._2)) 
     }.filter(_.isDefined).map(_.get) 
    } 
    } 

テスト：その結果

val list = List("NNS", "VBG", "JJ", "NNS", "IN", "NNP", "NNP") 

    println(findPattern(list, List("NNS", "VBG"))) 
    println(findPattern(list, List("NNS", "*", "VBG"))) 
    println(findPattern(list, List("NNS", "?", "VBG"))) 
    println(findPattern(list, List("NNS", "?", "JJ"))) 
    println(findPattern(list, List("VBG", "?", "NNS"))) 
    println(findPattern(list, List("JJ"))) 
    println(findPattern(list, List("VBG", "*", "IN"))) 
    println(findPattern(list, List("VBG", "*"))) 
    println(findPattern(list, List("Foo"))) 
    println(findPattern(list, List("VBG", "*", "Bar"))) 
    println(findPattern(list, List("NNS"))) 

：

[info] List(List(0, 1)) 
[info] List(List(0, 1)) 
[info] List() 
[info] List(List(0, 1, 2)) 
[info] List(List(1, 2, 3)) 
[info] List(List(2)) 
[info] List(List(1, 2, 3, 4)) 
[info] List(List(1, 2, 3, 4, 5, 6)) 
[info] List() 
[info] List() 
[info] List(List(0), List(3))