文字列 (コンピューターサイエンス)

コンピューティングにおける文字列データの図。 「example」という単語を各文字とともに個別のボックスに表示します。 上にある「文字列」という単語は、文全体を指します。 ラベル「Character」はその下にあり、個別のボックスを指します。
文字列は通常、文字で構成され、単語や文章など人間が判読できるデータを保存するためによく使用されます。

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

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

文字列がソース コード内に文字通りに現れる場合、その文字列は文字列リテラルまたは匿名文字列と呼ばれます。[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] 。

数学的システムとは、認識可能なマークの文字列のセットであり、文字列の一部が最初に取得され、マークに割り当てられた意味とは独立したルールに従って実行される演算によって残りがそこから導出されます。システムが音や匂いではなく「マーク」で構成されるべきであるということは重要ではありません。

Jean E. Sammet 氏によると、コンピュータ用の「最初の現実的な文字列処理およびパターン マッチング言語」は1950 年代のCOMITであり、次に1960 年代初頭のSNOBOL言語でした。[10]

文字列データ型

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

文字列の長さ

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

文字コード

文字列データ型は歴史的に 1 文字あたり 1 バイトを割り当ててきました。正確な文字セットは地域によって異なりますが、文字エンコーディングは十分に類似しているため、プログラムでは文字 (ピリオド、スペース、カンマなど) が特別に扱われるため、プログラマはこれを無視しても問題ないことがよくありました。 ) は、プログラムが遭遇するすべてのエンコーディングの同じ場所にありました。これらの文字セットは通常、ASCIIまたはEBCDICに基づいていました。あるエンコーディングのテキストが別のエンコーディングを使用するシステムで表示されると、テキストはしばしば文字化けしますが、多くの場合多少は読み取れるため、一部のコンピューター ユーザーは文字化けしたテキストを読めるようになりました。

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

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

実装

C++PerlRuby など の一部の言語では、通常、文字列の作成後に文字列の内容を変更できます。これらは可変文字列と呼ばれますJavaJavaScriptLuaPythonGoなどの他の言語では、値は固定されており、変更を加える場合は新しい文字列を作成する必要があります。これらは不変文字列と呼ばれます不変文字列を使用するこれらの言語の一部では、Java や.NETStringBuilderスレッドセーフ Java StringBufferCocoaなど、変更可能な別の型も提供しています。 NSMutableString不変性には長所と短所の両方があります。不変文字列では多くのコピーを非効率的に作成する必要があるかもしれませんが、不変文字列はよりシンプルで完全にスレッドセーフです。

文字列は通常、個々の単位または部分文字列 (固定長の場合は文字も含む) に高速にアクセスできるようにするために、バイト、文字、またはコード単位の配列として実装されます。Haskellなどのいくつかの言語では、代わりにリンク リストとして実装されています

PrologErlangなどの一部の言語は、専用の文字列データ型の実装をまったく避け、代わりに文字列を文字コードのリストとして表す規則を採用しています。

表現

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

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

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

ヌル終了

文字列の長さは、特別な終了文字を使用して暗黙的に保存できます。多くの場合、これはすべてのビットが 0 であるヌル文字(NUL)です。これは、一般的なC プログラミング言語で使用され、永続化されている規則です[11]したがって、この表現は一般にC 文字列と呼ばれますn文字の文字列のこの表現はn + 1 個のスペース (ターミネータの場合は 1)を必要とするため、暗黙的なデータ構造になります。

終了文字列では、終了コードはどの文字列でも使用できる文字ではありません。長さフィールドを持つ文字列にはこの制限はなく、任意のバイナリ データを格納することもできます。

8 ビット16 進数としてのASCII (またはより新しいUTF-8 ) 表現とともに、 10 バイトのバッファーに格納されたヌル終了文字列の例は次のとおりです。

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

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

バイト終端およびビット終端

文字列の終了に null 以外の特殊バイトを使用することは、歴史的にハードウェアとソフトウェアの両方で行われてきましたが、値が印刷文字でもある場合もありました。$多くのアセンブラー システムで使用され、CDCシステム (この文字の値はゼロ):で使用され、 ZX80では[12]が使用されました。これは、これが BASIC 言語の文字列区切り文字であったためです。 "

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

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

長さの接頭辞付き

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

