Bitap: my favorite string matching algorithm

查看原文 / View Original 编辑 / Edit

Bitap: my favorite string matching algorithm

Bitap：我最喜欢的字符串匹配算法

A classic problem is to find the first occurrence of a pattern $P$ in a string $T$. There are various classic algorithms to solve this problem efficiently, such as Boyer-Moore, Knuth-Morris-Pratt, and Two-Way. In this post I want to provide an exposition of a less well-known algorithm, the bitap or shift-and algorithm, that runs efficiently when the pattern $P$ is relatively short (of length less than the width of a machine word.) Despite its constraints, I like it a lot because it is simple both to understand and to implement, relatively efficient for short strings, and uses bit operations in a particularly elegant fashion. To show that the algorithm is as simple conceptually as claimed, let me try to derive it incrementally starting from the most naive string matching algorithm.

一个经典的问题是在字符串 $T$ 中查找模式串 $P$ 的首次出现位置。目前有多种经典算法可以高效地解决这个问题，例如 Boyer-Moore、Knuth-Morris-Pratt 和 Two-Way 算法。在这篇文章中，我想介绍一种不太为人所知的算法——Bitap（或称 Shift-and）算法。当模式串 $P$ 相对较短（长度小于机器字长）时，该算法运行效率很高。尽管有此限制，我依然非常喜欢它，因为它既易于理解又易于实现，对于短字符串而言效率较高，并且以一种极其优雅的方式使用了位运算。为了证明该算法在概念上确实如我所说的那样简单，我将从最朴素的字符串匹配算法开始，逐步推导出它。

Deriving bitap

推导 Bitap

The naive algorithm

朴素算法

The simplest brute-force algorithm to solve the string matching problem just tries to match the pattern $P$ starting from each possible position in the string $T$.

解决字符串匹配问题最简单的暴力算法，就是尝试从字符串 $T$ 的每一个可能位置开始匹配模式串 $P$。

// Returns the first index i such that T[i:] starts with the pattern P,
// or -1 if no such index occurs.
//
// The pattern P is required to be nonempty.
func match(T, P string) int {
    outer:
    // starting from each position i = 0, ... in the string T...
    for i := range len(T) - len(P) + 1 {
        // try to match the pattern P, one character at a time...
        for j := range len(P) {
            // moving onto the next start position if a mismatch occurs.
            if T[i+j] != P[j] {
                continue outer
            }
        }
        return i
    }
    return -1
}

The naive algorithm, but make it streaming

朴素算法的流式处理版本

Let’s now impose an additional constraint to motivate us to change the algorithm a little: instead of being given all the characters of the text $T$ at once, suppose that they are now provided in the form of a stream, one character at a time. (Perhaps $T$ is very long and we do not wish to load all its contents into memory at once.) The simple algorithm presented above is not streaming: it needs to read up to $m = \texttt{len}(P)$ characters ahead starting from the current position in $T$ to detect a match of the pattern. How can we adapt it so that it only performs one pass through the data?

现在让我们增加一个额外的约束，以促使我们对算法进行一些改进：假设我们不再是一次性获得文本 $T$ 的所有字符，而是以流的形式逐个字符提供（也许 $T$ 非常长，我们不希望一次性将其全部加载到内存中）。上面介绍的简单算法不是流式的：它需要从 $T$ 的当前位置开始向前读取最多 $m = \texttt{len}(P)$ 个字符来检测匹配。我们该如何调整它，使其只需对数据进行一次遍历呢？

After a bit of thought, one comes up with the following variant of the brute-force algorithm. Instead of immediately trying to detect an occurrence of $P$ by reading ahead in the text $T$ starting from each start position $i = 0, \dots$, we can instead maintain a set of in-progress matches as we scan through the text $T$. Conceptually, an in-progress match consists of the prefix of the pattern $P$ that has already been matched just before the current position, along with the remaining suffix that has not been matched yet. When we read a new character $c$ in $T$, we advance the in-progress matches that are expecting the character $c$, and kill the rest. If any of the active matches progress to the end of the pattern $P$, we are done.

经过一番思考，我们可以得出暴力算法的以下变体。我们不再从每个起始位置 $i = 0, \dots$ 开始通过向前读取文本 $T$ 来立即检测 $P$ 的出现，而是可以在扫描文本 $T$ 时维护一组“进行中的匹配”。从概念上讲，一个“进行中的匹配”由当前位置之前已经匹配的模式串 $P$ 的前缀，以及尚未匹配的剩余后缀组成。当我们读取 $T$ 中的新字符 $c$ 时，我们会推进那些期待字符 $c$ 的匹配，并终止其余的匹配。如果任何活跃的匹配推进到了模式串 $P$ 的末尾，我们就完成了任务。

