基于有限状态机模型的供电故障断电区间快速提取方法

杨涛存，郭剑峰，杜文然，徐贵红

（1.中国铁道科学研究院集团有限公司电子计算技术研究所，北京100081；2.中国铁道科学研究院集团有限公司基础设施检测研究所，北京100081；3.中国铁道科学研究院研究生部，北京100081）

1 背景

铁路供电故障数据分析中，需要计算断电区间长度，供电故障数据大多以非结构化文字描述形式记录存储，需从中提取断电区间起始位置、终止位置，计算两者里程差值，得到故障区间长度，再根据线路复线数量，计算此区间需乘的倍率系数。在实际生产中遇到供电故障问题时，从故障描述中提取断点区间起始位置、终止位置和倍率系数往往需要人工阅读提取，耗费大量时间、精力，使供电故障数据分析成本大幅提升。

随着自然语言处理技术在铁路领域的应用，研究如何从非结构化数据中提取特定信息是文本信息处理中的重要问题。有限状态机算法能够描述对象在生命周期内所经历的状态序列，作为一种有效的信息提取方法，被广泛用于多个领域。朱华炳等［1］在数控技术领域，通过分析STEP-NC数据流和STEP-NC程序模型，提出了基于有限状态机的STEP-NC信息提取系统实现方案；吴春成等［2］在航空领域有限状态机算法的基础上，对飞行控制软件进行测试，提高了检测错误的能力；王焕民等［3］在铁路运输领域，以有限状态机模型为基础，开发了一套检修业务流程建模与管理系统。在此，通过对目标文本进行预处理，获得关键词集，再对关键词集中的对象关键词进行特征信息提取，获得关键词特征集，结合模式识别或机器学习相关方法，达到快速提取文本中特定信息的目的。

2 相关技术

文本关键信息提取是自然语言处理专业中重要的研究内容，又称信息抽取，是把文本中包含的非结构化信息提取出来，形成结构化信息。把原始文本输入关键信息提取系统，系统输出固定格式的结构化信息表。通常，信息提取技术不需要全面理解整篇文档，只对文档中包含相关信息的部分进行解析。基于有限状态机的模式识别方法是一种经典的信息提取方法，具有速度快、准确率高、鲁棒性好等特点，广泛用于自然语言处理、信息提取的各种研究中。

2.1 有限状态机

有限状态机是一种用来进行对象行为建模的工具，主要作用是描述对象在生命周期内所经历的状态序列，以及如何响应来自外界的各种事件。在计算机科学中，有限状态机被广泛用于建模应用行为、硬件电路系统设计、软件工程、编译器、网络协议和计算与语言的研究。

2.2 正则匹配

正则表达式由美国数学家Stephen Kleene于1956年提出，又称正规表示法、正规式，主要用于描述正则集代数［4］。它是提供给计算机操作和检验所要提取字符串数据的一种强大工具，是1串特定意义字符组成的字符串，表示某种匹配的规则［5］。正则表达式最基本的3种功能是匹配、替换和提取。匹配功能是利用设定好的匹配表达式与数据文件中的目标文本进行比较，根据比较结果判断1个串是否含有某种子串、将匹配的子串做替换或者从某个串中取出符合某个条件的子串等。正则表达式匹配在文本编辑、生物信息学、模式识别等领域有重要的应用，几乎所有的主流高级语言都可以支持其运行［6］。

利用正则表达式快速匹配文本的特点进行信息提取。供电故障记录文件是非结构化的文本文件，而生产系统的记录文件是半结构化甚至非结构化的文本文件，因此利用正则表达式进行文本信息降维处理、匹配特征项，实现文本数据自动阅读和信息提取是切实可行的方法。

2.3 自然语言处理

自然语言处理是大规模文本数据自动分析的基础。常用的自然语言处理技术主要有中文分词、词性标注、未登录词识别、句法分析、文本聚类、信息提取和检索等技术［7］。自然语言处理研究提供的各种理论和工具，可以为深入分析文本内容提供可能的应用［8］。

