视频字幕
确定有限自动机，简称DFA，是理论计算机科学中的重要概念。它由五个基本要素组成：状态集合、字母表、转移函数、初始状态和接受状态集合。右侧展示了一个简单的DFA示例，包含三个状态，其中q0是初始状态，q2是接受状态，状态间通过字符a和b进行转移。
传统的DFA存储方式使用二维转移表，行表示状态，列表示输入字符，单元格存储目标状态。这种方法的空间复杂度为状态数乘以字符集大小。如右侧表格所示，红色标记的单元格表示无效转移，造成大量空间浪费。当状态数和字符集都很大时，这种浪费会变得非常严重。
双数组结构是一种高效的DFA存储方法，由base数组和check数组组成。base数组存储每个状态的基址值，用于计算转移目标位置。check数组用于验证转移的有效性，存储转移的来源状态。右侧展示了两个数组的结构，每个数组元素都有对应的索引。这种结构通过巧妙的设计实现了空间压缩和快速查询。