C # Array Subset Abrufen

Question

Ich habe ein Array von Bytes, und ich möchte, um zu bestimmen, ob der Inhalt dieses Array von Bytes innerhalb eines anderen größeren Arrays als eine kontinuierliche Sequenz vorhanden ist. Was ist der einfachste Weg, dies zu gehen zu tun?

Answer 1

Der naive Ansatz ist:

public static bool IsSubsetOf(byte[] set, byte[] subset) {
    for(int i = 0; i < set.Length && i + subset.Length <= set.Length; ++i)
        if (set.Skip(i).Take(subset.Length).SequenceEqual(subset))
            return true;
    return false;
}

Für eine effizientere Ansätze, könnten Sie erweiterte String-Matching-Algorithmen wie KMP betrachten .

Answer 2

Versuchen Sie, einige String-Suchalgorithmus anzupassen. Eines der am schnellsten Boyer-Moore . Es ist durchaus auch leicht. Für binäre Daten, Knuth-Morris-Pratt Algorithmus könnte auch sehr effizient arbeiten.

Answer 3

Das, was ein 1/1 Anschluss dieser Antwort lautet: Die Suche nach einer Folge von Bytes in einer Binärdatei mit Java

ist eine sehr effiziente Art und Weise, dies zu tun:

public static class KmpSearch {

    public static int IndexOf(byte[] data, byte[] pattern) {
        int[] failure = ComputeFailure(pattern);

        int j = 0;
        if (data.Length == 0) return -1;

        for (int i = 0; i < data.Length; i++) {
            while (j > 0 && pattern[j] != data[i]) {
                j = failure[j - 1];
            }
            if (pattern[j] == data[i]) { j++; }
            if (j == pattern.Length) {
                return i - pattern.Length + 1;
            }
        }
        return -1;
    }


    private static int[] ComputeFailure(byte[] pattern) {
        int[] failure = new int[pattern.Length];

        int j = 0;
        for (int i = 1; i < pattern.Length; i++) {
            while (j > 0 && pattern[j] != pattern[i]) {
                j = failure[j - 1];
            }
            if (pattern[j] == pattern[i]) {
                j++;
            }
            failure[i] = j;
        }

        return failure;
    }
}