ในวิทยาการคอมพิวเตอร์อัลกอริทึม Boyer–Moore–Horspoolหรืออัลกอริทึมของ Horspoolเป็นอัลกอริทึมสำหรับการค้นหาสตริงย่อยในสตริง อั ลกอริทึม นี้ได้รับการเผยแพร่โดยNigel Horspoolในปี 1980 ในชื่อ Simplified Boyer–Moore (SBM) ^{[ 1 ]}

นี่คือการลดทอนความซับซ้อนของอัลกอริทึมการค้นหาสตริง Boyer–Mooreซึ่งเกี่ยวข้องกับอัลกอริทึม Knuth–Morris–Pratt อัลกอริทึมนี้แลกเปลี่ยนพื้นที่จัดเก็บข้อมูลกับเวลา เพื่อให้ได้ความซับซ้อนโดยเฉลี่ยที่O(n)สำหรับข้อความแบบสุ่ม แม้ว่าจะมีO(nm)ในกรณีที่เลวร้ายที่สุดก็ตาม โดยที่ความยาวของรูปแบบคือmและความยาวของสตริงที่ใช้ค้นหาคือn

เช่นเดียวกับ Boyer–Moore, Boyer–Moore–Horspool จะประมวลผลรูปแบบล่วงหน้าเพื่อสร้างตารางที่มีจำนวนอักขระที่สามารถข้ามได้อย่างปลอดภัยสำหรับแต่ละสัญลักษณ์ในตัวอักษรขั้นตอนการประมวลผลล่วงหน้าในรูปแบบรหัสเทียมมีดังนี้ (สำหรับตัวอักษรที่มี 256 สัญลักษณ์ หรือไบต์):

// ต่างจากต้นฉบับ เราใช้ดัชนีแบบเริ่มต้นที่ศูนย์ที่นี่ฟังก์ชันpreprocess ( pattern ) T := ตารางใหม่ของ จำนวนเต็ม 256 ตัวสำหรับi ตั้งแต่0 ถึง256 (ไม่รวม) T [ i ] := ความยาวของ( pattern ) สำหรับi ตั้งแต่0 ถึงความยาวของ( pattern ) - 1 (ไม่รวม) T [ pattern [ i ]] := ความยาวของ( pattern ) - 1 - i ส่งคืนT

การค้นหารูปแบบดำเนินไปดังนี้ ขั้นตอนการค้นหาจะรายงานดัชนีของการพบ"เข็มในกองฟาง " ครั้งแรก

// เปรียบเทียบสตริงสองสตริง โดยตรวจสอบได้สูงสุด len ตัวอักษรแรก// หมายเหตุ: ฟังก์ชันนี้เทียบเท่ากับ !memcmp(str1, str2, len) function same ( str1 , str2 , len ) i := len - 1 // อัลกอริทึมดั้งเดิมพยายามใช้กลยุทธ์ที่ชาญฉลาด โดยตรวจสอบตัวอักษรตัวสุดท้ายก่อน จากนั้นตัวอักษรตัวรองสุดท้าย เป็นต้นwhile str1 [ i ] == str2 [ i ] if i == 0 return true i := i - 1 return falseฟังก์ชันsearch ( needle , haystack ) T := preprocess ( needle ) skip := 0 // haystack[skip:] หมายถึงสตริงย่อยที่เริ่มต้นที่ดัชนี `skip` จะเป็น &haystack[skip] ในภาษา C ในขณะที่length ( haystack ) - skip >= length ( needle ) ถ้าsame ( haystack [ skip : ] , needle , length ( needle )) ให้คืนค่าskip skip := skip + T [ haystack [ skip + length ( needle ) - 1 ]] ให้คืนค่า- 1

อัลกอริทึมนี้ทำงานได้ดีที่สุดกับสตริงคำค้นหาที่ยาว เมื่อมันพบอักขระที่ไม่ตรงกันอย่างต่อเนื่องที่หรือใกล้ไบต์สุดท้ายของตำแหน่งปัจจุบันในกองข้อมูล และไบต์สุดท้ายของคำค้นหาไม่ปรากฏที่อื่นภายในคำค้นหานั้น ตัวอย่างเช่น คำค้นหาขนาด 32 ไบต์ที่ลงท้ายด้วย "z" ค้นหาในกองข้อมูลขนาด 255 ไบต์ซึ่งไม่มีไบต์ "z" อยู่ จะต้องใช้การเปรียบเทียบมากถึง 224 ไบต์

กรณีที่ดีที่สุดนั้นเหมือนกับกรณีของอัลกอริธึมการค้นหาสตริง Boyer–Moore ในสัญกรณ์ Big Oแม้ว่าค่าใช้จ่ายคงที่ของการเริ่มต้นและการวนซ้ำแต่ละครั้งจะน้อยกว่าก็ตาม

พฤติกรรมที่เลวร้ายที่สุดเกิดขึ้นเมื่อค่าการข้ามอักขระที่ไม่ถูกต้องต่ำอย่างต่อเนื่อง (โดยมีขีดจำกัดล่างคือการเคลื่อนย้าย 1 ไบต์) และส่วนใหญ่ของข้อมูลที่ต้องการค้นหาตรงกับข้อมูลที่ต้องการในกองข้อมูล ค่าการข้ามอักขระที่ไม่ถูกต้องจะต่ำเฉพาะในกรณีที่ตรงกันบางส่วน เมื่ออักขระสุดท้ายของข้อมูลที่ต้องการค้นหาปรากฏอยู่ที่อื่นภายในข้อมูลที่ต้องการค้นหาด้วย โดยมีการเคลื่อนย้าย 1 ไบต์เกิดขึ้นเมื่อไบต์เดียวกันอยู่ในสองตำแหน่งสุดท้าย

กรณีเสื่อมสภาพตามแบบแผนที่คล้ายกับกรณี "ดีที่สุด" ข้างต้น คือ การค้นหาไบต์ 'a' ตามด้วยไบต์ 'z' จำนวน 31 ไบต์ ในกองไบต์ 'z' จำนวน 255 ไบต์ กระบวนการนี้จะทำการเปรียบเทียบไบต์สำเร็จ 31 ครั้ง จากนั้นจะทำการเปรียบเทียบไบต์ล้มเหลว 1 ครั้ง แล้วจึงเลื่อนไปข้างหน้า 1 ไบต์ กระบวนการนี้จะทำซ้ำอีก 223 ครั้ง (255 − 32) ทำให้จำนวนการเปรียบเทียบไบต์ทั้งหมดเป็น 7,168 ครั้ง (32 × 224) (ลูปการเปรียบเทียบไบต์ที่แตกต่างกันจะมีพฤติกรรมที่แตกต่างกัน)

กรณีที่เลวร้ายที่สุดนั้นสูงกว่าอัลกอริทึมการค้นหาสตริงของ Boyer–Moore อย่างมาก แม้ว่าโดยทั่วไปแล้วจะยากที่จะทำให้เกิดกรณีเช่นนี้ได้ก็ตาม นอกจากนี้ยังควรสังเกตว่ากรณีที่เลวร้ายที่สุดนี้ยังเป็นกรณีที่เลวร้ายที่สุดสำหรับmemcmp()อัลกอริทึมแบบพื้นฐาน (แต่ใช้กันทั่วไป) ด้วยเช่นกัน แม้ว่าการใช้งานอัลกอริทึมนั้นมักจะได้รับการปรับปรุงให้เหมาะสมยิ่งขึ้น (และเป็นมิตรกับแคชมากกว่า)

ฟังก์ชัน same_orig(str1, str2, len) i ← 0 ถ้า str1[len - 1] = str2[len - 1] ในขณะที่ str1[i] = str2[i] ถ้า i = len - 2 ให้คืนค่า true i ← i + 1 ส่งคืนค่าเท็จ

ฟังก์ชัน same_raita(str1, str2, len) i ← 0 กลาง ← ความยาว / 2 มีการตรวจสอบเบื้องต้น 3 ข้อ: ถ้า len ≥ 3 ถ้า str[mid] != str2[mid] ให้คืนค่า false ถ้า len ≥ 1 ถ้า str[0] != str2[0] ให้คืนค่า false ถ้า len ≥ 2 ถ้า str[len - 1] != str2[len - 1] ให้คืนค่า false ลูปเปรียบเทียบแบบใดก็ได้ส่งคืนค่า len < 3 หรือ SAME(&str1[1], &str2[1], len - 2)

• คำอธิบายของอัลกอริธึม
• การนำเอนจิน JavaScript V8 มาใช้งานโดยเขียนด้วยภาษา C++