用于选择性消除非确定性有限自动机的不确定性的方法、服务器、终端装置及计算机可读介质

摘要

本发明提供一种选择性地消除非确定性有限自动机的不确定性的方法，包括以下步骤：(a)将非确定性有限自动机内的状态中的、所算出的从特定状态移动而到达的概率为最高的状态决定为最大概率状态；(b)判断在所述非确定性有限自动机内第1迁移集合和第2迁移集合间是否存在至少一个共同迁移，所述第1迁移集合由使所述最大概率状态移动到状态i的迁移组成，所述第2迁移集合由使所述最大概率状态移动到状态j的迁移组成；(c)若判断为所述第1迁移集合和所述第2迁移集合间存在至少一个所述共同迁移，则从所述第1迁移集合及所述第2迁移集合中分别排除所述共同迁移，并生成状态k，所述状态k是通过仅由所述至少一个共同迁移组成的共同迁移集合而从所述最大概率状态移动后到达的状态，且所述状态k被新追加到所述非确定性有限自动机内。

说明书

技术领域

本发明涉及用于选择性地消除非确定性有限自动机的不确定性的方法、 服务器、终端装置及计算机可读介质。更具体地说，本发明涉及，筛选非确 定性有限自动机的字符串查找速度降低的原因即导致激活状态增加的迁移， 消除其不确定性，从而更有效地使用有限的内存资源的方法、服务器、终端 装置及计算机可读介质。

背景技术

正则表达式(regular expression)是用于描述符合特定规则的字符串的集 合的形式语言，简称正则式，多用于在计算机这类运算装置中比较或查找字 符串时描述要查找的字符串。根据涉及正则表达式的计算机科学中的领域 ——形式语言理论，正则表达式以表示无任何内容的字符串的？，及只由一 个字符构成的正则表达式(例如a,b,c等)为基本，利用连接(abc,bbbb,baba 等)、选择(ab|c,ab|ba等)、重复(c*等)等运算符，组合基本的正则表达式， 从而可以描述多种模式的字符串。此外，因为有可能发生正则表达式过长或 者过于复杂的情况，所以也出现了为使用方便，添加了多种扩展文法的形式 的正则表达式，而按照在计算机编程语言Perl中使用的方式所实现的PCRE (Perl Compatible Regular Expressions：perl语言兼容正则表达式)或者UNIX 系列计算机操作系统的标准中定义的POSIX正则表达式等属于此范畴。

利用正则表达式查找字符串时也随着具体执行查找的方式不同，查找时 间和内存使用量会有很大差距，因此对于利用正则表达式有效地查找字符串 的方法的研究一直在进行中。

首先，作为利用正则表达式执行查找字符串的现有技术的一个例子，介 绍过将正则表达式转换为非确定性有限自动机(Nondeterministic Finite  Automata:NFA)后查找字符串的方法。

图1示例性地示出了根据现有技术转换的一般的NFA。在图1中，包含 数字的圆表示NFA的状态，箭头及与其并记的字符表示输入相应字符时沿着 箭头从一个状态移动到另一状态的迁移，包含数字的圆中由两个同心圆组成 的表示终止状态；作为从开始状态出发而迁移的结果，到达终止状态就意味 着要查找的字符串已被查找到。参照图1，要查找的字符串可以是三个字符连 续地全都为a及b之一，或可以是连续的三个字符为bad的字符串，这用正则 表达式表示就可以是“[ab]{3}|bad”，这用NFA表示则可以如图1所示。

查看利用如图1所示的NFA，从输入字符串“gjekf3jmbab0d1f”中查找想 要的字符串的过程。

首先，从开始状态的状态0开始，逐一读入输入字符串中的字符，检查 某一个状态是否移动到另一个状态。第一个字符为“g”，但是没有对应输入“g” 而引导状态0移动到另一个状态的迁移，因而继续停留在状态0。第二个字符 “j”也没有相应的迁移，因而继续停留在状态0而读取下一个字符。因此，在 这种情况下，需要检查状态是否迁移的状态，即激活状态为状态0，共1个。

按照这种方式继续停留在状态0的情况下，输入至“gjekf3jm”时随后输入 的字符为“b”，图1的NFA中输入“b”的情况下存在引导状态0移动到状态1 及状态2的迁移，所以状态0会分别移动到状态1及状态2。因此，输入“b” 之后需要检查状态是否迁移的状态，即激活状态为状态0、状态1及状态2， 共3个。

