Заменить повторяющиеся строки в строке

Question

Я пытаюсь найти (и заменить) повторяющуюся строку в строке.

Моя строка может выглядеть следующим образом:

Lorem ipsum dolor sit amet sitамет сит амет сит нострумная тренировка амит сит ullamco labourisisis nisi ut aliquip ex ea Коммодаквакот.

Это должно стать:

Loremipsum dolor sit amet sit нострумное упражнение amit sit ullamco labourisisis aliquip ex ea Коммодо.

Обратите внимание, как amit sit не удаляется, так как не повторяется.

Или строка может быть такой:

Lorem ipsum dolor sit amet () sit amet () sit amet () сит нострумное упражнение ullamco labouris nisi ut аликип аликвип ex ea Коммодо конкват.

, которое должно стать:

Lorem ipsum dolor sit amet () sit нострумная тренировка ullamco labouris nisi ut аликип ex ea commodo следquat.

Так что это не просто az, но может иметь и другие (ascii) символы.Я очень рад, если кто-то может помочь мне с этим.

Следующим шагом будет сопоставить (и заменить) что-то вроде этого:

2 вопроса 3 вопроса 4 вопроса 5вопросы

, которые станут:

2 вопроса

Число в конечном выводе может быть любым числом 2,3,4,это не важноВ последнем примере будут только разные цифры, но слова будут одинаковыми.

Answer 1

Интересный вопрос. Это может быть решено с помощью одного оператора preg_replace(), но длина повторяющейся фразы должна быть ограничена, чтобы избежать чрезмерного возврата. Вот решение с закомментированным регулярным выражением, которое работает для тестовых данных и исправляет удвоенные, утроенные (или повторяющиеся n раз) фразы, имеющие максимальную длину 50 символов:

Решение к части 1:

