สตริง (วิทยาการคอมพิวเตอร์)

จากวิกิพีเดีย สารานุกรมเสรี
ข้ามไปที่การนำทาง ข้ามไปที่การค้นหา
ไดอะแกรมของข้อมูลสตริงในการคำนวณ  แสดงประโยค "This is a string!"  ด้วยตัวอักษรแต่ละตัวในกล่องแยก  คำว่า "สตริง" อยู่ด้านบน หมายถึงทั้งประโยค  ป้ายกำกับ "ตัวละคร" อยู่ด้านล่างและชี้ไปที่แต่ละกล่อง
Strings มักจะถูกสร้างขึ้นจากตัวละครพวกเขามีประโยชน์สำหรับการจัดเก็บข้อมูลที่มนุษย์สามารถอ่านได้เช่นประโยคหรือรายการของข้อมูลตามตัวอักษรเช่นลำดับนิวคลีอิกกรดของดีเอ็นเอ

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

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

เมื่อสตริงปรากฏตามตัวอักษรในซอร์สโค้ดจะเรียกว่าสตริงตามตัวอักษรหรือสตริงที่ไม่ระบุตัวตน [1]

ในภาษาอย่างเป็นทางการซึ่งจะใช้ในตรรกะทางคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์ทฤษฎีสตริงเป็นลำดับ จำกัด ของสัญลักษณ์ที่ได้รับการแต่งตั้งจากชุดที่เรียกว่าอักษร

ประเภทข้อมูลสตริง

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

ความยาวสาย

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

การเข้ารหัสอักขระ

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

logographicภาษาเช่นจีน , ญี่ปุ่นและเกาหลี (รู้จักกันในฐานะCJK ) จำเป็นต้องไปไกลกว่า 256 ตัวอักษร (ขีด จำกัด ของการเข้ารหัสหนึ่งไบต์ 8 บิตต่อตัวอักษร) สำหรับการแสดงที่เหมาะสม โซลูชั่นปกติที่เกี่ยวข้องกับการรักษาการแสดงเดี่ยวไบต์สำหรับ ASCII และการใช้การแสดงสองไบต์สำหรับ CJK ideographsการใช้สิ่งเหล่านี้กับรหัสที่มีอยู่ทำให้เกิดปัญหากับการจับคู่และการตัดสตริง ซึ่งความรุนแรงนั้นขึ้นอยู่กับวิธีการออกแบบการเข้ารหัสอักขระ การเข้ารหัสบางอย่างเช่นEUCครอบครัวรับประกันว่าค่าไบต์ในช่วง ASCII จะแสดงเฉพาะอักขระ ASCII นั้นเท่านั้น ทำให้การเข้ารหัสปลอดภัยสำหรับระบบที่ใช้อักขระเหล่านั้นเป็นตัวคั่นฟิลด์ การเข้ารหัสอื่นๆ เช่นISO-2022และShift-JISไม่รับประกันดังกล่าว ทำให้การจับคู่กับรหัสไบต์ไม่ปลอดภัย การเข้ารหัสเหล่านี้ไม่ใช่ "การซิงโครไนซ์ตัวเอง" ดังนั้นการระบุขอบเขตของอักขระจำเป็นต้องสำรองข้อมูลจนถึงจุดเริ่มต้นของสตริง และการวางสองสตริงเข้าด้วยกันอาจส่งผลให้สตริงที่สองเสียหายได้

Unicodeทำให้รูปภาพง่ายขึ้นบ้าง ภาษาโปรแกรมส่วนใหญ่ตอนนี้มีประเภทข้อมูลสำหรับสตริง Unicode รูปแบบสตรีมไบต์ที่ต้องการของ Unicode UTF-8ได้รับการออกแบบมาให้ไม่มีปัญหาที่อธิบายไว้ข้างต้นสำหรับการเข้ารหัสแบบหลายไบต์ที่เก่ากว่า UTF-8, UTF-16 และUTF-32ต้องการให้โปรแกรมเมอร์รู้ว่าหน่วยรหัสขนาดคงที่แตกต่างจาก "อักขระ" ปัญหาหลักในปัจจุบันคือ API ที่ออกแบบอย่างไม่ถูกต้องซึ่งพยายามซ่อนความแตกต่างนี้ (UTF-32 ทำ ทำให้จุดโค้ดมีขนาดคงที่ แต่สิ่งเหล่านี้ไม่ใช่ "อักขระ" เนื่องจากการเขียนโค้ด)