随后输入的字符为“a”，图1的NFA中，在输入“a”的情况下存在引导激 活状态即状态0移动到状态1的迁移、引导激活状态即状态1移动到状态3 的迁移、及引导激活状态即状态2移动到状态4的迁移，所以状态0、状态1 及状态2会分别移动到状态1、状态3及状态4。因此，输入“ba”之后需要检 查状态是否迁移的状态，即激活状态为状态0、状态1、状态3及状态4，共 4个。

随后输入的字符为“b”，图1的NFA中，在输入“b”的情况下存在引导激 活状态即状态0移动到状态1及状态2的迁移、引导激活状态即状态1移动 到状态3的迁移及引导激活状态即状态3移动到状态5的迁移，所以状态0 会移动到状态1及状态2，状态1会移动到状态3，状态3会移动到状态5。 因此，输入“bab”之后需要检查状态是否迁移的状态，即激活状态为状态0、 状态1、状态2、状态3及状态5，共5个。另一方面，由此到达了图1的NFA 的终止状态即状态5，因此可视为从提供的输入字符串中查找到了想要的字符 串，即，字符串“bab”。

如上所述，如图1所示的根据现有技术的NFA中对应字符的输入而存在 引导一个状态移动到两个以上状态的迁移。因此，利用根据现有技术的NFA 查找字符串时，随着查找对象的字符串中的字符逐一输入，需要检查的状态， 即，激活状态的数目会增多，而由于NFA的属性，每次输入字符时要检查所 有的激活状态，因此会发生随着激活状态的数目增加，查找速度相应地降低 的问题。

另一方面，作为利用正则表达式执行查找字符串的现有技术的另一例子， 也介绍过将非确定性有限自动机(Nondeterministic Finite Automata:NFA)转 换为确定有限自动机(Deterministic Finite Automata:DFA)后查找字符串的方 法。

利用DFA查找字符串时，激活状态数一直维持为一个，因此有能够提高 查找速度，使输入字符串处理过程单纯化的优点，然而存在将NFA转换为DFA 的过程中需要相当大的内存资源的问题。并且，要查找的字符串(即，正则 表达式)为多个或其模式复杂时，处理所需的内存使用量急剧增加，因此很 难利用DFA处理多个正则表达式或较长模式的正则表达式。尤其是，随着最 近对计算机安全性的要求提高，一般会合并要查找的多种字符串模式进行查 找，而在这种情况下正则表达式可能变得非常复杂，因此在普通的计算机内 存资源内利用DFA执行查找字符串甚至会是不可能的。

为了解决按照利用一般的DFA查找字符串的方法时可能发生的问题，也 出现了压缩DFA从而减少内存使用量的方法。即，将DFA拥有的迁移类似的 多个状态合并为一个状态，或将多个状态中共同使用的多个迁移合并为一个 迁移。然而，按照这种方法，互相并不完全相同的状态或者迁移也可能被合 并，因此可能发生无法正常处理输入字符串的情况甚至发生迁移失败的问题。 像这样发生迁移失败时需要额外的内存引用，因此即便内存使用量比压缩前 少，内存引用次数却比压缩前多，其结果无法避免查找速度的降低。

因此，需要一种使用非确定性有限自动机的情况下使激活状态数目最小 化，减少内存使用，使快速查找字符串成为可能的技术。

发明内容

技术问题

本发明的目的在于解决上述的所有问题。

此外，另一目的在于，将非确定性有限自动机(Nondeterministic Finite  Automata:NFA)内的状态中到达概率高的状态作为对象，变更NFA的状态和 迁移使其状态不会移动到互不相同的两个以上的状态，从而减少NFA的激活 状态数目并选择性地消除NFA的不确定性。

此外，另一目的在于，当最大概率状态到达终止状态或者NFA的总状态 数目超过预设值等满足规定条件时，终止不确定性消除过程，从而只在给定 的内存资源内有效地消除NFA的不确定性。

解决问题的手段

为了达到所述目的，本发明的代表性构成如下。

根据本发明的一实施方式，提供一种用于选择性地消除非确定性有限自 动机(Nondeterministic Finite Automata:NFA)的不确定性的方法，其包括以 下步骤：(a)将非确定性有限自动机内的状态中的从特定状态移动而到达的 概率的计算结果最高的状态决定为最大概率状态；(b)判断在所述非确定性 有限自动机内第1迁移集合和第2迁移集合间是否存在至少一个共同迁移， 所述第1迁移集合由使所述最大概率状态移动到状态i的迁移组成，所述第2 迁移集合由使所述最大概率状态移动到状态j的迁移组成；及(c)若判断为 所述第1迁移集合和所述第2迁移集合间存在至少一个所述共同迁移，则从 所述第1迁移集合及所述第2迁移集合中分别排除所述共同迁移，并生成状 态k，所述状态k为通过只由所述至少一个共同迁移组成的共同迁移集合而从 所述最大概率状态移动而到达的状态，且所述状态k被新追加到所述非确定 性有限自动机内。

