Obliczanie liczby wystąpień w liście/tablicy bajtów przy użyciu innej listy/tablicy bajtów

Question

Próbuję uzyskać liczbę wszystkich wystąpień sekwencji bajtów w kolejnych sekwencjach bajtów. Nie może jednak ponownie użyć bajtów, jeśli już je policzył. Na przykład biorąc pod uwagę ciąg znaków
k.k.k.k.k.k. załóżmy, że sekwencja bajtów to k.k, a następnie znalazłoby tylko 3 wystąpienia zamiast 5, ponieważ byłyby one zepsute, jak: [k.k].[k.k].[k.k]. i nie podoba im się [k.[k].[k].[k].[k].k], gdzie one przejechały i zasadniczo po prostu przesunęły 2 w prawo .

Idealnym pomysłem jest zorientowanie się, jak może wyglądać słownik kompresji lub kodowanie czasu wykonywania. więc celem byłoby uzyskanie tylko 2 części, aby uzyskać tylko 2 części, ponieważ (k.k.k.) jest największym i najlepszym symbolem, jaki możesz mieć.

Oto źródło tej pory:

using System; 
using System.Collections.Generic; 
using System.Collections; 
using System.Linq; 
using System.Text; 
using System.IO; 


    static class Compression 
    { 
     static int Main(string[] args) 
     { 

      List<byte> bytes = File.ReadAllBytes("ok.txt").ToList(); 
      List<List<int>> list = new List<List<int>>(); 

      // Starting Numbers of bytes - This can be changed manually. 
      int StartingNumBytes = bytes.Count; 
      for (int i = StartingNumBytes; i > 0; i--) 
      { 
       Console.WriteLine("i: " + i); 

       for (int ii = 0; ii < bytes.Count - i; ii++) 
       { 
        Console.WriteLine("ii: " + i); 
        // New pattern comes with refresh data. 
        List<byte> pattern = new List<byte>(); 

        for (int iii = 0; iii < i; iii++) 
        { 
         pattern.Add(bytes[ii + iii]); 
        } 



        DisplayBinary(bytes, "red"); 
        DisplayBinary(pattern, "green"); 

        int matches = 0; 
        // foreach (var position in bytes.ToArray().Locate(pattern.ToArray())) 
        for (int position = 0; position < bytes.Count; position++) { 
         if (pattern.Count > (bytes.Count - position)) 
         { 
          continue; 
         } 


         for (int iiii = 0; iiii < pattern.Count; iiii++) 
         { 
          if (bytes[position + iiii] != pattern[iiii]) 
          { 
           //Have to use goto because C# doesn't support continue <level> 
           goto outer; 
          } 

         } 

         // If it made it this far, it has found a match. 
         matches++; 
         Console.WriteLine("Matches: " + matches + " Orig Count: " + bytes.Count + " POS: " + position); 
         if (matches > 1) 
         { 
          int numBytesToRemove = pattern.Count; 
          for (int ra = 0; ra < numBytesToRemove; ra++) 
          { 
           // Remove it at the position it was found at, once it 
           // deletes the first one, the list will shift left and you'll need to be here again. 
           bytes.RemoveAt(position); 
          } 
          DisplayBinary(bytes, "red"); 
          Console.WriteLine(pattern.Count + " Bytes removed."); 

          // Since you deleted some bytes, set the position less because you will need to redo the pos. 
          position = position - 1; 
         } 


         outer: 
          continue; 
        } 

        List<int> sublist = new List<int>(); 
        sublist.Add(matches); 
        sublist.Add(pattern.Count); 
        // Some sort of calculation to determine how good the symbol was 
        sublist.Add(bytes.Count-((matches * pattern.Count)-matches)); 
        list.Add(sublist); 

       } 

      } 



      Display(list); 
      Console.Read(); 
      return 0; 
     } 


     static void DisplayBinary(List<byte> bytes, string color="white") 
     { 
      switch(color){ 
       case "green": 
        Console.ForegroundColor = ConsoleColor.Green; 
        break; 
       case "red": 
        Console.ForegroundColor = ConsoleColor.Red; 
        break; 
       default: 
        break; 
      } 


      for (int i=0; i<bytes.Count; i++) 
      { 
       if (i % 8 ==0) 
        Console.WriteLine(); 
       Console.Write(GetIntBinaryString(bytes[i]) + " "); 
      } 
      Console.WriteLine(); 
      Console.ResetColor(); 
     } 
     static string GetIntBinaryString(int n) 
     { 
      char[] b = new char[8]; 
      int pos = 7; 
      int i = 0; 

      while (i < 8) 
      { 
       if ((n & (1 << i)) != 0) 
       { 
        b[pos] = '1'; 
       } 
       else 
       { 
        b[pos] = '0'; 
       } 
       pos--; 
       i++; 
      } 
      //return new string(b).TrimStart('0'); 
      return new string(b); 
     } 

     static void Display(List<List<int>> list) 
     { 
      // 
      // Display everything in the List. 
      // 
      Console.WriteLine("Elements:"); 
      foreach (var sublist in list) 
      { 
       foreach (var value in sublist) 
       { 
        Console.Write("{0,4}", value); 

       } 
       Console.WriteLine(); 
      } 

      // 
      // Display total count. 
      // 
      int count = 0; 
      foreach (var sublist in list) 
      { 
       count += sublist.Count; 
      } 
      Console.WriteLine("Count:"); 
      Console.WriteLine(count); 
     } 

     static public int SearchBytePattern(byte[] pattern, byte[] bytes) 
     { 
      int matches = 0; 
      // precomputing this shaves some seconds from the loop execution 
      int maxloop = bytes.Length - pattern.Length; 
      for (int i = 0; i < maxloop; i++) 
      { 
       if (pattern[0] == bytes[i]) 
       { 
        bool ismatch = true; 
        for (int j = 1; j < pattern.Length; j++) 
        { 
         if (bytes[i + j] != pattern[j]) 
         { 
          ismatch = false; 
          break; 
         } 
        } 
        if (ismatch) 
        { 
         matches++; 
         i += pattern.Length - 1; 
        } 
       } 
      } 
      return matches; 
     } 
    } 

