T9联系人搜索算法

T9搜索算法是国内很常用的一个联系人查找算法，能够帮助我们在众多的联系人中快速定位想要找的人。

今天我们以前讨论一下，如何实现一个简单的T9 搜索算法。

一、功能梳理

首先我们梳理一下要实现什么样的效果。

如下图所示的拨号盘，假设我们想查找联系人张三，张三姓名的拼音是：Zhang San，我们希望类似九宫格输入法输入Zhang 一样通过按“9”、“4”、“2”、“6”、“4” 能匹配到所有姓名以Zhang开头的联系人，或者继续输入San对应的按键：“7”、“2”、“6”来快速定位拼音是Zhang San 的联系人。

image-20201214152626793.png

二、实现思路

功能很简单，可以通过构建一个基于联系人姓名拼音的树来解决。

一共分两步：

• 基于拼音、拼音字母和数字键的映射，构建查找树。
• 基于键盘输入在树种进行查找。

1、树的构建

按照拼音字母顺序构建一个树，这个树的每个节点是一个字母（联系人姓名的拼音），联系人都在叶子节点上。

例如有：李四、李琪、李青三个联系人

李四：L I S I

李琪：L I Q I

李青：L I Q I N G

可以通过拼音构建出如下的树：

image.png

再将字母转换为键盘上的数字，例如“L”在按键“5”上，“I”在按键“4”上，以此类推。得到一个由数字构成的树。

image.png

其中第三层的“S”和“Q”都在按键“7”上，所有合并为了一个节点。

2、根据键盘输入进行查找

假设我们要查找李青，键盘输入的顺序是 54746

• 输入：5

  从根节点开始，向后查找，发现子节点“5”，此时遍历节点“5”的所有子节点，找出所有叶子节点，就可以得到所有拼音以“5”对应的字母“JKL”开头的联系人。

  得到联系人：李四、李琪、李青。

• 输入：54

  继续从节点“5”向后查找，得到节点“4”，遍历“4”的所有子节点，找出所有叶子节点，得到拼音以“JKL”和“GHI”笛卡尔积之后的所有组合开头的联系人，在此例子中为：“JG”、“JH”、“JI”、“KG”、“KH”、“KI”、“LG”、“LH”、“LI”，其中包含我们要找的 李青的拼音前缀“LI”，由于笛卡尔积的数量会越来越多，后面的步骤不在一一列举。

  得到联系人：李四、李琪、李青。

• 输入：547

  继续从节点“4”向后查找，得到节点“7”，遍历“7”的所有子节点，找出所有叶子节点。

  得到联系人：李四、李琪、李青。

• 输入：5474

  继续从节点“7”向后查找，得到节点“4”(注意，此节点和之前的节点“4”不是同一个节点)，遍历“4”的所有子节点，找出所有叶子节点。此时李四已经不满足条件被筛选掉。

  得到联系人：李琪、李青。

• 输入：54746

  继续从节点“4”向后查找，得到节点“6”，遍历“6”的所有子节点，找出所有叶子节点。此时李四和李琪已经不满足条件被筛选掉。

  得到联系人：李青。

经过层层筛选，我们最终得到了想要查找的联系人“李青”

三、优化

你会发现，我们需要输入完整的拼音才能找到联系人，为了解决这个问题，我们还可以同时用姓名的拼音首字母构建第二棵树。在查找第一棵树的同时，也在第二棵树上进行同样的查找，此时就可以更快的将目标联系人输出到屏幕上。

需要注意的是，T9搜索算法的应用场景并不追请非常精准的定位到具体的某一位联系人，有可能两个联系人的查找路径是完全一样的（即一个节点上有两个或多个叶子节点）原因是一个数字键会对应多个字母。

所有T9搜索算法是一种模糊搜索，目的是帮助用户减少需要翻阅的结果的数量，缩小查找范围。

本篇文章仅仅简单的讨论了一下实现T9搜索的算法，才疏学浅，文笔有限，可能有没讲清楚透彻的地方，如果大家有兴趣，可以自行通过自己熟悉的编程语言写写看，在实战中加深理解。