文档章节

Boyer–Moore字符串匹配算法

满小茂
 满小茂
发布于 2017/04/08 18:32
字数 1565
阅读 223
收藏 0

精选30+云产品,助力企业轻松上云!>>>

        字符串查找算法,最常见的是KMP,但是不是很常用,最常用的是Boyer–Moore算法,很多文本编辑器的查找算法都是基于Boyer–Moore算法来查找;

        Boyer–Moore算法快的原因在于可以迅速判断搜索字符串和文本当前位置的关联关系,如果没有存在相似的可能则迅速后移,所以该算法可以快速查找字符串,并且搜索的字符串越长,算法执行速度越快。

        Boyer–Moore算法有两种规则,这两种规则也是这个算法的核心,坏字符后移规则和好后缀后移规则。

坏字符后移规则

     情况1:坏字符没出现在模式串中,这时可以把模式串移动到坏字符的下一个字符,继续比较,如下图:

            

     情况2:坏字符出现在模式串中,这时可以把模式串第一个出现的坏字符和母串的坏字符对齐,当然,这样可能造成模式串倒退移动,如下图:

    

好后缀后移规则

情况1:模式串中有子串匹配上好后缀,此时移动模式串,让该子串和好后缀对齐即可,如果超过一个子串匹配上好后缀,则选择最靠左边的子串对齐。

情况2:模式串中没有子串匹配上后后缀,此时需要寻找模式串的一个最长前缀,并让该前缀等于好后缀的后缀,寻找到该前缀后,让该前缀和好后缀对齐即可。

 

情况3:模式串中没有子串匹配上后后缀,并且在模式串中找不到最长前缀,让该前缀等于好后缀的后缀。此时,直接移动模式到好后缀的下一个字符。

代码实现

代码摘自维基百科

C语言实现

#include <stdint.h>
#include <stdlib.h>

#define ALPHABET_LEN 256
#define NOT_FOUND patlen
#define max(a, b) ((a < b) ? b : a)

// delta1 table: delta1[c] contains the distance between the last
// character of pat and the rightmost occurrence of c in pat.
// If c does not occur in pat, then delta1[c] = patlen.
// If c is at string[i] and c != pat[patlen-1], we can
// safely shift i over by delta1[c], which is the minimum distance
// needed to shift pat forward to get string[i] lined up 
// with some character in pat.
// this algorithm runs in alphabet_len+patlen time.
/**
*构造坏字符移动表
*/

void make_delta1(int *delta1, uint8_t *pat, int32_t patlen) {
    int i;
    for (i=0; i < ALPHABET_LEN; i++) {
        delta1[i] = NOT_FOUND;
    }
    for (i=0; i < patlen-1; i++) {
        delta1[pat[i]] = patlen-1 - i;
    }
}

// true if the suffix of word starting from word[pos] is a prefix 
// of word
int is_prefix(uint8_t *word, int wordlen, int pos) {
    int i;
    int suffixlen = wordlen - pos;
    // could also use the strncmp() library function here
    for (i = 0; i < suffixlen; i++) {
        if (word[i] != word[pos+i]) {
            return 0;
        }
    }
    return 1;
}

// length of the longest suffix of word ending on word[pos].
// suffix_length("dddbcabc", 8, 4) = 2
int suffix_length(uint8_t *word, int wordlen, int pos) {
    int i;
    // increment suffix length i to the first mismatch or beginning
    // of the word
    for (i = 0; (word[pos-i] == word[wordlen-1-i]) && (i < pos); i++);
    return i;
}

