[演算法] KMP

KMP演算法是在一段文字中，找出指定的子字串出現位置(substring search)的演算法
比較詳細的說明我就不闡述，把資料留在文末。

名詞定義一下:
在一段文字中的文字，假設叫做 text
要搜尋的子字串，假設叫做 pattern
在 text 中比對到的位置使用 i,
在 pattern 中比對的位置使用 j

Prerequisites

  • 製作出 prefix table


什麼是 Prefix table
Prefix table 是這個 pattern 字串所有的子字串的最長前後綴的表

舉例:
pattern = ABCDABD

各個子字串的最長前後綴

子字串 前綴 (prefix) 後綴 (prefix) 最大公前後綴字串長度
A 空 空 0
AB A B 0
ABC A,AB C,BC 0
ABCD A,AB,ABC D,CD,BCD 0
ABCDA A,AB,ABC,ABCD A,DA,CDA,BCDA 1
ABCDAB A,AB,ABC,ABCD,ABCDA B,AB,DAB,CDAB,BCDAB 2

這時候就可以把最大公前後綴字串長度變成程式在用的模式
pattern

A B C D A B D
0 0 0 0 1 2 0
-1 0 0 0 0 1 2

為什麼要多下面
-1 0 0 0 0 1 2 ?
其實就是把 prefix table 往後移動一位，在最前面補上 -1
而且完整的 pattern 其實用不到，所以大部分的做法都會這樣做哦！

其實 prefix table 的用意就是說
假設在 pattern 的 j = 5時，所座落在的位置：B
也就是 ABCDABD
前面最大相同的字串長度一定至少有兩位是一樣的，也就是至少是 AB!

當把 prefix table 建立完成之後，剩下就比較單純了

假設 text = "ABC ABCDAB ABCDABCDABDE"
pattern = "ABCDABD"

i = 0, j = 0
text[0] == pattern[0] => A == A => 所以接著比對下一個 => i++; j++;
.
.
.
i = 3, j = 3
text[3] != pattern[3] => ' ' !== D => 這時候看一下 prefix table 的第j (j=3) 個位置
=> prefix[3] = 0
=> 所以把 j 移動到 0, 也就是 i = 3, j = 0 繼續比較
             1         2  
i: 01234567890123456789012
T: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
j: 0123456

i = 3, j = 0
text[3] != pattern[0] => ' ' !== A => 這時候看一下 prefix table 的第j (j=0) 個位置
=> prefix[0] = -1 
=> 所以把 j 移動到 j = -1
=> j = -1 時就直接跳下一個
=> 直接跳下一個 => i++; j++
=> i = 4, j = 0
             1         2  
i: 01234567890123456789012
T: ABC ABCDAB ABCDABCDABDE
P:     ABCDABD
j:     0123456

i = 4, j = 0 接下來就一直比對到 i = 10, j = 6,
text[10] != pattern[6] => ' ' != D => 這時候看一下 prefix table 的第j (j=6) 個位置
=> prefix[6] = 2
=> 所以把 j 移動到 2, 也就是 i = 10, j = 2 繼續比較
             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456
i = 10, j = 2
text[10] != pattern[2] => ' ' != C => 這時候看一下 prefix table 的第j (j=2) 個位置
=> prefix[2] = 0
=> 所以把 j 移動到 0, 也就是 i = 10, j = 0 繼續比較
             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:           ABCDABD
i:           0123456
i = 10, j = 0
text[10] != pattern[0] => ' ' != A => 這時候看一下 prefix table 的第j (j=0) 個位置
=> prefix[0] = -1
=> j = -1
=> i++; j++;
=> i = 11, j = 0

i = 11, j = 0
沿路比對到
i = 17, j = 6
             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

i = 17, j = 6
text[17] != pattern[6] => C != D => 這時候看一下 prefix table 的第j (j=6) 個位置
=> prefix[6] = 2
=> 所以把 j 移動到 2, 也就是 i = 17, j = 2 繼續比較
             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456

這次就剛好
i = 17, j = 2 沿路比對到 i = 21, j = 6 一路都相等且 j 為最後一位
這時候就找出 pattern 的位置為 i - j => 21 - 6 = 15!

function prefixTable(pattern) {
    let maxPrefixLength = 0;
    let prefixTable = [0];
    let i = 1;
    while ( i < pattern.length ) {
        if (pattern[i] === pattern[maxPrefixLength]) {
            maxPrefixLength++;
            prefixTable[i] = maxPrefixLength;
            i++;
        } else {
            if (maxPrefixLength > 0) {
                maxPrefixLength = prefixTable[maxPrefixLength-1];    
            } else {
                maxPrefixLength = 0;
                prefixTable[i] = maxPrefixLength;
                i++;
            }
        }
    }
    return prefixTable;
}

function movePrefixTable(prefixTable) {
    let newPrefix = [...prefixTable];
    for (i = newPrefix.length -1; i > 0; i--) {
        newPrefix[i] = newPrefix[i-1];
    }
    newPrefix[0] = -1;
    return newPrefix;
}