การใช้งาน

บางภาษา เช่น C++ และRubyปกติอนุญาตให้เปลี่ยนเนื้อหาของสตริงหลังจากสร้างแล้ว สิ่งเหล่านี้เรียกว่าสตริงที่ไม่แน่นอนในภาษาอื่นๆ เช่นJavaและPythonค่าจะคงที่และต้องสร้างสตริงใหม่หากมีการแก้ไข สิ่งเหล่านี้เรียกว่าสตริงที่ไม่เปลี่ยนรูป (ภาษาเหล่านี้บางภาษายังมีอีกประเภทหนึ่งที่สามารถเปลี่ยนแปลงได้ เช่น Java และ.NET StringBuilder , Java ที่ปลอดภัยต่อเธรดStringBufferและCocoa NSMutableString )

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

บางภาษา เช่นPrologและErlangหลีกเลี่ยงการใช้ประเภทข้อมูลสตริงโดยเฉพาะเลย แทนที่จะใช้แบบแผนของการแสดงสตริงเป็นรายการของรหัสอักขระ

การเป็นตัวแทน

การแสดงสตริงขึ้นอยู่กับการเลือกรายการอักขระและวิธีการเข้ารหัสอักขระเป็นอย่างมาก การใช้งานสตริงที่เก่ากว่าได้รับการออกแบบมาเพื่อทำงานกับรายการเพลงและการเข้ารหัสที่กำหนดโดย ASCII หรือส่วนขยายล่าสุด เช่นISO 8859ซีรีส์ การใช้งานสมัยใหม่มักใช้รายการเพลงที่กว้างขวางซึ่งกำหนดโดย Unicode ร่วมกับการเข้ารหัสที่ซับซ้อนต่างๆ เช่น UTF-8 และ UTF-16

คำว่าbyte stringมักจะระบุสตริงวัตถุประสงค์ทั่วไปของไบต์ แทนที่จะเป็นสตริงที่มีแต่อักขระ (อ่านได้) เท่านั้น สตริงของบิต หรืออื่นๆ สตริงของไบต์มักจะบอกเป็นนัยว่าไบต์สามารถรับค่าใดๆ ก็ได้ และข้อมูลใดๆ สามารถจัดเก็บได้ตามที่เป็นอยู่ ซึ่งหมายความว่าไม่ควรมีการตีความค่าเป็นค่าการสิ้นสุด

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

สิ้นสุดด้วยค่า Null

ความยาวของสตริงสามารถจัดเก็บโดยปริยายได้โดยใช้อักขระสิ้นสุดพิเศษ มักจะเป็นอักขระ null (NUL) ซึ่งมีทุกบิตเป็นศูนย์ประชุมที่ใช้และชุลมุนโดยเป็นที่นิยมการเขียนโปรแกรมภาษา C [2]ดังนั้นตัวแทนนี้มักจะเรียกว่าเป็นสตริง C เป็นตัวแทนของนี้nสตริงอักขระใช้เวลาn + 1 พื้นที่ (1 สำหรับเทอร์มิ) และจึงเป็นโครงสร้างข้อมูลโดยปริยาย

ในสตริงที่ยุติ โค้ดการสิ้นสุดไม่ใช่อักขระที่อนุญาตในสตริงใดๆ สตริงที่มีฟิลด์ความยาวไม่มีข้อจำกัดนี้ และยังสามารถจัดเก็บข้อมูลไบนารีได้ตามต้องการ

ตัวอย่างของสตริงที่สิ้นสุดด้วยค่า null ที่เก็บไว้ในบัฟเฟอร์ 10 ไบต์พร้อมกับการแสดงASCII (หรือUTF-8 ที่ทันสมัยกว่า ) เป็นตัวเลขฐานสิบหก 8 บิตได้แก่

F R A N K NUL k e f w
46 16 52 16 41 16 4E 16 4B 16 00 16 6B 16 65 16 66 16 77 16