根据本发明的另一实施方式，提供一种用于选择性地消除非确定性有限 自动机的不确定性的方法，其包括以下步骤：(a)判断在非确定性有限自动 机内第1迁移集合和第2迁移集合间是否存在至少一个共同迁移，所述第1 迁移集合由使开始状态移动到状态i的迁移组成，所述第2迁移集合由使所述 开始状态移动到状态j的迁移组成；(b)若判断为所述第1迁移集合和所述第 2迁移集合间存在至少一个所述共同迁移，则从所述第1迁移集合及所述第2 迁移集合中分别排除所述共同迁移，并生成状态k，所述状态k为通过只由所 述至少一个共同迁移组成的共同迁移集合而从所述开始状态移动而到达的状 态，且所述状态k被新追加到所述非确定性有限自动机内；及(c)对能够从 所述开始状态移动而到达的至少一个状态分别输入作为查找对象的字符串 时，分别计算从所述开始状态移动而到达所述至少一个状态的概率，并将计 算出的概率最高的所述状态决定为最大概率状态。

根据本发明的另一实施方式，提供一种用于选择性地消除非确定性有限 自动机的不确定性的服务器，其包括：最大概率状态决定部，所述最大概率 状态决定部将非确定性有限自动机内的状态中从特定状态移动而到达的概率 的计算结果最高的状态决定为最大概率状态；及激活状态消除部，所述激活 状态消除部判断在所述非确定性有限自动机内第1迁移集合和第2迁移集合 间是否存在至少一个共同迁移，所述第1迁移集合由将所述最大概率状态移 动到状态i的迁移组成，所述第2迁移集合由将所述最大概率状态移动到状态 j的迁移组成，若判断为所述第1迁移集合和所述第2迁移集合间存在至少一 个所述共同迁移，则从所述第1迁移集合及所述第2迁移集合中分别排除所 述共同迁移，并生成状态k，所述状态k为通过只由所述至少一个共同迁移组 成的共同迁移集合而从所述最大概率状态移动而到达的状态，且所述状态k 被新追加到所述非确定性有限自动机内。

根据本发明的另一实施方式，提供一种用于选择性地消除非确定性有限 自动机的不确定性的服务器，其包括：激活状态消除部，所述激活状态消除 部判断在非确定性有限自动机内第1迁移集合和第2迁移集合间是否存在至 少一个共同迁移，所述第1迁移集合由使开始状态移动到状态i的迁移组成， 所述第2迁移集合由使所述开始状态移动到状态j的迁移组成，若判断为所述 第1迁移集合和所述第2迁移集合间存在至少一个所述共同迁移，则从所述 第1迁移集合及所述第2迁移集合中分别排除所述共同迁移，并生成状态k， 所述状态k为根据只由所述至少一个共同迁移组成的共同迁移集合而从所述 开始状态移动的结果所到达的状态，所述状态k被新追加到所述非确定性有 限自动机内；及最大概率状态决定部，对能够从所述开始状态移动而到达的 至少一个状态分别输入作为查找对象的字符串时，所述最大概率状态决定部 分别计算从所述开始状态移动而到达所述至少一个状态的概率，并将所述计 算出的概率最高的状态决定为最大概率状态。

根据本发明的另一实施方式，提供一种用于选择性地消除非确定性有限 自动机的不确定性的终端装置，其包括：最大概率状态决定部，所述最大概 率状态决定部将非确定性有限自动机内状态中的从特定状态移动而到达的概 率的计算结果最高的状态决定为最大概率状态；及激活状态消除部，所述激 活状态消除部判断在所述非确定性有限自动机内第1迁移集合和第2迁移集 合间是否存在至少一个共同迁移，所述第1迁移集合由使所述最大概率状态 移动到状态i的迁移组成，所述第2迁移集合由使所述最大概率状态移动到状 态j的迁移组成，若判断为所述第1迁移集合和所述第2迁移集合间存在至少 一个所述共同迁移，则从所述第1迁移集合及所述第2迁移集合中分别排除 所述共同迁移，并生成状态k，所述状态k为通过只由所述至少一个共同迁移 组成的共同迁移集合而从所述最大概率状态移动而到达的状态，且所述状态k 被新追加到所述非确定性有限自动机内。

