Récupération de sous-ensembles de tableaux C #

Question

J'ai un tableau d'octets et je veux déterminer si le contenu de ce tableau d'octets existe dans un autre tableau plus grand sous forme de séquence continue. Quel est le moyen le plus simple de procéder?

Answer 1

L’approche naïve est la suivante:

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

Pour des approches plus efficaces, vous pouvez envisager des algorithmes de correspondance de chaîne plus avancés tels que KMP .

Answer 2

Essayez d’adapter un algorithme de recherche de chaîne. L’un des plus rapides est Boyer-Moore . C'est assez facile aussi. Pour les données binaires, Knuth-Morris-Pratt L’algorithme pourrait également fonctionner très efficacement.

Answer 3

Ceci, qui est un portage 1/1 de cette réponse: Recherche d'une séquence d'octets dans un fichier binaire avec Java

Est un moyen très efficace de le faire:

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