من بين خوارزميات البحث عن مطابقة السلسلة، أشهر خوارزميتين هما خوارزمية KMP (Knuth-Morris-Pratt) وخوارزمية BM (Boyer-Moore). كلا الخوارزميتين لهما أوقات بحث خطية في أسوأ الحالات. ومع ذلك، من الناحية العملية، فإن خوارزمية KMP ليست أسرع بكثير من أبسط دالة مكتبة C strstr()، في حين أن خوارزمية BM غالبًا ما تكون أسرع بمقدار 3-5 مرات من خوارزمية KMP (لم تتم ممارستها شخصيًا). ومع ذلك، فإن خوارزمية BM ليست أسرع خوارزمية حتى الآن، إليك خوارزمية بحث، خوارزمية الأحد، وهي أسرع من خوارزمية BM.
فكرة خوارزمية الأحد تشبه إلى حد كبير فكرة الأحرف السيئة في خوارزمية BM. والفرق الوحيد هو أنه بعد فشل خوارزمية الأحد في المطابقة، فإنها تأخذ الحرف موضعًا واحدًا خلف الجزء الحالي من السلسلة الهدف الذي يتوافق مع سلسلة النمط لإجراء مطابقة سيئة للأحرف. عندما يتم اكتشاف فشل المطابقة، يتم الحكم على ما إذا كان الحرف الموجود في الإزاحة الحالية + طول سلسلة النمط + 1 (من المفترض أن يكون موضع K) في السلسلة الأصلية موجودًا في سلسلة النمط. إذا كان موجودًا، فقم بمحاذاة الموضع مع الحرف الموجود في سلسلة النمط، ثم قم بمطابقته من البداية، وإذا لم يكن موجودًا، فقم بتحريك سلسلة النمط للخلف، وقم بمحاذاته مع الحرف الموجود في k+1 من السلسلة الأصلية، ثم مباراة. كرر العملية المذكورة أعلاه حتى يتم العثور عليها أو العثور على السلسلة الأصلية. لقد كتبت مثالاً صغيرًا لتنفيذ الخوارزمية التالية.
في الكود، يتم تنفيذ خوارزميتين لمطابقة السلسلة، إحداهما هي طريقة الأحد، والأخرى هي الطريقة العادية لتحريك بت واحد في كل مرة. وتظهر مقارنة الكفاءة بين الاثنين في الوظيفة الرئيسية، وكلاهما على مستوى النانو ثانية . تمت إضافة الخطوات التفصيلية للخوارزمية مع التعليقات المقابلة في الكود. فيما يتعلق بخوارزمية BM، سنقارنها ونحللها معًا في المرة القادمة عندما تكون فارغة.
انسخ رمز الكود كما يلي:
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
/**
* @ المؤلف سكوت
*@التاريخ 28 ديسمبر 2013
* @وصف
*/
الطبقة العامة SundySearch {
نص السلسلة = فارغ؛
نمط السلسلة = فارغ؛
int currentPos = 0;
/**
* قائمة مواضع الحرف الأول من السلسلة الفرعية المتطابقة
*/
List<Integer> matchedPosList = new LinkedList<Integer>();
/**
* خريطة الأحرف المطابقة، وتسجيل الأحرف الموجودة في السلسلة المطابقة والإزاحة الأخيرة لكل حرف
*/
Map<Character, Integer> Map = new HashMap<Character, Integer>();
SundySearch العامة (نص السلسلة، نمط السلسلة) {
this.text = text;
this.pattern = Pattern;
this.initMap();
};
/**
* عند مطابقة يوم الأحد، يتم استخدامه لتخزين موضع التواجد الأخير لكل حرف في النمط، بالترتيب من اليسار إلى اليمين.
*/
initMap باطل خاص () {
لـ (int i = 0; i < Pattern.length(); i++) {
this.map.put(pattern.charAt(i), i);
}
}
/**
* مطابقة متكررة للسلسلة العادية، إذا فشلت المباراة، تقدم موضعًا واحدًا
*/
القائمة العامة<Integer> NormalMatch() {
//فشلت المطابقة، استمر في النزول
إذا (!matchFromSpecialPos(currentPos)) {
currentPos += 1;
إذا ((text.length() -currentPos) <pattern.length()) {
إرجاع قائمة PosList المتطابقة؛
}
NormalMatch();
} آخر {
// تطابق بنجاح، سجل الموقع
matchedPosList.add(currentPos);
currentPos += 1;
NormalMatch();
}
إرجاع قائمة PosList المتطابقة؛
}
/**
* مطابقة الأحد، بافتراض أن موضع الحرف K في النص هو: الإزاحة الحالية + طول سلسلة النمط + 1
*/
القائمة العامة<Integer> SundayMatch() {
// إذا لم تنجح أي مباراة
إذا (!matchFromSpecialPos(currentPos)) {
// إذا لم يظهر حرف K في النص في سلسلة النمط، فقم بتخطي طول سلسلة النمط بالكامل.
إذا ((currentPos + Pattern. length () + 1) < text. length ()
&& !map.containsKey(text.charAt(currentPos + Pattern.length() + 1))) {
currentPos += Pattern. length();
}آخر {
// إذا ظهر حرف K في النص في سلسلة النمط، فقم بمحاذاة موضع حرف K في النص مع موضع حرف K الأخير في سلسلة النمط.
إذا ((currentPos + Pattern.length() + 1) > text. length()) {
currentPos += 1;
} آخر {
currentPos += Pattern. length() - (Integer)map.get(text.charAt(currentPos + Pattern.length()));
}
}
// عند اكتمال المباراة، قم بإرجاع الإزاحة الأولية لجميع التطابقات الناجحة.
إذا ((text.length() -currentPos) <pattern.length()) {
إرجاع قائمة PosList المتطابقة؛
}
SundayMatch();
}آخر {
// إذا نجحت المباراة، تقدم قليلاً ثم طابقها مرة أخرى
matchedPosList.add(currentPos);
currentPos += 1;
SundayMatch();
}
إرجاع قائمة PosList المتطابقة؛
}
/**
* تحقق مما إذا كانت السلسلة الفرعية التي تبدأ من الإزاحة المحددة للنص تتطابق مع النمط
*/
المباراة المنطقية العامةFromSpecialPos(int pos) {
إذا ((text.length()-pos) <pattern.length()) {
عودة كاذبة.
}
لـ (int i = 0; i < Pattern.length(); i++) {
إذا (text.charAt(pos + i) == Pattern.charAt(i)) {
إذا (i == (pattern.length()-1)) {
عودة صحيحة؛
}
يكمل؛
} آخر {
استراحة؛
}
}
عودة كاذبة.
}
public static void main(String[] args) {
SundySearch sundySearch = new SundySearch("مرحبًا أدولف adfsadfklf adf234masdfsdfdsfdsfdsffwerwrewrerwerwersdf2666sdflsdfk"، "adf");
بداية طويلة = System.nanoTime();
System.out.println("NormalMatch:" + sundySearch.normalMatch());
System.out.println("NormalMatch:" + (System.nanoTime() - begin));
تبدأ = System.nanoTime();
System.out.println("SundayMatch:" + sundySearch.sundayMatch());
System.out.println("SundayMatch:" + (System.nanoTime() - begin));
}
}