Python-Levenshtein 0.12.2 实战5分钟实现TEDS表格相似度计算在数据处理和分析领域表格相似度计算是一个常见但颇具挑战性的任务。无论是文档比对、数据清洗还是OCR结果验证快速准确地评估两个表格的相似程度都能显著提升工作效率。本文将介绍如何利用Python-Levenshtein库在5分钟内构建一个完整的TEDSTree-Edit-Distance-based Similarity计算流程。1. TEDS基础与环境准备TEDS是一种基于树编辑距离的表格相似度评估方法它将表格结构转化为树形表示通过计算两棵树之间的编辑距离来量化相似度。与传统的单元格对比方法相比TEDS能更好地捕捉表格的结构特征包括合并单元格、表头位置等复杂情况。要开始我们的实现首先需要安装必要的Python包pip install python-Levenshtein beautifulsoup4这里我们选择Python-Levenshtein 0.12.2版本它提供了高效的字符串编辑距离计算功能。同时使用BeautifulSoup4来处理HTML表格的解析。2. 表格结构到树的转换TEDS的核心是将表格转换为树形结构。一个典型的HTML表格树表示如下table (root) ├── thead │ └── tr │ ├── th (colspan, rowspan, content) │ └── th └── tbody └── tr ├── td └── td以下代码展示了如何将HTML表格转换为这种树形结构的字符串表示from bs4 import BeautifulSoup def table_to_tree(html): soup BeautifulSoup(html, html.parser) table soup.find(table) def process_element(element): if element.name in [td, th]: attrs [] if colspan in element.attrs: attrs.append(fcolspan{element[colspan]}) if rowspan in element.attrs: attrs.append(frowspan{element[rowspan]}) attr_str ,.join(attrs) content element.get_text(stripTrue) return f{element.name}[{attr_str}]({content}) elif element.name in [thead, tbody, tr]: children .join(process_element(child) for child in element.children if child.name is not None) return f{element.name}{{{children}}} return return ftable{{{process_element(table)}}}3. TEDS计算实现有了树形表示后我们可以利用Python-Levenshtein计算编辑距离并转换为相似度分数import Levenshtein def calculate_teds(tree1, tree2): max_len max(len(tree1), len(tree2)) if max_len 0: return 1.0 # 两个空表格视为完全相同 distance Levenshtein.distance(tree1, tree2) return 1 - distance / max_len4. 完整流程与测试案例现在我们将所有步骤整合成一个完整的流程并针对三种典型表格结构进行测试def table_similarity(html1, html2): tree1 table_to_tree(html1) tree2 table_to_tree(html2) return calculate_teds(tree1, tree2) # 测试案例1简单表格 simple_table1 table trtdA/tdtdB/td/tr trtd1/tdtd2/td/tr /table simple_table2 table trtdA/tdtdC/td/tr trtd1/tdtd3/td/tr /table # 测试案例2含合并单元格的表格 merged_table1 table trtd colspan2Header/td/tr trtdA/tdtdB/td/tr /table merged_table2 table trtdHeader/tdtdHeader/td/tr trtdA/tdtdC/td/tr /table # 测试案例3带表头的表格 header_table1 table theadtrthName/ththAge/th/tr/thead tbodytrtdJohn/tdtd30/td/tr/tbody /table header_table2 table theadtrthName/ththScore/th/tr/thead tbodytrtdJohn/tdtd90/td/tr/tbody /table # 执行测试 cases [ (简单表格, simple_table1, simple_table2), (合并单元格, merged_table1, merged_table2), (带表头, header_table1, header_table2) ] for name, table1, table2 in cases: similarity table_similarity(table1, table2) print(f{name}相似度: {similarity:.2f})5. 性能优化与注意事项在实际应用中我们还需要考虑一些优化和注意事项预处理优化移除表格中的空白字符和无关属性对内容进行标准化处理如统一日期格式def normalize_table(html): soup BeautifulSoup(html, html.parser) for tag in soup.find_all(True): # 移除所有非必要属性 attrs dict(tag.attrs) for attr in list(attrs.keys()): if attr not in [colspan, rowspan]: del tag.attrs[attr] # 标准化文本内容 if tag.string: tag.string tag.get_text(stripTrue) return str(soup)阈值设定相似度0.9几乎相同相似度0.7-0.9结构相似内容不同相似度0.7显著差异大规模处理 当需要处理大量表格时可以考虑以下优化策略from concurrent.futures import ThreadPoolExecutor def batch_compute_similarity(table_pairs): with ThreadPoolExecutor() as executor: results list(executor.map( lambda pair: table_similarity(*pair), table_pairs )) return results6. 扩展应用场景TEDS方法不仅适用于HTML表格还可以扩展到其他结构化数据的比较Excel表格比较通过python-excel库读取表格后转换为HTML格式OCR结果验证将识别结果与标准表格进行相似度比对数据库表结构比对将表结构信息转换为树形表示以下是一个OCR验证的示例流程def ocr_validation(ground_truth_html, ocr_result_html): # 预处理OCR结果 processed_ocr preprocess_ocr(ocr_result_html) # 计算相似度 similarity table_similarity(ground_truth_html, processed_ocr) # 根据阈值判断识别质量 if similarity 0.95: return 优秀 elif similarity 0.8: return 良好 else: return 需人工检查在实际项目中TEDS方法帮助我们将原本需要人工检查的表格比对工作自动化将处理时间从小时级缩短到分钟级。特别是在处理数百个表格的批量验证时这种效率提升更为显著。
Python-Levenshtein 0.12.2 实战5分钟实现TEDS表格相似度计算在数据处理和分析领域表格相似度计算是一个常见但颇具挑战性的任务。无论是文档比对、数据清洗还是OCR结果验证快速准确地评估两个表格的相似程度都能显著提升工作效率。本文将介绍如何利用Python-Levenshtein库在5分钟内构建一个完整的TEDSTree-Edit-Distance-based Similarity计算流程。1. TEDS基础与环境准备TEDS是一种基于树编辑距离的表格相似度评估方法它将表格结构转化为树形表示通过计算两棵树之间的编辑距离来量化相似度。与传统的单元格对比方法相比TEDS能更好地捕捉表格的结构特征包括合并单元格、表头位置等复杂情况。要开始我们的实现首先需要安装必要的Python包pip install python-Levenshtein beautifulsoup4这里我们选择Python-Levenshtein 0.12.2版本它提供了高效的字符串编辑距离计算功能。同时使用BeautifulSoup4来处理HTML表格的解析。2. 表格结构到树的转换TEDS的核心是将表格转换为树形结构。一个典型的HTML表格树表示如下table (root) ├── thead │ └── tr │ ├── th (colspan, rowspan, content) │ └── th └── tbody └── tr ├── td └── td以下代码展示了如何将HTML表格转换为这种树形结构的字符串表示from bs4 import BeautifulSoup def table_to_tree(html): soup BeautifulSoup(html, html.parser) table soup.find(table) def process_element(element): if element.name in [td, th]: attrs [] if colspan in element.attrs: attrs.append(fcolspan{element[colspan]}) if rowspan in element.attrs: attrs.append(frowspan{element[rowspan]}) attr_str ,.join(attrs) content element.get_text(stripTrue) return f{element.name}[{attr_str}]({content}) elif element.name in [thead, tbody, tr]: children .join(process_element(child) for child in element.children if child.name is not None) return f{element.name}{{{children}}} return return ftable{{{process_element(table)}}}3. TEDS计算实现有了树形表示后我们可以利用Python-Levenshtein计算编辑距离并转换为相似度分数import Levenshtein def calculate_teds(tree1, tree2): max_len max(len(tree1), len(tree2)) if max_len 0: return 1.0 # 两个空表格视为完全相同 distance Levenshtein.distance(tree1, tree2) return 1 - distance / max_len4. 完整流程与测试案例现在我们将所有步骤整合成一个完整的流程并针对三种典型表格结构进行测试def table_similarity(html1, html2): tree1 table_to_tree(html1) tree2 table_to_tree(html2) return calculate_teds(tree1, tree2) # 测试案例1简单表格 simple_table1 table trtdA/tdtdB/td/tr trtd1/tdtd2/td/tr /table simple_table2 table trtdA/tdtdC/td/tr trtd1/tdtd3/td/tr /table # 测试案例2含合并单元格的表格 merged_table1 table trtd colspan2Header/td/tr trtdA/tdtdB/td/tr /table merged_table2 table trtdHeader/tdtdHeader/td/tr trtdA/tdtdC/td/tr /table # 测试案例3带表头的表格 header_table1 table theadtrthName/ththAge/th/tr/thead tbodytrtdJohn/tdtd30/td/tr/tbody /table header_table2 table theadtrthName/ththScore/th/tr/thead tbodytrtdJohn/tdtd90/td/tr/tbody /table # 执行测试 cases [ (简单表格, simple_table1, simple_table2), (合并单元格, merged_table1, merged_table2), (带表头, header_table1, header_table2) ] for name, table1, table2 in cases: similarity table_similarity(table1, table2) print(f{name}相似度: {similarity:.2f})5. 性能优化与注意事项在实际应用中我们还需要考虑一些优化和注意事项预处理优化移除表格中的空白字符和无关属性对内容进行标准化处理如统一日期格式def normalize_table(html): soup BeautifulSoup(html, html.parser) for tag in soup.find_all(True): # 移除所有非必要属性 attrs dict(tag.attrs) for attr in list(attrs.keys()): if attr not in [colspan, rowspan]: del tag.attrs[attr] # 标准化文本内容 if tag.string: tag.string tag.get_text(stripTrue) return str(soup)阈值设定相似度0.9几乎相同相似度0.7-0.9结构相似内容不同相似度0.7显著差异大规模处理 当需要处理大量表格时可以考虑以下优化策略from concurrent.futures import ThreadPoolExecutor def batch_compute_similarity(table_pairs): with ThreadPoolExecutor() as executor: results list(executor.map( lambda pair: table_similarity(*pair), table_pairs )) return results6. 扩展应用场景TEDS方法不仅适用于HTML表格还可以扩展到其他结构化数据的比较Excel表格比较通过python-excel库读取表格后转换为HTML格式OCR结果验证将识别结果与标准表格进行相似度比对数据库表结构比对将表结构信息转换为树形表示以下是一个OCR验证的示例流程def ocr_validation(ground_truth_html, ocr_result_html): # 预处理OCR结果 processed_ocr preprocess_ocr(ocr_result_html) # 计算相似度 similarity table_similarity(ground_truth_html, processed_ocr) # 根据阈值判断识别质量 if similarity 0.95: return 优秀 elif similarity 0.8: return 良好 else: return 需人工检查在实际项目中TEDS方法帮助我们将原本需要人工检查的表格比对工作自动化将处理时间从小时级缩短到分钟级。特别是在处理数百个表格的批量验证时这种效率提升更为显著。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
