السلاسل النصية (علوم الحاسوب)

على الرغم من أن السلاسل النصية الرسمية يمكن أن يكون لها طول محدود، إلا أن طول السلاسل في اللغات الحقيقية غالبًا ما يكون مقيدًا بحد أقصى اصطناعي. بشكل عام، يوجد نوعان من أنواع بيانات السلاسل النصية: السلاسل ذات الطول الثابت ، والتي لها طول أقصى ثابت يُحدد وقت الترجمة ، وتستخدم نفس مقدار الذاكرة سواءً كانت هذه القيمة القصوى مطلوبة أم لا؛ والسلاسل ذات الطول المتغير ، والتي لا يكون طولها ثابتًا بشكل اعتباطي، ويمكنها استخدام كميات متفاوتة من الذاكرة اعتمادًا على المتطلبات الفعلية أثناء التشغيل (انظر إدارة الذاكرة ). معظم السلاسل النصية في لغات البرمجة الحديثة هي سلاسل ذات طول متغير. بالطبع، حتى السلاسل ذات الطول المتغير محدودة في الطول بمقدار الذاكرة المتاحة. يمكن تخزين طول السلسلة كعدد صحيح منفصل (مما قد يفرض حدًا اصطناعيًا آخر على الطول) أو ضمنيًا من خلال حرف إنهاء، عادةً ما يكون قيمة حرفية جميع بتاتها أصفار، كما هو الحال في لغة البرمجة C. انظر أيضًا " السلاسل المنتهية بصفر " أدناه.

لطالما خصصت أنواع بيانات السلاسل بايتًا واحدًا لكل حرف، وعلى الرغم من اختلاف مجموعة الأحرف الدقيقة باختلاف المناطق، إلا أن ترميزات الأحرف كانت متشابهة بما يكفي ليتمكن المبرمجون غالبًا من تجاهل هذا الأمر، نظرًا لأن الأحرف التي يعاملها البرنامج بشكل خاص (مثل النقطة والمسافة والفاصلة) كانت في نفس الموضع في جميع الترميزات التي سيواجهها البرنامج. وكانت مجموعات الأحرف هذه تستند عادةً إلى ASCII أو EBCDIC . وإذا عُرض نصٌّ بترميزٍ ما على نظامٍ يستخدم ترميزًا مختلفًا، فغالبًا ما كان النص يُشوَّه ، وإن كان غالبًا ما يكون مقروءًا إلى حدٍّ ما، وقد تعلّم بعض مستخدمي الحاسوب قراءة النص المشوه.

تحتاج اللغات التصويرية مثل الصينية واليابانية والكورية (المعروفة مجتمعةً باسم CJK ) إلى أكثر بكثير من 256 حرفًا (الحد الأقصى لترميز بايت واحد لكل حرف، 8 بت) لتمثيلها بشكل معقول. تضمنت الحلول التقليدية استخدام تمثيلات أحادية البايت لرموز ASCII وتمثيلات ثنائية البايت لرموز CJK . أدى استخدام هذه الحلول مع التعليمات البرمجية الموجودة إلى مشاكل في مطابقة السلاسل النصية وقصها، وتفاوتت حدة هذه المشاكل تبعًا لتصميم ترميز الأحرف. تضمن بعض الترميزات، مثل عائلة EUC، أن قيمة البايت في نطاق ASCII ستمثل حرف ASCII هذا فقط، مما يجعل الترميز آمنًا للأنظمة التي تستخدم هذه الأحرف كفواصل بين الحقول. بينما لا تقدم ترميزات أخرى، مثل ISO-2022 و Shift-JIS، مثل هذه الضمانات، مما يجعل المطابقة على رموز البايت غير آمنة. لم تكن هذه الترميزات أيضًا "متزامنة ذاتيًا"، لذا فإن تحديد حدود الأحرف يتطلب الرجوع إلى بداية السلسلة، ويمكن أن يؤدي لصق سلسلتين معًا إلى تلف السلسلة الثانية.

