3

「abcbcdcde」という文字列があるとしましょう

正規表現を使用して、この文字列で繰り返されるすべての部分文字列を識別したい (つまり、総当たり反復ループはありません)。

上記の文字列の場合、結果セットは次のようになります: {"b", "bc", "c", "cd", "d"}

私の正規表現は、私の経験のある人にとってよりもはるかに錆びていることを告白しなければなりません。後方参照を使用してみましたが、それは連続した重複にしか一致しません。連続しているかどうかにかかわらず、すべての重複に一致する必要があります。

つまり、2 回目以降に出現する任意の文字に一致させたいと考えています。部分文字列が 5 回出現する場合、2 ～ 5 回の出現をそれぞれキャプチャします。わかる？

これはこれまでの私の哀れな試みです：

preg_match_all( '/(.+)(.*)\1+/', $string, $matches );  // Way off!

私は先読みで遊んでみましたが、私はそれを解体しています。私はPHP（PCRE）でこれを行っていますが、問題は多かれ少なかれ言語に依存しません。私がこれに困惑していることに気付くのは少し恥ずかしいです。

4

4 に答える 4

9

あなたの問題は再帰です...あなたは何を知っていますか、再帰を忘れてください! =p PHP では実際にはうまく機能せず、それがなくてもアルゴリズムはかなり明確です。

  function find_repeating_sequences($s)
  {
    $res = array();
    while ($s) {
        $i = 1; $pat = $s[0];
        while (false !== strpos($s, $pat, $i)) {
            $res[$pat] = 1;
            // expand pattern and try again
            $pat .= $s[$i++];
        }
        // move the string forward
        $s = substr($s, 1);
    }
    return array_keys($res);
  }

興味をそそられたので、 Tim の回答も PHP で書きました。

function find_repeating_sequences_re($s)
{
    $res = array();
    preg_match_all('/(?=(.+).*\1)/', $s, $matches);
    foreach ($matches[1] as $match) {
        $length = strlen($match);
        if ($length > 1) {
            for ($i = 0; $i < $length; ++$i) {
                for ($j = $i; $j < $length; ++$j) {
                    $res[substr($match, $i, $j - $i + 1)] = 1;
                }
            }
        } else {
            $res[$match] = 1;
        }
    }
    return array_keys($res);
}

800 バイトのランダム データの小さなベンチマークで、彼らに戦いを挑ませました。

$data = base64_encode(openssl_random_pseudo_bytes(600));

各コードを 10 ラウンド実行し、実行時間を測定します。結果？

Pure PHP      - 0.014s (10 runs)
PCRE          - 40.86s <-- ouch!

24kバイト（または実際には1kを超えるもの）を見ると、さらに奇妙になります。

Pure PHP      - 4.565s (10 runs)
PCRE          - 0.232s <-- WAT?!

正規表現が 1,000 文字で壊れ、$matches配列が空になったことが判明しました。これらは私の.ini設定です：

pcre.backtrack_limit => 1000000 => 1000000
pcre.recursion_limit => 100000 => 100000

わずか 1,000 文字の後にバックトラックまたは再帰の制限がどのように達成されるかは、私には明らかではありません。しかし、それらの設定が何らかの形で「修正」されたとしても、結果は明らかであり、PCRE は答えではないようです。

これをCで書くといくらかスピードアップすると思いますが、どの程度かはわかりません。

アップデート

hakre's answer の助けを借りて、以下を最適化した後、パフォーマンスを最大 18% 向上させる改良版をまとめました。

  1. 外側のループ内の呼び出しを削除しsubstr()て、文字列ポインターを進めます。これは、以前の再帰的な化身からの残り物でした。

  2. 部分的な結果をポジティブ キャッシュとして使用してstrpos()、内部ループ内の呼び出しをスキップします。

そして、ここにそのすべての栄光があります (:

function find_repeating_sequences3($s)
{
    $res = array(); 
    $p   = 0;
    $len = strlen($s);

    while ($p != $len) {
        $pat = $s[$p]; $i = ++$p;
        while ($i != $len) {
            if (!isset($res[$pat])) {
                if (false === strpos($s, $pat, $i)) {
                    break;
                }
                $res[$pat] = 1;
            }
            // expand pattern and try again
            $pat .= $s[$i++];
        }
    }
    return array_keys($res);
}
于 2012-12-14T08:20:30.740 に答える
2

bc...bc正規表現は貪欲に (finding ) または遅延 (finding b...band ) のいずれかに一致しますが、両方には一致しないため、単一の正規表現で必要な結果を取得することはできませんc...c。（あなたの場合、それは見つかりますが、 2回繰り返されるc...cためだけです。）c

しかし、長さが 1 を超える部分文字列の繰り返しを見つけたら、論理的には、その部分文字列の小さい部分文字列もすべて繰り返す必要があるということになります。スペルアウトしたい場合は、個別に行う必要があります。

あなたの例を取り上げます（私はPHPを知らないのでPythonを使用しています）：

>>> results = set(m.group(1) for m in re.finditer(r"(?=(.+).*\1)", "abcbcdcde"))
>>> results
{'d', 'cd', 'bc', 'c'}

次に、次の関数を各結果に適用できます。

def substrings(s):
    return [s[start:stop] for start in range(len(s)-1) 
                          for stop in range(start+1, len(s)+1)]

例えば：

>>> substrings("123456")
['1', '12', '123', '1234', '12345', '123456', '2', '23', '234', '2345', '23456',
 '3', '34', '345', '3456', '4', '45', '456', '5', '56']
于 2012-12-14T08:19:20.810 に答える
1

私が得ることができる最も近いのは/(?=(.+).*\1)/

先読みの目的は、同じ文字が複数回一致できるようにすることです (たとえば、cand cd)。ただし、何らかの理由で取得していないようですb...

于 2012-12-14T07:57:43.743 に答える
1

興味深い質問です。私は基本的にJacks answerの関数を取り、テストの数を減らすことができないか試していました.

最初は文字列の半分だけを検索しようとしましたが、substr毎回経由で検索するパターンを作成するのはコストがかかりすぎることがわかりました。反復ごとに1文字を追加することにより、ジャックの回答でどのように行われるかは、見た目がはるかに優れています。そして、時間がなくなったので、それ以上調べることができませんでした。

ただし、そのような代替実装を探しているうちに、少なくとも、私が念頭に置いていたアルゴリズムの違いのいくつかが Jacks 関数にも適用できることがわかりました。

  1. 検索はすでにオフセットで行われているため、外側の反復ごとに文字列の先頭を切り取る必要はありません。
  2. 繰り返しを探す対象の残りの部分が繰り返し針よりも小さい場合は、針を探す必要はありません。
  3. すでに針を検索している場合は、再度検索する必要はありません。

    注：これは記憶取引です。繰り返しが多い場合は、同様のメモリを使用します。ただし、繰り返しの量が少ない場合、このバリアントは以前よりも多くのメモリを使用します。

関数：

function find_repeating_sequences($string) {
    $result = array();
    $start  = 0;
    $max    = strlen($string);
    while ($start < $max) {
        $pat = $string[$start];
        $i   = ++$start;
        while ($max - $i > 0) {
            $found = isset($result[$pat]) ? $result[$pat] : false !== strpos($string, $pat, $i);
            if (!$result[$pat] = $found) break;
            // expand pattern and try again
            $pat .= $string[$i++];
        }
    }
    return array_keys(array_filter($result));
}

したがって、これをジャックの回答への追加と見なしてください。

于 2012-12-22T12:00:57.437 に答える