用于利用散列来执行基于全文的逻辑运算的方法
用于利用散列来执行基于全文的逻辑运算的方法
【专利摘要】提供用于利用散列来执行基于全文的逻辑运算的方法，该方法包括：（a）生成具有根据逻辑算子的类型改变的逻辑状态的散列数据结构，以对应于第一逻辑算子；（b）将与第一运算对象数据相对应的散列节点插入到从散列数据结构顺序地分配的桶中；以及（c）如果当前逻辑算子的类型为AND，则选择在步骤（b）中被插入在散列数据中的桶或者作为先前运算的结果值而选择的桶当中的、和与第二运算对象数据相对应的散列节点一致的桶，作为结果值，如果当前逻辑算子的类型为OR，则将未从散列数据结构检索到的与第二运算对象数据相对应的散列节点当中的散列节点插入到从散列数据结构顺序地分配的桶中，并且选择散列数据结构内的所有有效桶作为结果值。
【专利说明】用于利用散列来执行基于全文的逻辑运算的方法
【技术领域】
[0001]本发明涉及用于有效执行被用于从基于全文的数据库中检索关键字的逻辑运算的方法，更具体地，涉及用于在其中系统资源有限的移动终端上利用最小资源来有效执行逻辑运算的方法。
【背景技术】
[0002]信息检索系统是这样一种系统，S卩，该系统从其中被预测是用户所需的信息或数据之前被收集、处理以及操作并且按该信息或数据可以被容易找到的形状累积的数据库中快速检索适于用户需要的信息，该系统向用户提供该信息。
[0003]信息检索系统根据数据库中累积的信息的类型而被分类成引文检索、事实检索，以及全文检索。引文检索是，检索主要操作用户要寻找的主题的文献的书目记录，并且在线信息检索系统(如DIRL0G、BRS等)对应于引文检索。事实检索是，检索一般数据、数值数据以及事实数据，而化学文摘服务在线(CAS)(由此检索化学药品)、电子信息服务(EMIS)(由此检索半导体材料的数据)等属于事实检索的范畴。全文检索是，在需要时从累积文献的全文的数据库中检索书目数据、对应文本或全部原始文本。其中可以检索法律信息的LEXIS或WESTLAS、其中可以检索论文的NEXIS、Dow Jones检索等属于全文检索的范畴。
[0004]对于被用于从基于全文的数据库中检索关键字的逻辑运算来说，需要大容量计算资源。然而，可以在移动环境中使用的计算资源有限，致使检索速度在执行逻辑运算时降低。
[0005]由此，在移动终端上的基于全文的检索系统中，所提供逻辑算子的使用数非常有限，致使不能提供有效关键字检索。
【发明内容】
[0006]本发明提供了一种用于利用散列来执行基于全文的逻辑运算的方法，由此，提出了一种利用散列来估算基于全文的逻辑算子的方法，使得可以在系统资源有限的移动终端上利用最小资源来执行最佳AND/OR逻辑运算，并且使得逻辑运算结果数据可以在执行了逻辑运算之后从外部获得。
[0007]根据本发明一方面，提供了一种用于利用散列来执行基于全文的逻辑运算的方法，该方法包括以下步骤:(a)生成具有根据逻辑算子的类型改变的逻辑状态的散列数据结构，以对应于第一逻辑算子；(b)将与第一运算对象数据相对应的散列节点插入到从所述散列数据结构顺序地分配的桶中；以及(C)如果当前逻辑算子的类型为AND，则选择在步骤(b)中被插入在所述散列数据中的桶或者作为先前运算的结果值而选择的桶当中的、和与第二运算对象数据相对应的散列节点一致的桶，作为结果值，如果当前逻辑算子的类型为0R，则将未从所述散列数据结构检索到的与所述第二运算对象数据相对应的所述散列节点当中的散列节点插入到从所述散列数据结构顺序地分配的所述桶中，并且选择所述散列数据结构内的所有有效桶作为结果值。[0008]根据本发明另一方面，提供了一种计算机可读记录介质，该计算机可读记录介质上记录有散列数据结构和用于利用散列来执行基于全文的逻辑运算的用户接口，其中，所述散列数据结构包括:散列函数，该散列函数根据其中将散列标识符(ID)用作输入值的MOD运算而生成；散列表，该散列表是指定与散列键相对应的桶的开始位置的散列节点的列表集；以及桶块，在该桶块中，每一个桶都包括针对散列链的散列ID和指针，并且其中，所述用户接口包括:启动模块，该启动模块生成具有根据逻辑算子的类型改变的逻辑状态的散列数据结构，以对应于第一逻辑算子，并且分配和初始化存储器；插入模块，该插入模块将与第一运算对象数据相对应的散列节点插入到从所述散列数据结构顺序地分配的桶中；以及逻辑模块，如果当前逻辑算子的类型为AND，则选择被所述插入模块插入在所述散列数据中的桶或者作为先前运算的结果值而选择的桶当中的、和与第二运算对象数据相对应的散列节点一致的桶，作为结果值，如果当前逻辑算子的类型为0R，则将未从所述散列数据结构检索到的与所述第二运算对象数据相对应的所述散列节点当中的散列节点插入到从所述散列数据结构顺序地分配的所述桶中。
【专利附图】
【附图说明】
[0009]图1例示了根据本发明的实施方式的、在用于利用散列来执行基于全文的逻辑运算的方法中所使用的散列数据结构；
[0010]图2例示了在本发明中使用的用户接口当中执行启动模块的操作；
[0011]图3例示了在本发明中使用的用户接口当中执行清除模块的操作；
[0012]图4例示了在本发明中使用的用户接口当中执行插入模块的操作；
[0013]图5例示了在本发明中使用的用户接口当中执行逻辑模块的操作；
[0014]图6例示了在本发明中使用的用户接口当中执行逻辑改变模块的操作；
[0015]图7例示了在本发明中使用的用户接口当中执行尺寸模块的操作；
[0016]图8例示了在本发明中使用的用户接口当中执行下一个(Next)模块的操作；
[0017]图9A到9C例示了根据本发明实施方式的表和索引；以及
[0018]图1OA到14E例示了根据本发明实施方式的检索的插入操作、逻辑运算以及结果。
【具体实施方式】
[0019]下面，参照附图，对本发明进行更全面描述，其中，示出了本发明的示例性实施方式。
[0020]下面，参照图1，对根据本发明实施方式的、在用于利用散列来执行基于全文的逻辑运算的方法中所使用的散列数据结构进行描述。
[0021]在本发明中使用的散列数据结构可以包括:散列函数(未示出)、散列表10、桶块20、光标40、AND计数器50，以及OR计数器51。
[0022]散列函数是其中通过输入散列标识符(ID)而生成散列键的函数。散列函数可以通过MOD运算来生成。而且，全文数据库的记录ID被用作散列ID。
[0023]散列表10是指定与散列键相对应的桶30的开始位置的散列节点的列表集。散列表10的尺寸利用由用户输入的预计数(PreCount)来确定,并且可以被确定为比桶块20的尺寸更大一点的质数，以用于桶30的均匀分布。[0024]作为被插入到散列中的数据结构的桶30每一个均包括针对散列链32的散列ID和指针，以在散列彼此冲突时检索对应桶30。用于确定针对散列节点的、要通过用户输入的逻辑运算的结果值和数据(用户数据I和用户数据2)的计数器可以包括在桶30中。
[0025]桶块20是存储缓冲区，该存储缓冲区利用作为要插入到散列中的桶30的可预测数的预计数来预先生成。
[0026]光标40被用于指定桶块20上的桶30的位置，并且支持容易从外部获取的逻辑运
算的结果。
[0027]AND计数器50被用于计数AND逻辑运算的结果值的数量，而OR计数器51被用于计数OR逻辑运算的结果值的数量。
[0028]在本发明中，设置作为存储器管理器60的模块，并且存储器管理器60管理在散列中使用的存储器，具体来说，管理自动添加要插入当前桶的位置信息和桶块20的功能。存储器管理器60根据预定范围预先指定桶块20的尺寸，并且确定根据从用户输入的PreCount值所属于的范围的值，作为要生成的桶块20的尺寸。这里，桶块20的尺寸可以被确定为2n (其中，η是整数)以易于存储器管理。由用户输入的PreCount可以指定，以使两个或三个桶30可以呈现在散列链32内。有效的是，通过索引在与逻辑运算的第一运算对象数据相对应的集合中使用许多散列节点。
[0029]如果实际插入的桶30的数量大于桶块20的尺寸，则存储器管理器60自动生成新的桶块20。由此，在根据现有技术的散列数据结构中，只要当在散列彼此冲突时生成桶30时，都需要分配新的存储器空间，并且桶需要按连接列表形状配置。然而，根据本发明，已经在桶块20内生成的桶30可以顺序地分配并且可以按连接列表形状配置。
[0030]在本发明中使用的用户接口包括:启动、清除、插入、逻辑、逻辑改变、尺寸，以及下一个。
[0031](I)启动模块
[0032]如图2所示，启动模块执行初始化和资源分配以使用散列。
[0033]输入值由逻辑算子、算子数以及桶的可预测数PreCount组成。
[0034]逻辑算子是AND或0R。
[0035]算子数是其中AND或OR逻辑算子连续出现的数量。例如，当逻辑运算“A AND BAND C”呈现在集合A、B以及C上时，算子数为2。
[0036]桶的可预测数PreCount被用作用来确定散列表10的尺寸和桶块20的尺寸的重要输入值。
[0037]下面，对要由启动模块执行的操作进行描述。
[0038]初始化逻辑运算Hash (散列)的所有变量项(S100)。
[0039]桶块20的尺寸和散列表10的尺寸利用由用户输入的值PreCount确定(S110)。桶管理器60根据预定范围预先指定桶块20的尺寸，并且确定根据从用户输入的PreCount值所属于的范围的值，作为要生成的桶块20的尺寸。这里，桶块20的尺寸可以被确定为2n(其中，η是整数)以易于存储器管理。而且，散列表10的尺寸被确定为比桶块20的尺寸更大一点的质数。
[0040]利用散列表10的所确定尺寸将存储器分配给散列表10，并且初始化存储器(S120)。[0041]随后，生成具有根据输入逻辑算子的类型AND或OR改变的逻辑状态的散列数据结构(S130、S140)。即，桶的类型被分类成用于AND逻辑运算的桶30a和用于OR逻辑运算的桶30b，并且计数器被附加地包括在用于AND逻辑运算的桶30a中。该计数器被用于执行AND逻辑运算。在处于AND逻辑状态的散列数据结构中，仅可以执行AND逻辑运算，而在处于OR逻辑状态的散列数据结构中，仅可以执行OR逻辑运算。然而，如果逻辑算子的类型被改变成另一类型，则散列数据结构的逻辑状态可以通过下面将描述的逻辑改变模块来改变。
[0042](2)清除模块
[0043]如图3所示，清除模块执行完成所有逻辑运算的功能和释放散列内的资源的功倉泛。
[0044]不存在输入值。
[0045]下面，对要由清除模块执行的操作进行描述。
[0046]返回桶块20的存储器(S200)，并且返回散列表10的存储器(S210)，接着初始化所有变量项(S220)。
[0047](3)插入模块
[0048]如图4所示，插入模块将第一运算对象数据插入到已初始化散列数据结构中，以执行逻辑运算。如果集合A和B上存在运算“A AND B”，则插入模块执行将集合A的元素之一插入散列中的功能。
[0049]输入值是要作为散列节点输入的用户数据资料。
[0050]散列节点(数据资料):由要在散列函数中使用的散列ID和由用户输入的其它数据组成。
[0051]下面，对要由插入模块执行的操作进行描述。
[0052]首先，检索要输入的数据是否已经存在于散列中(S300)。即，检索散列中是否存在具有和输入散列节点的散列ID相同的散列ID的桶。
[0053]作为检索的结果，如果存在已经存在于散列中的数据，则不执行操作。
[0054]作为检索的结果，如果散列中不存在数据，则从存储器管理器60分配一个桶(S310)，并且利用散列函数生成散列键(S320)，接着将所分配桶连接至对应于该散列键的散列链(S330 )，从而将输入数据记录在所分配桶中(S340 )。
[0055]OR计数器值增加I (S350)。
[0056](4)逻辑模块
[0057]如图5所示，逻辑模块通过输入在逻辑算子之后放置的运算对象来执行逻辑运算。如果集合A和B上存在运算“A AND B”，则逻辑模块在集合B的多个元素之一上按散列执行AND运算函数，而如果集合A和B上存在运算“A OR B”，则逻辑模块在集合B的多个元素之一上按散列执行OR运算函数。
[0058]输入值由算子编号和散列节点(数据资料)组成。
[0059]算子编号:意指连续相同逻辑运算中的逻辑算子的顺序。例如，当存在逻辑运算“AAND B AND C AND D”时，算子数为3，而当执行第一逻辑运算(A AND B)时，算子编号为1，当执行第二逻辑运算((第一逻辑运算的结果)AND C)时，算子编号为2，当执行第三逻辑运算((第二逻辑运算的结果)AND D)时，算子编号为3。[0060]散列节点(数据资料):由要在散列函数中使用的散列ID和由用户输入的其它数据组成。
[0061]如果当前逻辑算子的类型为AND，则逻辑模块选择在通过插入模块插入在散列数据结构中的桶或者作为先前运算的结果值而选择的桶当中的和与第二运算对象数据相对应的散列节点一致的桶，作为结果值。另一方面，在当前逻辑算子的类型为OR时，如果没有从散列数据结构检索到与第二运算对象数据相对应的散列节点，则逻辑模块执行将散列节点插入到从散列数据结构顺序地分配的桶中的操作。下面，对其详细操作进行描述。
[0062]首先，执行要输入的数据是否已经存在于散列中的检索(S400)。即，检索散列中是否存在具有和输入散列节点的散列ID相同的散列ID的桶。
[0063]作为操作S400中的检索的结果，如果检索到该数据已经存在于散列中，则检查当前逻辑算子是AND还是0R(S410)。当前逻辑算子被设置为通过启动模块输入的逻辑算子，如果执行逻辑改变模块，则将当前逻辑算子改变成最近输入的逻辑算子。
[0064]作为操作S400中的检索的结果，如果检索到要输入的数据已经存在于散列中并且当前逻辑算子为AND，则当检索到的桶的计数器值和通过将输入算子编号减去I而获取的值相同(直至先前运算作为AND逻辑运算的结果值的桶)时(S420)，检索到的桶的计数器值增加I (当前运算的结果值)(S430)，如果检索到的桶的计数器的增加的计数器值与通过启动模块或逻辑改变模块输入的算子的数量一致(AND运算的最终结果值)(S440)，则AND计数器值增加I (S450)。与此相反，当检索到的桶的计数器值和通过将输入的算子的数量减去I而获取的值不同，或者检索到的桶的增加的计数器值和通过启动模块或逻辑改变模块输入的算子的数量不同时，不执行操作。
[0065]如果在操作S400中的检索没有结果，则检查当前逻辑算子是AND还是0R(S460)。
[0066]如果操作S400中的检索没有结果并且当前逻辑算子为AND，则不执行操作。
[0067]如果操作S400中的检索没有结果并且当前逻辑算子为0R，则从存储器管理器60分配一个桶(S470 )，并且利用散列函数生成散列键(S480 )，接着将所分配桶连接至对应于该散列键的散列链(S490)，并且将输入数据记录在所分配桶中(S500)，并接着OR计数器值增加 I (S510)。
[0068](5)逻辑改变模块
[0069]当逻辑算子改变时使用逻辑改变模块。逻辑改变模块执行改变散列的逻辑状态的功能。如果运算“(A AND B) OR C”呈现在集合A、B以及C上，则逻辑改变模块在执行了AND逻辑运算之后执行将散列的逻辑状态从AND改变成OR的功能。
[0070]输入值由逻辑算子和算子数组成。
[0071 ] 逻辑算子:AND或OR
[0072]算子数:其中AND或OR算子连续出现的数量
[0073]参照图6，对利用逻辑改变模块来将AND改变为OR的操作进行描述。
[0074]首先，新散列数据结构利用逻辑算子和作为输入值的算子数以及在当前散列数据结构中设置的桶的可预测数PreCount而内部地设置(S600 )。在这种情况下，使用上述启动模块。
[0075]随后，根据当前散列数据结构仅获取结果值，并且利用下面将描述的下一个(Next)模块将结果值插入到新散列数据结构中，接着将当前散列数据结构中的变量项映射至新散列数据结构的变量项(S610)。
[0076]随后，利用清除模块从当前散列数据结构释放存储器资源(S620)。
[0077]随后，将内部生成的新散列数据结构的变量项和指针映射至当前散列数据结构(S630)，并且仅内部生成的新散列数据结构的对象数据被消除(S640)。在这种情况下，新散列数据结构未被清除。
[0078]为了实现逻辑改变模块，存储散列内部的多个项当中的用户输入数据的缓冲区(散列表、桶块)需要利用指针从堆中分配。由此，当前散列数据结构的逻辑状态可以改变成新逻辑状态。
[0079]通过执行上述操作，当逻辑算子从AND改变成OR时，分配给散列数据结构的存储器的尺寸可以显著减小。
[0080]因为在通过逻辑改变模块执行从OR向AND改变的操作的同时所分配存储器的尺寸未减小，所以简单地改变当前散列数据结构的逻辑状态。在这种情况下，当前散列数据结构的桶改变成用于AND逻辑运算的桶30a。
[0081](6)尺寸模块
[0082]参照图7，尺寸模块执行将逻辑运算的结果的数量返回给用户的功能。
[0083]不存在输入值。
[0084]检查当前逻辑算子是AND还是0R(S700)，如果散列数据结构的逻辑状态是AND逻辑状态，则返回AND计数器值(S710)，如果散列数据结构的逻辑状态是OR逻辑状态，则返回OR计数器值(S720)。
[0085]( 7 )下一个(Next)模块
[0086]参照图8，下一个(Next)模块在执行了逻辑运算之后执行向用户返回逻辑运算的结果的功能。
[0087]不存在输入值。
[0088]对于下一个(Next)模块的情况来说，在当前逻辑算子的类型为AND时(在当前散列数据结构是在执行了 AND逻辑运算之后时)，从散列数据结构仅检索具有和AND逻辑算子的数量相同的计数器数的桶，并且设置为最终结果值，从而将放置光标的桶内的用户数据一个接一个地输出。在当前逻辑算子的类型为OR时(在当前散列数据结构是在执行了 OR逻辑运算之后时)，散列数据结构内的所有有效桶被设置为最终结果值，从而将放置光标的桶内的用户数据一个接一个地输出。下面，对其详细操作进行描述。
[0089]检查当前逻辑算子是AND还是0R(S800)，如果散列数据结构的逻辑状态是AND逻辑状态，则光标值增加1，并且在光标的位置中获取桶(S810)。
[0090]如果所获取桶无效，则散列数据结构内的所有桶块被舍去(rounded)，将“没有数据”返回给用户(S820)。
[0091]如果所获取桶有效，则桶内的计数器值和算子数彼此进行比较，如果计数器值和算子数相同，则返回桶内的用户数据(S830)，而如果计数器值和算子数不同，则该操作返回至操作S810。
[0092]如果散列数据结构的逻辑状态是OR逻辑状态，则光标值增加1，并且在光标的位置中获取桶(S840)。
[0093]如果所获取桶有效，则返回桶内的用户数据(S850)，而如果所获取桶无效，则散列数据结构内的所有桶块被舍去(rounded)，并且将“没有数据”返回给用户。
[0094]下面，参照下列示例，对根据本发明的、用于利用散列来执行基于全文的逻辑运算的方法进行描述。
[0095]假定在图9B和9C中示出与图9A中所示“表A”有关的“名称B+索引”和“区域B+索引”中的每一个。
[0096](示例I)检索包括与“名称”有关的“现代”和“汽车”的记录。
[0097]检索查询将按逻辑方式表达如下。
[0098]名称(“现代” AND “汽车”)
[0099]首先，如图1OA中所示，根据索引检索关键字“现代”，以使执行到散列中的插入操作。
[0100]接下来，如图1OB中所示，根据索引检索关键字“汽车”，以使针对散列执行AND逻
辑运算。
[0101]接着，图1OC中示出了检索的结果。
[0102]下面，对示例I的程序代码进行描述:
[0103]LogicHash hash;//散列对象
[0104]hash.StartUp (L0GIC_AND, I, 100) ;// 逻辑算子,算子数,桶的可预测数
[0105]hash.1nsert ({luser data}) ;//插入操作
[0106]hash.1nsert ({2user data});
[0107]hash.1nsert ({4user data});
[0108]hash.Logic (I, {luser data}) ;//AND 逻辑运算
[0109]hash.Logic (I, {4user data});
[0110]hash.Logic (I, {5user data});
[0111]int size=hash.SizeO ;//获取结果的数量
[0112]for (int i=0; i〈size; i++) {//检查检索的结果
[0113]{bucket} =hash.Next ();
[0114]}
[0115]hash.CleanUp () ; // 释放散列资源
[0116](示例2)检索包括与“名称”有关的“现代”或“汽车”的记录。
[0117]检索查询将按逻辑方式表达如下。
[0118]名称(“现代” OR “汽车”)
[0119]首先，如图1lA中所示，根据索引检索关键字“现代”，以使执行到散列中的插入操作。
[0120]接下来，如图1lB中所示，根据索引检索关键字“汽车”，以使针对散列执行OR逻辑运算。
[0121]接着，图1lC示出了检索的结果。
[0122]下面，对示例2的程序代码进行描述:
[0123]LogicHash hash;//散列对象
[0124]hash.StartUp (L0GIC_0R, I, 100) ;//逻辑算子,算子数,桶的可预测数
[0125]hash.1nsert ({luser data}) ;//插入操作[0126]hash.1nsert ({2user data});
[0127]hash.1nsert ({4user data});
[0128]hash.Logic (I, {luser data}) ;//OR 逻辑运算
[0129]hash.Logic (I, {4user data});
[0130]hash.Logic (I, {5user data});
[0131]int size=hash.SizeO ;//获取结果的数量
[0132]for (int i=0; i〈size; i++) {//检查检索的结果
[0133]{bucket} =hash.Next ();
[0134]}
[0135]hash.CleanUp () ; // 释放散列资源
[0136](示例3)检索包括与“名称”有关的“现代”和与“区域”有关的“首尔”的记录。
[0137]检索查询将按逻辑方式表达如下。
[0138]名称(“现代”)AND区域(“汽车”)
[0139]首先，如图12A中所示，根据索引检索关键字“现代”，以使执行到散列中的插入操作。
[0140]接下来，如图10B中所示，根据索引检索关键字“首尔”，以使针对散列执行AND逻
辑运算。
[0141]接着，图12C示出了检索的结果。
[0142]下面，对示例3的程序代码进行描述:
[0143]LogicHash hash;//散列对象
[0144]hash.StartUp (L0GIC_AND, I, 100) ;// 逻辑算子,算子数,桶的可预测数
[0145]hash.1nsert ({luser data}) ;//插入操作
[0146]hash.1nsert ({2user data});
[0147]hash.1nsert ({4user data});
[0148]hash.Logic (I, {luser data}) ;//AND 逻辑运算
[0149]hash.Logic (I, {2user data});
[0150]int size=hash.SizeO ;//获取结果的数量
[0151]for (int i=0; i〈size; i++) {//检查检索的结果
[0152]{bucket} =hash.Next ();
[0153]}
[0154]hash.CleanUp () ; // 释放散列资源
[0155](示例4)检索包括与“名称”有关的“现代”、“汽车”以及“洗车处”的记录。
[0156]检索查询将按逻辑方式表达如下。
[0157]名称(“现代” AND “汽车” AND “洗车处”)
[0158]首先，如图13A中所示，根据索引检索关键字“现代”，以使执行到散列中的插入操作。
[0159]接下来，如图13B中所示，根据索引检索关键字“汽车”，以使针对散列执行第一AND逻辑运算。
[0160]接下来，如图13C中所示，根据索引检索关键字“洗车处”，以使针对散列执行第二AND逻辑运算。
[0161]接着，图13D示出了检索的结果。
[0162]下面，对示例4的程序代码进行描述:
[0163]LogicHash hash;//散列对象
[0164]hash.StartUp (L0GIC_AND, 2, 100) ;// 逻辑算子,算子数,桶的可预测数
[0165]hash.1nsert ({luser data}) ;//插入操作
[0166]hash.1nsert ({2user data});
[0167]hash.1nsert ({4user data});
[0168]hash.Logic (I, {luser data});//第一AND 逻辑运算
[0169]hash.Logic (I, {4user data});
[0170]hash.Logic (I, {5user data});
[0171]hash.Logic (I, {4user data}) ;//第二 AND 逻辑运算
[0172]int size=hash.SizeO ;//获取结果的数量
[0173]for (int i=0; i〈size; i++) {//检查检索的结果
[0174]{bucket} =hash.Next ();
[0175]}
[0176]hash.CleanUp () ; // 释放散列资源
[0177](示例5)检索包括与“名称”有关的“现代”或“天堂”和与“区域”有关的“大田”
的记录。
[0178]检索查询将按逻辑方式表达如下。
[0179]名称(“现代” OR “天堂”)AND区域(“大田”)
[0180]首先，如图14A中所示，根据索引检索关键字“现代”，以使执行到散列中的插入操作。
[0181]接下来，如图14B中所示，根据索引检索关键字“天堂”，以使针对散列执行OR逻辑运算。
[0182]接下来，如图14C中所示，因为逻辑算子从OR改变成AND，所以改变散列数据结构的逻辑状态。
[0183]接下来，如图14D中所示，根据索引检索关键字“大田”，以使针对散列执行AND逻
辑运算。
[0184]接着，图14E示出了检索的结果。
[0185]下面，对示例5的程序代码进行描述:
[0186]LogicHash hash;//散列对象
[0187]hash.StartUp (L0GIC_0R, I, 100) ;//逻辑算子,算子数,桶的可预测数
[0188]hash.1nsert ({luser data}) ;//插入操作
[0189]hash.1nsert ({2user data});
[0190]hash.1nsert ({4user data});
[0191]hash.Logic (I, {3user data}) ;//OR 逻辑运算
[0192]hash.ChangeLogic (L0GIC_AND, I) ; //改变散列数据结构的逻辑状态
[0193]hash.Logic (I, {3user data}) ;//AND 逻辑运算[0194]hash.Logic (I, {4user data});
[0195]int size=hash.SizeO ;//获取结果的数量
[0196]for (int i=0; i〈size; i++) {//检查检索的结果
[0197]{bucket} =hash.Next ();
[0198]}
[0199]hash.CleanUp () ; // 释放散列资源
[0200]本发明的实施方式可以被记录在包括个人计算机(PC)的通用计算机中使用的记录介质中。该记录介质的示例包括:磁存储介质(例如，ROM、软盘、硬盘等)、光学记录介质(例如，⑶-R0M，或DVD)、电记录介质(例如，闪速存储器、存储器棒等)，以及载波(例如，经由因特网传输)。
[0201]工业应用性
[0202]如上所述，根据本发明的上述实施方式中的一个或更多个，利用散列缩减整个资源，以使可以有效地使用有限的系统资源。内存碎片被抑制，使得可以增加可用系统资源。由此，可以平稳地提供服务，并且还可以获取性能增益。
[0203]具体来说，可以增加其中存储器压缩功能比在一般PC中更简单的移动终端上的希望效果。
[0204]虽然本发明已经参照其示例性实施方式进行了具体示出和描述，但本领域普通技术人员应当明白，在不脱离如随附权利要求书中所定义的、本发明的精神和范围的情况下，可以在形式和细节上对本发明进行各种改变。
【权利要求】
1.一种用于利用散列来执行基于全文的逻辑运算的方法，该方法包括以下步骤: Ca)生成具有根据逻辑算子的类型改变的逻辑状态的散列数据结构，以对应于第一逻辑算子； (b)将与第一运算对象数据相对应的散列节点插入到从所述散列数据结构顺序地分配的桶中；以及 (c)如果当前逻辑算子的类型为AND，则选择在步骤(b)中被插入在所述散列数据中的桶或者作为先前运算的结果值而选择的桶当中的、和与第二运算对象数据相对应的散列节点一致的桶，作为结果值，如果当前逻辑算子的类型为0R，则将未从所述散列数据结构检索到的与所述第二运算对象数据相对应的所述散列节点当中的散列节点插入到从所述散列数据结构顺序地分配的所述桶中，并且选择所述散列数据结构内的所有有效桶作为结果值。
2.根据权利要求1所述的方法，所述方法还包括以下步骤:(d)如果当前逻辑算子不同于所述散列数据结构的逻辑状态，则根据当前逻辑算子改变所述散列数据结构的逻辑状态。
3.根据权利要求1所述的方法，其中，所述散列数据结构包括: 散列函数，该散列函数根据其中将散列标识符(ID)用作输入值的MOD运算而生成； 散列表，该散列表是指定与散列键相对应的桶的开始位置的散列节点的列表集；以及 桶块，在该桶块中，每一个桶都包括针对散列链的散列ID和指针。
4.根据权利要求3所述的方法，其中，具有逻辑状态AND的所述散列数据结构的桶还包括用于确定逻辑运算的结果`值的计数器。
5.根据权利要求3所述的方法，其中，在步骤(b)或(c)中分配所述桶的步骤包括:从所述散列数据结构顺序地分配预定桶块内的多个桶当中的未使用桶，如果在所述桶块中不存在未使用桶，则生成新桶块并且在所述新桶块内分配未使用桶。
6.根据权利要求3所述的方法，其中，所述桶块的尺寸被确定为2n，其中，η为整数。
7.根据权利要求6所述的方法，其中，所述散列表的尺寸被确定为比所述桶块的尺寸稍大的质数。
8.根据权利要求3所述的方法，其中，所述散列数据结构还包括: AND计数器，该AND计数器对AND逻辑运算的结果值的数量计数；和 OR计数器，该OR计数器对OR逻辑运算的结果值的数量计数。
9.根据权利要求2所述的方法，其中，步骤(d)包括:如果所述散列数据结构的逻辑状态从AND改变成0R，则生成新散列数据结构，将与现有散列数据结构的结果值相对应的桶插入到所述新散列数据结构中，释放所述现有散列数据结构的所有资源，并且将所述新散列数据结构映射至所述现有散列数据结构。
10.根据权利要求4所述的方法，所述方法还包括以下步骤:(e)如果当前逻辑算子的类型为AND，则仅输出具有和AND逻辑算子的数量相同的计数器数的桶作为来自所述散列数据结构的最终结果值，如果当前逻辑算子的类型为0R，则输出在所述散列数据结构内的所有有效桶作为最终结果值。
11.一种非临时性计算机可读记录介质，该非临时性计算机可读记录介质上记录有散列数据结构和用于利用散列来执行基于全文的逻辑运算的用户接口，其中，所述散列数据结构包括: 散列函数，该散列函数根据其中将散列标识符(ID)用作输入值的MOD运算而生成； 散列表，该散列表是指定与散列键相对应的桶的开始位置的散列节点的列表集；以及 桶块，在该桶块中，每一个桶都包括针对散列链的散列ID和指针，并且 其中，所述用户接口包括: 启动模块，该启动模块生成具有根据逻辑算子的类型改变的逻辑状态的散列数据结构，以对应于第一逻辑算子，并且分配和初始化存储器； 插入模块，该插入模块将与第一运算对象数据相对应的散列节点插入到从所述散列数据结构顺序地分配的桶中；以及 逻辑模块，如果当前逻辑算子的类型为AND，则选择被所述插入模块插入在所述散列数据中的桶或者作为先前运算的结果值而选择的桶当中的、和与第二运算对象数据相对应的散列节点一致的桶，作为结果值，如果当前逻辑算子的类型为0R，则将未从所述散列数据结构检索到的与所述第二运算对象数据相对应的所述散列节点当中的散列节点插入到从所述散列数据结构顺序地分配的所述桶中。
12.根据权利要求11所述的非临时性计算机可读记录介质，其中，所述用户接口还包括逻辑改变模块，如果当前逻辑算子不同于所述散列数据结构的逻辑状态，则所述逻辑改变模块根据当前逻辑算子改变所述散列数据结构的逻辑状态。
13.根据权利要求12所述的非临时性计算机可读记录介质，其中，具有逻辑状态AND的所述散列数据结构的桶还包括用于确定逻辑运算的结果值的计数器，并且 如果所述散列数据结构的逻辑状态从AND改变成0R，则所述逻辑改变模块生成新散列数据结构，将与现有散列数据结构的结果值相对应的桶插入到所述新散列数据结构，释放所述现有散列数据结构的所 有资源，并且将所述新散列数据结构映射至所述现有散列数据结构。
14.根据权利要求11所述的非临时性计算机可读记录介质，其中，所述散列数据结构还包括: AND计数器，该AND计数器对所述AND逻辑运算的结果值的数量计数；和OR计数器，该OR计数器对所述OR逻辑运算的结果值的数量计数，并且其中，所述用户接口还包括尺寸模块，该尺寸模块根据当前逻辑算子的类型输出所述AND计数器或所述OR计数器的值。
15.根据权利要求11所述的非临时性计算机可读记录介质，其中，如果当前逻辑算子的类型为AND，则所述用户接口仅输出具有和AND逻辑算子的数量相同的计数器数的桶作为来自所述散列数据结构的最终结果值，如果当前逻辑算子的类型为0R，则一个接一个地输出在所述散列数据结构内的所有有效桶作为最终结果值。
【文档编号】G06F17/30GK103874996SQ201280025701
【公开日】2014年6月18日 申请日期:2012年10月23日 优先权日:2012年10月17日
【发明者】金在光, 韩赫, 陈成日 申请人:实时科技株式会社
【专利摘要】提供用于利用散列来执行基于全文的逻辑运算的方法，该方法包括：（a）生成具有根据逻辑算子的类型改变的逻辑状态的散列数据结构，以对应于第一逻辑算子；（b）将与第一运算对象数据相对应的散列节点插入到从散列数据结构顺序地分配的桶中；以及（c）如果当前逻辑算子的类型为AND，则选择在步骤（b）中被插入在散列数据中的桶或者作为先前运算的结果值而选择的桶当中的、和与第二运算对象数据相对应的散列节点一致的桶，作为结果值，如果当前逻辑算子的类型为OR，则将未从散列数据结构检索到的与第二运算对象数据相对应的散列节点当中的散列节点插入到从散列数据结构顺序地分配的桶中，并且选择散列数据结构内的所有有效桶作为结果值。
【专利说明】用于利用散列来执行基于全文的逻辑运算的方法
【技术领域】
[0001]本发明涉及用于有效执行被用于从基于全文的数据库中检索关键字的逻辑运算的方法，更具体地，涉及用于在其中系统资源有限的移动终端上利用最小资源来有效执行逻辑运算的方法。
【背景技术】
[0002]信息检索系统是这样一种系统，S卩，该系统从其中被预测是用户所需的信息或数据之前被收集、处理以及操作并且按该信息或数据可以被容易找到的形状累积的数据库中快速检索适于用户需要的信息，该系统向用户提供该信息。
[0003]信息检索系统根据数据库中累积的信息的类型而被分类成引文检索、事实检索，以及全文检索。引文检索是，检索主要操作用户要寻找的主题的文献的书目记录，并且在线信息检索系统(如DIRL0G、BRS等)对应于引文检索。事实检索是，检索一般数据、数值数据以及事实数据，而化学文摘服务在线(CAS)(由此检索化学药品)、电子信息服务(EMIS)(由此检索半导体材料的数据)等属于事实检索的范畴。全文检索是，在需要时从累积文献的全文的数据库中检索书目数据、对应文本或全部原始文本。其中可以检索法律信息的LEXIS或WESTLAS、其中可以检索论文的NEXIS、Dow Jones检索等属于全文检索的范畴。
[0004]对于被用于从基于全文的数据库中检索关键字的逻辑运算来说，需要大容量计算资源。然而，可以在移动环境中使用的计算资源有限，致使检索速度在执行逻辑运算时降低。
[0005]由此，在移动终端上的基于全文的检索系统中，所提供逻辑算子的使用数非常有限，致使不能提供有效关键字检索。
【发明内容】
[0006]本发明提供了一种用于利用散列来执行基于全文的逻辑运算的方法，由此，提出了一种利用散列来估算基于全文的逻辑算子的方法，使得可以在系统资源有限的移动终端上利用最小资源来执行最佳AND/OR逻辑运算，并且使得逻辑运算结果数据可以在执行了逻辑运算之后从外部获得。
[0007]根据本发明一方面，提供了一种用于利用散列来执行基于全文的逻辑运算的方法，该方法包括以下步骤:(a)生成具有根据逻辑算子的类型改变的逻辑状态的散列数据结构，以对应于第一逻辑算子；(b)将与第一运算对象数据相对应的散列节点插入到从所述散列数据结构顺序地分配的桶中；以及(C)如果当前逻辑算子的类型为AND，则选择在步骤(b)中被插入在所述散列数据中的桶或者作为先前运算的结果值而选择的桶当中的、和与第二运算对象数据相对应的散列节点一致的桶，作为结果值，如果当前逻辑算子的类型为0R，则将未从所述散列数据结构检索到的与所述第二运算对象数据相对应的所述散列节点当中的散列节点插入到从所述散列数据结构顺序地分配的所述桶中，并且选择所述散列数据结构内的所有有效桶作为结果值。[0008]根据本发明另一方面，提供了一种计算机可读记录介质，该计算机可读记录介质上记录有散列数据结构和用于利用散列来执行基于全文的逻辑运算的用户接口，其中，所述散列数据结构包括:散列函数，该散列函数根据其中将散列标识符(ID)用作输入值的MOD运算而生成；散列表，该散列表是指定与散列键相对应的桶的开始位置的散列节点的列表集；以及桶块，在该桶块中，每一个桶都包括针对散列链的散列ID和指针，并且其中，所述用户接口包括:启动模块，该启动模块生成具有根据逻辑算子的类型改变的逻辑状态的散列数据结构，以对应于第一逻辑算子，并且分配和初始化存储器；插入模块，该插入模块将与第一运算对象数据相对应的散列节点插入到从所述散列数据结构顺序地分配的桶中；以及逻辑模块，如果当前逻辑算子的类型为AND，则选择被所述插入模块插入在所述散列数据中的桶或者作为先前运算的结果值而选择的桶当中的、和与第二运算对象数据相对应的散列节点一致的桶，作为结果值，如果当前逻辑算子的类型为0R，则将未从所述散列数据结构检索到的与所述第二运算对象数据相对应的所述散列节点当中的散列节点插入到从所述散列数据结构顺序地分配的所述桶中。
【专利附图】
【附图说明】
[0009]图1例示了根据本发明的实施方式的、在用于利用散列来执行基于全文的逻辑运算的方法中所使用的散列数据结构；
[0010]图2例示了在本发明中使用的用户接口当中执行启动模块的操作；
[0011]图3例示了在本发明中使用的用户接口当中执行清除模块的操作；
[0012]图4例示了在本发明中使用的用户接口当中执行插入模块的操作；
[0013]图5例示了在本发明中使用的用户接口当中执行逻辑模块的操作；
[0014]图6例示了在本发明中使用的用户接口当中执行逻辑改变模块的操作；
[0015]图7例示了在本发明中使用的用户接口当中执行尺寸模块的操作；
[0016]图8例示了在本发明中使用的用户接口当中执行下一个(Next)模块的操作；
[0017]图9A到9C例示了根据本发明实施方式的表和索引；以及
[0018]图1OA到14E例示了根据本发明实施方式的检索的插入操作、逻辑运算以及结果。
【具体实施方式】
[0019]下面，参照附图，对本发明进行更全面描述，其中，示出了本发明的示例性实施方式。
[0020]下面，参照图1，对根据本发明实施方式的、在用于利用散列来执行基于全文的逻辑运算的方法中所使用的散列数据结构进行描述。
[0021]在本发明中使用的散列数据结构可以包括:散列函数(未示出)、散列表10、桶块20、光标40、AND计数器50，以及OR计数器51。
[0022]散列函数是其中通过输入散列标识符(ID)而生成散列键的函数。散列函数可以通过MOD运算来生成。而且，全文数据库的记录ID被用作散列ID。
[0023]散列表10是指定与散列键相对应的桶30的开始位置的散列节点的列表集。散列表10的尺寸利用由用户输入的预计数(PreCount)来确定,并且可以被确定为比桶块20的尺寸更大一点的质数，以用于桶30的均匀分布。[0024]作为被插入到散列中的数据结构的桶30每一个均包括针对散列链32的散列ID和指针，以在散列彼此冲突时检索对应桶30。用于确定针对散列节点的、要通过用户输入的逻辑运算的结果值和数据(用户数据I和用户数据2)的计数器可以包括在桶30中。
[0025]桶块20是存储缓冲区，该存储缓冲区利用作为要插入到散列中的桶30的可预测数的预计数来预先生成。
[0026]光标40被用于指定桶块20上的桶30的位置，并且支持容易从外部获取的逻辑运
算的结果。
[0027]AND计数器50被用于计数AND逻辑运算的结果值的数量，而OR计数器51被用于计数OR逻辑运算的结果值的数量。
[0028]在本发明中，设置作为存储器管理器60的模块，并且存储器管理器60管理在散列中使用的存储器，具体来说，管理自动添加要插入当前桶的位置信息和桶块20的功能。存储器管理器60根据预定范围预先指定桶块20的尺寸，并且确定根据从用户输入的PreCount值所属于的范围的值，作为要生成的桶块20的尺寸。这里，桶块20的尺寸可以被确定为2n (其中，η是整数)以易于存储器管理。由用户输入的PreCount可以指定，以使两个或三个桶30可以呈现在散列链32内。有效的是，通过索引在与逻辑运算的第一运算对象数据相对应的集合中使用许多散列节点。
[0029]如果实际插入的桶30的数量大于桶块20的尺寸，则存储器管理器60自动生成新的桶块20。由此，在根据现有技术的散列数据结构中，只要当在散列彼此冲突时生成桶30时，都需要分配新的存储器空间，并且桶需要按连接列表形状配置。然而，根据本发明，已经在桶块20内生成的桶30可以顺序地分配并且可以按连接列表形状配置。
[0030]在本发明中使用的用户接口包括:启动、清除、插入、逻辑、逻辑改变、尺寸，以及下一个。
[0031](I)启动模块
[0032]如图2所示，启动模块执行初始化和资源分配以使用散列。
[0033]输入值由逻辑算子、算子数以及桶的可预测数PreCount组成。
[0034]逻辑算子是AND或0R。
[0035]算子数是其中AND或OR逻辑算子连续出现的数量。例如，当逻辑运算“A AND BAND C”呈现在集合A、B以及C上时，算子数为2。
[0036]桶的可预测数PreCount被用作用来确定散列表10的尺寸和桶块20的尺寸的重要输入值。
[0037]下面，对要由启动模块执行的操作进行描述。
[0038]初始化逻辑运算Hash (散列)的所有变量项(S100)。
[0039]桶块20的尺寸和散列表10的尺寸利用由用户输入的值PreCount确定(S110)。桶管理器60根据预定范围预先指定桶块20的尺寸，并且确定根据从用户输入的PreCount值所属于的范围的值，作为要生成的桶块20的尺寸。这里，桶块20的尺寸可以被确定为2n(其中，η是整数)以易于存储器管理。而且，散列表10的尺寸被确定为比桶块20的尺寸更大一点的质数。
[0040]利用散列表10的所确定尺寸将存储器分配给散列表10，并且初始化存储器(S120)。[0041]随后，生成具有根据输入逻辑算子的类型AND或OR改变的逻辑状态的散列数据结构(S130、S140)。即，桶的类型被分类成用于AND逻辑运算的桶30a和用于OR逻辑运算的桶30b，并且计数器被附加地包括在用于AND逻辑运算的桶30a中。该计数器被用于执行AND逻辑运算。在处于AND逻辑状态的散列数据结构中，仅可以执行AND逻辑运算，而在处于OR逻辑状态的散列数据结构中，仅可以执行OR逻辑运算。然而，如果逻辑算子的类型被改变成另一类型，则散列数据结构的逻辑状态可以通过下面将描述的逻辑改变模块来改变。
[0042](2)清除模块
[0043]如图3所示，清除模块执行完成所有逻辑运算的功能和释放散列内的资源的功倉泛。
[0044]不存在输入值。
[0045]下面，对要由清除模块执行的操作进行描述。
[0046]返回桶块20的存储器(S200)，并且返回散列表10的存储器(S210)，接着初始化所有变量项(S220)。
[0047](3)插入模块
[0048]如图4所示，插入模块将第一运算对象数据插入到已初始化散列数据结构中，以执行逻辑运算。如果集合A和B上存在运算“A AND B”，则插入模块执行将集合A的元素之一插入散列中的功能。
[0049]输入值是要作为散列节点输入的用户数据资料。
[0050]散列节点(数据资料):由要在散列函数中使用的散列ID和由用户输入的其它数据组成。
[0051]下面，对要由插入模块执行的操作进行描述。
[0052]首先，检索要输入的数据是否已经存在于散列中(S300)。即，检索散列中是否存在具有和输入散列节点的散列ID相同的散列ID的桶。
[0053]作为检索的结果，如果存在已经存在于散列中的数据，则不执行操作。
[0054]作为检索的结果，如果散列中不存在数据，则从存储器管理器60分配一个桶(S310)，并且利用散列函数生成散列键(S320)，接着将所分配桶连接至对应于该散列键的散列链(S330 )，从而将输入数据记录在所分配桶中(S340 )。
[0055]OR计数器值增加I (S350)。
[0056](4)逻辑模块
[0057]如图5所示，逻辑模块通过输入在逻辑算子之后放置的运算对象来执行逻辑运算。如果集合A和B上存在运算“A AND B”，则逻辑模块在集合B的多个元素之一上按散列执行AND运算函数，而如果集合A和B上存在运算“A OR B”，则逻辑模块在集合B的多个元素之一上按散列执行OR运算函数。
[0058]输入值由算子编号和散列节点(数据资料)组成。
[0059]算子编号:意指连续相同逻辑运算中的逻辑算子的顺序。例如，当存在逻辑运算“AAND B AND C AND D”时，算子数为3，而当执行第一逻辑运算(A AND B)时，算子编号为1，当执行第二逻辑运算((第一逻辑运算的结果)AND C)时，算子编号为2，当执行第三逻辑运算((第二逻辑运算的结果)AND D)时，算子编号为3。[0060]散列节点(数据资料):由要在散列函数中使用的散列ID和由用户输入的其它数据组成。
[0061]如果当前逻辑算子的类型为AND，则逻辑模块选择在通过插入模块插入在散列数据结构中的桶或者作为先前运算的结果值而选择的桶当中的和与第二运算对象数据相对应的散列节点一致的桶，作为结果值。另一方面，在当前逻辑算子的类型为OR时，如果没有从散列数据结构检索到与第二运算对象数据相对应的散列节点，则逻辑模块执行将散列节点插入到从散列数据结构顺序地分配的桶中的操作。下面，对其详细操作进行描述。
[0062]首先，执行要输入的数据是否已经存在于散列中的检索(S400)。即，检索散列中是否存在具有和输入散列节点的散列ID相同的散列ID的桶。
[0063]作为操作S400中的检索的结果，如果检索到该数据已经存在于散列中，则检查当前逻辑算子是AND还是0R(S410)。当前逻辑算子被设置为通过启动模块输入的逻辑算子，如果执行逻辑改变模块，则将当前逻辑算子改变成最近输入的逻辑算子。
[0064]作为操作S400中的检索的结果，如果检索到要输入的数据已经存在于散列中并且当前逻辑算子为AND，则当检索到的桶的计数器值和通过将输入算子编号减去I而获取的值相同(直至先前运算作为AND逻辑运算的结果值的桶)时(S420)，检索到的桶的计数器值增加I (当前运算的结果值)(S430)，如果检索到的桶的计数器的增加的计数器值与通过启动模块或逻辑改变模块输入的算子的数量一致(AND运算的最终结果值)(S440)，则AND计数器值增加I (S450)。与此相反，当检索到的桶的计数器值和通过将输入的算子的数量减去I而获取的值不同，或者检索到的桶的增加的计数器值和通过启动模块或逻辑改变模块输入的算子的数量不同时，不执行操作。
[0065]如果在操作S400中的检索没有结果，则检查当前逻辑算子是AND还是0R(S460)。
[0066]如果操作S400中的检索没有结果并且当前逻辑算子为AND，则不执行操作。
[0067]如果操作S400中的检索没有结果并且当前逻辑算子为0R，则从存储器管理器60分配一个桶(S470 )，并且利用散列函数生成散列键(S480 )，接着将所分配桶连接至对应于该散列键的散列链(S490)，并且将输入数据记录在所分配桶中(S500)，并接着OR计数器值增加 I (S510)。
[0068](5)逻辑改变模块
[0069]当逻辑算子改变时使用逻辑改变模块。逻辑改变模块执行改变散列的逻辑状态的功能。如果运算“(A AND B) OR C”呈现在集合A、B以及C上，则逻辑改变模块在执行了AND逻辑运算之后执行将散列的逻辑状态从AND改变成OR的功能。
[0070]输入值由逻辑算子和算子数组成。
[0071 ] 逻辑算子:AND或OR
[0072]算子数:其中AND或OR算子连续出现的数量
[0073]参照图6，对利用逻辑改变模块来将AND改变为OR的操作进行描述。
[0074]首先，新散列数据结构利用逻辑算子和作为输入值的算子数以及在当前散列数据结构中设置的桶的可预测数PreCount而内部地设置(S600 )。在这种情况下，使用上述启动模块。
[0075]随后，根据当前散列数据结构仅获取结果值，并且利用下面将描述的下一个(Next)模块将结果值插入到新散列数据结构中，接着将当前散列数据结构中的变量项映射至新散列数据结构的变量项(S610)。
[0076]随后，利用清除模块从当前散列数据结构释放存储器资源(S620)。
[0077]随后，将内部生成的新散列数据结构的变量项和指针映射至当前散列数据结构(S630)，并且仅内部生成的新散列数据结构的对象数据被消除(S640)。在这种情况下，新散列数据结构未被清除。
[0078]为了实现逻辑改变模块，存储散列内部的多个项当中的用户输入数据的缓冲区(散列表、桶块)需要利用指针从堆中分配。由此，当前散列数据结构的逻辑状态可以改变成新逻辑状态。
[0079]通过执行上述操作，当逻辑算子从AND改变成OR时，分配给散列数据结构的存储器的尺寸可以显著减小。
[0080]因为在通过逻辑改变模块执行从OR向AND改变的操作的同时所分配存储器的尺寸未减小，所以简单地改变当前散列数据结构的逻辑状态。在这种情况下，当前散列数据结构的桶改变成用于AND逻辑运算的桶30a。
[0081](6)尺寸模块
[0082]参照图7，尺寸模块执行将逻辑运算的结果的数量返回给用户的功能。
[0083]不存在输入值。
[0084]检查当前逻辑算子是AND还是0R(S700)，如果散列数据结构的逻辑状态是AND逻辑状态，则返回AND计数器值(S710)，如果散列数据结构的逻辑状态是OR逻辑状态，则返回OR计数器值(S720)。
[0085]( 7 )下一个(Next)模块
[0086]参照图8，下一个(Next)模块在执行了逻辑运算之后执行向用户返回逻辑运算的结果的功能。
[0087]不存在输入值。
[0088]对于下一个(Next)模块的情况来说，在当前逻辑算子的类型为AND时(在当前散列数据结构是在执行了 AND逻辑运算之后时)，从散列数据结构仅检索具有和AND逻辑算子的数量相同的计数器数的桶，并且设置为最终结果值，从而将放置光标的桶内的用户数据一个接一个地输出。在当前逻辑算子的类型为OR时(在当前散列数据结构是在执行了 OR逻辑运算之后时)，散列数据结构内的所有有效桶被设置为最终结果值，从而将放置光标的桶内的用户数据一个接一个地输出。下面，对其详细操作进行描述。
[0089]检查当前逻辑算子是AND还是0R(S800)，如果散列数据结构的逻辑状态是AND逻辑状态，则光标值增加1，并且在光标的位置中获取桶(S810)。
[0090]如果所获取桶无效，则散列数据结构内的所有桶块被舍去(rounded)，将“没有数据”返回给用户(S820)。
[0091]如果所获取桶有效，则桶内的计数器值和算子数彼此进行比较，如果计数器值和算子数相同，则返回桶内的用户数据(S830)，而如果计数器值和算子数不同，则该操作返回至操作S810。
[0092]如果散列数据结构的逻辑状态是OR逻辑状态，则光标值增加1，并且在光标的位置中获取桶(S840)。
[0093]如果所获取桶有效，则返回桶内的用户数据(S850)，而如果所获取桶无效，则散列数据结构内的所有桶块被舍去(rounded)，并且将“没有数据”返回给用户。
[0094]下面，参照下列示例，对根据本发明的、用于利用散列来执行基于全文的逻辑运算的方法进行描述。
[0095]假定在图9B和9C中示出与图9A中所示“表A”有关的“名称B+索引”和“区域B+索引”中的每一个。
[0096](示例I)检索包括与“名称”有关的“现代”和“汽车”的记录。
[0097]检索查询将按逻辑方式表达如下。
[0098]名称(“现代” AND “汽车”)
[0099]首先，如图1OA中所示，根据索引检索关键字“现代”，以使执行到散列中的插入操作。
[0100]接下来，如图1OB中所示，根据索引检索关键字“汽车”，以使针对散列执行AND逻
辑运算。
[0101]接着，图1OC中示出了检索的结果。
[0102]下面，对示例I的程序代码进行描述:
[0103]LogicHash hash;//散列对象
[0104]hash.StartUp (L0GIC_AND, I, 100) ;// 逻辑算子,算子数,桶的可预测数
[0105]hash.1nsert ({luser data}) ;//插入操作
[0106]hash.1nsert ({2user data});
[0107]hash.1nsert ({4user data});
[0108]hash.Logic (I, {luser data}) ;//AND 逻辑运算
[0109]hash.Logic (I, {4user data});
[0110]hash.Logic (I, {5user data});
[0111]int size=hash.SizeO ;//获取结果的数量
[0112]for (int i=0; i〈size; i++) {//检查检索的结果
[0113]{bucket} =hash.Next ();
[0114]}
[0115]hash.CleanUp () ; // 释放散列资源
[0116](示例2)检索包括与“名称”有关的“现代”或“汽车”的记录。
[0117]检索查询将按逻辑方式表达如下。
[0118]名称(“现代” OR “汽车”)
[0119]首先，如图1lA中所示，根据索引检索关键字“现代”，以使执行到散列中的插入操作。
[0120]接下来，如图1lB中所示，根据索引检索关键字“汽车”，以使针对散列执行OR逻辑运算。
[0121]接着，图1lC示出了检索的结果。
[0122]下面，对示例2的程序代码进行描述:
[0123]LogicHash hash;//散列对象
[0124]hash.StartUp (L0GIC_0R, I, 100) ;//逻辑算子,算子数,桶的可预测数
[0125]hash.1nsert ({luser data}) ;//插入操作[0126]hash.1nsert ({2user data});
[0127]hash.1nsert ({4user data});
[0128]hash.Logic (I, {luser data}) ;//OR 逻辑运算
[0129]hash.Logic (I, {4user data});
[0130]hash.Logic (I, {5user data});
[0131]int size=hash.SizeO ;//获取结果的数量
[0132]for (int i=0; i〈size; i++) {//检查检索的结果
[0133]{bucket} =hash.Next ();
[0134]}
[0135]hash.CleanUp () ; // 释放散列资源
[0136](示例3)检索包括与“名称”有关的“现代”和与“区域”有关的“首尔”的记录。
[0137]检索查询将按逻辑方式表达如下。
[0138]名称(“现代”)AND区域(“汽车”)
[0139]首先，如图12A中所示，根据索引检索关键字“现代”，以使执行到散列中的插入操作。
[0140]接下来，如图10B中所示，根据索引检索关键字“首尔”，以使针对散列执行AND逻
辑运算。
[0141]接着，图12C示出了检索的结果。
[0142]下面，对示例3的程序代码进行描述:
[0143]LogicHash hash;//散列对象
[0144]hash.StartUp (L0GIC_AND, I, 100) ;// 逻辑算子,算子数,桶的可预测数
[0145]hash.1nsert ({luser data}) ;//插入操作
[0146]hash.1nsert ({2user data});
[0147]hash.1nsert ({4user data});
[0148]hash.Logic (I, {luser data}) ;//AND 逻辑运算
[0149]hash.Logic (I, {2user data});
[0150]int size=hash.SizeO ;//获取结果的数量
[0151]for (int i=0; i〈size; i++) {//检查检索的结果
[0152]{bucket} =hash.Next ();
[0153]}
[0154]hash.CleanUp () ; // 释放散列资源
[0155](示例4)检索包括与“名称”有关的“现代”、“汽车”以及“洗车处”的记录。
[0156]检索查询将按逻辑方式表达如下。
[0157]名称(“现代” AND “汽车” AND “洗车处”)
[0158]首先，如图13A中所示，根据索引检索关键字“现代”，以使执行到散列中的插入操作。
[0159]接下来，如图13B中所示，根据索引检索关键字“汽车”，以使针对散列执行第一AND逻辑运算。
[0160]接下来，如图13C中所示，根据索引检索关键字“洗车处”，以使针对散列执行第二AND逻辑运算。
[0161]接着，图13D示出了检索的结果。
[0162]下面，对示例4的程序代码进行描述:
[0163]LogicHash hash;//散列对象
[0164]hash.StartUp (L0GIC_AND, 2, 100) ;// 逻辑算子,算子数,桶的可预测数
[0165]hash.1nsert ({luser data}) ;//插入操作
[0166]hash.1nsert ({2user data});
[0167]hash.1nsert ({4user data});
[0168]hash.Logic (I, {luser data});//第一AND 逻辑运算
[0169]hash.Logic (I, {4user data});
[0170]hash.Logic (I, {5user data});
[0171]hash.Logic (I, {4user data}) ;//第二 AND 逻辑运算
[0172]int size=hash.SizeO ;//获取结果的数量
[0173]for (int i=0; i〈size; i++) {//检查检索的结果
[0174]{bucket} =hash.Next ();
[0175]}
[0176]hash.CleanUp () ; // 释放散列资源
[0177](示例5)检索包括与“名称”有关的“现代”或“天堂”和与“区域”有关的“大田”
的记录。
[0178]检索查询将按逻辑方式表达如下。
[0179]名称(“现代” OR “天堂”)AND区域(“大田”)
[0180]首先，如图14A中所示，根据索引检索关键字“现代”，以使执行到散列中的插入操作。
[0181]接下来，如图14B中所示，根据索引检索关键字“天堂”，以使针对散列执行OR逻辑运算。
[0182]接下来，如图14C中所示，因为逻辑算子从OR改变成AND，所以改变散列数据结构的逻辑状态。
[0183]接下来，如图14D中所示，根据索引检索关键字“大田”，以使针对散列执行AND逻
辑运算。
[0184]接着，图14E示出了检索的结果。
[0185]下面，对示例5的程序代码进行描述:
[0186]LogicHash hash;//散列对象
[0187]hash.StartUp (L0GIC_0R, I, 100) ;//逻辑算子,算子数,桶的可预测数
[0188]hash.1nsert ({luser data}) ;//插入操作
[0189]hash.1nsert ({2user data});
[0190]hash.1nsert ({4user data});
[0191]hash.Logic (I, {3user data}) ;//OR 逻辑运算
[0192]hash.ChangeLogic (L0GIC_AND, I) ; //改变散列数据结构的逻辑状态
[0193]hash.Logic (I, {3user data}) ;//AND 逻辑运算[0194]hash.Logic (I, {4user data});
[0195]int size=hash.SizeO ;//获取结果的数量
[0196]for (int i=0; i〈size; i++) {//检查检索的结果
[0197]{bucket} =hash.Next ();
[0198]}
[0199]hash.CleanUp () ; // 释放散列资源
[0200]本发明的实施方式可以被记录在包括个人计算机(PC)的通用计算机中使用的记录介质中。该记录介质的示例包括:磁存储介质(例如，ROM、软盘、硬盘等)、光学记录介质(例如，⑶-R0M，或DVD)、电记录介质(例如，闪速存储器、存储器棒等)，以及载波(例如，经由因特网传输)。
[0201]工业应用性
[0202]如上所述，根据本发明的上述实施方式中的一个或更多个，利用散列缩减整个资源，以使可以有效地使用有限的系统资源。内存碎片被抑制，使得可以增加可用系统资源。由此，可以平稳地提供服务，并且还可以获取性能增益。
[0203]具体来说，可以增加其中存储器压缩功能比在一般PC中更简单的移动终端上的希望效果。
[0204]虽然本发明已经参照其示例性实施方式进行了具体示出和描述，但本领域普通技术人员应当明白，在不脱离如随附权利要求书中所定义的、本发明的精神和范围的情况下，可以在形式和细节上对本发明进行各种改变。
【权利要求】
1.一种用于利用散列来执行基于全文的逻辑运算的方法，该方法包括以下步骤: Ca)生成具有根据逻辑算子的类型改变的逻辑状态的散列数据结构，以对应于第一逻辑算子； (b)将与第一运算对象数据相对应的散列节点插入到从所述散列数据结构顺序地分配的桶中；以及 (c)如果当前逻辑算子的类型为AND，则选择在步骤(b)中被插入在所述散列数据中的桶或者作为先前运算的结果值而选择的桶当中的、和与第二运算对象数据相对应的散列节点一致的桶，作为结果值，如果当前逻辑算子的类型为0R，则将未从所述散列数据结构检索到的与所述第二运算对象数据相对应的所述散列节点当中的散列节点插入到从所述散列数据结构顺序地分配的所述桶中，并且选择所述散列数据结构内的所有有效桶作为结果值。
2.根据权利要求1所述的方法，所述方法还包括以下步骤:(d)如果当前逻辑算子不同于所述散列数据结构的逻辑状态，则根据当前逻辑算子改变所述散列数据结构的逻辑状态。
3.根据权利要求1所述的方法，其中，所述散列数据结构包括: 散列函数，该散列函数根据其中将散列标识符(ID)用作输入值的MOD运算而生成； 散列表，该散列表是指定与散列键相对应的桶的开始位置的散列节点的列表集；以及 桶块，在该桶块中，每一个桶都包括针对散列链的散列ID和指针。
4.根据权利要求3所述的方法，其中，具有逻辑状态AND的所述散列数据结构的桶还包括用于确定逻辑运算的结果`值的计数器。
5.根据权利要求3所述的方法，其中，在步骤(b)或(c)中分配所述桶的步骤包括:从所述散列数据结构顺序地分配预定桶块内的多个桶当中的未使用桶，如果在所述桶块中不存在未使用桶，则生成新桶块并且在所述新桶块内分配未使用桶。
6.根据权利要求3所述的方法，其中，所述桶块的尺寸被确定为2n，其中，η为整数。
7.根据权利要求6所述的方法，其中，所述散列表的尺寸被确定为比所述桶块的尺寸稍大的质数。
8.根据权利要求3所述的方法，其中，所述散列数据结构还包括: AND计数器，该AND计数器对AND逻辑运算的结果值的数量计数；和 OR计数器，该OR计数器对OR逻辑运算的结果值的数量计数。
9.根据权利要求2所述的方法，其中，步骤(d)包括:如果所述散列数据结构的逻辑状态从AND改变成0R，则生成新散列数据结构，将与现有散列数据结构的结果值相对应的桶插入到所述新散列数据结构中，释放所述现有散列数据结构的所有资源，并且将所述新散列数据结构映射至所述现有散列数据结构。
10.根据权利要求4所述的方法，所述方法还包括以下步骤:(e)如果当前逻辑算子的类型为AND，则仅输出具有和AND逻辑算子的数量相同的计数器数的桶作为来自所述散列数据结构的最终结果值，如果当前逻辑算子的类型为0R，则输出在所述散列数据结构内的所有有效桶作为最终结果值。
11.一种非临时性计算机可读记录介质，该非临时性计算机可读记录介质上记录有散列数据结构和用于利用散列来执行基于全文的逻辑运算的用户接口，其中，所述散列数据结构包括: 散列函数，该散列函数根据其中将散列标识符(ID)用作输入值的MOD运算而生成； 散列表，该散列表是指定与散列键相对应的桶的开始位置的散列节点的列表集；以及 桶块，在该桶块中，每一个桶都包括针对散列链的散列ID和指针，并且 其中，所述用户接口包括: 启动模块，该启动模块生成具有根据逻辑算子的类型改变的逻辑状态的散列数据结构，以对应于第一逻辑算子，并且分配和初始化存储器； 插入模块，该插入模块将与第一运算对象数据相对应的散列节点插入到从所述散列数据结构顺序地分配的桶中；以及 逻辑模块，如果当前逻辑算子的类型为AND，则选择被所述插入模块插入在所述散列数据中的桶或者作为先前运算的结果值而选择的桶当中的、和与第二运算对象数据相对应的散列节点一致的桶，作为结果值，如果当前逻辑算子的类型为0R，则将未从所述散列数据结构检索到的与所述第二运算对象数据相对应的所述散列节点当中的散列节点插入到从所述散列数据结构顺序地分配的所述桶中。
12.根据权利要求11所述的非临时性计算机可读记录介质，其中，所述用户接口还包括逻辑改变模块，如果当前逻辑算子不同于所述散列数据结构的逻辑状态，则所述逻辑改变模块根据当前逻辑算子改变所述散列数据结构的逻辑状态。
13.根据权利要求12所述的非临时性计算机可读记录介质，其中，具有逻辑状态AND的所述散列数据结构的桶还包括用于确定逻辑运算的结果值的计数器，并且 如果所述散列数据结构的逻辑状态从AND改变成0R，则所述逻辑改变模块生成新散列数据结构，将与现有散列数据结构的结果值相对应的桶插入到所述新散列数据结构，释放所述现有散列数据结构的所 有资源，并且将所述新散列数据结构映射至所述现有散列数据结构。
14.根据权利要求11所述的非临时性计算机可读记录介质，其中，所述散列数据结构还包括: AND计数器，该AND计数器对所述AND逻辑运算的结果值的数量计数；和OR计数器，该OR计数器对所述OR逻辑运算的结果值的数量计数，并且其中，所述用户接口还包括尺寸模块，该尺寸模块根据当前逻辑算子的类型输出所述AND计数器或所述OR计数器的值。
15.根据权利要求11所述的非临时性计算机可读记录介质，其中，如果当前逻辑算子的类型为AND，则所述用户接口仅输出具有和AND逻辑算子的数量相同的计数器数的桶作为来自所述散列数据结构的最终结果值，如果当前逻辑算子的类型为0R，则一个接一个地输出在所述散列数据结构内的所有有效桶作为最终结果值。
【文档编号】G06F17/30GK103874996SQ201280025701
【公开日】2014年6月18日 申请日期:2012年10月23日 优先权日:2012年10月17日
【发明者】金在光, 韩赫, 陈成日 申请人:实时科技株式会社
最新回复(0)