لقد بسّطت يونيكود الصورة إلى حد ما. فمعظم لغات البرمجة الآن تحتوي على نوع بيانات لسلاسل يونيكود. صُمم تنسيق دفق البايتات المفضل لدى يونيكود، UTF-8، لتجنب المشاكل المذكورة أعلاه في ترميزات البايتات المتعددة القديمة. تتطلب ترميزات UTF-8 وUTF-16 و UTF-32 من المبرمج معرفة أن وحدات الترميز ذات الحجم الثابت تختلف عن "الأحرف"، وتكمن الصعوبة الرئيسية حاليًا في واجهات برمجة التطبيقات المصممة بشكل خاطئ والتي تحاول إخفاء هذا الاختلاف (مع أن UTF-32 يجعل نقاط الترميز ذات حجم ثابت، إلا أنها ليست "أحرفًا" نظرًا لتركيبها للرموز).

تسمح بعض لغات البرمجة، مثل C++ و Perl و Ruby ، عادةً بتغيير محتوى السلسلة النصية بعد إنشائها؛ وتُسمى هذه السلاسل النصية القابلة للتغيير . أما في لغات أخرى، مثل Java و JavaScript و Lua و Python و Go ، فتكون القيمة ثابتة، ويجب إنشاء سلسلة نصية جديدة لإجراء أي تعديل؛ وتُسمى هذه السلاسل النصية غير القابلة للتغيير . توفر بعض هذه اللغات التي تدعم السلاسل النصية غير القابلة للتغيير نوعًا آخر قابلًا للتغيير، مثل Java و .NET ، و StringBuilderJava الآمنة للاستخدام المتزامن StringBuffer، و CocoaNSMutableString . يُصاحب عدم قابلية التغيير مزايا وعيوب: فبينما قد تتطلب السلاسل النصية غير القابلة للتغيير إنشاء نسخ متعددة، إلا أنها أبسط وأكثر أمانًا للاستخدام المتزامن .

تُنفَّذ السلاسل النصية عادةً على شكل مصفوفات من البايتات أو الأحرف أو وحدات الترميز، مما يسمح بالوصول السريع إلى الوحدات الفردية أو السلاسل الفرعية، بما في ذلك الأحرف عندما يكون لها طول ثابت. في المقابل ، تُنفِّذ بعض اللغات، مثل هاسكل، السلاسل النصية على شكل قوائم مرتبطة .

توفر العديد من اللغات عالية المستوى السلاسل كنوع بيانات أساسي، مثل JavaScript و PHP ، بينما توفرها معظم اللغات الأخرى كنوع بيانات مركب، وبعضها يدعم كتابة القيم الحرفية بشكل خاص، على سبيل المثال، Java و C# .

تتجنب بعض لغات البرمجة، مثل C و Prolog و Erlang ، تخصيص نوع بيانات للسلاسل النصية، وتعتمد بدلاً من ذلك على تمثيل السلاسل النصية كقوائم من رموز الأحرف. حتى في لغات البرمجة التي تحتوي على نوع بيانات مخصص للسلاسل النصية، يمكن عادةً التعامل مع السلاسل النصية كسلسلة من رموز الأحرف، مثل قوائم الأعداد الصحيحة أو غيرها من القيم.

تعتمد تمثيلات السلاسل النصية بشكل كبير على اختيار مجموعة الأحرف وطريقة ترميزها. صُممت تطبيقات السلاسل النصية القديمة للعمل مع مجموعة الأحرف والترميز المُحددين بواسطة ASCII، أو امتدادات أحدث مثل سلسلة ISO 8859. أما التطبيقات الحديثة، فتستخدم غالبًا مجموعة الأحرف الواسعة المُحددة بواسطة Unicode إلى جانب مجموعة متنوعة من الترميزات المعقدة مثل UTF-8 وUTF-16.

يشير مصطلح " سلسلة البايت" عادةً إلى سلسلة عامة من البايتات، وليس إلى سلاسل من الأحرف (القابلة للقراءة) فقط، أو سلاسل من البتات، أو ما شابه. وتوحي سلاسل البايت غالبًا بأن البايتات يمكن أن تأخذ أي قيمة، ويمكن تخزين أي بيانات كما هي، أي أنه لا ينبغي تفسير أي قيمة على أنها قيمة إنهاء.

