问题
正则表达式是对字符串匹配和处理最为强大的工具，绝大多数语言都提供了对正则表达式的支持。正则表达式常规用途包括：匹配或查找、替换、数据验证等。在这些使用场景中，先决条件是：得先有一个正则表达式。从一堆数据中人工提炼出一个合适的正则表达式，例如，考虑如下几十条药物批准文号数据：
国药准字Z22020031 国药准字Z44021605 国药准字H20052134
国药准字H20065128 国药准字H20063321 国药准字Z45020047
国药准字Z44023696 国药准字Z44020041 国药准字B20020729
国药准字Z37021536 国药准字Z10970003 国药准字Z20025893
国药准字Z20025021 国药准字Z41021818 国药准字Z13021046
国药准字Z10980075 国药准字Z22020445 国药准字Z45021256
国药准字Z20027946 国药准字Z20027945 国药准字Z20054513
国药准字Z20064282 国药准字Z20064281 国药准字Z20063129
国药准字Z20053531
我们很容易就写出一个正则表达式：
国药准字[BHZ]\d{8}
或者
国药准字[A-Z]\d{8}
但有没有可能让计算机自动生成这样的正则表达式呢？此外不可忽视的是，我们面对的数据并不能保证都是正确的，数据也会有质量问题，包含错误数据或脏数据。对于上述示例数据来说，下面两条数据就可认为是脏数据：
J20030052
国药准字
其中前一条缺失"国药准字"前缀，后一条没有具体的文号。
两个基础
字符符号的级别与上下级关系
一个典型的正则表达式，主要包括内容匹配符、数量限定符(* + ? {n} {n,m}等)、位置限定符（^ $ \b 等）、逻辑或等等。其中内容匹配符包含原始字符(a 2 Y ! \r \t等)、字符集合([a-z] [xyz]等)或代表一组字符的元字符（\d \w \s等）、以及能匹配除\r \n以外所有字符的"点"。这些匹配符之间存在一定的包含关系，也即上下级关系。表达能力最细的是原始字符，它们只能代表它们自身；字符集合类（如[a-z] \d \s）涵盖着一组字符，是在原始字符之上；"\w" 涵盖了“[a-z]" "[A-Z]" "\d" 以及下划线"_"； 而点"."能涵盖除"\r" "\n"以外的所有字符。他们之间的上下级关系如图一所示：
这里面有点小问题：\s是能匹配\r和\n的，然而.(点)却不能，因此严格意义上，点并不能作为\s的上级。但在我们的使用场景中，面对的都是简单的短文本数据，如身份证、邮箱、产品名称、编号等，这些数据中通常是不会有\r和\n的；而长文本数据一般来说没什么规律性，不适合用正则表达式来验证合规性。因此这么定义问题不大。
private val CHAR_ALL: Char = 0 // level 3
private val CHAR_WORD: Char = 1 //DIGITAL LETTER _ level 2
private val LETTER: Char = 2 //a-z A-Z \c level 1
private val LETTER_U: Char = 3 //A-Z \L level 1
private val LETTER_L: Char = 4 //a-z \l level 1
private val DIGITAL: Char = 5 //0 -9 \d ,level 1
private val OTHERLANG: Char = 6 // other language level 1
private val BLANK: Char = 7 // \s level 1
private val SPECIALCHAR = BLANK
val LEVELUPTABLE: Array[Char] = Array[Char]( //level 0 up to level 1
BLANK, BLANK, BLANK, BLANK, BLANK, BLANK, BLANK, BLANK, BLANK, BLANK, BLANK,
BLANK, BLANK, BLANK, BLANK, BLANK, BLANK, BLANK, BLANK, BLANK, BLANK, BLANK,
BLANK, BLANK, BLANK, BLANK, BLANK, BLANK, BLANK, BLANK, BLANK, BLANK, BLANK,
33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
DIGITAL, DIGITAL, DIGITAL, DIGITAL, DIGITAL, DIGITAL, DIGITAL, DIGITAL, DIGITAL, DIGITAL,
58, 59, 60, 61, 62, 63, 64, LETTER_U, LETTER_U, LETTER_U, LETTER_U, LETTER_U,
LETTER_U, LETTER_U, LETTER_U, LETTER_U, LETTER_U, LETTER_U, LETTER_U, LETTER_U,
LETTER_U, LETTER_U, LETTER_U, LETTER_U, LETTER_U, LETTER_U, LETTER_U, LETTER_U,
LETTER_U, LETTER_U, LETTER_U, LETTER_U, LETTER_U, 91, 92, 93, 94, 95, 96,
LETTER_L, LETTER_L, LETTER_L, LETTER_L, LETTER_L, LETTER_L, LETTER_L, LETTER_L,
LETTER_L, LETTER_L, LETTER_L, LETTER_L, LETTER_L, LETTER_L, LETTER_L, LETTER_L,
LETTER_L, LETTER_L, LETTER_L, LETTER_L, LETTER_L, LETTER_L, LETTER_L, LETTER_L,
LETTER_L, LETTER_L, 123, 124, 125, 126, 127)
val RegMap = Map[Char, String](DIGITAL -> "\\d", LETTER_L -> "[a-z]",
LETTER_U -> "[A-Z]", LETTER -> "[a-zA-z]", OTHERLANG -> "[\\u0100-\\uffff]",
BLANK -> "\\s", CHAR_WORD -> "\\w", CHAR_ALL -> ".", rootId -> "") ++
".\\?*+|{}()[]".toCharArray.map { c => c -> ("\\" + c.toString) }.toMap
Trie树
Trie树，即字典树，又称前缀树，典型应用是用于统计，排序和保存大量的字符（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
国药准字Z22020031 国药准字Z44021605 国药准字H20052134
国药准字H20065128 国药准字H20063321 国药准字Z45020047
国药准字Z44023696 国药准字Z44020041 国药准字B20020729
国药准字Z37021536 国药准字Z10970003 国药准字Z20025893
国药准字Z20025021 国药准字Z41021818 国药准字Z13021046
国药准字Z10980075 国药准字Z22020445 国药准字Z45021256
国药准字Z20027946 国药准字Z20027945 国药准字Z20054513
国药准字Z20064282 国药准字Z20064281 国药准字Z20063129
国药准字Z20053531 J20030052 国药准字
考虑如上27条数据，其中最后两条为脏数据，插入字典树后，结果如图二所示：
字典树构建的部分代码如下：
/**
* 往树中插入一条数据
*
* @param data
* @param support 数据重复的次数
* @return
*/
def addData(data: String, support: Int = 1): this.type = {
if (data == null || data.isEmpty) return this
val len = data.length
lengthInfo.get(len) match {
case Some(n) => lengthInfo += len -> (n + support)
case None => lengthInfo += len -> support
}
var curNode = ROOT
curNode.incInNum(support)
for (ch <- data) {
curNode = curNode.addChild(ch, support)
}
curNode.incEndNum(support)
this
}
def addData(data: Iterable[String]): this.type = {
data.foreach(d => addData(d, 1))
this
}
树的节点内容以及部分操作代码：
class TrieNode() {
private var item: Char = 0
private var repNumLow = 1 //repeat num lowerbound
private var repNumUpp = 1 //repeat num upperbound
private var itemLevel = 0 //item level
private var inNum = 0 //number of items into this node
private var endNum = 0 //number of items end from this node
private var childNodes = new HashMap[Char, TrieNode]()
// return child node
def addChild(ch: Char, support: Int): TrieNode = {
val child = childNodes.get(ch) match {
case Some(child) =>
child
case None =>
val child = TrieNode(ch)
childNodes += ch -> child
child
}
child.incInNum(support)
child
}
def copy(n: TrieNode): this.type = {
this.item = n.item
this.repNumLow = n.repNumLow
this.repNumUpp = n.repNumUpp
this.inNum = n.inNum
this.endNum = n.endNum
this.itemLevel = n.itemLevel
this.childNodes.clear()
this.childNodes ++= n.childNodes
this
}
def incRepNumUpp(supp: Int): this.type = {
this.repNumUpp += supp
this
}
def incRepNum(n: TrieNode): this.type = {
this.repNumUpp += n.repNumUpp
this.repNumLow += n.repNumLow
this
}
def mergeRepNum(n: TrieNode): this.type = {
if (this.repNumLow > n.repNumLow) this.repNumLow = n.repNumLow
if (this.repNumUpp < n.repNumUpp) this.repNumUpp = n.repNumUpp
this
}
/**
* merge 2 nodes to one
*
* @param other
*/
def mergeNode(other: TrieNode): this.type = {
this.incInNum(other.getInNum)
.incEndNum(other.getEndNum)
.mergeRepNum(other)
.mergeChildNodes(other)
this
}
/**
* merge the childs of node to current one
*
* @param other
*/
def mergeChildNodes(other: TrieNode): this.type = {
for ((_, otherChild) <- other.getChildNodes) {
this.childNodes.get(otherChild.getItem) match {
case Some(child) => child.mergeNode(otherChild)
case None => this.childNodes += otherChild.getItem -> otherChild
}
}
this
}
}
object TrieNode {
def apply(): TrieNode = new TrieNode()
def apply(item: Char): TrieNode = {
val t = new TrieNode()
t.item = item
t
}
def apply(n: TrieNode): TrieNode = new TrieNode().copy(n)
}
正则表达式生成算法
将数据插入到字典树后，如何得到正则表达式呢？
首先字典树的所有分支组成字符串然后按逻辑或的形式串联起来，就是一个正则表达式，如上述字典树输出结果：
(?:J20030052|国药准字B20020729|国药准字H20052134| ... )
这也是一个正则表达式，但没人会希望得到这样的结果，在机器学习领域，这样的结果叫着过拟合了，泛化能力差。
那么如何提升泛化能力呢？上面我们提到，不同级别字符的表达能力是不同，级别越高，表达能力越强，对应结果的泛化能力也就越高。因此将字典树的节点按需升级，相同值的节点合并后，得到的正则表达式的泛化能力将得到提升。
整个算法包含如下几个基本操作。
升级合并
一个节点是否需要升级呢？通过该节点的子分支数来判断，如果一个节点的子分支数较多，则说明后续的数据较复杂，需提升子节点的表达能力。
因此：如果节点的子分支分支数超过给定的阈值（例如3个），则将所有子节点提升一级。
注意子分支数计算时除了要计算子节点的数量，还需要考虑字符串到该节点终止的情况。例如“国药准字”中的“字”节点，除了3个子节点“BHZ”，还有一条数据在“字”处就终止了，这也算是一个分支，因此它的分支数要加1，即为4。代码中通过记录每个节点的数据进入条数以及终止条数来实现。
节点的多个子节点升级后的值（TrieNode.item）可能相同，如“字”节点的3个子节点“BHZ”升级后都为“[A-Z]"，这时需将相同值的节点以及所有下属子节点（即整个子分支）进行合并。
假设节点分支数升级的阈值为3，则图二所示的字典树升级合并后的结果如图三所示（旋转了90度）：
上图部分节点展示了数据进入的条数与终止的条数，如上侧分支只有1条数据，是在最后一个节点终止；下侧分支共有26条数据，1条在“字”节点终止，其余的都在最后节点终止。
/**
* 将node的所有子节点升到当前级curLevel，并对相同的节点进行合并
*
* @param node
* @return 所有已升级的节点数
*/
private def levelUp(node: TrieNode): Int = {
levelUp(node, false)
}
/**
* 将node的所有子节点升到当前级curLevel，并对相同的节点进行合并
*
* @param node
* @param forceLu 是否强制升级。若为否，则依据分支数来判断是否需要升级
* @return 所有已升级的节点数
*/
private def levelUp(node: TrieNode, forceLu: Boolean): Int = {
var lvNum = 0
val absGoodNum = (node.getInNum * absGoodBranch).toInt
val newChilds = new HashMap[Char, TrieNode]()
// 除去好的分支，剩下的分支数较少时也不升级
val forceLu2 = {
var num = 0
node.getChildNodes.values.foreach(n => if (n.getInNum < absGoodNum) num += 1)
num >= Branch_Num
}
for (child <- node.getChildNodes.values) {
if (forceLu || (child.getInNum < absGoodNum && forceLu2)) {
//子节点需要升级
lvNum += 1
val itemUp = charLevelUp(child.getItem, child.getItemLevel)
child.setItemLevel(curLevel)
child.setItem(itemUp)
lvNum += levelUp(child, true)
newChilds.get(itemUp) match {
case Some(ns) =>
ns.mergeNode(child)
case None =>
newChilds += itemUp -> child
}
}
else {
lvNum += levelUp(child, false)
newChilds += child.getItem -> child
}
}
node.setChildNodes(newChilds)
prune(node)
lvNum
}
剪枝
前面我们提到，输入数据里面可能包含脏数据的。那么如何区分脏数据呢？必须得假设，好数据是占多数的，脏数据只是少量，错误偶尔才犯。回到字典树，如果节点的某个分支的数据量较少，则认为此分支为脏数据，将其从树中剪去。具体可如此判断：对于一个节点的所有分支，如果某分支的数据量与分支平均数据量的比例小于某个阈值（如0.3），则视为脏数据。
对于上面的字典树，根节点有2个分支，分支平均数据量为27/2=13.5。左侧分支数据量与平均数的比例为1/13.5 = 0.074，小于阈值，因此将其从树中剪去。
”字“节点也有2个分支，平均数量为26/2=13，其中终止分支数据量占比为1/13=0.077，也小于阈值，将其从树中剪去（设置终止数为0）。
剪枝后，字典树变为如图四所示，从其中可输出正则表达式: "国药准字[A-Z]\d\d\d\d\d\d\d\d"。
/**
* 剪枝，分支的数据数量与所有姊妹分支平均数的比例小于阈值的分支从树中剪去
*
* @param node
*/
private def prune(node: TrieNode): Unit = {
if (!pruneDirtyData || !node.hasChilds) return
val childs = node.getChildNodes
val size = if (node.getEndNum > 0) childs.size + 1 else childs.size
val minSize = (node.getInNum / size * pruneScore).toInt
if (node.getEndNum < minSize) node.setEndNum(0)
val pruneChilds = new mutable.HashSet[Char]
childs.foreach(c => if (c._2.getInNum < minSize) pruneChilds += c._1)
pruneChilds.foreach(c => childs.remove(c))
}
深度合并
正则表达式中，如果某个字符（或元字符）多次出现，则可以用{n}、{n,m}等来表示匹配次数。在字典树中，这种情况表现为父节点与子节点的值相同，表示该值重复了2次；若再有同值的孙子节点，则代表重复了3次；以此类推。图四中，"\d"节点重复了8次。在这样一种简单情形下：节点只有一个子节点、且其值与父节点等同，我们可以将子节点可向上与父节点合并，并将父节点的重复次数增加1。对应图四，下端的7个"\d"节点都可往父节点合并，压缩成一个节点，结果如图五所示，可输出正则表达式"国药准字[A-Z]\d{8}"。
若子节点存在多个，此时与父节点同值的子节点往父节点合并时要慎重，因为可能产生不理想的结果。
如图六所示情况，只考虑单分支情况下的合并，可得图七，对应的正则表达式为："国药准字[A-Z]\d{3}(?:\d{5}|[a-z]{2})"；而此时若末端的"\d"节点再往父节点合并，则得到图八所示结果，对应的正则表达式为："国药准字[A-Z]\d{3,8}(?:[a-z]{2})?"。此规则表达的数据范围覆盖了图七的结果，但也较大地扩大了表达范围，会跟数据的实际情况产生一定的偏差。对于此例子，我们我们更希望得到图七的结果。
/**
* 存在多个子节点时，与父节点值相同时是否向父节点合并
* 经验判断规则，思路：大量数据分布在少量几个分支长度时，非必要下先不进行深度方向的合并，节点的升级时可能将相关子树合并在一起，
* 另外可以考虑：如果子节点往父节点合并后，后面的子树只有一个子分支，则可以合并；
*/
private def checkLengthInfo(): Unit = {
mergeDepth = false
if (lengthInfo.isEmpty) return
val maxGroups = (1 / (absGoodBranch + 0.000001)).toInt + 1
val avg = ROOT.getInNum / lengthInfo.size / 10
var groups = 0
lengthInfo.values.foreach(supp =>
if (supp >= avg) groups += 1
)
if (groups > maxGroups) mergeDepth = true
}
/**
* 深度方向的合并，子节点往父节点合并
*
* @param node
* @return 所有合并的节点数
*/
private def mergeDepth(node: TrieNode): Int = {
var mNum = 0
if (!node.hasChilds) return 0
val childs = node.getChildNodes
childs.values.foreach(c => mNum += mergeDepth(c))
prune(node)
childs.get(node.getItem) match {
case Some(child) =>
//存在与父节点相同item的子节点
if (childs.size == 1 && node.getEndNum == 0) {
//只有1个相同的子节点，跟父节点合并
mNum += 1
node.setChildNodes(child.getChildNodes)
node.incRepNum(child)
node.setInNum(child.getInNum)
node.setEndNum(child.getEndNum)
} else if (mergeDepth) {
mNum += 1
childs.remove(child.getItem)
node.mergeChildNodes(child)
node.incRepNumUpp(child.getRepNumUpp)
node.incEndNum(child.getEndNum)
prune(node)
}
case None =>
}
mNum
}
从字典树获取正则表达式
主要是要处理好多分支（用逻辑或并联）、节点重复次数、终止数等情况，代码如下：
/**
* 获得正则表达式
*
* @return
*/
def getRegString(): String = convertTree2String(ROOT, true)
private def convertTree2String(node: TrieNode, bHead: Boolean): String = {
if (!node.hasChilds) return ""
//获得所有子分支的规则表达式
val childRegs = node.getChildNodes.values.map(convert1Node _)
if (childRegs.size == 1) return childRegs.head
//存在多个分支，则用逻辑或组装
if (bHead) childRegs.mkString("|") else childRegs.mkString("(?:", "|", ")")
}
private def convert1Node(node: TrieNode): String = {
val item = node.getItem
//节点的值转换成正则表达式中的字符串
val itemReg = getItemChar(item)
val reg = new mutable.StringBuilder(itemReg)
//处理节点重复次数
val rl = node.getRepNumLow
val ru = node.getRepNumUpp
if (rl == ru) {
if (rl > 1) {
if (rl < 4 && item < 128 && item > SPECIALCHAR) reg.append(itemReg * (rl - 1))
else reg.append("{").append(rl).append("}")
}
} else reg.append("{").append(rl).append(",").append(ru).append("}")
if (!node.hasChilds) return reg.toString()
//获取子树的正则表达式
val childReg = convertTree2String(node, false)
if (childReg.isEmpty) return reg.toString()
//终止数不为零，说明子树的规则是可选的，因此要加问号
if (node.getEndNum > 0) reg.append("(?:").append(childReg).append(")?")
else reg.append(childReg)
reg.toString()
}
private def getItemChar(c: Char): String = {
RegMap.get(c) match {
case Some(r) => r
case None => c.toString
}
}
算法流程
算法的整体流程就是不停的重复升级、合并、剪枝操作，直到字典树不再改变或有节点级别已升级到给定的最高级。
def mine: Array[String] = {
checkLengthInfo()
absGoodBranchNum = (ROOT.getInNum * absGoodBranch).toInt
//记录迭代过程中的中间结果
val regsMap = new mutable.HashMap[String, Int]()
curLevel = 1
var changedNum = 0
do {
changedNum = levelUp(ROOT)
changedNum += mergeDepth(ROOT)
if (changedNum > 0) {
val reg = getRegString()
regsMap.get(reg) match {
case Some(n) => regsMap.put(reg, n + 1)
case None => regsMap.put(reg, 1)
}
}
curLevel += 1
} while (curLevel <= maxLevelUp && changedNum > 0)
regsMap.toArray.sortBy(x => (-x._2, x._1.length)).map(_._1)
}
测试示例
示例1
val data = "国药准字Z22020031\n国药准字Z44021605\n国药准字H20052134\n国药准字H20065128\n" +
"国药准字H20063321\n国药准字Z45020047\n国药准字Z44023696\n国药准字Z44020041\n" +
"国药准字B20020729\n国药准字Z37021536\n国药准字Z10970003\n国药准字Z20025893\n" +
"国药准字Z20025021\n国药准字Z41021818\n国药准字Z13021046\n国药准字Z10980075\n" +
"国药准字Z22020445\n国药准字Z45021256\n国药准字Z20027946\n国药准字Z20027945\n" +
"国药准字Z20054513\n国药准字Z20064282\n国药准字Z20064281\n国药准字Z20063129\n" +
"国药准字Z20053531"
val reg = new RegTree
reg.addData(data.split("\n"))
// 加两条脏数据
reg.addData("J20030052")
.addData("国药准字")
reg.mine
println(reg.getRegString())
输出结果：
国药准字[A-Z]\d{8}
示例2
val reg = new RegTree
//3个字母+3个数字 系列
reg.addData("abc123", 5)
.addData("cdd334", 3)
.addData("fdk324", 8)
.addData("odv082", 1)
.addData("jdv492", 3)
.addData("mfd729", 5)
.addData("uepw158", 1)
.addData("ids491", 1)
//4个字母+3个数字 系列
reg.addData("kkkk653", 20)
//11位数字 系列
reg.addData("13567891234", 20)
.addData("13812345678", 20)
//脏数据
reg.addData("ovd4321", 1)
.addData("123456789012345")
val r = reg.mine.mkString("\n\n")
println(r)
输出结果：
\d{11}|[a-z]{3,4}\d{3}
问题以及改进意见
一）字符级别的问题
如上文中提到的，\s是能匹配\r和\n的，然而.(点)却不能，因此严格意义上，点并没有覆盖\s的定义范围，因此不能作为\s的上级。若要解决此问题，可将\r \n 的上级新定义一个符号，跟现有的\s区分开来；并且在点之上再定义第4级，包括点和这个新增的符号，表示所有字符。代码中需加一些针对性的处理代码。
二）海量数据的字典树构建
如果面对的海量的数据，构建完整的字典树时可能要花费大量的内存。一个优化措施是数据抽样，推荐使用这个方法。因为这个算法的目的是从数据中提取正则规则，有一定的数据量涵盖了数据的特征后就够了，并不需要全部的数据。另一个优化措施是分批处理，例如插入1万条数据后，先对整个树进行初步剪枝和升级合并操作（最多升一级即可，暂时不进行深度方向的合并），再剩余数据插入树中。因为升一级后，候选节点值也就那么十几个，因此整个字典树的分支数会大大的降下来，内存开销会急剧减少。此时需注意树中各节点的级别，若不为0级，输入数据需先升级到相应的级别。
三）倒序规则
有些数据会含有公共的子串，例如测试用例1中的“国药准字”。如果公共子串出现在前面，构建字典树时就会形成公共的树根，而且因为权重较多，通常不会被升级，因此最终结果能较好的保留这部分特征。而若公共子串出现在尾部（例如电子邮箱，大部分以.com结尾），由于前面的分支较多，现在的算法会将末尾的公共子串给升级了，产生 ".[a-z]{3}"这样的结果，细节特征被隐藏掉了。一个改进思路是，对应输入数据，我们同时构建两棵字典树，一棵正序，另一棵按输入字符串的倒序构建。两棵树各自生成自己的正则规则，那么结果该选择哪个呢？如何评价规则的优劣呢？可以考虑如下两个准则：
- 最终结果树中的每个节点级别越高，节点的分值就越高
- 整棵树的所有节点的分值之和越低，最终结果更优
四）升级合并
当前算法处理时，如果判定某个节点的子节点需要升级，则将子节点及其下面的整个分支同步升级。另一种机制是只升级当前节点的子节点，并把子树合并后，子节点的子节点是否需要升级再判定。此措施应该能部分解决上面所说的公共子串在末尾以及在字符串中间的问题。
五）深度合并
简单情况下，即只有一个子节点，且值与父节点相同时，将子节点往父节点合并，这样做通常是没问题的。但复杂情况下的深度合并机制还有待进一步完善。可增加一个处理机制：若节点A包含多个子节点，其中节点B的值与A相同（A.item == B.item），如果A的子树结构（除去B分支）与B栋子树结构相同，即将B节点往A节点合并后，A的子树结构不会改变（即不增加新多分支）则这样的合并是可行的。
*最后 附上完整代码： https://github.com/mxnaxvex/RegexMaker
