字串
字串（英語：string），是由零個或多個字元組成的有限序列。一般記為（）。它是程式語言中表示文字的資料型別。
通常以串的整體作為運算物件，如：在串中尋找某個子串、求取一個子串、在串的某個位置上插入一個子串以及刪除一個子串等。兩個字串相等的充要條件是：長度相等，並且各個對應位置上的字元都相等。設p、q是兩個串，求q在p中首次出現的位置的運算叫做模式匹配。串的兩種最基本的儲存方式是順序儲存方式和連結儲存方式。
形式理論
[編輯]設Σ是叫做字母表的非空有限集合。Σ的元素叫做「符號」或「字元」。在Σ上的字串（或字）是來自Σ的任何有限序列。[1]例如，如果Σ = {0, 1}，則0101是在Σ之上的字串。
字串的長度是在字串中字元的數目（序列的長度），它可以是任何非負整數。「空字串」是在Σ上的唯一的長度為0的字串，並被指示為ε或λ。[1][2]
在Σ上的所有長度為n的字串的集合指示為Σn。例如，如果Σ = {0, 1}則Σ2 = {00, 01, 10, 11}。注意Σ0 = {ε}對於任何字母表Σ。
在Σ上的所有任何長度的字串的集合是Σ的Kleene閉包並被指示為Σ*。依據Σ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,…}）是在Σ上的形式語言。
串接和子串
[編輯]「串接」（英語：concatenation）是Σ*上的重要二元運算。對於Σ*中的兩個字串s和t，它們的串接被定義為在s中的字元序列之後跟隨着t中的字元序列，並被指示為st。例如，Σ = {a, b,…, z}，並且s = bear且t = hug，則st = bearhug而ts = hugbear。
字串串接是結合性的，但非交換性運算。空字串充當單位元；對於任何字串s，有εs = sε = s。所以，集合Σ*和串接運算形成了么半群，就是從Σ生成的自由么半群。此外，長度函數定義了一個從Σ*到非負整數的么半群同態。
字串s被稱為是字串t的「子串」（英語：substring）或「因子」（英語：factor），如果存在（可能為空）字串u和v使得t = usv。「是其子串」關係定義了在Σ*上的偏序，其最小元是空字串。
詞典排序
[編輯]經常需要定義在字串集合上的次序。如果字元表Σ有一個全序（cf. 字母序），則可以定義在Σ*上的叫做詞典序的全序。注意因為Σ是有限的，總是可以定義在Σ繼而在Σ*上的良好次序。例如，如果Σ = {0, 1}並且0 < 1，則Σ*的詞典次序是ε < 0 < 00 < 000 <…< 011 < 0110 <…< 01111 <…< 1 < 10 < 100 <…< 101 <…< 111…
字串運算
[編輯]在形式理論中經常出現一些在字串上的額外運算。它們在條目字串運算中給出。
字串資料類型
[編輯]字串資料類型是建模在形式字串的想法上的資料類型（Data type）。字串是幾乎在所有程式語言中都可以實現的非常重要和有用的資料類型。在某些語言中它們可作為基本類型獲得，在另一些語言中做為複合類型獲得。多數高階語言的語法允許用某種方式參照起來的字串來表示字串資料類型的實例；這種元字串叫做「常值」（英語：literal）或「字串常值」（英語：string literal）。
字串長度
[編輯]儘管形式字串可以有任意（但有限）的長度，實際語言的字串的長度經常被限制到一個人工極大值。一般的說，有兩種類型的字串資料類型：「定長字串」，它有固定的極大長度並且不管是否達到了這個極大值都使用同樣數量的主記憶體；和「變長字串」，它的長度不是專斷固定的並且依賴於實際的大小使用可變數量的主記憶體。在現代程式語言中的多數字串是變長字串。儘管叫這個名字，所有變長字串還是在長度上有個極限，一般的說這個極限只依賴於可獲得的主記憶體的數量。
字元編碼
[編輯]歷史上，字串資料類型為每個字元分配一個位元組，儘管精確的字元集隨着區域而改變，字元編碼足夠類似得程式設計師可以忽略它—同一個系統在不同的區域中使用的字元集組要麼讓一個字元在同樣位置，要麼根本就沒有它。這些字元集典型的基於ASCII碼或EBCDIC碼。
意音文字的語言比如漢語、日語和韓語（合稱為CJK）的合理表示需要多於256個字元（每字元一個位元組編碼的極限）。常規的解決涉及：保持對ASCII碼的單位元組表示，並使用雙位元組來表示CJK字形。現存代碼在用到它們會導致一些字串匹配和切斷上的問題，嚴重程度依賴於字元編碼是如何設計的。
- 某些編碼比如EUC家族保證在ASCII碼範圍內的位元組值只表示ASCII字元，使得使用這些字元作為欄位分隔符的系統得到編碼安全。其他編碼如ISO-2022和Shift-JIS不做這種擔保，使得基於位元組的代碼做的匹配不安全。
- 另一個問題是如果一個字串的開頭被刪除了，對解碼器的重要指示或關於在多位元組序列中的位置的資訊可能就遺失了。
- 另一個問題是如果字串被連接到一起（特別是在被不知道這個編碼的代碼截斷了它們的結尾之後），第一個字串可能不能導致編碼器進入適合處理第二個字串的狀態中。
Unicode也有些複雜的問題。多數語言有Unicode字串資料類型（通常是UTF-16，因為它在Unicode補充位面介入之前就被增加了）。在Unicode和本地編碼之間轉換要求理解本地編碼，這對於現存系統要一起傳輸各種編碼的字串而又沒有實際標記出它們用了什麼編碼就是個問題。
實現
[編輯]某些語言如C++把字串實現為可以用於任何基本類型的模版，但這是個例外而不是規則。
在一個物件導向語言把字串表示為對象的情況下，如果值可以在執行期變更，則叫做「可變的」（mutable），如果值在建立後就不可變更了，則叫做「不變的」（immutable）。例如，Ruby有可變字串，而Python的字串是不可變的。
其他語言，最著名的有Prolog和Erlang，避免實現字串資料類型，轉而採用把字串表示為字元代碼的列表的約定。
表示法
[編輯]一種常用的表示法是使用一個字元代碼的陣列，每個字元佔用一個位元組（如在ASCII代碼中）或兩個位元組（如在unicode中）。它的長度可以使用一個結束符（一般是NUL，ASCII代碼是0，在C程式語言中使用這種方法）。[3]或者在前面加入一個整數值來表示它的長度（在Pascal語言中使用這種方法）。
這是一個用NUL結束的字串的例子，它用10個byte儲存，用ASCII表示法：
| F | R | A | N | K | NUL | k | e | f | w |
| 46 | 52 | 41 | 4E | 4B | 00 | 6B | 66 | 66 | 77 |
上面的字串的長度為5個字元，但注意它佔用6個位元組。結束符後的字元沒有任何意義。
這是相同的Pascal字串：
| length | F | R | A | N | K | k | e | f | w |
| 05 | 46 | 52 | 41 | 4E | 4B | 6B | 66 | 66 | 77 |
當然，可能還有其它的表示法。使用樹和列表可以使得一些字串操作（如插入和刪除）更高效。
字串實用程式
[編輯]一些程式語言設計為編寫字串處理程式更容易編寫。這是一些例子：
很多UNIX實用程式進行簡單的字串處理，並能用於簡單地編寫一些強大的字串處理演算法。檔案和有限流可以像字串一樣檢視。
一些新的程式語言，包括Perl、Python和Ruby，藉助正則表達式來幫助文書處理。
演算法
[編輯]這是一些字串處理演算法，在字串上進行不同的處理：
參見
[編輯]參考資料
[編輯]- ^ 1.0 1.1 Barbara H. Partee; Alice ter Meulen; Robert E. Wall. Mathematical Methods in Linguistics. Kluwer. 1990.
- ^ John E. Hopcroft, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. 1979. ISBN 0-201-02988-X. Here: sect.1.1, p.1
- ^ Bryant, Randal E.; David, O'Hallaron, Computer Systems: A Programmer's Perspective 2003, Upper Saddle River, NJ: Pearson Education: 40, 2003 [2019-04-15], ISBN 0-13-034074-X, （原始內容存檔於2007-08-06）