Rapid identification of repeated patterns in strings, trees and arrays

Abstract

Many computational processes involve the detection of repeated patterns within a structure such as a string, tree or array. Parsing algorithms usually contain procedures for detecting matches in certain portions of the input string. Similarly, in the construction of symbol tables, matching entries are checked for. Then again, the optimization process in a compiler involves a search for repeated expressions. In processes which modify large files or data bases a check is often made to see if a given item is present, or to find all items in the file that contain a given item. When two lists of items are to be combined it is often desired that items with the same keys be placed together but that no other order of storing keys is required. Finally, it may be possible to compress the amount of storage required to store a structure with many repeated patterns by storing one copy of each pattern together with the locations of the pattern within the structure rather than storing the complete structure. In all of these problems a part of the process involves the detection of repeated patterns.