الگوریتم بایتپ

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو


الگوریتم بایتپ الگوریتم بایتپ، الگوریتمی تقریبی برای تشخیص تطابق دو رشته است. الگوریتم پیش رو، مشخص می کند که در متن ورودی، زیر رشته ای وجود دارد که "تقریباً" با الگوی مورد نظر داده شده، برابر باشد. در این تعریف، با مفهوم فاصله ی لونشتین (levenshtein) -- در صورتی که زیررشته و الگوی مد نظر، k فاصله از یکدیگر داشته باشند، الگوریتم آن ها را برابر در نظر می گیرد -- برابری تقریبی تعریف می شود. الگوریتم بایتپ، با پیش پردازش تعدادی ماسک بیتی، که هر کدام دارای یک بیت به ازای هر عضو الگو است، شروع می گردد. پس از آن الگوریتم اکثر عملیات خود را با عملگرهای دودویی انجام می دهد، که بسیار سریع می باشند.

با توجه به ساختمان داده ی مورد نیاز الگوریتم، این الگوریتم زمانی که طول الگوی ما، از عدد ثابتی کمتر باشد،(معمولاً زمانی که کوچکتر از واحد کلمه ی کامپیوتر مورد استفاده باشد) بهترین عملکرد خود را دارد، علاوه بر آن، زمانی که تعداد حروف به کار رفته، کم باشند نیز عملکرد الگوریتم مناسب است. پیچیدگی محاسباتی الگوریتم برای الفبای با تعداد حروف ثابت و کلمه با طول m و متنی با طول n، مستقل از ساختار متن و الگو، از \textstyle O(m \times n) می باشد.

بالینت دملکی (Bálint Dömölki)، الگوریتم بایتپ در حالت جستجوی دقیق را، در سال ۱۹۶۴ اختراع نمود و شیامسوندر (R. K. Shyamasundar) آن را در سال ۱۹۷۷ تعمیم داد.

جستجوی دقیق[ویرایش]

الگوریتم بایتپ، برای جستجوی دقیق الگو در متن، در حالت کلی، در زیر با زبان C پیاده سازی شده است.

 #include <stdlib.h>
 #include <string.h>
 
 typedef char BIT; /* needs only to hold the values 0 and 1 */
 
 const char *bitap_search(const char *text, const char *pattern)
 {
     const char *result = NULL;
     int m = strlen(pattern);
     BIT *R;
     int i, k;
 
     if (pattern[0] == '\0') return text;
 
     /* Initialize the bit array R */
     R = malloc((m+1) * sizeof *R);
     R[0] = 1;
     for (k=1; k <= m; ++k)
       R[k] = 0;
 
     for (i=0; text[i] != '\0'; ++i) {
         /* Update the bit array. */
         for (k=m; k>= 1; --k)
           R[k] = R[k-1] && (text[i] == pattern[k-1]);
 
         if (R[m]) {
             result = (text+i - m) + 1;
             break;
         }
     }
 
     free(R);
     return result;
 }

الگوریتم بایتپ، همان طور که در برنامه ی بالا می بینید، به خاطر تطابق طبیعی خود با عملیات دودویی، از دیگر الگوریتم های معروف جستجوی رشته، متمایز می باشد. توجه کنید که در مورد پیاده سازی بالا، بر خلاف تصور، هر بیت با مقدار ۰ نشان دهنده ی یک تطابق، و هر بیت با مقدار ۱ نشان دهنده ی یک عدم تطابق می باشد. می توان الگوریتم مشابهی با تصور شهودی از ۰ و ۱ نوشت، اما در این حالت ما باید دستور R |= ۱ را به حلقه ی داخلی اضافه کنیم. در این پیاده سازی، ما از این واقعیت که شیفت به چپ یک عدد، در سمت راست آن عدد، صفر اضافه می نماید به صورت بهینه استفاده کرده ایم.

توجه نمایید در پیاده سازی کلی برای تبدیل شرط (text[i] == pattern[k-۱]) به یک عملگر دودویی نیاز به یک ماسک دودویی CHAR_MAX داریم.

 #include <string.h>
 #include <limits.h>
 
 const char *bitap_bitwise_search(const char *text, const char *pattern)
 {
     int m = strlen(pattern);
     unsigned long R;
     unsigned long pattern_mask[CHAR_MAX+1];
     int i;
 
     if (pattern[0] == '\0') return text;
     if (m> 31) return "The pattern is too long!";
 
     /* Initialize the bit array R */
     R = ~1;
 
     /* Initialize the pattern bitmasks */
     for (i=0; i <= CHAR_MAX; ++i)
       pattern_mask[i] = ~0;
     for (i=0; i <m; ++i)
       pattern_mask[pattern[i]] &= ~(1UL <<i);
 
     for (i=0; text[i] != '\0'; ++i) {
         /* Update the bit array */
         R |= pattern_mask[text[i]];
         R <<= 1;
 
         if (0 == (R & (1UL <<m)))
           return (text + i - m) + 1;
     }
 
     return NULL;
 }

