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

การจับคู่สตริงแบบฮัวส์ปัวร์ 
การจับคู่สตริงแบบฮัวส์ปัวร์ หรือ 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

หมวดหมู่:ขั้นตอนวิธีการจับคู่สายอักขระ