patternmatching.java

implement a number of pattern-matching algorithms and to carry out an analysis of their operation

import java.io.*;
import javax.swing.*;
import java.lang.management.*;

public class PatternMatching
{
	public static void main(String[] args) 
	{
		//This string stores the document read from the source text.
		String text = getText();

		//This string stores the alphabet.
		String alphabet = getAlphabet(text);
		
		//The first step of the experiment.
		//All the patterns can be found in the text.
		System.out.println("Step One" + "\n" + "All the patterns can be found in the text");
		System.out.println("**************************************************");
		for (int len = 10; len <= 100; len += 10)
		{
			System.out.println("The length of the patterns is: " + len + "\n");

			//Build the patterns randomly
			String[] pattern = new String[100000];
			for (int n = 0; n < pattern.length; n ++)
			{
				int temp = (int)(Math.random() * (text.length() - len));
				pattern[n] = text.substring(temp, temp + len);
			}

			//Run and calculate the time they take.
			run(text, alphabet, pattern);
			System.out.println("**************************************************" + "\n");
		}

		//The second step of the experiment.
		//Nearly all the patterns cannot be found in the text.
		System.out.println("Step Two" + "\n" + "Nearly all the patterns cannot be found in the text");
		System.out.println("**************************************************");
		for (int len = 10; len <= 100; len += 10)
		{
			System.out.println("The length of the patterns is: " + len + "\n");

			//Build the patterns randomly
			String[] pattern = new String[100000];
			for (int n = 0; n < pattern.length; n ++)
			{
				pattern[n] = "";
				for (int m = 0; m < len; m ++)
					pattern[n] += (char)((int)'a' + Math.random() * 26);
			}

			//Run and calculate the time they take.
			run(text, alphabet, pattern);
			System.out.println("**************************************************" + "\n");
		}
	}

	/*This method is used to run all the match algorithms and calculate the time they take.*/
	public static void run(String text, String alphabet, String[] pattern)
	{
		//This variable is used to calculate the CPU time taken for each algorithm.
		ThreadMXBean timer = ManagementFactory.getThreadMXBean();

		//There variables are used to store the CPU time and the real time taken for each algorithm.
		long cupTime = 0;
		long realTime = 0;

		//Run the brute force match algorithm and calculate the time it takes.
		cupTime = timer.getCurrentThreadCpuTime();
		for (int n = 0; n < pattern.length; n ++)
			bruteForceMatch(text, pattern[n]);
		cupTime = timer.getCurrentThreadCpuTime() - cupTime;

		realTime = System.nanoTime();
		for (int n = 0; n < pattern.length; n ++)
			bruteForceMatch(text, pattern[n]);
		realTime = System.nanoTime() - realTime;

		System.out.println("The CPU time taken by the brute force match is:  " + (int)(cupTime / 1000000));
		System.out.println("The real time taken by the brute force match is:  " + (int)(realTime / 1000000) + "\n");

		//Run the Boyer Moore match algorithm and calculate the time it takes.
		cupTime = timer.getCurrentThreadCpuTime();
		for (int n = 0; n < pattern.length; n ++)
			boyerMooreMatch(text, pattern[n], alphabet);
		cupTime = timer.getCurrentThreadCpuTime() - cupTime;

		realTime = System.nanoTime();
		for (int n = 0; n < pattern.length; n ++)
			boyerMooreMatch(text, pattern[n], alphabet);
		realTime = System.nanoTime() - realTime;

		System.out.println("The CPU time taken by the Boyer Moore match is:  " + (int)(cupTime / 1000000));
		System.out.println("The real time taken by the Boyer Moore match is:  " + (int)(realTime / 1000000) + "\n");

		//Run the KMP match algorithm and calculate the time it takes.
		cupTime = timer.getCurrentThreadCpuTime();
		for (int n = 0; n < pattern.length; n ++)
			KMPMatch(text, pattern[n]);
		cupTime = timer.getCurrentThreadCpuTime() - cupTime;

		realTime = System.nanoTime();
		for (int n = 0; n < pattern.length; n ++)
			KMPMatch(text, pattern[n]);
		realTime = System.nanoTime() - realTime;

		System.out.println("The CPU time taken by the KMP match is:  " + (int)(cupTime / 1000000));
		System.out.println("The real time taken by the KMP match is:  " + (int)(realTime / 1000000) + "\n");
	}

