दिलचस्प पोस्ट
सही बाश और शैल स्क्रिप्ट चर पूंजीकरण पिक्सेल में स्क्रीन आयाम प्राप्त करें सी ++ में संरचना और कक्षा के बीच अंतर क्या हैं? संशोधन के लिए डेटाबेस डिजाइन? सी में एक +++++ बी काम क्यों नहीं करता? एचटीएमएल 5 वीडियो टैग के साथ स्थानीय (हार्ड ड्राइव) वीडियो फाइल खेलें? आईओओ – कोकाओपोड के साथ बिल्ड विफल रहता है हेडर फाइल नहीं मिल सकती वेक्टर के बीच विकल्प: :: आकार () और वेक्टर :: आरक्षित () मैं regex के साथ ओवरलैपिंग स्ट्रिंग का मिलान कैसे कर सकता हूं? Attr_accessor और attr_accessible के बीच का अंतर कैसे खिड़की का पता लगाने के लिए। प्रिंट () समाप्त PHP यूएमएल जेनरेटर क्यों कक्षा में प्रारंभिक केवल = या {} उपयोग कर सकते हैं? फ़ंक्शन के अंदर सरणी की लंबाई खोजना निंजा 2 + (और मैं अपने मॉड्यूल की व्यवस्था कैसे करूँ) के साथ इंजेक्शन कहाँ करूँ?

बाइट सरणी पैटर्न खोज

किसी को बाइट [] सरणी में एक बाइट पैटर्न के लिए खोज / मिलान करने का एक अच्छा और प्रभावी तरीका पता है और उसके बाद स्थिति वापस आती है

उदाहरण के लिए

byte[] pattern = new byte[] {12,3,5,76,8,0,6,125}; byte[] toBeSearched = new byte[] {23,36,43,76,125,56,34,234,12,3,5,76,8,0,6,125,234,56,211,122,22,4,7,89,76,64,12,3,5,76,8,0,6,125} 

वेब के समाधान से एकत्रित समाधान "बाइट सरणी पैटर्न खोज"

क्या मैं कुछ सुझाव देता हूं जिसमें स्ट्रिंग्स बनाने, एरेज़ या असुरक्षित कोड कॉपी करना शामिल नहीं है:

 using System; using System.Collections.Generic; static class ByteArrayRocks { static readonly int [] Empty = new int [0]; public static int [] Locate (this byte [] self, byte [] candidate) { if (IsEmptyLocate (self, candidate)) return Empty; var list = new List<int> (); for (int i = 0; i < self.Length; i++) { if (!IsMatch (self, i, candidate)) continue; list.Add (i); } return list.Count == 0 ? Empty : list.ToArray (); } static bool IsMatch (byte [] array, int position, byte [] candidate) { if (candidate.Length > (array.Length - position)) return false; for (int i = 0; i < candidate.Length; i++) if (array [position + i] != candidate [i]) return false; return true; } static bool IsEmptyLocate (byte [] array, byte [] candidate) { return array == null || candidate == null || array.Length == 0 || candidate.Length == 0 || candidate.Length > array.Length; } static void Main () { var data = new byte [] { 23, 36, 43, 76, 125, 56, 34, 234, 12, 3, 5, 76, 8, 0, 6, 125, 234, 56, 211, 122, 22, 4, 7, 89, 76, 64, 12, 3, 5, 76, 8, 0, 6, 125 }; var pattern = new byte [] { 12, 3, 5, 76, 8, 0, 6, 125 }; foreach (var position in data.Locate (pattern)) Console.WriteLine (position); } } 

संपादित करें (IAbstract द्वारा)यहां पोस्ट की सामग्री हिलना क्योंकि यह एक उत्तर नहीं है

जिज्ञासा से, मैंने अलग-अलग उत्तरों के साथ एक छोटा सा बेंचमार्क बनाया है

यहां लाखों पुनरावृत्तियों के परिणाम दिए गए हैं:

 solution [Locate]: 00:00:00.7714027 solution [FindAll]: 00:00:03.5404399 solution [SearchBytePattern]: 00:00:01.1105190 solution [MatchBytePattern]: 00:00:03.0658212 

LINQ विधि का उपयोग करें

 public static IEnumerable<int> PatternAt(byte[] source, byte[] pattern) { for (int i = 0; i < source.Length; i++) { if (source.Skip(i).Take(pattern.Length).SequenceEqual(pattern)) { yield return i; } } } 

बहुत आसान!

कुशल बॉययर-मूर एल्गोरिथम का उपयोग करें

इसे स्ट्रिंग्स के साथ स्ट्रिंग ढूंढने के लिए डिज़ाइन किया गया है, लेकिन आपको बाइट एरेज़ को इस पर प्रोजेक्ट करने के लिए बहुत कम कल्पना की आवश्यकता है।

सामान्य तौर पर सबसे अच्छा जवाब है: किसी भी स्ट्रिंग खोज अल्गोरिदम का उपयोग करें जो आपको पसंद है :)।

मूलतः मैंने कुछ पुराने कोड का उपयोग किया जो मैंने प्रयोग किया था लेकिन जेबी इवाइन के मानक के बारे में उत्सुक था। मैंने पाया कि मेरा समाधान बेवकूफ़ धीमा था ऐसा प्रतीत होता है कि ब्रूनो कंडोच की खोजबिट पाटर्न सबसे तेज है। मैं समझ नहीं सका क्योंकि विशेषकर जब से वह एक अर्रे का उपयोग करता है। कॉपी और एक एक्सटेंशन विधि लेकिन जेबी के परीक्षणों में सबूत है, इसलिए ब्रूनो की किस्मत।