ความยาวของสตริงในตัวอย่างข้างต้น " FRANK" คือ 5 อักขระ แต่มีขนาด 6 ไบต์ อักขระหลังจากเทอร์มิเนเตอร์ไม่เป็นส่วนหนึ่งของการแสดง อาจเป็นส่วนหนึ่งของข้อมูลอื่นหรือเพียงแค่ขยะ (สตริงของแบบฟอร์มนี้บางครั้งเรียกว่าสตริง ASCIZหลังจากคำสั่งภาษาแอสเซมบลีดั้งเดิมที่ใช้ในการประกาศ)

สิ้นสุดไบต์และบิต

การใช้ไบต์พิเศษอื่นที่ไม่ใช่ค่า null สำหรับการยกเลิกสตริงนั้นเคยปรากฏในทั้งฮาร์ดแวร์และซอฟต์แวร์ แม้ว่าบางครั้งมีค่าที่เป็นอักขระการพิมพ์ด้วย$ถูกใช้โดยระบบแอสเซมเบลอร์จำนวนมาก:ใช้โดยระบบCDC (อักขระนี้มีค่าเป็นศูนย์) และZX80ใช้"[3]เนื่องจากนี่คือตัวคั่นสตริงในภาษาพื้นฐาน

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

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

คำนำหน้าความยาว

ความยาวของสตริงยังสามารถจัดเก็บไว้อย่างชัดเจน ตัวอย่างเช่น โดยนำหน้าสตริงที่มีความยาวเป็นค่าไบต์ อนุสัญญานี้ใช้ในภาษาปาสกาลหลายภาษา; เป็นผลให้บางคนเรียกสตริงเช่นสตริงปาสคาลหรือP-สตริงการจัดเก็บความยาวสตริงเป็นไบต์ข้อ จำกัด ความยาวสายสูงสุดถึง 255 เพื่อหลีกเลี่ยงข้อ จำกัด เช่นการใช้งานที่ดีขึ้นของ P-สตริงใช้ 16, 32, หรือ 64 บิตคำที่จะเก็บความยาวสตริง เมื่อฟิลด์ความยาวครอบคลุมพื้นที่ที่อยู่สตริงจะถูกจำกัดโดยหน่วยความจำที่มีอยู่เท่านั้น

หากความยาวมีขอบเขต ก็สามารถเข้ารหัสในปริภูมิคงที่ ซึ่งโดยทั่วไปแล้วจะเป็นคำเครื่อง ดังนั้นจึงนำไปสู่โครงสร้างข้อมูลโดยปริยาย โดยใช้ช่องว่างn + kโดยที่kคือจำนวนอักขระในคำ (8 สำหรับ 8 บิต ASCII บนเครื่อง 64 บิต 1 สำหรับ UTF-32/UCS-4 แบบ 32 บิตบนเครื่อง 32 บิต ฯลฯ) หากความยาวไม่มีขอบเขต การเข้ารหัสความยาวnจะใช้พื้นที่บันทึก ( n ) (ดูรหัสความยาวคงที่ ) ดังนั้นสตริงที่นำหน้าความยาวจึงเป็นโครงสร้างข้อมูลที่กระชับ การเข้ารหัสสตริงที่มีความยาวnในบันทึก ( n ) + nช่องว่าง .

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

นี่คือสตริง Pascal ที่เก็บไว้ในบัฟเฟอร์ 10 ไบต์ พร้อมกับการแสดง ASCII / UTF-8:

ระยะเวลา F R A N K k e f w
05 16 46 16 52 16 41 16 4E 16 4B 16 6B 16 65 16 66 16 77 16

สตริงเป็นบันทึก

หลายภาษา รวมถึงภาษาเชิงวัตถุ ใช้สตริงเป็นระเบียนที่มีโครงสร้างภายใน เช่น:

 สตริงคลาส{ 
  size_t ความยาว; 
  ถ่าน* ข้อความ; 
};

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

การเป็นตัวแทนอื่น ๆ

ทั้งรหัสสิ้นสุดอักขระและรหัสความยาวจำกัดสตริง: ตัวอย่างเช่น อาร์เรย์อักขระ C ที่มีอักขระ null (NUL) ไม่สามารถจัดการได้โดยตรงโดยฟังก์ชันไลบรารีสตริง C : สตริงที่ใช้โค้ดความยาวจะถูกจำกัดไว้ที่ค่าสูงสุดของโค้ดความยาว

