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

文字列は通常、文字で構成され、単語や文章など、人間が読めるデータを格納するためによく使用されます。

コンピュータプログラミングにおいて、文字列は伝統的に文字のシーケンスであり、リテラル定数または何らかの変数として表されます。後者は、要素を変更して長さを変更できる場合もあれば、（作成後に）固定される場合もあります。文字列は多くの場合、バイト（またはワード）の配列データ構造として実装され、文字エンコーディングを使用して、通常は文字のシーケンスを格納する要素シーケンスが格納されます。より一般的には、文字列は文字以外のデータの シーケンス（またはリスト）を表すこともあります。

プログラミング言語と使用される正確なデータ型に応じて、文字列として宣言された変数は、メモリ内のストレージを事前に決定された最大長に対して静的に割り当てるか、または動的割り当てを使用して可変数の要素を保持できるようにします。

文字列がソースコード内に文字通り現れる場合、それは文字列リテラルまたは匿名文字列と呼ばれます。^{[ 1 ]}

数理論理学や理論計算機科学で使用される形式言語では、文字列はアルファベットと呼ばれる集合から選択された記号の有限の列です。

目的

文字列の主な目的は、単語や文など、人間が読めるテキストを格納することです。文字列は、コンピュータプログラムからそのプログラムのユーザーに情報を伝達するために使用されます。^{[ 2 ]}プログラムは、ユーザーから文字列入力を受け取ることもあります。さらに、文字列には、人間が読むことを想定していない文字で表現されたデータを格納することもあります。

文字列の例とその目的:

• 「 」のようなメッセージは、ソフトウェアがエンドユーザーfile upload completeに対して表示する文字列です。プログラムのソースコードでは、このメッセージは文字列リテラルとして表示される可能性があります。
• ソーシャルメディアI got a new job todayサービスのステータス更新における「 」のような、ユーザーが入力したテキスト。ソフトウェアは文字列リテラルではなく、この文字列をデータベースに保存する可能性が高いでしょう。
• DNAAGATGCCGTの核酸配列を表す「 」のようなアルファベット順のデータ。^{[ 3 ]}
• コンピュータの設定やパラメータ（?action=editURLクエリ文字列としての「 」など）。これらは、コンピュータとの通信を主な目的としていますが、人間がある程度判読できるように意図されていることがよくあります。

文字列という用語は、「ビット列」のように文字以外のデータやコンピュータ記録のシーケンスを指すこともありますが、修飾なしで使用される場合は文字列を指します。^{[ 4 ]}

歴史

「ストリング」という言葉が、一列、一連、または連続して並べられたものを指すのに使われるようになったのは、何世紀も前のことです。^{[ 5 ] [ 6 ]} 19世紀の植字工は、紙に印刷された活字の長さを表すのに「ストリング」という用語を使用していました。そして、そのストリングの長さを測ることで植字工の報酬が決まりました。^{[ 7 ] [ 4 ] [ 8 ]}

「文字列」という言葉が「一定の順序で並んだ記号や言語要素の列」という意味で使われるようになったのは、数学、記号論理学、言語理論の分野から、記号の意味を脇に置いて記号システムの形式的な振る舞いについて語るときに使われるようになったためである。 ^{[ 4 ]}

例えば、論理学者CIルイスは1918年に次のように書いています。^{[ 9 ]}

数学体系とは、認識可能な記号列の集合であり、その一部の列は最初に取り出され、残りの列は記号に割り当てられた意味とは無関係な規則に従って実行される演算によって導き出される。体系が音や匂いではなく「記号」で構成されるかどうかは重要ではない。

ジーン・E・サメットによれば、コンピュータのための「最初の現実的な文字列処理およびパターンマッチング言語」は1950年代のCOMITであり、その後1960年代初頭にSNOBOL言語が登場した。 ^{[ 10 ]}

文字列データ型

文字列データ型は、形式的な文字列の概念に基づいてモデル化されたデータ型です。文字列は非常に重要かつ有用なデータ型であるため、ほぼすべてのプログラミング言語で実装されています。言語によってはプリミティブ型として、また他の言語では複合型として使用できます。ほとんどの高水準プログラミング言語の構文では、通常は何らかの方法で引用符で囲まれた文字列を使用して、文字列データ型のインスタンスを表すことができます。このようなメタ文字列は、リテラルまたは文字列リテラルと呼ばれます。

