ขั้นตอนวิธีค้นหาสายอักขระบอยเยอร์–มัวร์

ขั้นตอนวิธีค้นหาสายอักขระบอยเยอร์-มัวร์ หรือ Boyer-Moore Algorithm เป็นวิธีการจับคู่แบบตรงทั้งหมด จะเปรียบเทียบสัญลักษณ์ของรูปแบบของ Pattern จากขวาไปซ้าย หลังการเปรียบเทียบรูปแบบที่ถูกเลื่อนไปแล้วตามขอบเขตที่กว้างที่สุดและจะเลื่อนค่าสูงสุดที่ถูกกำหนดโดย 2 กรณีคือ การแก้ปัญหา Good-Suffix และ การแก้ปัญหา Bad-Character

การแก้ปัญหา Bad-Character

ในการเลื่อนตำแหน่งจะหาได้จากตำแหน่งที่ผิดใน pattern ลบกับตำแหน่งที่ปรากฎใน pattern

ตัวอย่างการทำงาน

Text : [a, c, b, a, b, a, c, a, b, c, a, c, c]

Pattern : [a, b, c, a, c ]

(a) c ไม่เท่ากับ b และ b ปรากฎใน pattern จึ่งเลื่อนให้ b ในpattern ให้ตรงกับ b ใน text จะเลื่อนได้โดย 4-1 = 3 ตำแหน่ง

Text : [a, c, b, a, b, a, c, a, b, c, a, c, c]

Pattern : [a, b, c, a, c ]

(b) c ไม่เท่ากับ a และ a ปรากฎใน pattern จึ่งเลื่อนให้ a ในpattern ให้ตรงกับ a ใน text จะเลื่อนได้โดย 4-3 = 1 ตำแหน่ง

Text : [a, c, b, a, b, a, c, a, b, c, a, c, c]

Pattern : [a, b, c, a, c ]

(c) c ไม่เท่ากับ b และ b ปรากฎใน pattern จึ่งเลื่อนให้ b ในpattern ให้ตรงกับ b ใน text จะเลื่อนได้โดย 4-1 = 3 ตำแหน่ง

Text : [a, c, b, a, b, a, c, a, b, c, a, c, c]

Pattern : [a, b, c, a, c ]

(d) ทำการจับคู่เสร็จสมบูรณ์

การแก้ปัญหา Good-Suffix

ในการเลื่อนตำแหน่งจะหาได้จากความยาวของ pattern ลบกับความยาวตำแหน่งที่ปรากฎซึ่งจะต้องเป็นค่าสูงสุด

ตัวอย่างการทำงาน

Text : [b, a, a, c, d, b, a, c, a, c]

Pattern : [c, b, a, a, c]

(a) ในกรณีไม่ match ครั้งแรก ซึ่งตัวที่ถูกไม่มีเลย ให้เลื่อนไป 1 ตำแหน่ง

Text : [b, a, a, c, d, b, a, c, a, c]

Pattern : [c, b, a, a, c]

(b) กรณีที่ไม่มีตัวที่ match ใน pattern ให้เลื่อนไปด้วยความยาว pattern

Text : [b, a, a, c, d, b, a, c, a, c]

Pattern : [c, b, a, a, c]

(c) ปรากฎว่าไม่มีข้อความที่ตรงกัน

Text : [b, a, a, a, c, b, a, c, a, c]

Pattern : [a, c, b, c, c, b]

(d) กรณีที่ match แล้วมีตัวที่ match ใน pattern ให้เลื่อนไป 6-3 =3 ตำแหน่ง

Text : [b, a, a, a, c, b, a, c, a, c]

Pattern : [a, c, b, c, c, b]

กระบวนการที่จะแก้ปัญหาแบบ Good Suffix ค่อนข้างทำความเข้าใจแล้วดำเนินการยาก ดังนั้น อัลกอรึทึม Boyer Moore บางรุ่นได้ตัดการแก้ปัญหาGood Suffix ออกไปเนื่องจากการแก้ปัญหาแบบ Bad Character นั้นมีประสิทธิภาพมากกว่าและการแก้ป้ญหาแบบ Good Suffix จะเสียการเปรียบเทียบไปจำนวนมาก

ความซับซ้อนของเวลา

Best case : O(n/m) ถ้าตัวอักษรไม่มีอยู่เลยอาจส่งผลให้เกิดการเปลี่ยนแปลงโดยความยาว m

worst case : - O(nm) ถ้า pattern ปรากฏใน text

    - O(n+m) ถ้า pattern ไม่ปรากฏใน text

Code ของ Bad Character

def BadCharShift(pattern):     m = len(pattern)     skipList = {}     for i in range(0, m -1):         skipList[pattern[i]] = m-i-1     return skipList 

Code ของ Good Suffix

def findPosition(badchar, suffix, pattern): m = len(pattern) for offset in range(1, m+1)[::-1]: flag = True for suffix_index in range(0, len(suffix)): term_index = offset-len(suffix)-1+suffix_index if term_index < 0 or suffix[suffix_index] == pattern[term_index]: pass else: flag = False term_index = offset-len(suffix)-1 if flag and (term_index <= 0 or pattern[term_index-1] != badchar): return len(pattern)-offset+1 def SuffixShift(pattern): m = len(pattern) skipList = {} buffer = '' for i in range(0, m): skipList[len(buffer)] = findPosition(pattern[m-1-i], buffer, pattern) buffer = pattern[m-1-i] + buffer return skipList 

Code Boyer Moore

def Boyer_Moore(text, pattern): results = [] good = SuffixShift(pattern) bad = BadCharShift(pattern) n = len(text) m = len(pattern) i = 0 while i < n - m +1: j = m while j > 0 and pattern[j-1] == text[i+j-1]: j -= 1 if j > 0: badShift = bad.get(text[i+j-1], m) goodShift = good[m-j] if badShift > goodShift: i += badShift else: i += goodShift else: results.append(i) i += 1 return results 

อ้างอิง

ameerkat Boyer Moore string search implementation in Python ค้นหาเมืื่อ 1 เมษายน 2561

Korrakhod Baiya Boyer Moore Tang ค้นหาเมืื่อ 23 มีนาคม 2561

geeksforgeeks Pattern Searching | (Boyer Moore Algorithm – Bad Character Heuristic) ค้นหาเมืื่อ 3 เมษายน 2561

สมชาย ประสิทธิ์จูตระกูล อัลกอริทึม : 9.18 การจับคู่สตริง - Boyer-Moore ค้นหาเมืื่อ 20 มีนาคม 2561