根据本发明的另一实施方式，提供一种用于选择性地消除非确定性有限 自动机的不确定性的终端装置，其包括：激活状态消除部，所述激活状态消 除部判断在非确定性有限自动机内第1迁移集合和第2迁移集合间是否存在 至少一个共同迁移，所述第1迁移集合由使开始状态移动到状态i的迁移组成， 第2迁移集合由使所述开始状态移动到状态j的迁移组成，若判断为所述第1 迁移集合和所述第2迁移集合间存在至少一个所述共同迁移，则从所述第1 迁移集合及所述第2迁移集合中分别排除所述共同迁移，并生成状态k，所述 状态k为根据只由所述至少一个共同迁移组成的共同迁移集合而从所述开始 状态移动的结果所到达的状态，且所述状态k被新追加到所述非确定性有限 自动机内；及最大概率状态决定部，对能够从所述开始状态移动而到达的至 少一个状态分别输入作为查找对象的字符串时，所述最大概率状态决定部分 别计算从所述开始状态移动而到达所述至少一个状态的概率，并将所述计算 出的概率最高的状态决定为最大概率状态。

此外，进一步提供实现本发明的其它方法、服务器、终端装置及用于记 录用来执行所述方法的计算机程序的计算机可读介质。

技术效果

根据本发明，可以减少非确定性有限自动机的激活状态数目并选择性地 消除NFA的不确定性，从而可达到利用NFA查找字符串时能够减少内存使用 量并提高查找速度的效果。

此外，根据本发明，NFA的不确定性消除过程在最大概率状态到达终止 状态之前，跟踪最大概率状态并消除对于相应状态的不确定性，因此可分轻 重地消除NFA不确定性，从而使不确定性消除效率最高。

附图说明

图1示例性地示出了根据现有技术转换的一般的NFA。

图2示例性地示出了根据本发明一个实施例的字符串查找服务器的内部 组成。

图3至图5示例性地示出了根据本发明的一个实施例消除NFA不确定性 的过程。

图6示出了利用图1的一般的NFA查找字符串的情况，与利用图5的根 据本发明选择性地消除了不确定性的NFA来查找字符串的情况的比较结果。

附图标记

100：字符串查找服务器

110：NFA获取部

120：不确定性消除部

121：最大概率状态决定部

122：激活状态消除部

130：查找执行部

140：通信部

150：控制部

具体实施方式

下述的对于本发明的详细描述，参照了示例性地示出本发明可实施的特 定实施例的附图。这些实施例的描述详细到足够使本领域的技术人员实施本 发明。本发明的多种实施例虽互不相同，但并非互相排斥。例如，在此所记 载的与一个实施例相关的特定形状、结构及特性在不脱离本发明的思想及范 围的情况下能以其它实施例实现。此外，应理解各公开的实施例内的个别组 成要素的位置或配置在不脱离本发明的思想及范围的情况下可进行变更。因 此，下述的详细描述不是取限定的意思，而本发明的范围，如果恰当地说明， 应当跟等同于权利要求项所要求的所有范围一起，只由所附的权利要求书而 确定。附图中类似的标号在多个方面中表示相同或类似的功能。

下面，为了使本发明所属的技术领域内具备一般知识的人员容易实施本 发明，参照附图对本发明优选的实施例进行详细描述。

字符串查找服务器的组成

下面，查看为实现本发明而执行重要功能的字符串查找服务器的内部组 成及各组成要素的功能。

根据本发明的一个实施例，个人电脑(例如，台式电脑、笔记本电脑等)， 服务器、工作站、PDA、WebPAD、移动电话、智能手机等，只要是具备内存 装置并搭载微处理器因而具有运算能力的装置完全都能采用为本发明的字符 串查找服务器100。

图2示例性地示出了根据本发明一个实施例的字符串查找服务器的内部 组成。

参照图2，根据本发明一个实施例的字符串查找服务器100可包括：NFA 获取部110、不确定性消除部120、查找执行部130、通信部140及控制部150； 其中，不确定性消除部120可包括最大概率状态决定部121及激活状态消除 部122。根据本发明的一个实施例，NFA获取部110、不确定性消除部120、 查找执行部130、通信部140及控制部150中至少一部分可以是与外部系统(未 图示)进行通信的程序模块。这种程序模块能够以操作系统、应用程序模块 及其它程序模块的形式包含在字符串查找服务器100中，能够以物理形式存 储在各种公知的存储装置中。此外，这种程序模块也可以存储在能与字符串 查找服务器100进行通信的远程存储装置中。另一方面，这种程序模块包括 根据本发明执行下述的特定工作或者实行特定抽象数据类型的例程、子例程、 程序、物件、组件、数据结构等，但并不局限于此。

