รู้จักกับ String Matching Algorithm ในภาษา Swift

 

ในโลกแห่งการเขียนโปรแกรม การจับคู่ string หรือที่เรียกว่า String Matching เป็นเรื่องที่สำคัญมาก โดยเฉพาะในงานที่เกี่ยวข้องกับการค้นหาข้อมูล เช่น การค้นหาข้อความในเอกสาร การค้นหาไฟล์ในคอมพิวเตอร์ หรือแม้กระทั่งการทำงานในฐานข้อมูล ในบทความนี้เราจะมาสำรวจว่า String Matching Algorithm คืออะไร วิธีการทำงาน รวมถึงตัวอย่าง code ใช้ภาษา Swift พร้อมวิเคราะห์ความซับซ้อนและข้อดีข้อเสียของ Algorithm นี้

 

String Matching Algorithm คืออะไร?

String Matching Algorithm คือชุดของวิธีการที่ช่วยให้เราสามารถค้นหา substring หรือข้อความย่อยใน string หลักได้อย่างมีประสิทธิภาพ ตัวอย่างเช่น หากเราต้องการหาคำว่า "programming" ในประโยค "Learning programming is fun" วิธีการที่เรานำมาใช้ในการค้นหาอาจมีความแตกต่างกันไปขึ้นอยู่กับอัลกอริธึมที่เลือก

ปัญหาที่ String Matching Algorithm แก้ไขได้

- ค้นหาข้อความ: ค้นหา substring ใน string ตัวใหญ่ - การจัดเรียงข้อมูล: ใช้ในการกรองข้อมูลตามคีย์เวิร์ด - การประมวลผลข้อมูล: การหาคำที่ซ้ำในข้อมูลขนาดใหญ่

ตัวอย่าง Algorithm: Knuth-Morris-Pratt (KMP)

หนึ่งใน Algorithm ที่นิยมใช้กันแพร่หลายในการจับคู่ string คือ Knuth-Morris-Pratt (KMP) โดยอัลกอริธึมนี้จะทำการปรับกระบวนการเมื่อพบการไม่ตรงกัน แทนที่จะเริ่มจากตำแหน่งแรกใหม่ อัลกอริธึมจะพรินซ์ข้อมูลที่ใช้ในการจัดการกับความไม่ตรงกัน

#### โค้ดตัวอย่าง KMP ในภาษา Swift

 func KMPsearch(pattern: String, text: String) {
    let m = pattern.count
    let n = text.count
    var lps = [Int](repeating: 0, count: m)
    var j = 0 // index for pattern
    computeLPSArray(pattern: pattern, lps: &lps)

    var i = 0 // index for text
    while i < n {
        if pattern[pattern.index(pattern.startIndex, offsetBy: j)] == text[text.index(text.startIndex, offsetBy: i)] {
            j += 1
            i += 1
        }

        if j == m {
            print("Found pattern at index \(i - j)")
            j = lps[j - 1]
        } else if i < n && pattern[pattern.index(pattern.startIndex, offsetBy: j)] != text[text.index(text.startIndex, offsetBy: i)] {
            if j != 0 {
                j = lps[j - 1]
            } else {
                i += 1
            }
        }
    }
}

func computeLPSArray(pattern: String, lps: inout [Int]) {
    let m = pattern.count
    var len = 0 // length of previous longest prefix suffix
    var i = 1
    lps[0] = 0

    while i < m {
        if pattern[pattern.index(pattern.startIndex, offsetBy: i)] == pattern[pattern.index(pattern.startIndex, offsetBy: len)] {
            len += 1
            lps[i] = len
            i += 1
        } else {
            if len != 0 {
                len = lps[len - 1]
            } else {
                lps[i] = 0
                i += 1
            }
        }
    }
}

// Usage
let text = "ababcabcabababd"
let pattern = "ababd"
KMPsearch(pattern: pattern, text: text)

การทำงานของ KMP Algorithm

1. การสร้าง LPS Array: ก่อนเริ่มการค้นหา KMP จะสร้าง LPS (Longest Prefix Suffix) array เพื่อช่วยในการค้นหาครั้งถัดไปโดยไม่ต้องเปรียบเทียบตั้งแต่ต้นใหม่ 2. การเปรียบเทียบ: KMP จะเริ่มการค้นหาจากขอบเขตของ pattern และ text หากไม่ตรงกันจะใช้ LPS เพื่อเลื่อนจุดเริ่มต้นไปที่ตำแหน่งที่สามารถทำการเปรียบเทียบได้ใหม่

Use Case ในโลกจริง

คุณสามารถใช้ KMP Algorithm ในหลายกรณีเมื่อพิจารณาถึงความต้องการในการค้นหาว่า:

- การค้นหาข้อความในหนังสือ: เมื่อมี e-book ขนาดใหญ่และคุณต้องการค้นหาคำสำคัญได้อย่างรวดเร็ว - การประมวลผลฐานข้อมูล: การตรวจสอบว่าบางไฟล์มีข้อความที่เราต้องการหรือไม่ - การทำ SEO: ตรวจสอบว่าคำหลักปรากฏอยู่ในเนื้อหาของเว็บไซต์อย่างไร

วิเคราะห์ Complexity

1. เวลา (Time Complexity): KMP Algorithm มีเวลา O(n + m) ซึ่ง n คือความยาวของ text และ m คือความยาวของ pattern ซึ่งดีกว่าหลายอัลกอริธึมอื่นในกรณีที่ worse-case 2. พื้นที่ (Space Complexity): O(m) เนื่องจากต้องใช้พื้นที่ในการเก็บ LPS array

ข้อดีและข้อเสียของ KMP Algorithm

#### ข้อดี

- ไม่มีการย้อนกลับ: KMP ไม่ต้องเริ่มต้นใหม่จากต้นสุดเมื่อพบความไม่ตรงกัน - ประสิทธิภาพสูง: เหมาะสมสำหรับการค้นหาข้อความที่ต้องการจากข้อมูลขนาดใหญ่

#### ข้อเสีย

- ซับซ้อนในการเข้าใจ: KMP มีความซับซ้อนในการเขียนและทำความเข้าใจเมื่อเปรียบเทียบกับอัลกอริธึมง่ายๆ - การใช้หน่วยความจำ: แม้ LPS array จะมีขนาดเล็ก แต่ก็ต้องใช้พื้นที่เพิ่มเติมในการเก็บ

 

สรุป

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

หากคุณต้องการเรียนรู้เพิ่มเติมเกี่ยวกับการเขียนโปรแกรม รวมไปถึงการเข้าใจในเชิงลึกเกี่ยวกับ Algorithms เอพีที (EPT) มีหลักสูตรการเรียนการสอนพร้อมสิ่งอำนวยความสะดวกสามารถช่วยพัฒนา สร้างทักษะ และความรู้ทางด้านนี้ได้! อย่าพลาดโอกาสที่จะเติบโตไปกับเรา!

 

 

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