Найти самые длинные повторяющиеся строки?

У меня есть HTML/CSS/JavaScript с мучительно длинными именами классов, id, переменных и функций и другими комбинированными строками, которые используются снова и снова. Возможно, я мог бы переименовать или перестроить несколько из них и сократить текст пополам.Найти самые длинные повторяющиеся строки?

Итак, я ищу простой алгоритм, который сообщает о самых длинных повторяющихся строках в тексте. В идеале, это приведет к обратному сортировке по длине экземпляров, чтобы выделить строки, которые, если переименовать глобально, принесут наибольшую экономию.

Это похоже на то, что я мог бы сделать больно в 100 строках кода, для которых есть несколько изящных 10-строчных рекурсивных регулярных выражений. Это также звучит как домашняя проблема, но я уверяю вас, что это не так.

Я работаю на PHP, но мне будет приятно видеть что-то на любом языке.

ПРИМЕЧАНИЕ. Я не ищу нигде HTML/CSS/JavaScript как таковой. Мне нравится содержательный текст, поэтому я хочу сделать это вручную и взвешивать разборчивость против раздувания.

источник

2009-07-25 LibraryThingTim

Как о примере? – Gumbo

Метод грубой силы должен начинаться с позиции 0 и тестировать, если 0-1 - повторяющаяся строка. Если да, введите шаблон в массив, сколько раз оно повторяется. Затем попробуйте 0-2, 0-3 и т. Д. Как только шаблон не будет повторяться, переместите начальную позицию и сделайте 1-2 и т. Д. Пока вы делаете это или после того, как выбрасываете те, которые ничего не добавляют (например, если и hotdog и hot повторяются 10 раз, вы только держите хот-дог). Blech. – LibraryThingTim

Пример: Синий слон любил есть хот-доги на солнце. Пингвину нравилось лежать на солнце с синим слоном. синий слон x 2 на солнце x 2 enjoy x 2 – LibraryThingTim

Найдет все повторяющиеся строки:

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

Используйте это с preg_match_all и выбрать самый длинный.

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,}))

Это позволит ограничить количество символов, повторяющееся, по меньшей мере, три, а количество повторений до трех (первого + 2).

Редактировать: Изменено для разрешения символов между повторениями.
Редактировать: Изменен порядок сортировки, чтобы отразить наилучшее совпадение.

источник

2009-07-25 14:58:51

Лучше использовать '(? = ((. +?) \ 2 +))'. – Gumbo

Это не имеет значения. Он по-прежнему будет использовать всю длину. –

Но вы можете ограничить это с помощью '' {1, '. Floor (strlen ($ text)/2).'} ''. – Gumbo

Кажется, я немного поздно, но это также делает работу:

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/>"; 
}

выводе будет что-то вроде:

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

источник

2009-07-25 15:15:40 Nathan

Найти самые длинные повторяющиеся строки?

ответ

Смежные вопросы