$result = preg_replace('/
    # Match a doubled "phrase" having length up to 50 chars.
    (            # $1: Phrase having whitespace boundaries.
      (?<=\s|^)  # Assert phrase preceded by ws or BOL.
      \S         # First char of phrase is non-whitespace.
      .{0,49}?   # Lazily match phrase (50 chars max).
    )            # End $1: Phrase
    (?:          # Group for one or more duplicate phrases.
      \s+        # Doubled phrase separated by whitespace.
      \1         # Match duplicate of phrase.
    ){1,}        # Require one or more duplicate phrases.
    /x', '$1', $text);

Обратите внимание, что в этом решении «фраза» может состоять из одного слова, и существуют законные случаи, когда сдвоенные слова являются допустимой грамматикой и не должны быть исправлены. Если приведенное выше решение не является желаемым поведением, регулярное выражение можно легко изменить, чтобы определить «фразу» как два или более «слова».

Редактировать: Модифицировано выше регулярное выражение для обработки любого количества повторений фраз. Также добавлено решение второй части вопроса ниже.

А вот аналогичное решение, где фраза начинается со слова из цифр, а повторяющиеся фразы также должны начинаться со слова из цифр (но первое слово из цифр повторяющихся фраз не обязательно должно совпадать с оригиналом):

Решение к части 2:

$result = preg_replace('/
    # Match doubled "phrases" with wildcard digits first word.
    (            # $1: 1st word of phrase (digits).
    \b           # Anchor 1st phrase word to word boundary.
    \d+          # Phrase 1st word is string of digits.
    \s+          # 1st and 2nd words separated by whitespace.
    )            # End $1:  1st word of phrase (digits).
    (            # $2: Part of phrase after 1st digits word.
      \S         # First char of phrase is non-whitespace.
      .{0,49}?   # Lazily match phrase (50 chars max).
    )            # End $2: Part of phrase after 1st digits word.
    (?:          # Group for one or more duplicate phrases.
      \s+        # Doubled phrase separated by whitespace.
      \d+        # Match duplicate of phrase.
      \s+        # Doubled phrase separated by whitespace.
      \2         # Match duplicate of phrase.
    ){1,}        # Require one or more duplicate phrases.
    /x', '$1$2', $text);

Answer 2

Если это помогает, \1, \2 и т. Д. Используются для ссылки на предыдущую группировку. так, например, следующее выберет повторяющиеся слова и заставит их повторяться только один раз:

$string =~ s/(\w+) ( \1)+/$1/g

Повторяющиеся фразы могут быть похожи.

Answer 3

Код решения первой задачи:

<?php

    function split_repeating($string)
    {
        $words = explode(' ', $string);
        $words_count = count($words);

        $need_remove = array();
        for ($i = 0; $i < $words_count; $i++) {
            $need_remove[$i] = false;
        }

        // Here I iterate through the number of words that will be repeated and check all the possible positions reps
        for ($i = round($words_count / 2); $i >= 1; $i--) {
            for ($j = 0; $j < ($words_count - $i); $j++) {
                $need_remove_item = !$need_remove[$j];
                for ($k = $j; $k < ($j + $i); $k++) {
                    if ($words[$k] != $words[$k + $i]) {
                        $need_remove_item = false;
                        break;
                    }
                }
                if ($need_remove_item) {
                    for ($k = $j; $k < ($j + $i); $k++) {
                        $need_remove[$k] = true;
                    }
                }
            }
        }

        $result_string = '';
        for ($i = 0; $i < $words_count; $i++) {
            if (!$need_remove[$i]) {
                $result_string .= ' ' . $words[$i];
            }
        }
        return trim($result_string);
    }



    $string = 'Lorem ipsum dolor sit amet sit amet sit amet sit nostrud exercitation amit sit ullamco laboris nisi ut aliquip ex ea commodo consequat.';

    echo $string . '<br>';
    echo split_repeating($string) . '<br>';
    echo 'Lorem ipsum dolor sit amet sit nostrud exercitation amit sit ullamco laboris nisi ut aliquip ex ea commodo consequat.' . '<br>' . '<br>';



    $string = 'Lorem ipsum dolor sit amet () sit amet () sit amet () sit nostrud exercitation ullamco laboris nisi ut aliquip aliquip ex ea commodo consequat.';

    echo $string . '<br>';
    echo split_repeating($string) . '<br>';
    echo 'Lorem ipsum dolor sit amet () sit nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.';

?>

Код решения второй задачи:

<?php

    function split_repeating($string)
    {
        $words = explode(' ', $string);
        $words_count = count($words);

        $need_remove = array();
        for ($i = 0; $i < $words_count; $i++) {
            $need_remove[$i] = false;
        }

        for ($j = 0; $j < ($words_count - 1); $j++) {
            $need_remove_item = !$need_remove[$j];
            for ($k = $j + 1; $k < ($words_count - 1); $k += 2) {
                if ($words[$k] != $words[$k + 2]) {
                    $need_remove_item = false;
                    break;
                }
            }
            if ($need_remove_item) {
                for ($k = $j + 2; $k < $words_count; $k++) {
                    $need_remove[$k] = true;
                }
            }
        }

        $result_string = '';
        for ($i = 0; $i < $words_count; $i++) {
            if (!$need_remove[$i]) {
                $result_string .= ' ' . $words[$i];
            }
        }
        return trim($result_string);
    }



    $string = '2 questions 3 questions 4 questions 5 questions';

    echo $string . '<br>';
    echo split_repeating($string) . '<br>';
    echo '2 questions';

?>

Answer 4

2 вопроса 3 вопроса 4 вопроса 5 вопросов

становление

2 вопроса

Может быть решено с помощью:

$string =~ s/(\d+ (.*))( \d+ (\2))+/$1/g;

Соответствует числу, за которым следует что-либо (жадно), а затем ряд вещей, начинающихся с пробела, за которым следует число, за которым следует что-то, что соответствует предыдущему что-нибудь .Для всего этого он заменяет его первой парой чисел что-либо.

Answer 5

Старый добрый брутфорс ...

Это так уродливо, что я склонен опубликовать это как eval(base64_decode(...)), но вот оно:

function fixi($str) {
    $a = explode(" ", $str);
    return implode(' ', fix($a));
}

function fix($a) {
    $l = count($a);
    $len = 0;
    for($i=1; $i <= $l/2; $i++) {
        for($j=0; $j <= $l - 2*$i; $j++) {
            $n = 1;
            $found = false;
            while(1) {
                $a1 = array_slice($a, $j, $i);
                $a2 = array_slice($a, $j+$n*$i, $i);
                if ($a1 != $a2)
                    break;
                $found = true;
                $n++;
            }
            if ($found && $n*$i > $len) {
                $len = $n*$i;
                $f_j = $j;
                $f_i = $i;
            }
        }
    }
    if ($len) {
        return array_merge(
            fix(array_slice($a, 0, $f_j)),
            array_slice($a, $f_j, $f_i),
            fix(array_slice($a, $f_j+$len, $l))
        );
    }
    return $a;
}

Знаки пунктуации - часть слова, поэтому не ожидайте чудес.

Answer 6

((?:\b|^)[\x20-\x7E]+)(\1)+ будет соответствовать любой повторяющейся строке печатных символов ASCII, которые начинаются на границе слова.Это означает, что он будет совпадать с hello hello, но не с двойным l в привет.

Если вы хотите настроить символы, которые будут совпадать, вы можете изменить и добавить диапазоны в виде \x##-\x##\x##-\x## (где ## - это hex value) и пропустите -\x##, где вы просто хотите добавить один символ.

Единственная проблема, которую я вижу, состоит в том, что этот несколько простой подход выбрал бы законно повторяющееся словоа не повторная фраза.Если вы хотите заставить его выбирать только повторяющиеся фразы, состоящие из нескольких слов, вы можете использовать что-то вроде ((?:\b|^)[\x20-\x7E]+\s)(\1)+ (обратите внимание на дополнительные \s).

((?:\b|^)[\x20-\x7E]+\s)(.*(\1))+ приближается к решению вашей второйпроблема, но я, возможно, подумал об этом.

Редактировать: просто чтобы уточнить, вы бы использовали $string ~= /((?:\b|^)[\x20-\x7E]+\s)(.*(\1))+/$1/ig в Perl или эквивалент PHP, чтобы использовать это.

Answer 7

Большое спасибо всем за ответ на вопрос. Это мне очень помогло!. Я пробовал как регулярные выражения Ridgerunners, так и dtanders, и хотя они работали (с некоторыми изменениями) над некоторыми тестовыми строками, у меня были проблемы с другими строками.

Так что я пошел на атаку грубой силой :), которая вдохновлена ​​Nox. Таким образом, я мог бы объединить обе проблемы и при этом иметь хорошую производительность (даже лучше, чем регулярное выражение, поскольку это медленно в PHP).

Для всех, кто заинтересован, вот код концепции:

function split_repeating_num($string) {
$words = explode(' ', $string);
$all_words = $words;
$num_words = count($words);
$max_length = 100; //max length of substring to check
$max_words = 4; //maximum number of words in substring 
$found = array();
$current_pos = 0;
$unset = array();
foreach ($words as $key=>$word) {
    //see if this word exist in the next part of the string
    $len = strlen($word);
    if ($len === 0) continue;
    $current_pos += $len + 1; //+1 for the space
    $substr = substr($string, $current_pos, $max_length);
    if (($pos = strpos(substr($string, $current_pos, $max_length), $word)) !== false) {
        //found it
        //set pointer words and all_words to same value
        while (key($all_words) < $key ) next($all_words);
        while (key($all_words) > $key ) prev($all_words);
        $next_word = next($all_words);

        while (is_numeric($next_word) || $next_word === '') {
            $next_word = next($all_words);
        }
        // see if it follows the word directly
        if ($word === $next_word) {
            $unset [$key] = 1;
        } elseif ($key + 3 < $num_words) {
            for($i = $max_words; $i > 0; $i --) {
                $x = 0;
                $string_a = '';
                $string_b = '';
                while ($x < $i ) {
                    while (is_numeric($next_word) || $next_word === '' ) {
                        $next_word = each($all_words);
                    }
                    $x ++;
                    $string_a .= $next_word;
                    $string_b .= $words [key($all_words) + $i];
                }

                if ($string_a === $string_b) {
                    //we have a match
                    for($x = $key; $x < $i + $key; $x ++)
                        $unset [$x] = 1;
                }
            }
        }
    }

}
foreach ($unset as $k=>$v) {
    unset($words [$k]);
}
return implode(' ', $words);

}

Есть еще некоторые незначительные проблемы, и мне нужно проверить их, но, похоже, они справляются со своей задачей.