解析部分/不完整JSON时的灾难性回溯问题及解决方案咨询

我清楚用正则解析JSON并非最佳实践，但因需处理TB级规模的JSON数据，于是尝试实现了一个并行JSON读取器：通过截取随机数据块识别目标记录，再将块内首个匹配前的内容与前一块缓冲区合并、最后匹配后的内容与后一块缓冲区合并，再做分析。目前正则能正常识别首个及后续匹配，但在最后一个有效匹配后会陷入灾难性回溯。

相关正则表达式 #

{\s*
(?:
  \s*"negotiation_arrangement"\s*:\s*"[^"]+?"\s*,?\s*|
  \s*"name"\s*:\s*"[^"]+?",?\s*|
  \s*"billing_code_type"\s*:\s*"[^"]+?",?\s*|
  \s*"billing_code_type_version"\s*:\s*"[^"]+?",?\s*|
  \s*"billing_code"\s*:\s*"[^"]+?",?\s*|
  \s*"description"\s*:\s*"(?:\\.|[^"\\])*",?\s*|
  \s*"bundled_codes"\s*:\s*\[[^\]]*\]\s*,?|
  \s*"covered_service"\s*:\s*\[[^\]]*\]\s*,?|
  \s*"negotiated_rates"\s*:\s*(?:\[\s*
  (?:\s*\{\s*
  (?:
    \s*"provider_references"\s*:\s*\[[^"\[\]]+\]\s*,?\s*|
    (?:\s*"provider_groups"\s*:\s*\[\s*
      (?:{\s*
        (?:"npi"\s*:\s*\[[\d\,\s]*\]\s*,?\s*)|
        (?:"tin"\s*:\s*{\s*
          (?:"type"\s*:\s*"[^"]+"\s*,?\s*|
             "value"\s*:\s*"[^"]+"\s*,?\s*
          )+\s*\}\s*
        )\s*\}\s*,?\s*
      )+\s*],?
    )|
    (?:\s*"negotiated_prices"\s*:\s*\[\s*
      (?:\s*\{\s*
        (?:\s*"negotiated_type"\s*:\s*"[^"]*"\s*,? 
          |\s*"negotiated_rate"\s*:\s*[\d\.]*\s*,? 
          |\s*"expiration_date"\s*:\s*"[^"]*"\s*,? 
          |\s*"billing_class"\s*:\s*"[^"]*"\s*,? 
          |\s*"additional_information"\s*:\s*"[^"]*"\s*,?
          |\s*"service_code"\s*:\s*(?:\[[^\[\]]*\]|null),?
          |\s*"billing_code_modifier"\s*:\s*(?:\[[^\[\]]*\]|null),?
          ){0,7}
      \s*\},?)+
    )+\s*\]
  ){0,3}\s*\},?
)+
\s*\]\s*,?)
)+\s*}

引发问题的最小JSON示例 #

{
  "negotiated_rates": [
    {
      "provider_references": [
        532
      ],
      "negotiated_prices": [
        {
          "negotiated_rate": 3600
        }
    

解决方法 #

1. 优化正则表达式，消除灾难性回溯 #

灾难性回溯的根源是正则中存在大量嵌套的可选/重复结构（比如多层(?:...)+、宽松的{0,3}限定），匹配失败时引擎会尝试所有可能的回溯路径。可以通过以下方式修复：

• 使用原子组：用(?>...)包裹重复的分支结构，让引擎一旦匹配成功就不再回溯，避免无效的路径尝试。
• 收紧重复限定：把模糊的{0,3}这类限定改成更明确的范围，或者结合上下文减少分支可能性。
• 明确闭合标记：确保正则能精准匹配到完整的JSON对象闭合括号，而非依赖模糊的\s*}。

针对你的正则，重点优化negotiated_rates内部的嵌套重复结构，比如将多层(?:...)+替换为原子组包裹的版本。

2. 给re.finditer添加超时限制 #

Python的re模块本身没有超时参数，但可以通过signal模块给匹配过程设置超时，避免无限循环：

import re
import signal

class TimeoutError(Exception):
    pass

def timeout_handler(signum, frame):
    raise TimeoutError("正则匹配超时")

def finditer_with_timeout(pattern, text, timeout=5):
    signal.signal(signal.SIGALRM, timeout_handler)
    signal.alarm(timeout)
    try:
        return list(re.finditer(pattern, text))
    finally:
        signal.alarm(0)

调用该函数时，若匹配超过设定时间会抛出TimeoutError，终止匹配过程。

3. 优化缓冲区截取逻辑 #

在截取数据块时，通过计数括号、引号的方式，确保块的结束位置落在非字符串、非数组/对象内部的位置，避免读取不完整的JSON结构。从根源上减少正则匹配失败的场景，也就不会触发灾难性回溯。

内容的提问来源于stack exchange，提问作者Siddharth Chabra