如何防止正则表达式爆表?

先前给 helm 做了一点扩展:helm-pinyin: 为 helm 添加拼音搜索

就是利用 pinyinlib 生成匹配汉字的表达式,例如:

;; 仅匹配英文
(string-match-p "[^a]*[a][^b]*[b][^c]*[c]" "a-b-c")
;; 匹配中英文
(string-match-p "[^a啊...]*[a啊...][^b把...]*[b把...][^c擦...]*[c擦...]" "啊-波-吃")

加上中文之后,表达式长度暴增,很容易爆表,所以我简单地把中文首字的个数限制为 8。

但问题没有完全解决,还是会“随机”爆表。例如在输入到 .../default.y 还正常,再加一个字母变成 .../default.ya 就爆了。

看似有点不可思议,多加 1 个字就撑爆了?其实匹配汉字的表达式长度还是很惊人的,在 .../default.y 时已经接近极限了。

由于每个字母对应的汉字数量不同:

(("a" . 76)    ("h" . 346)   ("o" . 17)   ("u" . 3)
 ("b" . 333)   ("i" . 3)     ("p" . 246)  ("v" . 3)
 ("c" . 452)   ("j" . 554)   ("q" . 339)  ("w" . 213)
 ("d" . 340)   ("k" . 206)   ("r" . 104)  ("x" . 416)
 ("e" . 53)    ("l" . 491)   ("s" . 496)  ("y" . 600)
 ("f" . 211)   ("m" . 295)   ("t" . 291)  ("z" . 582)
 ("g" . 311)   ("n" . 173))

所以在特定的组合下,8 个字就足以撑爆表达式了,也就使得问题看起来的有点“随机”。

我打算改进一下:因为是模糊匹配,所以可以跳过中间的某些字母,例如:default.yamldefaultaml,跳过对应汉字比较多的 y,一下就少了好几百个字。

接着我又看了一下正则表达式的缓冲到底是有“多小”, 然而发现并不简单

平铺直叙的表达式,例如 ^aaaaaa....,最长可以到 32504 也就是 2^15 - 2^8 - 2^3

一旦表达式中出现了复杂的符号,能容纳的字数变得有点“捉摸不定了”:(下表中的 reg-n 表示需要扣除的长度,其数字越大,表示正则内容字数越少)

;;                           ‖ reg-max: 32504, reg-n: (- reg-bytes reg-max)
;; reg                       ‖ --------------------------------------------------
;;                           ‖ reg-n error-msg | reg-n error-msg
;; ------------------------- ‖ ----- --------- | ----- --------------------------
;; ^aaaaaaaaaaaaaaaaaaaaaaa… ‖     0 nil       |     1 Regular expression too big
;; ^\(a\)aaaaaaaaaaaaaaaaaa… ‖    -2 nil       |    -1 Regular expression too big
;; ^\(a\)\(b\)aaaaaaaaaaaaa… ‖    -4 nil       |    -3 Regular expression too big
;; ^\(a\|\)aaaaaaaaaaaaaaaa… ‖    -6 nil       |    -5 Regular expression too big
;; ^\(a\|b\)aaaaaaaaaaaaaaa… ‖    -8 nil       |    -7 Regular expression too big
;; ^[ab]aaaaaaaaaaaaaaaaaaa… ‖   -11 nil       |   -10 Regular expression too big
;; ^[a]aaaaaaaaaaaaaaaaaaaa… ‖   -12 nil       |   -11 Regular expression too big
;; ^[a-z]aaaaaaaaaaaaaaaaaa… ‖   -13 nil       |   -12 Regular expression too big
;; ^[a][b]aaaaaaaaaaaaaaaaa… ‖   -24 nil       |   -23 Regular expression too big
;; ^[^a]aaaaaaaaaaaaaaaaaaa… ‖   -11 nil       |   -10 Regular expression too big
;; ^[^a]*[a]aaaaaaaaaaaaaaa… ‖   -28 nil       |   -27 Regular expression too big
;; ^[^ab]*[ab]aaaaaaaaaaaaa… ‖   -26 nil       |   -25 Regular expression too big
;; ^[^a]*[a][^b]*[b]aaaaaaa… ‖   -56 nil       |   -55 Regular expression too big

总之,想要防止正则表达式爆表:

  1. 挑选对应汉字比较少的字母。
  2. 计算表达式中[]等符号的开销。(现在的关键是搞清楚其中的规律)

完成这两步之后,还是可能会报表,因为英文字母长度没限制,所以还是有可能出现处在爆表边缘、再输入一个字就爆了的情形,但概率应该比中大奖还低了。

2赞

这不应该用预处理把汉字替换成对应字母再搜索么

有考虑过这个方案,如果候选项太多,替换过程恐怕会很漫长。

预格式化文本将缩进 4 格
(defun pyim-cregexp-valid-p (cregexp)
  "Return t when cregexp is a valid regexp."
  (and cregexp
   (stringp cregexp)
   (condition-case nil
       (progn (string-match-p cregexp "") t)
     ;; FIXME: Emacs can't handle regexps whose length is too big :-(
     (error nil))))
1赞

我在折腾pyim-cregexp的时候,也遇到类似问题,你可以看看,也许有帮助

在构造正则表达的过程中,不断"试错",以求找到最大长度么?

当我发现正则表达式的最大长度“飘忽不定”而感到有些挫败时,也曾闪过这个“疯狂”的念头,但是立即否决了。不过既然你用实践检验过,我觉得可以试一试。

是的,粗暴但管用

#1楼列表中各种情况下的最大长度边界,就有用到这种“试错”的方法来确定。

但在正式代码中用这种方法还是有点犹豫,待我看看用“计算”确定长度的方法是否靠谱,再决定采用哪一种。