public Dictionary<string, List<string>> ConsecutiveMatches { get; set; } = new Dictionary<string, List<string>>();
I wouldn't allow public access to the result in this way, because I wouldn't want clients to be able to manipulate the result of the search directly. Instead I would make this result data be private and then expose it via a public read only method or property either as an IEnumerable<> or as an IReadOnlyDictionary<>:
private Dictionary<string, List<string>> matches = new Dictionary<string, List<string>>();
public IReadOnlyDictionary<string, List<string>> GetResult()
{
return new ReadOnlyDictionary<string, List<string>>(matches.Where(m => m.Value.Count > 1).ToDictionary(kvp => kvp.Key, kvp => kvp.Value));
}
In this way you ensure that the result is valid and consistent if you need it to be used more than once.
Another common way could be to implement IEnumerable<T>, but here that is IMO wrong because of the call to Load(...). A pattern like (for the different naming see below):
ConsecutiveMatcher matcher = new ConsecutiveMatcher();
matcher.Search(data);
foreach (var result in matcher.GetResult())
{
...
}
is more intuitive than:
ConsecutiveMatcher matcher = new ConsecutiveMatcher();
matcher.Search(data);
foreach (var result in matcher)
{
...
}
public void Load(List<string> dataset)
{
If this method is called more than once, you'll have to have a flag to indicate if the new data is to be appended to existing data or the cache should be reset:
public void Search(List<string> dataset, bool append = false)
{
if (dataset == null || dataset.Count == 0) return; // Or throw?
if (!append) matches.Clear();
and as shown, you should validate the input.
var words = sentence.Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries);
You have to refine the way you split into words:
In this sentence "this world in this world." the two "this world" occurrences are not matched by your way to split into words because of the punctuation.
On the other hand are "Hello World" "Hello. World" to be regarded as consecutively equal?
Depending on how you define a word and "consecutive", you could use a regex pattern like:
string pattern = @"(?<word>\b\w+\b)(?<space>[\W]*)";
and then split the string by a Regex match:
var words = Regex.Matches(sentence, pattern).Cast<Match>().Select(m => m.Groups["word"].Value).ToArray();
Whether the above pattern is suitable for your culture or needs you'll have to decide, but it could be a place to start.
permutation
strictly speaking the strings you are building are not permutations but
sub strings or prefix strings.
if (ConsecutiveMatches.TryGetValue(permutation, out var matches))
{
ConsecutiveMatches[permutation].Add(sentence);
}
else
{
ConsecutiveMatches.Add(permutation, new List<string> { sentence });
}
This is a little awkward construct. Why not use the maybe found matches:
if (!ConsecutiveMatches.TryGetValue(permutation, out var matches))
{
matches= new List<string>();
ConsecutiveMatches[permutation] = matches;
}
matches.Add(sentence);
All in all it's not a bad implementation, but there is a major problem in that it builds up a large dictionary of strings with large data sets and the deconstruct - reconstruct of prefix strings is time expensive. As "Oh My Goodness" states, a trie as data structure is more efficient in respect to memory and probably also time wise - for large data sets at least.
Below is an edition of your code with the above comments implemented. I've also renamed things a little bit in my flavor:
class ConsecutiveWordMatcher
{
private Dictionary<string, List<string>> matches = new Dictionary<string, List<string>>();
public void Search(List<string> dataset, bool append = false)
{
if (dataset == null || dataset.Count == 0) return;
if (!append) matches.Clear();
string pattern = @"(?<word>\b\w+\b)(?<space>[\W]*)";
for (int i = 0; i < dataset.Count; i++)
{
var sentence = dataset[i];
if (string.IsNullOrWhiteSpace(sentence)) continue;
var words = Regex.Matches(sentence, pattern).Cast<Match>().Select(m => m.Groups["word"].Value).ToArray();
BuildConsecutiveMatches(words, sentence);
}
}
private void BuildConsecutiveMatches(string[] words, string sentence)
{
BuildConsecutiveMatchesRecursive(words, 0, sentence);
}
private void BuildConsecutiveMatchesRecursive(string[] words, int index, string sentence)
{
if (index >= words.Length - 1)
{
return;
}
StringBuilder builder = new StringBuilder(words[index]);
builder.Append(' ');
foreach (string word in words.Skip(index + 1))
{
builder.Append(word);
var subString = builder.ToString();
if (!matches.TryGetValue(subString, out var sources))
{
sources = new List<string>();
matches[subString] = sources;
}
sources.Add(sentence);
builder.Append(' ');
}
BuildConsecutiveMatchesRecursive(words, ++index, sentence);
}
public IReadOnlyDictionary<string, List<string>> GetResult(int minOccurrences)
{
return new ReadOnlyDictionary<string, List<string>>(matches.Where(m => m.Value.Count >= minOccurrences).ToDictionary(kvp => kvp.Key, kvp => kvp.Value));
}
}
Just for fun and inspiration the below is an implementation using a trie like data structure:
public class SentenceInfo
{
public int Count { get; set; }
public string Sentence { get; set; }
public List<string> Sources { get; set; }
}
// A trie implementation
public class ConsecutiveWordMatcher
{
class Node
{
private Dictionary<string, Node> m_children = new Dictionary<string, Node>();
private List<string> m_sources = new List<string>();
public Node(string word)
{
Word = word;
}
public string Word { get; }
public Dictionary<string, Node> Children => m_children;
public int Count { get; private set; }
public void AddChild(Node child)
{
m_children[child.Word] = child;
}
public IEnumerable<string> Sentences
{
get
{
if (m_children.Count == 0)
{
yield return Word;
}
else
{
foreach (Node child in m_children.Values)
{
foreach (string substring in child.Sentences)
{
yield return $"{Word} {substring}";
}
}
}
}
}
public IEnumerable<SentenceInfo> GetMatches(int wordCount, int minOccurrences)
{
return GetMatches(wordCount, minOccurrences, 1);
}
private IEnumerable<SentenceInfo> GetMatches(int wordCount, int minOccurrences, int level)
{
if (Count >= minOccurrences)
{
if (level >= wordCount)
yield return new SentenceInfo { Count = 1, Sentence = Word, Sources = m_sources };
foreach (Node child in m_children.Where(kvp => kvp.Value.Count >= wordCount).Select(kvp => kvp.Value))
{
foreach (SentenceInfo info in child.GetMatches(wordCount, minOccurrences, level + 1))
{
info.Count++;
info.Sentence = $"{Word} {info.Sentence}";
yield return info;
}
}
}
}
internal bool TryGetNode(string word, out Node node)
{
return m_children.TryGetValue(word, out node);
}
internal void AddSequence(string[] sequence, int index, string source)
{
if (sequence.Length == 0 || index >= sequence.Length) return;
Count++;
string word = sequence[index];
if (word != Word) throw new InvalidOperationException($"'{word}' doesn't match '{Word}'");
if (!m_sources.Contains(source))
{
m_sources.Add(source);
}
if (index < sequence.Length - 1)
{
string nextWord = sequence[index + 1];
if (!m_children.TryGetValue(nextWord, out Node childNode))
{
childNode = new Node(nextWord);
m_children[nextWord] = childNode;
}
childNode.AddSequence(sequence, index + 1, source);
}
}
public override string ToString()
{
return Word;
}
internal void Clear()
{
m_children.Clear();
m_sources.Clear();
}
}
private readonly Node m_root = new Node("");
public ConsecutiveWordMatcher()
{
}
public void Search(List<string> dataset, bool append = false)
{
if (dataset == null || dataset.Count == 0) return;
if (!append)
m_root.Clear();
string pattern = @"(?<word>\b\w+\b)(?<space>[\W]*)";
foreach (string data in dataset)
{
if (string.IsNullOrWhiteSpace(data)) continue;
string line = data;
MatchCollection matches = Regex.Matches(line, pattern);
if (matches.Count > 0)
{
string[] sequence = matches.Cast<Match>().Select(m => m.Groups["word"].Value).ToArray();
for (int i = 0; i < matches.Count; i++)
{
HandleWord(sequence, i, data);
}
}
}
}
private void HandleWord(string[] sequence, int index, string source)
{
string word = sequence[index];
if (!m_root.TryGetNode(word, out Node node))
{
node = new Node(word);
m_root.AddChild(node);
}
node.AddSequence(sequence, index, source);
}
public IEnumerable<SentenceInfo> GetResult(int wordCount = 2, int minOccurrences = 2)
{
return m_root.Children.Values.SelectMany(n => n.GetMatches(wordCount, minOccurrences));
}
}
As a bonus I've added the possibility to change both how many consecutive words and how many occurrences to search for.
It isn't that well tested, so don't hang me, if...
var words = sentence.Split(" ", StringSplitOptions.RemoveEmptyEntries);appears to be invalid. \$\endgroup\$