首先，根据本发明的一个实施例，NFA获取部110执行如下功能：获取 与作为查找对象的正则表达式相对应的NFA。在此，可以设想作为查找对象 的正则表达式转换成NFA之后才由NFA获取部110获取的情况(在这种情况 下转换过程会由规定的正则表达式转换部(未图示)执行)，也可以设想作为 查找对象的正则表达式本身由NFA获取部110获取后再由NFA获取部110转 换成NFA的情况。一般来说，NFA由状态集合S、迁移集合Σ、迁移函数δ、 开始状态s0，终止状态集合F组成。其中，开始状态和终止状态都属于状态 集合S。并且，如在本发明中，如果是利用正则表达式查找字符串的情况，则 输入文字可相当于任意的ASCII码值，因此迁移集合Σ可以为{0,1,2,…,255}。

为了将正则表达式转换为NFA，需要规定的正则表达式转换技术，而这 样的正则表达式转换技术，可参照由A.Bruggemann-Klein所著并收录在1993 年的著作“Theoretical Computer Science”中的论文“Regular expressions into  finite automata”(应认为所述论文内容全部包含在本说明书中)。所述论文记 载了将正则表达式转换为较单纯形式的自动机——Glushkov自动机的方法。 当然，可适用于本发明的正则表达式转换技术并不局限于所述论文中所记载 的方法，而是可适用多种变形例来实现本发明。例如，根据本发明一个实施 例的正则表达式转换部可将正则表达式转换为Thompson自动机、Follow自动 机、Antimirov自动机等不同形式。以下，为了维持对发明的详细描述的一贯 性，以Glushkov自动机为基准描述本发明。

其次，根据本发明的一个实施例，不确定性消除部120执行如下功能： 在利用由正则表达式转换的NFA查找字符串的过程中，使激活状态的增加最 小化，从而消除NFA的不确定性。

更具体地，根据本发明一实施例的不确定性消除部120的最大概率状态 决定部121可决定NFA内的状态中随着输入字符串的输入而到达的概率高的 最大概率状态(其中，最大概率状态并不意味着在所有状态中具有最高概率 的状态，而是意味着可从任意状态到达的状态中具有最高概率的状态，因此 相当于最大概率状态的状态可存在多个，并且各自的最大概率值当然也可以 不同)，并且，根据本发明一个实施例的不确定性消除部120的激活状态消除 部122变更NFA的状态和迁移以避免最大概率状态移动到互不相同的两个以 上的状态从而可抑制激活状态增加。更具体地说，激活状态消除部122在使 得从最大概率状态移动到其它状态的迁移集合间存在共同迁移(即，增加激 活状态的迁移)时，生成通过只由共同迁移组成的迁移集合而从最大概率状 态移动而到达的新的状态，从而可防止随着输入字符串中字符的输入而从最 大概率移动到互不相同的两个以上状态(即，激活状态增加)的现象。

另一方面，根据本发明的一个实施例，查找执行部130执行如下功能： 使用由不确定性消除部120合并的NFA来对字符串执行查找。

然后，根据本发明的一个实施例，通信部140可执行使本发明的字符串 查找服务器100能够与外部装置进行通信的功能。

最后，根据本发明一实施例的控制部150执行控制NFA获取部110、不 确定性消除部120及查找执行部130之间的数据流的功能。即，控制部150 控制来自外部的或者字符串查找服务器100各组成要素之间的数据流，从而 控制NFA获取部110、不确定性消除部120、查找执行部130及通信部140 使其分别执行各自固有功能。

下面，更为仔细地查看根据本发明消除NFA不确定性的方法。

<第一步骤>

在消除NFA的不确定性的方法中决定NFA性能的最重要的过程可以说是 决定对激活状态的增加产生最大影响的迁移的过程，该过程可从查找字符串 时必须经过的开始状态出发跟踪到达概率最高的状态而执行。

首先，根据本发明一个实施例的不确定性消除部120可以计算出到达概 率，所述到达概率表示对包含在NFA内的各个状态输入字符串时，从特定状 态移动而到达相应状态的可能性，并以所计算出的到达概率为基准将到达概 率最大的状态决定为最大概率状态。只是，求出从特定状态到达的概率最大 的状态时，可以只将与所述特定状态通过直接连接关系(根据由迁移的方向 性的连接关系)而到达的状态作为对象执行计算，但并不局限于此。在此， 从第1状态移动而到达第2状态的到达概率，可通过将输入字符串所包含的 字符中引导第1状态迁移到第2状态的字符个数(例如，判断所述输入字符 串包含多少个引导第1状态迁移到第2状态的字符而获得的个数)除以输入 字符串所包含的字符(例如，包含在输入字符串中的所有字符)总个数的值 而计算出。