文字列の長さ

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

文字エンコーディング

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

中国語、日本語、韓国語などの表意文字言語（総称してCJK）は、適切な表現のために256文字（1文字あたり8ビット1バイトのエンコーディングの限界）をはるかに超える文字数を必要とします。通常の解決策としては、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のStringBuilder、スレッドセーフな Java StringBuffer、Cocoa など、別の可変型も提供しています。不変性には利点と欠点があります。不変文字列では、効率的に多数のコピーを作成する必要がある場合がありますが、より単純で完全にスレッドセーフNSMutableStringです。

文字列は通常、バイト、文字、またはコード単位の配列として実装され、個々の単位または部分文字列（固定長の文字を含む）への高速アクセスを可能にします。Haskellなどの一部の言語では、文字列をリンクリストとして実装しています。

多くの高水準言語では、JavaScriptやPHPなど、文字列をプリミティブ データ型として提供しています。一方、他のほとんどの言語では、文字列を複合データ型として提供しています。JavaやC#など一部の言語では、リテラルの記述に特別な言語サポートが備わっています。

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

表現

文字列の表現は、文字レパートリーの選択と文字エンコーディング方式に大きく依存します。古い文字列実装は、ASCII、あるいはISO 8859シリーズのような最近の拡張で定義されたレパートリーとエンコーディングで動作するように設計されていました。最近の実装では、Unicodeで定義された広範なレパートリーに加えて、UTF-8やUTF-16といった様々な複雑なエンコーディングが使用されることがよくあります。

バイト文字列という用語は通常、（読み取り可能な）文字のみの文字列やビット列などではなく、汎用的なバイト文字列を指します。バイト文字列は、バイトが任意の値をとることができ、任意のデータをそのまま保存できることを意味する場合が多く、つまり終端値として解釈される値が存在しないことを意味します。

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

ドープベクトル

文字列の長さは、実際の文字を格納する記憶領域とは別のドープベクトルに格納できます。IBM PL/I (F) コンパイラは、可変長文字列と文字列パラメータの受け渡しに文字列ドープベクトル^{[ 11 ]} (SDV) を使用していました。SDVは現在の長さと最大長を保持し、文字列本体とは隣接していません。PL/I (F) 以降、IBMはSDVを廃止し、長さプレフィックス付き文字列を採用しました。

ヌル終端

文字列の長さは、特殊な終端文字を用いることで暗黙的に保存することができます。多くの場合、これはすべてのビットがゼロであるヌル文字（NUL）であり、これは人気のCプログラミング言語で使用され、定着している慣習です。^{[ 12 ]}そのため、この表現は一般的にC文字列と呼ばれます。n文字の文字列のこの表現はn + 1個の空間（1個は終端文字）を占有するため、暗黙的なデータ構造となります。

終端文字列では、終端コードはどの文字列でも許可されません。長さフィールドを持つ文字列にはこの制限はなく、任意のバイナリデータを格納できます。

10 バイトのバッファに格納されたNULL 終端文字列と、そのASCII (またはより新しいUTF-8 ) 表現を 8 ビットの 16進数として示す例を次に示します。

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

上記の例の文字列「FRANK」の長さは5文字ですが、6バイトを占有します。終端文字の後の文字は表現の一部ではなく、他のデータの一部であるか、単なるゴミである可能性があります。（この形式の文字列は、宣言に使用された元のアセンブリ言語ディレクティブにちなんで、ASCIZ文字列と呼ばれることがあります。）

バイトおよびビット終端

文字列を終了するためにヌル以外の特別なバイトを使用することは、歴史的にはハードウェア^{[ a ]}とソフトウェアの両方で見られましたが、その値が印刷文字でもある場合もありました。$は多くのアセンブラシステムで使用され、CDC:システムで使用され（この文字の値はゼロでした）、ZX80では^{[ 15 ]}が使用されました。これは、これがBASIC言語の文字列区切り文字であったためです。 "

これに似たIBM 1401のような「データ処理」マシンでは、文字列の左側を区切るために特別なワードマークビットを使用し、右側から演算が開始されます。このビットは文字列の他の部分ではクリアである必要がありました。つまり、IBM 1401には7ビットワードがありましたが、これを機能として利用し、7番目のビットの割り当てをオーバーライドして（例えば）ASCIIコードを処理することを考えた人はほとんどいませんでした。

