有限状态机的地址解析方法及装置

摘要

本申请提出一种有限状态机的地址解析方法和装置，其中，该方法包括：根据预配的资源字典中的多个地址类型，采用预设的语法规则描述需要解析的地址结构；通过语法规则的解释程序将地址结构翻译成状态机框架，并根据状态机框架构建第一状态机；根据资源字典中与每个地址类型对应的地址资源，构建第二状态机并将所有的第二状态机合并加环构建第三状态机；将第一状态机和所述第三状态机合并构建第四状态机，以便应用第四状态机进行解码。实现了通过规则语言和解释程序自动构建地址解析状态机，并且随着拓扑结构的变化适应调整状态机，提高了地址解析的灵活性，可扩展性，以及通用性。

说明书

技术领域

本申请涉及信息处理技术领域，尤其涉及一种有限状态机的地址解析方法及装置。

背景技术

很多应用场景都会涉及地址解析过程。例如：在口语交互的酒店预订产品中，用户提 供想要预订的地址，然后系统通过解码器对用户提供的地址进行解析，进而根据解析结果 在数据库中进行相关查询。

目前相关的地址解析过程是根据地址资源来直接构建对应的状态机，然后通过解码器 对输入的地址信息进行解析。

然而，当所构建的地址解析状态机的设计极为复杂，并且其拓扑结构又经常根据需求 而发生变动时，需要耗费大量时间重新手写状态机，过程繁杂效率低下，由此可见，目构 建的地址解析的状态机缺乏灵活性，可扩展性，通用性。

发明内容

本申请旨在至少在一定程度上解决相关技术中的技术问题之一。

为此，本申请的第一个目的在于提出一种有限状态机的地址解析方法，该方法实现了 通过规则语言和解释程序自动构建地址解析状态机，并且随着拓扑结构的变化适应调整状 态机结构，提高了地址解析的灵活性，可扩展性，以及通用性。

本申请的第二个目的在于提出一种有限状态机的地址解析装置。

为达上述目的，本申请第一方面实施例提出了一种有限状态机的地址解析方法，包括： 根据预配的资源字典中的多个地址类型，采用预设的语法规则描述需要解析的地址结构； 通过所述语法规则的解释程序将所述地址结构翻译成状态机框架，并根据所述状态机框架 构建第一状态机；根据所述资源字典中与每个地址类型对应的地址资源，构建与每个地址 类型对应的第二状态机，并将所有的第二状态机合并加环构建第三状态机；将所述第一状 态机和所述第三状态机合并构建第四状态机，以便解码器应用所述第四状态机进行地址解 码。

本申请实施例的有限状态机的地址解析方法，通过根据预配的资源字典中的多个地址 类型，采用预设的语法规则描述需要解析的地址结构；通过所述语法规则的解释程序将所 述地址结构翻译成状态机框架，并根据所述状态机框架构建第一状态机；根据所述资源字 典中与每个地址类型对应的地址资源，构建与每个地址类型对应的第二状态机，并将所有 的第二状态机合并加环构建第三状态机；将所述第一状态机和所述第三状态机合并构建第 四状态机，以便解码器应用所述第四状态机进行地址解码。由此，实现了通过规则语言和 解释程序自动构建地址解析状态机，并且随着拓扑结构的变化适应调整状态机结构，提高 了地址解析的灵活性，可扩展性，以及通用性。

为达上述目的，本申请第二方面实施例提出了一种有限状态机的地址解析装置，包括： 描述模块，用于根据预配的资源字典中的多个地址类型，采用预设的语法规则描述需要解 析的地址结构；第一构建模块，用于通过所述语法规则的解释程序将所述地址结构翻译成 状态机框架，并根据所述状态机框架构建第一状态机；第二构建模块，用于根据所述资源 字典中与每个地址类型对应的地址资源，构建与每个地址类型对应的第二状态机，并将所 有的第二状态机合并加环构建第三状态机；第三构建模块，用于将所述第一状态机和所述 第三状态机合并构建第四状态机，以便解码器应用所述第四状态机进行地址解码。

