【数据结构】以不完整拼音搜索通讯录算法设计
本文主要分享算法设计思路，其中代码均原创，供大家参考和学习
文章目录
- 前言
- 一、问题描述
-
- 1.概述
- 2.具体要求
- 二、数据存储方案
-
- 1.名字对应的音节组合
- 2.拼音库
- 3.通讯录表
- 三、拼音模糊匹配的递归回溯算法
-
- 1.拼音匹配处理函数
- 2.拼音模糊匹配核心递归回溯（Match）
- 四、我最终实现的效果
-
- 1.结果描述
- 2.测试
- 3.我的小小的改进建议
- 总结
前言
开始学习数据结构的时候，很多像顺序表、二叉树、邻接链表的结构学会了完全不知道该在什么地方使用。到学习算法一段时间，做了些题目后，发现自己还是需要阅读一些博客和以前写过的数据结构去“启发式”的引导自己解决问题。其实我们一开始在学习数据结构的时候就应该去思考每个数据结构可以应用的场景，这样学习数据结构才有意思，才能“玩转数据结构”。
通讯录的拼音搜索也是我们常用的场景，“常用”、“不起眼”、但“有意思”。本项目也是我在大二数据结构课程设计的选题，分享一下我的思想给大家。
提示：问题描述很重要，大家以后做算法或者开发也一定要关注问题描述！！！
一、问题描述
1.概述
我们作为个人每天都使用通讯录（包括微信、qq中的通讯录），但考虑一个比较大的场景，许多大型企业也拥有企业的通讯录，可能有上千甚至上万人的名录，那么我们就希望做设计一个快速检索算法，能够通过输入部分的关键字的首拼字母快速的过滤出你想要的联系人。
2.具体要求
- 每个人的姓名可以从第一个字开始匹配，也可以从后面的字开始匹配，如“关云长”可以考虑“guanyun”，“guanyinchang”，“yunchang”，但不能考虑断开的情况，如“guanchang”。
- “多音字”匹配的所有可能，如“chang”可以考虑“zhang”和“chang”。（这里解释一下，为什么“chang”不单独只匹配“chang”，因为很多时候我们存了含多音，要保证假设用户不会“读”的情况下，仍然可以搜索到。）
- 每个汉字的音节可以只匹配部分前缀，如“关云长”可以用“gyc” ，“guyuchang”，“yunchang”，“yuc”得到匹配。
- 实现排序显示
- 相关数据结构、算法：哈希表，顺序表，递归回溯
二、数据存储方案
1.名字对应的音节组合
存储名字的每个字对应的音节采用“字符串”类型的顺序表“StringList”存储元素。一个顺序表结构存处一个名字的读音组合，比如“guanyunchang”可以存储为一个顺序表结构，“guan”存入item[0]，“yun”存入item[1]，“chang”存入item[2]。可以通过item[0][0]访问到‘g’。
其实这里也可以采用字符串类型数组，但是毕竟学习了数据结构，想练习一下顺序表的使用，并且自己写的顺序表在使用上更加灵活。
//顺序表
struct StringList {
string* item;
int capacity;
int length;
//构造函数
StringList(int c=10) {
capacity = c;
length = 0;
item = new string[capacity];
}
//添加元素
void append(string s) {
if (length == capacity) {
capacity += 10;
item = new string[capacity];
}
item[length++] = s;
}
//返回指定位置index的元素
string getItem(int index) {
return item[index];
}
//显示全部元素
void show() {
for (int i = 0; i < length; i++) {
cout << item[i] << " ";
}
cout << endl;
}
};
2.拼音库
拼音库可以用哈希表结构存储，这里用二维数组存储。
string hashs[Max_size][Max_size];//拼音库hashs表
C++处理拼音库（不如Java和C#方便），我采用的拼音表我提前处理过，我在这里给出资源链接。（大家下载保存为txt文件，设置ANSI编码格式）
拼音库文件下载-csdn
读取拼音表的方式（我的方式，大家可以参考，避免大家踩坑！）
//初始化hashs拼音库表
void initHashMap() {
string str;
ifstream inf;
//保存为ANSI编码格式
inf.open("yinjie.txt");
while (getline(inf, str)) {
//cout << str << endl;
int a1 = str[0];
int a0 = str[1];
a1 = -a1;
a0 = -a0;
string str1;
str1 = str.substr(2, str.length() - 2);
string str3 = str1;
hashs[a1][a0] = str3;
}
inf.close();
}
3.通讯录表
通讯录表可以爬取网上的名字数据（保证不犯法的前提下），或者自己写一个名字生成函数，准备好姓名的常用字表，按照一定的规则生成。在这为了测试简单直接写字符串数组存储。
string peopleTable[6];//联系人表
//初始化通讯录表
void initPeopleTable() {
peopleTable[0] = "关云长";
peopleTable[1] = "丁云长";
peopleTable[2] = "丁乐乐";
peopleTable[3] = "张三";
peopleTable[4] = "李四";
peopleTable[5] = "迪丽热巴";
}
三、拼音模糊匹配的递归回溯算法
1.拼音匹配处理函数
在正式进入递归去匹配之前，需要提前做一些工作，那么我们不如就把提前做的工作单独写，核心的递归回溯的算法单独抽象出去写，这样也提高的算法的复用性，并且也方便算法修改和重构。
提前做：
- 调用每个汉字转拼音的接口，这部分的相关处理不要递归实现只需要做一次。
- 如果名字中有多音字要每次按名字顺序和拼音库中的音节顺序每次产生新的组合。
- …
该函数类型为bool，被调用返回得到匹配还是未匹配的结果。
该函数的流程图如下：
代码：
（这里未给出处理多音，多音则是在该处理函数中增加音节的排列组合，实现方式很多：可以每次从每个字的音节中截断取一个处理啊生成组合，调用核心算法匹配；也可以提前取生成每个名字的多个音节组合；）
提示：推荐大家处理一个名字的多音组合时产生一个就匹配一个，这样会减少很多的排列组合的代价，当然也可以把名字中对应位置的常用音节在拼音库表中做调整，这样也可以大幅提高搜索匹配的时间。
//不完全拼音模糊匹配(不处理多音字)
bool PinyinMatch(string search, string name) {
StringList pinyinItem;
for (int i = 0; i < name.length(); i += 2) {
string s = getYinJie(name.substr(i, 2));//从拼音表中获得音节字符串
//cout << s.length() << endl;//验证一下存进去的字符串长度,是否截断
int pos = 0;
for (int j = 0; j < s.length(); j++) {
//判断是否含有空格，这里不考虑多音字，直接在第一个空格处截断取第一个读音
if (s[j] == ' ') {
pos = j; break; }
}
if (pos == 0) pinyinItem.append(s);//不含空格，直接存入pinyinItem[]
else {
string yinjie = s.substr(0, pos);//含空格，截断以后存入pinyinItem[]
pinyinItem.append(yinjie);
}
}
pinyinItem.show();//输出音节表测试
//调用匹配核心算法
if (Match(search, 0, pinyinItem, 0, 0) == true) return true;//如果匹配算法通过，认为该条记录匹配通过，返回true
return false;//匹配未通过返回false
//屏蔽核心算法测试pyItem，直接return true
//return true;
}
2.拼音模糊匹配核心递归回溯（Match）
首先了解我的Match函数的基础思想。该匹配函数需要传入输入的待匹配的字符串，以及名字转拼音音节后的存储的顺序表。然后根据递归回溯原理进行匹配。
首先看一下原理：
以输入“guanyucha”匹配“关云长”为例，“关云长”在工具函数pinyinMatch中得到pyItem为“guan”“yun”“chang”，然后首先进行“guanyucha”的首字母‘g’与“guan”比较相等后，递归，’u’,’a’,’n’分别继续匹配“guan”，该层匹配结束后，继续匹配’y’与“yun”的首字母匹配，匹配到’c’无法继续在“yun”中匹配，进入pyItem的下一个元素“chang”匹配之后的元素，匹配到’a’结束匹配，返回true标志匹配成功。
提示：核心核心核心！！！
每次传入Match函数中的参数有：
- string类型search（待匹配的拼音字符串）
- int类型的searchIndex（当前搜索到拼音字符串的位置，理解为拼音字符串的“指针”）
- StringList类型的pyItem（生成的当前扫描到名字的一个音节组合表）
- int类型的yinjieIndex（音节表的第几层，比如：“guan”第一层，“yun”第二层）
- int类型的yinjieStart。（音节的第几个字符，比如：'g’为yinjieIndex=0,yinjieStart=0时的字符）
递归回溯图：
递归回溯部分：
//匹配算法(递归回溯)
bool Match(string search,int searchIndex,StringList pyItem,int yinjieIndex,int yinjieStart) {
//这个if是规定第一个首字母必须匹配的一种匹配方法，例如yc是匹配不到gyc的
//if (searchIndex == 0)//如果在输入的search[]的第一个字母位置
// //第一个必须匹配&&如果只有一个字符，算匹配成功，否则从第二个字符开始比较,进入下一层递归
// return search[0] == pyItem.getItem(0)[0] && (search.length() == 1 || Match(search, 1, pyItem, 0, 1));
//这里处理如果guan yun chang，yc可以匹配，c不能匹配
if (searchIndex == 0) {
if (yinjieIndex > pyItem.length - 1) return false;
startFloorIndex++;
return search[0] == pyItem.getItem(yinjieIndex)[0] ? Match(search, 1, pyItem, yinjieIndex, 1) : Match(search, 0, pyItem, yinjieIndex + 1, 0);
}
//判断不越界&&判断匹配
if (pyItem.getItem(yinjieIndex).length() > yinjieStart && search[searchIndex] == pyItem.getItem(yinjieIndex)[yinjieStart])
//如果这是最后一个字符，检查之前的声母是否依次出现
//如果不是最后一个字符，同一个字的拼音连续匹配
return searchIndex == search.length() - 1 ? keyMatch(search, pyItem, yinjieIndex) : Match(search, searchIndex + 1, pyItem, yinjieIndex, yinjieStart + 1);
//判断不越界&&不能拼音连续匹配的情况下，看看下一个字的拼音的首字母能否匹配
else if (pyItem.length > yinjieIndex + 1 && search[searchIndex] == pyItem.getItem(yinjieIndex + 1)[0])
//如果这是最后一个字符，检查之前的声母是否依次出现
//如果不是最后一个字符，去判断下一个字拼音的第二个字母
return searchIndex == search.length() - 1 ? keyMatch(search, pyItem, yinjieIndex) : Match(search, searchIndex + 1, pyItem, yinjieIndex + 1, 1);
else if (pyItem.length > yinjieIndex + 1)//回退
for (int i = 1; i < searchIndex; i++)
if (Match(search, searchIndex - i, pyItem, yinjieIndex + 1, 0)) return true;
return false;
}
提示：代码中的keyMatch函数后面会解释，先说要注意的两个点！
递归回溯算法设计——处理几种不匹配返回false的情况：
- 待匹配字符串的第一个字符与每个音节的首字母都不匹配，就会在递归次数达到音节数之后直接跳出。
- 匹配到待匹配字符串的最后，检验之前的每个音节的首字母按顺序依次出现。不依次出现返回false。
- 其他：“guanyunchang123”“guanchang”“gc”匹配不到
匹配算法的完善——不能“截断匹配”：
例：关云长—用“gy”，“yc”可搜索，用“gc”不可搜索。
(实现原理与首字母的匹配原理一致，判断此记录的每个汉字的音节的首字母是否在搜索拼音中出现过,且按照顺序出现,用搜索字符控制判断次数。)
提示：看不懂递归回溯图的，我再解释一下，看懂的跳过。
- 如果搜索为关云，“gy“则判断两次，在“guan”,”yun”中判断gy都出现过则返回true匹配。
- 若输入“yc”因为与”guan”首字母不匹配则跳到”yun”，“chang”匹配，匹配成功返回true。
- 若输入为“gc”则”g”与”guan匹配“c’’与“yun”不匹配返回false。则此思想可实现不能截断匹配。
- 对模糊匹配的完善（首字母按序匹配），例如搜索”guanun”则“guan”匹配，进入“yun“因为首字母不匹配，故返回false。若没有首字母匹配功能，存在”guanun”中”un”也可进入匹配并且匹配成功显示，这个问题要避免。
辅助匹配部分（检验作用）：
//辅助变量：用于取到在辅助函数中第几层开始判断每个音节首字母顺序
int startFloorIndex = -1;
//辅助匹配函数,确保pyItem.getItem(n)[0]都按照顺序出现
//防止guan yu chang匹配gc(跳过了yu达到匹配的这种情况)
bool keyMatch(string search,StringList pyItem,int yinjieIndex) {
int lastIndex = 0;
int i;//i代表开始的层数
for (i = startFloorIndex; i < yinjieIndex + startFloorIndex; i++) {
lastIndex = IndexOf(search, pyItem.getItem(i)[0], lastIndex);
if (lastIndex == -1) return false;
lastIndex++;
}
return true;
}
- 首先需要一个getIndexof函数得到某个字母在拼音中的位置。只是判断在音节中有没有出现过。
- 设置辅助函数的原因：每次判断时需要知道此条记录每个汉字首字母是否在搜索拼音中出现过，若出现过得到此位置，若未出现过返回-1；
- keyMatch算法实现根据上述原理设置一个层数int startFloorIndex = -1；避免重复对某一个汉字的音节进行匹配重复递归。
- 每次对一个首字母判断之后进入下一个汉字的首字母匹配循环直至所有搜索音节匹配完毕。
- 若都按照顺序出现则返回true，否则返回false。
四、我最终实现的效果
本来是没有这部分的，因为本篇博客也只想阐述算法的设计思想。但是我对然不能分享我整个项目的源码给大家，但是可以给大家演示和说明一下我实现了核心的算法后，最终的效果，也希望大家能有启发，或者可以开发出可视化的界面达到更好的效果。
1.结果描述
- 最终的代码量共882行（包含简单的测试语句）
- 最大的测试数据量达到10000条通讯录，最长搜索时间<1000ms。
- 前面随机生成和加载通讯录到顺序表中花费的时间较长，这个是影响性能的地方。
- 最终功能的详细描述：
（1）实现拼音库的存储（以数组形式）
（2）实现随机生成10000条通讯录数据存储在电脑指定位置的文本文件中，做到数据持久化。名字的长度2-4。
（3）实现不完整拼音搜索的多音情况，最多支持四个字每个字包含四个多音（在这个名字的匹配中会产生256种组合的情况）
（4）实现通讯录从文件加载到顺序表后顺序存储（首字母顺序等），搜索结果显示按照首字母顺序（如果第一个字的首字母相同会按照第二个字的首字母顺序排序，在搜索匹配情况较多时，顺序排列会比较容易找到需要找到的那个人，符合实际我们现在通讯录的方式。)
（5）用比较取巧的方法实现分隔符匹配的功能。例如“xi’an”匹配“西安”不匹配“先”。以分隔符将整个字符串切割，“xi”和“an”分别拿进去模糊匹配，当两个匹配的结果都匹配到时，返回对应的记录。（因为“an”首字母匹配不到“xian”，所以“xi’an”匹配不到“先”，类似输入法里的功能）。
2.测试
运行开始，在指定位置生成通讯录（随机10000条）。
以“长乐宁”为例，输入“cln”，得到“长乐宁”。
输入“zhanglening”，得到“长乐宁”。
输入“zn”“zhangn”，无法得到“长乐宁”。
输入“ln”，得到“长乐宁”。
3.我的小小的改进建议
我的代码还有许多可改进的地方，希望大家多多批评指正！
- 提高封装性，将通讯录的每一个联系人封装包含name和phone的结构体，通讯录使用结构体数组或者结构体链表，动态创建、调用、实现。
- 拼音库的存储采用hash表或者一维数组的存储方式会更加节约空间，而且好用，够用，二维数组的存储方式有些浪费空间。
- 多音匹配根据音节使用频率依次组合，减少预处理的时间，加快匹配速度。
总结
希望本篇博客能让大家有所收获。
本算法最终是团队成果的呈现，在此特别感谢铁锅炖乔治couple，马总，yyj-么，韦哥的大力支持。代码改变着世界，我们创造代码，也是在创造世界，让我们在代码的世界里风雨同舟，一往无前！