मैंने बिट्स को और भी सरलीकृत किया है, इसलिए उम्मीद है कि यह स्पष्ट और सरल समाधान होगा। (ब्रूनो कॉंडे द्वारा किए गए सभी कड़ी मेहनत) एन्हांसमेंट हैं:

  • Buffer.BlockCopy
  • Array.IndexOf <बाइट>
  • जबकि पाश के लिए लूप के बजाय लूप
  • सूचकांक पैरामीटर प्रारंभ करें
  • विस्तार विधि में परिवर्तित

     public static List<int> IndexOfSequence(this byte[] buffer, byte[] pattern, int startIndex) { List<int> positions = new List<int>(); int i = Array.IndexOf<byte>(buffer, pattern[0], startIndex); while (i >= 0 && i <= buffer.Length - pattern.Length) { byte[] segment = new byte[pattern.Length]; Buffer.BlockCopy(buffer, i, segment, 0, pattern.Length); if (segment.SequenceEqual<byte>(pattern)) positions.Add(i); i = Array.IndexOf<byte>(buffer, pattern[0], i + pattern.Length); } return positions; } 

मेरा समाधान:

 class Program { public static void Main() { byte[] pattern = new byte[] {12,3,5,76,8,0,6,125}; byte[] toBeSearched = new byte[] { 23, 36, 43, 76, 125, 56, 34, 234, 12, 3, 5, 76, 8, 0, 6, 125, 234, 56, 211, 122, 22, 4, 7, 89, 76, 64, 12, 3, 5, 76, 8, 0, 6, 125}; List<int> positions = SearchBytePattern(pattern, toBeSearched); foreach (var item in positions) { Console.WriteLine("Pattern matched at pos {0}", item); } } static public List<int> SearchBytePattern(byte[] pattern, byte[] bytes) { List<int> positions = new List<int>(); int patternLength = pattern.Length; int totalLength = bytes.Length; byte firstMatchByte = pattern[0]; for (int i = 0; i < totalLength; i++) { if (firstMatchByte == bytes[i] && totalLength - i >= patternLength) { byte[] match = new byte[patternLength]; Array.Copy(bytes, i, match, 0, patternLength); if (match.SequenceEqual<byte>(pattern)) { positions.Add(i); i += patternLength - 1; } } } return positions; } } 

मैं एक LINQ विधि / उत्तर 🙂 गुम था

 /// <summary> /// Searches in the haystack array for the given needle using the default equality operator and returns the index at which the needle starts. /// </summary> /// <typeparam name="T">Type of the arrays.</typeparam> /// <param name="haystack">Sequence to operate on.</param> /// <param name="needle">Sequence to search for.</param> /// <returns>Index of the needle within the haystack or -1 if the needle isn't contained.</returns> public static IEnumerable<int> IndexOf<T>(this T[] haystack, T[] needle) { if ((needle != null) && (haystack.Length >= needle.Length)) { for (int l = 0; l < haystack.Length - needle.Length + 1; l++) { if (!needle.Where((data, index) => !haystack[l + index].Equals(data)).Any()) { yield return l; } } } } 

ऊपर Foubar के उत्तर का मेरा संस्करण, जो घास की ढंका के अंत से पहले की खोज से बचा जाता है, और एक शुरू ऑफसेट निर्दिष्ट करने की अनुमति देता है। मानता है सुई खाली या घास की ढंका से अधिक नहीं है

 public static unsafe long IndexOf(this byte[] haystack, byte[] needle, long startOffset = 0) { fixed (byte* h = haystack) fixed (byte* n = needle) { for (byte* hNext = h + startOffset, hEnd = h + haystack.LongLength + 1 - needle.LongLength, nEnd = n + needle.LongLength; hNext < hEnd; hNext++) for (byte* hInc = hNext, nInc = n; *nInc == *hInc; hInc++) if (++nInc == nEnd) return hNext - h; return -1; } } 

यह मेरा प्राप्य, अधिक सरल और तेज़ है:

 int Search(byte[] src, byte[] pattern) { int c = src.Length - pattern.Length + 1; int j; for (int i = 0; i < c; i++) { if (src[i] != pattern[0]) continue; for (j = pattern.Length - 1; j >= 1 && src[i + j] == pattern[j]; j--) ; if (j == 0) return i; } return -1; } 

ये सरल और तेज़ तरीके हैं जिनका आप उपयोग कर सकते हैं, और इन की तुलना में तेज़ी से कुछ भी नहीं होगा यह असुरक्षित है लेकिन यह है कि हम किस प्रकार पॉइंटर्स का उपयोग करते हैं वह गति है तो यहां मैं आपको अपने विस्तार विधियों की पेशकश करता हूं जो कि मैं एक एकल के लिए खोज करता हूं, और घटकों के अनुक्रमित सूची का उपयोग करता हूं। मैं यह कहना चाहूंगा कि यह सबसे साफ कोड है

  public static unsafe long IndexOf(this byte[] Haystack, byte[] Needle) { fixed (byte* H = Haystack) fixed (byte* N = Needle) { long i = 0; for (byte* hNext = H, hEnd = H + Haystack.LongLength; hNext < hEnd; i++, hNext++) { bool Found = true; for (byte* hInc = hNext, nInc = N, nEnd = N + Needle.LongLength; Found && nInc < nEnd; Found = *nInc == *hInc, nInc++, hInc++) ; if (Found) return i; } return -1; } } public static unsafe List<long> IndexesOf(this byte[] Haystack, byte[] Needle) { List<long> Indexes = new List<long>(); fixed (byte* H = Haystack) fixed (byte* N = Needle) { long i = 0; for (byte* hNext = H, hEnd = H + Haystack.LongLength; hNext < hEnd; i++, hNext++) { bool Found = true; for (byte* hInc = hNext, nInc = N, nEnd = N + Needle.LongLength; Found && nInc < nEnd; Found = *nInc == *hInc, nInc++, hInc++) ; if (Found) Indexes.Add(i); } return Indexes; } } 

