2
\$\begingroup\$

I have written an algorithm to do consecutive word match in a dataset

The input is a dataset (list of textlines) and I want to scan that and return repeated word(s) in the dataset along with some metadata like the strings (lines) they matched at.

I am having hard time to wrap my mind around a better approach to hand the consecutive words match. What I have so far is:

  • hashtable datastructure
  • I compute the permutations of each sentence's words. So complexity is n+ (n*avg words count). e.g: abc def gg ww will produce the following permutations

    -- abc def
    -- abc def gg
    -- abc def gg ww
    -- def gg
    -- def gg ww
    -- gg ww

  • I store every possible word combination from each sentence in a dictionary with value of 1
  • if a word combination exists in the dictionary, I increase the value by 1
  • using stringBuilder to avoid string immutability
  • I refine my dictionary at the end to remove any items that has value of 1

I am curios if:
1) this can be improved
2) are there any other datastructures/algo I can use to do the consecutive word matching on a text blob

It is C# now, but we are considering python or Go as well.

public Dictionary<string, List<string>> ConsecutiveMatches { get; set; }

public void Load(List<string> dataset)
{
    for (int i = 0; i < dataset.Count; i++)
    {
        var sentence = dataset[i];
        var words = sentence.Split(" ", StringSplitOptions.RemoveEmptyEntries);

        BuildConsecutiveMatches(words, sentence);
    }

    RefineConsecutiveMatches();
}

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;
    }

    var builder = new StringBuilder(words[index]);
    builder.Append(' ');

    for (int i = index + 1; i < words.Length; i++)
    {
        builder.Append(words[i]);
        var permutation = builder.ToString();
        if (ConsecutiveMatches.TryGetValue(permutation, out var matches))
        {
            ConsecutiveMatches[permutation].Add(sentence);
        }
        else
        {
            ConsecutiveMatches.Add(permutation, new List<string> { sentence });
        }
        builder.Append(' ');
    }

    BuildConsecutiveMatchesRecursive(words, ++index, sentence);
}

private void RefineConsecutiveMatches()
{
    ConsecutiveMatches = ConsecutiveMatches.Where(pair => pair.Value.Count >= 2)
                            .ToDictionary(pair => pair.Key,
                                        pair => pair.Value);
}
\$\endgroup\$
2
  • \$\begingroup\$ Are you sure this works because this line var words = sentence.Split(" ", StringSplitOptions.RemoveEmptyEntries); appears to be invalid. \$\endgroup\$
    – t3chb0t
    Apr 6, 2019 at 10:11
  • \$\begingroup\$ which part? i am on netcore2.1 fyi \$\endgroup\$ Apr 9, 2019 at 15:28

2 Answers 2

2
\$\begingroup\$

The data structure you want is called a trie. It's often used with letters in the nodes, for doing word search (finding anagrams and so on); in your case the keys would be words and the values would be sub-tries and arrays of line numbers or other metadata.

Given this input:

cat dog pig
dog pig cow

You'd make a structure like:

{
    cat: {
      dog: {
        pig: { "#": [ 1 ] },
        "#": [ 1 ]
      },
      "#": [ 1 ]
    },
    dog: {
      pig: { 
        cow: { "#": [ 2 ] },
        "#": [ 1, 2 ]
      },
      "#": [ 1, 2 ]
    },
    pig: { 
      cow: { "#": [ 2 ] },
      "#": [ 1, 2 ]
    },
    cow: { "#": [ 2 ] },
}
\$\endgroup\$
2
  • \$\begingroup\$ i am trying to wrap my head around how is this more performant than the hashtable implementation? also, in line 11 how were you able to determine that pig appeared in sentence #1 without traversing the trie? \$\endgroup\$ Apr 9, 2019 at 15:27
  • \$\begingroup\$ It's not more performant. The point is that it's equal performance with \$O(n^2)\$ storage while the hash uses \$O(n^3)\$ storage. pig is added to the trie as you traverse the text. \$\endgroup\$ Apr 9, 2019 at 17:17
2
\$\begingroup\$
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...

\$\endgroup\$
1
  • \$\begingroup\$ Great feedback. I will have to give your trie implementation a try and get back to you. I have a trie implemented for prefix match (char) but not for a word! \$\endgroup\$ Apr 9, 2019 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.