2.5.2 编辑距离有限状态机

编辑距离自动机的基本想法是：构建一个有限状态自动机，准确地识别出和目标词在给定的编辑距离内的字符串集合。可以输入任何词，然后自动机可以基于是否和目标词的编辑距离最多不超过给定距离，从而接收或拒绝它。而且，由于FSA的内在特性，可以在O(n)时间内判断是可以接收或应该拒绝。这里，n是测试字符串的长度。而标准的动态规划编辑距离计算方法需要O(m*n)时间，这里m和n是两个输入单词的长度。因此编辑距离自动机可以更快地检查许多单词和一个目标词是否在给定的最大距离内。

单词“food”的编辑距离自动机形成的非确定有限状态自动机，最大编辑距离是2。开始状态在左下，状态使用ne标记风格命名，这里n是目前为止正确匹配的字符数，e是错误数量。垂直转换表示未修改的字符，水平转换表示插入，两类对角线转换表示替换(用*标记的转换)和删除(空转换)，如图2-7所示。

图2-7 编辑距离自动机

单词“food”的长度是4，所以图2-7有5列。允许2次错误，所以有3行。

Levenshtein Automata接收两个参数，输入字符串和一个布尔值，说明换位是否可以作为一个编辑操作。如果“GO”可以换位，则可以接收“OG”。使用BasicOperations.run方法测试。

        //换位也可以看成是一个编辑操作
        LevenshteinAutomata builder = new LevenshteinAutomata("GO", true);
        Automaton a = builder.toAutomaton(1); //最大编辑距离是1
        System.out.println(BasicOperations.run(a, "OG")); //输出true

如果“GO”不能换位，则不能接收“OG”。

        LevenshteinAutomata builder = new LevenshteinAutomata("GO", false);
        Automaton a = builder.toAutomaton(1); //最大编辑距离是1
        System.out.println(BasicOperations.run(a, "OG")); //输出false

测试最大编辑距离是2的情况。

        LevenshteinAutomata builder = new LevenshteinAutomata("EBER", true);
        Automaton a = builder.toAutomaton(2); //最大编辑距离是2

测试可以接收哪些字符。

        System.out.println(BasicOperations.run(a, "BR")); //输出true
        System.out.println(BasicOperations.run(a, "EB")); //输出true
        System.out.println(BasicOperations.run(a, "EBE")); //输出true
        System.out.println(BasicOperations.run(a, "EBER")); //输出true
上一章目录下一章