बॉयर-मूर शायद सबसे तेज़ गैर-अनुक्रमित टेक्स्ट-सर्च एल्गोरिदम ज्ञात है। इसलिए मैं इसे Black Belt Coder वेबसाइट के लिए सी # में कार्यान्वित कर रहा हूं।सी # में बॉयर-मूर प्रैक्टिकल?
मैंने यह काम किया था और यह String.IndexOf() की तुलना में अनुमानित प्रदर्शन सुधारों को दिखाता है। हालांकि, जब मैंने StringComparison.OrdinalIndexOf पर तर्क जोड़ा, तो उसने मेरे बॉयर-मूर कार्यान्वयन को बेहतर प्रदर्शन करना शुरू कर दिया। कभी-कभी, काफी मात्रा में।
मुझे आश्चर्य है कि कोई मुझे यह जानने में मदद कर सकता है कि क्यों। मैं समझता हूं कि क्यों StringComparision.Ordinal चीजों को गति दे सकता है, लेकिन यह बॉयर-मूर से तेज कैसे हो सकता है? क्या यह .NET प्लेटफार्म के ऊपरी हिस्से की वजह से है, शायद इसलिए कि सरणी इंडेक्स को यह सुनिश्चित करने के लिए मान्य किया जाना चाहिए कि वे सीमा में हैं, या कुछ और पूरी तरह से। क्या कुछ एल्गोरिदम सी # .NET में व्यावहारिक नहीं हैं?
नीचे कुंजी कोड है।
// Base for search classes
abstract class SearchBase
{
public const int InvalidIndex = -1;
protected string _pattern;
public SearchBase(string pattern) { _pattern = pattern; }
public abstract int Search(string text, int startIndex);
public int Search(string text) { return Search(text, 0); }
}
/// <summary>
/// A simplified Boyer-Moore implementation.
///
/// Note: Uses a single skip array, which uses more memory than needed and
/// may not be large enough. Will be replaced with multi-stage table.
/// </summary>
class BoyerMoore2 : SearchBase
{
private byte[] _skipArray;
public BoyerMoore2(string pattern)
: base(pattern)
{
// TODO: To be replaced with multi-stage table
_skipArray = new byte[0x10000];
for (int i = 0; i < _skipArray.Length; i++)
_skipArray[i] = (byte)_pattern.Length;
for (int i = 0; i < _pattern.Length - 1; i++)
_skipArray[_pattern[i]] = (byte)(_pattern.Length - i - 1);
}
public override int Search(string text, int startIndex)
{
int i = startIndex;
// Loop while there's still room for search term
while (i <= (text.Length - _pattern.Length))
{
// Look if we have a match at this position
int j = _pattern.Length - 1;
while (j >= 0 && _pattern[j] == text[i + j])
j--;
if (j < 0)
{
// Match found
return i;
}
// Advance to next comparision
i += Math.Max(_skipArray[text[i + j]] - _pattern.Length + 1 + j, 1);
}
// No match found
return InvalidIndex;
}
}
संपादित करें: मैं http://www.blackbeltcoder.com/Articles/algorithms/fast-text-search-with-boyer-moore बिल्कुल अपने परीक्षण कोड और इस मामले पर निष्कर्ष पोस्ट किया है।
जोनाथन, "सी # .NET" जैसी कोई चीज़ नहीं है। –
क्या आप इस संभावना को पूरी तरह से बाहर कर रहे हैं कि बॉयर-मूर आंतरिक रूप से .NET में नियोजित है? बस उत्सुक। –
http://stackoverflow.com/questions/2584169/what-algorithm-net-use-for-searching-a-pattern-in-a-string और विशेष रूप से स्वीकृत उत्तर के तहत टिप्पणियां देखें। –