2

例：

{ 54, 87, 23, 87, 45, 67, 7, 85, 65, 65, 3, 4, 55, 76, 65, 64, 5, 6, 4, 54, 45 , 6, 4};

{ 76, 57, 65, 3, 4, 55, 76, 65, 64, 5, 6, 4, 54, 45 , 8, 65, 66, 57, 6, 7, 7, 56, 6, 7, 44 、57、8、76、54、67};

基本的に、2 つの byte[] があり、両方で最大の同一のバイト シーケンスを見つける必要があります。

私は明白なことを試し、結果をブルートフォースするいくつかのコードを書きました:

var bestIndex = 0;
var bestCount = 0;
for (var i1 = 0; i1 + bestCount < data1.Length; i1++)
{
    var currentCount = 0;
    for (var i2 = 0; i2 < data2.Length; i2++)
    {
        if (data1[i1 + currentCount] == data2[i2])
        {
            currentCount++;
            if (i1 + currentCount == data1.Length)
            {
                bestCount = currentCount;
                bestIndex = i1;
                break;
            }
        }
        else
        {
            if (currentCount > bestCount)
            {
                bestCount = currentCount;
                bestIndex = i1;
            }
            currentCount = 0;
        }
    }
    if (currentCount > bestCount)
    {
        bestCount = currentCount;
        bestIndex = i1;
    }
}

ただし、私のアプリケーションでは、バイト配列ははるかに大きくなり、最大で 1 GB にもなります。したがって、基本的には、それよりも効率的な方法に関するヒント/コードが必要です。

4

3 に答える 3

0

私はループを理解しました、これはより速いはずです。

byte[] data1 = { 54, 87, 23, 87, 45, 67, 7, 85, 65, 65, 3, 4, 55, 76, 65, 64, 5, 6, 4, 54, 45, 6, 4 };
byte[] data2 = { 76, 57, 65, 3, 4, 55, 76, 65, 64, 5, 6, 4, 54, 45, 8, 65, 66, 57, 6, 7, 7, 56, 6, 7, 44, 57, 8, 76, 54, 67 };


//figure out which one is smaller, since that one will limit the range options
byte[] smaller;
byte[] bigger;

if (data1.Count() > data2.Count())
{
    bigger = data1;
    smaller = data2;
}
else
{
    bigger = data2;
    smaller = data1;
}

Tuple<int, int> largestMatchingRange = new Tuple<int, int>(0, 0);

//iterate over slices in reverse length order
for (int length = smaller.Count() - 1; length > 0; length--)
{
    int numberOfSlicesForLength = smaller.Count() - length;

    bool match = true; // set in outer loop to allow for break

    for (int start = 0; start < numberOfSlicesForLength; start++)
    {
        //within a collection of similarly sized slices, we start with the slice found first within the array
        Tuple<int, int> range = new Tuple<int, int>(start, start + length);

        for (int i1 = 0; i1 < bigger.Count(); i1++)
        {
            if (bigger.Count() <= i1 + (range.Item2 - range.Item1))
            {
                //short cut if the available slice from the bigger array is shorter than the range length
                match = false;
                continue;
            }

            match = true; // reset to true to allow for new attempt for each larger array slice

            for (int i2 = range.Item1, i1Temp = i1; i2 < range.Item2; i2++, i1Temp++)
            {
                if (bigger[i1Temp] != smaller[i2])
                {
                    match = false;
                    break;
                }
            }
            if (match)
            {
                largestMatchingRange = range;
                break;
            }
        }
        if (match)
        {
            break;
        }
    }

    if (match)
    {
        break;
    }
}

byte[] largestMatchingBytes = smaller.Skip(largestMatchingRange.Item1).Take(largestMatchingRange.Item2 - largestMatchingRange.Item1).ToArray();
于 2016-08-22T22:03:58.837 に答える
0

バイトを 1 つずつチェックする代わりに、各バイト値のインデックスの場所をリストの辞書に保存できます。あなたの場合、256個のリストの配列の方が良いかもしれません。

List<int>[] index(byte[] a) {        // List<long> if the array can be more than 2GB
    var lists = new List<int>[256];
    for(int i = 0; i < a.Length; i++) {
        var b = a[i];
        if (lists[b] == null) lists[b] = new List<int>();
        lists[b].Add(i);
    }
    return lists;
}

次に、256 の可能なバイト値をループすることができます

byte[] data1 = { 54, 87, 23, 87, 45, 67, 7, 85, 65, 65, 3, 4, 55, 76, 65, 64, 5, 6, 4, 54, 45, 6, 4 };
byte[] data2 = { 76, 57, 65, 3, 4, 55, 76, 65, 64, 5, 6, 4, 54, 45, 8, 65, 66, 57, 6, 7, 7, 56, 6, 7, 44, 57, 8, 76, 54, 67 };

var indexes1 = index(data1);
var indexes2 = index(data2);

var bestIndex = 0;
var bestCount = 0;

for (var b = 0; b < 256; b++)
{
    var list1 = indexes1[b]; if (list1 == null) continue;
    var list2 = indexes1[b]; if (list2 == null) continue;

    foreach(var index1 in list1)
    {
        foreach (var index2 in list2)
        {
            // your code here 
            for (var i1 = index1; i1 < data1.Length - bestCount; i1++)
            {
                var currentCount = 0;
                for (var i2 = index2; i2 < data2.Length; i2++)
                {
                    if (data1[i1 + currentCount] == data2[i2])
                    {
                        currentCount++;
                        if (i1 + currentCount == data1.Length)
                        {
                            bestCount = currentCount;
                            bestIndex = i1;
                            break;
                        }
                    }
                    else
                    {
                        if (currentCount > bestCount)
                        {
                            bestCount = currentCount;
                            bestIndex = i1;
                        }
                        currentCount = 0;
                    }
                }
                if (currentCount > bestCount)
                {
                    bestCount = currentCount;
                    bestIndex = i1;
                }
            }
        }
    }
}

var best = data1.Skip(bestIndex).Take(bestCount);
Debug.Print(bestIndex + ", " + bestCount + ": " + string.Join(", ", best));

理論的には、配列が大きいほど比較が少なくて済むように感じますが、実際にはメモリキャッシュミスが多くなるため、他の回答のように線形の並列バージョンよりも高速になるかどうかはわかりません。私はこれについてあまり考えませんでしたが、うまくいけば、間違った場合に備えていくつかのアイデアを得ることができます.

アップデート

インデックスのリストはバイト配列の 4 倍以上のメモリを必要とするため、メモリが 32 GB 未満の通常のマシンでは、このアイデアがいかに悪いものであるかに気付きました。

于 2016-08-22T23:01:50.797 に答える
0

これについていくつかの考えがありました。これが役立つか害があるかはわかりませんが、最初に最大の可能性を逆算して、一致が見つかったらすぐに終了できるようにすることを検討しましたか.

        byte[] b1 = { 54, 87, 23, 87, 45, 67, 7, 85, 65, 65, 3, 4, 55, 76, 65, 64, 5, 6, 4, 54, 45, 6, 4 };
        byte[] b2 = { 76, 57, 65, 3, 4, 55, 76, 65, 64, 5, 6, 4, 54, 45, 8, 65, 66, 57, 6, 7, 7, 56, 6, 7, 44, 57, 8, 76, 54, 67 };

        //figure out which one is smaller, since that one will limit the range options
        byte[] smaller;
        byte[] bigger;

        if (b1.Count() > b2.Count())
        {
            bigger = b1;
            smaller = b2;
        }
        else
        {
            bigger = b2;
            smaller = b1;
        }


        // doesn't matter what order we put these in, since they will be ordered later by length
        List<Tuple<int, int>> ranges = new List<Tuple<int, int>>();
        Parallel.For(0, smaller.Count(), (i1) => {
            Parallel.For(i1 + 1, smaller.Count(), (i2) =>
            {
                ranges.Add(new Tuple<int, int>(i1, i2));
            });
        });

        // order by length of slice produced by range in descending order
        // this way, once we get an answer, we know nothing else can be longer
        ranges = ranges.OrderByDescending(x => x.Item2 - x.Item1).ToList();

        Tuple<int, int> largestMatchingRange = new Tuple<int, int>(0, 0);

        foreach (Tuple<int, int> range in ranges)
        {
            bool match = true; // set in outer loop to allow for break

            for (int i1 = 0; i1 < bigger.Count(); i1++)
            {
                if (bigger.Count() <= i1 + (range.Item2 - range.Item1))
                {
                    //short cut if the available slice from the bigger array is shorter than the range length
                    match = false;
                    continue;
                }

                match = true; // reset to true to allow for new attempt for each larger array slice

                for (int i2 = range.Item1, i1Temp = i1; i2 < range.Item2; i2++, i1Temp++)
                {
                    if (bigger[i1Temp] != smaller[i2])
                    {
                        match = false;
                        break;
                    }
                }
                if (match)
                {
                    largestMatchingRange = range;
                    break;
                }
            }
            if (match)
            {
                break;
            }
        }

        byte[] largestMatchingBytes = smaller.Skip(largestMatchingRange.Item1).Take(largestMatchingRange.Item2 - largestMatchingRange.Item1).ToArray();
于 2016-08-22T20:55:15.897 に答える