เปรียบเทียบสตริงด้วย Rabin-Karp Algorithm

ไม่ว่าจะโจทย์เขียนโปรแกรม หรือเขียนโปรแกรมทั่วๆไป มันจะมีปัญหาลักษณะว่าให้เปรียบเทียบ สตริง 2 ตัว ไม่ว่าจะเป็นเปรียบเทียบสตริง(String) กันตรงเลยว่าเท่ากันไหม หรือถามว่าสตริง x เป็นสตริงย่อย(Sub-String) ของ สตริง y หรือเปล่า

โดยทั่วไปแล้วการหาสตริงย่อยมักจะเจอเยอะกว่า และมีอัลกอริทึมหลายตัวที่พยายามพัฒนาในจุดนี้เหมือนกัน ทำให้เกิดเป็นวิธีการหา pattern ต่างๆ ซึ่งโพสต์นี้เราจะมาดูอัลกอรึทึมคลาสสิกที่ชื่อ Rabin-Karp กัน

วิธี Brute Force ที่เรียนๆกัน

ก่อนอื่นเลยเรามาดูวิธีแรกๆที่เขา(ในที่นี้หมายถึง “ทุกที่” 🤣) มักจะสอนกันก่อนก็คือ ให้เปรียบเทียบสตริงเข้าไปตรงๆเลย

อย่างเช่น

ถ้าถามว่ามีคำว่า ayi ใน “They are playing in the park” ไหม เราก็เอาตัวอักษรแรกของ ayi (a) ไปไล่หาในสตริงที่ต้องการตรวจสอบ ซึ่งถ้าเราเจอว่าในนั้นมีตัว a อยู่ก็ถามต่อว่าถัดจากตัว a นั้นเป็น ตัว y รึป่าว ถ้ายังใช่อีกก็ถามต่อไปเรื่อยๆจนกว่าจะเจอครบคำว่า ayi

เปรียบเทียบโดยการมองหาตัวอักษร a ในสตริงหลัก เปรียบเทียบสตริงย่อย ayi โดยการมองหาตัวอักษร a ในสตริงหลัก

ในกรณีตัวอย่างหลังจากไล่หาตัว a เราก็ไปเจอที่ are แต่ตัวถัดไปจาก a มันไม่ใช่ y ที่เราต้องการหา ก็เลยยังต้องหาต่อไป จนไปเจอตัว a ที่ playing ก็เลยไล่ถามตัวถัดไปใหม่จนครบสตริง ayi

ฟังดูก็ make sense ดี แล้วก็เขียนไม่ยากด้วยใช่มะ?

ปัญหาของวิธี Brute Force

ทีนี้ลองมาดูอีกตัวอย่างนึง

ถ้าจะหาคำว่า add ใน adadadadadadadad

เทียบหาสตริงย่อย 'a''d'd' เทียบหาสตริงย่อย add โดยการมองหาตัวอักษร a ในสตริงหลัก

จะเห็นว่าเราต้องเปรียบเทียบตัวอักษรทุกตัวจนถึงตัวสุดท้ายในทุกๆครั้งที่เช็คคำว่า add เพราะตัว a ก็เยอะแถมยังต่อหลังด้วย d อีก

มันก็เริ่มจะฟังดูไม่ค่อยโอเคละ แล้วถ้าสตริงเป็นลักษณะคล้ายแบบนี้แต่ยาวขึ้นมากๆล่ะ?
ก็คงจะไม่ดีสักเท่าไหร่ถ้าจะเอาวิธีนี้ไปใช้ในอะไรที่ต้องการการประมวลผลที่เร็วมากๆ…

จริงๆ แล้วมันก็มีวิธีอื่นๆ ที่สามารถใช้หาสตริงย่อยนะ และมีประสิทธิภาพมากกว่าการไล่ดูทีละตัวตรงๆ ในทางทำโจทย์แข่ง จะมีที่นิยมใช้กันสองตัวคือ KMP และ Rabin-Karp เพราะเขียนไม่ยากมากและใช้เวลาในการทำงานน้อย

