ขั้นตอนวิธีบอยเออร์–มัวร์–ฮอร์สพูล

การจับคู่สตริงแบบฮัวส์ปัวร์

การจับคู่สตริงแบบฮัวส์ปัวร์ หรือ Boyer-Moore-Horspool เป็นอัลกอริทึมที่ใช้ในการจับคู่สตริง (String Matching) ด้วยการเปรียบเทียบ pattern จากทางด้านขวาไปด้านซ้าย มีการปรับปรุงมาจาก Boyer Moore โดยเลือกใช้ Bad-Charactor เฉพาะ Last occurrence (การเกิดขึ้นครั้งสุดท้าย)

การเลื่อนตำแหน่ง

จะมีการสร้าง Bad Match Table โดย

จำนวนครั้งที่เลื่อน = ความยาวของ Pattern - ตำแหน่งของตัวอักษร - 1

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

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

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

เนื่องจากตัวที่ไม่ตรงกันกับ Text คือ c และ มี a ปรากฏใน Pattern จึงทำการเลื่อนตำแหน่งให้ a ใน Patern ตรงกับ a ใน Text โดยมีจำนวนครั้งการเลื่อน = 5 - 1 - 1 = 3

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

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

ความซับซ้อนของการทำงาน

Worst-case จะเป็นกรณีที่มีการเลื่อนของตัวอักษรถัดไปน้อย จะมีตวามซับซ้อนเป็น O(nm)

Best-case จะคล้ายกับของ Boyer-Moore ซึ่งก็คือ หากไม่มีตัวอักษรอยู่เลย จะส่งผลให้เกิดการเปลี่ยนแปลงด้วยความยาวของ pattern (m) จะมีความซับซ้อนเป็น O(n/m)

Code Python ของ การจับคู่สตริงแบบฮัวส์ปัวร์

def horspool(text,pattern): len_text = len(text) len_pattern = len(pattern) results = [] if len_pattern>len_text or len_text==0 or len_pattern==0: return results table = {index: len_pattern for index in range(256)} for index, char in enumerate(pattern): table[ord(char)] = len_pattern - index - 1 index = 0 while index <= len_text - len_pattern: skip = 0 text_part = text[index:index + len_pattern][::-1] for index2, current_char in enumerate(text_part): if pattern[len_pattern - index2 - 1] != current_char: skip = table[ord(current_char)] break else: results.append(index) skip = 1 index += skip return results 

แหล่งอ้างอิง

kagan94 Boyer Moore Horspool algorithm^{[ลิงก์เสีย]} ค้นหาเมื่อ 25 มีนาคม 2561

Nelson Rush BOYER-MOORE-HORSPOOL STRING SEARCHING ค้นหาเมื่อ 28 มีนาคม 2561

mtu Space and Time Tradeoffs ค้นหาเมื่อ 28 มีนาคม 2561