`
regular
  • 浏览: 77590 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

对于经典模式匹配算法的一些改动

    博客分类：
  • Java
算法CC++C#J# 
阅读更多
从一个很长的字符串（或者数组）中，查找某个子串（模式串）是否存在，在算法上被称为是“模式匹配”。

模式匹配的经典算法包括KMP算法、BM算法等等。以下简要回顾这些经典算法的思想，并说明我对此的改进想法。

KMP算法

首先对模式串进行处理，获得当某个字符位置失配的时候，比较位置的指针应该指向的下一个位置的数组。举例如下： 

模式串：A B A B C
next ：0 0 1 2 0


经过对上面的模式串进行处理，我们可以做如下比较： 
索引位：_ _ ▼ ↓
字符串：A B A A B A B D C A B A B A B C
模式串：A B A B C
比较位：_ _ ▲ ↑ 失配，指针指向 next[3] = 1 的位置

索引位：_ _ ▼ ↓
字符串：A B A A B A B D C A B A B A B C
模式串：_ _ A B A B C
比较位：    ▲ ↑ 仍然失配，next[1] = 0 的位置

索引位：_ _ ▼ ↓
字符串：A B A A B A B D C A B A B A B C
模式串：_ _ _ A B A B C
比较位：    ▲ ↑ OK了，继续向下走。

索引位：_ _ _ _ _ _ ▼ ↓
字符串：A B A A B A B D C A B A B A B C
模式串：_ _ _ A B A B C
比较位：      _ _ _ ▲ ↑ 失配，next[4] = 2 的位置。

索引位：_ _ _ _ _ _ ▼ ↓
字符串：A B A A B A B D C A B A B A B C
模式串：_ _ _ _ _ A B A B C
比较位：          _ ▲ ↑ 仍然失配，next[2] = 0 的位置。

索引位：_ _ _ _ _ _ ▼ ↓
字符串：A B A A B A B D C A B A B A B C
模式串：_ _ _ _ _ _ _ A B A B C
比较位：            ▲ ↑ 仍然失配且比较位已经是0了，只能索引，比较+1继续找。

索引位：_ _ _ _ _ _ _ ▼ ↓
字符串：A B A A B A B D C A B A B A B C
模式串：_ _ _ _ _ _ _ _ A B A B C
比较位：              ▲ ↑ 仍然失配且比较位已经是0了，只能索引，比较+1继续找。

索引位：_ _ _ _ _ _ _ _ ▼ ↓
字符串：A B A A B A B D C A B A B A B C
模式串：_ _ _ _ _ _ _ _ _ A B A B C
比较位：                ▲ ↑ OK，继续向下走。

索引位：_ _ _ _ _ _ _ _ _ _ _ _ ▼ ↓
字符串：A B A A B A B D C A B A B A B C
模式串：_ _ _ _ _ _ _ _ _ A B A B C
比较位：                  _ _ _ ▲ ↑ 失配，next[4] = 2 的位置。

索引位：_ _ _ _ _ _ _ _ _ _ _ _ ▼ ↓
字符串：A B A A B A B D C A B A B A B C
模式串：_ _ _ _ _ _ _ _ _ _ _ A B A B C
比较位：                      _ ▲ ↑ OK，任务达成。


KMP的比较位数组计算方式遵循下列公式： 
next[i]= { 0 | p = 1
           k | 1 <= k < i，且 P1..Pk-1 == Pi-k+1..Pi-1
           1 | 其他情况                                }

更详细的说明参见：
KMP算法详解

BM算法

首先建立两个表：

坏字符表，包含所有可能出现的字符，0x00..0xFF，说明如果尾部字符是这个的话，模式串为了能匹配这个位置的这个字符，右移的最短距离。

好后缀表，说明如果模式串中若有与某个长度的后缀一致的子串，则可以向右移动的距离。 

A 对齐源串和模式串的头部；
B 比较模式串尾字符与源串同位置字符是否一致；
  B.1 若不一致，则源串字符是否存在于模式串中；
    B.1.1 若不存在，则跳过模式串长度，转到B条目继续比较；
    B.1.2 若存在，则根据坏字符表右移模式串，转到B条目；
  B.2 若一致，反向比较倒数第二字符是否一致，直到倒数第n字符不一致，于是……
      检查坏字符表和好后缀表，选择可以移动的最大距离。

更详细的说明参见：
字符串匹配算法 boyer-moore算法
Boyer-Moore 经典单模式匹配算法

组合优化

首先，KMP算法可能会比较一些显然不可能匹配的情况： 
模式串：A B A B A
 next：0 0 1 2 3

索引位：_ _ _ ▼ ↓
字符串：A B A B D A B ...
模式串：A B A B A
比较位：_ _ _ ▲ ↑ 失配，next[4] = 2。

索引位：_ _ _ ▼ ↓
字符串：A B A B D A B ...
模式串：_ _ A B A B A
比较位：    _ ▲ ↑ 失配，next[2] = 0。

索引位：_ _ _ ▼ ↓
字符串：A B A B D A B ...
模式串：_ _ _ _ A B A B A
比较位：      ▲ ↑ 失配，比较位和索引位+1进行下一个比较。

索引位：_ _ _ _ ▼ ↓
字符串：A B A B D A B ...
模式串：_ _ _ _ _ A B A B A
比较位：        ▲ ↑ OK，继续之后的比较。


实际上，我们可以看到，上面例子里的第2，第3次比较根本没有必要。根本就可以直接跳到第4步继续下去。问题出现在什么地方？问题就出现在next的公式中。 
next[i]= { 0 | p = 1
           k | 1 <= k < i，且 P1..Pk-1 == Pi-k+1..Pi-1
           1 | 其他情况                                }

这个公式只说明了自匹配的情况，没说明在自匹配的基础上还应该有一个尾字符的不匹配。 
next[i]= { 0 | p = 1
           k | 1 <= k < i，且 P1..Pk-1 == Pi-k+1..Pi-1 & Pk != Pi
           1 | 其他情况                                           }

也就是说，若两个子串的下一个字符也一样，就没必要再匹配，因为只有源串里面比较的那个字符不一样才需要移动。

从Boyer-Moore Algorithm之中学习到，改良的BM算法中的好后缀表的建立也包含了同样的思想，而且更玄的是，好后缀表竟然能考虑到模式串的边界之外隐含的匹配信息，的确很强大。

另外，向BM算法致敬，若尾字符根本没出现在模式串中的话，所有的比较都根本无意义。所以这种情况下，相比上面调整的KMP算法的小挪移，可以实现大挪移。


修改之后的算法逻辑如下： 

模式串：A B A B A
 next：0 1 0 1 0
A 对齐源串和模式串的头部；
B 比较模式串尾字符与源串同位置字符是否一致；
  B.1 若不一致，则源串字符是否存在于模式串中；
    B.1.1 若不存在，则跳过模式串长度，转到B条目继续比较；
    B.1.2 若存在，则根据坏字符表右移模式串，转到B条目；
  B.2 若一致，使用“改·KMP法”匹配，决定模式串的右移值，转到B条目继续比较。

实际上，我在代码里创建的是跳转表，而不是指针索引位表。 
模式串：A B A B A
步进值：1 1 3 3 5  表示若此位失配，则模式串向右移动的位置。

索引位：index[n] = max(n - step[n], 1);

例子1：

索引位：_ _ _ ↓
字符串：A B A D A A B ...
模式串：A B A B A
比较位：_ _ _ ↑ 失配，step[4] = 3，index = max(4 - step[4], 1) = 1。

索引位：_ _ _ ↓
字符串：A B A D C A B ...
模式串：_ _ _ A B A B A
比较位：      ↑


例子2：

索引位：_ _ ↓
字符串：A B C A B D A B ...
模式串：A B A B A
比较位：_ _ ↑ 失配，step[3] = 3，index = max(3 - step[3], 1) = 1。

索引位：_ _ _ ↓
字符串：A B C A B D A B ...
模式串：_ _ _ A B A B A
比较位：      ↑

例子3（更为复杂的）：

模式串：A  B  A  B  A  C  A  B  A  B  A  D
步进值：1  1  3  3  5  2  7  7  9  9 11  6
索引值：1  1  1  1  1  4  1  1  1  1  1  6

索引位：_ _ _ _ _ ↓
字符串：A B A B A D A B ...
模式串：A B A B A C A B A B A D
比较位：_ _ _ _ _ ↑ 失配，step[6] = 2，index = 4。

索引位：_ _ _ _ _ ↓
字符串：A B A B A D A B...
模式串：_ _ A B A B A
比较位：    _ _ _ ↑

例子4：

索引位：_ _ _ _ _ _ _ _ _ _ _ ↓
字符串：A B A B A C A B A B A C A B ...
模式串：A B A B A C A B A B A D
比较位：_ _ _ _ _ _ _ _ _ _ _ ↑ 失配，step[12] = 6，index = 6。

索引位：_ _ _ _ _ _ _ _ _ _ _ ↓
字符串：A B A B A C A B A B A C A B ...
模式串：_ _ _ _ _ _ A B A B A C A B A B A D
比较位：            _ _ _ _ _ ↑

步进值的计算方法如下： 
模式串：A  B  A  B  A  C  A  B  A  B  A D
步进值：1  2  3  4  5  6  7  8  9 10 11 12 <- 设定初始值

第一轮：设定delta = 1
从头开始比较，直到发现不同，修改发现位置的步进值，设定为min(step, delta)

模式串：A  B  A  B  A  C  A  B  A  B  A D
比较位：↑__↑
设定步进值：
步进值：1 (1) ...

第二轮：设定delta = 2
从头开始比较，直到发现不同，修改发现位置的步进值，设定为min(step, delta)
模式串：A  B  A  B  A  C  A  B  A  B  A  D
比较位：↑_____↑
比较位：   ↑_____↑
比较位：      ↑_____↑
比较位：         ↑_____↑
设定步进值：
步进值：1  1  3  4  5 (2) ...

直到delta = length - 1


样例代码

最后，Java代码如下： 
/**
 * @version 1.0
 * @author Regular
 * @date 2009-06-11
 */
package cn.sh.huang;

import java.io.File;
import java.io.FileInputStream;
import java.nio.charset.Charset;

public class StringCmp
{

    /**
     * Entrance method
     *
     * @param args
     */
    public static void main(String[] args) throws Exception
    {
        String fileName = "C:\\Program Files\\Java\\jdk1.6.0_13\\LICENSE";
        String pattern = "enef";
        File file = new File(fileName);
        int fileLen = (int) file.length();
        FileInputStream fis = new FileInputStream(file);
        byte[] buffer = new byte[fileLen];
        fis.read(buffer);
        int i = indexOfData(buffer, 0, pattern);
        System.out.println(i);
    }

    private static int indexOfData(byte[] buffer, int index, String s)
    {
        byte[] pattern = s.getBytes(Charset.forName("US-ASCII"));
        int[] fast_shift = new int[256]; // 模式串尾字符比较结果的移动
        for (int i = 0; i < 256; i++) {
            fast_shift[i] = pattern.length;
        }
        for (int i = pattern.length - 1, j = 0; i >= 0; i--, j++) {
            int x = 0xFF & pattern[i];
            if (fast_shift[x] > j) {
                fast_shift[x] = j;
            }
        }
        int[] slow_shift = new int[pattern.length]; // 改·KMP算法的移动
        getNextStep(pattern, slow_shift);
        int cursor = 0;
        outterLoop: while (index + pattern.length <= buffer.length) {
            // 首先检查index + pattern.length - 1位置的字符，决定快速移动距离
            int x = 0xFF & buffer[index + pattern.length - 1];
            int shift = fast_shift[x];
            if (shift > 0) {
                index += shift;
                cursor = 0;
                continue;
            }
            // 若尾字符一致，使用改·KMP算法决定慢速移动距离
            while (cursor < pattern.length - 1) {
                if (pattern[cursor] != buffer[index + cursor]) {
                    index += slow_shift[cursor];
                    cursor = cursor - slow_shift[cursor];
                    if (cursor < 0) {
                        cursor = 0;
                    }
                    continue outterLoop;
                }
                cursor++;
            }
            return index;
        }
        return -1;
    }

    /**
     * <pre>
     *                   idx = max(0, n - step)
     * a b a b a c a b a b a d                        step    idx
     * X a b a b a c a b a b a d                       1       0
     * a X b a b a c a b a b a d                       1       0
     * a b X a b a b a c a b a b a d                   3       0
     * a b a X b a b a c a b a b a d                   3       0
     * a b a b X a b a b a c a b a b a d               5       0
     * a b a b a X a c a b a b a d                     2       3
     * a b a b a c X a b a b a c a b a b a d           7       0
     * a b a b a c a X b a b a c a b a b a d           7       0
     * a b a b a c a b X a b a b a c a b a b a d       9       0
     * a b a b a c a b a X b a b a c a b a b a d       9       0
     * a b a b a c a b a b X a b a b a c a b a b a d  11       0
     * a b a b a c a b a b a X a b a b a d             6       5
     * </pre>
     * @param pattern
     * @param next
     */
    private static void getNextStep(byte[] pattern, int[] next)
    {
        for (int i = 0; i < pattern.length; i++) {
            next[i] = i + 1;
        }
        // 卷积
        for (int delta = 1; delta < pattern.length; delta++) {
            int i = 0;
            int j = i + delta;
            while (pattern.length > j && pattern[i] == pattern[j]) {
                i++;
                j++;
            }
            if (pattern.length > j) {
                if (next[j] > delta) {
                    next[j] = delta;
                }
            }
        }
    }

}


总体看来，还是BM算法更好一些，其效率比KMP算法更高。

我这里虽然借用了BM的坏字符思想并改进了KMP的步进值计算，但由于逐字符比较始终是从头开始，而不像BM算法是从尾部开始，所以小挪移的潜力没有BM的那么大。

后续设想

若模式串相对较长的话，可以在模式串中找几个稀疏分布的点，比较的时候，首先比较这几个点的字符是否与源串相同，如果不同就没必要逐个字符比较了，肯定不一致，可以往后挪了。
0
顶
0
踩
分享到：
| 读写进程的互斥锁
评论
2 楼 iamsk 2009-06-16  
收藏，有空定会细看的。
1 楼 lin_style 2009-06-12  
重温，兼收藏。
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    Java模式匹配功能详解 (1).pdf

    在Java编程中，模式匹配是一种强大的工具，常用于解析、简化或操作复杂的对象结构，如在解析表达式或处理树形结构时。本篇将详细解释如何在Java中实现模式匹配，以及它如何帮助提高代码的性能和可读性。 在给定的...

    KM匹配题集

    KMP（Knuth-Morris-Pratt）算法是一种字符串匹配算法，主要用于在主串中查找子串出现的位置。这个算法避免了在遇到不匹配字符时的回溯，提高了搜索效率。KMP算法的核心是构造一个部分匹配表（也叫失配表），它记录了...

    生物信息学案例在《数据结构》教学中的应用.pdf

    串联重复序列识别的关键在于模式匹配算法，尤其是循环串的匹配算法。该算法可以通过对传统的字符串匹配算法进行改动来实现，从而定位特定基因在循环串中的位置。通过这种案例的引入，学生不仅能够理解生物信息学中所...

    英文拼写检错

    首先，项目采用了一种基于单词前缀树（Trie）的多串模式匹配算法。前缀树，也被称为字典树，是一种数据结构，用于存储一个字符串集合。在英文拼写检错中，它能快速地查找和比较单词。当输入的单词与字典中的单词进行...

    java设计模式选择题复习

    - **扩展性**：通过工厂模式，当需要添加新产品时，只需修改工厂的实现而不需改动客户端代码，增加了系统的灵活性。 - **缺点**： - **复杂度**：虽然工厂模式提高了代码的可维护性和扩展性，但也可能导致系统...

    Drools规则引擎介绍

    Rete 算法是一种高效的模式匹配算法，特别适用于处理大量的规则和事实。 在传统的编程方式中，业务逻辑通常嵌入在应用程序代码中，当业务规则发生变化时，需要重新编译和部署整个应用。而使用规则引擎如 Drools，...

    论文研究-基于SVM的GSM网络定位技术 .pdf

    利用SVM算法，根据移动台在通话过程中接收到的来自服务小区和邻小区**号特征，预测其所在的网格分区号，实现高精度的模式匹配定位。 综上所述，基于SVM的GSM网络定位技术是一种高效、实用的定位方法，通过分析移动...

    规则引擎应用实践

    1. 规则表示语言（Rete算法）：Rete是一种高效的模式匹配算法，用于快速找出满足条件的规则。 2. Drools：这是一个开源的Java规则引擎，支持Java Rule Language (JRL) 和 Decision Table 格式的规则定义。 3. BRMS...

    数据建模 模式的持久化

    然而，在关系数据库中，由于其基于记录的结构，需要额外的关系-对象服务来解决对象和表格之间的转换问题，这可能导致一些挑战，比如数据不匹配和额外的编程复杂性。 为了解决这些问题，出现了持久化框架。这种框架...

    java游戏开发-连连看2-实现游戏算法.doc

    为了提高程序的可扩展性和适应性，设计时应考虑到可能的改动，如增加新的游戏模式、调整地图大小或元素数量等。类和方法的结构应保持清晰，便于理解和修改。 以上是连连看2游戏算法的主要实现步骤，实际开发中还...

    C++ 经典泡泡龙源代码

    这意味着开发者可以自由地查看、分析和学习其中的代码结构、算法和设计模式，但不应该直接将其应用于盈利性产品中，以免引发版权问题。 【标签】"泡泡龙" 和 "c++" 指明了这个项目的主要内容。"泡泡龙" 指的是游戏...

    JBoss_Drools教程

    Rete 算法是一种高效的模式匹配算法，用于匹配事实（Facts）和规则。它通过构建 RETE 网络来加速规则的评估，当新的事实被插入到 Working Memory 中时，算法能够迅速找到匹配的规则并执行相应的动作。 **Drools ...

    新闻管理系统model2模式

    当需要修改某一部分功能时，只需要在对应层进行改动，而不会影响到其他层，这对于大型项目的长期维护至关重要。 总的来说，"新闻管理系统model2模式"是一个典型的分层架构的应用实例，它通过合理划分职责，提高了...

    Search and Replace.7z

    它可以是简单的字符串匹配，也可以涉及到正则表达式，以便进行更复杂的模式匹配。 - 替换功能：配合搜索，替换功能可以将找到的文本或模式替换为新的内容。这对于大规模修改代码中的某些元素或更新文档中的特定信息...

    gool连连看项目最终版(带配置文件 功能更完善 带注释)

    1. **智能匹配系统**：游戏中的自动匹配算法确保了每局游戏的挑战性和公平性，让玩家在消除图案时能感受到策略与运气的完美结合。 2. **多种游戏模式**：除了传统的单人模式，可能还包括多人对战模式、计时赛模式等...

    多线程 智能拷贝 工具

    该工具通过优化拷贝算法，能够智能地识别需要更新或新建的文件，避免了对未改动文件的无谓处理，从而节省了时间和系统资源。 “智能匹配”是这个工具的另一个关键特性。它可能包含以下方面：文件的哈希对比，用于...

    GNU regex 正则表达式 修正版

    正则表达式（Regex）是编程语言中用于处理字符串的强大工具，它允许我们用简洁的模式来匹配、查找、替换或提取文本中的特定字符序列。GNU regex库提供了对正则表达式的支持，使得程序员能够在自己的应用程序中轻松...

Magicbox
Global site tag (gtag.js) - Google Analytics