公开(公告)号：US5787430A

公开(公告)日：1998-07-28

申请号：US765764

申请日：1996-12-17

申请人： Willibald Doeringer ,  Douglas Dykeman ,  Gunter Karjoth ,  Mehdi Nassehi ,  Mohan Sharma

发明人： Willibald Doeringer ,  Douglas Dykeman ,  Gunter Karjoth ,  Mehdi Nassehi ,  Mohan Sharma

IPC分类号： G06F17/30 ,  H04L12/741 ,  H04L12/743

CPC分类号： H04L45/7457 ,  H04L45/54 ,  Y10S707/99933

摘要： The building, maintenance, and use of a database is described having a trie-like structure for storing entries and retrieving an at least partial match, preferably the longest partial match, or all partial matches of a search argument (input key) from said entries, said database having nodes (20), with each node containing first link information (21) leading to at least one previous node (parent pointer) and second link information (25,26) leading to at least one following node (child pointer), at least a stored key (entry, 23, 24), or a combination, thereof. The particular structure of the nodes allows a two-step search process, in which segments of a search argument are firstly used to determine a search path through the trie-like database, said search path being backtracked in the second part of the search. During the second part of the search the entire search argument is compared to entries stored in the nodes until a match is found. The described database allows an efficient use of memories and is advantageously applied to fast data retrieval, in particular related to communication within computer networks. No recursive procedures are applied.

摘要翻译： PCT No.PCT / EP94 / 02135 Sec。 371日期1996年12月17日第 102（e）日期1996年12月17日PCT提交1994年6月30日PCT公布。 第WO96 / 00945号公报 日期1996年1月11日描述数据库的构建，维护和使用被描述为具有类似于trie的结构，用于存储条目并且检索至少部分匹配，优选最长部分匹配或搜索参数的所有部分匹配（输入 密钥），所述数据库具有节点（20），每个节点包含通向至少一个先前节点（父指针）的第一链路信息（21）和导致至少一个跟随的第二链路信息（25,26） 节点（子指针），至少存储的密钥（条目23,24）或其组合。 节点的特定结构允许两步搜索过程，其中首先使用搜索参数的段来确定通过类似于trie的数据库的搜索路径，所述搜索路径在搜索的第二部分中被回溯。 在搜索的第二部分期间，将整个搜索参数与存储在节点中的条目进行比较，直到找到匹配。 所描述的数据库允许有效地使用存储器，并且有利地应用于快速数据检索，特别是涉及计算机网络内的通信。 不应用递归过程。