ข้อจำกัดทั้งสองนี้สามารถเอาชนะได้ด้วยการเขียนโปรแกรมที่ชาญฉลาด

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

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

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

ปัญหาด้านความปลอดภัย

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

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

สตริงตามตัวอักษร

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

ตัวแทนทั่วไปสองรายการคือ:

  • ล้อมรอบด้วยเครื่องหมายคำพูด ( อัญประกาศคู่ASCII 0x22หรืออัญประกาศเดี่ยว ASCII 0x27) ซึ่งใช้โดยภาษาโปรแกรมส่วนใหญ่ เพื่อให้สามารถใส่อักขระพิเศษ เช่น เครื่องหมายคำพูด อักขระขึ้นบรรทัดใหม่ หรืออักขระที่ไม่สามารถพิมพ์ได้ มักจะมีEscape Sequenceไว้ ซึ่งมักจะนำหน้าด้วยอักขระแบ็กสแลช (ASCII 0x5C)
  • ยกเลิกโดยการขึ้นบรรทัดใหม่ลำดับเช่นใน Windows INI ไฟล์

สตริงที่ไม่ใช่ข้อความ

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

โปรแกรมเมอร์ภาษาซีแยกแยะความแตกต่างระหว่าง "สตริง" หรือ "สตริงของอักขระ" ได้ชัดเจน ซึ่งตามคำจำกัดความแล้วจะเป็นโมฆะเสมอ เทียบกับ "สตริงไบต์" หรือ "สตริงเทียม" ซึ่งอาจจัดเก็บไว้ในอาร์เรย์เดียวกันแต่เป็น มักจะไม่สิ้นสุดเป็นโมฆะ ใช้สตริง C จัดการฟังก์ชั่นใน "สตริงไบต์" ดังกล่าวมักจะดูเหมือนว่าจะทำงาน แต่นำไปสู่การต่อมาปัญหาด้านความปลอดภัย [6] [7] [8]

อัลกอริทึมการประมวลผลสตริง

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

อัลกอริทึมบางหมวดหมู่รวมถึง:

อัลกอริทึมสตริงขั้นสูงมักจะจ้างกลไกที่ซับซ้อนและโครงสร้างข้อมูลในหมู่พวกเขาต้นไม้ต่อท้ายและเครื่อง จำกัด รัฐ

ชื่อstringologyได้รับการประกาศเกียรติคุณในปี 1984 โดยนักวิทยาศาสตร์คอมพิวเตอร์Zvi Galilสำหรับปัญหาของอัลกอริทึมและโครงสร้างข้อมูลที่ใช้สำหรับการประมวลผลสตริง [9] [ ต้องการแหล่งข้อมูลบุคคลที่สาม ]

ภาษาและยูทิลิตี้ที่เน้นสตริงอักขระ

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

ยูทิลิตีUnixจำนวนมากดำเนินการจัดการสตริงอย่างง่าย และสามารถใช้เพื่อตั้งโปรแกรมอัลกอริธึมการประมวลผลสตริงอันทรงพลังบางอย่างได้อย่างง่ายดาย ไฟล์และสตรีมที่จำกัดอาจถูกมองว่าเป็นสตริง

APIบางตัวเช่นMultimedia Control Interface , SQL แบบฝังหรือprintfใช้สตริงเพื่อเก็บคำสั่งที่จะถูกตีความ

ภาษาการเขียนโปรแกรมสคริปต์ล่าสุดรวมถึง Perl, Python , Ruby และ Tcl ใช้นิพจน์ทั่วไปเพื่ออำนวยความสะดวกในการดำเนินการข้อความ Perl ตั้งข้อสังเกตโดยเฉพาะอย่างยิ่งสำหรับการใช้สีหน้าปกติ[10]และอีกหลายภาษาอื่น ๆ และการประยุกต์ใช้นิพจน์ปกติ Perl เข้ากันได้

บางภาษา เช่น Perl และ Ruby รองรับการแก้ไขสตริงซึ่งอนุญาตให้ประเมินนิพจน์ที่กำหนดเองและรวมไว้ในตัวอักษรสตริง

ฟังก์ชันสตริงอักขระ

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

