4

我想知道是否有更简单的方法可以在数组中找到模式？

假设我正在寻找给定数组中的一种模式：A) 微笑、皱眉、微笑、皱眉等 B) 微笑、愤怒、皱眉、微笑、愤怒、皱眉等 C) 微笑、微笑、微笑

现在说给定的数组与模式 A 匹配：

生气，生气，生气，Smile, Frown, Smile, Frown, Smile, Frown,生气，皱眉，生气，皱眉，微笑

突出显示的部分是与模式 A 匹配的部分以及我想要存储在列表中的部分。

现在我有这样的事情：

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

有更好的方法吗？总感觉这个不好。。。。

4

5 回答 5

3

您可以将数组转换为字符串并将其与任何正则表达式模式匹配。

UPD：可能是前缀树可以帮助你。首先将所有模式添加到 trie，然后再匹配您的数组。但这很像一个本土的正则表达式引擎。

于 2013-03-06T15:48:06.697 回答
2

更新：我实现了我描述的方法。

运行下面的代码返回：

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

为了简单起见，我将代码和测试代码放在一个类中。完成这项工作的函数是 findPatternIndex。剩下的就是简单的测试、初始化和显示逻辑。

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

}

如果事先不知道填充数组的单词，则可以进一步更新代码以动态构建编码单词。显示所有匹配项的索引也很简单，而不仅仅是第一个匹配项。

于 2013-03-06T15:56:23.553 回答
2

KMP 字符串搜索算法的修改版本在这里可能很有用。

这是一些示例 Java 代码：http ://www.fmi.uni-sofia.bg/fmi/logic/vboutchkova/sources/KMPMatch.java

需要考虑的一些差异：

  • 它应该被构建为同时处理多个搜索词。在您的情况下，多种模式，例如：Smile, Frown,和Smile, Angry, Frown,
  • 重复的模式本身只是同一个词的多次重复。在您发现单个单词的位置后，您可以在搜索完成后组合找到的彼此相邻的模式。这将允许您获得重复的完整完整模式，例如：Smile, Frown, Smile, Frown, Smile, Frown,

希望这可以帮助。

于 2013-03-06T17:34:09.637 回答
0

用于Arrays.toString(Object[] a)将数组转换为String然后查找您的模式。

例如Arrays.toString(new String[] { "a", "b" })返回"[a, b]"。

于 2013-03-06T15:54:33.490 回答
0

可能有更简单的解决方案，但您可以在字符串的帮助下完成。优点是，您可以使用已经过测试的高性能代码。缺点是，您必须将数组转换为String.

创建String：您需要从值空间到字符串空间的映射。所以例如

{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"}

您需要注意映射的值不能相互交互。例如映射

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

将是一个无效的映射，因为你无法找出，如果"10"是 a1后跟 a 0，或者如果它是 a 10。

示例：假设您的数组包含{ANGRY. SMILE, FROWN, SMILE, FROWN, SMILE, FROWN, SMILE}. 那么你的映射String将是"ASFSFSFS".

定义模式：接下来，您需要定义一个模式。这只是一个String包含正确模式的 a，正如您期望在 mapped 中找到的那样String。

示例：在您的情况下，那将是

String pattern = "SFSFSF";

将字符串与模式匹配：现在，您可以使用它indexOf()来查找您的模式。

int start = mappedString.indexOf(pattern);

pattern这将为您提供in的第一次出现的索引mappedString。如果返回-1，则在字符串中未找到您的模式。

存储模式：否则，您可以将模式存储在列表中。

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

您可以使用 再次搜索mappedString.subString(start+pattern.length()).indexOf(pattern)。寻找下一个外观。

于 2013-03-06T16:45:13.627 回答