ทำความรู้จักกับ String Matching Algorithm ในภาษา Haskell

 

ในยุคดิจิตอลปัจจุบัน การจัดการข้อมูลที่อยู่ในรูปแบบของตัวอักษร (String) เป็นสิ่งที่มีความสำคัญอย่างยิ่ง โดยเฉพาะในการค้นหาข้อมูลตามคำที่กำหนด ในบทความนี้ เราจะมาเจาะลึกเกี่ยวกับ String Matching Algorithm โดยใช้ภาษา Haskell บทความนี้จะไม่เพียงแค่สอนการเขียนโปรแกรม แต่ยังช่วยให้คุณเข้าใจแนวคิดของอัลกอริธึมในการค้นหาข้อมูล รวมถึงตัวอย่างการใช้งานจริงเพื่อให้คุณเห็นภาพชัดเจนยิ่งขึ้น

 

String Matching Algorithm คืออะไร?

String Matching Algorithm

เป็นชุดของขั้นตอนหรือวิธีการที่ใช้สำหรับการค้นหาตำแหน่งของ substring (สตริงย่อย) ใดๆ ภายใน string (สตริงหลัก) อัลกอริธึมนี้มีการใช้งานที่หลากหลาย เช่น การค้นหาข้อความในไฟล์ การสืบค้นในแฟ้มข้อมูล (Database) การค้นหาข้อความในเว็บเพจ ฯลฯ

 

ตัวอย่างของ การใช้งานในชีวิตจริง

- การค้นหาข้อความในเอกสาร: เมื่อเราค้นหาคำในเอกสาร PDF หรือ Word จะต้องมีการค้นหา substring ใน text ทั้งหมดของเอกสาร - การค้นหาในฐานข้อมูล: เช่น การค้นหาชื่อผู้ใช้หรืออีเมลในระบบการจัดการข้อมูล - การวิเคราะห์ข้อมูล: ในการวิเคราะห์ข้อมูลข้อความหรือโซเชียลมีเดีย เพื่อตรวจสอบความคิดเห็นหรือคำที่เป็นที่นิยม

 

สูตรและอัลกอริธึมในการทำ String Matching

อัลกอริธึมที่นิยมใช้สำหรับการ Matching สตริงมีหลากหลายประเภท เช่น:

1. Naive String Matching: อัลกอริธึมนี้จะเปรียบเทียบทุกตำแหน่งใน string ทีละตัว 2. KMP (Knuth-Morris-Pratt): อัลกอริธึมที่ปรับปรุงประสิทธิภาพโดยใช้การวิเคราะห์ลักษณะของ substring 3. Boyer-Moore: อัลกอริธึมที่ทำงานอย่างมีประสิทธิภาพสูง โดยตรวจสอบตัวอักษรจากขวาไปซ้าย

 

มาทำความเข้าใจอัลกอริธึม Naive String Matching กัน

อัลกอริธึม Naive String Matching เป็นวิธีการที่เรียบง่ายที่สุดในการทำ String Matching โดยการเปรียบเทียบ substring กับ string ใหญ่ทีละตัวอักษร มาลองดูตัวอย่างกันดีกว่า:

 naiveStringMatch :: String -> String -> [Int]
naiveStringMatch text pattern = [i | i <- [0..(length text - length pattern)], take (length pattern) (drop i text) == pattern]

ในโค้ดด้านบน ฟังก์ชัน `naiveStringMatch` รับสองพารามิเตอร์คือ `text` และ `pattern` โดยมันจะสร้างลิสต์ของตำแหน่งที่ substring (pattern) ปรากฏอยู่ใน string (text)

ตัวอย่างการเรียกใช้งาน:

 main :: IO ()
main = do
    let text = "this is a simple example"
    let pattern = "is"
    print (naiveStringMatch text pattern)

เมื่อเรียกใช้งานโค้ดข้างต้น จะได้ผลลัพธ์เป็นตำแหน่งที่ substring "is" ปรากฏอยู่ใน string "this is a simple example"

