Optimal Mismatch Algorithm

This algorithm works by scanning pattern characters from the least frequent one to the most frequent one. Doing so one may hope to have a mismatch most of the times and thus to scan the whole text very quickly. One needs to know the frequencies of each of the character of the alphabet.

• C#
• VB.Net
• C
• C++

									private static char[] _x, _y;
private static int _m, _n;
private static int[] _adaptedGs, _qsBc, _frequency;
private static Pattern[] _pattern;

private static void OrderPattern(char[] x, Pattern[] pat, int[] freq)
{
	for (int i = 0; i < x.Length; ++i)
	{
		Pattern ptrn = new Pattern();
		ptrn.Location = i;
		ptrn.Character = x[i];
		pat[i] = ptrn;
	}

	QuickSortPattern(pat, 0, x.Length - 1, freq);
}

private static void QuickSortPattern(Pattern[] pat, int low, int n, int[] freq)
{
	int lo = low;
	int hi = n;

	if (lo >= n) return;

	Pattern mid = pat[(lo + hi) / 2];

	while (lo < hi)
	{
		while (lo < hi && OptimalPatternCompare(pat[lo], mid, freq) < 0) lo++;
		while (lo < hi && OptimalPatternCompare(pat[hi], mid, freq) > 0) hi--;

		if (lo < hi)
		{
			Pattern temp = pat[lo];
			pat[lo] = pat[hi];
			pat[hi] = temp;
		}
	}

	if (hi < lo)
	{
		int temp = hi;
		hi = lo;
		lo = temp;
	}

	QuickSortPattern(pat, low, lo, freq);
	QuickSortPattern(pat, lo == low ? lo + 1 : lo, n, freq);
}

private static int OptimalPatternCompare(Pattern pat1, Pattern pat2, int[] freq)
{
	int fx = freq[pat1.Character] - freq[pat2.Character];
	return (fx != 0 ? (fx > 0 ? 1 : -1) : (pat2.Location - pat1.Location));
}

private static int MatchShift(char[] x, int ploc, int lShift, Pattern[] pat)
{
	int i, j;

	for (; lShift < x.Length; ++lShift)
	{
		i = ploc;
		while (--i >= 0)
		{
			if ((j = (pat[i].Location - lShift)) < 0) continue;
			if (pat[i].Character != x[j]) break;
		}
		if (i < 0) break;
	}

	return (lShift);
}

private static void PreAdaptedGs(char[] x, int[] adaptedGs, Pattern[] pat)
{
	int lShift, i, pLoc;
	adaptedGs[0] = lShift = 1;

	for (pLoc = 1; pLoc <= x.Length; ++pLoc)
	{
		lShift = MatchShift(x, pLoc, lShift, pat);
		adaptedGs[pLoc] = lShift;
	}

	for (pLoc = 0; pLoc < x.Length; ++pLoc)
	{
		lShift = adaptedGs[pLoc];
		while (lShift < x.Length)
		{
			i = pat[pLoc].Location - lShift;
			if (i < 0 || pat[pLoc].Character != x[i]) break;
			++lShift;
			lShift = MatchShift(x, pLoc, lShift, pat);
		}
		adaptedGs[pLoc] = lShift;
	}
}

private static int[] CalculateCharFrequency(char[] x, char[] y, int z)
{
	int i;
	int[] freq = new int[z];
	for (i = 0; i < x.Length; i++) freq[x[i]]++;
	for (i = 0; i < y.Length; i++) freq[y[i]]++;
	return freq;
}

private static void PreQsBc(char[] x, int[] qsBc)
{
	int i, m = x.Length;

	for (i = 0; i < qsBc.Length; ++i)
		qsBc[i] = m + 1;

	for (i = 0; i < m; ++i)
		qsBc[x[i]] = m - i;
}

private static void SetupOptimalSearch()
{
	OrderPattern(_x, _pattern, _frequency);
	PreQsBc(_x, _qsBc);
	PreAdaptedGs(_x, _adaptedGs, _pattern);
}

public static void InitOptimalSearch(string pattern, string source)
{
	_x = pattern.ToCharArray();
	_y = source.ToCharArray();
	_m = _x.Length;
	_n = _y.Length;
	_adaptedGs = new int[_m + 1];
	_qsBc = new int[65536];
	_frequency = CalculateCharFrequency(_x, _y, 65536);
	_pattern = new Pattern[_m];
}

public static Result FindAll()
{
	int i, j;
	List<int> result = new List<int>();
	SetupOptimalSearch();

	j = 0;
	int jOld = 0;
	while (j <= _n - _m)
	{
		i = 0;
		while (i < _m && _pattern[i].Character == _y[j + _pattern[i].Location]) ++i;

		if (i >= _m)
			result.Add(j);

		jOld = j;
		if (j < _n - _m)
			j += Math.Max(_adaptedGs[i], _qsBc[_y[j + _m]]);
		else
			j += _adaptedGs[i];
	}

	return new Result(jOld, result);
}

public struct Result
{
	public int Comp;
	public List<int> Indexes;

	public Result(int comp, List<int> indexes)
	{
		Comp = comp;
		Indexes = indexes;
	}
}

public struct Pattern
{
	public int Location;
	public char Character;
}
								

Example

									string source = "GCATCGCAGAGAGTATACAGTACG";
string pattern = "GCAGAGAG";
InitOptimalSearch(pattern, source);
Result result = FindAll();
								

Output

									result {
	Comp: 14
	Indexes: { 5 }
}