การใช้งาน Longest Common Subsequence (LCS) ในภาษา Ruby อย่างง่าย

การวิเคราะห์สตริง (String Analysis) เป็นอีกหนึ่งหัวข้อที่มีความสำคัญในวิทยาการคอมพิวเตอร์ โดยเฉพาะในการประมวลผลภาษาธรรมชาติ (Natural Language Processing) และการค้นหาข้อมูล (Data Retrieval) หนึ่งในปัญหาที่น่าสนใจคือ การหาความยาวของ "Longest Common Subsequence" (LCS) หรือวิธีการหาลำดับย่อยที่ยาวที่สุดที่เป็นไปได้จากสองลำดับ ณ ที่นี้ เราจะใช้ภาษา Ruby ในการแก้ปัญหานี้

ความหมายและแนวคิดเบื้องต้นของ LCS

คำว่า "Longest Common Subsequence" หมายถึง ลำดับที่ปรากฏในสองลำดับ แต่ไม่ได้เรียงตามลำดับเดิม ซึ่งหมายความว่าสามารถข้ามบางตัวอักษรในลำดับหรือการเพิ่มตัวอักษรใหม่เข้าไปได้

ตัวอย่างเช่น:

- สำหรับลำดับ 1: "ABCDGH"

- สำหรับลำดับ 2: "AEDFHR"

LCS ของสองลำดับนี้คือ "ADH" ซึ่งมีความยาว 3

การคำนวณ LCS ด้วยวิธี Dynamic Programming

Dynamic Programming เป็นเทคนิคที่ใช้ในการแก้ปัญหาที่มีลักษณะเป็นปัญหาย่อย (Subproblems) โดยการเก็บผลลัพธ์ไว้ในตารางเพื่อลดเวลาในการคำนวณใหม่ในครั้งถัดไป

ขั้นตอนการสร้างตาราง

1. สร้างตาราง 2 มิติ ขนาด `(m+1) x (n+1)` โดย `m` คือความยาวของลำดับแรก และ `n` คือความยาวของลำดับที่สอง

2. กำหนดค่าทุกตำแหน่งในตารางให้เป็น 0

3. ถ้าอักษรในสองลำดับตรงกัน ให้อัพเดทค่าที่ตำแหน่ง `(i, j)` เป็น `1 + table[i - 1][j - 1]`

4. ถ้าไม่ตรงกัน ให้อัพเดทค่าที่ตำแหน่ง `(i, j)` เป็น `max(table[i - 1][j], table[i][j - 1])`

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

 def lcs(x, y)
  m = x.length
  n = y.length

  # Step 1: Create a 2D array to store lengths of longest common subsequence.
  table = Array.new(m + 1) { Array.new(n + 1, 0) }

  # Step 2: Build the table in a bottom-up manner
  for i in 1..m
    for j in 1..n
      if x[i - 1] == y[j - 1] # Characters match
        table[i][j] = table[i - 1][j - 1] + 1
      else # Characters do not match
        table[i][j] = [table[i - 1][j], table[i][j - 1]].max
      end
    end
  end

  # Step 3: The length of the longest common subsequence
  return table[m][n]
end

# ตัวอย่างการใช้งาน
x = "ABCDGH"
y = "AEDFHR"
puts "Length of LCS is #{lcs(x, y)}"

การอธิบายโค้ด

- โค้ดเริ่มต้นด้วยการประกาศฟังก์ชัน `lcs` ที่รับสองสตริง `x` และ `y`

- สร้างตาราง `table` ขนาด `(m+1) x (n+1)` เพื่อเก็บค่า

- ใช้ลูปเพื่อเติมค่าลงในตาราง โดยเช็คความตรงกันของอักษรที่ตำแหน่ง `(i-1)` ใน `x` กับ `(j-1)` ใน `y`

- จบด้วยการส่งค่าความยาวของ LCS กลับ

Use Case ในโลกจริง

การหาความยาวของ LCS มีการใช้งานในหลากหลายด้าน เช่น:

เรียนรู้เพิ่มเติมที่ EPT

หากคุณสนใจในด้านการเขียนโปรแกรมและต้องการเรียนรู้เรื่องราวที่เราได้พูดถึงในวันนี้มากขึ้น เช่น Dynamic Programming หรือการประมวลผลข้อมูล เชิญเยี่ยมชม EPT หรือ Expert-Programming-Tutor สถาบันที่มุ่งสร้างโปรแกรมเมอร์ที่มีคุณภาพ เป็นศูนย์กลางในการเรียนรู้ เตรียมตัวพร้อมสู่ยุคเทคโนโลยี สร้างโอกาสให้กับตัวคุณเอง!

มาร่วมสนุกและเรียนรู้ในการเขียนโค้ดไปด้วยกันที่ EPT!

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