เมื่อต้องการตัดคำขึ้นบรรทัดใหม่

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

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

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

ในโปรแกรมประมวลผลคำแบบกราฟิกร่วมสมัยMicrosoft WordและOpenOffice.orgคาดว่าผู้ใช้จะพิมพ์ carriage return ( ) ระหว่างแต่ละย่อหน้า การตั้งค่าการจัดรูปแบบเช่นการเยื้องบรรทัดแรกหรือระยะห่างระหว่างย่อหน้าจะมีผลโดยที่แคร่ตลับหมึกจะทำเครื่องหมายตัวแบ่ง ตัวแบ่งบรรทัดที่ไม่ใช่ย่อหน้าซึ่งเป็น soft return ถูกแทรกโดยใช้+ หรือผ่านเมนูและมีไว้สำหรับกรณีที่ข้อความควรขึ้นบรรทัดใหม่ แต่ไม่ต้องการผลข้างเคียงอื่น ๆ ของการเริ่มย่อหน้าใหม่ .↵ Enter⇧ Shift↵ Enter

ในภาษามาร์กอัปที่เน้นข้อความโดยทั่วไปแล้ว soft return จะถูกนำเสนอเป็นแท็กมาร์กอัป ตัวอย่างเช่นในHTMLมีแท็ก
ที่มีวัตถุประสงค์เดียวกันกับ soft return ในโปรแกรมประมวลผลคำที่อธิบายไว้ข้างต้น

Unicode

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

ชุดอักขระ Unicode มีอักขระตัวคั่นบรรทัดเช่นเดียวกับตัวคั่นย่อหน้าเพื่อแสดงความหมายของการคืนค่าแบบอ่อนและการคืนค่าแบบแข็ง

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

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

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

ในจีน , ญี่ปุ่นและเกาหลี , ตัดคำมักจะสามารถเกิดขึ้นก่อนและหลังการใด ๆของตัวละครฮันแต่ตัวอักษรวรรคตอนบางอย่างที่ไม่ได้รับอนุญาตที่จะเริ่มต้นบรรทัดใหม่ [2]ญี่ปุ่นKanaตัวอักษรของตัวอักษรภาษาญี่ปุ่นได้รับการปฏิบัติแบบเดียวกับตัวละครฮัน ( คันจิ ) โดยขยายคำความหมายสามารถและมีแนวโน้มที่จะถูกทำลายโดยไม่ต้องยัติภังค์ใด ๆ หรือข้อบ่งชี้อื่น ๆ ที่นี้ได้เกิดขึ้น

อย่างไรก็ตามในบางสถานการณ์ไม่ต้องการให้มีการตัดคำ ตัวอย่างเช่น

• อาจไม่ต้องการการตัดคำภายในชื่อบุคคลและ
• อาจไม่ต้องการการตัดคำภายในคำประสมใด ๆ (เมื่อข้อความถูกล้างออก แต่มีเฉพาะในบางรูปแบบเท่านั้น)

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

เครื่องหมายวรรคตอนCJKอาจเป็นไปตามหรือไม่ปฏิบัติตามกฎเกณฑ์ที่คล้ายคลึงกับสถานการณ์พิเศษดังกล่าวข้างต้น มันขึ้นอยู่กับกฎเส้นแบ่งใน CJK

อย่างไรก็ตามกรณีพิเศษของกฎการทำลายเส้นใน CJK จะใช้เสมอ: การตัดบรรทัดจะต้องไม่เกิดขึ้นภายในเส้นประ CJK และจุดไข่ปลา แม้ว่าแต่ละเครื่องหมายวรรคตอนเหล่านี้จะต้องแสดงด้วยอักขระสองตัวเนื่องจากข้อ จำกัด ของการเข้ารหัสอักขระที่มีอยู่ทั้งหมดแต่ละเครื่องหมายเหล่านี้เป็นเครื่องหมายวรรคตอนเดียวที่มีความกว้างสองemsไม่ใช่สองเครื่องหมายวรรคตอนกว้างหนึ่ง em

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

จำนวนบรรทัดขั้นต่ำ

