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

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

การจับคู่สตริงแบบฮัวส์ปัวร์ หรือ 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 เก็บถาวร 2021-11-27 ที่ เวย์แบ็กแมชชีน ค้นหาเมื่อ 28 มีนาคม 2561

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