例如，根据本发明一个实施例的不确定性消除部120，可将与NFA的状 态中输入字符串无关地必须到达的开始状态s0的到达概率设定为1，将其余状 态的到达概率设定为0，进行初始化使得开始状态s0成为最大概率状态。

<第二步骤>

然后，根据本发明一个实施例的不确定性消除部120可执行如下功能： 判断引导最大概率状态移动到其它状态的迁移中是否存在增加激活状态的迁 移，如果存在增加激活状态的迁移，则变更NFA内的状态及迁移，从而消除 激活状态的增加要因。

更具体地说，根据本发明一个实施例的不确定性消除部120可以判断： 由引导最大概率状态移动到状态i的迁移组成的第1迁移集合和由引导最大概 率状态移动到状态j的迁移组成的第2迁移集合间是否存在至少一个共同迁 移。并且，根据本发明一个实施例的不确定性消除部120，若判断为第1迁移 集合和第2迁移集合间存在至少一个所述共同迁移，则从所述第1迁移集合 及所述第2迁移集合中分别排除所述共同迁移，并生成状态k，所述状态k为 通过只由所述至少一个共同迁移组成的共同迁移集合而从所述最大概率状态 移动而到达的状态，且这样生成的状态k可以被新追加到所述非确定性有限 自动机内。并且，根据本发明一个实施例的不确定性消除部120，可以在分别 从第1迁移集合及第2迁移集合消除所述至少一个共同迁移从而不存在到达 状态i或者状态j的迁移的情况下，从NFA中删除相应的状态i或者状态j。

<第三步骤>

然后，本发明一实施例的不确定性消除部120可以计算出到达概率，所 述到达概率表示对包含在NFA内的各个状态输入字符串时，从最大概率状态 移动而到达相应状态的可能性，并将最大概率状态更新为所述计算出的到达 概率最高的状态。

在此，从第1状态移动而到达第2状态的到达概率，可以通过将输入字 符串所包含的字符中使第1状态迁移到第2状态的字符个数除以输入字符串 所包含的字符总个数的值而计算出。

此外，根据本发明的一实施例，在第三步骤计算出的到达概率也可以与 在第一步骤中计算出的到达概率进行合计，也可以将最大概率状态更新为这 样合计后的到达概率最高的状态。

<第四步骤>

然后，本发明一实施例的不确定性消除部120，以更新的最大概率状态为 基准，反复执行如前所述的第2步骤至第3步骤的过程。只是，在有限的内 存资源内，无限反复执行不确定性消除过程并非优选，因此在以下情况下可 终止不确定性消除过程从而提高不确定性消除的效率。

(1)根据本发明消除NFA的激活状态时会生成新的状态，因此在不确 定性消除过程中包含在NFA中的状态总数目会增加。包含在NFA中的状态总 数目过多时NFA的查找性能会降低，因此本发明一实施例的不确定性消除部 120可以在包含在NFA中的状态总数目超过预设值时，将NFA恢复到之前执 行的不确定性消除操作执行前的状态并且终止不确定性消除过程。

(2)根据本发明一实施例，最大概率状态到达相应NFA的终止状态时 也可以终止不确定性消除过程。

(3)根据本发明一实施例，包含在NFA中的所有状态的到达概率都大 于0时也可以终止不确定性消除过程。

下面，举具体例子来描述根据本发明的一个实施例消除NFA不确定性的 过程。图3至图5示例性地示出了根据本发明的一个实施例消除NFA不确定 性的过程。

在以下实施例中，假设作为查找对象的字符串是“gjekf3jmbab0d1f”，描述 输入字符串中所要查找的字符串的正则表达式为“[ab]{3}|bad”。

首先，参照图3，包含在NFA中的各状态的到达概率可被初始化，具体 来说，可以初始化成开始状态即状态0(310)的到达概率为1，其余的状态1 至状态5(320至360)的到达概率为0，并由此可以决定开始状态的状态0 (310)为最大概率状态。

继续参照图3，在最大概率状态的状态0(310)下输入字符b时，根据 迁移函数而移动到状态1(320)及状态2(330)，因此在这种情况下激活状 态由1个(即，从状态0(310)增加为2个(即状态1(320)及状态2(330)))。 因此，根据本发明的一个实施例，生成新的状态即状态6(图4中的470)， 使得在状态0(310)下输入字符b时，不会移动到状态1(320)或者状态2 (330)而是移动到状态6(图4中的470)，从而即便在状态0(310)下输入 字符b也可以不增加激活状态而维持为1个(即，图4中的状态6(470))。 也就是说，根据只由将状态0(310)迁移到状态1(320)的第1迁移集合{a, b}和将状态0(310)迁移到状态2(330)的第2迁移集合{b}之间的共同的 迁移组成的共同迁移集合{b}，可以生成从最大概率状态即状态0(310)移动 而到达的新的状态。图4中示出了这样生成的新的状态即状态6(470)。

