อัลกอริทึมการจับคู่สตริงที่ไร้เดียงสาใน Python: ตัวอย่าง จุดเด่น & ข้อดี & ข้อเสีย

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

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

อัลกอริธึมการค้นหารูปแบบไร้เดียงสา

ในการค้นหารูปแบบสตริงที่ไร้เดียงสา โปรแกรมจะทดสอบตำแหน่งของรูปแบบอินพุต P [1……i] ในสตริงของอักขระ T [1…..m]

โปรดทราบว่าความยาวของข้อความหรือสตริงที่ป้อนจะมากกว่าหรือเท่ากับรูปแบบเสมอ

นี่คืออัลกอริธึมการค้นหารูปแบบที่ไร้เดียงสาสำหรับภาษาการเขียนโปรแกรมต่างๆ

เริ่ม

แพท = แพทเทิร์น Size

str = ขนาดสตริง

for i = 0 ถึง (str – pat), do

สำหรับ j = 0 เพื่อตบเบา ๆ ทำ

ถ้า text[i+j] ≠ pattern[j] แล้ว

หมดห่วง

เสร็จแล้ว

ถ้า j == ตบ แล้ว

แสดงตำแหน่งของ i ตามรูปแบบที่พบ

เสร็จแล้ว

จบ

อัลกอริธึมนี้ค่อนข้างมีความสำคัญในวิทยาการคอมพิวเตอร์ เนื่องจากช่วยให้ผลการค้นหาเป็นผลลัพธ์

อ่าน : ประเภทของอัลกอริทึม AI ที่คุณควรรู้

ตัวอย่างการจับคู่สตริงที่ไร้เดียงสาบน Python

นี่คือตัวอย่างที่ใช้วิธีการค้นหารูปแบบไร้เดียงสาในโค้ดของหลาม

# โปรแกรม Python สำหรับการจับคู่สตริงที่ไร้เดียงสา

# ค้นหาอัลกอริทึม

ค้นหา def (P, T):

X = เลน(P)

Y = เลน (T)

# วนซ้ำเพื่อเปลี่ยน P[] ทีละรายการ */

สำหรับ ฉัน อยู่ใน ช่วง (X – Y + 1):

เจ = 0

# สำหรับดัชนีปัจจุบัน i ตรวจสอบ

# สำหรับการจับคู่รูปแบบ */

สำหรับ j ใน ช่วง (0, X):

ถ้า (txt[i + j] ! = P[j]):

หยุดพัก

ถ้า (j == X – 1):

พิมพ์ (“รูปแบบที่พบที่ตำแหน่ง “, i)

# รหัสไดรเวอร์

ถ้า __name__ == '__main__':

T = “UPGRADEDUBUPGRAABUPGRADEDU”

P = “อัพเกรด”

ค้นหา (P, T)

เอาท์พุต :

รูปแบบพบที่ตำแหน่ง 0

รูปแบบพบที่ตำแหน่ง 17

คำอธิบาย: ตำแหน่งแรกคือตำแหน่ง ที่ 0 เนื่องจากรูปแบบ “UPGRAD” ถูกพบครั้งแรกที่นี่ ผลลัพธ์แสดงให้เห็นว่าพบรูปแบบที่ตำแหน่ง 0

ในทำนองเดียวกัน พบรูปแบบถัดไปที่ตำแหน่ง 17

กรณีที่ดีที่สุดของการค้นหารูปแบบไร้เดียงสา

มีกรณีที่ดีที่สุดเพียงกรณีเดียวสำหรับอัลกอริธึมการค้นหารูปแบบไร้เดียงสา ซึ่งแตกต่างจากกรณีที่เลวร้ายที่สุดสองกรณี

กรณีที่ดีที่สุดเกิดขึ้นเมื่ออักขระตัวแรกในข้อความรูปแบบไม่มีในสตริงอินพุต

ตัวอย่าง:

T [] = “อัพเกรดดูฮิจกลุปกรา”;

P [] = “ทูกรา”;

ดังนั้น จำนวนของรูปแบบการจับคู่คือ O(n)

กรณีที่เลวร้ายที่สุดของการค้นหารูปแบบไร้เดียงสา

มีสองกรณีที่เลวร้ายที่สุดในแนวทางการค้นหาสตริงที่ไร้เดียงสา

1. เมื่ออักขระทั้งหมดในรูปแบบเหมือนกับอักขระในสตริงอินพุต

