String (computer Science) Article Index for
String 		Website Links For
String 		 

Information About

String (computer Science)
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...




STRING DATATYPES

A string datatype is a Datatype modeled on the idea of a formal string. Strings are such an important and useful datatype that they are implemented in nearly every Programming Language . In some languages they are available as Primitive Type s and in others as Composite Type s. The Syntax of most high-level programming languages allows for a string, usually quoted in some way, to represent an instance of a string datatype; such a meta-string is called a ''literal'' or '' String Literal ''.

Although formal strings can have an arbitrary (but 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, and ''variable length strings'' whose length is not arbitrarily fixed. Most strings in modern programming languages are variable length strings. Despite the name, even variable length strings are limited in length; although, generally, the limit depends only on the amount of Memory available.

Historically, string datatypes had one Byte for each character, and although the exact character set varied by region, the Character Encoding s were similar enough that programmers could generally get away with ignoring this — groups of character sets used by the same system in different regions either had a character in the same place, or did not have it at all. Mostly these character sets were based on ASCII , though IBM s mainframe systems went their own way and used EBCDIC .

Logograph ic languages such as Chinese , Japanese and Korean (known collectively as CJK ) need far more than 256 characters — the limit of a one-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 EUC family guarantee that a byte value in the ASCII range will only represent that ASCII character making the encoding safe for systems that use those characters as field separators or similar. Others such as ISO-2022 and Shift-jis do not make such guarantees, making matching on byte codes unsafe. Another issue is that if the beginning of a string is cut off, important instructions for the decoder or information on position in a multibyte sequence may be lost. Another issue is that if strings are joined together (especially after having their ends truncated by code not aware of the encoding), the first string may not leave the encoder in a state suitable for dealing with the second string.

Unicode has complicated the picture somewhat. Most languages have a datatype for Unicode strings (usually UTF-16 as it was usually added before Unicode supplemental planes were introduced). Converting between Unicode and local encodings requires an understanding of the local encoding, which may be problematic for existing systems where strings of various encodings are being transmitted together with no real marking as to what encoding they are in.

Some languages like C++ implement strings as templates that can be used with any primitive type, but this is the exception not the rule.


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 .

Most string implementations are very similar to variable-length 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 characters can take anywhere from one to four bytes. In these cases, the logical length of the string differs from the logical length of the array.

The length of a string can be stored implicitly by using a special terminating character; often this is the Null Character having value zero, a convention used and perpetuated by the popular C Programming Language . Hence this representation is commonly referred to as C String . The length of a string can also be stored explicitly, for example by prefixing the string with Integer value — a convention used in Pascal , consequently some people call it a P-string.

In terminated strings, the terminating code is not an allowable character in any string.

Here is an example of a null-terminated string stored in a 10-byte Buffer , along with its ASCII representation:




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


The length of a string in the above example 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 another string or just garbage. (Strings of this form are sometimes called ''ASCIZ strings'', after the Assembly Language directive used to declare them.)

Here is the equivalent (old style) Pascal string:




lengthF R A N K k f f w
0546 52 41 4E 4B 6B 66 66 77


While these representations are common, others are possible. Using Rope s makes certain string operations, such as insertions, deletions, and concatenations more efficient.


Memory management

There are several serious memory management issues with strings, depending on the language these may be either handled invisiblly by the language or left up to the programmer.
  • Making sure memory for strings that are no longer in use gets freed;

  • Making sure strings that are still in use ''do not'' get freed;

  • Making sure that a write to a memory block allocated to a string does not go past the end of the string. ( Buffer Overflow ); and

  • Making sure when a string is altered it does not have an unwanted/unexpected effect on other code.


Different languages deal with the issue of strings and their memory management in different ways:
  • C offers pointers to characters and the library supplies several functions which operate on strings as NUL terminated character sequences. The memory and buffer management must be dealt with by the programmer. This process is error prone and often leads to bugs when programmers get it wrong. In many cases these bugs have led to security holes (usually the famous Buffer Overflow attack). There is a notion that C's low level string programming leads to higher performance, and it does for certain operations such as character extractions. However, the NUL terminated string design actually leads to much slower concatenation, comparison and string in string searching than the length prefixed method. C++ adopts the same interface for basic strings.

  • Borland Pascal uses fixed-size arrays with a length byte at the beginning. The main weaknesses of this method are that it fundamentally limits the maximum length of the string (to 255), and always consumes memory for the whole buffer, even if the string itself is much shorter. The length limitation often forced coders to use character pointers to do things by hand like in C. On the other hand it does not involve the heap manager and therefore cannot cause a Memory Leak problem.

  • Delphi 2 upwards (and Freepascal in Delphi mode) uses reference counts maintained by the compiler. If an attempt is made to modify a string that has a reference count other than one, the string is copied first. Therefore, to the programmer, it looks like the string is being passed by-value but the huge overhead of copying the string on every assignment is removed. Unfortunately it also requires generation of what is effectively a try-finally block to ensure that the reference count is decreased when a procedure is exited by an exception. The main weakness of this is that it complicates multithreaded implementations of these languages, since reference counts need to be updated atomically.

  • The C++ STL makes use of advanced language features such as copy constructors and destructors for non reference objects to allow a string template and class to be implemented that has semantics similar to a primitive type.

  • Garbage-collected languages like Microsoft .NET , Python , Perl , Lua and Java usually make strings an Immutable class and let the garbage collector deal with strings that are no longer needed. This works well enough but can make string manipulation difficult and expensive so these languages usually have a second mutable class for doing string manipulation ('''' in Java, ''StringBuilder'' in .NET, and so on). Some languages, such as Java and .NET, take advantage of the immutable property of strings to compact storage for the strings in shared memory using a String Intern Pool . Within the shared memory, the same string data can be used for multiple strings.

  • D represents strings as arrays of characters. A D array is a length/pointer pair. This enables slicing and substrings can be taken without needing to copy the data. The length attribute means that bounds checking can be done. Garbage collection takes care of the problem of keeping track of string memory. Character arrays can be in UTF-8, UTF-16 or UTF-32 format.




VECTORS

While character strings are very common uses of strings, a string in computer science may refer generically to any vector of homogenously typed data. A string of bits or bytes, for example, may be used to represent data retrieved from a communications medium. This data may or may not be represented by a string-specific data type, depending on the needs of the application, the desire of the programmer, and the capabilities of the programming language being used.


STRING ALGORITHMS

There are many Algorithm s for processing strings, each with various tradeoffs. Some categories of algorithms include

Advanced string algorithms often employ complex mechanisms and data structures, among them Suffix Tree s and Finite State Machine s.


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:

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.

Several string libraries for the C and C++ programming languages do exist which add greater functionality for string processing in those languages:

Some APIs like Multimedia Control Interface , Embedded SQL or Printf use strings to hold commands that will be interpreted.

Recent Scripting Programming Language s, including Perl , Python , Ruby , and Tcl employ Regular Expression s to facilitate text operations.


FORMAL THEORY

One starts with a Non-empty Finite Set Σ called an '' Alphabet ''. Elements of this alphabet are called ''characters''. A string (or '''word''') over Σ is any finite Sequence of characters from Σ. Infinite sequences of characters are not allowed in this definition.

A particularly important string is the sequence of no characters, called the empty string. The empty string is often denoted ε or λ.

For example, if Σ = {0, 1}, strings over Σ are of the form
:ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …

  • . One can define a Binary Operation on Σ--- called '' Concatenation ''. If ''s'' and ''t'' are two strings, their concatenation, denoted ''st'', is defined as the sequence of characters in ''s'' followed by the sequence of characters in ''t''.


For example, if ''s'' = bear and ''t'' = hug then ''st'' = bearhug and ''ts'' = hugbear.

  • forms a Monoid under string concatenation. In fact, Σ--- is the Free Monoid generated by Σ.


  • to N (Non-negative integers with addition).



  • called Lexicographical Order . Note that when Σ is finite, it is always possible to define a well ordering on Σ and thus on Σ---. For example, the lexicographical ordering of {0,1}--- is λ, 0, 1, 00, 01, 10, 11, 000, 001, ...



  • itself is always an infinite language. Important examples of formal languages include Regular Expression s and Formal Grammar s.




    • CHARACTER STRING FUNCTIONS

    String Functions are used to manipulate a string or change or edit the contents of a string. They also are used to query information about a string. They are usually used within the context of a computer Programming Language .

    The most basic example of a string function is the ''length(string)'' function. This function returns the length of a string (not counting the null terminator or any other of the string's internal structural information) and does not change the string.

    eg. ''length("hello world")'' would return 11.

    There are many string functions which exist in other languages with similar or exactly the same syntax or parameters. For example in many languages the length function is usually represented as ''len(string)''. Even though string functions are very useful to a computer programmer, a computer programmer using these functions should be mindful that a string function in one language could behave differently or have a similar or completely different function name, parameters, syntax and outcomes.