ตัวอย่างพื้นฐานที่สุดของฟังก์ชันสตริงคือฟังก์ชันความยาวสตริงซึ่งเป็นฟังก์ชันที่คืนค่าความยาวของสตริง (ไม่นับอักขระตัวสิ้นสุดหรือข้อมูลโครงสร้างภายในใดๆ ของสตริง) และไม่แก้ไขสตริง ฟังก์ชั่นนี้มักจะเป็นชื่อหรือlength lenตัวอย่างเช่นlength("hello world")จะส่งกลับ 11 ฟังก์ชันทั่วไปอีกประการหนึ่งคือconcatenationโดยที่สตริงใหม่จะถูกสร้างขึ้นโดยการต่อท้ายสองสตริง ซึ่งมักจะเป็นโอเปอเรเตอร์ + การบวก

สถาปัตยกรรมชุดคำสั่งของไมโครโปรเซสเซอร์บางตัวมีการสนับสนุนโดยตรงสำหรับการดำเนินการสตริง เช่น การคัดลอกบล็อก (เช่น In intel x86m ) (11) REPNZ MOVSB

ทฤษฎีที่เป็นทางการ

ให้ Σ เป็นชุดสัญลักษณ์จำนวนจำกัด (หรือเรียกอีกอย่างว่า ตัวอักษร) เรียกว่าตัวอักษร . ไม่มีการตั้งสมมติฐานเกี่ยวกับธรรมชาติของสัญลักษณ์ สตริง (หรือคำ ) มากกว่าΣมี จำกัด ใด ๆลำดับของสัญลักษณ์จากΣ [12]ตัวอย่างเช่น ถ้า Σ = {0, 1} ดังนั้น01011คือสตริงที่อยู่เหนือ Σ

ความยาวของสตริงsคือจำนวนของสัญลักษณ์ในs (ความยาวของลำดับ) และสามารถเป็นจำนวนเต็มไม่เป็นลบ ; มันมักจะแสดงเป็น | |. สตริงที่ว่างเปล่าเป็นสตริงที่ไม่ซ้ำกันมากกว่าΣ 0 ยาวและมีการแสดงεหรือλ [12] [13]

ชุดของสตริงทั่วΣของความยาวnจะแสดงΣ n ตัวอย่างเช่น ถ้า Σ = {0, 1} แล้ว Σ 2 = {00, 01, 10, 11} โปรดทราบว่า Σ 0 = {ε} สำหรับตัวอักษร Σ ใดๆ

ชุดของสตริงทั่วΣยาว ๆ เป็นปิด KleeneของΣและจะแสดงΣ * ในแง่ของ Σ n ,

ตัวอย่างเช่น ถ้า Σ = {0, 1} แล้ว Σ * = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...} แม้ว่าเซต Σ *เองจะนับได้ไม่สิ้นสุดแต่แต่ละองค์ประกอบของ Σ *เป็นสตริงที่มีความยาวจำกัด

ชุดของสตริงที่อยู่เหนือ Σ (เช่นเซตย่อยใดๆของ Σ * ) เรียกว่าภาษาที่เป็นทางการ ส่วน Σ ตัวอย่างเช่น ถ้า Σ = {0, 1} ชุดของสตริงที่มีเลขศูนย์เป็นเลขคู่ {ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, ...} เป็นภาษาที่เป็นทางการมากกว่า Σ

การต่อและสตริงย่อย

เรียงต่อกันเป็นสิ่งสำคัญที่ดำเนินการทวิภาคในΣ*สำหรับการใด ๆ สองสาย sและเสื้อในΣ * , เรียงต่อกันของพวกเขาถูกกำหนดให้เป็นลำดับของสัญลักษณ์ใน sตามลำดับของตัวละครในเสื้อและจะแสดงเซนต์ตัวอย่างเช่นถ้าΣ = {A, B, ... , Z}, s  = และ T  = แล้ว ST  = และ TS =  bearhugbearhughugbear

สตริงเป็นเชื่อมโยงแต่ไม่ใช่การสับเปลี่ยนการดำเนินงาน สตริงว่าง ε ทำหน้าที่เป็นองค์ประกอบเอกลักษณ์ ; สำหรับสตริงs , ε s = s ε = s ดังนั้น เซต Σ *และการดำเนินการต่อกันจะเกิดเป็นmonoidซึ่งเป็นmonoid อิสระที่สร้างโดย Σ นอกจากนี้ ฟังก์ชันความยาวยังกำหนดmonoid homomorphismจาก Σ *เป็นจำนวนเต็มไม่เป็นลบ (นั่นคือ ฟังก์ชัน, ดังนั้น ).

