ทำความรู้จักกับ String Matching Algorithm ด้วยภาษา ABAP

 

 

บทนำ

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

 

String Matching Algorithm คืออะไร?

String Matching Algorithm คือ วิธีการที่ใช้ในการค้นหาและเปรียบเทียบสตริงหนึ่งกับอีกสตริงหนึ่ง ซึ่งสตริงที่เราต้องการค้นหามักจะถูกเรียกว่าสตริง "แพทเทิร์น" (Pattern) และสตริงที่เราต้องการค้นหาจะเรียกว่า "เท็กซ์" (Text) การทำงานของ algorithm นี้ทำให้เราสามารถหาแพทเทิร์นภายในเท็กซ์ได้อย่างมีประสิทธิภาพ

การใช้งาน

ตัวอย่างของการใช้งาน String Matching อยู่ในหลายด้าน ไม่ว่าจะเป็น:

1. การค้นหาในฐานข้อมูล

2. เว็บเซิร์ชเอนจิน

3. การตรวจจับการเปลี่ยนแปลงในไฟล์

4. การวิเคราะห์เนื้อหาในโซเชียลมีเดีย

 

Algorithm ที่นิยมใช้

มีหลายวิธีในการจับคู่สตริง แต่ที่นิยมมากที่สุดได้แก่:

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

ในวันนี้เราจะพูดถึง Naive Method และ KMP ในภาษา ABAP

 

ตัวอย่างโค้ด

Naive String Matching ใน ABAP

 DATA: lv_text TYPE string,
      lv_pattern TYPE string,
      lv_index TYPE i.

lv_text = 'Hello, welcome to the world of programming at EPT. Let\'s learn together!';
lv_pattern = 'programming'.

lv_index = 0.

WHILE lv_index < strlen( lv_text ) - strlen( lv_pattern ) + 1.
  IF lv_text+lv_index(len(lv_pattern)) = lv_pattern.
    WRITE: / 'Found pattern at index:', lv_index.
  ENDIF.
  lv_index = lv_index + 1.
ENDWHILE.

Knuth-Morris-Pratt (KMP) ใน ABAP

 CLASS lhc_kmp DEFINITION.
  PUBLIC SECTION.
    METHODS: search IMPORTING iv_text TYPE string
                        iv_pattern TYPE string
              RETURNING VALUE(rv_result) TYPE i.
ENDCLASS.

CLASS lhc_kmp IMPLEMENTATION.
  METHOD search.
    DATA: lv_pattern_array TYPE TABLE OF int,
          lv_index TYPE i,
          lv_m TYPE i.

    " Calculate LPS array
    CALL METHOD calculate_lps
      IMPORTING et_lps = lv_pattern_array
      iv_pattern = iv_pattern.

    DATA(lv_text_len) = strlen( iv_text ).
    DATA(lv_pattern_len) = strlen( iv_pattern ).

    lv_index = 0.
    lv_m = 0.

    WHILE lv_index < lv_text_len.
      IF iv_pattern+lv_m(1) = iv_text+lv_index(1).
        lv_index = lv_index + 1.
        lv_m = lv_m + 1.
      ENDIF.

      IF lv_m = lv_pattern_len.
        rv_result = lv_index - lv_m.
        RETURN.
      ELSEIF lv_index < lv_text_len AND iv_pattern+lv_m(1) <> iv_text+lv_index(1).
        IF lv_m <> 0.
          lv_m = lv_pattern_array[ lv_m - 1 ].
        ELSE.
          lv_index = lv_index + 1.
        ENDIF.
      ENDIF.
    ENDWHILE.
  ENDMETHOD.

  METHOD calculate_lps.
    " Implement LPS array calculation here
  ENDMETHOD.
ENDCLASS.

การวิเคราะห์ Complexity

1. Naive Method:

- Time Complexity: O(n*m) โดยที่ n คือความยาวของเท็กซ์ และ m คือความยาวของแพทเทิร์น เนื่องจากเราต้องเปรียบเทียบทุกตำแหน่งในเท็กซ์

- Space Complexity: O(1)

2. KMP:

- Time Complexity: O(n + m) ซึ่งเป็นผลมาจากการคำนวณ LPS และการค้นหาเอง

- Space Complexity: O(m) สำหรับ LPS array

ข้อดีข้อเสียของ Algorithm

#### Naive Method

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

#### KMP

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

 

Use Case ในโลกจริง

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

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

 

สรุป

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

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

 

 

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