วิธีง่ายๆในการตัดคำคือการใช้อัลกอริธึมโลภที่วางคำในบรรทัดให้ได้มากที่สุดจากนั้นไปยังบรรทัดถัดไปเพื่อทำแบบเดียวกันจนกว่าจะไม่มีคำเหลือให้วางอีก วิธีนี้จะใช้หลายโปรแกรมประมวลผลคำที่ทันสมัยเช่นOpenOffice.org Writerและ Microsoft Word [ ต้องการอ้างอิง ]อัลกอริทึมนี้ใช้จำนวนบรรทัดขั้นต่ำที่เป็นไปได้เสมอ แต่อาจนำไปสู่บรรทัดที่มีความยาวต่างกันมาก pseudocode ต่อไปนี้ใช้อัลกอริทึมนี้:

SpaceLeft: = LineWidthสำหรับแต่ละคำในข้อความ ถ้า (Width (Word) + SpaceWidth)> SpaceLeft แทรกตัวแบ่งบรรทัดก่อน Word ในข้อความ SpaceLeft: = LineWidth - ความกว้าง (Word) อื่น SpaceLeft: = SpaceLeft - (ความกว้าง (Word) + SpaceWidth)

ไหนLineWidthคือความกว้างของเส้นที่SpaceLeftเป็นความกว้างของพื้นที่ที่เหลืออยู่ในบรรทัดเพื่อเติมSpaceWidthคือความกว้างของตัวอักษรพื้นที่เดียวTextคือข้อความการป้อนข้อมูลเพื่อย้ำกว่าและWordเป็นคำที่อยู่ในข้อความนี้

ความหยาบขั้นต่ำ

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

สำหรับการป้อนข้อความ

AAA BB CC DDDDD

ด้วยความกว้างของบรรทัด 6 อัลกอริทึมโลภจะสร้าง:

------ ความกว้างของเส้น: 6AAA BB พื้นที่ที่เหลือ: 0CC พื้นที่ที่เหลือ: 4DDDDD พื้นที่ที่เหลือ: 1

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

------ ความกว้างของเส้น: 6AAA พื้นที่ที่เหลือ: 3BB CC พื้นที่ที่เหลือ: 1DDDDD พื้นที่ที่เหลือ: 1

ความแตกต่างที่นี่คือบรรทัดแรกหักก่อนBBแทนที่จะเป็นหลังทำให้ได้กำไรที่ดีกว่าและต้นทุนที่ต่ำกว่า 11

ด้วยการใช้อัลกอริธึมการเขียนโปรแกรมแบบไดนามิกเพื่อเลือกตำแหน่งที่จะทำลายเส้นแทนที่จะเลือกตัวแบ่งอย่างละโมบอาจพบวิธีแก้ปัญหาที่มีความหยาบน้อยที่สุดในเวลา, ที่ไหน คือจำนวนคำในข้อความที่ป้อน โดยปกติฟังก์ชันต้นทุนสำหรับเทคนิคนี้ควรได้รับการแก้ไขเพื่อไม่ให้นับช่องว่างที่เหลือในบรรทัดสุดท้ายของย่อหน้า การปรับเปลี่ยนนี้ช่วยให้ย่อหน้าจบลงตรงกลางบรรทัดโดยไม่มีการลงโทษ นอกจากนี้ยังสามารถใช้เทคนิคการเขียนโปรแกรมแบบไดนามิกเดียวกันเพื่อลดฟังก์ชันต้นทุนที่ซับซ้อนมากขึ้นซึ่งรวมปัจจัยอื่น ๆ เช่นจำนวนบรรทัดหรือต้นทุนสำหรับการยัติภังค์คำยาว [3]อัลกอริธึมเชิงเส้นเวลาที่เร็วขึ้น แต่ซับซ้อนขึ้นซึ่งขึ้นอยู่กับอัลกอริทึม SMAWKยังเป็นที่ทราบกันดีว่ามีปัญหาความหยาบขั้นต่ำและสำหรับฟังก์ชันต้นทุนอื่น ๆ ที่มีคุณสมบัติคล้ายคลึง [4] [5]

ประวัติศาสตร์

คุณลักษณะการแบ่งบรรทัดดั้งเดิมถูกนำมาใช้ในปี 1955 ใน "หน้าหน่วยควบคุมเครื่องพิมพ์" พัฒนาโดยWestern Union ระบบนี้ใช้รีเลย์มากกว่าคอมพิวเตอร์โปรแกรมดิจิตอลและดังนั้นจึงจำเป็นต้องมีขั้นตอนวิธีการง่ายๆที่สามารถดำเนินการได้โดยไม่ต้องบัฟเฟอร์ข้อมูล ในระบบเวสเทิร์นยูเนี่ยนแต่ละบรรทัดถูกหักที่อักขระช่องว่างตัวแรกที่จะปรากฏหลังอักขระที่ 58 หรือที่อักขระที่ 70 หากไม่พบอักขระเว้นวรรค [6]

