4

文字列内の部分文字列の繰り返しの最大数を検索しようとしています。ここにいくつかの例を示します。

"AQMQMB" => QM (2x)
"AQMPQMB" => <nothing>
"AACABABCABCABCP" => A (2x), AB (2x), ABC (3x)

ご覧のとおり、私は連続した部分文字列のみを検索していますが、これは問題のようです。すべての圧縮アルゴリズム（少なくとも私が知っている）は連続性（ LZ * ）を気にしないか、単純すぎて連続するパターンを処理できないためです。単一のデータ項目（RLE）の代わりに。同じ問題があるため、接尾辞木関連のアルゴリズムを使用することも役に立たないと思います。

これを行うことができるいくつかのバイオインフォマティクスアルゴリズムがあると思いますが、誰かがそのようなアルゴリズムについてのアイデアを持っていますか？

編集 2番目の例では、連続するパターンの可能性が複数ある可能性があります（Eugen Rieckの通知に感謝します。以下のコメントを読んでください）が、私のユースケースでは、これらの可能性のいずれも実際に受け入れられます。

4

2 に答える 2

3

ここでは、接尾辞木に関連するアルゴリズムが役立ちます。

1つは、Dan Gusfieldによる文字列、ツリー、およびシーケンスのアルゴリズム（第9.6章）で説明されています。分割統治法と接尾辞木を組み合わせて使用​​し、時間計算量O（N log N + Z）を持ちます。ここで、Zは部分文字列の繰り返し回数です。

同じ本で、接尾辞木を使用して、この問題のより単純なO（N 2）アルゴリズムについて説明しています。

于 2012-11-28T11:30:21.873 に答える
3

これは私が同様の問題に使用したものです：

<?php

$input="AACABABCABCABCP";

//Prepare index array (A..Z) - adapt to your character range
$idx=array();
for ($i="A"; strlen($i)==1; $i++) $idx[$i]=array();

//Prepare hits array
$hits=array();

//Loop
$len=strlen($input);
for ($i=0;$i<$len;$i++) {

    //Current character
    $current=$input[$i];

    //Cycle past occurrences of character
    foreach ($idx[$current] as $offset) {

        //Check if substring from past occurrence to now matches oncoming
        $matchlen=$i-$offset;
        $match=substr($input,$offset,$matchlen);
        if ($match==substr($input,$i,$matchlen)) {
            //match found - store it
            if (isset($hits[$match])) $hits[$match][]=$i;
            else $hits[$match]=array($offset,$i);
        }
    }

    //Store current character in index
    $idx[$current][]=$i;
}

print_r($hits);

?>

Nは文字列の長さ、Mは文字範囲の幅で、O（N * N / M）時間だと思います。

それはあなたの例の正解だと私が思うものを出力します。

編集：

このアルゴには、実行中に有効なスコアを保持するという利点があるため、バッファリングを介して確認できる限り、ストリームに使用できます。これは効率的に報われます。

編集2：

繰り返し検出に最大長を許可すると、スペースと時間の使用量が減少します。if ($matchlen>MAX_MATCH_LEN) ...制限インデックスサイズや文字列比較長などを使用して、過去の発生を「早期に」排除します。

于 2012-11-28T11:44:27.230 に答える