func matchOnepass(T, P string) int {
    type state struct {
        remaining string // suffix of P yet to be matched
    }
    var active []state
    for i := range len(T) {
        c := T[i]
        // Always attempt to start a new match.
        active = append(active, state{remaining: P})
        var next []state
        for _, m := range active {
            if c == m.remaining[0] {
                // Advance this in-progress match by one position.
                remaining := m.remaining[1:]
                if remaining == "" {
                    // Matched all of P, with the final character appearing at position i.
                    return i - len(P) + 1
                }
                next = append(next, state{remaining})
            }
        }
        active = next
    }
    return -1
}

We can optimize matchOnepass a little by representing an in-progress match state by the index $j$ of the next character to match in the pattern $P$. (The suffix of $P$ yet to be matched then corresponds to P[j:].) This simplification yields:

我们可以通过用模式串 $P$ 中下一个待匹配字符的索引 $j$ 来表示“进行中的匹配”状态，从而对 matchOnepass 进行一点优化。（此时 $P$ 中尚未匹配的后缀对应为 P[j:]。）这种简化得到：

func matchOnepassInt(T, P string) int {
    var active []int // state is now an int
    for i := range len(T) {
        c := T[i]
        active = append(active, 0) // attempt to start a new match
        var next []int
        for _, j := range active {
            if c == P[j] {
                // advance
                j++
                if j == len(P) {
                    // matched all of P
                    return i - len(P) + 1
                }
                next = append(next, j)
            }
        }
        active = next
    }
    return -1
}

How can we improve this algorithm further? One observation we can make is that the in-progress states in active are now always integers between 0 and len(P). If $P$ is not too long, there may be a more efficient way to represent the active set instead of a list of integers. This idea is what leads us to our next modification, using bitsets and bit manipulation, from which the bitap algorithm arises.

我们该如何进一步改进这个算法呢？我们可以观察到，active 中的进行中状态现在始终是 0 到 len(P) 之间的整数。如果 $P$ 不太长，也许有一种比整数列表更高效的方式来表示这个活跃集合。这个想法引导我们进行下一次修改，即使用位集（bitset）和位操作，Bitap 算法由此产生。

Bit manipulation

位操作

Indeed, if $P$ is relatively short, say len(P) < 64, then we can pack the set of active states into a single integer (understood as a 64-bit bitset.) So, for instance, if active = {1, 2, 7}, then active_bitset = 0b1000_0110. Let’s try this!

确实，如果 $P$ 相对较短，比如 len(P) < 64，那么我们可以将活跃状态集合打包成一个整数（理解为一个 64 位的位集）。例如，如果 active = {1, 2, 7}，那么 active_bitset = 0b1000_0110。让我们试试看！

func matchOnepassBitset(T, P string) int {
    var active uint64 // bitset
    for i := range len(T) {
        c := T[i]
        active |= 1 << 0 // add 0 to the bitset (attempt to start a new match)
        var next uint64
        for j := range 64 {
            if active&(1<<j) == 0 {
                continue
            }
            // for each state j in the active set...
            if c == P[j] {
                // advance
                j++
                if j == len(P) {
                    // matched all of P
                    return i - len(P) + 1
                }
                next |= 1 << j
            }
        }
        active = next
    }
    return -1
}

Hm. That doesn’t seem like a major improvement. Although it is nice that active has a more compact encoding, there are still two nested loops, begging the question to whether we can eliminate the inner loop somehow… It turns out that we indeed can, using some clever bit manipulation and a small change in perspective. Observe that, in the above algorithm, we look at each match state, checking if it can continue (by comparing c with P[j]), and then advance by one position if so. On the other hand, an alternative approach…

嗯。这看起来并没有太大的改进。虽然 active 的编码更紧凑了，但仍然存在两个嵌套循环，这不禁让人怀疑是否可以通过某种方式消除内层循环……事实证明，通过一些巧妙的位操作和视角的微小转变，我们确实可以做到。观察一下，在上述算法中，我们查看每个匹配状态，检查它是否可以继续（通过比较 c 和 P[j]），如果可以，则向前推进一个位置。另一方面，还有一种替代方法……

← 返回新闻列表 / Back to news list