جستجوی فازی[ویرایش]

برای تعمیم الگوریتم بایتپ، به جستجوگری فازی در متن، آرایه ی بیتی R باید به یک آرایه ی دوبعدی تبدیل شود. در این صورت، به جای آرایه ی تک بعدی R که متناسب با طول متن متغیر بود، k آرایه ی متفاوت با نام های R۱..k در نظر گرفته شود. آرایه ی Ri نمایشی از پیشوند های الگوی مدنظر که به یک پسوند دلخواه متن موجود با حداکثر i خطا را، در خود نگاه می دارد. در این کد، یک خطا می تواند یک درج، یک پاک کردن یا یک جایگزین کردن کاراکتری دلخواه باشد. برای اطلاعات بیش تر به فاصله ی لونشتین (levenshtein) مراجعه نمایید.

پیاده سازی زیر با استفاده از الگوریتم بایتپ، با توجه به تطابق فازی، اولین زیر رشته ای که حداکثر k خطا را دربردارد، بر خواهد گرداند. هر چند در کد، تنها به جایگزینی توجه شده است و حذف و درج در نظر گرفته نشده است.(در واقع فاصله ی همینگ در نظر گرفته شده است)

 #include <stdlib.h>
 #include <string.h>
 #include <limits.h>
 
 const char *bitap_fuzzy_bitwise_search(const char *text, const char *pattern, int k)
 {
     const char *result = NULL;
     int m = strlen(pattern);
     unsigned long *R;
     unsigned long pattern_mask[CHAR_MAX+1];
     int i, d;
 
     if (pattern[0] == '\0') return text;
     if (m> 31) return "The pattern is too long!";
 
     /* Initialize the bit array R */
     R = malloc((k+1) * sizeof *R);
     for (i=0; i <= k; ++i)
         R[i] = ~1;
 
     /* Initialize the pattern bitmasks */
     for (i=0; i <= CHAR_MAX; ++i)
         pattern_mask[i] = ~0;
     for (i=0; i <m; ++i)
         pattern_mask[pattern[i]] &= ~(1UL <<i);
 
     for (i=0; text[i] != '\0'; ++i) {
         /* Update the bit arrays */
         unsigned long old_Rd1 = R[0];
 
         R[0] |= pattern_mask[text[i]];
         R[0] <<= 1;
 
         for (d=1; d <= k; ++d) {
             unsigned long tmp = R[d];
             /* Substitution is all we care about */
             R[d] = (old_Rd1 & (R[d] | pattern_mask[text[i]])) <<1;
             old_Rd1 = tmp;
         }
 
         if (0 == (R[k] & (1UL <<m))) {
             result = (text+i - m) + 1;
             break;
         }
     }
 
     free(R);
     return result;
 }

الگوریتم های مشابه[ویرایش]

برخی دیگر از الگوریتم هایی که برای جستجوی یک الگو در متن استفاده می شوند عبارتند از KMP، RKS، BMS.

منابع[ویرایش]

Wiki Bitap Algorithm*

Wiki Bitwise Opeation*

Wiki Levenshtein Distance*

Wiki Fuzzy Maching*

پیوند به بیرون[ویرایش]

  1. ^  Bálint Dömölki, An algorithm for syntactical analysis, Computational Linguistics 3, Hungarian Academy of Science pp. 29–46, 1964.
  2. ^  Bálint Dömölki, A universal compiler system based on production rules, BIT Numerical Mathematics, 8(4), pp 262–275, 1968. doi:10.1007/BF01933436
  3. ^  R. K. Shyamasundar, Precedence parsing using Dömölki's algorithm, International Journal of Computer Mathematics, 6(2)pp 105–114, 1977
  4. ^  Udi Manber, Sun Wu. "Fast text searching with errors." Technical Report TR-91-11. Department of Computer Science, دانشگاه آریزونا, Tucson, June 1991. (gzipped PostScript)
  5. ^  Udi Manber, Sun Wu. "Fast text search allowing errors." Communications of the ACM, 35(10): pp. 83–91, October 1992, doi:10.1145/135239.135244.
  6. ^  Ricardo A. Baeza-Yates, Gastón H. Gonnet. "A New Approach to Text Searching." Communications of the ACM, 35(10): pp. 74–82, October 1992.
  7. ^  R. Baeza-Yates and G. Navarro. A faster algorithm for approximate string matching. In Dan Hirchsberg and Gene Myers, editors, Combinatorial Pattern Matching (CPM'96), LNCS 1075, pages 1–23, Irvine, CA, June 1996.
  8. ^  G. Myers. "A fast bit-vector algorithm for approximate string matching based on dynamic programming." Journal of the ACM ۴۶ (۳)، May ۱۹۹۹، ۳۹۵–۴۱۵.
  9. Libbitap، a free implementation that shows how the algorithm can easily be extended for most regular expressions. Unlike the code above، it places no limit on the pattern length.
  10. Baeza-Yates. Modern Information Retrieval. ISBN ۰-۲۰۱-۳۹۸۲۹-X.