長さが制限されている場合、定数空間 (通常はマシンワード) でエンコードできるため、n + k空間を使用する暗黙的なデータ構造になります。ここで、 kはワード内の文字数 (8 ビットの場合は 8) です。 64 ビット マシンでは ASCII、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

レコードとしての文字列

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

クラス文字列{ size_t長さ; 文字*テキスト; };  
   
   

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

その他の表現

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

これらの制限は両方とも、賢いプログラミングによって克服できます。

文字の終了に関連する問題がなく、原則としてコードの長さの限界を克服できるデータ構造とそれを操作する関数を作成することが可能です。ランレングス符号化(繰り返し文字を文字値と長さで置き換える) やハミング符号化[要説明]の技術を使用して、表現された文字列を最適化することも可能です

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

テキスト エディタの中核となるデータ構造は、編集中のファイルの現在の状態を表す文字列 (文字のシーケンス) を管理するものです。その状態は単一の長く連続した文字配列に保存できますが、一般的なテキスト エディタでは代わりにシーケンス データ構造として代替表現 (ギャップバッファ行のリンク リストピース テーブル、またはロープ)を使用します。挿入、削除、以前の編集の取り消しなどの特定の文字列操作がより効率的になります。[14]

セキュリティ上の懸念

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

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

リテラル文字列

場合によっては、人間が判読可能であり、マシンによる使用を目的としたテキスト ファイル内に文字列を埋め込む必要があります。これは、たとえばプログラミング言語のソース コードや構成ファイルで必要です。この場合、NUL 文字は通常は表示されず (印刷できず)、キーボードから入力するのが難しいため、ターミネータとしては適切に機能しません。また、文字列の長さを手動で計算して追跡するのは面倒でエラーが発生しやすいため、文字列の長さを保存することも不便です。

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

非テキスト文字列

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

C プログラマーは、定義上常に null で終了する「文字列」、別名「文字列」と、同じ配列に格納される可能性はあるが「バイト文字列」または「疑似文字列」を明確に区別します。多くの場合、null で終了しません。このような「バイト文字列」に対してC 文字列処理関数を使用すると、多くの場合、機能するように見えますが、後でセキュリティ上の問題が発生します。[15] [16] [17]

文字列処理アルゴリズム

文字列を処理するアルゴリズムは多数あり、それぞれにさまざまなトレードオフがあります。競合するアルゴリズムを実行時間、ストレージ要件などに関して分析できます。ストリング学という名前は、文字列処理に使用されるアルゴリズムとデータ構造の理論を表すために、1984 年にコンピューター科学者のZvi Galilによって造られました。[18] [19] [20]

アルゴリズムのいくつかのカテゴリには次のものがあります。

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

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

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

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

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

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

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

文字列関数

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

文字列関数の最も基本的な例は、文字列長関数です。この関数は、文字列の長さを返し (終端文字や文字列の内部構造情報はカウントしません)、文字列を変更しません。この関数には、多くの場合length、 またはという名前が付けられますlenたとえば、length("hello world")11 が返されます。もう 1 つの一般的な関数はconcatenationです。この関数では、2 つの文字列を追加することによって新しい文字列が作成されます。多くの場合、これは + 加算演算子です。

一部のマイクロプロセッサ命令セット アーキテクチャには、ブロック コピーなどの文字列操作の直接サポートが含まれています ( Intel x86m などREPNZ MOVSB)。[22]

形式理論

Σ を、アルファベットと呼ばれる有限の記号 (文字とも呼ばれる) のセットとするシンボルの性質についてはいかなる仮定も行われません。Σ 上の文字(または単語) は、Σ からの記号の有限シーケンスです。[23]たとえば、Σ = {0, 1} の場合、01011は Σ 上の文字列です。

文字列sの長さはs内のシンボルの数(シーケンスの長さ) であり、負でない任意の整数を指定できます。| として表されることがよくあります。s |。の文字列は、長さ 0 の Σ にわたる一意の文字列であり、εまたはλで表されます。[23] [24]

長さnの Σ にわたるすべての文字列のセットは、 Σ nで示されますたとえば、Σ = {0, 1} の場合、Σ 2 = {00, 01, 10, 11} となります。どのアルファベット Σ でもΣ 0 = {ε} であることに注意してください。

Σ 上の任意の長さのすべての文字列の集合はΣ のクリーン閉包であり、 Σ *と表されますΣ nに関して

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