中文分词是中文信息处理的基础，现有的分词算法大致可分为三大类：基于字符串匹配、基于理解、基于统计的分词方法。基于字符串匹配的分词方法具有算法简单、分词效率高的特点，因此常常综合运用于其他分词算法中［9］。这类算法是按照一定策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配，若在词典中找到这个字符串，则匹配成功（识别出一个词）。由于这类算法都要用到一个词典，因此查询效率是影响这类算法的一个关键因素［9］，为了快速对查询子串进行“词”判断，使用有限状态机算法对词典进行快速查询。

供电故障描述数据按结构化组织，但描述内容是文本形式，属于非结构化的数据，同时数据中包括专业术语、英文符号、数字及特殊字符等，内容相对杂乱，因此文本数据挖掘方法的选择是工作重点和难点。

3 方法设计

提出基于有限状态机的自动化特征信息提取方法，供电故障信息首先经过分词预处理，形成中文单词，然后利用基于有限状态机的匹配模型，结合正则表达式技术，进行提取匹配，提取出断电区间起始位置、终止位置和倍率系数。

3.1 问题描述

供电故障数据以结构化方式存储，包括十几个字段信息，供电区间相关信息只来自局别、线别和断电区间字段，方法实现过程中，只考虑这些字段，不与其他字段交互。

需求的目标是从相关字段中，自动提取匹配出线别、断电区间起始位置、断电区间终止位置和倍率系数。断电区间起始及终止位置，可能是某车站或某线路的某里程点；倍率系数是计算断电区间长度时，由于复线等因素影响，断电区间终止到起始位置长度需要相乘系数，例如单线铁路或只有上、下行单个行别断电的故障，倍率系数就是1，若双线铁路上、下行均同时停电，倍率系数是2。

匹配得到断电区间起始位置、终止位置和倍率系数后，再根据线路设备台账，查询断电线路中断电区间起始位置、终止位置的对应里程，用里程数差值乘以倍率系数，得到最终断电区间长度。

用L表示断点区间长度，ms表示断电区间起始里程，me表示断点区间终点里程，γ表示倍率系数，则L可表示为三者的函数，其表达式如下：

3.2 分词预处理

由于需求中所描述的问题属于中文自然语言处理问题，采用分词技术对数据进行预处理是数据处理的第一个步骤［10］。所谓中文分词是将1个汉字序列切分成多个单独的词。分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。当前主流的中文分词方法可分为三大类：基于字符串匹配、基于理解、基于统计的分词方法。

采用一种基于Trie树［11］结构的算法，Trie树也称前缀树，是一种有序树，是专门用来处理字符串匹配的数据结构，解决在1组字符串集合中快速查找某个字符串的问题。这种方法高效实现词图扫描，得到句子中汉字的所有成词可能，并且将所有成词可能的情况构成有向无环图（DAG）。在该图中查找最大概率路径，在实现过程中，不仅将字典生成Trie树，同时把每个词的出现次数转换为频率，再采用动态规划查找法，找出基于词频的最大切分组合。对于分词词典中未出现的词，即未登录词，采用Viterbi算法［12］，将问题抽象为最优选择问题，每一步的所有选择都保存了前面所有步骤到当前选择的最小总代价，以及当前代价情况下前面步骤的选择。依次计算完所有步骤后，通过回溯的方法找到最优选择路径［4］，将这种方法用于汉字成词的HMM模型，估计其成词概率，再进行分词［13］。

3.3 有限状态机匹配模型

经过分词预处理后的断电区间数据，成为单词流序列数据，适用于建立有限状态机匹配模型，对其中断电区间起始位置、终止位置和倍率系数3个信息进行提取。

由于任务是从1个结构化字段中提取3个信息，对原始数据观察，数据中自然存在特定分隔符，可以将这3部分中的1部分或2部分自然分隔，因此数据匹配时，首先对断电区间数据利用分隔符字典中定义的分隔符进行切分，使之成为2个或3个文本区段，再进行信息匹配。分隔符字典定义见表1。

表1 分隔符字典定义表

文本数据经分隔符分割后，处理成前、后2段，从前段中提取断电区间起始位置信息，从后段中提取断电区间终止位置和倍率系数信息。断电区间起始位置信息提取时，经过特殊、无效、提示字符去除，进入线路所匹配模式或线路匹配模式，在相应匹配模式中，去除非站名相关字符，匹配得相应站名。断电区间终止位置提取时，与断电区间起始位置提取步骤相同，经过特殊、无效、提示字符去除，进入线路所匹配模式或线路匹配模式，在相应匹配模式中，去除非站名相关字符，匹配得相应站名。倍率系数提取时，根据关键字，判断进入行别匹配模式或复线匹配模式，再匹配线数量，得到倍率系数。

