CN103918027B - 用于语音应用中的最优有限状态转换机(fst)的有效渐进修改 - Google Patents

Abstract

公开了一种用于添加和删除句子的渐进修改单词级有限状态转换机(FST)的方法。确定FST中与该句子的前缀部分匹配的状态和弧的前缀子集。确定FST中与该句子的后缀部分匹配的状态和弧的后缀子集。通过将状态和弧的新序列附加到与前缀和后缀之间的句子的剩余部分相对应的FST，然后可以将新句子附加到FST中。通过将前缀子集和后缀子集之间的任何弧和状态删除，可以将现有句子从FST中删除。所产生的已修改的FST是局部有效的，但是并不满足全局优化标准，诸如最小化。

Description

用于语音应用中的最优有限状态转换机(FST)的有效渐进修改

技术领域

本发明涉及语音处理应用系统，并且更具体地，涉及在诸如自动语音识别系统和文-语转换系统的语音处理应用中使用的预编译的搜索网络。

背景技术

语音识别系统试图确定语音输入的语义含义。典型地，概率有限状态语音模型用于确定与语音输入最对应的词序列。一个常见的例子是汽车应用，其允许控制乘客车厢内的应用，诸如导航系统、语音、空调控制等等。诸如该设备中的识别任务表示诸如用户命令和城市内街道的列表的预先确定的元素，以及诸如mp3歌曲列表、来自个人数字化地址簿(例如，来自智能电话)的姓名和感兴趣的导航点的动态确定的元素的组合。对于这些应用，预期具有带有快速低延迟性能的紧凑存储有效搜索网络。

该识别任务包括多个不同的知识等级，从基本语音声音的声学形式，诸如所熟知的音素(phoneme)，到形成识别词汇中单词的音素序列，到形成识别语法中短语的单词序列。组织识别任务的一种有效且方便的方式是基于有限状态机的使用，诸如有限状态接受器(FSA)和有限状态转换机(FST)。为了便利，下述讨论中使用术语FST，然而，不是任何特定的严格意义，而是以通用的包含的方式，其也能够应用在FSA和其他特定形式的有限状态机的许多方面。附图1示出了一个简单FST的特定的示例，所述FST解析单词等级符号集合：{AAA，BA，AAB}；参见例如Jurafsky&Martin编写的Speech and LanguageProcessing(语音和语言处理)，Prentice Hall2001，第33-83页，ISBN0-13-095069-6；其通过引用被包含在此。

在诸如智能电话的移动平台上实施语音处理系统特别受到有限的可用资源的挑战。实施一些优化以提高速度、精确率和/或有限存储器的使用。除此之外，FST允许声学信息(HMM集合)、单词发音、语言模型和识别语法的单独的统一的表示。由于该统一表示，导致在遍历搜索网络期间，可以执行计算花费不大的计算，而其他计算花费大的优化能够被卸下到预编译阶段进行。FST的静态编译的优化使用的最广泛的四个包括确定化、最小化、权重和标签推送；参见例如Mohri编写的Minimization of Sequential Transducers(序列转换机的最小化)，(5^th Annual Symposium on Combinatorial Pattern Matching1994，关于组合模式匹配的第5年度论文集中发表，1994年)；通过引用被包含在此。

不管确定化，现有的FST优化是全局的，也就是说，需要作为一个整体来访问FST，并且因而，不能在渐进修改搜索网络的语音应用中应用。渐进将句子添加到单词级FST的一些理论性方法在Crochemore和Giambruno编写的On-Line Construction Of A smallAutomaton for A Finite Set of Words(用于有限单词集合的小型机器人的在线建立)，出版于Prugue Stringology Conference2009中更加全面地被描述；通过引用被包含在此。

发明内容