Σ 上の文字列のセット (つまり、Σ *の任意の部分集合) は、 Σ 上の形式言語と呼ばれます。たとえば、Σ = {0, 1} の場合、偶数個のゼロを含む文字列のセット {ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, ...} は Σ 上の形式言語です。

連結と部分文字列

連結はΣ *に対する重要な二項演算ですΣ *内の 2 つの文字列sおよびtについて、それらの連結はsのシンボルのシーケンスとそれに続くtの文字のシーケンスとして定義され、 stと表されますたとえば、Σ = {a, b, ..., z}、 s  = 、およびt  =  st  = およびts  = bearhugbearhughugbear

文字列の連結は結合操作ですが、非可換操作です。空の文字列 ε は単位要素として機能します。任意の文字列sに対して、ε s = s ε = s となります。したがって、集合 Σ *と連結演算はΣ によって生成される自由モノイドであるモノイドを形成します。さらに、長さ関数は、Σ *から非負の整数までのモノイド準同型性(つまり、のような関数) を定義します。

t = usvとなる (おそらく空の) 文字列uおよびv存在する場合、文字s はtの部分文字列または因数であると言われます「の部分文字列である」という関係は、Σ * の半順序を定義しますその最小要素の文字列です

接頭辞と接尾辞

t = suとなる文字列u が存在する場合、文字列sはt接頭辞であると言われますu が空でない場合sはt適切な接頭辞であると言われます対称的に、 t = usとなるような文字列u が存在する場合、文字列s はt接尾辞であると言われますu が空でない場合sはt適切な接尾辞であると言われます。サフィックスとプレフィックスはtの部分文字列です。「の接頭辞である」と「の接尾辞である」という関係は両方とも接頭辞の順序です。

反転

文字列の反転とは、同じ記号を持つが順序が逆になった文字列のことです。たとえば、s = abc (a、b、c はアルファベットの記号) の場合、sの逆はcba になります。それ自体を逆にした文字列 (例: s = madam) は回文と呼ばれ、これには空の文字列と長さ 1 のすべての文字列も含まれます。

回転

t = vuの場合、文字列s = uvはtの回転であると言われますたとえば、Σ = {0, 1} の場合、文字列 0011001 は 0100110 の回転です。ここで、u = 00110 およびv = 01 です。別の例として、文字列 abc には 3 つの異なる回転があります。abc 自体 ( u =abc、v =ε の場合)、bca ( u =bc、v =a の場合)、および cab ( u =c、v =ab の場合)。

辞書編集上の順序付け

多くの場合、一連の文字列の順序を定義すると便利です。アルファベット Σ に全順序(アルファベット順を参照) がある場合、辞書順と呼ばれるΣ *の全順序を定義できますたとえば、Σ = {0, 1} および 0 < 1 の場合、Σ *の辞書編集順序には、ε < 0 < 00 < 000 < ... < 0001 < 001 < 01 < 010 < 011 < 0110 < の関係が含まれます。 01111 < 1 < 10 < 100 < 101 < 111 < 1111 < 11111 ... 辞書編集上の順序は、アルファベット順であれば完全ですが、自明でないアルファベットについては、たとえアルファベット順で あっても十分な根拠がありません。

十分な根拠を維持する代替の文字列順序については、 Shortlexを参照してください。

文字列操作

形式理論では、文字列に対する追加の演算が多数発生します。これらについては、文字列操作に関する記事で説明されています

トポロジー

長さ 3 のバイナリ文字列の (ハイパー) 立方体

文字列は、グラフ上のノードとして次の解釈を許可します。ここで、kは Σ 内のシンボルの数です。

固定長文字列または可変長文字列のセット上の自然なトポロジは離散トポロジですが、無限の文字列のセット上の自然なトポロジは限界トポロジであり、無限の文字列のセットを次のセットの逆極限としてます有限の文字列。これは、 p進数とカントール集合の一部の構造に使用される構造であり、同じトポロジーを生成します。

トポロジの文字列表現間の同型性は、辞書編集上の最小の文字列ローテーションに従って正規化することによって見つけることができます

こちらも参照