تتشابه معظم تطبيقات السلاسل النصية إلى حد كبير مع المصفوفات ذات الطول المتغير ، حيث تخزن عناصرها رموز الأحرف المقابلة. ويكمن الاختلاف الرئيسي في أنه مع بعض الترميزات، قد يشغل حرف منطقي واحد أكثر من عنصر واحد في المصفوفة. يحدث هذا، على سبيل المثال، مع ترميز UTF-8، حيث يمكن أن تشغل الرموز المفردة ( نقاط ترميز UCS ) من بايت واحد إلى أربعة بايتات، ويمكن أن يشغل الحرف الواحد عددًا غير محدد من الرموز. في هذه الحالات، يختلف الطول المنطقي للسلسلة (عدد الأحرف) عن الطول الفعلي للمصفوفة (عدد البايتات المستخدمة). يتجنب ترميز UTF-32 الجزء الأول من هذه المشكلة.

public final class String { private unsigned long length ; // طول السلسلة private UniquePointer < char [] > text ; // ملكية صريحة // الدوال العامة... }

قد يؤثر اختلاف تخطيط الذاكرة ومتطلبات التخزين للسلاسل النصية على أمان البرنامج الذي يصل إلى بيانات السلسلة. فعادةً ما تكون تمثيلات السلاسل النصية التي تتطلب حرف إنهاء عرضةً لمشاكل تجاوز سعة المخزن المؤقت إذا لم يكن حرف الإنهاء موجودًا، سواءً كان ذلك بسبب خطأ برمجي أو قيام مهاجم بتغيير البيانات عمدًا. كما أن تمثيلات السلاسل النصية التي تعتمد حقل طول منفصل تكون عرضةً للمشاكل أيضًا إذا أمكن التلاعب بالطول. في مثل هذه الحالات، يتطلب رمز البرنامج الذي يصل إلى بيانات السلسلة النصية فحصًا للحدود لضمان عدم وصوله عن غير قصد إلى بيانات خارج حدود ذاكرة السلسلة أو تغييرها.

تُستقى البيانات النصية عادةً من مدخلات المستخدم للبرنامج. لذا، يقع على عاتق البرنامج مسؤولية التحقق من صحة هذه البيانات لضمان تمثيلها للتنسيق المطلوب. قد يؤدي عدم إجراء التحقق الكافي أو انعدامه من مدخلات المستخدم إلى جعل البرنامج عرضةً لهجمات حقن التعليمات البرمجية .

عملية الربط هيعملية ثنائية مهمة${\displaystyle \Sigma ^{*}}$لأي سلسلتين${\displaystyle s}$و${\displaystyle t}$في${\displaystyle \Sigma ^{*}}$، ويُعرَّف تسلسلها بأنه سلسلة الرموز في${\displaystyle s}$متبوعًا بتسلسل الأحرف في${\displaystyle t}$، ويُشار إليه بـ${\displaystyle st}$على سبيل المثال، إذا${\displaystyle \Sigma =\{{\texttt {a}},{\texttt {b}},...,{\texttt {z}}\}}$(أي الأبجدية الإنجليزية الصغيرة )،${\displaystyle s={\texttt {bear}}}$، و${\displaystyle t={\texttt {hug}}}$، ثم${\displaystyle st={\texttt {bearhug}}}$و${\displaystyle ts={\texttt {hugbear}}}$.

عملية دمج السلاسل النصية هي عملية تجميعية ، ولكنها غير تبديلية . السلسلة النصية الفارغة${\displaystyle \varepsilon }$يُستخدم كعنصر هوية ؛ لأي سلسلة نصية${\displaystyle s}$،${\displaystyle \varepsilon s=s\varepsilon =s}$لذلك، فإن المجموعة${\displaystyle \Sigma ^{*}}$وتُشكّل عملية الربط أحاديًا ، وهو الأحادي الحر الناتج عن${\displaystyle \Sigma }$بالإضافة إلى ذلك، تُعرّف دالة الطول تشاكلًا أحاديًا من${\displaystyle \Sigma ^{*}}$إلى الأعداد الصحيحة غير السالبة (أي دالة)${\displaystyle L:\Sigma ^{*}\mapsto \mathbb {N} \cup \{0\}}$بحيث${\displaystyle L(st)=L(s)+L(t)\quad \forall s,t\in \Sigma ^{*}}$).