初期のマイクロコンピュータソフトウェアは、ASCIIコードが上位ビットを使用しないという事実を利用し、文字列の終了を示すために上位ビットを設定していました。出力前に0にリセットする必要があります。^{[ 16 ]}

長さプレフィックス付き

文字列の長さは、例えば文字列の先頭にバイト値として長さを付加するなどして明示的に格納することもできます。この規則は多くのPascal方言で使用されており、そのため、このような文字列はPascal文字列またはP文字列と呼ばれることもあります。文字列の長さをバイトとして格納すると、最大文字列長が255に制限されます。このような制限を回避するために、P文字列の改良された実装では、16ビット、32ビット、または64ビットのワードを使用して文字列の長さを格納します。長さフィールドがアドレス空間をカバーする場合、文字列は利用可能なメモリによってのみ制限されます。

長さが制限されている場合、通常はマシンワードである定数スペースにエンコードできるため、暗黙のデータ構造が生成され、n + kスペースが必要になります。ここで、kはワード内の文字数です (64 ビットマシン上の 8 ビット ASCII の場合は 8、32 ビットマシン上の 32 ビット UTF-32/UCS-4 の場合は 1 など)。長さが制限されていない場合、長さ n をエンコードするとlog ( n ) スペースが必要になります (固定長コードを参照)。そのため、長さプレフィックス付き文字列は簡潔なデータ構造となり、長さnの文字列を log( n ) + nスペースでエンコードします。

後者の場合、長さプレフィックス フィールド自体は固定長ではないため、文字列が長くなって長さフィールドを増やす必要がある場合は、実際の文字列データを移動する必要があります。

以下は、10 バイトのバッファに格納された Pascal 文字列とその ASCII / UTF-8 表現です。

長さ	F	R	A	N	K	k	e	f	w
05 16	46 16	52 16	41 16	4E 16	4B 16	6B 16	65 16	66 16	77 16

レコードとしての文字列

オブジェクト指向言語を含む多くの言語では、次のような内部構造を持つ レコードとして文字列を実装します。

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

ただし、実装は通常は隠蔽されているため、文字列へのアクセスと変更はメンバー関数を介して行う必要があります。textは動的に割り当てられたメモリ領域へのポインタであり、必要に応じて拡張される可能性があります。文字列（C++）も参照してください。

その他の表現

文字終了コードと長さコードはどちらも文字列を制限します。たとえば、ヌル (NUL) 文字を含む C 文字配列は、C 文字列ライブラリ関数では直接処理できません。長さコードを使用する文字列は、長さコードの最大値に制限されます。

これら両方の制限は、巧みなプログラミングによって克服できます。

文字終端に伴う問題を回避し、原理的には長さコードの限界を克服できるデータ構造と、それらを操作する関数を作成することは可能です。また、ランレングス符号化（繰り返し文字を文字値と長さで置き換える）やハミング符号化の手法を用いて、表現された文字列を最適化することも可能になります。

これらの表現は一般的ですが、他にも可能です。ロープを使用すると、挿入、削除、連結などの特定の文字列操作がより効率的になります。

テキストエディタのコアデータ構造は、編集中のファイルの現在の状態を表す文字列（文字のシーケンス）を管理するものです。この状態は単一の長い連続した文字配列に格納することもできますが、一般的なテキストエディタでは、代わりにギャップバッファ、行のリンクリスト、ピーステーブル、ロープといった代替表現をシーケンスデータ構造として用い、挿入、削除、以前の編集の取り消しといった特定の文字列操作をより効率的に実行します。^{[ 17 ]}

セキュリティ上の懸念

文字列のメモリレイアウトとストレージ要件の違いは、文字列データにアクセスするプログラムのセキュリティに影響を与える可能性があります。終端文字を必要とする文字列表現は、コーディングエラーや攻撃者による意図的なデータ改ざんなどにより終端文字が存在しない場合、バッファオーバーフローの問題が発生する可能性が高くなります。また、独立した長さフィールドを採用した文字列表現も、長さを操作できる場合、影響を受けやすくなります。このような場合、文字列データにアクセスするプログラムコードでは、文字列のメモリ制限を超えるデータに誤ってアクセスしたり変更したりしないよう、境界チェックを行う必要があります。

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

リテラル文字列