本申请实施例的有限状态机的地址解析装置，通过根据预配的资源字典中的多个地址 类型，采用预设的语法规则描述需要解析的地址结构；通过所述语法规则的解释程序将所 述地址结构翻译成状态机框架，并根据所述状态机框架构建第一状态机；根据所述资源字 典中与每个地址类型对应的地址资源，构建与每个地址类型对应的第二状态机，并将所有 的第二状态机合并加环构建第三状态机；将所述第一状态机和所述第三状态机合并构建第 四状态机，以便解码器应用所述第四状态机进行地址解码。由此，实现了通过规则语言和 解释程序自动构建地址解析状态机，并且随着拓扑结构的变化适应调整状态机结构，提高 了地址解析的灵活性，可扩展性，以及通用性。

附图说明

本发明上述的和/或附加的方面和优点从下面结合附图对实施例的描述中将变得明显 和容易理解，其中：

图1是本申请一个实施例的有限状态机的地址解析方法的流程图；

图2为第一状态机的结构图；

图3为城市地址类型的第二状态机的结构图；

图4为区地址类型的第二状态机的结构图；

图5为商圈地址类型的第二状态机的结构图；

图6为第三状态机的结构图；

图7为第四状态机的结构图；

图8为样例状态机的结构图；

图9是本申请另一个实施例的有限状态机的地址解析方法的流程图；

图10是本申请一个实施例的有限状态机的地址解析装置的结构示意图；

图11是本申请另一个实施例的有限状态机的地址解析装置的结构示意图。

具体实施方式

下面详细描述本申请的实施例，所述实施例的示例在附图中示出，其中自始至终相同 或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描 述的实施例是示例性的，旨在用于解释本申请，而不能理解为对本申请的限制。

下面参考附图描述本申请实施例的有限状态机的地址解析方法及装置。

图1是本申请一个实施例的有限状态机的地址解析方法的流程图。

如图1所示，该有限状态机的地址解析方法包括：

步骤101，根据预配的资源字典中的多个地址类型，采用预设的语法规则描述需要解 析的地址结构。

具体来说，本发明实施例提供的有限状态机的地址解析方法可以应用于提供地址解析 服务的应用中，该应用可以根据实际需要进行选择。例如包括：导航应用、查询预定应用 等，本实施例对此不作限制。

根据具体的应用需求预先配置好资源字典，其中，资源字典包括：多个地址类型，以 及与每个地址类型对应的地址资源。

需要说明的是，资源字典中的地址类型和对应的地址资源可以根据具体场景进行配置 和调整，本实施例对此不作限制。为了更加清楚的说明资源字典的配置过程，以三个地址 类型为例解释说明如下，其中，这三个地址类型具体包括：城市，区，商圈，以文件的形 式进行存储，具体参见表1：

表1

需要说明的是，表1所示的资源字典的内容仅为距离说明，可以根据具体情况进行配 置和调整。

根据上述预先配置的资源字典中的多个地址类型，采用预设的语法规则描述需要解析 的地址结构。

由于随着实际应用的需要，地址解析状态机的拓扑结构经常发生变化。传统的方法在 面对结构上的变化时，需要大量的更改往往费时费力，还十分容易出错，不够灵活。本实 施例提供的有限状态机的地址解析方法，专门设计了一个语法规则，采用预设的语法规则 描述需要解析的地址结构。简明的语法规则大大简化了状态机的高层设计。

可以理解的是，根据资源字典的具体内容和具体需求，采用预设的语法规则描述的地 址结构不同，变化非常多。继续以表1的资源字典为例，采用预设的语法规则描述需要解 析的地址结构，具体如下：

对表1中的city，district，business进行结构设计，合法的地址解析需求包括如下 几种形式：

a.city直接跟district然后再跟business，就比如北京市海淀区五道口；

b.city直接跟business，比如北京市五道口；

c.district后跟business，比如海淀区五道口。

为了针对上述情况设计对应的高层状态机，采用预设的语法规则描述对应的地址结构 具体如下：

city->district->business；

city->business；

district->business。

这样就完成了状态机的地址结构的高层设计。