خيط${\displaystyle s}$يُقال إنها سلسلة فرعية أو عامل من${\displaystyle t}$إذا كانت هناك سلاسل نصية (ربما فارغة)${\displaystyle u}$و${\displaystyle v}$بحيث${\displaystyle t=usv}$تحدد العلاقة "سلسلة فرعية من" ترتيبًا جزئيًا على${\displaystyle \Sigma ^{*}}$، وأصغر عنصر فيها هو السلسلة الفارغة.

خيط${\displaystyle s}$يقال إنها بادئة لـ${\displaystyle t}$إذا كان هناك سلسلة${\displaystyle u}$بحيث${\displaystyle t=su}$. لو${\displaystyle u}$غير فارغ،${\displaystyle s}$ويُقال إنها بادئة مناسبة لـ${\displaystyle t}$بشكل متناظر، خيط${\displaystyle s}$يقال إنها لاحقة من${\displaystyle t}$إذا كان هناك سلسلة${\displaystyle u}$بحيث${\displaystyle t=us}$. لو${\displaystyle u}$غير فارغ،${\displaystyle s}$ويُقال إنها لاحقة مناسبة لـ${\displaystyle t}$اللواحق والبوادئ هي سلاسل فرعية من${\displaystyle t}$. كلا العلاقتين "هو بادئة لـ" و "هو لاحقة لـ" هما ترتيبات بادئة .

