最も長い繰り返し文字列を検索しますか？

私は辛抱強く長いクラス、ID、変数、関数名、および繰り返し使用される他の結合文字列を持つHTML/CSS/JavaScriptをいくつか持っています。私はたぶん名前を変更したり、いくつかを再構成したり、テキストを半分にすることができました。最も長い繰り返し文字列を検索しますか？

だから私は、テキスト中の最も長い繰り返し文字列を報告する単純なアルゴリズムを探しています。理想的には、インスタンスの長さをインスタンスごとに逆順に並べ替えることで、グローバルに名前を変更すると最も節約できる文字列を強調表示します。

これは、私が100行のコードで苦労してできることのように感じます。そのためには、エレガントな10行の再帰正規表現があります。宿題のように聞こえるかもしれませんが、そうではないと私は確信しています。

私はPHPで働いていますが、どの言語で何かを見て楽しんでいます。

注：私はHTML/CSS/JavaScriptの縮小そのものを探しているわけではありません。私は意味のあるテキストが好きなので、私は手でそれをやりたいし、肥大化に対して可読性を測る。そのpreg_match_allで

(?=((.+)(?:.*?\2)+))

を使用し、最長いずれかを選択します。

出典

2009-07-25 LibraryThingTim

：

preg_match_all('/(id|class)+="([a-zA-Z0-9-_ ]+)"/', $html, $matches); $result = explode(" ", implode(" ", $matches[2])); $parsed = array(); foreach($result as $string) { if(isset($parsed[$string])) { $parsed[$string]++; } else { $parsed[$string] = 1; } } arsort($parsed); foreach($parsed as $k => $v) { echo $k . " -> Found " . $v . " times<br/>"; }

が出力に含まのようなものでしょうか？ – Gumbo

ブルートフォースの方法は、位置0で開始し、0-1が繰り返し文字列であるかどうかをテストすることです。はいの場合は、何回繰り返されたかで配列にパターンを入力します。次に、0-2、0-3などを試してください。パターンが繰り返されていない場合は、開始位置を移動し、1-2を実行します。これを行う間、または何も追加しないものを捨てた後（たとえば、ifホットドッグとホットの両方が10回繰り返されると、ホットドッグだけが維持されます）。ブリーチ。 – LibraryThingTim

例：青い象は太陽の下でホットドッグを食べました。ペンギンは青い象と一緒に太陽の下で横たわって楽しんだ。青い象x 2 太陽で2 お楽しみくださいx 2 – LibraryThingTim

これは、すべての繰り返し文字列を検索します。

function len_cmp($match1,$match2) { 
    return $match2[0] - $match1[0]; 
} 

preg_match_all('/(?=((.+)(?:.*?\2)+))/s', $text, $matches, PREG_SET_ORDER); 

foreach ($matches as $match) { 
    $match[0] = substr_count($match[1], $match[2]) * strlen($match[2]); 
} 

usort($matches, "len_cmp"); 

foreach ($matches as $match) { 
    echo "($matches[2]) $matches[1]\n"; 
}

多くの文字列が繰り返される可能性があるため、この方法はかなり遅くなる可能性があります。パターンの最小の長さと最小の繰り返し数を指定することによって、いくらか減らすことができます。

(?=((.{3,})(?:.*?\2){2,}))

これは、繰り返し回数を3回以上、繰り返し回数を3回（first + 2）に制限します。

編集：繰り返しの間に文字を許可するように変更されました。
編集：ベストマッチを反映するように並べ替え順序を変更しました。

出典

2009-07-25 14:58:51

'（？=（（+ +））\ 2 +））'をうまく使います。 – Gumbo

それは問題ではありません。それはまだすべての長さを試してみます。 –

しかし '' {1、 '。floor（strlen（$ text）/ 2）。'} ''で制限することができます。 – Gumbo

私は少し遅れてるようだが、それはまた仕事ん：

例についてどう

some_id -> Found 2 times 
some_class -> Found 2 times

出典

2009-07-25 15:15:40 Nathan

最も長い繰り返し文字列を検索しますか？

答えて

関連する問題