पता लगाने के साथ बेंचमार्क, यह 1.2-1.4x तेज है

जेबी इवाइन का उत्तर है:

  for (int i = 0; i < self.Length; i++) { if (!IsMatch (self, i, candidate)) continue; list.Add (i); } 

और उसके बाद IsMatch फ़ंक्शन पहले जांचता है कि क्या candidate खोजा जा रहा है उस सरणी की सीमा से परे है या नहीं।

यह अधिक कुशल होगा यदि लूप को कोडित किया गया है:

  for (int i = 0; i < self.Length - candidate.Length; i++) { if (!IsMatch (self, i, candidate)) continue; list.Add (i); } 

इस बिंदु पर कोई भी IsMatch की शुरुआत से परीक्षण को समाप्त कर सकता है , जब तक कि आप पूर्व-शर्तों के माध्यम से अनुबंध करते हैं, तब तक इसे "अवैध" मापदंडों के साथ नहीं बुलाते।

मैंने अपने जवाब से सुझावों का उपयोग करते हुए एक नया फ़ंक्शन बनाया है और अल्नितक द्वारा जवाब दिया है।

 public static List<Int32> LocateSubset(Byte[] superSet, Byte[] subSet) { if ((superSet == null) || (subSet == null)) { throw new ArgumentNullException(); } if ((superSet.Length < subSet.Length) || (superSet.Length == 0) || (subSet.Length == 0)) { return new List<Int32>(); } var result = new List<Int32>(); Int32 currentIndex = 0; Int32 maxIndex = superSet.Length - subSet.Length; while (currentIndex < maxIndex) { Int32 matchCount = CountMatches(superSet, currentIndex, subSet); if (matchCount == subSet.Length) { result.Add(currentIndex); } currentIndex++; if (matchCount > 0) { currentIndex += matchCount - 1; } } return result; } private static Int32 CountMatches(Byte[] superSet, int startIndex, Byte[] subSet) { Int32 currentOffset = 0; while (currentOffset < subSet.Length) { if (superSet[startIndex + currentOffset] != subSet[currentOffset]) { break; } currentOffset++; } return currentOffset; } 

एकमात्र हिस्सा मैं बहुत खुश नहीं हूँ के बारे में है

  currentIndex++; if (matchCount > 0) { currentIndex += matchCount - 1; } 

भाग … मैं 1 से बचने के लिए अगर अन्य का उपयोग करना चाहूंगा, लेकिन इससे बेहतर शाखा की भविष्यवाणी हो सकती है (हालांकि मुझे यकीन नहीं है कि यह उस बात से ज्यादा मायने रखता है) ..

सरल मुश्किल क्यों बनाते हैं? यह लूप के लिए किसी भी भाषा में किया जा सकता है। यहाँ सी # में एक है:

 सिस्टम का उपयोग कर;
 System.Collections.Generic का उपयोग कर;

 नामस्थान बाइनरी खोज
 {
     कक्षा कार्यक्रम
     {
         स्थिर शून्य मुख्य (स्ट्रिंग [] आर्ग्स)
         {
             बाइट [] पैटर्न = नया बाइट [] {12,3,5,76,8,0,6,125};
             बाइट [] टू बीयर की गई = नई बाइट [] (23,36,43,76,125,56,34,234,12,3,5,76,8,0,6,125,234,56,211, 
122,22,4,7,89,76,64,12,3,5,76,8,0,6,125}; सूची <int> occurences = findOcurences (toBeSearched, pattern); फॉरचाच (घटनाओं में पूर्णांक) { कंसोल.प्रकाशलाइन ("0-आधारित सूचकांक से शुरू हुई मैच मिला:" + घटना); } } स्थैतिक सूची <int> खोजओक्चरनेंस (बाइट [] घास का ढेर, बाइट [] सुई) { सूची <int> occurences = नई सूची <int> (); के लिए (इंट I = 0; i <haystack.Length; i ++) { अगर (सुई [0] == हेज़स्टैक [आई]) { bool found = true; int j, k; के लिए (जे = 0, कश्मीर = i; जे <सुई। लांघ; जे ++, कश्मीर ++) { अगर (कश्मीर> = घास का ढेर। लांघ || सुई [जे]! = घास का ढेर [के]) { पाया = झूठा; टूटना; } } अगर मिल गया) { occurences.Add (i - 1); मैं = कश्मीर; } } } वापसी की घटनाएं; } } }

समय लेने के लिए शुक्रिया…

यह वह कोड है जिसका उपयोग मैं / मेरे सवाल से पहले करने से पहले / परीक्षण कर रहा था … मैंने इस सवाल का कारण यह पूछा था कि मैं निश्चित है कि मैं ऐसा करने के लिए इष्टतम कोड का उपयोग नहीं कर रहा हूं … तो फिर धन्यवाद समय लेने के लिए!

  private static int CountPatternMatches(byte[] pattern, byte[] bytes) { int counter = 0; for (int i = 0; i < bytes.Length; i++) { if (bytes[i] == pattern[0] && (i + pattern.Length) < bytes.Length) { for (int x = 1; x < pattern.Length; x++) { if (pattern[x] != bytes[x+i]) { break; } if (x == pattern.Length -1) { counter++; i = i + pattern.Length; } } } } return counter; } 

