The Efficient way to Identify the Regular Expression in Text Databases

Abstract

Given a list of n strings of length at most k, where l is length of the largest string. The object is to cover the strings by a minimal number of regular expressions r1, r2, r3………………..,rm for m≥1,such that a) Every string in the database satisfies at least one ri and b) Any string ‘X’ of length at most K satisfying r1+r2+r3+……………….+rm is at a distance at most p from a string ‘y’ in the database ,where ‘p’ is a prescribed constant parameter.We assume that the database is in the form of B+ tree. We start with leaf nodes and collection all the strings of maximum length in the database For identifying regular expressions in database the thesis aims at developing a procedure similar to that for Boolean formulas (in DNF or CNF), where the function values and don’t care term’s are specified.