好後綴規則 (長度 1)
比對方向 ← ０１２３４ ＱＱＱＱＣＣＣＡＢＣ Ｘ｜ ＣＣＡＢＣ ０１２３４ 移動方向 → 壞字符：Ｑ 壞字符位置：３ 好後綴：Ｃ (壞字符右邊的字。位於$Text。 $Key也有相同的字 ) 好後綴位置：４ (總是 最大索引值 ４) 尋找範圍： 在後續移動過程中，仍有機會和「$Text裡的好後綴Ｃ」對齊的字： $Key[0]到 $Key[3] (那些字總是位於 $Key最後一個字的左邊 ) 和好後綴相同的字的位置：１ 額外檢查： 位置 １ 的左邊的字：Ｃ 「$Key裡的好後綴」的左邊的字：Ｂ (它和壞字符比對失敗過) 以上兩者不相同，所以可以移到 位置１ 移動格數：好後綴位置 - 找到的位置 4 - 1 = 3 ＱＱＱＱＣＣＣＡＢＣ ｜ ＣＣＡＢＣ 找到Ｃ對齊，移動３格 有 2 個 Ｃ 找距離「好後綴」最近的那個
額外檢查失敗的例子 比對方向 ← ０１２３４ ＱＱＱＱＣＢＣＡＢＣ Ｘ ＢＣＡＢＣ ０１２３４ 移動方向 → 壞字符：Ｑ 壞字符位置：３ 好後綴：Ｃ (壞字符右邊的字。位於$Text。 $Key也有相同的字 ) 好後綴位置：４ (總是 最大索引值 ４) 尋找範圍： 在後續移動過程中，仍有機會和「$Text裡的好後綴Ｃ」對齊的字： $Key[0]到 $Key[3] (那些字總是位於 $Key最後一個字的左邊 ) 和好後綴相同的字的位置：１ 額外檢查： 位置 １ 的左邊的字：Ｂ 「$Key裡的好後綴」的左邊的字：Ｂ (它和壞字符比對失敗過) 以上兩者相同，所以不可以移到 位置 １ ＱＱＱＱＣＢＣＡＢＣ Ｘ｜ ＢＣＡＢＣ 勉強移到 位置 １的結果 Ｃ可以對齊 但Ｂ不行。就像上次那樣 ＱＱＱＱＣＢＣＡＢＣ ｜ ＢＣＡＢＣ 最後，沒有找到可以對齊的 移動格數：4 - (-1) = 5
左邊沒有東西、不用額外檢查 比對方向 ← ０１２３４ ＱＱＱＱＣＣＡＡＢＣ Ｘ ＣＡＡＢＣ ０１２３４ 移動方向 → 壞字符：Ｑ 壞字符位置：３ 好後綴：Ｃ (壞字符右邊的字。位於$Text。 $Key也有相同的字 ) 好後綴位置：４ (總是 最大索引值 ４) 尋找範圍： 在後續移動過程中，仍有機會和「$Text裡的好後綴Ｃ」對齊的字： $Key[0]到 $Key[3] (那些字總是位於 $Key最後一個字的左邊 ) 和好後綴相同的字的位置：０ 位置 ０ 的左邊的字：沒有 不用額外檢查了 移動格數：好後綴位置 - 找到的位置 4 - 0 = 4 ＱＱＱＱＣＣＡＡＢＣ ｜ ＣＡＡＢＣ 找到Ｃ對齊，移動４格
好後綴規則(長度 1) vs 壞字符規則
兩者很像。以下是它們的差別。 $i 為比對失敗位置 尋找範圍： Bc：$Key[$i]的左邊 Gs：$Key[-1]的左邊 ($Key最後一個字的左邊) 符合的條件： Bc:和「壞字符」一樣 Gs: 1. 和「好後綴」($Key最後一個字) 一樣 2. 需要作「額外檢查」 需不需要去猜「壞字符」是什麼？ Bc:需要。 因此，製表時需要較大的空間 $B4 = @( 4 - (-1) ) * 256 使用表格時，需要知道「壞字符」是什麼 [int]$badChar = $Text[$base + $i] if ( $Bc[$i][ $badChar ] -gt $Gs[$i] ) Gs:不需要。
好後綴規則 (長度 2)
比對方向 ← ０１２３４５ ＱＱＱＱＢＣＢＢＣＡＢＣ Ｘ ＢＢＣＡＢＣ ０１２３４５ 移動方向 → 壞字符：Ｑ 壞字符位置：３ 好後綴：ＢＣ (壞字符右邊的那些字。位於$Text。 $Key也有相同的字 ) 好後綴位置：５ (總是 最大索引值 ５) (它有兩個字，以５來代表) 尋找範圍： 在後續移動過程中，仍有機會和「$Text裡的好後綴ＢＣ」對齊的字： $Key[0]到 $Key[4] (那些字總是位於 $Key最後一個字的左邊 ) 和好後綴ＢＣ相同的字的位置：２ (它有兩個字，以索引２來代表) 額外檢查： 位置 ２(和位置１)的左側的字：Ｂ 「$Key裡的好後綴」的左側的字：Ａ (它和壞字符比對失敗過) 以上兩者不相同，所以可以移到 位置 ２ 移動格數：好後綴位置 - 找到的位置 5 - 2 = 3 ０１２３４５ ＱＱＱＱＢＣＢＢＣＡＢＣ ｜｜ ＢＢＣＡＢＣ 找到ＢＣ，而且左邊不同 移動格數：5 - 2 = 3
額外檢查失敗的例子 比對方向 ← ０１２３４５ ＱＱＱＱＢＣＡＢＣＡＢＣ Ｘ ＡＢＣＡＢＣ ０１２３４５ 移動方向 → 壞字符：Ｑ 壞字符位置：３ 好後綴：ＢＣ (壞字符右邊的那些字。位於$Text。 $Key也有相同的字 ) 好後綴位置：５ (總是 最大索引值 ５) (它有兩個字，以５來代表) 尋找範圍： 在後續移動過程中，仍有機會和「$Text裡的好後綴ＢＣ」對齊的字： $Key[0]到 $Key[4] (那些字總是位於 $Key最後一個字的左邊 ) 和好後綴ＢＣ相同的字的位置：２ (它有兩個字，以索引２來代表) 額外檢查： 位置 ２(和位置１)的左側的字：Ａ 「$Key裡的好後綴」的左側的字：Ａ (它和壞字符比對失敗過) 以上兩者相同，所以不可以移到 位置 ２ ＱＱＱＱＢＣＡＢＣＡＢＣ Ｘ｜｜ ＡＢＣＡＢＣ 勉強移到 位置 ２的結果 ＢＣ可以對齊 但Ａ不行。就像上次那樣 ＱＱＱＱＢＣＡＢＣＡＢＣ ｜ ＡＢＣＡＢＣ 最後，沒有找到可以對齊的 移動格數：5 - (-1) = 6
左邊沒有東西、不用額外檢查 比對方向 ← ０１２３４５ ＱＱＱＱＢＣＢＣＣＡＢＣ Ｘ ＢＣＣＡＢＣ ０１２３４５ 移動方向 → 壞字符：Ｑ 壞字符位置：３ 好後綴：ＢＣ (壞字符右邊的那些字。位於$Text。 $Key也有相同的字 ) 好後綴位置：５ (總是 最大索引值 ５) (它有兩個字，以５來代表) 尋找範圍： 在後續移動過程中，仍有機會和「$Text裡的好後綴ＢＣ」對齊的字： $Key[0]到 $Key[4] (那些字總是位於 $Key最後一個字的左邊 ) 和好後綴ＢＣ相同的字的位置：１ (它有兩個字，以索引１來代表) 額外檢查： 位置 １(和位置０)的左側的字：沒有 不用額外檢查了 移動格數：好後綴位置 - 找到的位置 5 - 1 = 4 ０１２３４５ ＱＱＱＱＢＣＢＣＣＡＢＣ ｜｜ ＢＣＣＡＢＣ 找到ＢＣ ＢＣ左邊沒有東西，不用額外檢查 移動格數：5 - 1 = 4
部份好後綴、不用額外檢查 比對方向 ← ０１２３４５ ＱＱＱＱＢＣＣＡＢＡＢＣ Ｘ ＣＡＢＡＢＣ ０１２３４５ 移動方向 → 壞字符：Ｑ 壞字符位置：３ 好後綴：ＢＣ (壞字符右邊的那些字。位於$Text。 $Key也有相同的字 ) 好後綴位置：５ (總是 最大索引值 ５) (它有兩個字，以５來代表) 尋找範圍： 在後續移動過程中，仍有機會和「$Text裡的好後綴ＢＣ」對齊的字： $Key[0]到 $Key[4] (那些字總是位於 $Key最後一個字的左邊 ) 和好後綴ＢＣ相同的字的位置：沒有 和「部份好後綴Ｃ」相同的字的位置：０ 額外檢查： 因為是部份好後綴，不用額外檢查了 移動格數：好後綴位置 - 找到的位置 5 - 0 = 5 ０１２３４５ ＱＱＱＱＢＣＣＡＢＡＢＣ ｜ ＣＡＢＡＢＣ 當「完整版的後綴」找不到，「部份版的」也可以 只對齊Ｃ即可 移動格數：5 - 0 = 5
找到的對齊位置有兩種
1.通過額外檢查的位置 不能對齊「其他長度的好後綴」 比對方向 ← ０１２３４５６ ＱＱＱＱＱＢＣＢＢＢＣＡＢＣ Ｘ ＢＢＢＣＡＢＣ 移動方向 → 找到的位置３：長度 ２ 好後綴專用。不能對齊「其他長度的好後綴」 長度 ２ 好後綴 ０１２３４５６ ＱＱＱＱＱＢＣＢＢＢＣＡＢＣ ｜｜ ＢＢＢＣＡＢＣ 長度 １ 好後綴 ０１２３４５６ ＱＱＱＱＱＱＣＢＢＢＣＡＢＣ Ｘ｜ ＢＢＢＣＡＢＣ 長度 ３ 好後綴 ０１２３４５６ ＱＱＱＱＡＢＣＢＢＢＣＡＢＣ Ｘ｜｜ ＢＢＢＣＡＢＣ 長度 ４ 好後綴 ０１２３４５６ ＱＱＱＣＡＢＣＢＢＢＣＡＢＣ Ｘ｜｜ ＢＢＢＣＡＢＣ
2.不用額外檢查的位置 (左邊沒有東西) 「長度大於、等於它」的好後綴可以和它對齊 「長度 小於 它 」的好後綴不能和它對齊 比對方向 ← ０１２３４５６ ＱＱＱＱＱＢＣＢＣＡＣＡＢＣ Ｘ ＢＣＡＣＡＢＣ 移動方向 → 「長度 大於、等於 ２ 」的好後綴可以和它對齊 「長度 小於 ２ 」的好後綴不能和它對齊 長度 ２ 好後綴 ０１２３４５６ ＱＱＱＱＱＢＣＢＣＡＣＡＢＣ ｜｜ ＢＣＡＣＡＢＣ 長度 １ 好後綴 ０１２３４５６ ＱＱＱＱＱＱＣＢＣＡＣＡＢＣ Ｘ｜ ＢＣＡＣＡＢＣ 長度 ３ 好後綴 ０１２３４５６ ＱＱＱＱＡＢＣＢＣＡＣＡＢＣ ｜｜ ＢＣＡＣＡＢＣ 長度 ４ 好後綴 ０１２３４５６ ＱＱＱＣＡＢＣＢＣＡＣＡＢＣ ｜｜ ＢＣＡＣＡＢＣ
開始製表 $Gs
方法一： 根據比對失敗位置，計算好後綴長度 在可能的對齊位置，逐一確認：是否和好後綴相同？
$Key = 'ＢＣＡＢＣ' $Gs = @( 5 ) * 5 <# 結果： $Gs[0] = $Gs[1] = $Gs[2] = $Gs[3] = $Gs[4] = 5 $Gs是一個陣列、有5個元素。每個元素的值都是5 元素的索引值：比對失敗位置 元素的值：比對失敗發生時，要移動的距離 先假設找不到可以對齊的位置 移動距離 = 好後綴位置 - 找不到 = 4 - (-1) = 5 位置 4 沒有好後綴，稍後會再設值 $Gs[4] = 1 #> #========= 設定 $Gs[3] =========== #====== step 1：根據比對失敗位置，計算好後綴長度===== #好後綴位置 = 總是最後面的索引值 $good = 4 #好後綴長度 = 好後綴位置 - 比對失敗位置 $len = 4 - 3
#====== step 2：在可能的對齊位置，逐一確認：是否和好後綴相同？===== # $test 是可能的對齊位置 從 位置 3 開始找 # 位置 3 = 好後綴位置的左邊 = $good - 1 for($test = 3; $test -ge 0; $test--){ $g = $good $t = $test # $L -gt 0 表示：好後綴 還沒比對完 # $t -ge 0 表示：$Key[$t]還有字可以參加比對 # 如果 $t -lt 0 $Key[$t]已經沒有字可以參加比對 # 儘管 $L -gt 0 好後綴還沒比對完，也會停止比對 # 不斷使$g 和 $t 向左移動、進行比對 for ($L = $len ; $L -gt 0 -and $t -ge 0 ; $g--,$t--,$L--){ # 如果比對失敗，這個位置不可以對齊 if ($Key[$g] -ne $Key[$t]) {break} } #======== $Key[$t]已經沒有字可以參加比對 ======= # $t 對齊範圍左端 對齊範圍右端 # -1 0 $test # # $g $g + 1 $good # 好後綴的左端 好後綴的右端 # 也可以寫成 $Gs[3] = $g - $t if ($t -eq -1) { $Gs[3] = $good - $test ;break} #============ 好後綴比對完成 =============== # 而且，$Key[$t]還有字可以參加比對 # 檢查左側是否「不相同」 # 此時的 $t $g 為左側 # 左側 對齊範圍左端 對齊範圍右端 # $t $t + 1 $test # # $g $g + 1 $good # 左側 好後綴的左端 好後綴的右端 # # 也可以寫成 $Gs[3] = $g - $t # # 此時的 $g 也是 比對失敗位置 # 也可以寫成 $Gs[$g] = $g - $t if ($L -eq 0) { if ($Key[$g] -ne $Key[$t]) {$Gs[3] = $good - $test ;break } } } #上面只是$Gs[3]的設值，還有$Gs[2] $Gs[1] $Gs[0]和上例類似 #位置 4沒有好後綴 $Gs[4] = 1
方法二： 確認每個可能的對齊位置(從右邊開始 )，可以符合多少後綴長？
藉由所符合的後綴長，推得在哪一個「比對失敗位置」發生時，可以和好後綴對齊
$Key = 'ＢＣＡＢＣ' $Gs = @( 5 ) * 5 <# 結果： $Gs[0] = $Gs[1] = $Gs[2] = $Gs[3] = $Gs[4] = 5 $Gs是一個陣列、有5個元素。每個元素的值都是5 元素的索引值：比對失敗位置 元素的值：比對失敗發生時，要移動的距離 先假設找不到可以對齊的位置 移動距離 = 好後綴位置 - 找不到 = 4 - (-1) = 5 位置 4 沒有好後綴，稍後會再設值 $Gs[4] = 1 #> #好後綴位置 = 總是最後面的索引值 $good = 4 # $test 是可能的對齊位置 從 位置 3 開始找 # 位置 3 = 好後綴位置的左邊 = $good - 1 for($test = 3; $test -ge 0; $test--){ $g = $good $t = $test # 使$g 和 $t 持續向左移動、進行比對 # $t 可能會到達最左邊(接下來，就沒有字了) for ( ; $t -ge 0 ; $g--,$t--){ if ($Key[$g] -ne $Key[$t]) {break} } if ($t -eq $test){ # ===== 可能 1 ：$t根本沒移動。符合 0 個 後綴長 ====== }elseif($t -eq -1){ # === 可能 2 ：$t 已經到達 $Key的最前面了，沒有字可供繼續比對了=== # 符合的後綴長 等於 ($test + 1) 也等於 ($good - $g) # 比對失敗位置 等於 好後綴位置 - 符合的後綴長 # 等於 $good - ($test + 1) # 也等於 $g # $t 對齊範圍左端 對齊範圍右端 # -1 0 $test # # $g $g + 1 $good # 比對失敗位置 好後綴的左端 好後綴的右端 #如果仍是預設值，才設值 if ($Gs[$g] -eq 5){$Gs[$g] = $good - $test} # 比對失敗位置 $g 左邊的那些位置： 0 到 ($g - 1) # 所需要對齊的後綴長 大於 $test所提供的長度 # $test 可以和這些比對失敗位置的好後綴對齊 for ($i = 0; $i -lt $g; $i++){ #如果仍是預設值，才設值 if ($Gs[$i] -eq 5){$Gs[$i] = $good - $test} } }else{ #===== 可能 3 ：$t 移動了幾格。符合了幾格後綴長 ====== # $t 介於 「完全不動」和「沒有字可比對」 之間 # 符合的後綴長 等於 ($test - $t) 也等於 ($good - $g) # 比對失敗位置 等於 好後綴位置 - 符合的後綴長 # 等於 $good - ($test -$t) # 也等於 $g # 左側不同 對齊範圍左端 對齊範圍右端 # $t $t + 1 $test # # $g $g + 1 $good # 比對失敗位置 好後綴的左端 好後綴的右端 #如果仍是預設值，才設值 if ($Gs[$g] -eq 5){$Gs[$g] = $good - $test} } } #位置 4沒有好後綴 $Gs[4] = 1
方法三： 確認每個可能的對齊位置(從最左邊開始 )，可以符合多少後綴長？
藉由所符合的後綴長，推得在哪一個「比對失敗位置」發生時，可以和好後綴對齊
$Key = 'ＢＣＡＢＣ' $Gs = @( 5 ) * 5 <# 結果： $Gs[0] = $Gs[1] = $Gs[2] = $Gs[3] = $Gs[4] = 5 $Gs是一個陣列、有5個元素。每個元素的值都是5 元素的索引值：比對失敗位置 元素的值：比對失敗發生時，要移動的距離 先假設找不到可以對齊的位置 移動距離 = 好後綴位置 - 找不到 = 4 - (-1) = 5 位置 4 沒有好後綴，稍後會再設值 $Gs[4] = 1 #> #好後綴位置 = 總是最後面的索引值 $good = 4 #移動距離的預設值 $defaultMove = 5 # $test 是可能的對齊位置，從最左邊開始找。 for($test = 0; $test -le 3; $test++){ $g = $good $t = $test # 使$g 和 $t 持續向左移動、進行比對 # $t 可能會到達最左邊(接下來，就沒有字了) for ( ; $t -ge 0 ; $g--,$t--){ if ($Key[$g] -ne $Key[$t]) {break} } if ($t -eq $test){ # ===== 可能 1 ：$t根本沒移動。符合 0 個 後綴長 ====== # 原本想要符合的後綴長 ($test + 1 ) # 比對失敗位置 等於 好後綴位置 - 符合的後綴長 # 等於 $good - ($test + 1 ) # 使用預設值 $Gs[$good - $test -1 ] = $defaultMove }elseif($t -eq -1){ # === 可能 2 ：$t 已經到達 $Key的最前面了，沒有字可供繼續比對了=== # 符合的後綴長 等於 ($test + 1) 也等於 ($good - $g) # 比對失敗位置 等於 好後綴位置 - 符合的後綴長 # 等於 $good - ($test + 1) # 也等於 $g # $t 對齊範圍左端 對齊範圍右端 # -1 0 $test # $g $g + 1 $good # 比對失敗位置 好後綴的左端 好後綴的右端 $Gs[$g] = $good - $test #修改移動距離的預設值 $defaultMove = $good - $test # 比對失敗位置 $g 左邊的那些位置： 0 到 ($g - 1) # 所需要對齊的後綴長 大於 $test所提供的長度 # $test 可以和這些比對失敗位置的好後綴對齊 # $Gs[0] 到 $Gs[$g - 1] 都可以設值為 $good - $test # 在此先不設值，而是把值先存到 $defaultMove # $test 在之後的回合裡，會向右移動 # 會陸續設定 $Gs[$g - 1] 到 $Gs[0] # 等到沒找到更適合的值，再使用 $defaultMove }else{ #===== 可能 3 ：$t 移動了幾格。符合了幾格後綴長 ====== # 此處的$t 介於 「完全不動」和「$Key最前面」 之間 # 符合的後綴長 等於 ($test - $t) 也等於 ($good - $g) # 比對失敗位置 等於 $good - ($test -$t) # 也等於 $g # 左側不同 對齊範圍左端 對齊範圍右端 # $t $t + 1 $test # # $g $g + 1 $good # 比對失敗位置 好後綴的左端 好後綴的右端 $Gs[$g] = $good - $test } } #位置 4沒有好後綴 $Gs[4] = 1
沒有留言:
張貼留言