利用者:Moro/メモ/string

プログラミングや数学の一分野において、 ストリング (string) とは、あらかじめ定義された集合もしくはアルファベットから選ばれた記号を順番に並べた列を意味する。

プログラミングにおけるストリングは、通常、データ値の列を格納するデータ型のひとつとして理解される。このデータ値は、バイト列であることが普通で、さらにそれは文字コードに基づく文字を表すことが多い。そこからストリングは、より一般的なデータ型である配列とは区別される。ストリングが文字列を表現することが多いことから、「バイナリ・ストリング」や「バイト・ストリング」などと言う場合には、そのストリングに格納されたデータが（必ずしも）テキストを表現しているわけではないことを示している。

ある変数がデータ型としてストリングであると宣言された場合、通常、あらかじめ定められた数のシンボルを保持することが可能な領域をメモリ上に確保する。ソースコード中にストリングがそのまま書かれた場合には、文字リテラルと呼ばれ、書かれている通りのことを表現しているとされる。

形式理論

Σをアルファベットとする。このアルファベットは、空集合ではない有限の集合である。 Σの要素は「シンボル」または「文字」と言われる。 Σからなるストリング (あるいは語) とは、Σ中の文字による有限の文字列すべてである。例えば、Σ = {0, 1} とした場合、「0101」はΣからなるストリングのひとつである。

ストリングの長さとは、そのストリングの中の文字の数 (列の長さ) であり、任意の負ではない整数である。空ストリングとは、Σからなるストリングの中、長さが0という特殊なものであり、 ε または λ と書く。

Σからなる長さ n のすべてのストリングの集合は、Σⁿ と書く。例えば、Σ = {0, 1} の場合、Σ² = {00, 01, 10, 11} である。なお、Σ⁰ = {ε} は、任意のアルファベットΣにあてはまる。

Σからなる任意の長さのすべてのストリングの集合は、Σのクリーネ閉包であり、Σ* と書く。 Σⁿについて次のことが成り立つ。

\Sigma ^{*}=\bigcup _{n\in \mathbb {N} }\Sigma ^{n}

例えば、Σ = {0, 1} とした場合、Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …} となる。 Σ*自体は可算有限集合であるが、Σ* の要素は全て有限の長さを持つ。

Σからなるストリングの集合 (すなわち Σ* の部分集合) は、Σからなる形式言語とよぶ。例えば、Σ = {0, 1} とした場合、偶数個の「0」を含むストリングの集合 ({ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, …}) は、Σからなる形式言語である。

連結と部分ストリング

連結は、Σ* に対する重要な二項演算のひとつである。 Σ* からとった二つの任意のストリング s と t があるとして、これらの連結とは、s 内の文字シーケンスに t 内の文字シーケンスが続くことと定義され、 st と書かれる。例えば、Σ = {a, b, …, z}、s = bear、t = hug とした場合、 st = bearhug、ts = hugbearとなる。

ストリングの連結は、結合的ではあるが、不可換な演算である。また、空ストリングは単位元である。すなわち任意の s に対して εs = sε = s を満たす。したがって、集合Σ* とその結合法則は、モノイドを形成する。Σから生成された自由モノイドである。加えて、長さを求める関数は、Σ* から負ではない整数へのモノイド準同型として定義できる。

もし t = usv を満たすストリング u と v (空ストリングでも可) が存在するとき、ストリング s は t の部分ストリングまたは要素と言われる。「〜は…の部分ストリングである」という二項関係は、最小限が空ストリングである Σ* の半順序集合と定義される。

辞書式順序

ストリングの集合について順序を定義する要求はしばしばある。もしアルファベット Σ が全順序集合 (例えばアルファベット順) であれば、 Σ* についての全順序集合が定義でき、それを辞書式順序と呼ぶ。ちなみに、Σ が有限であることから、Σ の整列集合を、ひいては Σ* の整列集合を定義することもできる。例えば、Σ = {0, 1} で 0 < 1 ならば、Σ* の辞書式順序は ε < 0 < 00 < 000 < … < 011 < 0110 < … < 01111 < … < 1 < 10 < 100 < … < 101 < … < 111 … となる。

ストリング演算

形式理論においては、この他にも多くのストリングについての演算が存在する。ストリング演算参照。

トポロジー

ストリングをグラフ上のノードとして見れば、以下のような解釈が成り立つ:

固定長のストリングは、超立方体上のノードと見なすことができる。
可変長の（かつ有限長の）ストリングは、kをΣ中のシンボルの数とするk分木上のノードと見なすことができる。
無限長のストリングはk分木上の無限のパスと見なすことができる。

固定長または可変長のストリングの集合についての自然な位相は離散位相であるが、無限長のストリングの集合についての自然な位相は極限位相であり、無限長ストリングの集合を有限長ストリングの集合の逆極限と見ることができる。これは、p進数のために用いられる構造であり、またカントール集合の構造の一部でもあるので、それらと同じトポロジーが導かれる。

文字列型

文字列型は、ストリングの形式的な概念をモデル化したデータ型のひとつである。文字列型はほとんどすべてのプログラミング言語で実装されている、重要で使用頻度の高いデータ型である。文字列型をプリミティブ型とする言語もあれば、複合型とするものもある。高級なプログラミング言語のほとんどが、構文規則において文字列を定めており、通常は何らかの引用符によって括ることで文字列型のインスタンスを表現する。また、そのようなメタ文字列をリテラルもしくな文字列リテラルなどとよぶ。

文字列の長さ

→「ヌル (コンピュータ)」も参照