标记长字符串中的有效单词

我认为作为有效单词(从有限字典中提取的单词)的串联出现的所有字符串的集合在字符的字母表上形成了一种规则语言。然后可以构建一个有限自动机,它完全接受所需的字符串;计算时间是O(n)。

例如,让字典由单词{bat,bag}组成。然后我们构造了以下自动机:状态由0,1,2表示。边:(0,1,b)、(1,2,a)、(2,0,t)、(2,0,g);其中三元组(x,y,z)表示输入z上从x到y的边。唯一接受状态为0。在每个步骤中,在读取下一个输入符号时,必须计算在该输入上可到达的状态集。假设自动机中的状态数是恒定的,则其复杂性为O(n)。至于空间复杂度,我想你可以用O(字数)和上面的结构提示。

在另一个例子中,用{bag,bat,bun,but}这个词,自动机看起来是这样的:

更正式地说,我们的算法如下:

2. 读下一个输入字符,让我们用a来表示它。
3. 对于s中的每个元素s,确定我们在读取a时从s进入的状态;也就是说,状态r使得上面的符号(s,r,a)是一条边。让我们用R来表示这些状态的集合。也就是说,R={R | s in s,(s,R,a)是边}。
4. (如果R为空,则字符串不被接受,算法停止。)
5. 如果没有更多的输入符号,请检查是否有任何接受状态在R中(在本例中,只有一个接受状态,即开始状态)。如果是,则接受字符串,如果不是,则不接受字符串。
6. 否则,取S:=R并转到2。

现在,这个循环的执行次数和输入符号的执行次数一样多。我们唯一要检查的是步骤3和步骤5需要恒定的时间。假设S和R的大小不大于自动机中的状态数(状态数是常量),并且我们可以以查找时间是常量的方式存储边,则如下所示。(请注意,我们当然会丢失多个“parsing”,但这也不是一个要求。)

我会选择隐式回溯的递归算法。函数签名: f: input -> result ,与 input result 任何一个 true 或 false 取决于整个字符串是否可以正确标记。

工作原理如下:

1. 输入 是空字符串,返回 是的 .
2. 看一个前缀的长度 (即第一个字符)。如果在字典里,就跑 f 关于的后缀 输入 是的 是的 也。
3. 如果上一步的前缀长度不在字典中,或者 f 在上一步中返回 假 ,将前缀的长度增加1,然后重复步骤2。如果不能再使用前缀(已经在字符串末尾),返回 假

对于前缀不明确的词典,这 在实践中取得了相当好的运行时间(我想说,在一般情况下是O(n)),尽管在理论上,O(2^n)复杂度的病理病例可能是可以构造的。然而,我怀疑我们能做得更好,因为我们需要回溯无论如何,所以“本能”的O(n)方法使用传统的预计算lexer是不可能的。。。我想。

编辑: