6

もつ 

List<byte> lbyte

もつ

byte[] searchBytes

1バイトだけでなく、searchBytesのインデックスをlbyteで検索するにはどうすればよいですか?
例えば

Int32 index = lbyte.FirstIndexOf(searchBytes);

これが私が思いついたブルートフォースです。
私が求めているパフォーマンスではありません。 

public static Int32 ListIndexOfArray(List<byte> lb, byte[] sbs)
{
    if (sbs == null) return -1;
    if (sbs.Length == 0) return -1;
    if (sbs.Length > 8) return -1;
    if (sbs.Length == 1) return lb.FirstOrDefault(x => x == sbs[0]);
    Int32 sbsLen = sbs.Length;
    Int32 sbsCurMatch = 0;
    for (int i = 0; i < lb.Count; i++)
    {
        if (lb[i] == sbs[sbsCurMatch])
        {
            sbsCurMatch++;
            if (sbsCurMatch == sbsLen)
            {
                //int index = lb.FindIndex(e => sbs.All(f => f.Equals(e)));  // fails to find a match
                IndexOfArray = i - sbsLen + 1;
                return;
            }
        }
        else 
        {
            sbsCurMatch = 0;
        }
    }
    return -1;
}
4

3 に答える 3

4

ブルートフォースは常にオプションです。他のいくつかの方法に比べて遅いですが、実際には通常それほど悪くはありません。実装が簡単で、lbyte大規模でなく、病理学的データがない場合でも十分に受け入れられます。

力ずくの文字列検索と同じ概念です。

于 2013-04-20T00:16:49.683 に答える
3

ここでは、 Boyer-Moore アルゴリズムが役立つことがあります。リストを配列に変換して検索します。アルゴリズム コードは、この投稿から取得されます。

static int SimpleBoyerMooreSearch(byte[] haystack, byte[] needle)
{
    int[] lookup = new int[256];
    for (int i = 0; i < lookup.Length; i++) { lookup[i] = needle.Length; }

    for (int i = 0; i < needle.Length; i++)
    {
        lookup[needle[i]] = needle.Length - i - 1;
    }

    int index = needle.Length - 1;
    var lastByte = needle.Last();
    while (index < haystack.Length)
    {
        var checkByte = haystack[index];
        if (haystack[index] == lastByte)
        {
            bool found = true;
            for (int j = needle.Length - 2; j >= 0; j--)
            {
                if (haystack[index - needle.Length + j + 1] != needle[j])
                {
                    found = false;
                    break;
                }
            }

            if (found)
                return index - needle.Length + 1;
            else
                index++;
        }
        else
        {
            index += lookup[checkByte];
        }
    }
    return -1;
}

すると、このように検索できます。lbyteが一定時間経過しても変わらない場合は、一度配列に変換して渡すだけです。

//index is returned, or -1 if 'searchBytes' is not found
int startIndex = SimpleBoyerMooreSearch(lbyte.ToArray(), searchBytes);

コメントに基づいて更新します。これは、配列とリストIList（および実装する他のものをIList渡すことができること）を意味する実装です。

 static int SimpleBoyerMooreSearch(IList<byte> haystack, IList<byte> needle)
 {
    int[] lookup = new int[256];
    for (int i = 0; i < lookup.Length; i++) { lookup[i] = needle.Count; }

    for (int i = 0; i < needle.Count; i++)
    {
        lookup[needle[i]] = needle.Count - i - 1;
    }

    int index = needle.Count - 1;
    var lastByte = needle[index];
    while (index < haystack.Count)
    {
        var checkByte = haystack[index];
        if (haystack[index] == lastByte)
        {
            bool found = true;
            for (int j = needle.Count - 2; j >= 0; j--)
            {
                if (haystack[index - needle.Count + j + 1] != needle[j])
                {
                    found = false;
                    break;
                }
            }

            if (found)
                return index - needle.Count + 1;
            else
                index++;
        }
        else
        {
            index += lookup[checkByte];
        }
    }
    return -1;
}

配列とリストは IList を実装しているため、あなたのケースで呼び出すときに変換は必要ありません。

int startIndex = SimpleBoyerMooreSearch(lbyte, searchBytes);
于 2013-04-20T00:24:23.910 に答える
1

ラムダ式でできる別の方法

int index = lbyte.FindIndex(e => searchBytes.All(i => i.Equals(e));
于 2013-04-20T00:39:00.223 に答える