由此可见，在实际情况中，状态机地址结构的设计很可能根据需求而产生变化。针对 表1，如果需要在地址结构中加入省份的解析，那么对本技术而言，只需要在资源字典中 配置省份类型的资源，然后在状态机的高层设计中增加一些描述语言即可，比如

province->city->district->business。

由此可见，这样便能完成自动构建状态机的任务，这种方式可以极大的面对实际情况 中的各种变更，也将极大的简化任务，提高处理效率。

步骤102，通过所述语法规则的解释程序将所述地址结构翻译成状态机框架，并根据 所述状态机框架构建第一状态机。

具体地，需要通过语法规则的解释程序对上述的语法规则进行解释，将上述描述的地 址结构翻译成状态机框架。其中，所述状态机框架包括：每个地址类型的分割标签；与每 个分割标签对应的开始标识、中间过程标识以及结束标识，以及状态机中的起始节点和终 止节点。

为了更加清楚的说明解释程序对上述语法规则的翻译过程，继续以表1为例，翻译过 来的状态机在本发明中如下：

01startcity+start；

12city+corecity+end；

23startdistrict+start；

34district+coredistrict+end；

45startbusiness+start；

56business+corebusiness+end；

24<eps><eps>。

其中，+start表示某项分割标签开始，+core表示该标签的中间过程，这项标签是抽 象的，因为在最后的合成时，+core会跟具体的词典中的实例结合展开，+end表示该项标 签的结束，<eps>表示空边。前面的数字编号分别表示起始节点和终止节点，每一行边是状 态机的一条边，这是真实的状态机的设计方式。

由此可见，手工设计这样的状态机是非常复杂的，真实的数据例子远比当前举例说明 的复杂，对手工设计进行更改非常耗费时间和精力，本实施例是从解释程序转换过来的状 态机属于最终要构建的状态机的框架，大大提高了构建效率。

进而，根据解释程序根据地址结构翻译成的状态机框架构建第一状态机，在本发明中 也称为高层状态机(即本发明中涉及的第一状态机)。图2为第一状态机的结构图，为了后 续表述方便，将第一状态机记为FST1。

由此可见，在对高层的状态机进行设计时，只需要按照一些事先规定好的语法规则进 行书写，这相当于在人更方便的描述语言和构建工具之间加了一层解释程序，而这层解释 程序负责将人更容易编写的设计语言转换为构建工具识别的描述语言。这样，状态机的设 计将可以用更加简洁的规则语言的描述。

步骤103，根据所述资源字典中与每个地址类型对应的地址资源，构建与每个地址类 型对应的第二状态机，并将所有的第二状态机合并加环构建第三状态机。

具体地，首先，根据资源字典中与每个地址类型对应的地址资源，构建与每个地址类 型对应的第二状态机。

然后，将所有的第二状态机合并加环构建第三状态机。

为了更加清楚的说明如何根据资源字典中与每个地址类型对应的地址资源，构建与每 个地址类型对应的第二状态机，继续以表1为例解释说明如下：

根据资源字典中三个地址类型分别对应的地址资源，分别构建与每个地址类型对应的 状态机(即本发明中涉及的第二状态机)。

首先，将与city地址类型对应的资源展开进行构图，图3为城市地址类型的第二状态 机的结构图，为了后续描述方便，将与城市类型对应的第二状态机记为FST2。参见图3， 其中start表示该项city的开始，一直到city+core结束。

接着，将与distirct地址类型对应的资源展开进行构图，图4为区地址类型的第二状 态机的结构图，为了后续描述方便，将与区地址类型对应的第二状态机记为FST3。参见图 4，其中start表示该项distirct的开始，一直到distirct+core结束。

接着，将与business地址类型对应的资源展开进行构图，图5为商圈地址类型的第二 状态机的结构图，为了后续描述方便，将与商圈地址类型对应的第二状态机记为FST4。参 见图5，其中start表示该项business的开始，一直到business+core结束。

进而，将FST2，FST3，FST4进行合并(即在多个第二状态机之间执行并操作)，加环 (首尾相连)，得到第三状态机，图6为第三状态机的结构图，为了后续描述方便，将第三 状态机记为FST5。