本发明的实施例是关于通过增加和删除句子来渐进修改单词级有限状态转换机(FST)的方法。确定在FST中与句子的前缀部分匹配的状态和弧的前缀子集。确定在FST中与句子的后缀部分匹配的状态和弧的后缀子集。然后通过将状态和弧的新序列附加到与前缀和后缀之间的句子的剩余部分相对应的FST，将新句子添加到FST。通过将前缀子集和后缀子集之间的任何状态删除，可以从FST中删除现有句子。产生的修改的FST是局部有效的，但是并不满足全局优化标准，诸如最小化标准。

FST可以是语音应用FST，并且在语音应用的在线操作期间能够动态地从FST中添加或从FST中删除句子。为了删除现有句子，在部分匹配处理(“模糊删除”)中可以将各步骤重复一次或多次，以从FST中删除现有句子的多个实例。能够使用哈希表来确定前缀子集和/或后缀子集，例如，特别的双向使用的哈希表。全局优化标准可以包括FST最小化标准。

附图说明

图1示出了一个特定FST的一个简单示例。

图2A-C示出了根据本发明的一个实施例，将句子添加到FST中的示例。

图3A-C示出了将新状态添加到现存FST中用于共享后缀的示例。

图4A-B示出了FST的全局非最小性的示例。

图5A-B示出了使用精确匹配处理从现有FST中删除句子的示例。

图6A-B示出了用于从现有FST中删除句子的部分匹配处理的示例。

图7示出了根据本发明的一个实施例，使用修改的FST设置的系统的实施例的基本架构。

具体实施方式

本发明的各种实施例是针对使用稍劣于全局优化的局部优化有效地允许FST的动态修改的技术；例如，基于渐进的局部最小化将句子添加到单词级FST或从单词级FST中删除句子。局部最小化的性能是最小化的弱化版本，其只应用于后缀路径，在其上所有状态具有不超过一个弧的扇出(fan-out)。给定长度是N的句子，基于O(N)的折算复杂度(amortized complexity)，也就是说，实施时需要花费不超过c*N个步骤，其中c是常数，而不是N²个步骤，本发明的具体实施例将句子添加到FST或从FST中删除句子。这可以被用于渐进编写FST，其与全局优化的FST几乎一样地有效地将语音解码为文本，并且同样帮助减少了用于FST的(离线)静态编译所耗费的存储器。尽管下面的讨论是关于语音识别应用的，但是该方法可以扩展到任何需要渐进建立时间或空间有效的FST的应用，例如，文语转换，文本处理，等等。

图2A-C示出了根据本发明的一个实施例，将句子添加到FST的示例，其中基于共享新句子的前缀和后缀和现有的FST中已存在的那些，其具有线性时间复杂度(NB：再次如上面所解释的，在本文中，FSA和FST之间形式上的区别实际上是微不足道的，其中为了简化图，来自FST的输入/输出弧标签对被给定单一的标签)。图2A示出了句子ABC的简单的现有的单词级FST。为了将新句子ADC添加到该FST，首先，确定FST中状态和弧的前缀子集与该新句子的前缀部分匹配。在该特定情况中，添加新的句子ADC的现有的前缀子集可以被确定为，如图2B所示的，现有状态0和1以及它们的连接弧A。接下来，确定FST中状态和弧的后缀子集与该新句子后缀部分匹配。在新句子ADC的情况下，后缀子集应该是现有的状态2和3以及它们的连接弧C。然后通过将状态和弧的新序列添加至前缀和后缀之间句子的剩余部分相对应的FST中，可以将该新句子添加至FST中。在添加ADC的情况下，通过在状态1和2之间添加弧D来完成上述，如图2C所示。

产生的修改的FST仅在只添加了不存在的状态/弧的情况下局部有效，但是它不满足全局优化标准，诸如最小化。然而，它至少满足较弱的渐进最小化。使用哈希表来确定前缀子集和/或后缀子集。例如，O(1)线性时间复杂度的前缀哈希表被使用，使得：f(状态，弧标签)→目标状态，从而确保整体复杂度将不会差于O(N)。并且，执行各个步骤的特定顺序不重要。

