Sequential pattern memory searching and storage management technique

Abstract

The adaptive sequential pattern memory search technique only examines the contents of a subset of the total number of memory locations in each search for information representative of a character string. The subset includes a plurality of storage locations and each examination is performed in one concurrent read operation. If the character string is not matched, the memory must be updated to store information representative of the unmatched string. This updating process selects one location from the subset for storing this representative information. Advantageously, an indicator of when each stored representative information last matched a character string is maintained and utilized in the selection process. In addition, to avoid operational errors associated with outputting invalid information from the 'child' of a previously discarded 'parent', an indication of the time each stored entry is created is utilized to remove such invalid information as it is detected in the updating process.