원문정보
초록
영어
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.
목차
1. Introduction
1.1 Survey of the Paper
1.2 Flow of the Paper
2. B+ Tree
2.1 B+ tree properties
2.2 Main Characteristics
2.3 Example of a B+ -tree
3. Dynamic Programming Algorthim (Dpa) To Edit Distance
3.1 Algorithm
3.2 Example
4. Regular Expressions
4.1 Identities For Regular Expressions
4.2 Regular Expressions Notation
4.3 Boolean ‘OR’
4.4 Basic operations for creating regular expressions
4.5 Boolean Expression
5. State Minimization
5.1 Algorithmic Approach To State Minimization
5.2 Algorithmic Sketch
5.3 state Minimization Example1
5.4 state Minimization Example 2
6. GREP COMMAND
7. Conclusion
References