Boyer Moore String Matching in D Lang

下雨的假日就是要寫程式啊！
演算法本身請看參考資訊

先來個介面

import std.stdio;
import std.algorithm: max;

void boyer_moore_matching(T)(T[] text, T[] pattern) {
	// TODO: 印出每個 matching 的 index
}

void main()
{
	boyer_moore_matching!char("AABCABABCABABA".dup, "ABABA".dup);
}

1. import module 會引入所有 module expose 的類別、函數，也可以只引入部分功能，例如 import std.algorithm: max; 只會引入 max
2. 字串常數 (string) 是 immutable 所以要用 dup (duplicate) 動態複製，複製體型別為 char[] (背景故事連結)
3. 一上來就用泛形介面 i.e. auto func(T)(T arg) 這邊 T 可以是任何型別
4. 呼叫泛型函數要用 ! 後面接型別，多個型別可以用 func!(type1, type2)(arg) 的方式

這個介面有個問題，因為字串比對不需要修改 text 或是 pattern ，應該要讓這兩個參數型別是個常量，這樣也能省去兩次複製 (dup)。

import std.stdio;

void boyer_moore_matching(T)(const T[] text, const T[] pattern) {
	// TODO: 印出每個 matching 的 index
}

void main() {
	boyer_moore_matching!char("AABCABABCABABA", "ABABA");
}

前處理之一 (Bad Character Shift)

// 沒得比，下課！
if(pattern.length == 0)
	return text;
	
const int alphabet_size = 1 << (T.sizeof << 3);
const int not_found = pattern.length;
	
int[alphabet_size] delta1;
	
// bad-character rule: O(alphabet_size + pattern.length)
delta1[0..$] = not_found;
foreach(size_t i, c; pattern[0..($-1)]) {
  	delta1[c] = pattern.length - 1 - i;
}

1. T.sizeof 取得 T 型別的位元組大小，以 char 為例大小是 1
2. .sizeof 是 property ，可以自訂
3. int[alphabet_size] delta1 是靜態陣列，長度不可變。陣列宣告方式其實也支援 C-Style 的 int arr[2]，不過會有 warning
4. delta1[0..$] 裡面的 $ 代表該陣列最後一個之後的索引值 (等於長度)
5. delta1[0..$] = not_found 把陣列全部元素設為 not_found (not_found = pattern.length)
6. foreach(int i, c; pattern[0..($-1)])
   6.1. int i 是陣列索引值，可以不給
   6.2. c 是陣列元素值，這邊 c 是複製出來的，不想要複製可以加上 ref
7. delta1[c] c 的型別是 char 所以這邊隱含 integer promotion；文件連結

前處理之二 (Good-Suffixes Shift)

int[] delta2 = new int[plen];
int[] suff = suffixes(pattern);

// preprocess for delta2
delta2[0..$] = plen;
int j = 0;
	
foreach_reverse(i, _; pattern) {
	if(suff[i] == i + 1) {
		for(; j < plen - 1 - i; ++j) {
			if(delta2[j] == plen)
				delta2[j] = plen - 1 - cast(int)i;
		}
	}
}
	
for(int i = 0; i < plen - 2; ++i)
	delta2[plen - 1 - suff[i]] = plen - 1 - i;

1. new 出來可以不管他因為有 GC，也支援 RAII ，有機會再來研究
2. foreach_reverse 這邊有個問題，索引 i 不能用 int 型別宣告，所以只好在下面自己 cast；已回報

函數 suffixes

auto suffixes(T)(const T[] pattern) {
	const int plen = cast(int)pattern.length;
	int result[] = new int[plen];
	
	result[$-1] = plen;
	
	int g = plen - 1;
	int f;
	
	for(int i = plen - 2; i >= 0; --i) {
		if(i > g && result[i + plen - 1 - f] < i - g)
			result[i] = result[i + plen - 1 - f];
		else {
			if (i < g)
				g = i;
			f = i;
			while(g >= 0 && pattern[g] == pattern[g + plen - 1 -f])
				--g;
			result[i] = f - g;
		}
	}
	
	return result;
}

1. .length 屬性型別是 ulong ，不能自動轉換，所以 cast(int)pattern.length
2. 目前找不到文件解釋上面的 casting 是否合法 (未定義！？)

搜！

j = 0;
while(j <= cast(int)text.length - plen) {
	int i = plen - 1;
	for(; i >= 0 && pattern[i] == text[i + j]; --i){}
	if (i < 0) {
		writeln(j);
		j += delta2[0];
	} else 
		j += max(delta2[i], delta1[text[i + j]] - plen + 1 + i);
}

完整程式

import std.stdio;                                                                                                                                                                                        
import std.algorithm: max;

auto suffixes(T)(const T[] pattern) {
    const int plen = cast(int)pattern.length;
    int[] result = new int[plen];

    result[$-1] = plen;
    int g = plen - 1;
    int f;

    for(int i = plen - 2; i >= 0; --i) {
        if(i > g && result[i + plen - 1 - f] < i - g)
            result[i] = result[i + plen - 1 - f];
        else {
            if (i < g)
                g = i;
            f = i;
            while(g >= 0 && pattern[g] == pattern[g + plen - 1 -f])
                --g;
            result[i] = f - g;
        }
    }
    return result;
}

void boyer_moore_matching(T)(const T[] text, const T[] pattern) {
    if(pattern.length == 0)
        return text;

    const int plen = cast(int)pattern.length;
    const int alphabet_size = 1 << (T.sizeof << 3);
    int[alphabet_size] delta1;

    // preprocess for delta1
    delta1[0..$] = plen;
    foreach(int i, c; pattern[0..($-1)]) {
        delta1[c] = plen - 1 - i;
    }

    int[] delta2 = new int[plen];
    int[] suff = suffixes(pattern);

    // preprocess for delta2
    delta2[0..$] = plen;
    int j = 0;

    foreach_reverse(i, _; pattern) {
        if(suff[i] == i + 1) {
            for(; j < plen - 1 - i; ++j) {
                if(delta2[j] == plen)
                    delta2[j] = plen - 1 - cast(int)i;
            }
        }
    }

    for(int i = 0; i < plen - 1; ++i)
        delta2[plen - 1 - suff[i]] = plen - 1 - i;

	// matching
    j = 0;
	while(j <= cast(int)text.length - plen) {
        int i = plen - 1;
        for(; i >= 0 && pattern[i] == text[i + j]; --i){}
        if (i < 0) {
            writeln(j);
            j += delta2[0];
        } else
            j += max(delta2[i], delta1[text[i + j]] - plen + 1 + i);
    }
}

void main() {
    boyer_moore_matching!char("abaccabaabbccababbccab", "abbccab");
}

最後想說一件事，其實 D 的標準函式庫有 boyerMooreFinder 。

參考資訊

• Boyer-Moore algorithm, Thierry Lecroq
• Boyer–Moore string search algorithm, Wikipedia
• Computer Algorithms: Boyer-Moore String Searching

---

Written with StackEdit.