步骤104，将所述第一状态机和所述第三状态机合并构建第四状态机，以便解码器应 用所述第四状态机进行地址解码。

具体地，将所述第一状态机和所述第三状态机合并构建第四状态机，并将第四状态机 置于解码器中。

继续参见上述实施例，将FST5与FST1进行合成，得到最终的状态机(即本发明涉及 的第四状态机)。其中，图7为第四状态机的结构图，为了后续描述方便，将第四状态机记 为FST6。

进而，当解码器接收到待进行解析的地址信息时，应用第四状态机对地址信息进行地 址解码。

本申请实施例的有限状态机的地址解析方法，根据预配的资源字典中的多个地址类型， 采用预设的语法规则描述需要解析的地址结构；通过所述语法规则的解释程序将所述地址 结构翻译成状态机框架，并根据所述状态机框架构建第一状态机；根据所述资源字典中与 每个地址类型对应的地址资源，构建与每个地址类型对应的第二状态机，并将所有的第二 状态机合并加环构建第三状态机；将所述第一状态机和所述第三状态机合并构建第四状态 机，以便解码器应用所述第四状态机进行地址解码。由此，实现了通过规则语言和解释程 序自动构建地址解析状态机，并且随着拓扑结构的变化适应调整状态机结构，提高了地址 解析的灵活性，可扩展性，以及通用性。

进一步地，为了提高解码的准确性，针对步骤101具体包括：

采用预设的语法规则描述需要解析的地址结构，以及与地址结构对应的权重信息；

针对步骤102具体包括：

通过所述语法规则的解释程序将所述地址结构和所述权重信息，翻译成携带地址权重 的状态机框架，并根据所述状态机框架构建携带地址权重的第一状态机。

具体地，在上述的地址解析状态机的构图过程中，预先通过语法规则设置地址权重， 进而设计带权重的状态机来进行切分决策，以便当解码器解码选择权重分数和最大的作为 解码结果。

为了更加清楚的说明上述过程，通过图8所示实施例说明如下：

图8为样例状态机的结构图，为了后续描述方便，将样例状态机记为WFST1。

参见图8，作为一个例子，假设city字典有城市A，business字典有商圈名B，AB。 将地址解析的状态机按照尽可能对输入串进行切分的原则设计，可以通过在city, business设置权重为1达到此目的，假设现在有一个输入串是AB，那么在WFST1上可以搜 索到的路径有如下两条：

第一条路径(节点编号构成)：01325，权重和为1+1＝2；第二条路径(节点编 号构成)：0245，权重和为1。

当选择权重最大的那条路径即第一条那么输出便是A(city)B(business)，这也是对输 入串尽可能切分的一种设计。如果将状态机设计为尽可能匹配输入串的长度，那么将上述 状态机的权重选择改为选择路径权重最小的即可，这样输入串AB的输出便是 AB(business)，这样便是尽可能的匹配输入串。

无论上述哪种设计策略，仅仅一种切分原则都无法避免误切分的问题，假设采用尽可 能切分策略，且A＝北京,B＝工商银行，在实际情况中AB很可能不分开更好。所以，仅仅依 靠带权重的状态机来设计切分原则，这样的解码结果准确率不够高。仅依靠带权重的状态 机的另一个缺点是对语义无法进行检查，比如输入串是上海市天安门，它的输出就是上海 市(city)天安门(business)。这个地址串符号地址的结构，即符号地址语法本，但语义上 不正确，因为上海没有天安门，但当前的状态机无法核查。

因为，为了解决上述问题，进一步地提高解码的准确性，在解码器中设置语言模型结 合权重信息进行解码，参见图9的解码过程。

图9是本申请另一个实施例的有限状态机的地址解析方法的流程图。

如图9所示，在步骤104之后，该有限状态机的地址解析方法可以还包括以下步骤：

步骤201，接收待解析的地址信息；

步骤202，应用所述第四状态机对所述地址信息进行解码。

步骤203，根据预设的权重获取解码结果的权重值。

步骤204，根据预设的语言模型对解码结果进行评分。