// delta2 table: given a mismatch at pat[pos], we want to align 
// with the next possible full match could be based on what we
// know about pat[pos+1] to pat[patlen-1].
//
// In case 1:
// pat[pos+1] to pat[patlen-1] does not occur elsewhere in pat,
// the next plausible match starts at or after the mismatch.
// If, within the substring pat[pos+1 .. patlen-1], lies a prefix
// of pat, the next plausible match is here (if there are multiple
// prefixes in the substring, pick the longest). Otherwise, the
// next plausible match starts past the character aligned with 
// pat[patlen-1].
// 
// In case 2:
// pat[pos+1] to pat[patlen-1] does occur elsewhere in pat. The
// mismatch tells us that we are not looking at the end of a match.
// We may, however, be looking at the middle of a match.
// 
// The first loop, which takes care of case 1, is analogous to
// the KMP table, adapted for a 'backwards' scan order with the
// additional restriction that the substrings it considers as 
// potential prefixes are all suffixes. In the worst case scenario
// pat consists of the same letter repeated, so every suffix is
// a prefix. This loop alone is not sufficient, however:
// Suppose that pat is "ABYXCDBYX", and text is ".....ABYXCDEYX".
// We will match X, Y, and find B != E. There is no prefix of pat
// in the suffix "YX", so the first loop tells us to skip forward
// by 9 characters.
// Although superficially similar to the KMP table, the KMP table
// relies on information about the beginning of the partial match
// that the BM algorithm does not have.
//
// The second loop addresses case 2. Since suffix_length may not be
// unique, we want to take the minimum value, which will tell us
// how far away the closest potential match is.
//构造好后缀后移表
void make_delta2(int *delta2, uint8_t *pat, int32_t patlen) {
    int p;
    int last_prefix_index = patlen-1;

    // first loop
    for (p=patlen-1; p>=0; p--) {
        if (is_prefix(pat, patlen, p+1)) {
            last_prefix_index = p+1;
        }
        delta2[p] = last_prefix_index + (patlen-1 - p);
    }

    // second loop
    for (p=0; p < patlen-1; p++) {
        int slen = suffix_length(pat, patlen, p);
        if (pat[p - slen] != pat[patlen-1 - slen]) {
            delta2[patlen-1 - slen] = patlen-1 - p + slen;
        }
    }
}

uint8_t* boyer_moore (uint8_t *string, uint32_t stringlen, uint8_t *pat, uint32_t patlen) {
    int i;
    int delta1[ALPHABET_LEN];
    int *delta2 = (int *)malloc(patlen * sizeof(int));
    make_delta1(delta1, pat, patlen);
    make_delta2(delta2, pat, patlen);

    // The empty pattern must be considered specially
    if (patlen == 0) {
        free(delta2);
        return string;
    }

    i = patlen-1;
    while (i < stringlen) {
        int j = patlen-1;
        while (j >= 0 && (string[i] == pat[j])) {
            --i;
            --j;
        }
        if (j < 0) {
            free(delta2);
            return (string + i+1);
        }

        i += max(delta1[string[i]], delta2[j]);
    }
    free(delta2);
    return NULL;
}

 

Java实现

 /**
     * Returns the index within this string of the first occurrence of the
     * specified substring. If it is not a substring, return -1.
     * 
     * @param haystack The string to be scanned
     * @param needle The target string to search
     * @return The start index of the substring
     */
    public static int indexOf(char[] haystack, char[] needle) {
        if (needle.length == 0) {
            return 0;
        }
        int charTable[] = makeCharTable(needle);
        int offsetTable[] = makeOffsetTable(needle);
        for (int i = needle.length - 1, j; i < haystack.length;) {
            for (j = needle.length - 1; needle[j] == haystack[i]; --i, --j) {
                if (j == 0) {
                    return i;
                }
            }
            // i += needle.length - j; // For naive method
            i += Math.max(offsetTable[needle.length - 1 - j], charTable[haystack[i]]);
        }
        return -1;
    }
    
    /**
     * Makes the jump table based on the mismatched character information.
     */
    private static int[] makeCharTable(char[] needle) {
        final int ALPHABET_SIZE = Character.MAX_VALUE + 1; // 65536
        int[] table = new int[ALPHABET_SIZE];
        for (int i = 0; i < table.length; ++i) {
            table[i] = needle.length;
        }
        for (int i = 0; i < needle.length - 1; ++i) {
            table[needle[i]] = needle.length - 1 - i;
        }
        return table;
    }
    
    /**
     * Makes the jump table based on the scan offset which mismatch occurs.
     */
    private static int[] makeOffsetTable(char[] needle) {
        int[] table = new int[needle.length];
        int lastPrefixPosition = needle.length;
        for (int i = needle.length - 1; i >= 0; --i) {
            if (isPrefix(needle, i + 1)) {
                lastPrefixPosition = i + 1;
            }
            table[needle.length - 1 - i] = lastPrefixPosition - i + needle.length - 1;
        }
        for (int i = 0; i < needle.length - 1; ++i) {
            int slen = suffixLength(needle, i);
            table[slen] = needle.length - 1 - i + slen;
        }
        return table;
    }
    
    /**
     * Is needle[p:end] a prefix of needle?
     */
    private static boolean isPrefix(char[] needle, int p) {
        for (int i = p, j = 0; i < needle.length; ++i, ++j) {
            if (needle[i] != needle[j]) {
                return false;
            }
        }
        return true;
    }
    
    /**
     * Returns the maximum length of the substring ends at p and is a suffix.
     */
    private static int suffixLength(char[] needle, int p) {
        int len = 0;
        for (int i = p, j = needle.length - 1;
                 i >= 0 && needle[i] == needle[j]; --i, --j) {
            len += 1;
        }
        return len;
    }

 

