Skip to content

Peng2017/KnowledgeGraph_Expression_Parser

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

3 Commits
.cache
.cache
 
 
JS版本
JS版本
 
 
.gitignore
.gitignore
 
 
KnowledgeGraph_Expression_Parser.py
KnowledgeGraph_Expression_Parser.py
 
 
README.md
README.md
 
 

Repository files navigation

AST 算法知识图谱解析器

🎯 项目概述

本项目实现了基于抽象语法树(AST)的数学表达式知识图谱解析器，支持将复杂数学表达式转换为多叉树结构的知识图谱，并提供并发计算能力。

核心特性

  • 多叉树结构：支持同级节点批量处理，避免二叉树的语义分割问题
  • 递归下降解析器：基于Go语言math-engine设计，准确处理运算符优先级
  • 单层触发并发：每次只执行一层聚合，有效控制资源使用和避免递归溢出
  • 分支独立聚合：支持不同分支独立完成聚合，无需等待其他分支
  • 原子操作方法：将运算符处理模块化为独立的原子操作方法，便于业务扩展
  • 括号识别：将括号作为独立运算符处理，支持LLM语义分析
  • 格式化日志：提供可读性强的并发任务执行日志
  • 执行顺序可视化：生成多种格式的执行流程图，包括Mermaid流程图、文本流程图和详细执行信息

🏗️ 技术架构

多叉树结构

class MultiOpNode(ASTNode):
    """多元运算节点 - 支持同级运算符的多叉树结构"""
    def __init__(self, operands: List[ASTNode], operators: List[str], priority: int):
        self.operands = operands    # 操作数列表（可变长度）
        self.operators = operators  # 操作符列表
        self.priority = priority    # 优先级

运算符优先级

priority_levels = {
    'Add': 1, 'Sub': 1,      # 加减法：优先级1
    'Mult': 2, 'Div': 2,     # 乘除法：优先级2  
    'Pow': 3,                # 幂运算：优先级3
    '()': 100                # 括号：优先级100（最高）
}

🚀 使用方法

基本用法

from KnowledgeGraph_Expression_Parser import KnowledgeGraphParser

# 创建解析器实例
parser = KnowledgeGraphParser()

# 解析表达式
expr = "A1^2+((B1*2-C1)/D1^(E+F)+G)*H-1"
kg_data = parser.parse_to_kg(expr)

# 输出知识图谱
print(json.dumps(kg_data, indent=2, ensure_ascii=False))

异步并发计算

import asyncio

async def main():
    parser = KnowledgeGraphParser()
    expr = "A+B*C"
    kg_data = parser.parse_to_kg(expr)
    
    # 异步聚合计算
    result = await parser.aggregate_from_leaves(kg_data)
    print(f"计算结果: {result}")

asyncio.run(main())

执行顺序可视化

程序会自动在 .cache 目录生成三种可视化文件：

  • execution_flow.mmd - 可在 Mermaid Live Editor 中查看的专业流程图
  • execution_flow.txt - 直接在终端查看的ASCII艺术流程图
  • execution_flow.json - 包含完整执行数据的JSON文件，便于程序化处理

📋 输出格式

三阶段输出

🌳 第一阶段：AST结构生成 (.ast文件)

  • 语法解析：将数学表达式转换为抽象语法树
  • 词法分析：识别数字、变量、运算符、括号等token
  • 语法验证：确保表达式语法正确性

📊 第二阶段：知识图谱生成 (.json文件)

  • 多叉树转换：将二叉AST转换为多叉树结构
  • 表达式提取：为每个节点生成完整的表达式字符串
  • 运算符识别：标识每个节点的运算符类型（包括括号"()"）
  • 优先级计算：为每个节点分配运算优先级（0-100取值范围）
JSON结构示例
{
  "root": {
    "KG_ID": [0],
    "expression": "A1^2+((B1*2-C1)/D1^(E+F)+G)*H-1",
    "operator": "",
    "depth": 0,
    "priority": 1,
    "is_variable": false,
    "children": [
      {
        "KG_ID": [0, 0],
        "expression": "A1^2",
        "operator": "",
        "priority": 3,
        "children": [...]
      }
    ]
  }
}