图3A-C示出了将新的状态添加到现有FST用于共享后缀的另一个示例。图3A示出了句子AAA的现有FST。为了添加新句子BA，通过使用状态2并添加从状态0到状态2的新弧B来共享后缀A，如图3B所示。然后，为了添加另一个新句子AAB，添加状态4，其接收前缀子集AA，从状态2到状态3的现有弧A从状态2到状态3被重复(解析现有的句子AAA)，并且添加新弧4B3，以完成新路径AAB，如图3C所示。

在一些点处，尽管该方法是局部有效的，但是增长的FST变得全局非最小。例如，如果图3C中已修改的FST要添加另一个新句子BB，那么将确认现有的B前缀，以及从状态2到状态3添加的新弧B，如图4A所示。但是，该新FST不是全局最小化的，因为状态4将不再需要，并且应该被删除，如图4B所示，其仍然能够正确解析所有以及仅AAA，BA，AAB和BB。但是，处理的容易性要超过全局非最小化的小的渐进损失。

除了向现有FST添加句子之外，通过删除前缀子集和后缀子集之间的任何弧和状态；例如，通过用于以后使用的“空”列表，还可以从FST中删除现有句子。在与该删除处理关联地，哈希表是有用的，例如，前缀哈希表能够快速访问潜在匹配的起始状态。这样：p→O(p)访问哈希表，其匹配输入标签p。只有废弃的弧才需要被删除。

