6

文字列 s があり、s で最も頻繁に出現する長さ X の部分文字列を検索したいと考えています。部分文字列の重複は許可されます。

たとえば、s="aoaoa" で X=3 の場合、アルゴリズムは "aoa" (s に 2 回現れる) を見つける必要があります。

O(n)時間でこれを行うアルゴリズムは存在しますか?

4

8 に答える 8

8

これは、O（n）時間のローリングハッシュを使用して実行できます（ハッシュ分布が良好であると想定）。単純なローリングハッシュは、文字列内の文字のxorになります。これは、2つのxorを使用して、前の部分文字列ハッシュから段階的に計算できます。（xorよりも優れたローリングハッシュについては、Wikipediaのエントリを参照してください。）O（n）時間のローリングハッシュを使用して、n-x+1サブストリングのハッシュを計算します。衝突がなかった場合、答えは明らかです。衝突が発生した場合は、さらに作業を行う必要があります。それがすべてO（n）時間で解決できるかどうかを理解しようとすると、私の脳は痛いです。

アップデート：

これがランダム化されたO（n）アルゴリズムです。ハッシュテーブルをスキャンすることで、O（n）時間の最上位のハッシュを見つけることができます（単純に保ち、同点がないと仮定します）。そのハッシュを含む1つのX長文字列を検索します（ハッシュテーブルにレコードを保持するか、ローリングハッシュをやり直します）。次に、O（n）文字列検索アルゴリズムを使用して、s内のその文字列のすべての出現箇所を検索します。ハッシュテーブルに記録したのと同じ数のオカレンスが見つかった場合は、これで完了です。

そうでない場合は、ハッシュの衝突があることを意味します。新しいランダムハッシュ関数を選択して、再試行してください。ハッシュ関数にlog（n）+1ビットがあり、ペアごとに独立している場合[ Prob(h(s) == h(t)) < 1/2^{n+1} if s != t]、sで最も頻繁なx長の部分文字列がsの<=nの他の長さのx部分文字列と衝突する確率は最大で1です。 /2。したがって、衝突が発生した場合は、新しいランダムハッシュ関数を選択して再試行すると、成功するまでに一定回数の試行のみが必要になります。

これで、ランダム化されたペアごとに独立したローリングハッシュアルゴリズムのみが必要になります。

Update2：

実際には、すべての（nは2つを選択）衝突を回避するために2log（n）ビットのハッシュが必要です。これは、衝突があると正しい答えが隠される可能性があるためです。まだ実行可能であり、一般的な多項式除算によるハッシュでうまくいくようです。

于 2009-10-20T21:57:01.197 に答える
4

X が固定されていて定数と見なされない限り、厳密に O(n) 時間でこれを行う簡単な方法はわかりません。X がアルゴリズムのパラメータである場合、これを行う最も簡単な方法は実際には O(n*X) になります。これは、長さ X の部分文字列に対して比較操作、文字列のコピー、ハッシュなどを行う必要があるためです。すべての反復。

(私は、s が数ギガバイトの文字列であり、X が 100 万を超える数であり、文字列比較を行う簡単な方法や、長さ X の部分文字列をハッシュする単純な方法が見当たらないことを想像しています。 (1)、X のサイズに依存しない)

すべてをそのままにして、部分文字列全体の再ハッシュを回避することで、スキャン中の文字列のコピーを回避できる可能性があります。おそらく、一度に 1 バイトずつ追加し、最も古いバイトを削除できるインクリメンタル ハッシュ アルゴリズムを使用することで可能です。 -- しかし、コストのかかる後処理ステップでフィルター処理する必要がある膨大な数の衝突が発生しないようなアルゴリズムを私は知りません。

アップデート

Keith Randall 氏は、この種のハッシュはローリング ハッシュとして知られていると指摘しています。ただし、各一致の開始文字列位置をハッシュ テーブルに格納し、文字列をスキャンした後にすべての一致が true であることを確認する必要があることは依然として残っています。各ハッシュキーで見つかった一致の数に基づいて、nX エントリを含む可能性のあるハッシュテーブルをソートし、各結果を検証する必要があります-おそらく O(n) では実行できません。

于 2009-10-20T20:55:20.547 に答える
1

