n元与k元字母表上字符串的双射相关技术问题咨询

1. n元与k元字母表字符串的双射 #

n元字母表Σₙ和k元字母表Σₖ上的所有字符串（含空串）都是可数无限集，必然存在双射，具体可通过自然数中转构造：

• 第一步：将Σₙ的字符串映射到自然数。按字符串长度从小到大排序，同长度按字典序排列：空串对应0，长度1的n个字符串依次对应1_{n，长度2的n²个字符串对应n+1}n+n²，以此类推，每个字符串唯一对应一个自然数。
• 第二步：将自然数映射到Σₖ的字符串。把第一步得到的自然数转换为k进制表示，每个k进制数位对应Σₖ中的一个字符，即可得到Σₖ上的字符串。
  若仅考虑非空字符串，只需排除空串的映射，调整自然数的起始对应关系即可。

2. 自然语言句子与二进制字符串的双射 #

自然语言句子集合（无论是否限定语法正确）是可数无限集（每个句子是有限长度的字符序列，字符集有限），二进制字符串集合同样是可数无限集，因此存在双射。构造思路如下：

• 先对所有自然语言句子排序：按句子长度从小到大，同长度按字符的编码顺序（如Unicode）排列，每个句子对应唯一的自然数。
• 将该自然数转换为二进制字符串（若需避免空串，可将自然数m对应m+1的二进制表示），即可完成映射。
  构造失败通常是因为对“自然语言句子”的定义模糊（如是否包含无意义句子），或未建立严格的全序排列规则。

3. 满足句子长度非递减的双射构造 #

可以构造这样的双射，核心是保持长度分组的顺序对应：

• 第一步：将自然语言句子按长度分组，记长度为L的句子有m_L个，按顺序枚举所有句子（长度从小到大，同长度按字典序）。
• 第二步：将二进制字符串也按长度分组，记长度为l的二进制串有2^l个，同样按顺序枚举。
• 第三步：建立对应关系：让长度较小的句子组整体对应长度较小的二进制串组，确保若句子s₁长度≤s₂长度，则f(s₁)的长度≤f(s₂)的长度。具体可通过累计计数实现：计算长度1到L的句子总数S_L，找到最小的l_L使得长度1到l_L的二进制串总数≥S_L，将长度L的句子映射到长度l_L的二进制串中未被占用的部分，保证l_L随L非递减。

4. 这类双射的刻画 #

满足“句子长度非递减则映射后二进制串长度非递减”的双射，需满足以下核心特征：

• 设自然语言句子按长度分为有限子集A₁,A₂,...（A_L为长度L的句子集合，大小m_L），二进制字符串按长度分为有限子集B₁,B₂,...（B_l为长度l的二进制串集合，大小2^l）。
• 存在非递减的整数序列{l_L}（l₁≤l₂≤...），使得每个A_L的映射像f(A_L)是∪_{l=l_L}^{l_{L+1}-1} B_l的一个大小为m_L的子集，且所有f(A_L)两两不交、并集为全体二进制字符串。
• 对于任意两个长度l₁<l₂，f⁻¹(B_{l₁})中的句子长度均≤f⁻¹(B_{l₂})中的句子长度，即二进制串的长度顺序与原句子的长度顺序保持一致。

内容的提问来源于stack exchange，提问作者Jan Pax