列表结构

相关源文件

• src/ccmain/paramsd.cpp
• src/ccmain/paramsd.h
• src/ccstruct/blobbox.h
• src/ccstruct/ocrblock.cpp
• src/ccstruct/stepblob.h
• src/ccstruct/werd.cpp
• src/ccstruct/werd.h
• src/ccutil/ambigs.cpp
• src/ccutil/ambigs.h
• src/ccutil/clst.h
• src/ccutil/elst.h
• src/ccutil/elst2.h
• src/textord/colpartition.cpp
• src/textord/colpartition.h
• src/textord/tabvector.cpp
• src/textord/tabvector.h
• src/wordrec/lm_state.h
• unittest/list_test.cc

本页面记录了 Tesseract OCR 代码库中使用的列表数据结构。Tesseract 实现三种主要的列表结构，用于高效地表示和操作数据元素的集合。这些列表结构是许多内部数据表示的基础，从 OCR 处理过程中存储块和单词，到管理参数列表和搜索结果。

列表结构概述

Tesseract实现了三种主要的链表类型，每种类型都有不同的特性

来源: src/ccutil/clst.h36-996 src/ccutil/elst.h76-86 src/ccutil/elst2.h54-64

命名和宏

列表结构被实现为泛型模板类，并使用宏来创建特定类型的列表类

• CLIST: 使用 CLISTIZEH(T) 宏生成，创建一个 T_CLIST 类
• ELIST: 使用 ELISTIZEH(T) 宏生成，创建一个 T_LIST 类
• ELIST2: 使用 ELIST2IZEH(T) 宏生成，创建一个 T_LIST 类

每种列表类型都有相应的迭代器类型用于遍历列表

• C_IT: CLIST 的迭代器 (T_C_IT)
• ELIST_ITERATOR: ELIST 的迭代器
• ELIST2_ITERATOR: ELIST2 的迭代器

来源: src/ccutil/clst.h991-995 src/ccutil/elst.h760-772 src/ccutil/elst2.h996-1005

内存架构

三种列表类型在内存架构上存在显著差异

主要区别

1. CLIST (ConsList):

   • 使用独立的“cons单元”链接数据对象
   • 每个链节点包含一个指向数据和指向下一个节点的指针
   • 数据对象独立于列表结构

2. ELIST (IntrusiveForwardList):

   • 将链（next指针）直接嵌入数据对象中
   • 数据类必须继承自 ELIST<T>::LINK
   • 单向链表，但结构是循环的

3. ELIST2 (IntrusiveList):

   • 将next和prev指针都嵌入数据对象中
   • 数据类必须继承自 ELIST2<T>::LINK
   • 双向链表，循环结构
   • 允许高效的双向遍历

来源: src/ccutil/clst.h37-62 src/ccutil/elst.h89-111 src/ccutil/elst2.h67-87

列表迭代器使用

所有三种列表类型都提供了用于遍历和操作列表的迭代器。这里是一个遍历列表的常见模式

该模式在代码库中被广泛用于处理列表中的元素。

来源: src/ccstruct/werd.cpp70-105 src/ccutil/clst.h695-756 src/ccutil/elst2.h567-607

常用操作

所有列表类型都支持通用操作，但实现方式略有不同

列表遍历

• mark_cycle_pt(): 将当前位置标记为循环点
• forward(): 移动到下一个元素
• cycled_list(): 检查是否已回到循环点

元素访问

• data(): 获取当前元素数据
• extract(): 从列表中移除当前元素并返回
• move_to_first(): 移动到列表的第一个元素
• move_to_last(): 移动到列表的最后一个元素

列表操作

• add_after_then_move(): 在当前元素后添加元素，并移动到新元素
• add_before_then_move(): 在当前元素前添加元素，并移动到新元素
• add_list_after(): 在当前元素后添加另一个列表
• add_list_before(): 在当前元素前添加另一个列表

来源: src/ccutil/clst.h426-487 src/ccutil/elst.h528-562 src/ccutil/elst2.h568-608

CLIST 特定功能

CLIST 结构 (ConsList) 提供了一些其他列表类型所没有的附加功能

1. 排序: 内置排序功能
2. 按顺序添加: 添加元素时保持顺序
3. 集合减法: 计算列表之间的集合差

来源: src/ccutil/clst.h891-917 src/ccutil/clst.h927-960 src/ccutil/clst.h967-988

ELIST2 特定功能

ELIST2 结构 (IntrusiveList) 提供双向遍历功能

来源: src/ccutil/elst2.h614-649

Tesseract 中的使用模式

列表结构在 Tesseract 代码库中被广泛使用

CLIST 用法

CLIST 通常用于数据对象并非专门为列表包含而设计的集合

来源: src/ccstruct/blobbox.h141 src/textord/tabvector.h58

ELIST 用法

ELIST 用于更轻量级的列表，只需要前向遍历

来源：src/ccutil/ambigs.h134 src/ccmain/paramsd.h47

ELIST2 用法

ELIST2 用于需要双向遍历的最重要结构

来源：src/ccstruct/werd.h199 src/textord/colpartition.h56

实现细节

循环结构

所有列表类型都实现为循环列表，其中最后一个元素指向第一个元素。此设计允许

1. 使用单个指针检查来检测空列表
2. 高效访问第一个和最后一个元素
3. 简化的迭代（无需检查空指针）

内存管理

列表结构以不同的方式处理内存管理

• CLIST：仅拥有链接节点，不拥有数据对象
• ELIST/ELIST2：列表不拥有对象；对象仅包含嵌入式链接

大多数列表提供以下方法

• shallow_clear()：清空列表而不删除数据
• deep_clear()：清空列表并删除数据对象

来源：src/ccutil/clst.h824-836 src/ccutil/clst.h800-811

提取和迭代

所有列表类型都提供了在迭代期间删除元素的强大机制

来源：src/ccstruct/werd.cpp217-220 src/colpartition.cpp217-224

最佳实践

1. 选择合适的列表类型:

   • 当数据对象不应被修改以包含链接指针时，使用 CLIST
   • 对于轻量级单向遍历，使用 ELIST
   • 当需要双向遍历时，使用 ELIST2

2. 迭代器生命周期:

   • 迭代前始终使用 mark_cycle_pt()
   • 检查 cycled_list() 来检测迭代结束
   • 在迭代过程中要小心 extract()

3. 内存管理:

   • 明确数据对象的归属
   • 当列表拥有其数据时，使用 deep_clear()
   • 当数据由其他地方拥有时，使用 shallow_clear()

来源：unittest/list_test.cc50-79 unittest/list_test.cc81-105 unittest/list_test.cc107-149

总结

Tesseract 的列表结构提供了高效的链表实现，针对不同的用例进行了优化。理解这些结构对于使用 Tesseract 代码库至关重要，因为它们构成了系统中大多数数据集合的基础。