ในโพสต์นี้เราจะพูดถึงแต่ Rabin-Karp (เพราะมันเขียนง่ายกว่า KMP 🤣; เอาจริงๆไว้พูดทีหลังแหละ คอนเซปต์มันล้ำเกินไปยังหาวิธีทำบนเว็บดีๆไม่ได้)

Rabin-Karp Algorithm

Algorithm นี้จะอาศัยหลักการที่ชื่อว่า Rolling Hash มาเพื่อทำให้การเปรียบเทียบข้อมูลทำได้เร็วขึ้น เพราะถ้าสังเกตดูตอนเปรียบเทียบสตริงในวิธีก่อนหน้านี้ จะเทียบทีนึงก็ต้องค่อยๆเทียบทีละตัวอักษรซึ่ง ถ้าทำบ่อยๆก็จะช้า แต่ถ้าเปลี่ยนใหม่เป็นเทียบแค่ตัวเลขตัวเดียว มันก็ทำได้เร็วขึ้นเยอะเหมือนกัน

Rolling Hash

มันเป็นการแปลงสตริงให้กลายเป็นตัวเลขเพื่อที่จะได้เอาไปใช้เปรียบเทียบ โดยจะใช้หลักการของเลขฐานมาใช้คำนวณ คิดซะว่าทั้งสตริงคือเลขฐานที่ฐานมีค่าเยอะประมาณนึง เราจะเรียกเลขฐานนี้ว่า $p$ หรือก็คือ เราจะมองสตริงเป็นเลขฐาน $p$ นั่นแหละ

โดยวิธีที่เราจะทำคือสร้างฟังก์ชัน hash เพื่อแปลงตัวเลขฐาน $p$ ที่ว่านี้ ให้กลายเป็นเลขฐาน $10$ ที่เราคุ้นๆตานี่แหละเพื่อที่จะได้เปรียบเทียบได้ง่ายๆ

สมการแปลงเลขฐานก็ใช้แบบปกติได้เลย แค่ตำแหน่งอาจจะมีการเปลี่ยนแปลงบ้าง เพราะเราทำบนสตริง

\begin{aligned} H(s) & = s[0]*p^{n-1} + s[1]*p^{n-2} + s[2]*p^{n-3} + \dots + s[n-1] \\ &= \sum_{i=0}^{n-1} s[i]*p^{n-i-1} \end{aligned}

โดย $n$ แทนขนาดของสตริงที่เอามาใช้ hash และ $p$ แทนเลขที่เราเลือกเองได้

เลือกค่า p ยังไงดี?

มันก็ไม่ใช่ว่าเลือกค่า $p$ เป็นอะไรก็ได้หรอก อย่างน้อยๆค่า $p$ ควรจะต้องมากกว่าจำนวนตัวอักษรในสตริงที่เราเอามาทำ hashing เพราะไม่งั้นตัวเลขที่ได้จะเกิดการ collide ได้ง่ายขึ้นมากๆ

collide หมายถึงการที่มี input 2 ตัวที่ใส่เข้า hash ไปแล้วได้ output เดียวกัน ซึ่งมันจะทำให้โอกาสเกิดข้อผิดพลาดในการเปรียบเทียบเยอะขึ้น

ถ้าจะให้ดี $p$ เป็นจำนวนเฉพาะด้วยจะดีมาก

ตัวอย่าง:

