给定有限列表示字符串正则表达式的语法推理?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (19)

我正在分析一个大型的公共数据集,其中包含大量冗长的人类可读的字符串,这些字符串显然是由一些正规的语法(在形式语言理论意义上)生成的。

一个接一个地查看这些字符串的集合来查看模式并不难;不幸的是,大约有24000个独特的字符串被分成33个类别和1714个子类别,因此手动这样做有点痛苦。

我曾经考虑过重复的、贪婪的、最长的、公共的子字符串消除,但这只是因为它不会折叠任何东西,只有精确的匹配,所以不会检测到,比如说,在语法中某个特定位置改变数字字符串的常见模式。

强迫任何不脱离普通子字符串消除的东西是可能的,但在计算上可能是不可行的。

提问于
用户回答回答于

是的,事实证明这是存在的;所需要的是学术上被称为DFA学习算法的例子包括:

  • 安谷蛋白L*
  • L*(在列中添加反示例)
  • 卡恩斯/瓦兹拉尼
  • 里弗特/夏蒂瓦尔
  • nl*
  • 正则正负推理(RPNI)
  • 德莱特2
  • Biermann&Feldman算法
  • Biermann&Feldman算法(使用SAT算法)
用户回答回答于

(用于Python的自然语言工具包),看看它是否至少能够识别反复出现的模式。

基于Java的软件包,用于统计自然语言处理、文档分类、聚类、主题建模、信息提取等

扫码关注云+社区