อัลกอริทึมโลภสำหรับสายการทำลายถือกำเนิดวิธีการเขียนโปรแกรมแบบไดนามิกที่ระบุไว้โดยโดนัลด์ Knuthในที่ไม่ถูกเผยแพร่ 1977 บันทึกการอธิบายระบบของเขา typesetting เท็กซ์[7]และเผยแพร่ต่อไปในรายละเอียดมากขึ้นโดยนูและ Plass (1981)

• พื้นที่ไม่ทำลาย
• การจัดตำแหน่งตัวพิมพ์
• พื้นที่กว้างเป็นศูนย์
• ตัวแบ่งคำ
• ตัวเชื่อมคำ

• อัลกอริทึม Unicode Line Breaking

อัลกอริทึมของ Knuth

• "Knuth & Plass line-break Revisited"
• "tex_wrap": "ใช้อัลกอริทึมของ TeX ในการแบ่งย่อหน้าออกเป็นบรรทัด" ข้อมูลอ้างอิง: "Breaking Paragraphs into Lines", DE Knuth and MF Plass, Chapter 3 of _Digital Typography_, CSLI Lecture Notes # 78
• Text :: Reflow - โมดูล Perl สำหรับการรีเฟรชไฟล์ข้อความโดยใช้อัลกอริทึมการย่อหน้าของ Knuth "อัลกอริทึมการจัดเรียงใหม่พยายามทำให้บรรทัดมีความยาวเท่ากัน แต่ยังพยายามแบ่งวรรคตอนและหลีกเลี่ยงการใช้ชื่อที่ถูกต้องหรือตามหลังคำเชื่อมบางอย่าง (" a "," the "ฯลฯ ) ผลลัพธ์คือไฟล์ที่มี ขอบด้านขวา "ขาด ๆ หาย ๆ " มากกว่าที่เกิดจาก fmt หรือ Text :: Wrap แต่อ่านง่ายกว่าเนื่องจากมีการแบ่งวลีน้อยลงในการแบ่งบรรทัด "
• การปรับอัลกอริทึมนูมาทำความรู้จักกับ"ยัติภังค์อ่อน"
• อัลกอริธึมการทำลายของ Knuth "คำอธิบายโดยละเอียดของแบบจำลองและอัลกอริทึมมีอยู่ในกระดาษ" Breaking Paragraphs into Lines "โดย Donald E. Knuth ซึ่งตีพิมพ์ในหนังสือ" Digital Typography "(Stanford, California: Center for the Study of Language and Information, 2542), (เอกสารประกอบการบรรยาย CSLI, เลขที่ 78. ) "; ส่วนหนึ่งของGoogle Summer Of Code 2006
• "Bridging the Algorithm Gap: A Linear-time Functional Program for Paragraph Formatting"โดย Oege de Moor, Jeremy Gibbons, 1999

ลิงค์ตัดคำอื่น ๆ

• ปัญหาย้อนกลับ - การเลือกคอลัมน์ให้กว้างพอที่จะพอดีกับ (ห่อ) ข้อความ ( เวอร์ชันที่เก็บถาวร )
• KWordWrap Class Reference ที่ใช้ใน KDE GUI
• "Knuth linebreaking องค์ประกอบสำหรับการจัดรูปแบบออบเจ็กต์"โดย Simon Pepping 2006 ขยายโมเดล Knuth เพื่อรองรับการปรับปรุงเล็กน้อย
• "กลยุทธ์การทำลายหน้า"ขยายโมเดล Knuth เพื่อรองรับการปรับปรุงเล็กน้อย
• "อัลกอริทึมการแบ่งบรรทัดแบบ Knuth-Plass ... สิ่งที่น่าสนใจจริงๆคือการที่อัลกอริทึมของ Adobe แตกต่างจากอัลกอริทึม Knuth-Plass ต้องแตกต่างกันเนื่องจาก Adobe ได้จัดการจดสิทธิบัตรอัลกอริทึม (6,510,441)" [1]
• "Murray Sargent: คณิตศาสตร์ในที่ทำงาน"
• "การทำลายเส้น" จะเปรียบเทียบอัลกอริทึมของความซับซ้อนของเวลาต่างๆ