📝 第三阶段：可视化输出 (.md文件)

  • 树形结构：清晰的Markdown树形显示
  • 节点信息：包含KG_ID、表达式、运算符、深度、优先级等

🎯 第四阶段：执行顺序可视化

  • Mermaid流程图 (.mmd文件)：专业的流程图格式，支持在线渲染和编辑
  • 文本流程图 (.txt文件)：ASCII艺术风格的易读流程图，包含批次信息和操作符图例
  • 详细执行信息 (.json文件)：完整的执行数据结构，包含每个批次的节点信息和操作类型
知识图谱输出结构示例 (markdown多叉树)
[0]: {"KG_ID": [0], "expression": "A1^2+((B1*2-C1)/D1^(E+F)+G)*H-1", "is_variable": false, "operator": "", "depth": 0, "priority": 1}
    ├── [0,0]: {"KG_ID": [0, 0], "expression": "A1^2", "is_variable": false, "operator": "", "depth": 1, "priority": 3}
    │   ├── [0,0,0]: {"KG_ID": [0, 0, 0], "expression": "A1", "is_variable": true, "operator": "", "depth": 2, "priority": 0}
    │   └── [0,0,1]: {"KG_ID": [0, 0, 1], "expression": "2", "is_variable": true, "operator": "^", "depth": 2, "priority": 0}
    ├── [0,1]: {"KG_ID": [0, 1], "expression": "((B1*2-C1)/D1^(E+F)+G)*H", "is_variable": false, "operator": "+", "depth": 1, "priority": 2}
    │   ├── [0,1,0]: {"KG_ID": [0, 1, 0], "expression": "((B1*2-C1)/D1^(E+F)+G)", "is_variable": false, "operator": "", "depth": 2, "priority": 100}
    │   │   └── [0,1,0,0]: {"KG_ID": [0, 1, 0, 0], "expression": "(B1*2-C1)/D1^(E+F)+G", "is_variable": false, "operator": "()", "depth": 3, "priority": 1}
    │   │       ├── [0,1,0,0,0]: {"KG_ID": [0, 1, 0, 0, 0], "expression": "(B1*2-C1)/D1^(E+F)", "is_variable": false, "operator": "", "depth": 4, "priority": 2}
    │   │       │   ├── [0,1,0,0,0,0]: {"KG_ID": [0, 1, 0, 0, 0, 0], "expression": "(B1*2-C1)", "is_variable": false, "operator": "", "depth": 5, "priority": 100}
    │   │       │   │   └── [0,1,0,0,0,0,0]: {"KG_ID": [0, 1, 0, 0, 0, 0, 0], "expression": "B1*2-C1", "is_variable": false, "operator": "()", "depth": 6, "priority": 1}
    │   │       │   │       ├── [0,1,0,0,0,0,0,0]: {"KG_ID": [0, 1, 0, 0, 0, 0, 0, 0], "expression": "B1*2", "is_variable": false, "operator": "", "depth": 7, "priority": 2}
    │   │       │   │       │   ├── [0,1,0,0,0,0,0,0,0]: {"KG_ID": [0, 1, 0, 0, 0, 0, 0, 0, 0], "expression": "B1", "is_variable": true, "operator": "", "depth": 8, "priority": 0}
    │   │       │   │       │   └── [0,1,0,0,0,0,0,0,1]: {"KG_ID": [0, 1, 0, 0, 0, 0, 0, 0, 1], "expression": "2", "is_variable": true, "operator": "*", "depth": 8, "priority": 0}
    │   │       │   │       └── [0,1,0,0,0,0,0,1]: {"KG_ID": [0, 1, 0, 0, 0, 0, 0, 1], "expression": "C1", "is_variable": true, "operator": "-", "depth": 7, "priority": 0}
    │   │       │   └── [0,1,0,0,0,1]: {"KG_ID": [0, 1, 0, 0, 0, 1], "expression": "D1^(E+F)", "is_variable": false, "operator": "/", "depth": 5, "priority": 3}
    │   │       │       ├── [0,1,0,0,0,1,0]: {"KG_ID": [0, 1, 0, 0, 0, 1, 0], "expression": "D1", "is_variable": true, "operator": "", "depth": 6, "priority": 0}
    │   │       │       └── [0,1,0,0,0,1,1]: {"KG_ID": [0, 1, 0, 0, 0, 1, 1], "expression": "(E+F)", "is_variable": false, "operator": "^", "depth": 6, "priority": 100}
    │   │       │           └── [0,1,0,0,0,1,1,0]: {"KG_ID": [0, 1, 0, 0, 0, 1, 1, 0], "expression": "E+F", "is_variable": false, "operator": "()", "depth": 7, "priority": 1}
    │   │       │               ├── [0,1,0,0,0,1,1,0,0]: {"KG_ID": [0, 1, 0, 0, 0, 1, 1, 0, 0], "expression": "E", "is_variable": true, "operator": "", "depth": 8, "priority": 0}
    │   │       │               └── [0,1,0,0,0,1,1,0,1]: {"KG_ID": [0, 1, 0, 0, 0, 1, 1, 0, 1], "expression": "F", "is_variable": true, "operator": "+", "depth": 8, "priority": 0}
    │   │       └── [0,1,0,0,1]: {"KG_ID": [0, 1, 0, 0, 1], "expression": "G", "is_variable": true, "operator": "+", "depth": 4, "priority": 0}
    │   └── [0,1,1]: {"KG_ID": [0, 1, 1], "expression": "H", "is_variable": true, "operator": "*", "depth": 2, "priority": 0}
    └── [0,2]: {"KG_ID": [0, 2], "expression": "1", "is_variable": true, "operator": "-", "depth": 1, "priority": 0}

