文字列（コンピュータサイエンス）

形式的な文字列は任意の有限長を持つことができますが、実際のプログラミング言語では、文字列の長さは人為的な最大値に制限されることがよくあります。一般に、文字列データ型には 2 種類あります。固定長文字列は、コンパイル時に決定される固定の最大長を持ち、この最大長が必要かどうかに関わらず同じ量のメモリを使用します。可変長文字列は、長さが任意に固定されておらず、実行時の実際の要件に応じて可変量のメモリを使用できます (メモリ管理を参照)。現代のプログラミング言語のほとんどの文字列は可変長文字列です。もちろん、可変長文字列であっても、使用可能なメモリ量によって長さが制限されます。文字列の長さは、別の整数として格納することも (これにより、長さに人為的な制限が加わる可能性があります)、C 言語のようにすべてのビットがゼロの文字値である終端文字によって暗黙的に格納することもできます。下記の「ヌル終端」も参照してください。

文字列データ型は従来、文字ごとに1バイトを割り当てており、文字セットは地域によって異なっていたものの、文字エンコーディングは十分に似通っていたため、プログラマーはしばしばこれを無視することができました。これは、プログラムが特別に扱う文字（ピリオド、スペース、コンマなど）が、プログラムが遭遇するすべてのエンコーディングで同じ位置にあったためです。これらの文字セットは通常、ASCIIまたはEBCDICに基づいていました。あるエンコーディングのテキストを別のエンコーディングを使用するシステムで表示すると、テキストはしばしば文字化けしましたが、多くの場合、ある程度は読み取ることができたため、一部のコンピューターユーザーは文字化けしたテキストを読むことを覚えました。

中国語、日本語、韓国語（総称してCJKと呼ばれる）などの表意文字言語では、適切な表現のために256文字（1文字あたり8ビットバイトのエンコーディングの限界）をはるかに超える文字数が必要です。従来の解決策は、ASCIIには1バイト表現、CJKの表意文字には2バイト表現を使用することでした。これらを既存のコードで使用すると、文字列のマッチングや切り取りに問題が発生し、その深刻度は文字エンコーディングの設計方法によって異なりました。EUCファミリーなどの一部のエンコーディングでは、ASCII範囲内のバイト値がそのASCII文字のみを表すことが保証されているため、これらの文字をフィールド区切り文字として使用するシステムではエンコーディングが安全です。ISO -2022やShift-JISなどの他のエンコーディングでは、このような保証がないため、バイトコードによるマッチングが安全ではありません。これらのエンコーディングは「自己同期」もしていなかったため、文字境界を見つけるには文字列の先頭に戻る必要があり、2つの文字列を貼り付けると2番目の文字列が破損する可能性がありました。

Unicode は状況をいくらか単純化しました。現在、ほとんどのプログラミング言語には Unicode 文字列用のデータ型があります。Unicode が推奨するバイトストリーム形式であるUTF-8は、古いマルチバイトエンコーディングで上記のような問題が発生しないように設計されています。UTF-8、UTF-16、UTF-32 では、プログラマーは固定サイズのコード単位が「文字」とは異なることを認識する必要があります。現在の主な問題は、この違いを隠蔽しようとする API の設計が不適切であることです (UTF-32 ではコードポイントが固定サイズになりますが、これらはコードを構成するため「文字」ではありません)。

C++、Perl、Ruby などの一部の言語では、通常、文字列が作成された後でもその内容を変更することができます。これらは可変文字列と呼ばれます。Java 、JavaScript、Lua、Python、Goなどの他の言語では、値は固定されており、変更を加える場合は新しい文字列を作成する必要があります。これらは不変文字列と呼ばれます。不変文字列を持つこれらの言語の中には、Java や.NETの、スレッドセーフな Java 、Cocoaのように、可変の別の型も提供しているものがあります。不変性には利点と欠点があります。不変文字列では、非効率的に多くのコピーを作成する必要があるかもしれませんが、よりシンプルで完全にスレッドセーフです。StringBuilderStringBufferNSMutableString