步骤205，根据所述评分和所述权重值进行插值处理获取解码结果。

具体地，当解码器接收到待进行解析的地址信息时，应用上述实施例构建的第四状态 机对地址信息进行地址解码。

为了保证解码结果的准确性，本实施例根据预先建立的地址语料库训练一个语言模型， 在解码过程中，对所有候选解码结果将其权重和与语言模型得分进行插值，选择得分最高 的作为解码结果。这样用语言模型来进行语义上的检查，比如上述的上海市天安门在真实 的地址中很少见，因为并不存在，所以语言模型对这个输入串的打分非常低，在和状态机 的解码路径权重和插值时就能降低这个输入串的整体得分。

本申请实施例的有限状态机的地址解析方法，通过接收待解析的地址信息，应用所述 第四状态机对所述地址信息进行解码，根据预设的权重获取解码结果的权重值，根据预设 的语言模型对解码结果进行评分，根据所述评分和所述权重值进行插值处理获取解码结果。 由此，实现了通过规则语言和解释程序自动构建的地址解析状态机，以及预设的语言模型 进行地址解析，提高了地址解析的准确性和通用性。

为了实现上述实施例，本申请还提出一种有限状态机的地址解析装置。

图10是本申请一个实施例的有限状态机的地址解析装置的结构示意图。

如图10所示，该有限状态机的地址解析装置包括：

描述模块11，用于根据预配的资源字典中的多个地址类型，采用预设的语法规则描述 需要解析的地址结构；

第一构建模块12，用于通过所述语法规则的解释程序将所述地址结构翻译成状态机框 架，并根据所述状态机框架构建第一状态机；

第二构建模块13，用于根据所述资源字典中与每个地址类型对应的地址资源，构建与 每个地址类型对应的第二状态机，并将所有的第二状态机合并加环构建第三状态机；

第三构建模块14，用于将所述第一状态机和所述第三状态机合并构建第四状态机，以 便解码器应用所述第四状态机进行地址解码。

需要说明的是，前述对有限状态机的地址解析方法实施例的解释说明也适用于该实施 例的有限状态机的地址解析装置，此处不再赘述。

具体地，所述地址结构包括以下至少之一：

城市信息、区信息、以及商圈信息；

城市信息以及商圈信息；

区信息以及商圈信息。

具体地，所述状态机框架包括：

每个地址类型的分割标签；

与每个分割标签对应的开始标识、中间过程标识以及结束标识；

状态机中的起始节点和终止节点。

在一个实施例中，

描述模块11用于：采用预设的语法规则描述需要解析的地址结构，以及与地址结构对 应的权重信息；

第一构建模块12用于：通过所述语法规则的解释程序将所述地址结构和所述权重信 息，翻译成携带地址权重的状态机框架，并根据所述状态机框架构建携带地址权重的第一 状态机。

本申请实施例的有限状态机的地址解析装置，根据预配的资源字典中的多个地址类型， 采用预设的语法规则描述需要解析的地址结构；通过所述语法规则的解释程序将所述地址 结构翻译成状态机框架，并根据所述状态机框架构建第一状态机；根据所述资源字典中与 每个地址类型对应的地址资源，构建与每个地址类型对应的第二状态机，并将所有的第二 状态机合并加环构建第三状态机；将所述第一状态机和所述第三状态机合并构建第四状态 机，以便解码器应用所述第四状态机进行地址解码。由此，实现了通过规则语言和解释程 序自动构建地址解析状态机，并且随着拓扑结构的变化适应调整状态机结构，提高了地址 解析的灵活性，可扩展性，以及通用性。

图11是本申请另一个实施例的有限状态机的地址解析装置的结构示意图，如图11所 示，基于图10所示实施例，还包括：

接收模块15，用于接收待解析的地址信息；

解码模块16，用于应用所述第四状态机对所述地址信息进行解码。

进一步地，还包括：

处理模块17，用于根据预设的权重获取解码结果的权重值，根据预设的语言模型对解 码结果进行评分，根据所述评分和所述权重值进行插值处理获取解码结果。