場合によっては、文字列を人間が読める形式でありながら、機械による処理も想定したテキストファイルに埋め込む必要があります。例えば、プログラミング言語のソースコードや設定ファイルなどがこれに該当します。この場合、NUL文字は通常は表示されず（印刷もできない）、キーボードからの入力も難しいため、終端文字としてはあまり機能しません。また、文字列の長さを保存しておくことも不便です。手動で文字列の長さを計算して追跡するのは面倒で、間違いが発生しやすいからです。

一般的な表現は次の 2 つです。

• ほとんどのプログラミング言語で使用される引用符（ASCII 0x22二重引用符"str"または ASCII 0x27 一重引用符）で囲まれます'str'。引用符自体、改行文字、印刷できない文字などの特殊文字を含めるには、エスケープシーケンスが使用されることが多く、通常はバックスラッシュ文字（ASCII 0x5C）を先頭に付けます。
• Windows INI ファイルなどでは改行シーケンスによって終了します。

非テキスト文字列

文字列は文字列の非常に一般的な用途ですが、コンピュータサイエンスにおける文字列は、一般的に均一な型を持つデータのシーケンスを指す場合があります。例えば、ビット文字列やバイト文字列は、通信媒体から取得した非テキストバイナリデータを表すために使用される場合があります。このデータは、アプリケーションのニーズ、プログラマの希望、および使用するプログラミング言語の機能に応じて、文字列固有のデータ型で表現される場合とされない場合があります。プログラミング言語の文字列実装が8ビットクリーンでない場合、データ破損が発生する可能性があります。

C言語のプログラマーは、「文字列」（つまり「文字の列」）と「文字の配列」（同じ配列に格納されることもあるが、多くの場合はNULLで終端されない）を明確に区別しています。このような文字の配列に対してC言語の文字列処理関数を使用すると、一見うまく動作するように見えますが、後々セキュリティ上の問題につながることがあります。^{[ 18 ] [ 19 ] [ 20 ]}

文字列処理アルゴリズム

文字列処理には多くのアルゴリズムがあり、それぞれに様々なトレードオフがあります。競合するアルゴリズムは、実行時間、必要なストレージ容量などの観点から分析できます。文字列学（stringology）という名称は、1984年にコンピュータ科学者のズヴィ・ガリルによって、文字列処理に用いられるアルゴリズムとデータ構造の理論にちなんで名付けられました。^{[ 21 ] [ 22 ] [ 23 ]}

アルゴリズムのカテゴリには次のようなものがあります。

• 特定の部分文字列またはパターンを見つけるための文字列検索アルゴリズム
• 文字列操作アルゴリズム
• ソートアルゴリズム
• 正規表現アルゴリズム
• 文字列の解析
• シーケンスマイニング

高度な文字列アルゴリズムでは、サフィックス ツリーや有限状態マシンなどの複雑なメカニズムとデータ構造が採用されることが多いです。

文字列指向言語とユーティリティ

文字列は非常に便利なデータ型であるため、文字列処理アプリケーションを容易に作成できるようにするために、いくつかの言語が設計されています。例としては、以下の言語が挙げられます。

• AWK
• アイコン
• おたふく風邪
• パール
• レックス
• ルビー
• sed
• スノボル
• Tcl
• TTM

多くのUnixユーティリティは単純な文字列操作を行うため、強力な文字列処理アルゴリズムを簡単にプログラムすることができます。ファイルや有限ストリームも文字列として扱うことができます。

マルチメディア コントロール インターフェイス、埋め込み SQL、printfなどの一部のAPIでは、解釈されるコマンドを保持するために文字列が使用されます。

Perl、Python、Ruby、Tclなど、多くのスクリプトプログラミング言語は、テキスト操作を容易にするために正規表現を採用しています。Perlは特に正規表現の使用で知られており、^{[ 24 ]}他の多くの言語やアプリケーションもPerl互換の正規表現を実装しています。

Perl や Ruby などの一部の言語では文字列補間がサポートされており、任意の式を評価して文字列リテラルに含めることができます。

文字列関数

文字列関数は、文字列を作成したり、変更可能な文字列の内容を変更したりするために使用されます。また、文字列に関する情報を照会するためにも使用されます。関数のセットとその名前は、コンピュータプログラミング言語によって異なります。