O(n*m) である必要があります。ここで、m はリスト内の文字列の平均の長さです。m の値が非常に小さい場合、アルゴリズムは O(n) に近づきます。

  • 文字列の長さごとにカウントのハッシュテーブルを作成する
  • 文字列のコレクションを反復処理し、それに応じてハッシュテーブルを更新し、現在最も普及している数値をハッシュテーブルとは別の整数変数として格納します
  • 終わり。
于 2009-10-20T20:20:55.563 に答える
0

部分文字列のツリーを構築できます。アイデアは、電話帳のように部分文字列を整理することです。次に、部分文字列を調べて、そのカウントを 1 増やします。

上記の例では、ツリーには「a」と「o」の文字で始まるセクション (ノード) があります。「a」が 3 回、「o」が 2 回表示されます。したがって、これらのノードの数はそれぞれ 3 と 2 になります。

次に、「a」ノードの下に、サブストリング「ao」に対応する「o」のサブノードが表示されます。これは 2 回表示されます。'o' ノードの下にも 'a' が 2 回表示されます。

弦の端に到達するまで、この方法を続けます。

「abac」のツリーの表現は次のようになります (同じレベルのノードはカンマで区切られ、サブノードは括弧で囲まれ、カウントはコロンの後に表示されます)。

a:2(b:1(a:1(c:1())),c:1()),b:1(a:1(c:1())),c:1()

ツリーを引き抜くと、よりはっきりとわかります！たとえば、文字列 'aba' が 1 回出現する、または文字列 'a' が 2 回出現する、などです。文字列)。

どの部分文字列が最も繰り返されているかを調べるには、ツリーの深さ優先検索を行い、葉ノードに到達するたびにカウントを記録し、最も高いものを追跡します。

実行時間はおそらく O(log(n)) のようなものですが、確かに O(n^2) よりも優れています。

于 2009-10-21T10:58:54.027 に答える
0

これは私がCで行ったバージョンです。それが役立つことを願っています.

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

int main(void)
{
    char *string = NULL, *maxstring = NULL, *tmpstr = NULL, *tmpstr2 = NULL;
    unsigned int n = 0, i = 0, j = 0, matchcount = 0, maxcount = 0;

    string = "aoaoa";
    n = 3;

    for (i = 0; i <= (strlen(string) - n); i++) {
        tmpstr = (char *)malloc(n + 1);
        strncpy(tmpstr, string + i, n);
        *(tmpstr + (n + 1)) = '\0';
        for (j = 0; j <= (strlen(string) - n); j++) {
            tmpstr2 = (char *)malloc(n + 1);
            strncpy(tmpstr2, string + j, n);
            *(tmpstr2 + (n + 1)) = '\0';
            if (!strcmp(tmpstr, tmpstr2))
                matchcount++;
        }
        if (matchcount > maxcount) {
            maxstring = tmpstr;
            maxcount = matchcount;
        }
        matchcount = 0;
    }

    printf("max string: \"%s\", count: %d\n", maxstring, maxcount);

    free(tmpstr);
    free(tmpstr2);

    return 0;
}
于 2009-10-20T22:42:55.507 に答える
0

Python での単純なソリューション

from collections import defaultdict
from operator    import itemgetter

def naive(s, X):
    freq = defaultdict(int)
    for i in range(len(s) - X + 1):
        freq[s[i:i+X]] += 1
    return max(freq.iteritems(), key=itemgetter(1))

print naive("aoaoa", 3)
# -> ('aoa', 2)

平易な英語で

  1. マッピングの作成: 長さの部分文字列-> 文字列X内での出現回数s

    for i in range(len(s) - X + 1):
    freq[s[i:i+X]] += 1

  2. マッピングで最大の 2 番目の項目 (頻度) を持つペアを見つけます

    max(freq.iteritems(), key=itemgetter(1))
于 2009-10-20T20:35:38.060 に答える
-1

LZWアルゴリズムはこれを行います

これは、Lempel-Ziv-Welch（GIF画像形式で使用されるLZW）圧縮アルゴリズムが行うこととまったく同じです。流行している繰り返しバイトを見つけて、それらを短いものに変更します。

ウィキペディアのLZW

于 2009-10-20T22:13:11.093 に答える
-2

O(n) でこれを行う方法はありません。

これについて私が間違っていることを証明できる場合は、遠慮なく反対票を投じてください。しかし、私には何もありません。

于 2009-10-20T21:31:44.103 に答える