H(``abc")= (1\times29^2)+(2\times29^1)+(3\times 29^0)

ในกรณีนี้เราจะแทนให้ตัวอักษร a = 1, b = 2ไปเรื่อยๆจนถึง z = 26 และค่า $p= 29$ เพราะเราต้องการค่า $p$ ที่มากกว่า 26 เพื่อให้มันมากกว่าจำนวนตัวอักษรที่มีในภาษาอังกฤษ และเป็นจำนวนเฉพาะ

ระวังอย่าให้ตัวเลขที่เราจะใช้แทนตัวอักษรซ้ำกัน

ถ้าเราจะให้ทั้ง a = 1 และ b = 1 ก็เหมือนกับมองว่า a และ b เป็นตัวอักษรเดียวกัน ซึ่งก็แปลว่า $H(aa) = H(ab) = H(bb) = H(ba)$ ซึ่งมันอาจจะมีประโยชน์ในบางกรณี แต่ส่วนใหญ่แล้วไม่ใช้กัน

วิธีที่ใช้แปลงตัวอักษรที่นิยมคือ เอาไปลบด้วยตัวอักษรที่มีค่า ASCII ต่ำสุด แล้วบวก 1 เพื่อที่จะได้ไม่ต้องมาเลือกตัวเลขเอง

1
char c = 'C';
2
int8_t number = c - 'A' + 1; // 67 - 65 + 1 = 3

สมมติถ้ามีตัวพิมพ์ใหญ่ด้วยก็จะมีตัวอักษรทั้งหมด $52$ ตัว เราก็ควรเลือกค่า $p$ เป็นจำนวนเฉพาะที่ใกล้เคียง ซึ่งจะใช้ $59$ หรือมากกว่าก็ได้

ทีนี้ลักษณะสำคัญของ rolling hash คือ ในกรณี input เปลี่ยนแค่นิดหน่อย มันไม่จำเป็นต้องคำนวณ hash ใหม่ทั้งหมดเหมือน hash ทั่วไป

อย่างตอนแรกที่เราคำนวณ hash ของ abc ไว้แล้ว ถ้าเราอยากจะหาว่า hash ที่แทน abcd คืออะไร ก็สามารถคำนวณโดยเพิ่ม d เข้าไปเลยก็ได้

จาก abc:

H(``abc")= (1\times29^2)+(2\times29^1)+(3\times 29^0)

ไปเป็น abcd:

\begin{aligned} H(``abcd") & = (1\times29^3)+(2\times29^2)+(3\times 29^1) + (4 \times 29^0) \\ & = ((1\times29^2)+(2\times29^1)+(3\times 29^0)) \times 29 + H(``d") \\ & = H(``abc") \times 29 + H(``d")\\ \end{aligned}

จะเห็นว่า hash ที่เปลี่ยนหลังจากเพิ่มตัวอักษรท้ายสตริง มีค่าเท่ากับค่า hash ก่อนเพิ่มคูณด้วย $p$ แล้วค่อยบวกค่า hash ของตัวอักษรตัวใหม่ หรือเขียนได้เป็น

H(s + c) = H(s) * p + H(c)

เมื่อ $s$ แทนสตริงขนาดเท่าไหร่ก็ได้ และ $c$ แทนตัวอักษรตัวเดียวที่เพิ่มเข้ามาใหม

อีก operation นึงที่ทำได้คือการเอาตัวอักษรออกจาก hash

ถ้าอยากจะเอาตัวอักษรหน้าออกก็ทำได้โดยการลบออกธรรมดาๆ เลยนี่แหละ

\begin{aligned} H(``bcd") & = (2\times29^2)+(3\times 29^1) + (4 \times 29^0) \\ & = (1\times29^3)+(2\times29^2)+(3\times 29^1) + (4 \times 29^0) - (1 \times 29^3)\\ & = H(``abcd") - H(``a") \times 29^3\\ & = H(``abcd") - H(``a") \times 29^{len(``bcd")} \end{aligned}

แล้วพอเราสามารถคำนวณเลข hash จากการเพิ่ม/ลด ขนาดของสตริงได้ ปัญหาก็ก็เหลือแค่คำนวณค่า hash ของแต่ละบล๊อกของสตริงหลักก็พอ

คำนวณ hash ของแต่ละบล๊อก

ซึ่งการคำนวณ hash ของแต่ละบล๊อกก็ไม่ได้ต้องคำนวณใหม่ตั้งแต่เริ่ม (เพราะไม่งั้นก็ไม่ได้เร็วกว่าวิธีเดิมอ่ะนะ) เพราะเราสามารถแก้ค่า hash ที่เราคำนวณมาก่อนหน้าให้กลายเป็นค่าถัดไปได้ โดยการเอาตัวหน้าออกแล้วเพิ่มตัวหลัง
อย่างในตัวอย่างคือเอาตัว a ออกจากด้านหน้า และเพิ่ม d เข้าไปด้านหลังสตริง

ซึ่งก็ทำได้ไม่ยากและให้โปรแกรมคำนวณส่วนนี้ก็เร็วกว่าให้มันเทียบทั้งสตริงเยอะ

แต่บางทีเลขมันก็เยอะมากจนมัน overflow ได้ถึงแม้จะใช้ long long(เลข 64 bits) ก็ตาม เขาก็เลยจะใช้จำนวนเฉพาะที่ใหญ่มากตัวนึง (นิยมใช้ 1e9 + 7) มา mod เพื่อทำให้เลขมันไม่ทะลุไปเยอะเกิน

การเขียน Rabin-Karp

เล่ามาตั้งนานกว่าจะได้เข้าเรื่อง Rabin-Karp…

Rabin-Karp เนี่ย concept คือ Rolling Hash เลย ก็คือไล่เช็กค่า hash ที่ได้ของแต่ละบล๊อก เพิ่มเติมคือเอาไปเทียบกับสตริงที่ต้องการจะหาด้วย

คำนวณ hash ของแต่ละบล๊อกเหมือนเดิม

ก็คือเก็บค่า hash ของสตริงที่จะหา อย่างเช่น add ก็คำนวณ $H(``add")$ เก็บไว้ แล้วไปไล่เทียบทีละบล๊อกของสตริงหลักเลย และมันก็เป็นไปได้แค่ 2 แบบ

ถ้าได้ค่า hash ไม่ตรงกัน ก็ไม่ใช่แน่ๆ และเลื่อนตำแหน่งที่หาไป 1 ตำแหน่งเพื่อหาต่อ
ถ้าค่า hash ตรงกันก็อาจจะเป็นสตริงย่อยก็ได้

ทีนี้ถึงเราได้ hash ตรงก็ไม่ได้แปลว่าจะเป็นสตริงย่อยเสมอไป

มันมีโอกาสที่เกิด collision หรือเลข hash ซ้ำกันได้อยู่ (แค่น้อยมากๆ) แต่ถ้าต้องการความถูกต้อง ก็สามารถ loop เพื่อเช็กตรงๆที่ตำแหน่งนั้นอีกทีก็ได้

หรือจะใช้อีกวิธีคือสร้าง modulo มาอีกชุดนึง เพื่อให้มีค่า hash เพิ่มอีกหนึ่งชุด จะได้ลดโอกาสการ collide โดยปกติแล้วใช้ modulo สัก 2-3 ตัวโอกาสก็น้อยมากพอแล้ว

Time Complexity

เราจะได้ว่า Rabin-Karp มี time complexity อยู่ที่ $O(n + m)$ โดยที่ $n$ คือ ขนาดของสตริงหลัก และ $m$ คือ ขนาดของสตริงที่ต้องการหา เพราะว่าตอนเราคำนวณ hash แต่ละบล๊อกของสตริงหลัก จะใช้เวลา $O(n)$ และ hash ของสตริงที่ต้องการหาก็ใช้เวลา $O(m)$

พอตอนจะมาเทียบก็เหมือนมองหาตัวเลขนึงใน array ธรรมดาซึ่งใช้เวลา $O(n)$ รวมกันก็เลยเป็น $O(n + m)$

ซึ่งเร็วกว่าวิธี Brute Force ที่ต้องเทียบทีละตัวอักษรที่ใช้เวลา $O(n \times m)$ อยู่

แชร์หน่อยก๊าบ ⊹

คัดลอกแล้ว!