T [] = “อีอีอีอีอีอีอีอีอีอีอีอีอีอีอีอีอีอีอีอีอีอีอี”;

P [] = “EEE”;

1. เมื่อเฉพาะอักขระตัวสุดท้ายในรูปแบบแตกต่างจากสตริงอินพุต

T [] = “อีอีอีอีอีอีอีอีอีอีอีอีด”;

P [] = “EEEED”;

ในกรณีเช่นนี้ จำนวนการเปรียบเทียบในหน่วย O(m*(n-m+1))

คุณสมบัติของอัลกอริทึมการจับคู่สตริงไร้เดียงสา

อัลกอริธึมการจับคู่สตริงมีไว้สำหรับการค้นหารูปแบบที่กำหนดทั้งหมดในข้อความ

นี่คือคุณสมบัติเด่นของอัลกอริทึม

1. เป็นวิธีที่ง่ายที่สุดในการค้นหารูปแบบในข้อความที่ป้อน จะตรวจสอบอักขระทั้งหมดทีละตัวในสตริงอักขระที่กำหนด
2. ค้นหาสตริงที่ตรงกัน – ไม่ว่าจะเป็นรูปแบบที่แน่นอนมากขึ้นหรือมากขึ้น
3. จะใช้มากขึ้นเมื่อมีข้อความขนาดเล็ก นอกจากนี้ยังไม่ต้องการขั้นตอนก่อนการประมวลผลใดๆ
4. วิธีค้นหานี้ไม่ใช้พื้นที่เพิ่มเติมในการทำงานและค้นหารูปแบบในสตริง

อ่านเพิ่มเติม: โครงสร้างข้อมูล & อัลกอริธึมใน Python

ข้อดีของการค้นหารูปแบบที่ไร้เดียงสา

1. ไม่มีขั้นตอนก่อนการประมวลผลที่จำเป็นในแนวทางการค้นหาที่ไร้เดียงสา เนื่องจากเวลาดำเนินการเท่ากับเวลาที่ตรงกัน
2. ไม่จำเป็นต้องใช้พื้นที่ปฏิบัติการเพิ่มเติม
3. การเปรียบเทียบรูปแบบกับสตริงสามารถทำได้ในลำดับใดก็ได้

ข้อเสียของการจับคู่สตริงที่ไร้เดียงสา

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

บทสรุป

อัลกอริธึมการจับคู่สตริงที่ไร้เดียงสาเป็นวิธีที่นิยมใช้มากที่สุดในการค้นหาตำแหน่งของรูปแบบดังกล่าวในข้อความที่กำหนด ด้วยเหตุผลหลายประการ เช่น ไม่ต้องการการประมวลผลล่วงหน้า ไม่มีพื้นที่เพิ่มเติมสำหรับการดำเนินการ ฯลฯ อย่างไรก็ตาม ไม่สามารถใช้กับข้อความที่ค่อนข้างใหญ่ได้เนื่องจาก ของความไร้ประสิทธิภาพในการดำเนินการขนาดใหญ่ได้รวดเร็วขึ้น

เราหวังว่าโพสต์นี้จะให้แนวคิดที่ดีแก่คุณเกี่ยวกับวิธีการค้นหารูปแบบไร้เดียงสาใน python หากต้องการเรียนรู้เกี่ยวกับการใช้แนวทางนี้และทำความเข้าใจหัวข้อนี้ให้กว้างขึ้น โปรดติดต่อผู้เชี่ยวชาญที่ upGrad เรามีหลักสูตรที่ออกแบบมาเป็นพิเศษสำหรับผู้ที่ต้องการเพิ่มทักษะ ติดต่อเราวันนี้!

หากคุณสนใจที่จะเรียนรู้เพิ่มเติมเกี่ยวกับ AI, แมชชีนเลิร์นนิง โปรดดูที่ IIIT-B & upGrad's PG Diploma in Machine Learning & AI ซึ่งออกแบบมาสำหรับมืออาชีพที่ทำงานและมีการฝึกอบรมที่เข้มงวดมากกว่า 450 ชั่วโมง กรณีศึกษาและการมอบหมายมากกว่า 30 รายการ สถานะศิษย์เก่า IIIT-B โครงการหลัก 5 โครงการและความช่วยเหลือด้านงานกับบริษัทชั้นนำ