function kmpSearch(text, pattern) {
    let m = text.length;
    let n = pattern.length;
    let prefix = movePrefixTable(prefixTable(pattern));
    let i = 0;
    let j = 0;

    while (i < m) {
        if (text[i] === pattern[j] && j === (n-1)) {
            return i - j;
        }
        if (text[i] === pattern[j]) {
            i++; j++;
        } else {
            j = prefix[j];
            if (j === -1) {
                i++;
                j++;
            }
        }
    }
    return -1
}

補充資料:
https://www.youtube.com/watch?v=dgPabAsTFa8

留言

張貼留言

這個網誌中的熱門文章

[MySQL] schema 與資料類型優化

圖片
選擇優化的資料類型 原則: 越小越好 因為會佔用最小的磁碟、記憶體與CPU快取。 越簡單越好 操作整數比操作字串代價低，因為字串排序規則 ex: 儲存ip應該用 unsigned int - 4 bytes, 用 varchar 會用到 15 bytes 儲存時間應該用 mysql 內建的時間類型 DATETIME, TIMESTAMP可以儲存相同資料：時間日期，精確到秒 TIMESTAMP 只用 DATETIME 一半的儲存空間，根據時區自動變化 TIMESTAMP 允許的時間範圍比 DATETIME 小很多 避免 NULL 在 innodb 上有單獨的 bit 儲存 null 值，但在 myisam，但還是盡量避免 整數類型 tinyint - 8 bits smallint - 16 bits mediumint - 24 bits int - 32 bits bigint - 64 bits 如果是有正負數的，會因為 1 bits 會用來記錄正負，故範圍為 -2^(n-1) ~ 2^(n-1) unsigned 的範圍則是 -2^n ~ 2^n MySQL 可以為整數指定寬度，例如 INT(11)，其實沒什麼意義，11只是表示與 MySQL 相關工具(client 端的 cli) 用來顯示的長度，對於儲存與計算來說，INT(1)與INT(20)是一樣的。 實數類型 decimal(M,N) - M: 最大位數, N: 小數點後有幾位 ex: decimal(18, 9) => 9位數字.9位數字，總共使用 9 個 bytes float => 4 bytes double => 8 bytes decimal的計算雖然比較精確，但需要額外，但需要額外的空間與計算開銷，資料量較大時，可以用 bigint 代替 decimal，假設需要精準到萬分之一，則可以將數字*1百萬，將結果存在 bigint 內，可以同時避免福點數計算不精準與 decimal 計算代價太高。 字串類型 VARCHAR row_format=fix，這樣就都會固定長度，沒意義 varchar會需要額外1~2 bytes記錄長度, 假設用 latin1 charset, varchar(10) => 11 bytes, varchar(1000) => 1002...
閱讀完整內容

[翻譯] 介紹現代網路負載平衡與代理伺服器

圖片
原文(Source): https://blog.envoyproxy.io/introduction-to-modern-network-load-balancing-and-proxying-a57f6ff80236 什麼是網路負載平衡 (network load balancing) 與 代理伺服器的代理行為 (proxying)? 維基百科是這樣定義負載平衡的 > 負載平衡藉由工作量分配到多台運算資源, 例如: 主機, 主機叢集, 網路連結, CPU,  硬碟等. > 負載平衡盡量最佳化資源的使用, 最大化每個最大化每個資源的吞吐量(生產能力), 最小化反應時間, 避免單一資源工作量過重 > 使用多個資源來當負載平衡來提升可靠與高可用而不是單一個資源 > 負載平衡總是使用獨立的軟體或硬體, 例如獨立的 multilayer switch, 或是 DNS主機的程式 上面的定義用於各資訊領域的各方面, 不單單只有網路而已. 作業系統使用負載平衡在實體處理器去分配運算任務, 容器編排服務像是K8S使用負載平衡在不同的主機叢集中去分配任務, 而網路負載平衡器則是將網路上進來的任務分配給可用的後端主機們. 剩下的文章主要都是講解關於網路負載平衡. 圖1 圖1展示了從應用層來看網路負載平衡. 許多的用戶端(Client)透過只需要向 load balancer 請求, load balancer就會將這些request, 也就是上述提到的任務分配給可用的後端服務. Load balancer位於Client 與後端之間執行幾個重要的任務: 服務發現 (Service discovery) 後端的服務在系統的哪裡, 他們的IP(位置)是什麼? (也就是load balancer該如何與後端主機溝通) 服務的狀態檢查 (Health checking) 現在的服務是否是可接受請求的 負載平衡 (Load Balancing) 該用什麼樣的演算法去平均將request分配給可用的服務 在分散式系統使用負載平衡主要有幾個好處: 主機抽象 (Naming abstraction): 每個client 不需要知道每個後端服務在哪, 只需要利用預先定義好的機制向負載平衡器...
閱讀完整內容