附:

    Rabin-Karp算法也是字符串匹配算法,基于hash值比较,Go语言标准库的字符串包含函数就是使用的这个算法实现的。

上一篇: Hadoop MapReduce流程
下一篇: Flume 日志收集
满小茂

满小茂

粉丝 85
博文 115
码字总数 138147
作品 0
成都
程序员
私信 提问
加载中
请先登录后再评论。
算法——Boyer–Moore–Horspool algorithm(翻译版)

舍卒保车,壮士断腕。(描述时空权衡) 题目描述 Boyer-Moore字符串搜索算法是一种高效的字符串搜索算法.它是由鲍勃·博耶和J·斯特罗瑟·摩尔于1977年开发的。该算法预处理正在搜索的目标字...

osc_0bpc54vt
05/17
11
0
算法——Boyer–Moore–Horspool algorithm(翻译版)

舍卒保车,壮士断腕。(描述时空权衡) 题目描述 Boyer-Moore字符串搜索算法是一种高效的字符串搜索算法.它是由鲍勃·博耶和J·斯特罗瑟·摩尔于1977年开发的。该算法预处理正在搜索的目标字...

刘小白.
05/16
0
0
字符串匹配的Boyer-Moore算法

来源:阮一峰 上一篇文章,我介绍了KMP算法。 但是,它并不是效率最高的算法,实际采用并不多。各种文本编辑器的”查找”功能(Ctrl+F),大多采用Boyer-Moore算法。 Boyer-Moore算法不仅效率...

iamwent
2013/05/05
15
0
kbmmw 中的Boyer-Moore算法

kbmmw 5.10 版本中实现了一个非常好用的字符串搜索算法,即Boyer-Moore算法。 在用于查找子字符串的算法当中,BM(Boyer-Moore)算法是目前被认为最高效的字符串搜索算法, 它由Bob Boyer和J...

xalion
2019/11/25
0
0
字符串匹配算法之"Boyer Moore"

Boyer-Moore字符串搜索算法是一种非常高效的字符串搜索算法。它由Bob Boyer和J Strother Moore设计于1977年,最初的定义1975年就给出了,后续才给出构造算法以及算法证明。 先假定部分定义:...

famince
2013/11/29
283
0

没有更多内容

加载失败,请刷新页面

加载更多

要求jQuery在执行某些操作之前等待所有图像加载的官方方式

问题: In jQuery when you do this: 在jQuery中,当您执行以下操作时: $(function() { alert("DOM is loaded, but images not necessarily all loaded");}); It waits for the DOM t......

法国红酒甜
昨天
11
0
实现Map按值排序

Map按照值排序,需要自定义比较器,实现Comparator接口,实现compare方法。 public class SortByVlue {public static void main(String[] args) {Map<String, Long> map = new HashMap<......

游人未归
昨天
16
0
定天气爬虫加定时发送天气邮件

今天无聊,在家研究个爬虫玩玩 主要用到以下几个库: request 请求资源 iconv-lite转码,有的网站html格式不是utf-8 cheerio类似jq,操作html,获取相关爬虫数据 nodemailer 发送邮件,例如q...

莫西摩西
昨天
14
0
还在为大屏分辨率困扰?图扑提供响应式(自适应)可视化大屏

前言 数据可视化在当下信息时代已经成为炙手可热的话题,而 B/S 化趋势,也使得许多大屏应用上在网页端出现,今天给大家分享一套不一样风格的大屏页面,与传统深蓝色不同,这次采用了暗红色设...

xhload3d
昨天
20
0
如何妙用Spring 数据绑定机制

前言 在剖析完 Spring Boot 返回统一数据格式是怎样实现的?文章之后,一直觉得有必要说明一下 Spring's Data Binding Mechanism 「Spring 数据绑定机制」。 默认情况下,Spring 只知道如何转...

码农小胖哥
2019/12/27
21
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部