สตริงsบอกว่าจะเป็นสตริงย่อยหรือปัจจัยของทีถ้ามีอยู่ (อาจจะเป็นที่ว่างเปล่า) สายยูและvดังกล่าวว่าT = USV ความสัมพันธ์ "คือการย่อยของ" กำหนดส่วนคำสั่งในΣ *ที่องค์ประกอบน้อยซึ่งเป็นสตริงที่ว่างเปล่า

คำนำหน้าและคำต่อท้าย

สตริงsมีการกล่าวถึงเป็นคำนำหน้าของทีถ้ามีสตริงยูดังกล่าวที่T = suถ้ามึงเป็นว่าง, sมีการกล่าวถึงเป็นที่เหมาะสมคำนำหน้าของเสื้อแฟ่, สตริงsมีการกล่าวถึงเป็นคำต่อท้ายของทีถ้ามีสตริงยูดังกล่าวที่T = เราถ้าคุณเป็น nonempty sจะเป็นคำต่อท้ายที่เหมาะสมของt. คำต่อท้ายและคำนำหน้าเป็นสตริงของเสื้อ ทั้งความสัมพันธ์ "เป็นคำนำหน้า" และ "เป็นคำต่อท้ายของ" ได้รับการสั่งซื้อคำนำหน้า

การกลับรายการ

ด้านหลังของสตริงคือสตริงที่มีสัญลักษณ์เหมือนกันแต่อยู่ในลำดับที่กลับกัน ตัวอย่างเช่น ถ้าs = abc (โดยที่ a, b และ c เป็นสัญลักษณ์ของตัวอักษร) การกลับกันของsคือ cba สตริงที่ตรงกันข้ามตัวเอง (เช่นs = madam) เรียกว่าpalindromeซึ่งรวมถึงสตริงว่างและสตริงทั้งหมดที่มีความยาว 1

การหมุน

สตริงs = uvมีการกล่าวถึงเป็นการหมุนของทีถ้าT = วู ตัวอย่างเช่น ถ้า Σ = {0, 1} สตริง 0011001 คือการหมุนของ 0100110 โดยที่u = 00110 และv = 01 อีกตัวอย่างหนึ่ง สตริง abc มีการหมุนที่แตกต่างกันสามแบบ กล่าวคือ abc เอง (ด้วยu =abc, v =ε), bca (พร้อมu =bc, v =a) และ cab (ด้วยu =c, v =ab)

การเรียงลำดับศัพท์

มักจะเป็นประโยชน์ในการกำหนดลำดับในชุดของสตริง ถ้าตัวอักษรΣมียอดสั่งซื้อ (cf ลำดับตัวอักษร ) หนึ่งสามารถกำหนดยอดสั่งซื้อในΣ *เรียกว่าการสั่งซื้อพจนานุกรมตัวอย่างเช่น ถ้า Σ = {0, 1} และ 0 < 1 ดังนั้นลำดับศัพท์ใน Σ * จะรวมความสัมพันธ์ ε < 0 < 00 < 000 < ... < 0001 < 001 < 01 < 010 < 011 < 0110 < 01111 < 1 < 10 < 100 < 101 < 111 < 1111 < 11111 ... ลำดับพจนานุกรมเป็นผลรวมหากลำดับตามตัวอักษร แต่ไม่ได้มีพื้นฐานที่ดีสำหรับตัวอักษรที่ไม่น่าสนใจ แม้ว่าจะเรียงลำดับตามตัวอักษรก็ตาม

ดูShortlexสำหรับการจัดลำดับสตริงทางเลือกที่คงไว้ซึ่งรากฐานที่ดี

การทำงานของสตริง

การดำเนินการเพิ่มเติมจำนวนหนึ่งเกี่ยวกับสตริงมักเกิดขึ้นในทฤษฎีที่เป็นทางการ เหล่านี้จะได้รับในบทความเกี่ยวกับการดำเนินงานสตริง

โทโพโลยี

(ไฮเปอร์)คิวบ์ของสตริงไบนารีที่มีความยาว 3