📊 并发任务执行日志

功能描述： 提供格式化的并发任务执行日志输出功能，支持多行显示，提升可读性和调试便利性。

日志格式：

批次 1:
当前批次并发处理的任务节点:
  [0,0]:A1
  [0,1]:B
  [0,2]:C
聚合后的父节点ID:
  [0,1]

批次 2:
当前批次并发处理的任务节点:
  [0,1]:A+B
  [0,2]:C
聚合后的父节点ID:
  [0]

技术特性：

  • 结构清晰：批次信息分层显示
  • 可读性强：每个节点单独一行
  • 调试友好：复杂表达式信息不挤在一行
  • 层次分明：批次间空行分隔

🔧 单层触发并发机制

核心设计理念

  • 资源控制：每次触发只执行一层聚合，避免递归导致的资源溢出
  • 分支独立：不同分支可以独立完成聚合，无需等待其他分支
  • 硬件友好：合理分配硬件资源，避免任务溢出和系统无响应

工作原理

while True:
    # 查找当前可以聚合的节点
    ready_nodes = self._find_ready_for_aggregation(kg_data, result_cache)
    
    if not ready_nodes:
        break  # 没有更多可聚合的节点
    
    # 批量处理当前层的节点
    await self.batch_process_same_level(ready_nodes, "llm_analysis")

🧩 原子操作方法架构

运算符分类与业务语义

1. 括号运算 _process_parentheses_operation

  • 业务定义：最优先执行的任务
  • 应用场景：概念解析，如 "金刚石半导体" 需要搜索引擎或LLM初步回答
  • 未来扩展：概念解析、搜索引擎查询、权威性验证

2. 加减法运算 _process_addition_subtraction_operation

  • 业务定义：现在和过去的企业事实
  • 应用场景：公司介绍、管理团队、核心产品、技术优势、TAM、财务表现、投资风险
  • 案例：PE历史最低点(+)、ARR创新高(+)、收入下降(-)、产品被淘汰(-)
  • 未来扩展：LLM必须给出3个正面和反面意见

3. 乘除法运算 _process_multiplication_division_operation

  • 业务定义：企业通过努力可以改变的市场份额和技术领先
  • 应用场景：竞争分析、市场地位、技术路线挑战
  • 案例：OpenAI行业头部地位()、谷歌搜索90%份额()、业务拆分(/)、失去客户(/)
  • 未来扩展：网络搜索节点的搜索结论(乘法支持，除法相悖)