参考文献

  1. ^ "Java の概要 - MFC 158 G". 2016年3月3日のオリジナルからアーカイブ。文字列リテラル (または定数) は「匿名文字列」と呼ばれます
  2. ^ サンジェルマン、H. ジェームス。「ストリングス」。ユタ大学カーラート コンピューティング スクール
  3. ^ フランシス、デヴィッド M. メルク、ヘザー L. (2019 年 11 月 14 日) 「生化学的実体およびデータ列としての DNA」。
  4. ^ abc バーチフィールド、RW (1986)。"弦"。オックスフォード英語辞典の補足オックスフォード、クラレンドンプレスにて。
  5. ^ 「文字列」。オックスフォード英語辞典Vol. X. オックスフォード、クラレンドンプレスにて。1933年。
  6. ^ "文字列 (n.)". オンライン語源辞典
  7. ^ ウィリアム・ドワイト、ホイットニー; スミス、ベンジャミン E.「ストリング」。世紀の辞書ニューヨーク:センチュリーカンパニー。p. 5994。
  8. ^ “オールド・ユニオンの終焉”. ミルウォーキーセンチネル1898 年 1 月 11 日。p. 3.
  9. ^ CI、ルイス(1918)。記号論理の調査。バークレー: カリフォルニア大学出版局。p. 355.
  10. ^ ジーン・E・サメット (1972 年 7 月)。「プログラミング言語: 歴史と未来」(PDF)ACM の通信15 (7)。土井:10.1145/361454.361485。S2CID  2003242。
  11. ^ ランダル・E・ブライアント; David、O'Hallaron (2003)、Computer Systems: A Programmer's Perspective (2003 ed.)、ニュージャージー州アッパーサドルリバー: Pearson Education、p. 40、ISBN  0-13-034074-X、オリジナルから 2007 年 8 月 6 日にアーカイブ
  12. ^ ウェアマス、ジェフ。「Sinclair ZX80 ROM のアセンブリリスト」。2015年8月15日のオリジナルからアーカイブ。{{cite web}}: CS1 メイン: URL が不適切です (リンク)
  13. ^ アリソン、デニス。「Tiny BASICのデザインノート」。2017年4月10日のオリジナルからアーカイブ。
  14. ^ チャールズ・クロウリー。「テキスト シーケンスのデータ構造」 2016 年 3 月 4 日にWayback Machineにアーカイブされました。セクション「はじめに」は、2016 年 4 月 4 日にWayback Machineにアーカイブされました。
  15. ^ "strlcpy と strlcat - 一貫性があり、安全な、文字列のコピーと連結。" 2016 年 3 月 13 日にウェイバック マシンにアーカイブされました
  16. ^ "strcpy、strncpy、strlcpy についての暴言。" 2016 年 2 月 29 日にウェイバック マシンにアーカイブされました
  17. ^ キース・トンプソン。「いいえ、strncpy() は「より安全な」strcpy() ではありません。」2012年。
  18. ^ “プラハ弦楽学クラブ”. stringology.org2015 年 6 月 1 日のオリジナルからアーカイブ2015 年5 月 23 日に取得
  19. ^ エヴァーツ、ホリー (2021 年 3 月 18 日)。「元学部長ズヴィ・ガリルが過去10年間で最も影響力のあるコンピューター科学者トップ10に選出」コロンビアエンジニアリング彼は文字列アルゴリズムの下位分野である「文字列学」という用語を発明しました。
  20. ^ クロシュモア、マキシム (2002)。ストリングロジーの宝石シンガポール。p. v. ISBN 981-02-4782-6ストリングロジーという用語は、文字列アルゴリズムおよびテキスト アルゴリズムの一般的なニックネームです。{{cite book}}: CS1 メイン: 発行元の場所がありません (リンク)
  21. ^ 「Perl の基本」。2012 年 4 月 21 日のオリジナルからアーカイブされました。Perl の最も有名な強みは、正規表現を使用した文字列操作にあります。
  22. ^ "x86 文字列命令". 2015年3月27日のオリジナルからアーカイブ。
  23. ^ ab バーバラ・H・パーティ; アリス・テル・ミューレン; ロバート E. ウォール (1990)。言語学における数学的方法クルーワー。
  24. ^ ジョン E. ホップクロフト、ジェフリー D. ウルマン (1979)。オートマトンの理論、言語、計算の紹介アディソン・ウェスリー。ISBN 0-201-02988-Xここ: セクション 1.1、p.1