另一方面，由于状态6(470)的产生而没有了到达自身的迁移的状态2 (430)可从NFA中删除。

然后，参照图4，可将当前最大概率状态(即，状态0(410))更新为到 达概率最高的状态，该到达概率表示从状态0(410)移动而到达的可能性。 更具体地说，包含在输入字符串中的字符总个数为15个，其中可使状态0(410) 移动到状态1(420)的字符“a”的个数为1个，因此可以计算出从状态0(410) 移动而到达状态1(420)的概率为1/15。另一方面，包含在输入字符串中的 字符总个数为15个，其中可使状态0(410)移动到状态6(470)的字符“b” 的个数为2个，因此可以计算出从状态0(410)移动而到达状态6(470)的 概率为2/15。如上所述，当以状态0(410)为出发点时到状态6(470)的到 达概率大于到状态1(420)的到达概率，到其余状态的到达概率也不可能大 于到状态6(470)的到达概率，因此可将最大概率状态从状态0(410)更新 为状态6(470)。

继续，参照图4，在最大概率状态的状态6(470)下输入字符a时，根 据迁移函数而移动到状态3(440)及状态4(450)，因此在这种情况下激活 状态增加1个(即，从状态6(470)变为2个(即状态3(440)及状态4(450)))。 因此，根据本发明的一个实施例，生成新的状态即状态7(图5中的580)， 使得在状态6(470)下输入字符a时，不会移动到状态3(440)或状者态4 (450)而是移动到状态7(图5中的580)，从而即便在状态6(470)下输入 字符a也可以不增加激活状态而维持为1个(即，图5中的状态7(580))。 也就是说，可以生成根据只由将状态6(470)迁移到状态3(440)的第1迁 移集合{a,b}和将状态6(470)迁移到状态4(450)的第2迁移集合{a}之间 共同的迁移组成的共同迁移集合{a}而从最大概率状态即状态6(470)移动而 到达的新的状态。图5中示出了这样生成的新的状态即状态7(580)。

另一方面，由于状态7(580)的生成而没有了到达自身的迁移的状态4 (450)可从NFA中删除。

然后，参照图5，现在可将最大概率状态(即，状态6(570))更新为表 示从状态6(570)移动而到达的可能性的到达概率最高的状态。更具体地说， 包含在输入字符串中的字符总个数为15个，其中可使状态6(570)移动到状 态3(540)的字符“b”的个数为2个，因此可以计算出从状态6(570)移动而 到达状态3(540)的概率为2/15。另一方面，包含在输入字符串中的字符总 个数为15个，其中可使状态6(570)移动到状态7(580)的字符“a”的个数 为1个，因此可以计算出从状态6(570)移动而到达状态7(580)的概率为 1/15。如上所述，当以状态6(570)为出发点时到状态3(540)的到达概率 大于到状态7(580)的到达概率，到其余状态的到达概率也不可能大于到状 态3(540)的到达概率，因此可将最大概率状态从状态6(570)更新为状态 3(540)。

继续参照图5，在最大概率状态的状态3(540)下输入字符“a”或字符“b” 时，都会根据迁移函数而移动到状态5(560)，因此在这种情况下激活状态仍 维持为1个(即，从状态3(540)为一个即状态5(560))。因此，根据本发 明一实施例，最大概率状态为状态3(540)的情况下不需要消除激活状态。

接着参照图5，可将当前最大概率状态(即，状态3(540))更新为到达 概率最高的状态，该到达概率表示从状态3(540)移动而到达的可能性。更 具体地说，包含在输入字符串中的字符总个数为15个，其中可使状态3(540) 移动到状态5(560)的字符“a”和字符“b”的个数之和为3个，因此可以计算 出从状态3(540)移动而到达状态5(560)的概率为3/15＝1/5。另一方面， 可以计算出从状态3(540)移动而到达其余状态的概率为0。如上所述，当 以状态3(540)为出发点时到状态5(560)的到达概率大于到其余状态的到 达概率，因此可将最大概率状态从状态3(540)更新为状态5(560)。

最后，由于现在最大概率状态(即，状态5(560))到达了终止状态，因 此根据本发明的一实施例可以终止NFA的不确定性消除过程，并且如图5所 示的NFA可作为不确定性消除的最终结果。