文字列関数の最も基本的な例は、文字列長関数です。これは文字列の長さ（終端文字や文字列の内部構造情報は含みません）を返す関数で、文字列自体を変更することはありません。この関数はlength、len、 、 などと呼ばれることがよくありますsize。例えば、length("hello world")は11を返します。もう一つの一般的な関数は連結関数です。これは2つの文字列を連結することで新しい文字列を作成するもので、通常は + 加算演算子を使用します。

一部のマイクロプロセッサの命令セットアーキテクチャには、ブロックコピーなどの文字列操作を直接サポートする機能が含まれています（例：Intel x86mREPNZ MOVSB）。^{[ 25 ]}

形式理論

を、アルファベットと呼ばれる、明確に区別できる記号（文字とも呼ばれる）の有限集合とする。上の文字列（または単語^{[ 26 ]}、式^{[ 27 ]}）は、からの任意の有限の記号列である。^{[ 28 ]}例えば、 ならば、は 上の文字列である。 ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma =\{{\texttt {0}},{\texttt {1}}\}}$ ${\displaystyle {\texttt {01011}}}$ ${\displaystyle \Sigma }$

文字列の長さは、（シーケンスの長さ）に含まれる記号の数であり、任意の非負整数で表されます。これは と表記されることが多いです。空文字列は長さ を超える唯一の文字列であり、または と表記されます。^{[ 28 ] [ 29 ]}${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle |s|}$ ${\displaystyle \Sigma }$ ${\displaystyle 0}$ ${\displaystyle \varepsilon }$ ${\displaystyle \lambda}$

長さ以上の文字列全体の集合は と表記されます。例えば の場合、 となります。すべてのアルファベット に対してが成り立ちます。 ${\displaystyle \Sigma }$ ${\displaystyle n}$ ${\displaystyle \Sigma ^{n}}$ ${\displaystyle \Sigma =\{{\texttt {0}},{\texttt {1}}\}}$ ${\displaystyle \Sigma ^{2}=\{{\texttt {00}},{\texttt {01}},{\texttt {10}},{\texttt {11}}\}}$ ${\displaystyle \Sigma ^{0}=\{\varepsilon \}}$ ${\displaystyle \Sigma }$

任意の長さの上のすべての弦の集合はのクリーネ閉包であり、 と表記される。 に関して、 ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma^{*}}$ ${\displaystyle \Sigma ^{n}}$

${\displaystyle \Sigma^{*}=\bigcup_{n=0}^{\infty}\Sigma^{n}}$

たとえば、の場合にはとなります。集合自体は可算無限ですが、 の各要素は有限の長さの文字列です。 ${\displaystyle \Sigma =\{{\texttt {0}},{\texttt {1}}\}}$ ${\displaystyle \Sigma ^{*}=\{\varepsilon ,{\texttt {0}},{\texttt {1}},{\texttt {00}},{\texttt {01}},{\texttt {10}},{\texttt {11}},{\texttt {000}},{\texttt {001}},{\texttt {010}},{\texttt {011}},...\}}$ ${\displaystyle \Sigma^{*}}$ ${\displaystyle \Sigma^{*}}$

（つまり の任意の部分集合）上の文字列の集合は上の形式言語と呼ばれます。例えば の場合、偶数個のゼロを含む文字列の集合は 上の形式言語です。 ${\displaystyle \Sigma }$ ${\displaystyle \Sigma^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma =\{{\texttt {0}},{\texttt {1}}\}}$ ${\displaystyle \{\varepsilon ,{\texttt {1}},{\texttt {00}},{\texttt {11}},{\texttt {001}},{\texttt {010}},{\texttt {100}},{\texttt {111}},{\texttt {0000}},{\texttt {0011}},{\texttt {0101}},{\texttt {0110}},{\texttt {1001}},{\texttt {1010}},{\texttt {1100}},{\texttt {1111}},...\}}$ ${\displaystyle \Sigma }$

連結と部分文字列

連結はにおける重要な二項演算です。内の任意の2つの文字列と、それらの連結は 内の記号の列に 内の文字の列を続けたもの、 と表記されます。例えば、 （つまり英語の小文字）、、 の場合、 およびとなります。 ${\displaystyle \Sigma^{*}}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle \Sigma^{*}}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle st}$ ${\displaystyle \Sigma =\{{\texttt {a}},{\texttt {b}},...,{\texttt {z}}\}}$ ${\displaystyle s={\texttt {クマ}}}$ ${\displaystyle t={\texttt {ハグ}}}$ ${\displaystyle st={\texttt {ベアハグ}}}$ ${\displaystyle ts={\texttt {ハグベア}}}$

