代码之家  ›  专栏  ›  技术社区  ›  inf3rno

无训练集的字符串模式识别

  •  0
  • inf3rno  · 技术社区  · 8 年前

    我有多个字符串,它们是基于几个(大部分)已知变量和几个未知模板创建的。我想知道从这些字符串中提取变量部分的模板是什么。之后,我可以相对容易地推断出每个子串的含义,所以这里的问题只是模式识别。例如:

    "76 (q) h"
    "a x q y 123"
    "c x e y 73"
    "3 (e) z"
    ...
    
    # pattern recognition: examples -> templates
    "{1} x {2} y {3}"
    "{1} ({2}) {3}"
    
    # clusters based on template type
    "{1} x {2} y {3}" -> ["a x q y 123", "c x e y 73", ...]
    "{1} ({2}) {3}" -> ["76 (q) h", "3 (e) z", ...]
    
    # inference: substrings -> extracted variables
    "76 (q) h" -> ["76", "q", "h"] -> {x: "h", y: "q", z: 76}
    "a x q y 123" -> ["a", "q", "123"] -> {x: "a", y: "q", z: 123}
    "c x e y 73" -> ["c", "e", "73"] -> {x: "c", y: "e", z: 73}
    "3 (e) z" -> ["3", "e", "z"] -> {x: "z", y: "e", z: 3}
    

    我发现了一个类似的问题: Intelligent pattern matching in string ,但在我的例子中,没有办法用积极的东西来训练解析器。有没有办法解决这个问题?

    1 回复  |  直到 8 年前
        1
  •  0
  •   inf3rno    8 年前

    事实证明,我需要的是序列模式挖掘。有很多算法,例如SPADE、PrefixSpan、CloSpan、BIDE等。我需要的是一个也能处理间隙的算法,或者一个能找到频繁子串的算法,我可以用通配符连接这些子串。从发现的频繁闭合模式中选择合适的模式远非显而易见,我仍在努力,但我现在比2个月前更接近了。