/// <summary>
/// Does pattern matching by strings.
/// </summary>
/// <typeparam name="T">The type to pattern match.</typeparam>
public class PatternStringMatcher<T>
{
/// <summary>
/// Creates a new string pattern matcher.
/// </summary>
/// <param name="arbitraryChooser">Gets called when the pattern matcher can't detect a pattern.</param>
/// <param name="chooser">Gets called on the type that it thinks will be next.</param>
public PatternStringMatcher(Func<T, T> arbitraryChooser, Func<T, T> chooser)
{
FullPattern = new List<T>();
PatternDictionary = new Dictionary<T, List<PatternData>>();
this.ArbitraryChooser = arbitraryChooser;
this.Chooser = chooser;
}
/// <summary>
/// The full pattern so far.
/// </summary>
public List<T> FullPattern;
/// <summary>
/// The dictionary of found patterns.
/// </summary>
public Dictionary<T, List<PatternData>> PatternDictionary;
/// <summary>
/// Chooses arbitrarily.
/// </summary>
public Func<T, T> ArbitraryChooser;
/// <summary>
/// Makes an intelligent choice.
/// </summary>
public Func<T, T> Chooser;
/// <summary>
/// Contains pattern data.
/// </summary>
public struct PatternData
{
/// <summary>
/// Creates data for a new pattern.
/// </summary>
/// <param name="index">The starting index of the new pattern.</param>
/// <param name="count">The size count of the new pattern.</param>
public PatternData(Int32 index, Int32 count = 1)
{
this.Index = index;
this.Count = count;
}
/// <summary>
/// The starting index of the pattern.
/// </summary>
public Int32 Index;
/// <summary>
/// The size of the pattern.
/// </summary>
public Int32 Count;
/// <summary>
/// Gets the type at the relative index.
/// </summary>
/// <param name="fullPattern">The pattern to index in.</param>
/// <param name="relativeIndex">A relative index in the pattern.</param>
/// <returns>Returns the object of type T at the relative index.</returns>
public T this[List<T> fullPattern, Int32 relativeIndex]
{
get
{
return fullPattern[index: this.Index + relativeIndex];
}
}
}
/// <summary>
/// Adds a new datum to the pattern.
/// </summary>
/// <param name="t"></param>
public void AddNew(T t)
{
// Extends the pattern.
this.FullPattern.Add(t);
// Makes sure the pattern dictionary contains the datum as a key.
if (!this.PatternDictionary.Keys.Contains(t))
this.PatternDictionary.Add(t, new List<PatternData>());
// This if statement is a left-over.
if (this.FullPattern.Count > 0)
{
// Extends the pattern list with the new pattern.
List<PatternData> patternList = this.PatternDictionary[this.FullPattern[this.FullPattern.Count - 1]];
if (patternList.Count == 0)
patternList.Add(new PatternData(index: this.FullPattern.Count - 1));
else
{
patternList.Add(new PatternData(
index: patternList[patternList.Count - 1].Index,
count: patternList[patternList.Count - 1].Count + 1)
);
}
}
}
/// <summary>
/// Attempts to predict the next datum in the pattern.
/// </summary>
/// <param name="a">The datum to predict against.</param>
/// <returns>Returns a predicted or arbitrary datum.</returns>
public T Predict(T a)
{
// If we don't have any data in the full pattern yet, choose arbitrarily.
if (this.FullPattern.Count == 0)
return this.ArbitraryChooser(a);
// Get the tail of the full pattern.
T tail = this.FullPattern[FullPattern.Count - 1];
// If we don't have a pattern index for that yet, choose arbitrarily.
if (!this.PatternDictionary.Keys.Contains(tail))
return this.ArbitraryChooser(a);
else
{
// Try to find a pattern with the highest match.
// A list of patterns.
List<PatternData> patternList = this.PatternDictionary[tail];
// The best pattern match.
PatternData bestPatternMatch = new PatternData();
// The current number of matches.
Int32 currentMatchCount = 1;
// The highest number of matches found.
Int32 highestMatchCount = 1;
// If we've found a pattern at all.
Boolean foundPattern = false;
// Start with the most recent pattern.
for (Int32 t = patternList.Count - 1; t >= 0; --t)
{
// Check to see how many matches this pattern has.
currentMatchCount = 1;
// If it doesn't have more data than the highest match count,
// it's not going to have a higher match count.
if (patternList[t].Count > highestMatchCount)
{
// Search from the most recent datum in the pattern.
for (Int32 t2 = patternList[t].Count - 1; t2 >= 0; --t2)
if (patternList[t][this.FullPattern, t2].Equals(this.FullPattern[FullPattern.Count - 1]))
++currentMatchCount;
else
break;
}
// If we've found a better match, store it.
if (currentMatchCount > highestMatchCount)
{
foundPattern = true;
highestMatchCount = currentMatchCount;
bestPatternMatch = patternList[t];
}
}
// If we've found a pattern, choose using last datum as the next predicted.
if (foundPattern)
return this.Chooser(
bestPatternMatch[
this.FullPattern,
relativeIndex: (bestPatternMatch.Count - 1)
]
);
else
return this.ArbitraryChooser(a);
}
}
}
Critique my String Pattern Matching algorithm
Author
I've got a simple Rock, Paper, Scissors input/output synced to my pattern matcher. I suspect, however, that I'm missing something in the pattern matcher - It doesn't "feel" right. It seems like it would just match whatever was the largest pattern that matched that datum. Going to read that section again.
It does seem to work also, but not near as well as I'd expect.
Author
Ok, if I'm reading it right, now, this code should be correct:
/// <summary> /// Does pattern matching by strings. /// </summary> /// <typeparam name="T">The type to pattern match.</typeparam> public class PatternStringMatcher<T> { /// <summary> /// Creates a new string pattern matcher. /// </summary> /// <param name="arbitraryChooser">Gets called when the pattern matcher can't detect a pattern.</param> /// <param name="chooser">Gets called on the type that it thinks will be next.</param> public PatternStringMatcher(Func<T, T> arbitraryChooser, Func<T, T> chooser) { FullPattern = new List<T>(); PatternDictionary = new Dictionary<T, List<PatternData>>(); this.ArbitraryChooser = arbitraryChooser; this.Chooser = chooser; } /// <summary> /// The full pattern so far. /// </summary> public List<T> FullPattern; /// <summary> /// The dictionary of found patterns. /// </summary> public Dictionary<T, List<PatternData>> PatternDictionary; /// <summary> /// Chooses arbitrarily. /// </summary> public Func<T, T> ArbitraryChooser; /// <summary> /// Makes an intelligent choice. /// </summary> public Func<T, T> Chooser; /// <summary> /// Contains pattern data. /// </summary> public struct PatternData { /// <summary> /// Creates data for a new pattern. /// </summary> /// <param name="index">The starting index of the new pattern.</param> /// <param name="count">The size count of the new pattern.</param> public PatternData(Int32 index, Int32 count = 1) { this.Index = index; this.Count = count; } /// <summary> /// The starting index of the pattern. /// </summary> public Int32 Index; /// <summary> /// The size of the pattern. /// </summary> public Int32 Count; /// <summary> /// Gets the type at the relative index. /// </summary> /// <param name="fullPattern">The pattern to index in.</param> /// <param name="relativeIndex">A relative index in the pattern.</param> /// <returns>Returns the object of type T at the relative index.</returns> public T AtIndex(List<T> fullPattern, Int32 relativeIndex = 0) { return fullPattern[index: this.Index + relativeIndex]; } } Int32 maxMatchSize = 0, maxMatchPosition; /// <summary> /// Adds a new datum to the pattern. /// </summary> /// <param name="t"></param> public void AddNew(T newElement) { // If we have a pattern, if (this.FullPattern.Count > 0) { // Get the former last element, T formerLastElement = this.FullPattern[this.FullPattern.Count - 1]; // Get all occurances of the new element List<PatternData> occurences = this.PatternDictionary[newElement]; // Temporary holders. PatternData thisEntry; PatternData neighbor; // Work backwards through the occurances; for (Int32 t = occurences.Count - 1; t >= 1; --t) { // Get the current entry and its left neighbor. thisEntry = occurences[t]; neighbor = occurences[t - 1]; // Try to pattern match against the previous element to our new element. // We go through the occurances backwards, getting a count of // the number of times the pattern before our new element repeats. if (neighbor.AtIndex(fullPattern: this.FullPattern).Equals(formerLastElement)) { thisEntry.Count = 1 + neighbor.Count; } else { thisEntry.Count = 1; } // And we keep the biggest match size. if (thisEntry.Count > maxMatchSize) { maxMatchSize = thisEntry.Count; maxMatchPosition = thisEntry.Index; } } // Then, add the new element and an occurance index for it. this.FullPattern.Add(newElement); if (!this.PatternDictionary.Keys.Contains(newElement)) this.PatternDictionary.Add(newElement, new List<PatternData>()); this.PatternDictionary[newElement].Add(new PatternData(index: this.FullPattern.Count - 1)); } } /// <summary> /// Attempts to predict the next datum in the pattern. /// </summary> /// <param name="a">The datum to predict against.</param> /// <returns>Returns a predicted or arbitrary datum.</returns> public T Predict(T a) { if (maxMatchSize > 0) return this.Chooser(this.FullPattern[maxMatchPosition + 1]); else return this.ArbitraryChooser(a); } }
Quote:
It doesn't "feel" right. It seems like it would just match whatever was the largest pattern that matched that datum. Going to read that section again
Um. What exactly are you talking about?
And why are you trying reinvent this wheel? What is the problem this is supposed to be a solution for? Et cetera. You posts sound like internal dialog which isn't very helpful.
Author
It's self-assigned homework, essentially, same with the Genetic Engineering and Neural Network stuff. I'm implementing a string pattern matching algorithm according to what's described in the AI Game Programming Wisdom book.
After all, the more I know, the better programs I can write in the future.
After all, the more I know, the better programs I can write in the future.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