ความยุ่งเหยิง (Complexity)

- เวลาที่ใช้: O(n * m) โดยที่ n คือความยาวของ string และ m คือความยาวของ substring เนื่องจากต้องวนลูปผ่าน string ทั้งหมดในทุกๆ ตำแหน่งเพื่อเปรียบเทียบ - พื้นที่: O(1) ใช้พื้นที่คงที่ในการจัดเก็บข้อมูลเพิ่มเติม

ข้อดีและข้อเสียของ Naive String Matching Algorithm

#### ข้อดี:

- เข้าใจง่าย: เป็นตัวอย่างอัลกอริธึมที่เข้าใจได้ง่าย เหมาะสำหรับผู้เริ่มต้น - ไม่มีการตั้งค่าเพิ่มเติม: ใช้งานง่าย ไม่ต้องมีการประยุกต์ใช้เทคนิคที่ซับซ้อน

#### ข้อเสีย:

- ไม่เหมาะกับข้อมูลใหญ่: เนื่องจากความซับซ้อน O(n * m) จะทำให้ประสิทธิภาพช้าลงสำหรับข้อมูลขนาดใหญ่ - ไม่สามารถใช้ประโยชน์จากผลลัพธ์ก่อนหน้า: โค้ดนี้จะทำการเริ่มใหม่ทุกครั้งในการค้นหา

 

วิธีที่ดีกว่า: ใช้ KMP Algorithm

การเข้ามาของ KMP Algorithm ได้เพิ่มประสิทธิภาพในการค้นหาข้อมูลโดยใช้การเรียงลำดับของตัวอักษรใน substring และช่วยให้เราหลีกเลี่ยงการเปรียบเทียบที่ไม่จำเป็น

ตัวอย่างของ KMP Algorithm ใน Haskell:

 kmpAlgorithm :: String -> String -> [Int]
kmpAlgorithm text pattern = kmpSearch text (prefixTable pattern) 0 0
  where
    prefixTable p = -- สร้างตาราง prefix (ไม่แสดงในนี้)
    kmpSearch t p tIdx pIdx
      | tIdx + pIdx == length t = []
      | pIdx == length p = tIdx : kmpSearch t p (tIdx + pIdx) 0
      | tIdx < length t && (t !! (tIdx + pIdx)) == (p !! pIdx) = kmpSearch t p tIdx (pIdx + 1)
      | pIdx > 0 = kmpSearch t p tIdx (prefixTable p !! (pIdx - 1))
      | otherwise = kmpSearch t p (tIdx + 1) 0

การใช้งาน KMP

 main :: IO ()
main = do
    let text = "abcabcabcdabcde"
    let pattern = "abc"
    print (kmpAlgorithm text pattern)

สรุป

String Matching Algorithm เป็นเครื่องมือที่สำคัญในการจัดการข้อมูลในรูปแบบ string ในยุคดิจิตอล พวกเราได้เรียนรู้เกี่ยวกับ Naive String Matching Algorithm และ KMP Algorithm ที่สามารถปรับปรุงประสิทธิภาพได้อย่างมาก โค้ดตัวอย่างที่เรานำเสนอในภาษา Haskell จะช่วยให้คุณเข้าใจการทำงานของอัลกอริธึมเหล่านี้ได้ดีขึ้น

หากคุณต้องการเรียนรู้การเขียนโปรแกรมใน Python หรือ Haskell เพิ่มเติมเพื่อที่จะนำความรู้ที่ได้ไปใช้ในการพัฒนาโปรเจคจริงๆ เราขอเชิญคุณมาเรียนรู้ที่โรงเรียน EPT (Expert-Programming-Tutor) เพราะที่นี่เรามีหลักสูตรที่ครบครันและการสอนที่มีคุณภาพ พร้อมผู้สอนและแนวทางที่ประสบการณ์มากมายในวงการโปรแกรมมิ่ง!

 

 

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง