使用快速查询索引结构的电子字典单词查询方法

1.一种电子字典的单词查询方法，其特征在于包括有步骤：
在存储器中设置单词索引数据部分，用以储存对应于所述待查询单词的 多个单词索引值，所述单词索引值用以记录对应的待查询单词在所述单词数 据库中的位置信息；
在存储器中设置二次索引数据部分，用以储存分别对应于预定字母数的 有序序列中的项目的多个二次索引值，所述二次索引值用以记录其开始字母 与有序序列项目相同的待查询单词，其对应的单词索引值在所述单词索引数 据部的位置信息；
在存储器中设置单词相关内容索引数据部分，用以储存对应于所述单词 相关内容的多个单词相关内容索引值，其中所述单词相关内容索引值用以记 录对应的单词相关内容在所述单词相关内容数据库中的位置信息，
中央处理单元根据用户从输入设备输入的单词中与所述有序序列的预 定字母数相同的开始字母部分，从所述二次索引部取出一第一二次索引值；
中央处理单元从所述二次索引部取出所述第一二次索引值的下一个的 第二二次索引值；
中央处理单元以所述第一二次索引值和所述第二二次索引值所对应的 单词索引值为范围，从所述单词索引数据部找出对应于所述输入单词的单词 索引值；以及
根据对应于所述输入单词的单词索引值，从所述单词相关内容索引数据 部中找出对应的单词相关内容索引值。
2.如权利要求1所述的方法，其中所述快速查询索引结构中的所述二 次索引数据部中，所述二次索引值系对应于两个字母的有序序列项目。
3.如权利要求1所述的方法，其中在所述第一二次索引值和所述第二 二次索引值所对应的单词索引值为范围中，利用连续折半查询方法，找出对 应于所述输入单词的单词索引值。
4.如权利要求1所述的单词查询方法，其中在所述二次索引数据部中， 所述二次索引值系对应于两个字母的有序序列项目。
5.一种电子字典的单词查询方法，其特征在于包括有步骤：
在存储器中设置单词索引数据部分，用以储存对应于所述待查询单词的 多个单词索引值，所述单词索引值用以记录对应的待查询单词在所述单词数 据库中的位置信息；
在存储器中设置二次索引数据部分，用以储存分别对应于预定字母数的 有序序列中的项目的多个二次索引值，所述二次索引值用以记录其开始字母 与有序序列项目相同的待查询单词，其对应的单词索引值在所述单词索引数 据部的位置信息；
在存储器中设置单词相关内容索引数据部分，用以储存对应于所述单词 相关内容的多个单词相关内容索引值，其中所述单词相关内容索引值用以记 录对应的单词相关内容在所述单词相关内容数据库中的位置信息，
中央处理单元根据所述输入单词，从所述二次索引部取出一第一二次索 引值；
中央处理单元从所述二次索引部取出所述第一二次索引值的下一个的 第二二次索引值；
设定所述第一二次索引值所对应的第一单词索引值和所述第二二次索 引值所对应的第二单词索引值为一查询范围；以及
根据所述第一二次索引值所对应的第一单词索引值，从所述单词相关内 容索引数据部中找出对应的单词相关内容索引值；
当所述输入单词的字母数大于所述有序序列的预定字母数，执行下列步 骤：
以所述第一单词索引值和所述第二单词索引值为查询范围，从所述单词 索引数据部找出对应于所述输入单词的第三单词索引值；
以所述第三单词索引值取代所述第一单词索引值；以及
根据取代后的所述第一单词索引值，从所述单词相关内容索引数据部中 找出对应的单词相关内容索引值。
6.如权利要求5所述的单词查询方法，其中在所述第一单词索引值和 所述第二单词索引值为范围中，利用连续折半查询方法，找出对应于所述输 入单词的第三单词索引值。
7.如权利要求5所述的单词查询方法，其中在所述二次索引数据部中， 所述二次索引值对应于两个字母的有序序列项目。

本发明涉及一种使用快速查询索引结构的电子字典单词查询方法，特别 涉及利用二次索引数据和单词索引数据所建立的索引结构来快速查询单词， 并且能够随着用户逐次输入单词各字母的同时，动态地快速查询数据的单词 查询方法。\n对于电脑上的电子字典来说，一般在用户输入单词的过程中，会利用输 入单词的部分内容(例如前几个字母)来查询单词的相关内容，例如释义，同 时还必须快速地查询出所输入单词部分内容的后续单词。换言之，每当用户 输入待查询单词的任何一个字母时，电子字典就必须执行一遍查询动作，因 此查询动作的快慢势必影响到用户对于电子字典整体性能的感觉。\n图1表示传统电子字典执行动态单词查询的索引数据结构以及查询处理 步骤的数据流图。其中，10表示用户所输入的单词，其可能是完整的待查询 单词亦或是待查询单词的部分输入内容。20是单词索引数据，30则是单词数 据库，图2表示单词数据库30的结构。其中，单词数据库30储存所有可查 询的单词，而单词索引数据20则是用来储存指出某个单词在单词数据库30 的储存位置的索引值。举例来说，如果单词数据库30中的所有可查询单词以 连续方式储存，则单词“a”在单词索引数据20中对应项目的索引值设为0， 单词“aardvark”在单词索引数据20中对应项目的索引值设为1(前一单词 为单字母)，单词“aardwolf”在单词索引数据20中对应项目的索引值设为 9(前两个单词合计有9个字母)，其余依此类推。40是单词相关内容索引数 据，50是单词相关内容数据库。单词相关内容数据库50是用来储存所有可 查询单词所对应到的内容，包括释义，方法等等信息；而单词相关内容索引 数据40则是用来储存指出某个单词相关内容在单词相关内容数据库50的储 存位置的索引值。\n从于单词索引数据20、单词数据库30、单词相关内容索引数据40和单 词相关内容数据库50为固定数据，因此在一般电子字典中是利用只读存储器 (mask ROM)加以储存。另外，对于包含数万条或是数十万条单词的电子字典 而言，单词数据库30和单词相关内容数据库50的数据量非常的大。为了节 省储存空间，降低成本，一般会利用数据压缩的方式处理这些数据库。考虑 到解压缩效率，一般会采用区块压缩的方式来减少每次解压缩所要处理的数 据量。\n以下说明现有技术单词查询处理流程。当用户输入单词10后，可以先 利用折半查询方法来查询出对应的单词索引值。首先透过步骤1，在单词索 引数据20中找出第一个和最后一个单词索引值，进行折半查询来找出真正对 应此单词10的期望索引值。接着透过步骤2，从单词数据库30中找出对应 此期望索引值的期望单词，如果单词数据库为压缩数据时，则在步骤2必须 同时进行解压缩的处理。透过步骤3，从所找出的期望单词与单词10进行比 较，如果两者相同，则表示已经找到对应的单词索引值；如果两者不同，则 更新折半查询范围，重新执行步骤1到步骤3，直到找到真正的对应单词索 引值为止。当找到对应单词10的单词索引值后，就可以透过步骤4，从单词 相关内容索引数据40找出对应的单词相关内容索引值；再利用所找到的单词 相关内容索引值，透过步骤5，从单词相关内容数据库50中找出对应的相关 内容。\n接着以一实例来说明现有技术中的单词查询过程。图3～图6表示使用 电子字典输入查询单词“schema”的过程中，电子字典显示查询结果的示意 图。在图3中，用户输入查询单词的部分字母“s”，系统会将单词索引数据 20的第一项索引值和最后一项索引值之间设定为查询范围，进行连续性的折 半查询；当系统查询到单词数据库30内的单词“S”之后，则结束连续性折 半查询，再透过单词相关内容索引数据40和单词相关内容数据库50，找出 其相关内容以便显示。接着在图4至图6的处理部分也与所述方式一致，用 户依序输入“sc”、“sch”、“schema”，系统则利用折半查询方式，连续地进 行查询/对比的动作，直到确认查询目标为止。\n从上述说明的单词查询流程可以发现，整个处理最耗时的部分是找出对 应的单词索引值，亦即步骤1至步骤3的循环处理。特别是对于具有十几万 或数十万的大字典而言，重复查询的次数非常庞大。如果数据是利用压缩方 式储存的，在步骤2的解压缩动作也会耗费相当多的时间，这也正是传统查 询方法速度较慢的原因。\n有鉴于此，本发明的主要目的在于提供一种使用电子字典快速查询索引 结构的单词查询方法，能够简化用户在逐字输入单词过程中所需要的查询动 作，以提高电子字典使用的效率。\n为实现本发明的目的，提供了一种电子字典的单词查询方法，包括有步 骤：在存储器中设置单词索引数据部分，用以储存对应于所述待查询单词的 多个单词索引值，所述单词索引值用以记录对应的待查询单词在所述单词数 据库中的位置信息；在存储器中设置二次索引数据部分，用以储存分别对应 于预定字母数的有序序列中的项目的多个二次索引值，所述二次索引值用以 记录其开始字母与有序序列项目相同的待查询单词，其对应的单词索引值在 所述单词索引数据部的位置信息；在存储器中设置单词相关内容索引数据部 分，用以储存对应于所述单词相关内容的多个单词相关内容索引值，其中所 述单词相关内容索引值用以记录对应的单词相关内容在所述单词相关内容数 据库中的位置信息；中央处理单元根据用户从输入设备输入的单词中与所述 有序序列的预定字母数相同的开始字母部分，从所述二次索引部取出一第一 二次索引值；中央处理单元从所述二次索引部取出所述第一二次索引值的下 一个的第二二次索引值；中央处理单元以所述第一二次索引值和所述第二二 次索引值所对应的单词索引值为范围，从所述单词索引数据部找出对应于所 述输入单词的单词索引值；以及根据对应于所述输入单词的单词索引值，从 所述单词相关内容索引数据部中找出对应的单词相关内容索引值。\n还提供了一种电子字典的单词查询方法，包括步骤：在存储器中设置单 词索引数据部分，用以储存对应于所述待查询单词的多个单词索引值，所述 单词索引值用以记录对应的待查询单词在所述单词数据库中的位置信息；在 存储器中设置二次索引数据部分，用以储存分别对应于预定字母数的有序序 列中的项目的多个二次索引值，所述二次索引值用以记录其开始字母与有序 序列项目相同的待查询单词，其对应的单词索引值在所述单词索引数据部的 位置信息；在存储器中设置单词相关内容索引数据部分，用以储存对应于所 述单词相关内容的多个单词相关内容索引值，其中所述单词相关内容索引值 用以记录对应的单词相关内容在所述单词相关内容数据库中的位置信息；中 央处理单元根据所述输入单词，从所述二次索引部取出一第一二次索引值； 中央处理单元从所述二次索引部取出所述第一二次索引值的下一个的第二二 次索引值；设定所述第一二次索引值所对应的第一单词索引值和所述第二二 次索引值所对应的第二单词索引值为一查询范围；以及根据所述第一二次索 引值所对应的第一单词索引值，从所述单词相关内容索引数据部中找出对应 的单词相关内容索引值；当所述输入单词的字母数大于所述有序序列的预定 字母数，执行下列步骤：以所述第一单词索引值和所述第二单词索引值为查 询范围，从所述单词索引数据部找出对应于所述输入单词的第三单词索引 值；以所述第三单词索引值取代所述第一单词索引值；以及根据取代后的所 述第一单词索引值，从所述单词相关内容索引数据部中找出对应的单词相关 内容索引值。\n为使本发明的上述目的、特征和优点能更明显易懂，下文特举一优选实 施例，并配合附图，作详细说明如下：\n图1表示现有技术电子字典执行动态单词查询的索引数据结构以及查询 处理步骤的数据流图。\n图2表示一般单词数据库结构的示意图。\n图3～图6表示使用电子字典输入查询单词“schema”的过程中，电子 字典显示查询结果的示意图。\n图7表示本发明实施例中执行动态单词查询所使用的索引数据结构以及 查询处理步骤的数据流图。\n图8表示本发明实施例中使用的二次索引数据结构的示意图。\n图9表示本发明实施例中使用的二次索引数据、单词索引数据以及单词 数据库之间关联性的示意图。\n图10表示本发明实施例执行动态单词查询的处理流程图。\n图11是实施本发明方法的电子字典的硬件组成配置图。\n符号说明：\n10～单词；15～二次索引数据；20～单词索引数据；30～单词数据库； 40～单词相关内容索引数据；50～单词相关内容数据库。\n本发明的电子字典使用快速查询索引结构的单词查询方法，主要是透过 二次索引数据来减少查询单词索引数据时所需要进行的循环数，同时可以减 少执行单词数据库解压缩处理的次数，提高查询的效率。特别是适合于电子 字典动态查询的应用上。以下配合图式，详细说明本发明的实施例。\n图11是实施本发明方法的电子字典的硬件组成配置图。实施本发明方 法的电子字典的硬件配置包括：中央处理单元1，为整个系统的控制中心， 控制执行本发明方法的各个步骤；输入设备3，用于输入用户想要查询的字 串；显示设备2，用于显示用户输入的字串和查询内容；存储器4，其中存放 有单词数据库和单词相关内容数据库，该单词数据库包括已排序的多个待查 询单词并且该单词相关内容数据库包括分别对应于该待查询单词的多个单词 相关内容，该存储器中还存储有电子字典快速查询索引结构。\n图7表示本实施例中执行动态单词查询的索引数据结构以及查询处理步 骤的数据流图。在图7中，除了系统必备的单词数据库30和单词相关内容数 据库之处，索引数据结构中包括了二次索引数据15、单词索引数据20和单 词相关内容索引数据40。其中单词索引数据20和单词相关内容索引数据40 与现有技术中所述者相同，此处不再赘述，以下则详细说明二次索引数据20 的结构。\n二次索引数据20是用来储存二次索引值，其分别对应于具有预定字母 数的有序序列中的各项目。有序序列是指长度不超过预定字母数而依照字母 顺序(类似一般字典中的排序方式)排列而成的序列。在本实施例中，有序序 列的预定字母数为2个，因此其有序序列可以表示为(a、aa、ab、ac、…、b、 ba、bb、bc、…c、ca、cb、cc、…zy、zz)，其项目总数为26×27＝702。二 次索引值则是用来记录开始字母与有序序列项目相同的待查询单词，其对应 的单词索引值在单词索引数据部20的位置信息。\n图8表示本实施例中二次索引数据结构的示意图。如图所示，二次索引 数据15包括彼此对应的有序序列部15b以及二次索引值部15a。必须说明的 是，二次索引数据15实际置于存储器中者只有二次索引值部15a，有序序列 部15b则为虚拟对应数据。当需要找出某个有序序列项目在二次索引数据20 中所对应的二次索引值，可以透过以下公式决定：\n(第一字母顺序编号-1)×27+第二字母顺序编号(1)\n举例来说，有序序列项目“sc”所对应的二次索引值系置于二次索引数 据20中的第(19-1)×27+3＝489个位置中。另外，实际的二次索引值是用来 指向以对应有序序列项目为首的第一个待查询单词的单词索引值位置。例如 有序序列项目“sc”所对应的二次索引值为47，表示在单词索引数据20中 第47个位置的单词索引值所对应的待查询单词，是以“sc”为首并且在单词 数据库中排序在最前面的待查询单词。\n图9可以用来说明本实施例中二次索引数据15、单词索引数据20以及 单词数据库30之间关联性的示意图。如图所示，二次索引数据15中的二次 索引值，是用来指向单词索引数据20中对应于其有序序列项的第一个单词的 单词索引项；而单词索引数据20中的单词索引项则指向其对应单词在单词数 据库30中的储存位置。例如，对应于有序序列项目“aa”的二次索引值为1， 指向单词索引数据20中的第1个单词索引值，而此单词索引值则指向以“aa” 为开头的第一个单词“aardvard”的储存位置；对应于有序序列项目“ab” 的二次索引值为30，指向单词索引数据20中的第30个单词索引值，而此单 词索引值则指向以“ab”为开头的第一个单词“ab”的储存位置；对应于有 序序列项目“ba”的二次索引值为183，指向单词索引数据20中的第183个 单词索引值，而此单词索引值则指向以“ab”为开头的第一个单词“backer” 的储存位置。\n回到图7，以下说明利用本实施例的索引数据结构进行单词查询的过 程。首先，接收用户所输入的单词10。在步骤1a中，根据单词10的开始字 母部分(在本实施例中为两个字母)，利用上述的公式(1)计算出单词10所对 应的二次索引值的储存位置；再透过此储存位置从二次索引数据15取出二次 索引值I1。同时，从二次索引数据15取出二次索引值I1的下一个二次索引 值I2。在步骤1b中，则根据在上一步骤中得到的二次索引值I1和二次索引 值I2，从单词索引数据20中找出对应的单词索引值R1和单词索引值R2。在 步骤2和步骤3中，则以单词索引值R1和单词索引值R2为范围，进行连续 的折半查询/对比的处理，藉以从单词索引数据20找出对应于单词10的单词 索引值。此折半查询/对比处理与现有技术方式相同，亦即以折半查询方式找 出期望索引值，再从单词数据库30中找出对应于此期望索引值的期望单词 (步骤2)，期望单词与实际的单词10进行对比后(步骤3)，则可以决定是否 找到符合的单词索引值，如果尚未找到，则利用期望索引值来更新折半查询 范围，反复进行直到找出为止。当找出对应于单词10的单词索引值之后，便 可以透过单词相关内容索引数据40找出其对应的单词相关内容索引值(步骤 4)，再从单词相关内容数据库50找出其对应的单词相关内容(步骤5)。\n以下利用查询单词“schema”为例说明上述查询动作。首先，利用此单 词的前两个字母“sc”来对二次索引数据15进行查询。透过公式(1)，可知 其二次索引值储存于二次索引数据15的第(19-1)×27+3＝489个位置。因此， 在二次索引数据15的第489个和第490个位置上，可以找到二次索引值I1 和I2。再利用二次索引值I1和I2，可以从单词索引数据20找到对应的单词 索引值R1和R2。再以单词索引值R1和R2，以折半查询方式找出对应于 “schema”的单词索引值，接着便可以查询出其对应的相关内容。\n从上述说明可知，从于在本实施例中的查询动作是先利用二次索引数据 来决定出折半查询范围，因此降低了执行折半查询/对比的次数，不仅可以缩 短查询时间，同时减少对单词数据库(一般为压缩形式)进行解压缩的处理次 数，提高整体单词查询的性能。\n本实施例的查询索引结构是非常适合于一般电子字典中动态的查询方 式，亦即随着用户逐次输入单词的各字母，能够快速地查询出与目前输入部 分者相同或最接近的单词的相关内容。图10表示本实施例中执行动态单词查 询的处理流程图。首先，系统依序接收用户所输入的单词字母(S1)。当输入 单词的字母数不大于两个(有序序列的预定字母数)时(S2)，则可以直接利用 二次索引数据15来快速完成查询。先利用目前所输入的单词，计算出单词输 入字母在二次索引数据15的位置，并且取得其所对应的二次索引值I1(S3)。 接着再利用二次索引值I1和下一个项目的二次索引值I2，找出其对应的单 词索引值R1、R2，用以确定折半查询范围为R1～R2(S4)。接着则利用二次索 引值I1所得到的待查单词的单词索引值R1(S5)，查询单词数据库30和单词 相关内容数据库50(S6)，找出目前输入部分所对应的最相似单词以及其相关 内容，并且在电子字典的显示幕(未图示)上则显示出所查询出的最相似单词 及其相关内容(S7)，完成阶段性的查询工作。当用户输入的字母数超过两个 以上时(S2)，则是以先前所决定的单词索引值R1～R2范围间进行折半查询， 找出最接近于目前输入单词部分的待查单词的单词索引值R3，并且以R3更 新上述的查询范围中的R1(S8)。同样的，利用单词索引值R1(已更新)来查询 单词数据库30和单词相关内容数据库50(S6)，找出目前输入部分所对应的 最相似单词以及其相关内容，并且在电子字典的显示幕上显示所查询出的最 相似单词及其相关内容(S7)。上述动态查询动作会在用户结束输入或者是已 查询到所需要单词时终止。\n配合图3～图6，利用用户动态输入查询单词“schema”为范例，说明 图10所示的动态查询动作。在图3中，用户输入部分查询单词“s”，从于尚 未超过两个字母，所以利用公式(1)计算出在二次索引数据15中的对应储存 位置：\n储存位置＝(字母“s”顺序编号-1)×27+0＝(19-1)×27+0+486\n因此，在二次索引数据15的第486项储存位置中可得到以“s”为首的 第一个单词的二次索引值I1。接着利用二次索引值I1，可得到在单词索引数 据20的第I1项中所储存的单词索引值R1，其表示以“s”为首的第一个单 词在单词数据库30中的储存位置。同时可以在第I1+1项、第I1+2项等等得 到其后续单词的单词索引值。在图3的左半部即显示目前最接近单词(即“s”) 以及其后续单词。同时，利用单词索引值R1可以透过单词相关内容索引数据 40以及单词相关内容数据库50查询出对应于此最接近单词(即“s”)的相关 内容，如图显示于右半部。\n在图4中，用户输入了部分查询单词“sc”，同样未超过两个字母，所 以再利用公式(1)计算出在二次索引数据15中的对应储存位置：\n储存位置＝(字母“s”顺序编号-1)×27+(字母“c”顺序编号)\n        ＝(19-1)×27+3＝489\n因此，在二次索引数据15的第489项储存位置中可得到以“sc”为首 的第一个单词的二次索引值I1。接着利用二次索引值I1，可得到在单词索引 数据20的第I1项中所储存的单词索引值R1，其表示以“sc”为首的第一个 单词在单词数据库30中的储存位置。同样的，利用单词索引值R1可以透过 单词相关内容索引数据40以及单词相关内容数据库50查询出对应于此最接 近单词(即“sc”)的相关内容。另外，在处理此阶段的输入单词时，可以建 立后续输入阶段所需要的折半查询范围。在上述处理中所得到的单词索引值 R1为此范围的一端，其对应于以“sc”为首的第一个单词。接着，从二次索 引数据15的第490项储存位置中得到其下一个的二次索引值I2，再从单词 索引数据20找到第I2项中所储存的单词索引值R2，其为范围的另一端，对 应于以“sd”为首的第一个单词。亦即，无论用户后续所输入的字母为何， 此单词所对应的单词索引值会在R1(对应于“sa”为首的第一个单词)和R2(对 应于“sd”为首的第一个单词)之间。\n接着在图5中，用户输入了部分查询单词“sch”，已经超过两个字母， 因此可以直接利用先前所建立的折半查询范围R1～R2来进行查询。当找到以 “sch”为首的第一个单词以及其单词索引值R3时，则显示所查询到的最接 近单词(即“SCH”)和后续单词以及其相关内容。另外，利用最接近单词的单 词索引值R3来取代上述的折半查询范围值R1，亦即无论用户后续所输入的 字母为何，此单词所对应的单词索引值会在更新后的R1(对应于“sch”为首 的第一个单词)和R2(对应于“sd”为首的第一个单词)之间。同样的处理适 用于用户后续输入的各字母，直到如图6所示，用户输入“schema”之后， 便完成所有查询的动作。\n本实施例的索引数据结构以及动态查询方法，其优点便在于可以节省大 量反复折半查询的次数。表1是用以比较现有技术和本发明的平均查询次 数。一般标准折半查询的次数为log2(N)，其中N表示待查询总项目。以字典 单词数50000～100000为例，现有技术平均需要15.6到16.6次的查询动作。 而在本发明中，从于利用二次索引数据先将所有单词区分为702类(以两个字 母来分类)，所以平均只需要6.1到7.1次查询动作，便可以找到所需要单词。 表1     字典单词数     现有技术(次)         本发明(次)     50000     1og250000＝15.6   log2(50000/7.02)＝6.1     100000     1og210000＝16.6   log2(100000/702)＝7.1\n如果以50000字的字典为例分析逐次输入各单词字母的平均查询次数， 则如表2所示。在表2中，输入字母数为累计次数，更可以看出本发明在减 少查询次数上的效果。 表2     输入字母数     现有技术(次)               本发明(次)     1     log250000＝15.6   1     2     2×log250000＝31.2   2     5     5×log250000＝78   3×log2(50000/702)+2＝20.3     10     10×log250000＝156   6×log2(50000/702)+2＝38.6\n本发明虽以一优选实施例公开如上，然其并非用以限定本发明，本领域 技术人员，在不脱离本发明的精神和范围内，可做某些改动和替代，因此本 发明的保护范围当从后附的权利要求所界定。