4. 幂运算 _process_power_operation

  • 业务定义：企业层面无法控制的全行业影响因素
  • 应用场景：宏观市场、行业赛道、政策影响
  • 案例：AI推理井喷、房地产崩盘、政府封杀政策
  • 未来扩展：宏观经济分析、政策影响分析、不可控因素评估

架构优势

  • 模块化设计：每个运算符对应独立的业务逻辑
  • 业务语义清晰：运算符与实际业务场景直接对应
  • 易于扩展：新增业务逻辑只需修改对应的原子操作方法
  • 向后兼容：当前版本保持简单字符串处理，未来可无缝升级
  • 调试友好：每个方法都有调试打印，便于观察执行流程
  • 可视化支持：自动生成执行顺序流程图，直观展示并发执行过程

🎨 执行顺序可视化功能

业务语义标注

每个操作类型都有对应的业务语义和可视化符号：

  • 🔤 变量获取：从数据库或搜索引擎获取基础数据
  • 📦 括号运算：概念解析，需要LLM理解复杂概念
  • ➕ 加减法：企业历史事实和现状分析
  • ✖️ 乘除法：市场竞争和技术领先性分析
  • 🔺 幂运算：行业宏观因素和政策影响

可视化输出格式

1. Mermaid流程图 (.mmd)

graph TD
    START([开始解析])
    BATCH1[批次1]
    START --> BATCH1
    N1_0[A1\n(变量获取)]
    N1_0 --> N1_0_result{获取: A1}
    BATCH1 --> N1_0
    END([完成聚合])
Loading

2. 文本流程图 (.txt)

┌─────────────────┐
│   开始解析      │
└─────────────────┘
         │
         ▼
┌─────────────────┐
│   批次 1        │
└─────────────────┘
         │
    ┌────┴────┐
    ▼         ▼
┌─────────┐ ┌─────────┐
│🔤 A1     │ │🔤 B1     │
└─────────┘ └─────────┘

3. 详细执行信息 (.json)

[
  {
    "batch_id": 1,
    "nodes": [
      {
        "id": "0,0,0,0",
        "expression": "A1",
        "is_variable": true,
        "operator": "",
        "operation_type": "变量获取"
      }
    ]
  }
]

可视化特性

  • 批次展示：清晰显示每个并发执行批次
  • 操作分类：用不同符号和颜色区分操作类型
  • 执行顺序：直观展示从叶子节点到根节点的聚合过程
  • 业务语义：每个操作都有明确的业务含义标注
  • 多格式支持：提供专业图表、文本图表和数据结构三种格式

📈 性能优势

1. 资源控制能力

  • 单层执行：每次只处理一层节点，避免递归溢出
  • 内存友好：控制并发数量，避免内存过度消耗
  • 可中断性：支持分层执行，便于中断和恢复
  • 负载均衡：合理分配计算资源

2. 批量处理能力

  • 并行API调用：同级节点可并行处理，减少调用次数
  • 效率提升：测试显示可提升 60-80% 的处理效率
  • 资源优化：减少网络请求和计算资源消耗

3. 语义完整性

  • 保持上下文：同级节点保持完整的语义关联
  • 避免信息丢失：多叉树结构不会拆分语义相关的操作
  • 支持复杂分析：便于进行整体性的语义分析

🔥 实际应用场景

财务表达式分析

# 示例："营收+利润-成本-税费"
# 可以批量查询所有财务指标，而不是逐个查询

LLM语义分析

# 示例："A1+B1+C1" 的三个变量可以批量进行语义理解
# 而不是分解为 "((A1+B1)+C1)" 的二叉树结构

并发计算流程

从叶子节点开始的并发执行，以复杂表达式 A1^2+((B1*2-C1)/D1^(E+F)+G)*H-1 为例：

Step 0: 初始树状态

所有节点构建完成，等待从叶子节点开始执行：