معكوس السلسلة هو سلسلة تحتوي على نفس الرموز ولكن بترتيب عكسي. على سبيل المثال، إذا${\displaystyle s={\texttt {abc}}}$(أين${\displaystyle {\texttt {a}}}$،${\displaystyle {\texttt {b}}}$، و${\displaystyle {\texttt {c}}}$(هي رموز الأبجدية)، ثم عكسها${\displaystyle s}$يكون${\displaystyle {\texttt {cba}}}$سلسلة معكوسة (مثلاً،${\displaystyle s={\texttt {madam}}}$يُطلق على هذا الاسم اسم المتناظر ، والذي يشمل أيضًا السلسلة الفارغة وجميع السلاسل ذات الطول${\displaystyle 1}$.

خيط${\displaystyle s=uv}$يقال إنها دورة من${\displaystyle t}$لو${\displaystyle t=vu}$على سبيل المثال، إذا${\displaystyle \Sigma =\{{\texttt {0}},{\texttt {1}}\}}$السلسلة${\displaystyle {\texttt {0011001}}}$هو دوران${\displaystyle {\texttt {0100110}}}$، أين${\displaystyle u={\texttt {00110}}}$و${\displaystyle v={\texttt {01}}}$كمثال آخر، السلسلة${\displaystyle {\texttt {abc}}}$له ثلاث دورات مختلفة، وهي:${\displaystyle {\texttt {abc}}}$نفسه (مع${\displaystyle u={\texttt {abc}}}$،${\displaystyle v=\varepsilon }$)${\displaystyle {\texttt {bca}}}$(مع${\displaystyle u={\texttt {bc}},v={\texttt {a}}}$)، و${\displaystyle {\texttt {cab}}}$(مع${\displaystyle u={\texttt {c}},v={\texttt {ab}}}$).

من المفيد غالبًا تحديد ترتيب لمجموعة من السلاسل النصية. إذا كانت الأبجدية${\displaystyle \Sigma }$له ترتيب كلي (انظر الترتيب الأبجدي )، ويمكن تعريف ترتيب كلي على${\displaystyle \Sigma ^{*}}$يُطلق عليه الترتيب المعجمي . يكون الترتيب المعجمي تامًا إذا كان الترتيب الأبجدي تامًا، ولكنه لا يكون ذا أساس متين لأي أبجدية غير بديهية، حتى لو كان الترتيب الأبجدي تامًا. على سبيل المثال، إذا${\displaystyle \Sigma =\{{\texttt {0}},{\texttt {1}}\}}$و${\displaystyle {\texttt {0}}<{\texttt {1}}}$ثم الترتيب المعجمي على${\displaystyle \Sigma ^{*}}$يشمل ذلك العلاقات${\displaystyle \varepsilon <{\texttt {0}}<{\texttt {00}}<{\texttt {000}}<...<{\texttt {0001}}<...<{\texttt {001}}<...<{\texttt {01}}<{\texttt {010}}<...<{\texttt {011}}<{\texttt {0110}}<...<{\texttt {01111}}<...<{\texttt {1}}<{\texttt {10}}<{\texttt {100}}<...<{\texttt {101}}<...<{\texttt {111}}<...<{\texttt {1111}}<...<{\texttt {11111}}...}$فيما يتعلق بهذا الترتيب، على سبيل المثال المجموعة اللانهائية${\displaystyle \{{\texttt {1}},{\texttt {01}},{\texttt {001}},{\texttt {0001}},{\texttt {00001}},{\texttt {000001}},...\}}$لا يحتوي على عنصر أدنى.

راجع Shortlex للاطلاع على ترتيب بديل للسلاسل النصية يحافظ على سلامة الأساس. بالنسبة للأبجدية المذكورة في المثال، يكون ترتيب Shortlex كالتالي:${\displaystyle \varepsilon <{\texttt {0}}<{\texttt {1}}<{\texttt {00}}<{\texttt {01}}<{\texttt {10}}<{\texttt {11}}<{\texttt {000}}<{\texttt {001}}<{\texttt {010}}<{\texttt {011}}<{\texttt {100}}<{\texttt {101}}<{\texttt {0110}}<{\texttt {111}}<{\texttt {0000}}<{\texttt {0001}}<{\texttt {0010}}<{\texttt {0011}}<...<{\texttt {1111}}<{\texttt {00000}}<{\texttt {00001}}...}$

توجد عدة عمليات إضافية على السلاسل النصية شائعة في النظرية الرسمية. وقد وردت هذه العمليات في مقالة عمليات السلاسل النصية .

يمكن تفسير السلاسل النصية على النحو التالي كعقد على الرسم البياني، حيث${\displaystyle k}$عدد الرموز في${\displaystyle \Sigma }$:

• سلاسل ذات طول ثابت${\displaystyle n}$يمكن اعتبارها مواقع الأعداد الصحيحة في${\displaystyle n}$مكعب فائق الأبعاد ذو أضلاع طولها${\displaystyle k-1}$.
• يمكن اعتبار السلاسل ذات الأطوال المتغيرة (ذات الطول المحدود) بمثابة عقد على سطح مثالي${\displaystyle k}$شجرة -ary .
• يمكن اعتبار السلاسل اللانهائية (التي لم يتم تناولها هنا) بمثابة مسارات لانهائية على${\displaystyle k}$رسم بياني كامل مكون من عقدة واحدة .

الطوبولوجيا الطبيعية لمجموعة السلاسل ذات الطول الثابت أو المتغير هي الطوبولوجيا المنفصلة، ​​بينما الطوبولوجيا الطبيعية لمجموعة السلاسل اللانهائية هي طوبولوجيا النهاية ، حيث تُعتبر مجموعة السلاسل اللانهائية النهاية العكسية لمجموعات السلاسل المنتهية. هذا هو البناء المستخدم للأعداد p -adic وبعض بنى مجموعة كانتور ، وينتج عنه نفس الطوبولوجيا.

يمكن إيجاد التماثلات بين تمثيلات السلاسل للطوبولوجيا عن طريق التطبيع وفقًا لدوران السلسلة الأدنى معجميًا .