Patrz postu, aby uzyskać non binarnego pliku powinno być, oto dane binarne: 011010110010111001101011001011100110101100101110011010110010111001101011001011100110101100101110 Jestem nadzieję, że ona mniejsza niż jak go Rozpoczęty.

Answer 1

private static int CountOccurences(byte[] target, byte[] pattern) 
{ 
    var targetString = BitConverter.ToString(target); 
    var patternString = BitConverter.ToString(pattern); 
    return new Regex(patternString).Matches(targetString).Count; 
} 

Answer 2

szybkie i brudne bez regex. chociaż nie jestem pewien, czy odpowiada on na cel pytania, powinien być względnie szybki. myślę, że zamierzam przeprowadzić kilka testów rozrządu przeciwko regex zobaczyć na pewno względnych prędkości:

private int CountOccurrences(string TestString, string TestPattern) 
    { 
     int PatternCount = 0; 
     int SearchIndex = 0; 

     if (TestPattern.Length == 0) 
      throw new ApplicationException("CountOccurrences: Unable to process because TestPattern has zero length."); 

     if (TestString.Length == 0) 
      return 0; 

     do 
     { 
      SearchIndex = TestString.IndexOf(TestPattern, SearchIndex); 

      if (SearchIndex >= 0) 
      { 
       ++PatternCount; 
       SearchIndex += TestPattern.Length; 
      } 
     } 
     while ((SearchIndex >= 0) && (SearchIndex < TestString.Length)); 

     return PatternCount; 
    } 

    private void btnTest_Click(object sender, EventArgs e) 
    { 
     string TestString1 = "k.k.k.k.k.k.k.k.k.k.k.k"; 
     string TestPattern1 = "k.k"; 

     System.Console.WriteLine(CountOccurrences(TestString1, TestPattern1).ToString()); // outputs 6 
     System.Console.WriteLine(CountOccurrences(TestString1 + ".k", TestPattern1).ToString()); // still 6 
     System.Console.WriteLine(CountOccurrences(TestString1, TestPattern1 + ".").ToString()); // only 5 
    } 

Answer 3

Dzięki temu rozwiązaniu, że masz dostęp do poszczególnych indeksów, które dopasowane (podczas wyliczania) lub można nazwać Count() na wynik, aby zobaczyć, jak wiele meczów było:

public static IEnumerable<int> Find<T>(T[] pattern, T[] sequence, bool overlap) 
{ 
    int i = 0; 
    while (i < sequence.Length - pattern.Length + 1) 
    { 
     if (pattern.SequenceEqual(sequence.Skip(i).Take(pattern.Length))) 
     { 
      yield return i; 
      i += overlap ? 1 : pattern.Length; 
     } 
     else 
     { 
      i++; 
     } 
    } 
}

nazywają go z overlap: false aby rozwiązać swój problem lub overlap: true zobaczyć OVERLAPPED mecze

mam AC (jeśli jesteś zainteresowany). ouple innych metod z nieco innym API (wraz z lepszą wydajnością) here, w tym jedną, która działa bezpośrednio na strumienie bajtów.