[0]
├── [0,0] (A1^2)

## 📝 更新日志

### v2.0.0 - 单层触发并发机制 (2024-01-XX)

#### 🚀 重大更新
- **重构聚合逻辑**：从深度优先改为单层触发机制
- **新增原子操作方法**：将运算符处理模块化为独立方法
- **优化资源控制**：每次只执行一层聚合，避免递归溢出
- **支持分支独立**：不同分支可独立完成聚合

#### 🔧 技术改进
- 新增 `_find_ready_for_aggregation()` 方法：智能识别可聚合节点
- 重构 `aggregate_from_leaves()` 方法：实现单层触发逻辑
- 新增原子操作方法：
  - `_process_parentheses_operation()` - 括号运算
  - `_process_addition_subtraction_operation()` - 加减法运算
  - `_process_multiplication_division_operation()` - 乘除法运算
  - `_process_power_operation()` - 幂运算
  - `_process_default_operation()` - 默认运算

#### 🎯 业务价值
- **硬件友好**：有效控制资源使用，避免系统无响应
- **业务扩展**：每个运算符对应明确的业务语义
- **调试便利**：每个原子操作都有调试打印
- **架构清晰**：模块化设计便于未来扩展

#### 🧪 测试验证
- ✅ 单层触发机制正常工作
- ✅ 原子操作方法正确调用
- ✅ 根节点聚合逻辑修复
- ✅ 调试打印信息完整
- ✅ 最终聚合结果正确
│   ├── [0,0,0] (A1)
│   └── [0,0,1] (2)
├── [0,1] (((B1*2-C1)/D1^(E+F)+G)*H)
│   ├── [0,1,0] (((B1*2-C1)/D1^(E+F)+G))
│   │   └── [0,1,0,0] ((B1*2-C1)/D1^(E+F)+G)
│   │       ├── [0,1,0,0,0] ((B1*2-C1)/D1^(E+F))
│   │       │   ├── [0,1,0,0,0,0] ((B1*2-C1))
│   │       │   │   └── [0,1,0,0,0,0,0] (B1*2-C1)
│   │       │   │       ├── [0,1,0,0,0,0,0,0] (B1*2)
│   │       │   │       │   ├── [0,1,0,0,0,0,0,0,0] (B1)
│   │       │   │       │   └── [0,1,0,0,0,0,0,0,1] (2)
│   │       │   │       └── [0,1,0,0,0,0,0,1] (C1)
│   │       │   └── [0,1,0,0,0,1] (D1^(E+F))
│   │       │       ├── [0,1,0,0,0,1,0] (D1)
│   │       │       └── [0,1,0,0,0,1,1] ((E+F))
│   │       │           └── [0,1,0,0,0,1,1,0] (E+F)
│   │       │               ├── [0,1,0,0,0,1,1,0,0] (E)
│   │       │               └── [0,1,0,0,0,1,1,0,1] (F)
│   │       └── [0,1,0,0,1] (G)
│   └── [0,1,1] (H)
└── [0,2] (1)

Step 1: 叶子节点GetVariable（并发执行）

所有叶子节点（变量）可以并发获取值：

  • [0,0,0] (A1) - GetVariable
  • [0,0,1] (2) - GetVariable
  • [0,1,0,0,0,0,0,0,0] (B1) - GetVariable
  • [0,1,0,0,0,0,0,0,1] (2) - GetVariable
  • [0,1,0,0,0,0,0,1] (C1) - GetVariable
  • [0,1,0,0,0,1,0] (D1) - GetVariable
  • [0,1,0,0,0,1,1,0,0] (E) - GetVariable
  • [0,1,0,0,0,1,1,0,1] (F) - GetVariable
  • [0,1,0,0,1] (G) - GetVariable
  • [0,1,1] (H) - GetVariable
  • [0,2] (1) - GetVariable

Step 2: 第一轮聚合

兄弟节点完成后开始聚合，关键规则：只有当所有兄弟节点都完成计算时，才能向上聚合：

