การใช้งาน Longest common subsequent ในภาษา Lua แบบง่ายๆ พร้อมตัวอย่าง

# การใช้งาน Longest Common Subsequence (LCS) ในภาษา Lua พร้อมตัวอย่างในโลกจริง

บทนำ

ในโลกของการเขียนโปรแกรม เทคนิคต่างๆมีความสำคัญอย่างมาก หนึ่งในเทคนิคที่มีประโยชน์และน่าสนใจคืออัลกอริทึม "Longest Common Subsequence" (LCS) ซึ่งเป็นวิธีการหาลำดับย่อยร่วมที่ยาวที่สุดระหว่างสองสายอักขระ ตัวอย่างเช่น ถ้าเรามีสายอักขระ "ABCBDAB" และ "BDCAB" นั้น LCS ของสองสายนี้อาจจะเป็น "BCAB" หรือ "BDAB"

ยกตัวอย่าง usecase ในโลกจริงของ LCS เช่น การเปรียบเทียบดีเอ็นเอในงานชีววิทยาคำนวณ การหาความคล้ายคลึงของข้อความในงานด้านเอกสาร รวมถึงการใช้ในระบบควบคุมเวอร์ชันของโค้ดในการพัฒนาซอฟต์แวร์

ในบทความนี้ เราจะมาดูการใช้งาน LCS ในภาษา Lua แบบง่ายๆ พร้อมกับตัวอย่าง code ที่ใช้ในการคำนวณและอธิบายการทำงานของมัน

ตัวอย่างโค้ดภาษา Lua สำหรับ LCS

ก่อนที่จะไปถึงการเขียนโค้ด ขอให้เราทำความเข้าใจเกี่ยวกับหลักการของ LCS อัลกอริทึมดังกล่าวใช้เทคนิคของ Dynamic Programming โดยสร้างตารางเพื่อเก็บความยาวของ LCS ในทุกๆ subsequence

ตัวอย่างโค้ดที่ 1: LCS พื้นฐาน

 function LCS(X, Y)
    local m = #X
    local n = #Y
    local L = {}

    for i = 0, m do
        L[i] = {}
        for j = 0, n do
            L[i][j] = 0
        end
    end

    for i = 1, m do
        for j = 1, n do
            if X:sub(i, i) == Y:sub(j, j) then
                L[i][j] = L[i-1][j-1] + 1
            else
                L[i][j] = math.max(L[i-1][j], L[i][j-1])
            end
        end
    end

    return L[m][n]
end

local str1 = "ABCBDAB"
local str2 = "BDCAB"
print("LCS length: ", LCS(str1, str2))

ในตัวอย่างโค้ดนี้ เราได้สร้างฟังก์ชั่น `LCS` ที่มีพารามิเตอร์เป็นสายอักขระ X และ Y ภายในฟังก์ชั่น เริ่มด้วยการสร้างตาราง L ที่มีขนาด (m+1) x (n+1) โดยที่ m และ n คือความยาวของ X และ Y ตามลำดับ การวนลูปทำการประมวลผลและในที่สุดเราจะได้คำตอบที่ตำแหน่ง L[m][n] ซึ่งก็คือความยาวของ LCS

ความสำเร็จของโค้ดนี้มาจากความก้าวหน้าทีละขั้นตอน (Dynamic Programming) ที่เราพิจารณากรณีฐานและกรณีการเพิ่มสายอักขระทีละตัว ในทางปฏิบัติ เทคนิคนี้สามารถประยุกต์ไปใช้กับการจัดการกับข้อมูลประเภทต่างๆ เช่น ข้อมูลเชิงพันธุกรรม หรือการจับคู่ข้อความ (text matching) ในงานด้านวิทยาศาสตร์

ตัวอย่างโค้ดที่ 2: การันตรีการหา LCS แบบไม่ซ้ำกัน

อย่างไรก็ตาม ในบางครั้งอาจมีหลาย LCS ที่ยาวที่สุด ถ้าเราอยากได้ตัวอย่างเดียวที่ไม่ซ้ำกัน เราอาจต้องทำการปรับแต่งเพิ่มเติมลงในโค้ดของเรา

 -- สมมุติฟังก์ชัน Traceback ที่จะช่วยในการสร้าง LCS โดยใช้ตาราง L จากข้างต้น
function Traceback(L, X, Y, i, j)
    if i == 0 or j == 0 then
        return ""
    elseif X:sub(i, i) == Y:sub(j, j) then
        return Traceback(L, X, Y, i-1, j-1) .. X:sub(i, i)
    elseif L[i-1][j] > L[i][j-1] then
        return Traceback(L, X, Y, i-1, j)
    else
        return Traceback(L, X, Y, i, j-1)
    end
end

-- การใช้งาน Traceback พร้อมฟังก์ชัน LCS เดิม...
local str1 = "ABCBDAB"
local str2 = "BDCAB"
local L = LCS(str1, str2) -- ต้องเก็บค่าตาราง L จากโค้ด LCS ก่อนหน้านี้
print("One of the LCS: ", Traceback(L, str1, str2, #str1, #str2))

ในโค้ดนี้ เรามีฟังก์ชั่น `Traceback` ที่สร้างสายอักขระ LCS จากตารางที่ได้จาก LCS ฟังก์ชั่นนี้จะเดินย้อนกลับตามตาราง L เพื่อสร้างลำดับย่อยที่ต้องการได้

ตัวอย่างโค้ดที่ 3: LCS กับภาษา Lua แบบเรียกซ้ำ

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

 -- เราสมมุติว่ามีฟังก์ชั่น LCS ที่ได้สร้างไว้ด้วยเทคนิค Dynamic Programming เหมือนโค้ดที่ 1

function RecursiveLCS(X, Y, m, n, L)
    if m == 0 or n == 0 then
        return 0
    elseif L[m][n] ~= nil then
        return L[m][n]
    elseif X:sub(m, m) == Y:sub(n, n) then
        L[m][n] = RecursiveLCS(X, Y, m-1, n-1, L) + 1
        return L[m][n]
    else
        L[m][n] = math.max(RecursiveLCS(X, Y, m-1, n, L), RecursiveLCS(X, Y, m, n-1, L))
        return L[m][n]
    end
end

local str1 = "ABCBDAB"
local str2 = "BDCAB"
local L = {}
print("LCS length: ", RecursiveLCS(str1, str2, #str1, #str2, L))

จากตัวอย่างโค้ดที่สามนี้ เราสามารถเห็นถึงการนำ Dynamic Programming มาใช้กับการเรียกซ้ำได้อย่างเหมาะสม โดยการจดจำค่าที่ได้คำนวณแล้วเพื่อไม่ต้องคำนวณซ้ำอีก (Memoization)

การนำ LCS ไปใช้ในโลกจริง

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

ส่งท้าย

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

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

สนใจเรียนรู้เพิ่มเติม? ติดต่อเราได้ที่ Expert-Programming-Tutor ที่เราพร้อมให้คำแนะนำและบ่มเพาะเส้นทางการเป็นโปรแกรมเมอร์ให้ก้าวหน้ากับคุณ!

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