古语词典

来自计算思维百科
跳转至: 导航搜索
古语词典1.jpg

考古爱好者琼斯在芝加哥近郊发现了古代文明古迹,其中包括古语词典。词典中的单词虽然以英文小写字母组成,但词典中的单词顺序与现代英语完全不同。琼斯想要知道,这些单词是以非字典顺序排序的其他顺序排成,还是字母顺序与英语不同。

琼斯猜想:该古语只是字母顺序与现代英语不同,词典中的单词依然以古代字典顺序排列。现在假定此假设为真,想从单词目录中找出字母顺序。

例如,有5个单词gg、kia、lotte、lg、hanwha按顺序记录于词典中。我们要如何根据这5个单词找出部分字母的顺序呢?

解决方案

方案一:比较插入法

我们知道,词典中单词是依次按照每个字母的顺序排列在词典中的,根据这一原则,我们按顺序从5个单词的第一个字母看起:

g k l l h

根据第一个字母,我们知道字典中部分字母顺序是

g k l h

而对于第一个字母相同的单词lotte、lg,看第二个字母是o、g,所以字母o应该在g的前面,结合上次结果将字母o插入得到部分字母顺序如下:

o、g、k、l、h

这样就可以推测出部分字符的排列顺序。

运用的计算思维

比较插入法是一种比较直接的方法,体现“启发式”机械化的思维方式。

方案二:图结构建模

如果单词A比单词B在词典中出现更早。从第一个字母开始比较两个单词,并找出第一个不同的字母,那么按照字母顺序,A相应位置的字母应该出现在B相应位置字母的前面。我们用有向图表示这种顺序。将字母作为顶点,从排在前面的字母发出一条边指向相对后的字母。那么,我们想要得到的字母顺序就是对图进行拓扑排序的结果。

据此,我们根据5个单词gg、kia、lotte、lg、hanwha的第一个字母建立的拓扑图如下:

古语词典2.png

根据lotte、lg的第二个字母顺序,往图上添加的顶点和边如下:

古语词典3.png

接下来就是利用拓扑排序输出顶点顺序:

第一步:找出入度为0的顶点(没有边指向该顶点)输出;

输出结果:字母o

第二步:从图中删除该顶点及从该顶点出发的边

古语词典4.png

第三步:重复第一和第二步直到不存在入度为0的顶点。

最后输出结果为o、g、k、l、h

运用的计算思维

方案二将字母之间的顺序关系表示成有向图,最后对有向图进行拓扑排序方法就能求出字母顺序。这是一种将问题进行转化的方法,运用“转化”“嵌入”的计算思维。

参考文献

[1]具宗万.算法问题实战策略[M].崔盛一,译.北京:人民邮电出版社,2015