String (computer science): Difference between revisions

Revision as of 12:47, 2 October 2024

Revision as of 12:09, 6 October 2024

Line 12:

== Purpose ==

A primary purpose of strings is to store human-readable text, suchlike as [[Word|words]] and [[Sentence (linguistics)|sentences]]. Strings are used to communicate information from a [[computer program]] to the user of the program.<ref>{{cite web |url=https://users.cs.utah.edu/~germain/PPS/Topics/strings.html |website=University of Utah, Kahlert School of Computing |title=Strings

|first=H. James |last=de St. Germain }}</ref> A program may also accept string input from its user. Further, strings may store data expressed as characters yet not intended for human reading.

Line 30:

Use of the word "string" to mean "a sequence of symbols or linguistic elements in a definite order" emerged from mathematics, [[symbolic logic]], and [[linguistic theory]] to speak about the [[formal system|formal]] behavior of symbolic systems, setting aside the symbols' meaning.<ref name=Burchfield1986>{{cite encyclopedia |title=string |encyclopedia=A Supplement to the Oxford English Dictionary |year=1986 |last=Burchfield |first=R.W. |publisher=Oxford at the Clarendon Press |author-link=Robert Burchfield }}</ref>

For example, [[Logician (disambiguation)|logician]] [[C. I. Lewis]] wrote in 1918:<ref>{{cite book |title=A survey of symbolic logic |___location=Berkeley |publisher=University of California Press |year=1918 |page=355 |last=Lewis |first=C.I. |author-link=C.I. Lewis |url=https://archive.org/details/asurveyofsymboli00lewiuoft/page/355/mode/1up }}</ref>

<blockquote>

''A mathematical system is any set of strings of recognisable marks in which some of the strings are taken initially and the remainder derived from these by operations performed according to rules which are independent of any meaning assigned to the marks. That a system should consist of 'marks' instead of sounds or odours is immaterial.''

</blockquote>

According to [[Jean E. Sammet]], "''the first realistic string handling and pattern matching language''" for computers was [[COMIT]] in the 1950s, followed by the [[SNOBOL]] language of the early 1960s.<ref>{{cite journal |url=https://redirect.cs.umbc.edu/courses/undergraduate/331/resources/papers/sammet1972.pdf |journal=Communications of the ACM |first=Jean E. |last=Sammet |title=Programming Languages: History and Future |date=July 1972 |volume=15 |number=7 |doi=10.1145/361454.361485 |s2cid=2003242 }}</ref>

== String datatypes ==

Line 43:

=== String length ===

Although formal strings can have an arbitrary [[finite]] length, the length of strings in real languages is often constrained to an artificial maximum. In general, there are two types of string datatypes: ''fixed-length strings'', which have a fixed maximum length to be determined at [[compile time]] and which use the same amount of memory whether this maximum is needed or not, and ''variable-length strings'', whose length is not arbitrarily fixed and which can use varying amounts of memory depending on the actual requirements at run time (see [[Memory management]]). Most strings in modern [[programming languages]] are variable-length strings. Of course, even variable-length strings are limited in length – by the size of available [[computer memory]]. The string length can be stored as a separate [[integer]] (which may put another artificial limit on the length) or implicitly through a termination character, usually a character value with all bits zero such as in the [[C (programming language)|C programming language]]. See also "[[#Null-terminated|Null-terminated]]" below.

=== Character encoding ===

String datatypes have historically allocated one [[byte]] per character, and, although the exact character set varied by region, character encodings were similar enough that programmers could often get away with ignoring this, since characters a program treated specially (such as period and space and comma) were in the same place in all the encodings a program would encounter. These character sets were typically based on [[ASCII]] or [[EBCDIC]]. If text in one encoding was displayed on a system using a different encoding, text was often [[mojibake|mangled]], though often somewhat readable and some computer users learned to read the mangled text.

[[Logograph]]ic languages such as [[Chinese language|Chinese]], [[Japanese language|Japanese]], and [[Korean language|Korean]] (known collectively as [[CJK characters|CJK]]) need far more than 256 characters (the limit of a one 8-bit byte per-character encoding) for reasonable representation. The normal solutions involved keeping single-byte representations for ASCII and using two-byte representations for CJK [[ideographs]]. Use of these with existing code led to problems with matching and cutting of strings, the severity of which depended on how the character encoding was designed. Some encodings such as the [[Extended Unix Code|EUC]] family guarantee that a byte value in the ASCII range will represent only that ASCII character, making the encoding safe for systems that use those characters as field separators. Other encodings such as [[ISO-2022]] and [[Shift-JIS]] do not make such guarantees, making matching on byte codes unsafe. These encodings also were not "self-synchronizing", so that locating character boundaries required backing up to the start of a string, and pasting two strings together could result in corruption of the second string.

[[Unicode]] has simplified the picture somewhat. Most programming languages now have a datatype for Unicode strings. Unicode's preferred byte stream format [[UTF-8]] is designed not to have the problems described above for older multibyte encodings. UTF-8, [[UTF-16]] and [[UTF-32]] require the programmer to know that the fixed-size code units are different from the "characters", the main difficulty currently is incorrectly designed APIs that attempt to hide this difference (UTF-32 does make ''code points'' fixed-sized, but these are not "characters" due to composing codes).

=== Implementations ===

{{anchor|String Buffers}}

Some languages, such as [[C++]], [[Perl]] and [[Ruby (programming language)|Ruby]], normally allow the contents of a string to be changed after it has been created; these are termed ''mutable'' strings. In other languages, such as [[Java (programming language)|Java]], [[JavaScript]], [[Lua (programming language)|Lua]], [[Python (programming language)|Python]], and [[Go (programming language)|Go]], the value is fixed and a new string must be created if any alteration is to be made; these are termed ''immutable'' strings. Some of these languages with immutable strings also provide another type that is mutable, such as Java and [[.NET Framework|.NET]]'s {{Javadoc:SE|java/lang|StringBuilder}}, the thread-safe Java {{Javadoc:SE|java/lang|StringBuffer}}, and the [[Cocoa (API)|Cocoa]] <code>NSMutableString</code>. There are both advantages and disadvantages to immutability: although immutable strings may require inefficiently creating many copies, they are simpler and completely [[Thread safety|thread-safe]].

Strings are typically implemented as [[array data type|arrays]] of bytes, characters, or code units, in order to allow fast access to individual units or substrings—including characters when they have a fixed length. A few languages such as [[Haskell (programming language)|Haskell]] implement them as [[linked list]]s instead.

Line 61:

=== 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.

Line 124:

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).--->

Line 160 ⟶ 161:

==== Other representations ====

Both character termination and length codes limit strings: For example, [[C (programming language)|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.

However, bothBoth 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. }}.

Line 177 ⟶ 178:

=== Security concerns ===

The differing [[Computer memory|memory]] layout and storage requirements of strings can affect the security of the program accessing the string data. String representations requiring a terminating character are commonly susceptible to [[buffer overflow]] problems if the terminating character is not present, caused by a coding error or an [[hacker (computer security)|attacker]] deliberately altering the data. String representations adopting a separate length field are also susceptible if the length can be manipulated. In such cases, program code accessing the string data requires [[bounds checking]] to ensure that it does not inadvertently access or change data outside of the string memory limits.

String data is frequently obtained from user input to a program. As such, it is the responsibility of the program to validate the string to ensure that it represents the expected format. Performing [[Improper input validation|limited or no validation]] of user input can cause a program to be vulnerable to [[code injection]] attacks.

Line 184 ⟶ 185:

{{Main|String literal}}

Sometimes, strings need to be embedded inside a [[text file]] that is both human-readable and intended for consumption by a machine. This is needed in, for example, [[source code]] of programming languages, or in [[Configuration file|configuration files]]. In this case, the [[Null character|NUL character]] does not work well as a terminator since it is normally invisible (non-printable) and is difficult to input via a [[Computer keyboard|keyboard]]. Storing the string length would also be inconvenient as manual computation and tracking of the length is tedious and error-prone.

Two common representations are:

Line 193 ⟶ 194:

While character strings are very common uses of strings, a string in computer science may refer generically to any sequence of homogeneously typed data. A [[bit string]] or [[byte string]], for example, may be used to represent non-textual [[binary data]] retrieved from a communications medium. This data may or may not be represented by a string-specific datatype, depending on the needs of the application, the desire of the programmer, and the capabilities of the programming language being used. If the programming language's string implementation is not [[8-bit clean]], data corruption may ensue.

C programmers draw a sharp distinction between a "string", aka a "string of characters", which by definition is always null terminated, andvs. a "byte string" or "pseudo string" which may be stored in the same array but is often not null terminated.
Using [[C string handling]] functions on such a "byte string" often seems to work, but later leads to [[#Security concerns|security problems]].<ref>

[https://www.sudo.ws/todd/papers/strlcpy.html "strlcpy and strlcat - consistent, safe, string copy and concatenation."] {{webarchive|url=https://web.archive.org/web/20160313163321/https://www.sudo.ws/todd/papers/strlcpy.html |date=2016-03-13 }}

</ref><ref>

Line 208 ⟶ 210:

Some categories of algorithms include:

* [[String searching algorithm]]s for finding a given substring or pattern.

* [[String manipulation algorithm]]s.

* [[Sorting algorithm]]s.

* [[Regular expression]] algorithms.

* [[Parser|Parsing]] a string.

* [[Sequence mining]].

Advanced string algorithms often employ complex mechanisms and data structures, among them [[suffix tree]]s and [[finite-state machine]]s.

Line 219 ⟶ 221:

== Character string-oriented languages and utilities ==

Character strings are such a useful datatype that several languages have been designed in order to make string processing applications easy to write. Examples include the following languages:

* [[AWK]].

* [[Icon (programming language)|Icon]].

* [[MUMPS]].

* [[Perl]].

* [[Rexx]].

* [[Ruby (programming language)|Ruby]].

* [[sed]].

* [[SNOBOL]].

* [[Tcl]].

* [[TTM (programming language)|TTM]].

Many [[Unix]] utilities perform simple string manipulations and can be used to easily program some powerful string processing algorithms. Files and finite streams may be viewed as strings.

Line 299 ⟶ 301:

== See also ==

* [[Binary-safe]] — a property of string manipulating functions treating their input as raw data stream.

* [[Bit array]] — a string of binary digits.

* [[C string handling]] — overview of C string handling.

* [[C++ string handling]] — overview of C++ string handling.

* [[Comparison of programming languages (string functions)]].

* [[Connection string]] — passed to a driver to initiate a connection (e.g., to a database).

* [[Empty string]] — its properties and representation in programming languages.

* [[Incompressible string]] — a string that cannot be compressed by any algorithm.

* [[Rope (data structure)]] — a data structure for efficiently manipulating long strings.

* [[String metric]] — notions of similarity between strings.

== References ==