Patent ID: 8521751
Filing Date: 2013-08-27
Classification: G06F

Abstract:
1. A search device which carries out a longest prefix match search based on registered patterns and a search key which are character strings, comprising: a processor; a dividing position list which stores a plurality of dividing positions for dividing a character string; a vector which is an array of numerical values; a hash table which stores said registered patterns; a first prefix extraction unit which selects one largest dividing position which does not exceed a length of an inputted registered pattern from said dividing position list, extracts a prefix from said inputted registered pattern with said selected dividing position as a boundary, and obtains a suffix length by subtracting the length of said prefix from the length of said inputted registered pattern; a first hash execution unit which calculates a plurality of hash values by applying a plurality of hash functions to the prefix extracted by said first prefix extraction unit; a vector update unit which calculates a plurality of numerical values by adding the plurality of hash values calculated by said first hash execution unit and said suffix length, treats said plurality of numerical values which are calculated as a plurality of addresses in said vector, and updates each content corresponding to said plurality of addresses to a numerical value which is different from an initial value; a hash table registration unit which stores said inputted registered pattern in said hash table; a second prefix extraction unit which selects a dividing position which does not exceed a length of an inputted search key in descending order from said dividing position list and extracts one or more prefix from said inputted search key with said selected dividing position as a boundary; a second hash execution unit which calculates a plurality of hash values by applying a plurality of the same hash functions as used by said first hash execution unit to the prefix extracted by said second prefix extraction unit; a pattern length estimation unit which calculates a plurality of numerical values by adding the plurality of hash values calculated by said second hash execution unit and an offset, treats said plurality of numerical values which are calculated as a plurality of addresses in said vector, and calculates a sum of a length of the prefix extracted by said second prefix extraction unit and said offset as a length of a matching candidate in case all of contents corresponding to said plurality of addresses are different from initial values; and a hash table search unit which extracts a character string which is equal to a length of a matching candidate calculated by said pattern length estimation unit from beginning of said inputted search key and searches said hash table for a registered pattern which matches exactly with said character string which is extracted.