需要说明的是，前述对有限状态机的地址解析方法实施例的解释说明也适用于该实施 例的有限状态机的地址解析装置，此处不再赘述。

本申请实施例的有限状态机的地址解析装置，通过接收待解析的地址信息，应用所述 第四状态机对所述地址信息进行解码，根据预设的权重获取解码结果的权重值，根据预设 的语言模型对解码结果进行评分，根据所述评分和所述权重值进行插值处理获取解码结果。 由此，实现了通过规则语言和解释程序自动构建的地址解析状态机，以及预设的语言模型 进行地址解析，提高了地址解析的准确性和通用性。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示 例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者 特点包含于本申请的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述 不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以 在任一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领 域的技术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进 行结合和组合。

此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性 或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示 或者隐含地包括至少一个该特征。在本申请的描述中，“多个”的含义是至少两个，例如两 个，三个等，除非另有明确具体的限定。

流程图中或在此以其他方式描述的任何过程或方法描述可以被理解为，表示包括一个 或更多个用于实现特定逻辑功能或过程的步骤的可执行指令的代码的模块、片段或部分， 并且本申请的优选实施方式的范围包括另外的实现，其中可以不按所示出或讨论的顺序， 包括根据所涉及的功能按基本同时的方式或按相反的顺序，来执行功能，这应被本申请的 实施例所属技术领域的技术人员所理解。

在流程图中表示或在此以其他方式描述的逻辑和/或步骤，例如，可以被认为是用于实 现逻辑功能的可执行指令的定序列表，可以具体实现在任何计算机可读介质中，以供指令 执行系统、装置或设备(如基于计算机的系统、包括处理器的系统或其他可以从指令执行 系统、装置或设备取指令并执行指令的系统)使用，或结合这些指令执行系统、装置或设 备而使用。就本说明书而言，"计算机可读介质"可以是任何可以包含、存储、通信、传播 或传输程序以供指令执行系统、装置或设备或结合这些指令执行系统、装置或设备而使用 的装置。计算机可读介质的更具体的示例(非穷尽性列表)包括以下：具有一个或多个布 线的电连接部(电子装置)，便携式计算机盘盒(磁装置)，随机存取存储器(RAM)，只读 存储器(ROM)，可擦除可编辑只读存储器(EPROM或闪速存储器)，光纤装置，以及便携式 光盘只读存储器(CDROM)。另外，计算机可读介质甚至可以是可在其上打印所述程序的纸 或其他合适的介质，因为可以例如通过对纸或其他介质进行光学扫描，接着进行编辑、解 译或必要时以其他合适方式进行处理来以电子方式获得所述程序，然后将其存储在计算机 存储器中。

应当理解，本申请的各部分可以用硬件、软件、固件或它们的组合来实现。在上述实 施方式中，多个步骤或方法可以用存储在存储器中且由合适的指令执行系统执行的软件或 固件来实现。例如，如果用硬件来实现，和在另一实施方式中一样，可用本领域公知的下 列技术中的任一项或他们的组合来实现：具有用于对数据信号实现逻辑功能的逻辑门电路 的离散逻辑电路，具有合适的组合逻辑门电路的专用集成电路，可编程门阵列(PGA)，现 场可编程门阵列(FPGA)等。

本技术领域的普通技术人员可以理解实现上述实施例方法携带的全部或部分步骤是可 以通过程序来指令相关的硬件完成，所述的程序可以存储于一种计算机可读存储介质中， 该程序在执行时，包括方法实施例的步骤之一或其组合。

此外，在本申请各个实施例中的各功能单元可以集成在一个第一处理模块中，也可以 是各个单元单独物理存在，也可以两个或两个以上单元集成在一个模块中。上述集成的模 块既可以采用硬件的形式实现，也可以采用软件功能模块的形式实现。所述集成的模块如 果以软件功能模块的形式实现并作为独立的产品销售或使用时，也可以存储在一个计算机 可读取存储介质中。

上述提到的存储介质可以是只读存储器，磁盘或光盘等。尽管上面已经示出和描述了 本申请的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本申请的限制， 本领域的普通技术人员在本申请的范围内可以对上述实施例进行变化、修改、替换和变型。