	/*Brute-Force pattern matching*/
	public static int bruteForceMatch(String text, String pattern)
	{
		int m = pattern.length();
		int n = text.length();

		for (int i = 0; i <= n - m; i ++)
		{
			int j = 0;
			while (j < m && text.charAt(i + j) == pattern.charAt(j))
				j ++;
			if (j == m)
				return i;
		}

		return -1;
	}

	/*The Boyer-Moore pattern matching*/
	public static int boyerMooreMatch(String text, String pattern, String alphabet)
	{
		int m = pattern.length();
		int n = text.length();

		int[] lastOccuranceList = lastOccuranceFunction(pattern, alphabet);

		int i = m - 1;
		int j = m - 1;

		while (i <= n - 1)
		{
			if (text.charAt(i) == pattern.charAt(j))
				if (j == 0)
					return i;
				else
				{
					i --;
					j --;
				}
			else
			{
				int l = lastOccuranceList[alphabet.indexOf(text.charAt(i))];
				if (j < l + 1)
					i = i + m - j;
				else
					i = i + m - l - 1;
				j = m - 1;
			}
		}

		return -1;
	}

	/*The last occurance function used by the the Boyer-Moore pattern matching*/
	public static int[] lastOccuranceFunction(String pattern, String alphabet)
	{
		int[] l = new int[alphabet.length()];
		for (int k = 0; k < l.length; k ++)
			l[k] = pattern.lastIndexOf(alphabet.charAt(k));
		return l;
	}

	/*The KMP pattern matching*/
	public static int KMPMatch(String text, String pattern)
	{
		int m = pattern.length();
		int n = text.length();
		int[] f = failureFunction(pattern);

		int i = 0;
		int j = 0;

		while (i < n)
		{
			if (text.charAt(i) == pattern.charAt(j))
				if (j == m - 1)
					return i - j;
				else
				{
					i ++;
					j ++;
				}
			else
			{
				if (j > 0)
					j = f[j - 1];
				else
					i ++;
			}
		}

		return -1;
	}

	/*The failure function used by the KMP pattern matching*/
	public static int[] failureFunction(String pattern)
	{
		int m = pattern.length();

		int[] f = new int[m];
		f[0] = 0;

		int i = 1;
		int j = 0;

		while (i < m)
			if (pattern.charAt(i) == pattern.charAt(j))
			{
				f[i] = j + 1;
				i ++;
				j ++;
			}
			else if (j > 0)
				j = f[j - 1];
			else
			{
				f[i] = 0;
				i ++;
		}

		return f;
	}

	/*This method reads the content of the source text into the program*/
	public static String getText()
	{
		String text = "";
		try
		{
			String line = "";
			BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("File.txt")));
			while ((line = reader.readLine()) != null)
				text += line;
			reader.close();
		}
		catch(Exception e)
		{
			e.printStackTrace();
		}
		return text;
	}

	/*This method gets the alphabet of the source text.*/
	public static String getAlphabet(String text)
	{
		String alphabet = "";

		for (int n = 0; n < text.length(); n ++)
		{
			char temp = text.charAt(n);
			if (alphabet.indexOf(temp) == -1)
				alphabet += temp;
		}

		int[] array = new int[alphabet.length()];
		for (int n = 0; n < array.length; n ++)
			array[n] = alphabet.charAt(n);

		for (int n = 0; n < array.length - 1; n ++)
			for (int m = 0; m < array.length - n - 1; m ++)
				if (array[m] > array[m + 1])
				{
					int temp = array[m];
					array[m] = array[m + 1];
					array[m + 1] = temp;
				}
		
		alphabet = "";
		for (int n = 0; n < array.length; n ++)
			alphabet += (char)array[n];

		return alphabet;
	}
}