0

ボイヤームーア文字c（++）Wikipediaの実装を適応させて、文字列内のパターンのすべての一致を取得しようとしています。そのまま、ウィキペディアの実装は最初の一致を返します。メインコードは次のようになります。

char* boyer_moore (uint8_t *string, uint32_t stringlen, uint8_t *pat, uint32_t patlen) {
    int i;
    int delta1[ALPHABET_LEN];
    int *delta2 = malloc(patlen * sizeof(int));
    make_delta1(delta1, pat, patlen);
    make_delta2(delta2, pat, patlen);

    i = patlen-1;
    while (i < stringlen) {
        int j = patlen-1;
        while (j >= 0 && (string[i] == pat[j])) {
            --i;
            --j;
        }
        if (j < 0) {
            free(delta2);
            return (string + i+1);
        }

        i += max(delta1[string[i]], delta2[j]);
    }
    free(delta2);
    return NULL;
}

配列/ベクトルにインデックスを追加し、外側のループを続行させた後、ブロックを変更しようとしましたif (j < 0)が、機能していないようです。変更されたコードをテストしても、一致するものは1つだけです。おそらく、この実装はすべての一致を返すように設計されておらず、そうするためにいくつかの迅速な変更が必要ですか？アルゴリズム自体がよくわからないので、どうやってこれを機能させるのかわかりません。誰かが私を正しい方向に向けることができれば、私は感謝するでしょう。

注：関数make_delta1およびmake_delta2は、ソースで以前に定義されており（Wikipediaページを確認してください）、max（）関数呼び出しは、実際にはソースでも以前に定義されたマクロです。

4

1 に答える 1

4

Boyer-Mooreのアルゴリズムは、たとえば、より長い文字列内で「HELLO WORLD」を検索するときに、特定の位置で見つかった文字が、一致するものが見つかった場合にその位置の周りで見つけることができるものを制限するという事実を利用しています。海軍戦闘ゲームの例：国境から4つのセルで外洋を見つけた場合、そこに5セルのキャリアが隠れている場合に備えて、残りの4つのセルをテストする必要はありません。ありえない。

たとえば、11番目の位置に「D」が見つかった場合、それはHELLOWORLDの最後の文字である可能性があります。ただし、「Q」、「Q」がHELLO WORLD内のどこにも存在しない場合、これは、検索対象の文字列が最初の11文字のど​​こにも存在しないことを意味し、そこでの検索を完全に回避できます。一方、「L」は、位置11-3（HELLO WORLDの3番目の文字はL）、11-4、または11-10から始まるHELLOWORLDが存在することを意味する場合があります。

検索するときは、2つのデルタ配列を使用してこれらの可能性を追跡します。

したがって、パターンを見つけたら、実行する必要があります。

if (j < 0)
{
    // Found a pattern from position i+1 to i+1+patlen
    // Add vector or whatever is needed; check we don't overflow it.
    if (index_size+1 >= index_counter)
    {
        index[index_counter] = 0;
        return index_size;
    }
    index[index_counter++] = i+1;

    // Reinitialize j to restart search
    j = patlen-1;

    // Reinitialize i to start at i+1+patlen
    i += patlen +1; // (not completely sure of that +1)

    // Do not free delta2
    // free(delta2);

    // Continue loop without altering i again
    continue;
}
i += max(delta1[string[i]], delta2[j]);
}
free(delta2);
index[index_counter] = 0;
return index_counter;

関数にaのようなものを渡すと、これはインデックスのゼロで終了するリストを返すはずですsize_t *indexes。

この関数は、0（見つからない）、index_size（一致が多すぎる）、または1とindex_size-1の間の一致数を返します。

これにより、たとえば、すでに見つかった（index_size-1）サブ文字列の検索全体を繰り返すことなく、一致を追加できます。配列であるnum_indexesnew_numを増やしてから、オフセットの新しい配列、新しいサイズのnew_num、およびインデックスに1を加えた一致のオフセットから始まるhaystack文字列を関数に渡します（以前のリビジョンで書いたように、プラス針の長さ;コメントを参照）。reallocindexesold_index_size-1old_index_size-1

このアプローチでは、重複する一致も報告されます。たとえば、バナナでanaを検索すると、b * ana *naとban* ana *が見つかります。

アップデート

上記をテストしましたが、機能しているようです。gccが不平を言うのを防ぐために、これら2つのインクルードを追加してウィキペディアのコードを変更しました

#include <stdio.h>
#include <string.h>

次に、if (j < 0)見つけたものを単に出力するように変更しました

    if (j < 0) {
            printf("Found %s at offset %d: %s\n", pat, i+1, string+i+1);
            //free(delta2);
            // return (string + i+1);
            i += patlen + 1;
            j = patlen - 1;
            continue;
    }

そして最後に私はこれでテストしました

int main(void)
{
    char *s = "This is a string in which I am going to look for a string I will string along";
    char *p = "string";
    boyer_moore(s, strlen(s), p, strlen(p));
    return 0;
}

予想通り、次のようになりました。

Found string at offset 10: string in which I am going to look for a string I will string along
Found string at offset 51: string I will string along
Found string at offset 65: string along

文字列に2つの重複するシーケンスが含まれている場合、両方が見つかります。

char *s = "This is an andean andeandean andean trouble";
char *p = "andean";

Found andean at offset 11: andean andeandean andean trouble
Found andean at offset 18: andeandean andean trouble
Found andean at offset 22: andean andean trouble
Found andean at offset 29: andean trouble

重複する一致を回避するための最も簡単な方法は、重複を保存しないことです。これは関数で実行できますが、最初のデルタベクトルを再初期化し、文字列ポインターを更新することを意味します。また、保存されたインデックスが単調にならないように、2番目のiインデックスを保存する必要がありi2ます。それは価値がありません。より良い：

    if (j < 0) {
        // We have found a patlen match at i+1
        // Is it an overlap?
        if (index && (indexes[index] + patlen < i+1))
        {
            // Yes, it is. So we don't store it.


            // We could store the last of several overlaps
            // It's not exactly trivial, though:
            // searching 'anana' in 'Bananananana'
            // finds FOUR matches, and the fourth is NOT overlapped
            // with the first. So in case of overlap, if we want to keep
            // the LAST of the bunch, we must save info somewhere else,
            // say last_conflicting_overlap, and check twice.
            // Then again, the third match (which is the last to overlap
            // with the first) would overlap with the fourth.

            // So the "return as many non overlapping matches as possible"
            // is actually accomplished by doing NOTHING in this branch of the IF.
        }
        else
        {
            // Not an overlap, so store it.
            indexes[++index] = i+1;
            if (index == max_indexes) // Too many matches already found?
                break; // Stop searching and return found so far
        }
        // Adapt i and j to keep searching
        i += patlen + 1;
        j = patlen - 1;
        continue;
    }
于 2012-10-03T06:51:03.457 に答える