เครื่องมือสำหรับนักพัฒนา · การเปรียบเทียบข้อความ
ความแตกต่างของข้อความค้นหาบรรทัดที่เปลี่ยนแปลงอย่างไร: LCS และอัลกอริทึมของ Myers
· มันทำงานอย่างไร
ข้อความที่แตกต่าง อัลกอริธึม นักพัฒนาเวิร์กโฟลว์
อธิบายแนวคิดลำดับต่อมาที่ยาวที่สุดเบื้องหลังการเปรียบเทียบแบบใช้เส้น และเหตุใดอัลกอริทึมของ Myers จึงทำให้มันเร็วพอที่จะรันได้ทันที แม้แต่ในแท็บเบราว์เซอร์
สองไฟล์ หนึ่งคำถาม: บรรทัดไหนรอด? - การเปรียบเทียบเฟรมเป็นการค้นหาเส้นที่ยาวที่สุดที่ใช้กันในทั้งสองเวอร์ชันแทนที่จะจับคู่หมายเลขบรรทัด
ไม่มีการแก้ไขสองครั้งโดยมีป้ายกำกับระบุว่าบรรทัดใดรอด ขั้นแรก ToolAcre แยกแต่ละข้อความออกเป็นรายการเรียงลำดับ จากนั้นค้นหาลำดับย่อยแบบยาวที่ปรากฏในทั้งสองรายการในลำดับเดียวกัน เส้นที่อยู่ด้านนอกสันที่ใช้ร่วมกันนั้นจะกลายเป็นการเพิ่มเติมหรือการลบออก แทนที่จะคาดเดาการปรับเปลี่ยน
ผลลัพธ์จะมีตำแหน่งอิงเดียวดั้งเดิมสำหรับทั้งสองฝ่าย แถวที่ไม่เปลี่ยนแปลงจะมีตัวเลขอยู่แต่ละด้าน การลบออกทางด้านซ้ายเท่านั้น และการเพิ่มทางด้านขวาเท่านั้น การบัญชีนั้นทำให้เรื่องราวที่แสดงสามารถตรวจสอบได้แม้ว่าบรรทัดที่ซ้ำกันจะทำให้มีการจัดแนวที่เป็นไปได้มากกว่าหนึ่งรายการ
เหตุใด diff จึงทำงานบนบรรทัด ไม่ใช่อักขระ - การแยกบรรทัดใหม่เปลี่ยนข้อความให้เป็นลำดับของหน่วยที่เทียบเคียงได้อย่างไร และเหตุใดจึงทำให้ร้อยแก้วมีพฤติกรรมแตกต่างจากโค้ด
การใช้งานถือว่าบรรทัดที่สมบูรณ์เป็นหน่วยการเปรียบเทียบ ขอบเขตการขึ้นบรรทัดใหม่จะกำหนดผลลัพธ์: การแก้ไขด้วยคำเดียวในย่อหน้าที่เก็บไว้ในบรรทัดเดียวจะแทนที่ทั้งบรรทัด ในขณะที่ร้อยแก้วเดียวกันที่จัดเรียงประโยคต่อประโยคสามารถแยกขอบเขตที่เล็กกว่ามากได้
การเปรียบเทียบเส้นไม่ใช่การวิเคราะห์อักขระที่ซ่อนอยู่หลังจอแสดงผลอื่น `splitLines` สร้างอาร์เรย์ และตาราง LCS จะเปรียบเทียบคีย์บรรทัดหนึ่งกับอีกบรรทัดหนึ่ง รายละเอียดที่คาดการณ์ได้นี้เหมาะสมกับไฟล์ต้นฉบับและไฟล์การกำหนดค่า แต่ไม่สามารถเน้นตัวอักษรที่เปลี่ยนไปในการแทนที่ที่ดูตรงกันได้
ลำดับย่อยทั่วไปที่ยาวที่สุดในรูปแบบธรรมดา — อธิบายแนวคิด LCS ในตัวอย่างห้าบรรทัด และแสดงให้เห็นว่าทุกสิ่งที่อยู่นอกลำดับย่อยกลายเป็นการแทรกหรือการลบได้อย่างไร
ลองนึกภาพเส้นซ้าย A, B, C, D, E และเส้นขวา A, C, E. A, C และ E รวมกันเป็นลำดับย่อยร่วมที่ได้รับคำสั่ง B และ D อยู่ข้างนอก ดังนั้นผลลัพธ์จะรายงานการลบสองครั้งและแถวที่ไม่เปลี่ยนแปลงสามแถวโดยไม่จำเป็นต้องจับคู่บรรทัดที่ถูกลบอย่างใดอย่างหนึ่งกับการแทนที่
ตารางจะบันทึกความยาวร่วมที่ดีที่สุดสำหรับคู่ตำแหน่งที่เหลือทุกคู่ การฟื้นฟูจะดำเนินไปตามคุณค่าเหล่านั้น ปุ่มที่เท่ากันจะเลื่อนไปข้างหน้าทั้งสองด้าน มิฉะนั้นค่าใกล้เคียงที่ใหญ่กว่าจะตัดสินใจว่าจะปล่อยการลบออกทางซ้ายหรือการเพิ่มทางขวา
อัลกอริธึมของ Myers และเหตุใดความเร็วจึงมีความสำคัญ — อธิบายโดยไม่ต้องใช้สูตรว่าการติดตามสคริปต์แก้ไขที่สั้นที่สุดช่วยให้การเปรียบเทียบรวดเร็วในไฟล์ที่มีบรรทัดหลายพันบรรทัดได้อย่างไร
สมุดงานชื่อ Myers แต่ `diff.js` ใช้การเขียนโปรแกรมไดนามิกลำดับที่ยาวที่สุดทั่วไปแบบธรรมดาอย่างชัดเจน ความคิดเห็นระบุเวลา O(n·m) และหน่วยความจำสำหรับจุดศูนย์กลางที่ต่างกัน การอ้างสิทธิ์ของ Myers หรือพฤติกรรมการแก้ไขกราฟที่สั้นที่สุดจะแทนที่อัลกอริธึมที่คุ้นเคยสำหรับโค้ดที่จัดส่งจริง
ToolAcre จำกัดต้นทุนก่อนการจัดสรร คำนำหน้าและคำต่อท้ายที่เท่ากันจะถูกลอกออกในการส่งผ่านเชิงเส้น และค่ากลางที่ต่างกันอาจมีบรรทัด 2,000 ได้สูงสุด เมทริกซ์คือ `Uint32Array`; ตารางที่อนุญาตที่เลวร้ายที่สุดที่บันทึกไว้นั้นกินพื้นที่ประมาณสิบหกเมกะไบต์ แทนที่จะเป็นค่าในกล่องที่ไม่มีขอบเขต
ToolAcre ใช้ตาราง LCS ไม่ใช่อัลกอริทึม Myers ที่มีชื่ออยู่ในโครงร่าง
เปรียบเทียบบันทึกการเปลี่ยนแปลงที่มี "การค้นหาที่เพิ่ม" "การส่งออกแบบคงที่" และ "ความช่วยเหลือที่อัปเดต" กับการแก้ไขที่เก็บรายการแรกและรายการที่สาม แต่แทรก "ตัวกรองที่เพิ่ม" ก่อนรายการสุดท้าย รายการทั่วไปจะยึดเส้นทาง "การส่งออกแบบคงที่" จะถูกลบออก และเพิ่ม "ตัวกรองที่เพิ่ม"
อัลกอริทึมไม่เรียกคู่นั้นว่าเป็นบรรทัดที่แก้ไข คำศัพท์แถวมีค่าเท่ากันเท่านั้น เพิ่มและลบ ดังนั้นการแทนที่ข้อความจะปรากฏเป็นการลบหนึ่งครั้งตามด้วยการบวกหนึ่งครั้ง สรุปจะนับการดำเนินการเหล่านั้นแยกจากกัน และทำเครื่องหมายข้อความว่าเหมือนกันเมื่อการนับทั้งสองเป็นศูนย์เท่านั้น
เหตุใดความแตกต่างที่ถูกต้องสองรายการจึงดูแตกต่างกัน - แสดงให้เห็นว่าความสัมพันธ์ระหว่างสคริปต์แก้ไขที่สั้นเท่ากันอธิบายได้อย่างไรว่าทำไมเครื่องมือหนึ่งตำหนิบรรทัดว่างและอีกอันตำหนิวงเล็บปิด
เส้นที่ซ้ำหรือเปลี่ยนกันได้สามารถสร้างลำดับย่อยทั่วไปหลายลำดับที่มีความยาวเท่ากันได้ ToolAcre แก้ไขหนึ่งเน็คไทโดยเลือกที่จะลบออกเมื่อค่าตารางที่อยู่ติดกันสองค่าเท่ากัน การใช้งานที่ถูกต้องอื่นอาจเลือกส่วนเพิ่มเติมก่อนและนำเสนอการจัดตำแหน่งที่ดูแตกต่างออกไปโดยมีค่าใช้จ่ายในการแก้ไขเท่ากัน
นั่นคือสาเหตุที่บรรทัดว่างหรือวงเล็บปีกกาปิดปรากฏติดอยู่กับส่วนอื่นๆ ของเครื่องมือต่างๆ ความคลาดเคลื่อนไม่ได้หมายถึงการเปรียบเทียบเนื้อหาที่สูญหายโดยอัตโนมัติ อ่านหมายเลขบรรทัดเดิมและแถวที่ไม่มีการเปลี่ยนแปลงก่อนที่จะถือว่าความแตกต่างในการนำเสนอเป็นการกล่าวอ้างข้อเท็จจริงที่แข่งขันกัน
สิ่งนี้ไม่ครอบคลุมถึง - การเปรียบเทียบความหมายหรือโครงสร้าง การตรวจจับการเคลื่อนไหว และการเน้นระดับคำอยู่นอกเหนือการคำนวณแบบต่างแบบเส้น
ไม่มีสิ่งใดในเส้นทางนี้แยกวิเคราะห์แผนผังไวยากรณ์ จดจำตัวระบุที่ถูกเปลี่ยนชื่อ ป้ายกำกับย้ายบล็อก หรือเข้าใจความหมายร้อยแก้ว ย่อหน้าที่ถูกย้ายละเมิดข้อกำหนดในลำดับที่ใช้ร่วมกัน และสามารถปรากฏได้หนึ่งครั้งเมื่อถูกลบ และอีกครั้งเมื่อถูกเพิ่ม เครื่องมือนี้ยังไม่ได้คำนวณการไฮไลต์ระดับอักขระหรือคำภายในแถว
การละเว้นเหล่านั้นเป็นขอบเขต ไม่ใช่โหมดที่ซ่อนอยู่ ใช้ผู้ตรวจสอบที่เข้าใจภาษาสำหรับการอ้างสิทธิ์เชิงความหมายและการควบคุมเวอร์ชันสำหรับประวัติการผสาน Text diff ตอบคำถามแคบกว่าว่าลำดับบรรทัดที่เรียงลำดับสองรายการแตกต่างกันอย่างไร จากนั้นให้มนุษย์ตีความว่าการแก้ไขข้อความเหล่านั้นมีความสำคัญหรือไม่
ประเด็นสำคัญ: ความหมายของบรรทัดที่ไฮไลต์จริงๆ — สรุปวิธีการอ่านความแตกต่างของบรรทัดว่าเป็นเรื่องราวที่สั้นที่สุดของการแก้ไข และวิธีที่การเปรียบเทียบข้อความของ ToolAcre เรียกใช้สิ่งนี้ในแท็บของคุณโดยไม่ต้องอัปโหลดอะไรเลย
อ่านแถวสีเขียวและสีแดงเป็นคำอธิบายเดียวที่ได้รับจาก LCS ไม่ใช่เพื่อพิสูจน์เจตนาของผู้เขียน การตัดแต่งคำนำหน้าและส่วนต่อท้ายจะเปลี่ยนปริมาณงาน แต่ไม่ใช่การบัญชีบรรทัดสุดท้าย ข้อความต้นฉบับจะยังคงอยู่ในทุกแถว แม้ว่าตัวเลือกตัวพิมพ์หรือช่องว่างจะมีคีย์ที่หลวมกว่าสำหรับการจับคู่ก็ตาม
การเปรียบเทียบดำเนินการผ่านโมดูลเบราว์เซอร์ที่นำเข้าและแสดงผลด้วยโหนดข้อความ DOM ไม่มีจุดสิ้นสุดการแปลงในเส้นทางเครื่องมือ ลองตัวอย่างห้าบรรทัด สลับด้านข้าง และดาวน์โหลดเอาต์พุตรูปแพตช์เพื่อดูว่าทิศทางเปลี่ยนการเพิ่มเติมเป็นการลบออกอย่างไรโดยไม่ต้องประดิษฐ์ความหมาย