[0]
├── [0,0] ✅ 聚合完成 (A1^2)
├── [0,1]
│   ├── [0,1,0]
│   │   └── [0,1,0,0]
│   │       ├── [0,1,0,0,0]
│   │       │   ├── [0,1,0,0,0,0]
│   │       │   │   └── [0,1,0,0,0,0,0]
│   │       │   │       ├── [0,1,0,0,0,0,0,0] ✅ 聚合完成 (B1*2)
│   │       │   │       └── [0,1,0,0,0,0,0,1] ⏸️ 等待兄弟节点
│   │       │   └── [0,1,0,0,0,1]
│   │       │       ├── [0,1,0,0,0,1,0] ⏸️ 等待兄弟节点
│   │       │       └── [0,1,0,0,0,1,1]
│   │       │           └── [0,1,0,0,0,1,1,0] ✅ 聚合完成 (E+F)
│   │       └── [0,1,0,0,1] ⏸️ 等待兄弟节点
│   └── [0,1,1] ⏸️ 等待兄弟节点
└── [0,2] ⏸️ 等待兄弟节点

Step 3-N: 逐层向上聚合

继续按照"兄弟节点同步"原则逐层聚合：

Step 3:

[0]
├── [0,0] ✅ 已完成
├── [0,1]
│   ├── [0,1,0]
│   │   └── [0,1,0,0]
│   │       ├── [0,1,0,0,0]
│   │       │   ├── [0,1,0,0,0,0]
│   │       │   │   └── [0,1,0,0,0,0,0] ✅ 聚合完成 (B1*2-C1)
│   │       │   └── [0,1,0,0,0,1] ✅ 聚合完成 (D1^(E+F))
│   │       └── [0,1,0,0,1] ⏸️ 等待兄弟节点
│   └── [0,1,1] ⏸️ 等待兄弟节点
└── [0,2] ⏸️ 等待兄弟节点

最终Step: 所有节点聚合到根节点

[0] ✅ 最终结果

核心机制说明

  1. 并发GetVariable：所有叶子节点可以同时获取变量值（对应LLM场景中的并发API调用）
  2. 兄弟节点同步等待：同一父节点下的所有子节点必须全部完成计算，父节点才能开始聚合
  3. 优先级驱动：按照运算符优先级（括号>幂运算>乘除>加减）进行聚合
  4. 逐层向上：从最深层开始，逐层向根节点聚合
  5. 语义完整性：确保每个聚合步骤都保持数学表达式的语义正确性

🛠️ 核心技术特性

解析器特性

  • 递归下降解析器：准确处理运算符优先级
  • 多叉树结构：支持同级节点批量处理
  • 括号识别：将括号作为独立运算符处理
  • 高性能：优化的解析和计算算法
  • 业务适用性：适合LLM语义分析等复杂场景
  • 日志格式化：提供可读性强的执行日志

📁 文件结构

00_knowledgegraph算法/
├── KnowledgeGraph_Expression_Parser.py  # 主程序文件
├── .cache/                              # 输出文件目录
│   ├── output.json                      # 知识图谱JSON输出
│   ├── output.md                        # 可视化树结构
│   ├── output.ast                       # AST结构输出
│   ├── output.log                       # 格式化并发日志
│   ├── execution_flow.mmd               # Mermaid流程图
│   ├── execution_flow.txt               # 文本流程图
│   └── execution_flow.json              # 详细执行信息
└── README.md                            # 本文档

🎯 总结

本AST算法成功实现了：

  • ✅ 多叉树结构的数学表达式解析
  • ✅ 递归下降解析器的准确性
  • ✅ 括号作为独立运算符的处理
  • ✅ 并发任务的异步执行
  • ✅ 格式化日志的可读性提升
  • ✅ 完整的三阶段输出系统

这些特性使得本算法特别适合需要LLM语义分析、网络搜索、财务数据分析等复杂业务场景的应用。

Citation:

Github项目math-engine(Go语言)提供了本项目核心解析算法: https://github.com/dengsgo/math-engine

About

No description, website, or topics provided.

Resources

Readme
Activity

Stars

1 star

Watchers

0 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages