ช่วงเวลาสุ่มและการค้นหาสตริงย่อย Rabin Karp
ฉันกำลังอ่านอัลกอริทึม Rabin-Karb จาก Sedgewick หนังสือกล่าวว่า:
เราใช้ Q ไพรม์แบบสุ่มโดยรับค่าให้มากที่สุดในขณะที่หลีกเลี่ยงการล้น
ในการอ่านครั้งแรกฉันไม่สังเกตเห็นความสำคัญของการสุ่มและเมื่อฉันเห็นว่าในรหัส a long
ถูกใช้ความคิดแรกของฉันคือ
a) ใช้ตะแกรงของ Eratosthene เพื่อค้นหาไพรม์ขนาดใหญ่ที่เหมาะกับ a long
หรือ
b) ค้นหาจากรายการของ ไพรม์ไพรม์ใด ๆ ที่ใหญ่พอที่มากกว่าint
และใช้เป็นค่าคงที่
แต่คำอธิบายที่เหลือก็บอกว่า:
เราจะใช้
long
ค่าที่มากกว่า10^20
ทำให้ความน่าจะเป็นที่การชนกันเกิดขึ้นน้อยกว่า10^-20
ส่วนนี้ทำให้ฉันสับสนเนื่องจากlong
ไม่สามารถใส่10^20
ค่าที่มากกว่านั้นได้ จากนั้นเมื่อฉันตรวจสอบการคำนวณสำหรับจำนวนเฉพาะหนังสือจะเลื่อนไปตามแบบฝึกหัดที่มีคำใบ้ต่อไปนี้:
ตัวเลข n หลักแบบสุ่มเป็นจำนวนเฉพาะโดยมีสัดส่วนความน่าจะเป็นเป็น 1 / n
นั่นหมายความว่าอย่างไร?
โดยพื้นฐานแล้วสิ่งที่ฉันไม่ได้รับคือ
ก) ความหมายของการใช้ไพรม์สุ่มคืออะไร? ทำไมเราไม่สามารถคำนวณล่วงหน้าและใช้เป็นค่าคงที่ได้?
b) เหตุใดจึงมีการ10^20
กล่าวถึงเนื่องจากอยู่นอกช่วงสำหรับlong
?
c) คำใบ้นั้นมีประโยชน์อย่างไร? หมายความว่าอย่างไรกันแน่?
คำตอบ
อีกครั้ง Sedgewick ได้พยายามทำให้อัลกอริทึมง่ายขึ้นและได้รับรายละเอียดผิดเล็กน้อย อันดับแรกอย่างที่คุณสังเกต 10 20ไม่สามารถแสดงเป็น 64 บิตได้ แม้จะเอาไพรม์เข้าใกล้ 2 63 - 1 อย่างไรก็ตามคุณอาจต้องการพื้นที่สักหน่อยในการคูณด้วยวิธีปกติโดยไม่ให้ล้นเพื่อให้โมดูโลที่ตามมานั้นถูกต้อง คำตอบใช้ไพรม์ 31 บิตซึ่งทำให้ง่าย แต่ให้ความน่าจะเป็นในการชนในช่วง 10 −9เท่านั้น
เวอร์ชันดั้งเดิมใช้ลายนิ้วมือของราบินและพหุนามแบบสุ่มที่ไม่สามารถวัดค่าได้ในช่วง𝔽 2 [x] ซึ่งจากมุมมองของทฤษฎีจำนวนพีชคณิตจะมีพฤติกรรมเหมือนกับการสุ่มไพรม์มากกว่าจำนวนเต็ม หากเราเลือกพหุนามเป็นระดับ 32 หรือ 64 ลายนิ้วมือจะพอดีกับคำในคอมพิวเตอร์ที่มีความยาวที่เหมาะสมและการบวกและการลบพหุนามจะทำงานเป็น XOR แบบบิตดังนั้นจึงไม่มีการล้น
ตอนนี้ Sedgewick คงไม่ต้องการอธิบายว่าแหวนพหุนามทำงานอย่างไร ละเอียด. ถ้าฉันต้องใช้แนวทางนี้ในทางปฏิบัติฉันจะเลือกไพรม์ p ใกล้กับค่าสูงสุดที่แก้ไขได้ง่ายโดยมีคำแนะนำราคาถูก (ฉันเป็นบางส่วนของ
2
31 - 2
27 + 1
; แก้ไขจริง 2 31 - 1 ทำงานได้ดียิ่งขึ้นเนื่องจากเราไม่จำเป็นต้องมีไพรม์สมูทที่นี่) จากนั้นเลือกตัวเลขสุ่มใน [1, p − 1] เพื่อประเมินพหุนามที่ (นี่คือวิธีที่ Wikipedia อธิบาย) เหตุผลที่เราต้องการการสุ่มก็คือมิฉะนั้นฝ่ายตรงข้ามที่หลงลืมสามารถเลือกอินพุตที่รับประกันว่าจะมีการชนกันของแฮชจำนวนมากซึ่งจะทำให้เวลาในการทำงานลดลงอย่างมาก
Sedgewick ต้องการติดตามต้นฉบับให้ใกล้กว่านั้นเล็กน้อยอย่างไรก็ตามโดยพื้นฐานแล้วจะประเมินพหุนามที่ค่าคงที่เป็น x (ตัวอักษร x ในเวอร์ชันดั้งเดิมที่ใช้วงแหวนพหุนาม) เขาต้องการไพรม์แบบสุ่มเพื่อให้ฝ่ายตรงข้ามที่หลงลืมไม่สามารถสร้างการชนกันได้ การกรองตัวเลขให้ใหญ่พอนั้นค่อนข้างไร้ประสิทธิภาพดังนั้นเขาจึงหันไปหา Prime Number Theorem (ซึ่งเป็นคณิตศาสตร์ที่อยู่เบื้องหลังคำใบ้ของเขา แต่มันมีเพียงแบบไม่มีอาการเท่านั้นซึ่งทำให้เกิดความยุ่งเหยิงในทางทฤษฎี) และการทดสอบแบบรวดเร็ว (ซึ่งอาจเป็นไปได้ กรณีที่ล้มเหลวจะไม่ส่งผลต่อความถูกต้องของอัลกอริทึมและหายากพอที่จะไม่ส่งผลต่อเวลาทำงานที่คาดไว้)
ฉันไม่แน่ใจว่าเขาพิสูจน์ความน่าจะเป็นของการชนกันอย่างเป็นทางการได้อย่างไร ความคิดคร่าวๆของฉันคือโดยทั่วไปแสดงให้เห็นว่ามีช่วงเวลาที่น่าสนใจเพียงพอในหน้าต่างที่น่าสนใจใช้ทฤษฎีบทเศษเหลือของจีนเพื่อแสดงให้เห็นว่าเป็นไปไม่ได้ที่จะมีการชนกันหลายช่วงเวลามากเกินไปในคราวเดียวสรุปได้ว่าความน่าจะเป็นของการชนนั้นถูกล้อมรอบด้วย ความน่าจะเป็นในการเลือกไพรม์ไม่ดีซึ่งมีค่าต่ำ แต่ Prime Number Theorem มีเพียงแบบไม่มีอาการดังนั้นเราจึงต้องอาศัยการทดลองทางคอมพิวเตอร์เกี่ยวกับความหนาแน่นของไพรม์ในช่วงคำของเครื่อง ไม่ค่อยดี.