สตริงยอมรับการตีความต่อไปนี้เป็นโหนดบนกราฟ โดยที่kคือจำนวนสัญลักษณ์ใน Σ:

  • สตริงที่มีความยาวคงที่nสามารถดูได้ว่าเป็นตำแหน่งจำนวนเต็มในไฮเปอร์คิวบ์nมิติที่มีด้านยาวk -1
  • สตริงตัวแปรความยาว (ความยาว จำกัด ) สามารถดูเป็นโหนดบนที่สมบูรณ์แบบkต้นไม้ -ary
  • สตริงอินฟินิท (มิฉะนั้นไม่ถือว่านี่) สามารถดูเป็นเส้นทางที่ไม่มีที่สิ้นสุดในk -node สมบูรณ์กราฟ

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

Isomorphismsระหว่างการแสดงสตริงของโครงสร้างสามารถพบได้โดย normalizing ตามการหมุนน้อยที่สุด lexicographically สตริง

ดูเพิ่มเติม

อ้างอิง

  1. ^ "แนะนำ Java - MFC 158 G" . เก็บจากต้นฉบับเมื่อ 2016-03-03 ตัวอักษรสตริง (หรือค่าคงที่) เรียกว่า 'สตริงที่ไม่ระบุชื่อ'
  2. ^ ไบรอันท์ แรนดัล อี. ; David, O'Hallaron (2003), ระบบคอมพิวเตอร์: มุมมองของโปรแกรมเมอร์ (2003 ed.), Upper Saddle River, NJ: Pearson Education, p. 40, ISBN  0-13-034074-X, เก็บถาวรจากต้นฉบับเมื่อ 2007-08-06
  3. ^ Wearmouth เจฟฟ์ "การชุมนุมรายชื่อของรอมของซินแคล ZX80 ว่า" เก็บจากต้นฉบับเมื่อ 15 สิงหาคม 2015CS1 maint: URL ไม่พอดี ( ลิงค์ )
  4. ^ แอลลิสัน, เดนนิส. "หมายเหตุการออกแบบสำหรับ Tiny Basic" . เก็บถาวรจากต้นฉบับเมื่อ 2017-04-10.
  5. ชาร์ลส์ คราวลีย์. "โครงสร้างข้อมูลสำหรับลำดับข้อความ" ที่จัดเก็บ 2016/03/04 ที่เครื่อง Wayback มาตรา "รู้จัก" ที่จัดเก็บ 2016/04/04 ที่เครื่อง Wayback
  6. ^ "strlcpy และ strlcat - สม่ำเสมอ ปลอดภัย คัดลอกสตริงและต่อกัน" เก็บถาวร 2016-03-13 ที่ Wayback Machine
  7. ^ "พูดจาโผงผางเกี่ยวกับ strcpy, strncpy และ strlcpy" เก็บถาวร 2016-02-29 ที่ Wayback Machine
  8. คีธ ทอมป์สัน. "ไม่ strncpy() ไม่ใช่ strcpy() ที่ "ปลอดภัยกว่า" 2555.
  9. ^ "ชมรมสตริงโลจีแห่งปราก" . สตริงวิทยา . org เก็บถาวรจากต้นฉบับเมื่อ 1 มิถุนายน 2558 . สืบค้นเมื่อ23 พฤษภาคม 2558 .
  10. ^ "Perl ที่จำเป็น" . เก็บถาวรจากต้นฉบับเมื่อ 2012-04-21 จุดแข็งที่โด่งดังที่สุดของ Perl อยู่ที่การจัดการสตริงด้วยนิพจน์ทั่วไป
  11. ^ "คำสั่งสตริง x86" . เก็บถาวรจากต้นฉบับเมื่อ 2015-03-27
  12. อรรถเป็น บาร์บารา เอช. ปาร์ตี; อลิซ เทอร์ มูเลน ; โรเบิร์ต อี. วอลล์ (1990). วิธีการทางคณิตศาสตร์ในภาษาศาสตร์ . คลูเวอร์
  13. จอห์น อี. ฮอพครอฟต์, เจฟฟรีย์ ดี. อุลล์แมน (1979) รู้เบื้องต้นเกี่ยวกับออทฤษฎีภาษาและการคำนวณ แอดดิสัน-เวสลีย์. ISBN 0-201-02988-X. ที่นี่: sect.1.1, p.1