الفرق بين المراجعتين ل"Algorithms/String Searching Algorithms"
سطر 2: | سطر 2: | ||
تعدّ خوارزميات البحث عن النصوص (وتسمّى كذلك بخوارزميات البحث عن الأنماط Pattern Searching) جزءًا من خوارزميات النصوص String Algorithms، وتساعد هذه الخوارزميات في البحث عن سلسلة نصية معيّنة في سلسلة نصية أخرى. | تعدّ خوارزميات البحث عن النصوص (وتسمّى كذلك بخوارزميات البحث عن الأنماط Pattern Searching) جزءًا من خوارزميات النصوص String Algorithms، وتساعد هذه الخوارزميات في البحث عن سلسلة نصية معيّنة في سلسلة نصية أخرى. | ||
− | == الخوارزمية البسيطة == | + | == [[Algorithms/naive string searching|الخوارزمية البسيطة]] == |
تنتقل الخوارزمية عبر جميع الحروف في السلسلة النصية واحدًا تلو الآخر بحثًا عن التسلسل الذي يطابق النمط المعطى. | تنتقل الخوارزمية عبر جميع الحروف في السلسلة النصية واحدًا تلو الآخر بحثًا عن التسلسل الذي يطابق النمط المعطى. | ||
− | == خوارزمية KMP == | + | == [[Algorithms/KMP|خوارزمية KMP]] == |
تعالج الخوارزمية النمط المراد البحث عنه لتجنّب تكرار البحث عن أنماط جرى البحث عنها في الخطوات السابقة. | تعالج الخوارزمية النمط المراد البحث عنه لتجنّب تكرار البحث عن أنماط جرى البحث عنها في الخطوات السابقة. | ||
− | == خوارزمية رابين-كارب == | + | == [[Algorithms/Rabin Karp|خوارزمية رابين-كارب]] == |
تحرّك خوارزمية رابين-كارب Rabin-Karp النمط الذي تبحث عنه عبر السلسلة النصية موقعًا تلو الآخر وتطابق قيمة التقطيع Hash value للنمط المعطى مع قيمة التقطيع لجزء السلسلة الذي تجري معه المقارنة | تحرّك خوارزمية رابين-كارب Rabin-Karp النمط الذي تبحث عنه عبر السلسلة النصية موقعًا تلو الآخر وتطابق قيمة التقطيع Hash value للنمط المعطى مع قيمة التقطيع لجزء السلسلة الذي تجري معه المقارنة | ||
− | == خوارزمية بوير-مور == | + | == [[Algorithms/Boyer Moore|خوارزمية بوير-مور]] == |
تعتمد خوارزمية بوير-مور Boyer-Moore على الأسلوبين: استكشاف الحروف السيئة، واستكشاف اللاحقة الجيدة. | تعتمد خوارزمية بوير-مور Boyer-Moore على الأسلوبين: استكشاف الحروف السيئة، واستكشاف اللاحقة الجيدة. | ||
− | == خوارزمية آهو-كوراسك == | + | == [[Algorithms/Aho Corasick|خوارزمية آهو-كوراسك]] == |
− | == خوارزمية Z == | + | == [[Algorithms/Z|خوارزمية Z]] == |
− | |||
− | |||
+ | تستعين الخوارزمية بمصفوفة <code>Z</code> في البحث عن النمط المعطى، ويخزّن العنصر <code>Z[i]</code> طول أطول سلسلة نصية فرعية تبدأ من الموقع <code>str[i]</code> والتي تكون في الوقت نفسه سابقة للسلسة النصية <code>str[0..n-1]</code>. | ||
[[تصنيف: الخوارزميات]] | [[تصنيف: الخوارزميات]] |
مراجعة 21:42، 30 سبتمبر 2019
تعدّ خوارزميات البحث عن النصوص (وتسمّى كذلك بخوارزميات البحث عن الأنماط Pattern Searching) جزءًا من خوارزميات النصوص String Algorithms، وتساعد هذه الخوارزميات في البحث عن سلسلة نصية معيّنة في سلسلة نصية أخرى.
الخوارزمية البسيطة
تنتقل الخوارزمية عبر جميع الحروف في السلسلة النصية واحدًا تلو الآخر بحثًا عن التسلسل الذي يطابق النمط المعطى.
خوارزمية KMP
تعالج الخوارزمية النمط المراد البحث عنه لتجنّب تكرار البحث عن أنماط جرى البحث عنها في الخطوات السابقة.
خوارزمية رابين-كارب
تحرّك خوارزمية رابين-كارب Rabin-Karp النمط الذي تبحث عنه عبر السلسلة النصية موقعًا تلو الآخر وتطابق قيمة التقطيع Hash value للنمط المعطى مع قيمة التقطيع لجزء السلسلة الذي تجري معه المقارنة
خوارزمية بوير-مور
تعتمد خوارزمية بوير-مور Boyer-Moore على الأسلوبين: استكشاف الحروف السيئة، واستكشاف اللاحقة الجيدة.
خوارزمية آهو-كوراسك
خوارزمية Z
تستعين الخوارزمية بمصفوفة Z
في البحث عن النمط المعطى، ويخزّن العنصر Z[i]
طول أطول سلسلة نصية فرعية تبدأ من الموقع str[i]
والتي تكون في الوقت نفسه سابقة للسلسة النصية str[0..n-1]
.