Brute Force Algorithm

There are different algorithms for approximate string matching. A fundamental approach is the Brute Force Algorithm.

A brute-force approach would be to compute the edit distances to query object(q) from all N substrings of  text(T), and then choose the substring with the minimum edit distance. The sequential steps are given below:

Steps:

1. Read N (say=50) strings from the text file T.

2. Take an input (query object q) from the user.

3. Calculate the edit distances to query object, q from all N strings of T.

4. Find out the minimum edit distance.

5. Output will be the string which has the minimum edit distance.  

Let N=5 and T is:{been, bid, moon, sun, star}

Say, q=’seen’

The edit distances to query object q from all N strings of T will be respectively:

{1,4,3,2,3}

The minimum distance is: 1

Hence the output will be: been

Until next time, I am signing off.