Editing String (computer science) (section)

=== Representations ===
Representations of strings depend heavily on the choice of character repertoire and the method of character encoding. Older string implementations were designed to work with repertoire and encoding defined by ASCII, or more recent extensions like the [[ISO 8859]] series. Modern implementations often use the extensive repertoire defined by Unicode along with a variety of complex encodings such as UTF-8 and UTF-16.

The term ''byte string'' usually indicates a general-purpose string of bytes, rather than strings of only (readable) characters, strings of bits, or such. Byte strings often imply that bytes can take any value and any data can be stored as-is, meaning that there should be no value interpreted as a termination value.

Most string implementations are very similar to variable-length [[Array data type|array]]s with the entries storing the [[character code]]s of corresponding characters. The principal difference is that, with certain encodings, a single logical character may take up more than one entry in the array. This happens for example with UTF-8, where single codes ([[Universal Character Set|UCS]] code points) can take anywhere from one to four bytes, and single characters can take an arbitrary number of codes. In these cases, the logical length of the string (number of characters) differs from the physical length of the array (number of bytes in use). [[UTF-32]] avoids the first part of the problem.

==== Null-terminated ====
{{Main|Null-terminated string}}

The length of a string can be stored implicitly by using a special terminating character; often this is the [[null character]] (NUL), which has all bits zero, a convention used and perpetuated by the popular [[C (programming language)|C programming language]].<ref>
{{Citation
 |last1        = Bryant
 |first1       = Randal E.
 |author-link = Randal Bryant
 |last2       = David
 |first2      = O'Hallaron
 |title       = Computer Systems: A Programmer's Perspective
 |place       = Upper Saddle River, NJ
 |publisher   = Pearson Education
 |year        = 2003
 |edition     = 2003
 |url         = http://csapp.cs.cmu.edu/
 |isbn        = 0-13-034074-X
 |page        = 40
 |url-status     = live
 |archive-url  = https://web.archive.org/web/20070806075942/http://csapp.cs.cmu.edu/
 |archive-date = 2007-08-06
}}
</ref> Hence, this representation is commonly referred to as a '''C string'''. This representation of an ''n''-character string takes ''n'' + 1 space (1 for the terminator), and is thus an [[implicit data structure]].

In terminated strings, the terminating code is not an allowable character in any string. Strings with ''length'' field do not have this limitation and can also store arbitrary [[binary data]].

An example of a ''null-terminated string'' stored in a 10-byte [[Buffer (computer science)|buffer]], along with its [[ASCII]] (or more modern [[UTF-8]]) representation as 8-bit [[hexadecimal number]]s is:

{| class="wikitable" style="margin-left: auto; margin-right:auto"
 |-
 | <code>F</code>  || <code>R</code>  || <code>A</code>  || <code>N</code>  || <code>K</code>
 | <small>[[Null character|NUL]]</small>
 | style="background: #DDD" | <code style="background: #DDD">k</code>
 | style="background: #DDD" | <code style="background: #DDD">e</code>
 | style="background: #DDD" | <code style="background: #DDD">f</code>
 | style="background: #DDD" | <code style="background: #DDD">w</code>
 |-
 | 46<sub>[[Hexadecimal#Using 0–9 and A–F|16]]</sub> || 52<sub>16</sub> || 41<sub>16</sub> || 4E<sub>16</sub> || 4B<sub>16</sub>
 | 00<sub>16</sub>
 | style="background: #DDD" | 6B<sub>16</sub>
 | style="background: #DDD" | 65<sub>16</sub>
 | style="background: #DDD" | 66<sub>16</sub>
 | style="background: #DDD" | 77<sub>16</sub>
 |}

The length of the string in the above example, "<code>FRANK</code>", is 5 characters, but it occupies 6 bytes. Characters after the terminator do not form part of the representation; they may be either part of other data or just garbage. (Strings of this form are sometimes called ''ASCIZ strings'', after the original [[assembly language]] directive used to declare them.)

==== Byte- and bit-terminated ====
Using a special byte other than null for terminating strings has historically appeared in both hardware and software, though sometimes with a value that was also a printing character. <code>$</code> was used by many assembler systems, <code>:</code> used by [[Control Data Corporation|CDC]] systems (this character had a value of zero), and the [[ZX80]] used <code>"</code><ref name=asm>{{cite web|last1=Wearmouth |first1=Geoff |title=An Assembly Listing of the ROM of the Sinclair ZX80 |url=http://www.wearmouth.demon.co.uk/zx80.htm |url-status=unfit |archive-url=https://web.archive.org/web/20150815035611/http://www.wearmouth.demon.co.uk/zx80.htm |archive-date=August 15, 2015 }}</ref> since this was the string delimiter in its BASIC language.

Somewhat similar, "data processing" machines like the [[IBM 1401]] used a special [[Word mark (computer hardware)|word mark]] bit to delimit strings at the left, where the operation would start at the right. This bit had to be clear in all other parts of the string. This meant that, while the IBM 1401 had a seven-bit word, almost no-one ever thought to use this as a feature, and override the assignment of the seventh bit to (for example) handle ASCII codes.

Early microcomputer software relied upon the fact that ASCII codes do not use the high-order bit, and set it to indicate the end of a string. It must be reset to 0 prior to output.<ref>{{cite web |last1=Allison |first1=Dennis |title=Design Notes for Tiny BASIC |url=http://www.ittybittycomputers.com/IttyBitty/TinyBasic/DDJ1/Design.html |url-status=live |archive-url=https://web.archive.org/web/20170410220759/http://www.ittybittycomputers.com/IttyBitty/TinyBasic/DDJ1/Design.html |archive-date=2017-04-10 }}</ref>

==== Length-prefixed ====
The length of a string can also be stored explicitly, for example by prefixing the string with the length as a byte value. This convention is used in many [[Pascal (programming language)|Pascal]] dialects; as a consequence, some people call such a string a '''Pascal string''' or '''P-string'''. Storing the string length as byte limits the maximum string length to 255. To avoid such limitations, improved implementations of P-strings use 16-, 32-, or 64-bit [[Word (data type)|words]] to store the string length. When the ''length'' field covers the [[address space]], strings are limited only by the [[Dynamic memory allocation|available memory]].

If the length is bounded, then it can be encoded in constant space, typically a machine word, thus leading to an [[implicit data structure]], taking ''n'' + ''k'' space, where ''k'' is the number of characters in a word (8 for 8-bit ASCII on a 64-bit machine, 1 for 32-bit UTF-32/UCS-4 on a 32-bit machine, etc.).
If the length is not bounded, encoding a length ''n'' takes log(''n'') space (see [[fixed-length code]]), so length-prefixed strings are a [[succinct data structure]], encoding a string of length ''n'' in log(''n'') + ''n'' space.

In the latter case, the length-prefix field itself does not have fixed length, therefore the actual string data needs to be moved when the string grows such that the length field needs to be increased.<!---commented out: "bad" is not an issue in a technical encyclopedic article---This in itself is not that bad since the number of bytes is just logarithmic on the length of string,---><!---commented out: while NULL-terminated string allow for pointers to proper substrings, length-prefixed strings do not; a pointer to a length-prefixed string has to point to the length field, which remains at the same location after growing--- but the downside is that any direct pointers to the string data get invalidated (they should move by one).--->

Here is a Pascal string stored in a 10-byte buffer, along with its ASCII / UTF-8 representation:

{| class="wikitable" style="margin-left: auto; margin-right:auto"
 |-
 | <small>length</small>
 | <code>F</code>  || <code>R</code>  || <code>A</code>  || <code>N</code>  || <code>K</code>
 | style="background: #DDD" | <code style="background: #DDD">k</code>
 | style="background: #DDD" | <code style="background: #DDD">e</code>
 | style="background: #DDD" | <code style="background: #DDD">f</code>
 | style="background: #DDD" | <code style="background: #DDD">w</code>
 |-
 | 05<sub>16</sub>
 | 46<sub>16</sub> || 52<sub>16</sub> || 41<sub>16</sub> || 4E<sub>16</sub> || 4B<sub>16</sub>
 | style="background: #DDD" | 6B<sub>16</sub>
 | style="background: #DDD" | 65<sub>16</sub>
 | style="background: #DDD" | 66<sub>16</sub>
 | style="background: #DDD" | 77<sub>16</sub>
 |}

==== Strings as records ====
Many languages, including object-oriented ones, implement strings as [[record (computer science)|record]]s with an internal structure like:

<syntaxhighlight lang="cpp">
class string {
  size_t length;
  char *text;
};
</syntaxhighlight>

However, since the implementation is usually [[information hiding|hidden]], the string must be accessed and modified through member functions. <code>text</code> is a pointer to a dynamically allocated memory area, which might be expanded as needed. See also [[string (C++)]].

==== Other representations ====
Both character termination and length codes limit strings: For example, C character arrays that contain null (NUL) characters cannot be handled directly by [[C string handling|C string]] library functions: Strings using a length code are limited to the maximum value of the length code.

Both of these limitations can be overcome by clever programming.

It is possible to create data structures and functions that manipulate them that do not have the problems associated with character termination and can in principle overcome length code bounds. It is also possible to optimize the string represented using techniques from [[Run-length encoding|run length encoding]] (replacing repeated characters by the character value and a length) and [[Hamming coding|Hamming encoding]]{{ clarify | date = June 2015 | reason = did you mean Huffman compression? Or do we need a few more words about error correction coding here? I don't see how either one helps us find out how long the string is. }}.

While these representations are common, others are possible. Using [[Rope (data structure)|rope]]s makes certain string operations, such as insertions, deletions, and concatenations more efficient.

The core data structure in a [[text editor]] is the one that manages the string (sequence of characters) that represents the current state of the file being edited.
While that state could be stored in a single long consecutive array of characters, a typical text editor instead uses an alternative representation as its sequence data structure—a [[gap buffer]], a [[linked list]] of lines, a [[piece table]], or a [[Rope (data structure)|rope]]—which makes certain string operations, such as insertions, deletions, and undoing previous edits, more efficient.<ref>
Charles Crowley.
[http://www.cs.unm.edu/~crowley/papers/sds.pdf "Data Structures for Text Sequences"] {{webarchive|url=https://web.archive.org/web/20160304042917/https://www.cs.unm.edu/~crowley/papers/sds.pdf |date=2016-03-04 }}.
Section
[http://www.cs.unm.edu/~crowley/papers/sds/node1.html "Introduction"] {{webarchive|url=https://web.archive.org/web/20160404020539/http://www.cs.unm.edu/~crowley/papers/sds/node1.html |date=2016-04-04 }}.
</ref>