finding patterns in an array

Question

I was wondering if there is an easier way to find a pattern within an array?

Say i'm looking for one of the patterns in the a given array: A) Smile, Frown, Smile, Frown, etc B) Smile, Angry, Frown, Smile, Angry, Frown, etc C) Smile, Smile, Smile

Now say the array that is given matches pattern A as such:

Angry, Angry, Angry, Smile, Frown, Smile, Frown, Smile, Frown, Angry, Frown, Angry, Frown, Smile

The highlighted section is the section which matches with pattern A and the section I want to store away in a list.

Right now I have something like this:

For each element in the array
check to see if element is smile
if element is smile, check to see if next element is frown
if element is smile and next element is frown - store away in a list 
set a boolean saying we've found pattern A

if the boolean value is false and we did not find the smile frown pattern
For each element in the array
check to see if element is smile
if element is smile, check to see if next element is angry,
is next element is angry, check to see if next next element is frown
if element is smile, next element is angry, next next element is frown - store away in a list
set a boolean saying we've found pattern B

if boolean value is false for both finding pattern A and pattern B search for pattern C

Is there a better approach to this? I feel like this is overall bad....

1) How large is this array? 2) Is it an array of Strings like in your example? Or something else? 3) Do you want to be as fast as possible or should the code be as readable and understandable as possible? — brimborium
– brimborium, Commented Mar 6, 2013 at 16:18

Mikhail · Accepted Answer · 2013-03-06 16:43:55Z

3

You can convert array to a string and match it against any regular expression pattern.

UPD: May be a prefix tree can help you. First add all your patterns to a trie, then match your array agains it. But that would be very like a homegrown regular expression engine.

edited Mar 6, 2013 at 16:43

answered Mar 6, 2013 at 15:48

Mikhail

4,22317 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Lolo Over a year ago

Converting to a string would allow to tell whether there was a match or not, but it would not provide an easy way to tell where the pattern match occurred in the original array. You need to add the step of encoding each array element into a char or a string of the same length for each element in the array if you want to figure out where the pattern is in the original array.

Mikhail Over a year ago

If we are talking about efficiency it could be done with prefix tree. If spped is not a point of consideration simple HashMap could be used. I just though that this is too obvious, and not mentioned it.

Lolo · Accepted Answer · 2013-03-06 22:53:43Z

UPDATE: I implemented the approach I was describing.

Running the code below returns:

First match against pattern found at index 3
No match found.

I put the code and the test code inside one class for the sake of simplicity. The function that does the work is findPatternIndex. The rest is simple test, init, and display logic.

import java.util.LinkedHashMap;
import java.util.Map;

import org.junit.Before;
import org.junit.Test;

public class PatternMatching {

  private final Map<String, Character> encodedWords = new LinkedHashMap<String, Character>();

  @Before
  public void init() {
    encodedWords.put("Angry", 'A');
    encodedWords.put("Smile", 'S');
    encodedWords.put("Frown", 'F');
  }

  public int findPatternIndex(final String[] array, final String pattern) {
    final StringBuffer encodedSequence = new StringBuffer();
    for (final String element : array) {
      encodedSequence.append(encodedWords.get(element));
    }
    return encodedSequence.toString().indexOf(pattern);
  }

  private void displayFindings(final int index) {
    if (index==-1) {
      System.out.println("No match found.");
    } else {
      System.out.println("First match against pattern found at index " + index);
    }
  }

  @Test
  public void shouldFindOneMatchThenNone() {
    final String[] array = {"Angry","Angry","Angry","Smile","Frown","Smile","Frown","Smile","Frown","Angry","Frown","Angry","Frown","Smile"};
    String pattern="SFSF";
    displayFindings(findPatternIndex(array, pattern));
    pattern="AAF";
    displayFindings(findPatternIndex(array, pattern));
  }

}

The code could further be updated to build encodedWords dynamically if the words populating the array are not known in advance. It would also be simple enough to display the index of all matches instead of just the first one.

tdedecko · Accepted Answer · 2013-03-06 17:34:09Z

A modified version of KMP string search algorithm could be useful here.

Here is some sample Java code: http://www.fmi.uni-sofia.bg/fmi/logic/vboutchkova/sources/KMPMatch.java

Some difference to consider:

It should be built to work on multiple search words at the same time. In your case multiple patterns such as: Smile, Frown, and Smile, Angry, Frown,
The patterns themselves that repeat are just multiple repetitions of the same word. After you discover the locations of the individual words you can combine the found patterns that are adjacent to each other after the search is complete. This will allow you get that complete full pattern that is repeated such as: Smile, Frown, Smile, Frown, Smile, Frown,

Hope this helps.

user2030471 · Accepted Answer · 2013-03-06 15:54:33Z

0

Use Arrays.toString(Object[] a) to convert the array to String and then look for your pattern.

For example Arrays.toString(new String[] { "a", "b" }) returns "[a, b]".

answered Mar 6, 2013 at 15:54

user2030471

Comments

brimborium · Accepted Answer · 2013-03-07 08:16:24Z

There might be simpler solutions, but you can do it with the help of strings. The advantage is, that you can use already tested and performant code. The disadvantage is, that you will have to convert your array to a String.

Create the String: You need a mapping from your value space to the String space. So for instance

{0, 1, 2} -> {"0", "1", "2"}
{0, 1, ..., 99, 100} -> {"_0", "_1", ..., "_99", "_100"}
{SMILE, FROWN, ANGRY} -> {"S", "F", "A"}
{"Smile", "Frown", "Angry"} -> {"Smile", "Frown", "Angry"}

You need to be careful that the mapped values can not interact with each other. For instance a mapping

{0, 1, ..., 10} -> {"0", "1", ..., "10"}

would be an invalid mapping because you can not find out, if "10" is a 1 followed by a 0, or if it is a 10.

Example: Let's say your array contains {ANGRY. SMILE, FROWN, SMILE, FROWN, SMILE, FROWN, SMILE}. Then your mapped String would be "ASFSFSFS".

Define patterns: Next, you need to define a pattern. This is simply a String that contains the correct pattern as you would expect to find it in the mapped String.

Example: In your case, that would be

String pattern = "SFSFSF";

Match string against pattern: Now, you can use indexOf() to find your pattern.

int start = mappedString.indexOf(pattern);

This will give you the index of the first appearence of pattern in mappedString. If it returns -1, your pattern has not been found in the string.

Store the pattern: Otherwise, You can store the pattern in your list.

if (start > 0) storePatternInList(yourList, new ObjectEnum[]{SMILE, FROWN, SMILE, FROWN, SMILE, FROWN});

You can search again with mappedString.subString(start+pattern.length()).indexOf(pattern). To find the next appearance.

Collectives™ on Stack Overflow

finding patterns in an array

5 Answers 5

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related