Detection of maximal repeating patterns and limited length repeating patterns

TR Number

Date

1995

Journal Title

Journal ISSN

Volume Title

Publisher

Virginia Tech

Abstract

Given a string of characters, that string may contain patterns of characters that occur more than once. These are Repeating Patterns. A Maximal Repeating Pattern (MRP) is a repeating pattern that is not a substring of a longer repeating pattern or occurs at least once where it is not a substring of another repeating pattern. This report rigorously addresses the computation of MRPs and proposes two new categories of repeating patterns whose computational bounds are more attractive for use in human-computer interaction where the computational complexity is a significant issue.

A modified trie is used to find Maximal Repeating Patterns in a given text string. The advantages in time complexity and memory usage gained by limiting the length of MRPs and the usefulness of limiting the spatial context of repeating patterns when processing large data sets are explored.

Description

Keywords

Citation