[go: up one dir, main page]
Scribd
Upload
76 views10 pages

Finite Fields and String Matching Presentation

This document discusses string matching and approximate string matching. It proposes encoding the input strings as elements of a finite field to allow for mismatches. An algorithm is presented that sets up systems of equations for mismatch positions and encodes the input as integers. Fourier transforms and convolutions are used to solve the systems of equations in optimal O(n log n) time to find all occurrences of the pattern in the text.

Uploaded by

amacfies
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
76 views10 pages

Finite Fields and String Matching Presentation

This document discusses string matching and approximate string matching. It proposes encoding the input strings as elements of a finite field to allow for mismatches. An algorithm is presented that sets up systems of equations for mismatch positions and encodes the input as integers. Fourier transforms and convolutions are used to solve the systems of equations in optimal O(n log n) time to find all occurrences of the pattern in the text.

Uploaded by

amacfies
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 10

Finite fields and string matching

Andrew MacFie Math 5900 X

String matching
Input
Text: = 0 1 1 Pattern: = 0 1 1

Objective
Find all occurrences of in as substring

Knuth-Morris-Pratt: +

Approximate string matching


What if matches dont have to be exact?
Allow up to mismatches

and if the alphabet contains wildcards? Clifford et al. approach: use finite field as alphabet

Algorithm
Encode input as finite field elements Set up systems of equations for mismatch positions For = 0 to do Compute =
=1

Find roots of End for Encode input as integers Verify that all mismatches are found for each position

Preliminary 1: Convolutions
Fourier Transform

= = 1

Polynomial multiplication

Convolutions


=0

Preliminary 2: 2 trick
1

takes log time

Compute each in log time

Equations for the output


For each position :

1 1 1 2 1 1
2 1 1

+ + +

2 2 2 2 2 2

2 + 2 2
1

+ + + +

+ + +

= = =

2 +

0 1 2 = 2

=
=0

+ + +

Equations for the output


For each position :

1 1 1 2 1 1
2 1 1

+ + +

2 2 2 2 2 2

2 + 2 2

+ + + +

+ + +

= = =

2 +
=1

0 1 2 = 2
1

0 , 1 , , 2 has minimal polynomial = Berlekamp-Massey!

Verification step
For each position :


=0

2 ? + + =


=1

Analysis
Running time: log 2 log 2 + log log Optimal:

You might also like