Bitap algoritmus

A bitap algoritmus (más néven shift-or, shift-and vagy Baeza-Yates–Gonnet-algoritmus) egy közelítő karakterlánc-illesztési algoritmus. Az algoritmus megmondja, hogy egy adott szöveg tartalmaz-e egy olyan részkarakterláncot, amely „megközelítőleg egyenlő” egy adott mintával ("pattern"), ahol a közelítő egyenlőséget Levenshtein-távolsággal definiálják – ha a részkarakterlánc és a minta egy adott k távolságon belül vannak egymástól, akkor az algoritmus egyenlőnek tekinti őket. Az algoritmus azzal kezdődik, hogy előre kiszámít egy bitmaszk-készletet, amely a minta minden eleméhez egy bitet tartalmaz. Ezután a munka nagy részét bitenkénti műveletekkel képes elvégezni, amelyek rendkívül gyorsak.

A bitap algoritmus talán leginkább az Udi Manber, Sun Wu és Burra Gopal által írt agrep Unix segédprogram egyik alapjául szolgáló algoritmusaként ismert. Manber és Wu eredeti tanulmánya az algoritmus kiterjesztéseit tartalmazza az általános reguláris kifejezések fuzzy (közelítő) illesztésének kezelésére.

Az algoritmus által megkövetelt adatszerkezetek miatt a konstansnál rövidebb mintákon teljesít a legjobban (jellemzően a szóban forgó gép szóhosszával megegyezően), és a bemeneteket részesíti előnyben egy rövid ábécével szemben. Miután azonban egy adott ábécére és m szóhosszra implementálták, a futási ideje teljesen kiszámítható – O(mn) műveletben fut, függetlenül a szöveg vagy a minta szerkezetétől.

A pontos karakterlánc-keresésre szolgáló bitap algoritmust Dömölki Bálint találta fel 1964-ben, majd R. K. Shyamasundar fejlesztette tovább 1977-ben, mielőtt Ricardo Baeza-Yates és Gaston Gonnet 1989-ben újraértelmezték (az első szerző PhD-dolgozatának egyik fejezete), és kiterjesztették a karakterosztályok, helyettesítő karakterek és eltérések kezelésére is. 1991-ben Manber és Wu kiterjesztette a beszúrások és törlések kezelésére is (teljes fuzzy karakterlánc-keresés). Ezt az algoritmust később Baeza-Yates és Navarro fejlesztette tovább 1996-ban.

Pontos keresés

A pontos karakterlánc-keresés bitap algoritmusa teljes általánosságban így néz ki pszeudokódban:

algorithm bitap_search is
    input: text as a string.
           pattern as a string.
    output: string
    m := length(pattern)

    if m = 0 then
        return text

    /* Initialize the bit array R. */
    R := new array[m+1] of bit, initially all 0
    R[0] := 1

    for i := 0; i < length(text); i += 1 do
        /* Update the bit array. */
        for k := m; k ≥ 1; k -= 1 do
            R[k] := R[k - 1] & (text[i] = pattern[k - 1])

        if R[m] then
            return (text + i - m) + 1

    return null

A bitap abban különbözik a többi jól ismert karakterlánc-kereső algoritmustól, hogy természetes módon leképezi az adatokat egyszerű bitenkénti műveletekre, ahogyan a fenti program következő módosításában is látható. Figyeljük meg, hogy ebben a megvalósításban, ellentétben az intuíciónkkal, minden nulla értékű bit egyezést, és minden 1 értékű bit nem egyezést jelöl. Ugyanez az algoritmus felírható a 0 és 1 intuitív szemantikájával, de ebben az esetben egy másik utasítást kell bevezetnünk a belső ciklusba az R |= 1 beállításához. Ebben a megvalósításban azt a tényt használjuk ki, hogy egy érték balra eltolása nullákat tol el a jobb oldalon, ami pontosan az a viselkedés, amire szükségünk van.

Azt is vegyük észre, hogy CHAR_MAX további bitmaszkokra van szükségünk ahhoz, hogy az általános implementációban a (text[i] == pattern[k-1]) feltételt bitenkénti műveletekké alakítsuk. Ezért a bitap algoritmus jobban teljesít, ha kisebb ábécéken keresztüli bemenetekre alkalmazzuk.

 #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 (m == 0) return text;
     if (m > 31) throw "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;
 }

Fuzzy keresés

Ahhoz, hogy fuzzy karakterlánc-keresést végezzünk a bitap algoritmussal, ki kell terjeszteni az R bittömböt egy második dimenzióba. Ahelyett, hogy egyetlen R tömbünk lenne, amely a szöveg hosszában változik, most k darab különböző R_1..k tömbünk van. Az R_i tömb a minta azon előtagjainak reprezentációját tartalmazza, amelyek az aktuális karakterlánc bármely utótagjához illeszkednek i vagy kevesebb hibával. Ebben az összefüggésben a "hiba" lehet beszúrás, törlés vagy helyettesítés; további információkért ezekről a műveletekről lásd a Levenshtein-távolságot.

Az alábbi implementáció fuzzy illesztést végez (az első egyezést adja vissza legfeljebb k hibával) a fuzzy bitap algoritmus használatával. Azonban csak a helyettesítésekre figyel, a beszúrásokra vagy törlésekre nem – más szóval, k Hamming-távolságot alkalmaz. Mint korábban, a 0 és az 1 szemantikája felcserélődik a hagyományos jelentésükhöz képest.

 #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;
 }

Fordítás

• Ez a szócikk részben vagy egészben a Bitap algorithm című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.