文字列の連結は結合的だが非可換な演算である。空文字列は単位元として機能し、任意の文字列 に対してとなる。したがって、集合と連結演算はモノイド、つまり によって生成される自由モノイドを形成する。さらに、長さ関数はから非負整数 へのモノイド準同型性（つまりとなる関数）を定義する。 ${\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 s}$ ${\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 {マダム}}}$ ${\displaystyle 1}$

回転

文字列が の回転であるとは、の回転のことです。例えば、文字列が の回転である場合、 およびとなります。別の例として、文字列には3つの異なる回転、すなわち、文字列自体の回転（ 、 の場合）、（ の場合）、（ の場合）があります。 ${\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}}}$ ${\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}}$ ${\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 3}$

文字列はグラフ上のノードとして次のように解釈できます。ここで、は 内のシンボルの数です。 ${\displaystyle k}$ ${\displaystyle \Sigma }$

• 長さ の固定長文字列は、長さ の辺を持つ次元ハイパーキューブ内の整数位置として見ることができます。${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle k-1}$
• 可変長文字列 (有限長) は、完全な-ary ツリー${\displaystyle k}$ 上のノードとして見ることができます。
• 無限文字列(ここでは考慮されません) は、 -ノード完全グラフ上の無限パスとして表示できます。${\displaystyle k}$

固定長文字列または可変長文字列の集合上の自然な位相は離散位相であるが、無限文字列の集合上の自然な位相は極限位相であり、これは無限文字列の集合を有限文字列の集合の逆極限と見なすものである。これはp進数やカントール集合のいくつかの構成に用いられる構成であり、同じ位相を与える。

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

参照

• バイナリセーフ— 入力を生のデータストリームとして扱う文字列操作関数の特性
• ビット配列— 2進数の文字列
• C 文字列処理— C 文字列処理の概要
• C++ 文字列処理— C++ 文字列処理の概要
• プログラミング言語の比較（文字列関数）
• 接続文字列- 接続を開始するためにドライバーに渡されます（例：データベースへの接続）
• 空文字列— その特性とプログラミング言語における表現
• 圧縮不可能な文字列— いかなるアルゴリズムでも圧縮できない文字列
• ロープ（データ構造） —長い文字列を効率的に操作するためのデータ構造
• 文字列インターン- 不変である必要がある各異なる文字列値のコピーを 1 つだけ保存する方法。
• 文字列メトリック— 文字列間の類似性の概念

説明ノート

1. 例えば、 RCA 501アイテム転送（IT）命令^{[ 13 ]}はアイテムセパレータシンボル（ISS）を使用し、 RCA 301シンボル位置特定（LSL、LSR）、シンボルによるデータ転送（DSL、DSR）、およびシンボル転送によるフィル（SF）命令^{[ 14 ]}は命令内で文字を使用します。

参考文献