जो कोई भी मेरे कोड में कोई त्रुटि देखता है? क्या यह एक हैशिस दृष्टिकोण के रूप में माना जाता है? मैंने लगभग हर नमूने की कोशिश की है जो आप लोग पोस्ट कर चुके हैं और मुझे मैच के परिणामों में कुछ बदलाव मिलते हैं। मैं अपने परीक्षणों को ~ 10 एमबी बाइट सरणी के साथ चला रहा हूं जैसा कि मेरे लिए बीयरसर्चित सरणी है

मैं एक समाधान का उपयोग करेगा जो एक स्ट्रिंग में कनवर्ट करते हुए मिलान करता है …

आपको Knuth-Morris-Pratt खोज एल्गोरिथ्म को कार्यान्वित करने के लिए सरल कार्य लिखना चाहिए। यह सबसे तेज़ सरल एल्गोरिथ्म होगा, जो आप सही अनुक्रमित खोजने के लिए उपयोग कर सकते हैं। (आप बॉयर-मूर का उपयोग कर सकते हैं लेकिन इसकी अधिक सेटअप की आवश्यकता होगी

आपके द्वारा एल्गोरिदम को अनुकूलित करने के बाद, आप अन्य प्रकार की ऑप्टिमाइज़ेशन देखने की कोशिश कर सकते हैं। लेकिन आप मूल बातें से शुरू करना चाहिए

उदाहरण के लिए, वर्तमान "सबसे तेज़" जेबी इवान द्वारा Locate समाधान है

यदि आप कोर को देखें तो

  for (int i = 0; i < self.Length; i++) { if (!IsMatch (self, i, candidate)) continue; list.Add (i); } 

उप एल्गोरिथ्म के एक मैच के बाद, यह i + 1 पर एक मैच ढूंढना शुरू कर देगा, लेकिन आप पहले से ही जानते हैं कि पहला संभावित मैच मैं + उम्मीदवार होगा। इसलिए यदि आप जोड़ते हैं,

 i += candidate.Length -2; // -2 instead of -1 because the i++ will add the last index 

यह बहुत तेजी से होगा जब आप सुपरसेट के सबसेट की बहुत सारी घटनाओं की अपेक्षा करते हैं। (ब्रूनो कोंडे अपने समाधान में पहले से ही ऐसा करता है)

लेकिन यह केएनपी एल्गोरिथ्म का सिर्फ एक आधा हिस्सा है, आपको उस नंबर के लिए एक अतिरिक्त पैरामीटर भी जोड़ना चाहिए, जिसे आइसमाच नामक नामक नंबर दिया गया है, जो कि एक आउट पैरामीटर होगा।

यह निम्नलिखित को हल करेगा:

 int validMatches = 0; if (!IsMatch (self, i, candidate, out validMatches)) { i += validMatches - 1; // -1 because the i++ will do the last one continue; } 

तथा

 static bool IsMatch (byte [] array, int position, byte [] candidate, out int numberOfValidMatches) { numberOfValidMatches = 0; if (candidate.Length > (array.Length - position)) return false; for (i = 0; i < candidate.Length; i++) { if (array [position + i] != candidate [i]) return false; numberOfValidMatches++; } return true; } 

रिफैक्टरिंग का एक छोटा सा और आप संख्याओं का उपयोग कर सकते हैंवाप-मैट्स को लूप वैरिएबल के रूप में, और 2 और -1 से बचने के लिए थोड़ी सी समय तक स्थिति का पता लगाएं। लेकिन मैं सिर्फ यह स्पष्ट करना चाहता था कि आप केएमपी एल्गोरिदम कैसे जोड़ सकते हैं।

स्पीड सब कुछ नहीं है क्या आप उन्हें स्थिरता के लिए जांचते हैं?

मैंने यहां सूचीबद्ध सभी कोड का परीक्षण नहीं किया। मैंने अपने कोड का परीक्षण किया (जो पूरी तरह अनुरूप नहीं था, मैं स्वीकार करता हूं) और सूचकांक ओफ़ स्यूएंसेंस मैंने पाया कि कई परीक्षणों के लिए सूचकांक की अपेक्षा मेरे कोड की तुलना में काफी तेज थी, लेकिन दोहराया परीक्षण के साथ मुझे पता चला कि यह कम संगत था। विशेष रूप से यह सरणी के अंत में पैटर्न खोजने में सबसे अधिक परेशानी होती है लेकिन यह कभी-कभी सरणी के बीच में भी उन्हें याद नहीं करेगा।

मेरे परीक्षण कोड को दक्षता के लिए तैयार नहीं किया गया है, मैं कुछ यादृच्छिक आंकड़ों के साथ ही अंदर जाना चाहता था। यह परीक्षण पैटर्न लगभग एक एचपी फॉर्म अपलोड स्ट्रीम में एक सीमा चिन्ह की तरह है। जब मैं इस कोड में दौड़ रहा था, तब मैं देख रहा था, इसलिए मुझे लगा कि मैं उस तरह के डेटा के साथ परीक्षण करूँगा जिसे मैं खोज रहा हूं। ऐसा प्रतीत होता है कि पैटर्न जितना ज्यादा होता है, उतना ही अक्सर सूचकांक की गुणवत्ता एक मूल्य की कमी होगी।

 private static void TestMethod() { Random rnd = new Random(DateTime.Now.Millisecond); string Pattern = "-------------------------------65498495198498"; byte[] pattern = Encoding.ASCII.GetBytes(Pattern); byte[] testBytes; int count = 3; for (int i = 0; i < 100; i++) { StringBuilder TestString = new StringBuilder(2500); TestString.Append(Pattern); byte[] buf = new byte[1000]; rnd.NextBytes(buf); TestString.Append(Encoding.ASCII.GetString(buf)); TestString.Append(Pattern); rnd.NextBytes(buf); TestString.Append(Encoding.ASCII.GetString(buf)); TestString.Append(Pattern); testBytes = Encoding.ASCII.GetBytes(TestString.ToString()); List<int> idx = IndexOfSequence(ref testBytes, pattern, 0); if (idx.Count != count) { Console.Write("change from {0} to {1} on iteration {2}: ", count, idx.Count, i); foreach (int ix in idx) { Console.Write("{0}, ", ix); } Console.WriteLine(); count = idx.Count; } } Console.WriteLine("Press ENTER to exit"); Console.ReadLine(); } 

(जाहिर है मैं इस परीक्षा के लिए एक सामान्य विधि में वापस अनुक्रमण से IndexOfequence को परिवर्तित कर देता हूं)

यहां मेरे आउटपुट का एक नमूना चलाने है:

 change from 3 to 2 on iteration 1: 0, 2090, change from 2 to 3 on iteration 2: 0, 1045, 2090, change from 3 to 2 on iteration 3: 0, 1045, change from 2 to 3 on iteration 4: 0, 1045, 2090, change from 3 to 2 on iteration 6: 0, 2090, change from 2 to 3 on iteration 7: 0, 1045, 2090, change from 3 to 2 on iteration 11: 0, 2090, change from 2 to 3 on iteration 12: 0, 1045, 2090, change from 3 to 2 on iteration 14: 0, 2090, change from 2 to 3 on iteration 16: 0, 1045, 2090, change from 3 to 2 on iteration 17: 0, 1045, change from 2 to 3 on iteration 18: 0, 1045, 2090, change from 3 to 1 on iteration 20: 0, change from 1 to 3 on iteration 21: 0, 1045, 2090, change from 3 to 2 on iteration 22: 0, 2090, change from 2 to 3 on iteration 23: 0, 1045, 2090, change from 3 to 2 on iteration 24: 0, 2090, change from 2 to 3 on iteration 25: 0, 1045, 2090, change from 3 to 2 on iteration 26: 0, 2090, change from 2 to 3 on iteration 27: 0, 1045, 2090, change from 3 to 2 on iteration 43: 0, 1045, change from 2 to 3 on iteration 44: 0, 1045, 2090, change from 3 to 2 on iteration 48: 0, 1045, change from 2 to 3 on iteration 49: 0, 1045, 2090, change from 3 to 2 on iteration 50: 0, 2090, change from 2 to 3 on iteration 52: 0, 1045, 2090, change from 3 to 2 on iteration 54: 0, 1045, change from 2 to 3 on iteration 57: 0, 1045, 2090, change from 3 to 2 on iteration 62: 0, 1045, change from 2 to 3 on iteration 63: 0, 1045, 2090, change from 3 to 2 on iteration 72: 0, 2090, change from 2 to 3 on iteration 73: 0, 1045, 2090, change from 3 to 2 on iteration 75: 0, 2090, change from 2 to 3 on iteration 76: 0, 1045, 2090, change from 3 to 2 on iteration 78: 0, 1045, change from 2 to 3 on iteration 79: 0, 1045, 2090, change from 3 to 2 on iteration 81: 0, 2090, change from 2 to 3 on iteration 82: 0, 1045, 2090, change from 3 to 2 on iteration 85: 0, 2090, change from 2 to 3 on iteration 86: 0, 1045, 2090, change from 3 to 2 on iteration 89: 0, 2090, change from 2 to 3 on iteration 90: 0, 1045, 2090, change from 3 to 2 on iteration 91: 0, 2090, change from 2 to 1 on iteration 92: 0, change from 1 to 3 on iteration 93: 0, 1045, 2090, change from 3 to 1 on iteration 99: 0, 

मैं इंडेक्सऑफ़ सफ़लता को चुनने का मतलब नहीं हूं, यह सिर्फ उसी के रूप में हुआ जिसे मैंने आज के साथ काम करना शुरू किया। मैंने उस दिन के अंत में देखा कि यह डेटा में पैटर्नों को याद नहीं रहा है, इसलिए मैंने आज रात को अपना खुद का पैटर्न मैटचर लिखा है यह उतना तेज नहीं है जितना कि। मैं इसे थोड़ा और अधिक देखने के लिए जा रहा हूँ कि क्या मैं इसे पोस्ट करने से पहले 100% संगत प्राप्त कर सकता हूं।

मैं सिर्फ हर किसी को याद दिलाना चाहता था कि उन्हें इस तरह से चीजों की जांच करनी चाहिए ताकि वे उत्पादन कोड पर भरोसा करने से पहले सुनिश्चित करें कि वे अच्छे, दोहराए जाने वाले परिणाम दें।

मैंने विभिन्न समाधानों की कोशिश की और SearchBytePattern एक को संशोधित कर दिया। मैं एक 30k अनुक्रम पर परीक्षण किया और यह, तेज़ है 🙂

  static public int SearchBytePattern(byte[] pattern, byte[] bytes) { int matches = 0; for (int i = 0; i < bytes.Length; i++) { if (pattern[0] == bytes[i] && bytes.Length - i >= pattern.Length) { bool ismatch = true; for (int j = 1; j < pattern.Length && ismatch == true; j++) { if (bytes[i + j] != pattern[j]) ismatch = false; } if (ismatch) { matches++; i += pattern.Length - 1; } } } return matches; } 

मुझे अपने विचारों को जानने दें।

यहाँ एक समाधान है जिसके साथ मैं आया हूं। मैं कार्यान्वयन के साथ रास्ते में पाया नोट्स शामिल यह आगे, पिछड़े और अलग (/ डीसी) रीमेमेंट मात्रा जैसे दिशा के साथ मेल कर सकता है; घास का ढेर में किसी भी ऑफसेट से शुरू

कोई इनपुट भयानक होगा!

  /// <summary> /// Matches a byte array to another byte array /// forwards or reverse /// </summary> /// <param name="a">byte array</param> /// <param name="offset">start offset</param> /// <param name="len">max length</param> /// <param name="b">byte array</param> /// <param name="direction">to move each iteration</param> /// <returns>true if all bytes match, otherwise false</returns> internal static bool Matches(ref byte[] a, int offset, int len, ref byte[] b, int direction = 1) { #region Only Matched from offset Within a and b, could not differ, eg if you wanted to mach in reverse for only part of a in some of b that would not work //if (direction == 0) throw new ArgumentException("direction"); //for (; offset < len; offset += direction) if (a[offset] != b[offset]) return false; //return true; #endregion //Will match if b contains len of a and return aa index of positive value return IndexOfBytes(ref a, ref offset, len, ref b, len) != -1; } ///Here is the Implementation code /// <summary> /// Swaps two integers without using a temporary variable /// </summary> /// <param name="a"></param> /// <param name="b"></param> internal static void Swap(ref int a, ref int b) { a ^= b; b ^= a; a ^= b; } /// <summary> /// Swaps two bytes without using a temporary variable /// </summary> /// <param name="a"></param> /// <param name="b"></param> internal static void Swap(ref byte a, ref byte b) { a ^= b; b ^= a; a ^= b; } /// <summary> /// Can be used to find if a array starts, ends spot Matches or compltely contains a sub byte array /// Set checkLength to the amount of bytes from the needle you want to match, start at 0 for forward searches start at hayStack.Lenght -1 for reverse matches /// </summary> /// <param name="a">Needle</param> /// <param name="offset">Start in Haystack</param> /// <param name="len">Length of required match</param> /// <param name="b">Haystack</param> /// <param name="direction">Which way to move the iterator</param> /// <returns>Index if found, otherwise -1</returns> internal static int IndexOfBytes(ref byte[] needle, ref int offset, int checkLength, ref byte[] haystack, int direction = 1) { //If the direction is == 0 we would spin forever making no progress if (direction == 0) throw new ArgumentException("direction"); //Cache the length of the needle and the haystack, setup the endIndex for a reverse search int needleLength = needle.Length, haystackLength = haystack.Length, endIndex = 0, workingOffset = offset; //Allocate a value for the endIndex and workingOffset //If we are going forward then the bound is the haystackLength if (direction >= 1) endIndex = haystackLength; #region [Optomization - Not Required] //{ //I though this was required for partial matching but it seems it is not needed in this form //workingOffset = needleLength - checkLength; //} #endregion else Swap(ref workingOffset, ref endIndex); #region [Optomization - Not Required] //{ //Otherwise we are going in reverse and the endIndex is the needleLength - checkLength //I though the length had to be adjusted but it seems it is not needed in this form //endIndex = needleLength - checkLength; //} #endregion #region [Optomized to above] //Allocate a value for the endIndex //endIndex = direction >= 1 ? haystackLength : needleLength - checkLength, //Determine the workingOffset //workingOffset = offset > needleLength ? offset : needleLength; //If we are doing in reverse swap the two //if (workingOffset > endIndex) Swap(ref workingOffset, ref endIndex); //Else we are going in forward direction do the offset is adjusted by the length of the check //else workingOffset -= checkLength; //Start at the checkIndex (workingOffset) every search attempt #endregion //Save the checkIndex (used after the for loop is done with it to determine if the match was checkLength long) int checkIndex = workingOffset; #region [For Loop Version] ///Optomized with while (single op) ///for (int checkIndex = workingOffset; checkIndex < endIndex; offset += direction, checkIndex = workingOffset) ///{ ///Start at the checkIndex /// While the checkIndex < checkLength move forward /// If NOT (the needle at the checkIndex matched the haystack at the offset + checkIndex) BREAK ELSE we have a match continue the search /// for (; checkIndex < checkLength; ++checkIndex) if (needle[checkIndex] != haystack[offset + checkIndex]) break; else continue; /// If the match was the length of the check /// if (checkIndex == checkLength) return offset; //We are done matching ///} #endregion //While the checkIndex < endIndex while (checkIndex < endIndex) { for (; checkIndex < checkLength; ++checkIndex) if (needle[checkIndex] != haystack[offset + checkIndex]) break; else continue; //If the match was the length of the check if (checkIndex == checkLength) return offset; //We are done matching //Move the offset by the direction, reset the checkIndex to the workingOffset offset += direction; checkIndex = workingOffset; } //We did not have a match with the given options return -1; } 

यहाँ मेरा (सबसे ज्यादा प्रदर्शनकर्ता) समाधान नहीं है यह इस तथ्य पर निर्भर करता है कि बाइट / लैटिन -1 रूपांतरण दोषरहित है, जो बाइट / एएससीआईआई या बाइट / यूटीएफ 8 रूपांतरण के लिए सही नहीं है।

इसका लाभ यह है कि यह किसी भी बाइट मान के लिए वर्क्स (टीएम) है (कुछ अन्य समाधान बाइट्स 0x80-0xff के साथ गलत तरीके से काम करते हैं) और अधिक उन्नत regex मिलान करने के लिए विस्तारित किया जा सकता है

 using System; using System.Collections.Generic; using System.Text; using System.Text.RegularExpressions; class C { public static void Main() { byte[] data = {0, 100, 0, 255, 100, 0, 100, 0, 255}; byte[] pattern = {0, 255}; foreach (int i in FindAll(data, pattern)) { Console.WriteLine(i); } } public static IEnumerable<int> FindAll( byte[] haystack, byte[] needle ) { // bytes <-> latin-1 conversion is lossless Encoding latin1 = Encoding.GetEncoding("iso-8859-1"); string sHaystack = latin1.GetString(haystack); string sNeedle = latin1.GetString(needle); for (Match m = Regex.Match(sHaystack, Regex.Escape(sNeedle)); m.Success; m = m.NextMatch()) { yield return m.Index; } } } 

मैं थोड़ी देर के लिए पार्टी में हूँ, बॉयर मूर एल्गोरिथ्म का उपयोग करने के बारे में कैसे, लेकिन तार के बजाय बाइट्स की खोज करें। सी # नीचे कोड।

EyeCode इंक

 class Program { static void Main(string[] args) { byte[] text = new byte[] {12,3,5,76,8,0,6,125,23,36,43,76,125,56,34,234,12,4,5,76,8,0,6,125,234,56,211,122,22,4,7,89,76,64,12,3,5,76,8,0,6,123}; byte[] pattern = new byte[] {12,3,5,76,8,0,6,125}; BoyerMoore tmpSearch = new BoyerMoore(pattern,text); Console.WriteLine(tmpSearch.Match()); Console.ReadKey(); } public class BoyerMoore { private static int ALPHABET_SIZE = 256; private byte[] text; private byte[] pattern; private int[] last; private int[] match; private int[] suffix; public BoyerMoore(byte[] pattern, byte[] text) { this.text = text; this.pattern = pattern; last = new int[ALPHABET_SIZE]; match = new int[pattern.Length]; suffix = new int[pattern.Length]; } /** * Searches the pattern in the text. * returns the position of the first occurrence, if found and -1 otherwise. */ public int Match() { // Preprocessing ComputeLast(); ComputeMatch(); // Searching int i = pattern.Length - 1; int j = pattern.Length - 1; while (i < text.Length) { if (pattern[j] == text[i]) { if (j == 0) { return i; } j--; i--; } else { i += pattern.Length - j - 1 + Math.Max(j - last[text[i]], match[j]); j = pattern.Length - 1; } } return -1; } /** * Computes the function last and stores its values in the array last. * last(Char ch) = the index of the right-most occurrence of the character ch * in the pattern; * -1 if ch does not occur in the pattern. */ private void ComputeLast() { for (int k = 0; k < last.Length; k++) { last[k] = -1; } for (int j = pattern.Length-1; j >= 0; j--) { if (last[pattern[j]] < 0) { last[pattern[j]] = j; } } } /** * Computes the function match and stores its values in the array match. * match(j) = min{ s | 0 < s <= j && p[js]!=p[j] * && p[j-s+1]..p[ms-1] is suffix of p[j+1]..p[m-1] }, * if such s exists, else * min{ s | j+1 <= s <= m * && p[0]..p[ms-1] is suffix of p[j+1]..p[m-1] }, * if such s exists, * m, otherwise, * where p is the pattern and m is its length. */ private void ComputeMatch() { /* Phase 1 */ for (int j = 0; j < match.Length; j++) { match[j] = match.Length; } //O(m) ComputeSuffix(); //O(m) /* Phase 2 */ //Uses an auxiliary array, backwards version of the KMP failure function. //suffix[i] = the smallest j > i st p[j..m-1] is a prefix of p[i..m-1], //if there is no such j, suffix[i] = m //Compute the smallest shift s, such that 0 < s <= j and //p[js]!=p[j] and p[j-s+1..ms-1] is suffix of p[j+1..m-1] or j == m-1}, // if such s exists, for (int i = 0; i < match.Length - 1; i++) { int j = suffix[i + 1] - 1; // suffix[i+1] <= suffix[i] + 1 if (suffix[i] > j) { // therefore pattern[i] != pattern[j] match[j] = j - i; } else {// j == suffix[i] match[j] = Math.Min(j - i + match[i], match[j]); } } /* Phase 3 */ //Uses the suffix array to compute each shift s such that //p[0..ms-1] is a suffix of p[j+1..m-1] with j < s < m //and stores the minimum of this shift and the previously computed one. if (suffix[0] < pattern.Length) { for (int j = suffix[0] - 1; j >= 0; j--) { if (suffix[0] < match[j]) { match[j] = suffix[0]; } } { int j = suffix[0]; for (int k = suffix[j]; k < pattern.Length; k = suffix[k]) { while (j < k) { if (match[j] > k) { match[j] = k; } j++; } } } } } /** * Computes the values of suffix, which is an auxiliary array, * backwards version of the KMP failure function. * * suffix[i] = the smallest j > i st p[j..m-1] is a prefix of p[i..m-1], * if there is no such j, suffix[i] = m, ie * p[suffix[i]..m-1] is the longest prefix of p[i..m-1], if suffix[i] < m. */ private void ComputeSuffix() { suffix[suffix.Length-1] = suffix.Length; int j = suffix.Length - 1; for (int i = suffix.Length - 2; i >= 0; i--) { while (j < suffix.Length - 1 && !pattern[j].Equals(pattern[i])) { j = suffix[j + 1] - 1; } if (pattern[j] == pattern[i]) { j--; } suffix[i] = j + 1; } } } } 

Here's a simple code i wrote using only basic data types: (It returns the index of first occurance)

 private static int findMatch(byte[] data, byte[] pattern) { if(pattern.length > data.length){ return -1; } for(int i = 0; i<data.length ;){ int j; for(j=0;j<pattern.length;j++){ if(pattern[j]!=data[i]) break; i++; } if(j==pattern.length){ System.out.println("Pattern found at : "+(i - pattern.length )); return i - pattern.length ; } if(j!=0)continue; i++; } return -1; } 

Just another answer that is easy to follow and pretty efficient for a O(n) type of operation without using unsafe code or copying parts of the source arrays.

Be sure to test. Some of the suggestions found on this topic are susceptible to gotta situations.

  static void Main(string[] args) { // 1 1 1 1 1 1 1 1 1 1 2 2 2 // 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 byte[] buffer = new byte[] { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 5, 5, 0, 5, 5, 1, 2 }; byte[] beginPattern = new byte[] { 1, 0, 2 }; byte[] middlePattern = new byte[] { 8, 9, 10 }; byte[] endPattern = new byte[] { 9, 10, 11 }; byte[] wholePattern = new byte[] { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }; byte[] noMatchPattern = new byte[] { 7, 7, 7 }; int beginIndex = ByteArrayPatternIndex(buffer, beginPattern); int middleIndex = ByteArrayPatternIndex(buffer, middlePattern); int endIndex = ByteArrayPatternIndex(buffer, endPattern); int wholeIndex = ByteArrayPatternIndex(buffer, wholePattern); int noMatchIndex = ByteArrayPatternIndex(buffer, noMatchPattern); } /// <summary> /// Returns the index of the first occurrence of a byte array within another byte array /// </summary> /// <param name="buffer">The byte array to be searched</param> /// <param name="pattern">The byte array that contains the pattern to be found</param> /// <returns>If buffer contains pattern then the index of the first occurrence of pattern within buffer; otherwise, -1</returns> public static int ByteArrayPatternIndex(byte[] buffer, byte[] pattern) { if (buffer != null && pattern != null && pattern.Length <= buffer.Length) { int resumeIndex; for (int i = 0; i <= buffer.Length - pattern.Length; i++) { if (buffer[i] == pattern[0]) // Current byte equals first byte of pattern { resumeIndex = 0; for (int x = 1; x < pattern.Length; x++) { if (buffer[i + x] == pattern[x]) { if (x == pattern.Length - 1) // Matched the entire pattern return i; else if (resumeIndex == 0 && buffer[i + x] == pattern[0]) // The current byte equals the first byte of the pattern so start here on the next outer loop iteration resumeIndex = i + x; } else { if (resumeIndex > 0) i = resumeIndex - 1; // The outer loop iterator will increment so subtract one else if (x > 1) i += (x - 1); // Advance the outer loop variable since we already checked these bytes break; } } } } } return -1; } /// <summary> /// Returns the indexes of each occurrence of a byte array within another byte array /// </summary> /// <param name="buffer">The byte array to be searched</param> /// <param name="pattern">The byte array that contains the pattern to be found</param> /// <returns>If buffer contains pattern then the indexes of the occurrences of pattern within buffer; otherwise, null</returns> /// <remarks>A single byte in the buffer array can only be part of one match. For example, if searching for 1,2,1 in 1,2,1,2,1 only zero would be returned.</remarks> public static int[] ByteArrayPatternIndex(byte[] buffer, byte[] pattern) { if (buffer != null && pattern != null && pattern.Length <= buffer.Length) { List<int> indexes = new List<int>(); int resumeIndex; for (int i = 0; i <= buffer.Length - pattern.Length; i++) { if (buffer[i] == pattern[0]) // Current byte equals first byte of pattern { resumeIndex = 0; for (int x = 1; x < pattern.Length; x++) { if (buffer[i + x] == pattern[x]) { if (x == pattern.Length - 1) // Matched the entire pattern indexes.Add(i); else if (resumeIndex == 0 && buffer[i + x] == pattern[0]) // The current byte equals the first byte of the pattern so start here on the next outer loop iteration resumeIndex = i + x; } else { if (resumeIndex > 0) i = resumeIndex - 1; // The outer loop iterator will increment so subtract one else if (x > 1) i += (x - 1); // Advance the outer loop variable since we already checked these bytes break; } } } } if (indexes.Count > 0) return indexes.ToArray(); } return null; } 

You can use ORegex:

 var oregex = new ORegex<byte>("{0}{1}{2}", x=> x==12, x=> x==3, x=> x==5); var toSearch = new byte[]{1,1,12,3,5,1,12,3,5,5,5,5}; var found = oregex.Matches(toSearch); 

Will be found two matches:

 i:2;l:3 i:6;l:3 

Complexity: O(n*m) in worst case, in real life it is O(n) because of internal state machine. It is faster than .NET Regex in some cases. It is compact, fast and designed especialy for array pattern matching.

I tried to understand Sanchez's proposal and make faster search.Below code's performance nearly equal.But code is more understandable.

 public int Search3(byte[] src, byte[] pattern) { int index = -1; for (int i = 0; i < src.Length; i++) { if (src[i] != pattern[0]) { continue; } else { bool isContinoue = true; for (int j = 1; j < pattern.Length; j++) { if (src[++i] != pattern[j]) { isContinoue = true; break; } if(j == pattern.Length - 1) { isContinoue = false; } } if ( ! isContinoue) { index = i-( pattern.Length-1) ; break; } } } return index; } 

You can put the byte array into String and run match by IndexOf. Or you can at least reuse existing algorithms on string matching.

  [STAThread] static void Main(string[] args) { byte[] pattern = new byte[] {12,3,5,76,8,0,6,125}; byte[] toBeSearched = new byte[] {23,36,43,76,125,56,34,234,12,3,5,76,8,0,6,125,234,56,211,122,22,4,7,89,76,64,12,3,5,76,8,0,6,125}; string needle, haystack; unsafe { fixed(byte * p = pattern) { needle = new string((SByte *) p, 0, pattern.Length); } // fixed fixed (byte * p2 = toBeSearched) { haystack = new string((SByte *) p2, 0, toBeSearched.Length); } // fixed int i = haystack.IndexOf(needle, 0); System.Console.Out.WriteLine(i); } } 

toBeSearched.Except(pattern) will return you differences toBeSearched.Intersect(pattern) will produce set of intersections Generally, you should look into extended methods within Linq extensions