字符串

✍ dations ◷ 2025-07-08 09:34:51 #电脑术语,数据结构,形式语言,字符编码

字符串(英语:string),是由零个或多个字符组成的有限序列。一般记为 s = a 1 a 2 a n {\displaystyle s=a_{1}a_{2}\dots a_{n}} 是在Σ之上的字符串。

字符串的长度是在字符串中字符的数目(序列的长度),它可以是任何非负整数。“空串”是在Σ上的唯一的长度为0的字符串,并被指示为或。

在Σ上的所有长度为的字符串的集合指示为Σ。例如,如果Σ = {0, 1}则Σ2 = {00, 01, 10, 11}。注意Σ0 = {ε}对于任何字母表Σ。

在Σ上的所有任何长度的字符串的集合是Σ的Kleene闭包并被指示为Σ*。依据Σ,

例如,如果Σ = {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,…})是在Σ上的形式语言。

“串接”(英语:)是Σ*上的重要二元运算。对于Σ*中的两个字符串和,它们的串接被定义为在中的字符序列之后跟随着中的字符序列,并被指示为。例如,Σ = {a, b,…, z},并且 = bear且 = hug,则 = bearhug而 = hugbear

字符串串接是结合性的,但非交换性运算。空串充当单比特;对于任何字符串,有ε = ε = 。所以,集合Σ*和串接运算形成了幺半群,就是从Σ生成的自由幺半群。此外,长度函数定义了一个从Σ*到非负整数的幺半群同态。

字符串被称为是字符串的“子串”(英语:)或“因子”(英语:),如果存在(可能为空)字符串和使得 = 。“是其子串”关系定义了在Σ*上的偏序,其最小元是空串。

经常需要定义在字符串集合上的次序。如果字符表Σ有一个全序(cf. 字母序),则可以定义在Σ*上的叫做词典序的全序。注意因为Σ是有限的,总是可以定义在Σ继而在Σ*上的良好次序。例如,如果Σ = {0, 1}并且0 < 1,则Σ*的词典次序是ε < 0 < 00 < 000 <…< 011 < 0110 <…< 01111 <…< 1 < 10 < 100 <…< 101 <…< 111…

在形式理论中经常出现一些在字符串上的额外运算。它们在条目字符串运算中给出。

字符串数据类型是建模在形式字符串的想法上的数据类型(Data type)。字符串是几乎在所有编程语言中都可以实现的非常重要和有用的数据类型。在某些语言中它们可作为基本类型获得,在另一些语言中做为复合类型获得。多数高级语言的语法允许用某种方式引用起来的字符串来表示字符串数据类型的实例;这种元字符串叫做“文字”(英语:)或“字符串文字”(英语:)。

尽管形式字符串可以有任意(但有限)的长度,实际语言的字符串的长度经常被限制到一个人工极大值。一般的说,有两种类型的字符串数据类型:“定长字符串”,它有固定的极大长度并且不管是否达到了这个极大值都使用同样数量的内存;和“变长字符串”,它的长度不是专断固定的并且依赖于实际的大小使用可变量量的内存。在现代编程语言中的多数字符串是变长字符串。尽管叫这个名字,所有变长字符串还是在长度上有个极限,一般的说这个极限只依赖于可获得的内存的数量。

历史上,字符串数据类型为每个字符分配一个字节,尽管精确的字符集随着区域而改变,字符编码足够类似得程序员可以忽略它—同一个系统在不同的区域中使用的字符集组要么让一个字符在同样位置,要么根本就没有它。这些字符集典型的基于ASCII码或EBCDIC码。

意音文字的语言比如汉语、日语和朝鲜语(合称为CJK)的合理表示需要多于256个字符(每字符一个字节编码的极限)。常规的解决涉及:保持对ASCII码的单字节表示,并使用双字节来表示CJK字形。现存代码在用到它们会导致一些字符串匹配和切断上的问题,严重程度依赖于字符编码是如何设计的。

Unicode也有些复杂的问题。多数语言有Unicode字符串数据类型(通常是UTF-16,因为它在Unicode补充位面介入之前就被增加了)。在Unicode和本地编码之间转换要求理解本地编码,这对于现存系统要一起传输各种编码的字符串而又没有实际标记出它们用了什么编码就是个问题。

某些语言如C++把字符串实现为可以用于任何基本类型的模版,但这是个例外而不是规则。