信息提取过程，抽象为有限状态机模型，不同匹配步骤作为有限状态机的状态，根据数据特征及业务需求，抽象为9个状态，由S加数字0到8表示，有限状态机状态定义见表2。

表2 有限状态机状态定义表

匹配过程符合有限状态机状态转移过程，各状态接受不同条件输入，得到不同输出及发生状态转移，有限状态机模型状态转移见图1。

图1 有限状态机模型状态转移图

状态转移条件即输入的字符或单词，根据不同条件输入，按照状态转移图中的各有向边，由一个状态转移至另一个状态。用ε符号表示空输入，EOF表示输入结束符，状态转移条件矩阵定义见表3。

表3 状态转移条件矩阵定义表

4 试验验证

多种高级语言均支持有限状态机模型［14］，试验部分基于Python框架实现上述有限状态机模型，并对此模型准确率及运行速度开展测试，试验所用系统软、硬件环境见表4。

表4 试验环境列表

4.1 数据选取

选取某段时间内某地区高速铁路供电故障数据，对上述模型进行测试。数据以结构化方式存储，模型所处理的字段为局别、线别、断电区间共3个字段，断电区间描述中，基本涵盖生产系统中各种常见的故障描述方式。

4.2 试验结果

分别对基于Python框架的有限状态机自动识别模型进行准确率、运行速度测试，采用典型评价指标评价结果。

4.2.1 准确率

利用模型进行准确率测试，准备测试数据共200条，按批测试，每批40条，分别统计计算断电区间起始位置、终止位置和倍率系数准确率，模型提取结果与正确标签直接对比，内容完全一致，认为识别正确，任何字符不一致认为识别错误，按此计算识别准确率。模型准确率测试结果见表5。

表5 模型准确率测试结果 %

断电区间字段经过2次切分形成3个部分，断电区间起始位置识别准确率达到92.0%；由于断电区间终止位置位于文本数据中部，较易出现切分错误导致的识别不准确，虽然与断电区间起始位置识别算法相近，断电区间终止位置识别准确率大幅低于起始位置准确率，但仍能达到79.0%；倍率系数字段处于文本数据末端，受切分算法影响较小，利用有限状态机模型，也基本吻合数据，提取准确率能达到91.5%。

4.2.2 运行速度

在准确率测试中，模型运行可在短时间内完成。为进一步测试模型运行速度，选取某较大供电故障数据集，共7 000条数据，每500条作为1批数据，输入模型，测试其运行时间。

模型平均运行时间测试见图2，每500条最长运行时间27.0 ms，最短运行时间16.0 ms，平均运行时间为20.2 ms，不同批次间运行时间差距不大，基本稳定在20 ms左右，每千条数据处理时间为40 ms。

模型累积运行时间测试见图3，分3个批次测试模型处理2 000条数据的累计运行时间，3次模型处理2 000条数据执行时间分别为87.96 ms、76.94 ms和77.97 ms，每执行500条数据记录一次执行时间，可见运行时间与执行条数大致呈线性正相关关系，每500条数据执行时间约20 ms，与模型平均运行时间测试结果接近。

供电故障生产数据集条数在103数量级，根据测试结果可知，模型运行速度较快，且无需前期训练或拟合，可满足在短时间内处理大量数据特征信息提取的需求。

图2 模型平均运行时间测试

图3 模型累计运行时间测试

5 结束语

基于有限状态机的自动化特征信息提取方法，结合当前主流的自然语言处理分词技术，并利用正则匹配技术构建模式识别模型，能够处理非结构化文字描述的供电故障信息，应用于实际生产数据测试时，可准确、快速地完成断电区间特征信息提取工作，代替人工整理计算，节约时间、降低精力耗费。

供电故障断电区间自动化特征信息提取与计算方法依托于铁路信息化理念和整体框架，并且随生产系统不断更新、日趋完善，具有一定的技术含量，能产生相应的经济效益，同时践行铁路安全管理信息化、科学化，有助于提升铁路运营安全数据分析效率。