4

配列内のパターンを見つける簡単な方法があるかどうか疑問に思っていましたか?

与えられた配列のパターンの 1 つを探しているとしましょう: 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:プレフィックスツリーが役立つ場合があります。最初にすべてのパターンをトライに追加してから、配列をそれと照合します。しかし、それは自家製の正規表現エンジンに非常に似ています。

于 2013-03-06T15:48:06.697 に答える
2

更新：私は説明していたアプローチを実装しました。

以下のコードを実行すると、次のようになります。

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

簡単にするために、コードとテストコードを1つのクラスに入れました。作業を行う関数は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));
  }

}

配列に入力されている単語が事前にわからない場合は、コードをさらに更新して、encodedWordsを動的に構築できます。また、最初の一致だけでなく、すべての一致のインデックスを表示するのも簡単です。

于 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

もっと簡単な解決策があるかもしれませんが、文字列の助けを借りてそれを行うことができます。利点は、既にテスト済みでパフォーマンスの高いコードを使用できることです。欠点は、配列を に変換する必要があることです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"の後にが1続く0かどうか、または であるかどうかがわからないため、無効なマッピングになります10。

例:配列に が含まれているとします{ANGRY. SMILE, FROWN, SMILE, FROWN, SMILE, FROWN, SMILE}。次に、マップStringは になります"ASFSFSFS"。

パターンの定義:次に、パターンを定義する必要があります。Stringこれは、マップされた で見つかると予想される正しいパターンを含む単純なです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 に答える
0

を使用Arrays.toString(Object[] a)して配列を変換しString、パターンを探します。

たとえば、をArrays.toString(new String[] { "a", "b" })返します"[a, b]"。

于 2013-03-06T15:54:33.490 に答える