从现有FST中删除句子的一个特定处理可以基于精确匹配的方法来实现，如图5A-B所示。图5A示出了解析句子AAA和BA的现有FST。为了删除句子，首先，任何剩余的前缀和/或后缀必须被确定和保留。例如，为了删除句子AAA(和保留BA)，没有保留前缀，但是BA对应的A后缀被确认和保留，因此后缀子集(2，A，3)被保留(即，状态2和状态3以及它们之间的弧(边)A：同时删除AA的路径的剩余部分：状态1和弧和(如图5B所示的(-1))。

弧/状态删除步骤可以在局部匹配处理中被重复一次或多次(例如，对于重复的测试是基于检查哈希表中的冲突)，以从FST中删除现有句子或句子片段的多个实例。例如，图6A示出了与图5A所示一样的现有的FST，其用于解析句子AAA和BA。为了删除现有的部分句子，*A*，第一个实例在已删除(-1)的弧中找到，然后该方法重复，接下来删除弧然后删除弧直至部分句子*A*的所有实例已被确认和删除，如图6B所示。再一次，例如，使用已修改的前缀哈希函数“f(弧标签)→目标状态”，对于实施哈希表可以是有用的。该部分匹配方法能够大大增加冲突数目以便使句子添加可能不再足够有效。使用仔细选择的哈希函数和组访问(添加，删除)可能是有帮助的，这使得产生的数据结构只因哈希函数而不同。

图7示出了根据本发明的一个实施例，使用修改的FST设置的系统的实施例的基本架构，在语音应用FST情形下，在语音应用的在线操作期间能够动态添加和删除句子，也就是说，在运行期间可以修改该系统。在语音应用中，编译器703通过HMM单元序列702(即，声学模型)执行渐进最小化单词级FST701(即，语言模型)的运行时间扩展来创建HMM单元-到-单词FST704(在其上编译器703也执行确定化和局部最小化)用于未知的语音输入的语音识别。并且，尽管HMM单元-到-单词FST704如上述内容(即，在识别期间)被渐进创建而不是严格意义上全局最小化，但是它对于商业应用仍然是足够紧凑和有效的，并且避免了附加的计算。在一些实施例中，运行时间扩展可以是可选的步骤，其可以被执行或不被执行。HMM-单元-到-单词FST也可以直接使用渐进最小化被创建。但是，由于诸如冗长的发音(和相同的使用超过一次)的各种因素，导致该方法可能需要更多的开销用于添加的/删除的步骤。因而，由于此原因，特定具体实施例选择在识别期间动态扩展转换本(transcription)。

可以通过任何传统的计算机编程语言全部或部分地实现本发明的实施例。例如，可以通过面向过程的编程语言(例如，“C”)或面向对象编程语言(例如，“C++”、Python)实现优选的实施例。本发明的可替换实施例被实现为预编程的硬件元件，或其他相关组件，或硬件和软件组件的组合。

实施例全部或部分地被实现为在计算机系统中使用的计算机程序产品。该实施可以包括一系列计算机指令，其或固定在有形介质上，诸如计算机可读介质(例如，软盘、CD-ROM、ROM，像“闪存ROM”的电可擦除ROM，或者固定盘)或经由调制解调器或其他接口设备可传送到计算机系统，诸如经过介质连接到网络的通信适配器。该介质或是一有形介质(例如，光的或模拟通信传输线路)或使用无线技术实现的介质(例如，微波的，红外的或其他传输技术)。该一系列计算机指令包括实施在此这里先前所描述的与该系统有关的全部或部分功能。本领域技术人员应该理解，这些计算机指令可以通过很多编程语言被编写成很多程序语言以用于配合许多计算机架构或操作系统使用。此外，这些指令可以存储在任何存储器设备中，诸如半导体、磁的、光的或其他存储器设备上，并且可以使用通过任何通信技术被发送，诸如光的、红外的、微波的或其他传送传输技术。可以预想到预期，这样的一个计算机程序产品可以被分发作为一可移动被分布于具有所附的打印或电子文档(例如，套装软件(shrink wrapped software))的可移动介质，预加载有计算机系统(例如，在系统ROM或固定盘上)，或通过网络(诸如，因特网或万维网)从服务器或电子公示板分发。当然，本发明一些实施例可以被实现为软件(例如，计算机程序产品)和硬件两者的组合。本发明的其它实施例仍然被全部实现为硬件，或全部实现为软件(例如，计算机程序产品)。

尽管此处已公开了本发明的各种示例性实施例，但对本领域技术人员显而易见的是，在不背离本发明的真实保护范围的情况下，可以做出各种改变和修改以完成本发明的一些优点。

Claims (9)

1.一种把新句子添加到具有多个状态和连接弧的单词级有限状态转换机FST的方法，所述方法包括：

使用哈希表确定与所述新句子的前缀部分匹配的在所述FST中现有的状态和弧的前缀子集；

把与所述新句子的所述前缀部分之后的剩余部分相对应的状态和弧的新序列附加到所述FST；

使用哈希表确定与所述新句子的后缀部分相对应的在所述FST中现有的状态和弧的后缀子集；以及

把所述后缀部分之前的所述新序列的部分连接到所述后缀子集以创建修改的FST，所述修改的FST包括所述新句子而不满足全局优化标准。

2.根据权利要求1所述的方法，其中，所述FST是语音应用FST。

3.根据权利要求2所述的方法，其中，在所述语音应用的在线操作期间将所述新句子动态地添加到所述FST。

4.根据权利要求2所述的方法，其中，在离线编译处理期间将所述新句子添加至所述FST。

5.根据权利要求2所述的方法，进一步包括：

动态地扩展所述修改的FST以用于语音应用。

6.一种从具有多个状态和连接弧的单词级有限状态转换机FST中删除现有句子的方法，所述方法包括如下步骤：

使用哈希表确定与所述现有句子的前缀部分匹配并且与所述FST的至少另一个句子相对应的在所述FST中的状态和弧的前缀子集；

使用哈希表确定与所述现有句子的后缀部分匹配并且与所述FST的至少另一个句子相对应的在所述FST中的状态和弧的后缀子集；

从所述FST中删除在所述前缀子集和所述后缀子集之间的任何状态和弧以创建修改的FST，所述修改的FST没有所述现有句子并且不满足全局优化标准。

7.根据权利要求6所述的方法，其中，所述FST是语音应用FST。

8.根据权利要求7所述的方法，其中，在所述语音应用的在线操作期间从所述FST中动态地删除所述现有的句子。

9.根据权利要求6所述的方法，其中，在部分匹配处理中重复各所述的步骤一次或多次以从所述FST中删除所述现有句子的多个实例。