Author: JieJiSS

这是我写的第一篇博文，在进入正文部分前得先荡开一笔，说一下关于这个博客的一些事情。

主要也是过去的一年里发生了太多的变化，选科，重新分班，研学，退模，各种比赛，各种项目，以及一些更重要但是我不愿意放到网上的事情。因此，我感觉有必要开个博客，随便写点记录性的文字，作为日后反溯的抓手。

关于博客的技术选型，目前考虑的是 Markdown + Hexo 生成静态页面。之前倒是有给 THSCSLab 写过一个基于 markdown-it 的自动分配路由 + 实时渲染 Markdown 的博客，但是那玩意就是个玩具，不能往生产环境放的

如何在首页上展示按时间顺序排列的 blog posts 倒是个问题，因为现在的首页是静态的，服务器上也没有架数据库（从根源上解决 SQL Injection 233333）。可能还是得走类似定时任务生成 .json 格式的目录文件，让 Server 进程在空闲的时候读取进来这种 tricky 的路子。

以上。

正文部分

有一个需求是我已经拿到了一堆姓名，为了查询方便我要把他们都转成可能的拼音组合。我希望实现的效果：

1
2
3
4
5
$ node ./search.js --pinyin="xm"
小明
小米
小猫
徐苗

已有的文件 data.txt：

1
小明,小红,小米,小刚,小猫,小狗,徐苗,二壮,四喜

0x00 数据预处理

这个没什么好说的，读进内存处理一下就好了：

1
2
3
4
5
6
7
const { readFileSync } = require("fs");
const { join } = require("path");

const names = readFileSync(join(__dirname, "data.txt"))
	.toString("utf-8")
	.trim()
	.split(",");

0x01 姓名转拼音

要实现姓名转拼音一般有两种方向：

  • 网上的一些帖子会给出写好的正则表达式或者是很大的一个对象，大概像这样：

    1
    2
    3
    4
    {
        "谬缪繆謬": "miu",
        ...
    }

    之后用 Object.keys() 配合 String.prototype.indexOf 就可以取出对应的拼音了。

    但是这种方法可靠性存疑，支持的汉字数量也很有限。

  • 使用现成的 npm packages，例如 pinyin（字库 ~41000 字，支持音调，10,000 字/s）和 pinyinlite（字库 ~27000 字，10,000,000 字/s，不支持音调）。

    显然我这个需求不需要支持音调，起名字也起不到 Unicode BMP 以外的汉字，所以自然选择更快速的 pinyinlite。

    1
    2
    const pylite = require("pinyinlite");
    let pyArr = pylite("解集");  // [['jie', 'xie'], ['ji']]  Type: string[][]

再仔细研究下需求，发现我们只需要姓名拼音首字母就可以了，所以对返回的结果做进一步处理：

1
2
pyArr = pyArr.map(pys => pys.map(py => py.charAt(0))); // 用 charAt 不用 [0] 是为了方便理解
// pyArr 现在是 [['j', 'x'], ['j']]

如果所有字都是单音字，那就很好办，直接用 pyArr.join("") 就可以得到姓名拼音首字母了，例如 小明 变成 xm，小刚 变成 xg。但是有的时候会出现多音字，所以得想办法正确处理多音字，而不能简单地 join：

1
2
pyArr.join("");  // 解集 -> 'jxj'，但是我们想要的是 ['jj', 'xj']
// 其实是个笛卡尔积

笛卡尔积

定义

笛卡尔积，又称为直积，其表示为 \(X\times Y​\)。可将笛卡尔积运算描述为： \[ A \times B=\\{(x,y)\,|\,x\in A,y\in B\\} \]

对应的 MATLAB 函数是 kron(A, B)。

具体例子

考虑矩阵 \(A\) 和 \(B\)： \[ A=\begin{bmatrix} m \\\\ n \end{bmatrix},\, B=\begin{bmatrix} p \\\\ q \end{bmatrix} \] 则有： \[ A \times B = \begin{bmatrix} mp \\\\ mq \\\\ np \\\\ nq \end{bmatrix} \] 所以本质上，对于每个字的拼音首字母矩阵 \(A_1\cdots A_n\)，题述需求的所求结果即为 \(A_1\times A_2 \times \cdots \times A_n\)。（我不是很确定连乘符号 \(\prod\) 能不能描述矩阵直积，所以干脆展开写好了）

实现

百度上一搜一大把，基本上都是递归实现的，这里不再赘述。

0x02 处理多音字

第一个想到的是用 for 循环遍历数组，拼接出每种可能性再 push 到一个大数组里存着，最后直接输出这个大数组。然而名字并不是定长的，这种办法如果想要处理长度为 2 的名字就需要嵌套 2 层，长度为 3 则嵌套 3 层，以此类推。关键问题是，嵌套的层数是在写代码的时候确定了的（代码运行起来之后就不能动态改变 for 循环的层数了（真的吗？）），灵活性太差了，根本用不了。所以还得另外想办法。

于是经过十来分钟的思考，又想到另外一些办法：

  • 根据输入的字符串的长度，动态生成指定嵌套层数的 for 循环，用邪恶的 eval 函数执行（误。这法子听着就 tricky，而且速度慢的一匹（eval 会破坏 JIT 优化，而且需要在运行时解析、转译、执行代码）。
  • 深度优先搜索 DFS。稍微考虑了一下，感觉递归应该比 while() 好写，所以就通过递归来实现了。从数组的小端开始，遍历当前位置的每一种可能的拼音首字母，并每次都递归调用自身来遍历当前情况下的下一个位置的所有组合（需要传入一个参数 prefix 来表明当前的前缀）。最末端的递归调用完成函数返回一个 string[]，之后上一层递归函数中将接到的所有 string[] 给 concat 起来，返回给上上层，这样就可以完成整个 DFS 了。其实这种也不是真正的「支持超大长度姓名」，因为递归调用的次数受到解释器的限制（js 的尾递归还不够成熟，很多浏览器都不支持），不过基本上够用了。
  • 中序遍历图：将 pyArr 拼接到 [""] 的右侧，形成这样一个东西：["", ...pyArr]。这个数组可以等价转化为一个 n + 1 层的、层与层之间全连通的图（定义 n 为输入字符串的长度），其根节点为刚才强行塞进去的那个空字符串。对着这个空字符串做中序遍历，最终得到的结果就是我们要的东西了。不过这个法子不太好实现，要写的代码比较多，所以我最后也没有采用。

第二种方法看上去最合适，实现一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @author JieJiSS
 * @param {string[][]} arr
 * @param {number?} offset Current index. Default value is 0
 * @returns {string[]} All possible pinyin combinations
 */
function enumAllCombinations(arr, offset = 0) {
    const current = arr[offset];
    const all = [];
    if(arr.length === offset + 1) {
        return arr[offset];
    }
    const tails = enumAllCombinations(arr, offset + 1);
    for(let i = 0; i < current.length; i++) {
        for(let j = 0; j < tails.length; j++) {
            all.push(current[i] + tails[j]);
        }
    }
    return all;
}

刨去 jsDoc 注释，总共十多行的样子。最终效果如下：

1
enumAllCombinations([["j", "x"], ["j"]]);  // ["jj", "xj"]

封装一下，加上对命令行的支持（yargs 大法好），去掉头和尾巴，裹上面包糠，炸至金黄，就可以吃了（逃

来源：https://blog.jiejiss.com/