1. 「Java入門 – MFC 158 G」。2016年3月3日時点のオリジナルよりアーカイブ。文字列リテラル（または定数）は「匿名文字列」と呼ばれます。
2. de St. Germain, H. James. 「Strings」ユタ大学カーラートコンピューティングスクール.
3. フランシス、デイビッド・M.; メルク、ヘザー・L. (2019年11月14日). 「生化学的実体およびデータ文字列としてのDNA」 .
4. Burchfield, RW (1986). 「string」.オックスフォード英語辞典補遺. オックスフォード社、クラレンドン・プレス.
5. "string".オックスフォード英語辞典. 第10巻. オックスフォード社（クラレンドン出版）. 1933年.
6. 「string (n.)」オンライン語源辞典。
7. ホイットニー、ウィリアム・ドワイト；スミス、ベンジャミン・E.「string」。センチュリー辞典。ニューヨーク：センチュリー・カンパニー。p. 5994。
8. 「オールド・ユニオンの終焉」ミルウォーキー・センチネル、1898年1月11日、3ページ。
9. Lewis, CI (1918). 『記号論理学概論』 バークレー: カリフォルニア大学出版局. p. 355.
10. Sammet, Jean E. (1972年7月). 「プログラミング言語：歴史と未来」(PDF) . Communications of the ACM . 15 (7). doi : 10.1145/361454.361485 . S2CID 2003242 . 
11. 「文字列データ」（PDF） . IBM System/360 オペレーティング・システム - PL/I (F) - プログラマーズ・ガイド - プログラム番号 360S-NL-5ll（PDF） . システム・リファレンス・ライブラリー（第5版）. 1968年11月. p. 136. C28-6594-4 . 2025年9月2日閲覧.可変長データには、「ドープ・ベクター」と呼ばれる制御領域が関連付けられており、文字列を記述します。ドープ・ベクターには、文字列の最大長と現在の長さの記録と、文字列の先頭へのポインターが含まれます。ドープ・ベクターは、記述するデータに隣接している必要はありませんが、通常は同じストレージ・クラスのストレージを占有します。
12. ブライアント、ランダル E. ; デビッド、オハラロン (2003)、『コンピュータシステム：プログラマの視点』（2003年版）、アッパーサドルリバー、ニュージャージー：ピアソンエデュケーション、p. 40、ISBN 0-13-034074-X、2007年8月6日にオリジナルからアーカイブ
13. 「RCA 501 説明書」（PDF） . RCA 501 電子データ処理システム - プログラマーズ・リファレンス・マニュアル（PDF） . Radio Corporation of America . 1958年. p.  35. P501-2 . 2025年11月18日閲覧。
14. 「RCA 301命令 - 概要」（PDF） . RCA 301電子データ処理システム - プログラマーズ・リファレンス・マニュアル（PDF） . Radio Corporation of America . 1962年1月. pp.  33-44 . 93-17-000 . 2025年11月18日閲覧。
15. Wearmouth, Geoff. 「Sinclair ZX80のROMのアセンブリリスト」。2015年8月15日時点のオリジナルよりアーカイブ。
16. Allison, Dennis. 「Tiny BASICの設計ノート」。2017年4月10日時点のオリジナルよりアーカイブ。
17. Charles Crowley. 「テキストシーケンスのデータ構造」Wayback Machineで2016年3月4日にアーカイブ。セクション 「はじめに」Wayback Machineで2016年4月4日にアーカイブ。
18. 「strlcpyとstrlcat - 一貫性があり安全な文字列のコピーと連結」Wayback Machineに2016年3月13日アーカイブ
19. 「strcpy、strncpy、strlcpyについての愚痴」 2016年2月29日アーカイブ、Wayback Machine
20. Keith Thompson. 「いいえ、strncpy() は「より安全な」strcpy() ではありません」。2012年。
21. 「プラハ・ストリングロジー・クラブ」stringology.org . 2015年6月1日時点のオリジナルよりアーカイブ。2015年5月23日閲覧。
22. Evarts, Holly (2021年3月18日). 「元学部長Zvi Galil氏が過去10年間で最も影響力のあるコンピュータ科学者トップ10に選出」 .コロンビア工科大学.彼は文字列アルゴリズムのサブフィールドである「ストリングロジー（stringology）」という用語を考案した。
23. クロシュモア、マキシム（2002年）『弦学の宝石』シンガポール、p.v. ISBN 981-02-4782-6ストリングロジーという用語は、文字列アルゴリズムだけでなくテキスト アルゴリズムに対しても一般的に使われる愛称です。
24. 「Essential Perl」。2012年4月21日時点のオリジナルよりアーカイブ。Perlの最も有名な強みは、正規表現を使った文字列操作です。
25. 「x86 文字列命令」。2015年3月27日時点のオリジナルよりアーカイブ。
26. フレッチャー, ピーター; ホイル, ヒューズ; パティ, C. ウェイン (1991). 『離散数学の基礎』 PWS-Kent. p. 114. ISBN 0-53492-373-9Σをアルファベットとする。Σ上の空でない単語は、定義域I _n（任意のn∈ℕに対して）と余定義域Σを持つ有限列である。
27. ショーンフィールド、ジョセフ・R. (2010) [1967].数学論理学（復刻版）. CRC Press. p. 2. ISBN 978-156881135-2ある言語の記号の有限の列は、その言語の表現と呼ばれます。
28. Barbara H. Partee; Alice ter Meulen ; Robert E. Wall (1990). Mathematical Methods in Linguistics . Kluwer.
29. ジョン・E・ホップクロフト、ジェフリー・D・ウルマン (1979). 『オートマトン理論、言語、計算入門』アディソン・ウェズレー. ISBN 0-201-02988-X。ここ: sect.1.1、p.1