下面，查看利用根据本发明一个实施例选择性地消除了不确定性的图5 的NFA来查找字符串的过程。在以下实施例中，假设作为查找对象的输入字 符串为“gjekf3jmbab0d1f”。

图5的NFA从开始状态即状态0(510)开始依次逐一读入输入字符串中 的字符，同时检查某一个状态是否移动到另一个状态。

第一个字符为“g”，但是没有对应输入“g”而使状态0迁移到另一个状态的 迁移，因而继续停留在状态0。第二个字符“j”也没有相应的迁移，因而继续 停留在状态0。因此，在这种情况下，只有状态0(510)是需要检查状态是 否迁移的状态，即激活状态。

按照这种方式停留在状态0的情况下，输入至“gjekf3jm”后随后输入的字 符为“b”，图5的NFA中输入“b”的情况下存在使状态0(510)移动到状态6 (570)的迁移，所以状态0(510)会移动到状态6(570)。因此，输入“b” 之后需要检查状态是否迁移的状态，即激活状态为状态0(510)及状态6(570)， 共2个。

随后输入的字符为“a”，图5的NFA中输入“a”的情况下存在使激活状态 即状态0(510)移动到状态1(520)的迁移及使激活状态即状态6(570)移 动到状态7(580)的迁移，所以状态0(510)及状态6(570)会分别移动到 状态1(520)及状态7(580)。因此，输入“ba”之后需要检查状态是否迁移的 状态，即激活状态为状态0(510)、状态1(520)及状态7(580)，共3个。

随后输入的字符为“b”，图5的NFA中输入“b”的情况下存在使激活状态 即状态0(510)移动到状态6(570)的迁移、使激活状态即状态1(530)移 动到状态3(540)的迁移及使激活状态即状态7(580)移动到状态5(560) 的迁移，所以状态0(510)及状态1(520)及状态7(580)会分别移动到状 态6(570)及状态3(540)及状态5(560)。因此输入“bab”之后需要检查状 态是否迁移的状态，即激活状态为状态0(510)、状态3(540)、状态5(560) 及状态6(570)，共4个。

另一方面，因为由此到达作为图1的NFA的终止状态的状态5(560)， 所以可视为从提供的输入字符串中已查找到想要的字符串，即，字符串“bab”。

图6示出了利用图1的NFA查找字符串的情况与利用图5的根据本发明 选择性地消除了不确定性的NFA来查找字符串的情况的比较结果。参照图6， 利用图5的NFA的情况跟利用图1的NFA的情况相比，可以确认在每个步骤 减少至少一个激活状态。如能在图6中所确认，按照根据本发明的NFA不确 定性的消除方法，可以达到查找字符串时减少内存使用量并提高查找速度的 效果。

以上，以在服务器上执行获取及合并NFA并查找字符串的过程的实施例 为中心进行了描述。但是本发明的组成并不局限于所述实施例，所述一系列 过程在使用者的终端装置(未图示)上也完全可以执行。例如，通过安装在 终端装置上的规定应用程序来执行获取及/或合并NFA并查找字符串的过程。

如上描述的根据本发明的实施例能够以可通过多种计算机组成要素而执 行的程序指令的形式实现，并记录在计算机可读介质上。所述计算机可读介 质可包括单独或组合的程序指令、数据文件、数据结构等。记录在所述计算 机可读介质上的程序指令可以是为本发明特别设计并构成的，也可以是计算 机软件领域技术人员公知而能够使用的。计算机可读介质的例子包括，像硬 盘、软盘及磁带这样的磁性介质，像CD-ROM、DVD这样的光记录介质，像 光磁软盘(floptical disk)这样的磁光介质(magneto-optical media)，以及像 ROM、RAM、闪存等用于存储并执行程序指令而特别构成的硬件装置。程序 指令的例子不仅包括由编译器生成的机器语言代码，也包括使用解释器等而 能够由计算机执行的高级语言代码。所述硬件装置为了执行根据本发明的处 理而构成为通过一个以上的软件模块操作，反之亦然。

以上通过具体组成要素等的特定事项和有限的实施例及附图来对本发明 进行了说明，但这只是出于帮助全面理解本发明的目的而提供，本发明并不 局限于所述实施例，本发明所属领域内具备一般知识的技术人员可在所记载 的基础上进行多种修改和变形。

因此，本发明的思想不应局限于如上描述的实施例，而应当理解为，不 只是下述的权利要求范围，进行与此权利要求范围等同或等价变形的全部也 都落在本发明的思想范围之内。