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

先前给 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. 计算表达式中[]等符号的开销。(现在的关键是搞清楚其中的规律)

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

3 个赞

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

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

预格式化文本将缩进 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楼列表中各种情况下的最大长度边界,就有用到这种“试错”的方法来确定。

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

长度限制飘忽不定应该是因为不同种类符号产生的状态机的部分复杂度不同