文字列は通常、バイト配列、文字配列、またはコード単位配列として実装され、個々の単位や部分文字列（固定長の文字を含む）に高速にアクセスできるようになっています。Haskellなどの一部の言語では、代わりに連結リストとして実装されています。

JavaScriptやPHPなど、多くの高水準言語は文字列を基本データ型として提供していますが、 JavaやC#のように、文字列を複合データ型として提供し、リテラルを記述するための特別な言語サポートを備えている言語もあります。

C、Prolog、Erlangなどの一部のプログラミング言語では、専用の文字列データ型を実装せず、代わりに文字列を文字コードのリストとして表現するという慣習を採用しています。専用の文字列型を持つプログラミング言語であっても、文字列は通常、整数やその他の値のリストと同様に、文字コードのシーケンスとして反復処理できます。

文字列の表現方法は、使用する文字セットと文字エンコーディング方式に大きく依存します。古い文字列実装は、ASCIIで定義された文字セットとエンコーディング、あるいはISO 8859シリーズのようなより新しい拡張規格に対応するように設計されていました。現代の実装では、Unicodeで定義された豊富な文字セットに加え、UTF-8やUTF-16といった多様な複雑なエンコーディング方式がよく用いられています。

バイト列という用語は通常、文字のみの文字列やビット列などではなく、汎用的なバイト列を指します。バイト列は、バイトが任意の値を取ることができ、あらゆるデータをそのまま格納できることを暗示しており、終端値として解釈される値は存在しないことを意味します。

ほとんどの文字列実装は、対応する文字の文字コードを格納するエントリを持つ可変長配列と非常によく似ています。主な違いは、特定のエンコーディングでは、1つの論理文字が配列内の複数のエントリを占める場合があることです。たとえば、UTF-8では、単一のコード（UCSコードポイント）が1バイトから4バイトまでを占め、1つの文字が任意の数のコードを占めることができます。このような場合、文字列の論理長（文字数）は、配列の物理的な長さ（使用バイト数）とは異なります。UTF -32は、この問題の前半部分を回避します。

public final class String { private unsigned long length ; // 文字列の長さprivate UniquePointer < char [] > text ; // 明示的な所有権// 公開メソッド... }

文字列のメモリレイアウトとストレージ要件の違いは、文字列データにアクセスするプログラムのセキュリティに影響を与える可能性があります。終端文字を必要とする文字列表現は、コーディングエラーや攻撃者による意図的なデータ改ざんによって終端文字が存在しない場合、バッファオーバーフローの問題に陥りやすい傾向があります。長さフィールドを別個に持つ文字列表現も、長さが操作可能な場合は同様に脆弱性があります。このような場合、文字列データにアクセスするプログラムコードは、文字列メモリの制限範囲外のデータに誤ってアクセスしたり変更したりしないように、境界チェックを行う必要があります。

文字列データは、プログラムへのユーザー入力から取得されることが多い。そのため、プログラムは文字列が期待される形式であることを確認するために、文字列の検証を行う責任がある。ユーザー入力の検証を不十分または全く行わないと、プログラムはコードインジェクション攻撃に対して脆弱になる可能性がある。

連結は重要な二項演算です$\displaystyle \Sigma ^{*}}$任意の2つの文字列について${\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 {ハグ}}}$、 それから${\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}}}$3つの異なる回転があります。${\displaystyle {\texttt {abc}}}$それ自体（${\displaystyle u={\texttt {abc}}}$、${\displaystyle v=\バレプシロン }$)${\displaystyle {\texttt {bca}}}$（と${\displaystyle u={\texttt {bc}},v={\texttt {a}}}$）、 そして${\displaystyle {\texttt {タクシー}}}$（と${\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進数やカントール集合のいくつかの構成に用いられる構成であり、同じ位相が得られます。

位相の文字列表現間の同型性は、辞書式最小の文字列回転に従って正規化することによって見つけることができます。