跳到主要內容

Boyer Moore String Matching in D Lang

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 。

參考資訊

Written with StackEdit.

標籤：

留言

張貼留言

這個網誌中的熱門文章

得利油漆色卡編碼方式

得利油漆色卡編碼方式 類似 Munsell 色彩系統 ，編碼方式為 HUE LRV/CHROMA 例如 10GY 61/449 ( 色卡 ) 編碼數值 描述 10GY hue ，色輪上從 Y(ellow) 到 G(reen) 區分為 0 ~ 99 ，數值越小越靠近 Y，越大越靠近 G 61 LRV (Light Reflectance Value) 塗料反射光源的比率，數值從 0% ~ 100% ，越高越亮，反之越暗，也可理解為明度 449 chroma 可理解為彩度，數值沒有上限，越高顏色純度 (濃度) 越高 取決於測量儀器，對應至 RGB 並不保證視覺感受相同。 參考資料： 色卡對照網站 e-paint.co.uk Written with StackEdit .
張貼留言
閱讀完整內容

UTF8 與 Unicode 的轉換 (C++)

UTF8 與 Unicode 的轉換 (C++) 先釐清一下這兩者的性質 Unicode: 為世界上所有的文字系統制訂的標準，基本上就是給每個字(letter)一個編號 UTF-8: 為 unicode 的編號制定一個數位編碼方法 UTF-8 是一個長度介於 1~6 byte 的編碼，將 unicode 編號 (code point) 分為六個區間如下表 1 Bits First code point Last code point Bytes Byte 1 Byte 2 Byte 3 Byte 4 Byte 5 Byte 6 7 U+0000 U+007F 1 0xxxxxxx 11 U+0080 U+07FF 2 110xxxxx 10xxxxxx 16 U+0800 U+FFFF 3 1110xxxx 10xxxxxx 10xxxxxx 21 U+10000 U+1FFFFF 4 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx 26 U+200000 U+3FFFFFF 5 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 31 U+4000000 U+7FFFFFFF 6 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 觀察上面的表應該可以發現 除了 7 bits 的區間外，第一個 byte 開頭連續 1 的個數就是長度，例如 110XXXXX 就是 2 byte 長，而 1110xxxx 就是 3 byte 除了第一個 byte 外，之後的 byte 前兩個 bit 一定是 10 開頭，這樣的好處在於確立了編碼的 self-synchronizeing，意即當編碼為多個 byte 時，任取一個 byte 無法正常解碼。 Note 第一點中的例外 (7 bits) 是為了與 ASCII 的相容性，而第二點會影響到 code point 至 UTF-8 的轉換。 為了與 UTF-16 的相容性，在 R...
張貼留言
閱讀完整內容

C++17 新功能 try_emplace

C++17 新功能 try_emplace 回顧 emplace 大家的好朋友 Standard Template Library (STL) 容器提供如 push_back , insert 等介面，讓我們塞東西進去； C++11 之後，新增了 emplace 系列的介面，如 std::vector::emplace_back , std::map::emplace 等，差異在於 emplace 是在容器內 in-place 直接建構新元素，而不像 push_back 在傳遞參數前建構，下面用實例來說明： struct Value { // ctor1 Value ( int size ) : array ( new char [ size ] ) , size ( size ) { printf ( "ctor1: %d\n" , size ) ; } // ctor2 Value ( const Value & v ) : array ( new char [ v . size ] ) , size ( v . size ) { printf ( "ctor2: %d\n" , size ) ; memcpy ( array . get ( ) , v . array . get ( ) , size ) ; } private : std :: unique_ptr < char [ ] > array ; int size = 0 ; } ; struct Value 定義了自訂建構子 (ctor1)，以指定大小 size 配置陣列，複製建構子 (ctor2) 則會配置與來源相同大小及內容的陣列，為了方便觀察加了一些 printf 。當我們如下使用 std::vector::push_back 時 std :: vector < Value > v ; v . push_back ( Value ( 2048 ) ) ; 首先 Value 會先呼叫 ctor1，傳給 push_ba...
張貼留言
閱讀完整內容