在一个面向对象语言把字符串表示为对象的情况下,如果值可以在运行期变更,则叫做“可变的”(mutable),如果值在创建后就不可变更了,则叫做“不变的”(immutable)。例如,Ruby有可变字符串,而Python的字符串是不可变的。

其他语言,最著名的有Prolog和Erlang,避免实现字符串数据类型,转而采用把字符串表示为字符代码的列表的约定。

一种常用的表示法是使用一个字符代码的数组,每个字符占用一个字节(如在ASCII代码中)或两个字节(如在unicode中)。它的长度可以使用一个结束符(一般是NUL,ASCII代码是0,在C编程语言中使用这种方法)。或者在前面加入一个整数值来表示它的长度(在Pascal语言中使用这种方法)。

这是一个用NUL结束的字符串的例子,它用10个byte存储,用ASCII表示法:

上面的字符串的长度为5个字符,但注意它占用6个字节。结束符后的字符没有任何意义。

这是相同的Pascal字符串:

当然,可能还有其它的表示法。使用树和列表可以使得一些字符串操作(如插入和删除)更高效。

一些编程语言设计为编写字符串处理程序更容易编写。这是一些例子:

很多UNIX实用程序进行简单的字符串处理,并能用于简单地编写一些强大的字符串处理算法。文件和有限流可以像字符串一样查看。

一些新的编程语言,包括Perl、Python和Ruby,借助正则表达式来帮助文字处理。

这是一些字符串处理算法,在字符串上进行不同的处理:

相关

  • HCG试验hCG试验(hCG pregnancy strip test)是利用检验人绒毛膜促性腺激素的方式,判断是否有怀孕的试验(妊娠试验) 。hCG(人绒毛膜促性腺激素)是胚胎受精后立刻就会分泌的激素,之后也会由胎
  • 兰学家兰学指的是日本江户时代经荷兰人传入日本的学术、文化、技术的总称,字面意思为荷兰学术,引申可解释为西洋学术(简称洋学)。兰学是一种透过与出岛的荷人交流而由日本人发展而成的
  • 卡氏间质细胞卡氏间质细胞(interstitial cell of Cajal、ICC,卡哈尔细胞)是在胃肠道中发现的一种间质细胞。有不同类型且具有不同的功能。其中“肌间质细胞”(Myenteric Interstitial cells
  • 袁亚湘袁亚湘(1960年1月-),湖南人,中国数学家,中国科学院数学与系统科学研究院研究员、博士生导师。现任国际工业与应用数学联盟(International Council for Industrial and Applied Math
  • 斯里兰卡总统斯里兰卡民主社会主义共和国总统,是斯里兰卡民主社会主义共和国的国家元首和政府首脑、斯里兰卡军队(英语:Sri Lanka Armed Forces)总司令,1978年开始设置总统一职。总统一职在斯
  • 蒂伯·赫夫勒蒂伯·赫夫勒(匈牙利语:Tibor Heffler;1987年5月17日-)是一位匈牙利足球运动员。在场上的位置是中场。他现在效力于匈牙利足球甲级联赛球队维迪奥顿足球俱乐部。他也代表匈牙利国
  • 邵虚白邵虚白(1906年-1940年)字全品,浙江鄞县人。民国时期记者、政治人物、烈士。大清光绪三十二年(1906年) 生。1922年,毕业于江苏南京金陵初级中学。后任职于宁绍轮船公司之新宁绍轮,加
  • 毛鸿宾毛鸿宾(1806年-1868年),字翊云,号菊隐,山东历城(今属济南市)人,中国清朝官员。鸿宾为道光十八年(1838年)进士,选翰林院庶吉士,散馆后授编修。历迁御史、给事中。咸丰三年(1853年),在尚书孙瑞
  • 顾悦履顾悦履(?-?),字丹宸,号秋崖,浙江海宁人。清朝官员。康熙三十三年(1694年)甲戌科一甲第三名进士(探花)。授翰林院编修。康熙四十二年,出督山东学政。累官内阁学士兼礼部侍郎。顾悦履能诗善
  • 高熙喆高熙喆(1854年-1938年),字仲瑊,一字亦愚。山东省兖州府滕县城关镇(今属枣庄市滕州市)人,原籍浙江省绍兴府会稽县。清末民初政治人物、经学家、史学家、书法家。自幼熟读经史,入滕县道