PHP Обнаружение повторяющегося текста

Ответ 1

Это основная проблема классификации текста. lots статьи о том, как определить, если какой-то текст - это спам/не спам, который я бы рекомендовал копать, если вы действительно хотите вдаваться в подробности. Многое из этого, вероятно, слишком велико для того, что вам нужно сделать здесь.

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

Вот очертания того, что я буду делать:

• Построить гистограмму вхождения слов для строки ввода
• Изучите гистограммы некоторого допустимого и недопустимого текста
• Придумайте формулу для классификации гистограммы как действительной или нет

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

Вот пример кода для вас:

$str = 'Love a and peace love a and peace love a and peace love a and peace love a and peace love a and peace';

// Build a histogram mapping words to occurrence counts
$hist = array();

// Split on any number of consecutive whitespace characters
foreach (preg_split('/\s+/', $str) as $word)
{
  // Force all words lowercase to ignore capitalization differences
  $word = strtolower($word);

  // Count occurrences of the word
  if (isset($hist[$word]))
  {
    $hist[$word]++;
  }
  else
  {
    $hist[$word] = 1;
  }
}

// Once you're done, extract only the counts
$vals = array_values($hist);
rsort($vals); // Sort max to min

// Now that you have the counts, analyze and decide valid/invalid
var_dump($vals);

Когда вы запустите этот код в некоторых повторяющихся строках, вы увидите разницу. Здесь график массива $vals из строки примера, которую вы указали:

Сравните это с первыми двумя параграфами Martin Luther King Jr. bio из Википедии:

Длинный хвост указывает много уникальных слов. Там еще некоторое повторение, но общая форма показывает некоторые изменения.

FYI, PHP имеет stats пакет, который вы можете установить, если вы собираетесь делать много математики, как стандартное отклонение, распределение моделирование и т.д.

Ответ 2

Вы можете использовать регулярное выражение, например:

if (preg_match('/(.{10,})\\1{2,}/', $theText)) {
    echo "The string is repeated.";
}

Пояснение:

• (.{10,}) ищет и фиксирует строку длиной не менее 10 символов
• \\1{2,} ищет первую строку как минимум еще 2 раза

Возможные настройки в соответствии с вашими потребностями:

• Измените 10 на более высокое или меньшее число, чтобы соответствовать более длинным или коротким повторяющимся строкам. Я просто использовал 10 в качестве примера.
• Если вы хотите поймать хотя бы одно повторение (love and peace love and peace), удалите {2,}. Если вы хотите поймать большее количество повторений, увеличьте 2.
• Если вам все равно, сколько раз повторение происходит, только это происходит, удалите , в {2,}.

Ответ 3

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

Вот какой код, который не использует PCRE и использует встроенные строковые функции PHP (str_word_count и array_count_values ​​):

<?php
    $words = str_word_count("Love a and peace love a and peace love a and peace love a and peace love a and peace love a and peace", 1);
    $words = array_count_values($words);

  var_dump($words);
  /*
  array(5) {
    ["Love"]=>
    int(1)
    ["a"]=>
    int(6)
    ["and"]=>
    int(6)
    ["peace"]=>
    int(6)
    ["love"]=>
    int(5)
  }
  */

Некоторые настройки могут быть следующими:

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

Ответ 4

Еще одна идея - использовать substr_count итерацию:

$str = "Love a and peace love a and peace love a and peace love a and peace love a and peace love a and peace";

$rep = "";

$str = strtolower($str);
for($i=0,$len=strlen($str),$pattern=""; $i<$len; ++$i) {
  $pattern.= $str[$i];
  if(substr_count($str,$pattern)>1)
    $rep = strlen($rep)<strlen($pattern) ? $pattern : $rep;
  else
    $pattern = "";
}

// warn if 20%+ of the string is repetitive
if(strlen($rep)>strlen($str)/5) echo "Repetitive string alert!";
else echo "String seems to be non-repetitive.";

echo " Longest pattern found: '$rep'";

Что бы вывести

Repetitive string alert! Longest pattern found: 'love a and peace love a and peace love a and peace'

Ответ 5

// 3 examples of how you might detect repeating user input

// use preg_match

// pattern to match agains
$pattern = '/^text goes here$/';

// the user input
$input = 'text goes here';

// check if its match
$repeats = preg_match($pattern, $input);

if ($repeats) {
    var_dump($repeats);
} else {
    // do something else
}

// use strpos

$string = 'text goes here';
$input = 'text goes here';
$repeats = strpos($string, $input);

if ($repeats !== false) {
    # code...
    var_dump($repeats);
} else {
    // do something else
}

// or you could do something like:
function repeatingWords($str)
{
    $words = explode(' ', trim($str));  //Trim to prevent any extra blank
    if (count(array_unique($words)) == count($words)) {
        return true; //Same amount of words
    }

    return false;
}

$string = 'text goes here. text goes here. ';

if (repeatingWords($string)) {
    var_dump($string);
} else {
    // do something else
}

Ответ 6

Я думаю, что подход к поиску повторяющихся слов будет беспорядочным. Скорее всего, вы получите повторяющиеся слова в реальных описаниях: "Я действительно, действительно, действительно, как мороженое, особенно ванильный мороженое".

Лучший подход состоит в том, чтобы разбить строку, чтобы получить слова, найти все уникальные слова, добавить все число символов уникальных слов и установить слишком ограниченное число. Скажем, вам требуется 100 символов, требуется около 60 уникальных символов из слов.

Копирование подхода @ficuscr

$words = str_word_count("Love a and peace love a and peace love a and peace love a and peace love a and peace love a and peace", 1);
$total = 0;
foreach ($words as $key => $count) { $total += strlen($key) }

Ответ 7

Здесь приведен код функции, которую вы ищете в описании:

<?php
function duplicate(){
    $txt = strtolower("Love a and peace love a and peace love a and peace love a and peace love a and peace love a and peace");
    $strings = explode(" ",$txt);
    $set = 2 ;
    for($i=0;$i < sizeof($strings);$i++){
        $count = 0;
        $current = $strings[$i];
        for($j=$i+1;$j < sizeof($strings);$j++){
            if($strings[$j]!==$current){
                continue;
            }else if($count<$set){
                $count++;
            }else{
                echo ("String ".$current." repeated more than ".$set." times\n");
            }
        }
    }
}
echo("Hello World!\n");
duplicate();
?>

Ответ 8

Я не уверен, что это хорошая идея для борьбы с такой проблемой. Если человек хочет ставить хлам в поле aboutme, они всегда придумают, как это сделать. Но я проигнорирую этот факт и борюсь с проблемой как алгоритмический вызов:

Наличие строки S, которая состоит из подстрок (которые могут появляться много раз и неперекрывающиеся) найти подстроку, в которую она состоит.

Определение - вошь, и я предполагаю, что строка уже преобразована в нижний регистр.

Сначала проще:

Используйте модификацию самой длинной общей подпоследовательности, которая имеет легкое решение для программирования DP. Но вместо того, чтобы найти подпоследовательность в двух разных последовательностях, вы можете найти самую длинную общую подпоследовательность строки относительно той же строки LCS(s, s).

В начале это звучит глупо (конечно LCS(s, s) == s), но на самом деле нас не волнует ответ, мы заботимся о DP-матрице, которую она получает.

Посмотрим на пример: s = "abcabcabc", а матрица:

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 1, 0, 0, 1, 0, 0]
[0, 0, 2, 0, 0, 2, 0, 0, 2, 0]
[0, 0, 0, 3, 0, 0, 3, 0, 0, 3]
[0, 1, 0, 0, 4, 0, 0, 4, 0, 0]
[0, 0, 2, 0, 0, 5, 0, 0, 5, 0]
[0, 0, 0, 3, 0, 0, 6, 0, 0, 6]
[0, 1, 0, 0, 4, 0, 0, 7, 0, 0]
[0, 0, 2, 0, 0, 5, 0, 0, 8, 0]
[0, 0, 0, 3, 0, 0, 6, 0, 0, 9]

Обратите внимание на красивые диагонали. Как вы видите, первая диагональ заканчивается на 3, вторая с 6 и третья - с 9 (наше оригинальное решение DP, которое нам все равно).

Это не совпадение. Надеюсь, что, посмотрев более подробно о том, как построена матрица DP, вы можете видеть, что эти диагонали соответствуют повторяющимся строкам.

Вот пример для s = "aaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtas" и самая последняя строка в матрице: [0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 17, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 34, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 51, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 68].

Как вы видите, большие числа (17, 34, 51, 68) соответствуют концу диагоналей (там также есть некоторый шум, потому что я специально добавил небольшие дубликаты букв, например aaa).

Что подсказывает, что мы можем просто найти gcd самых больших двух чисел gcd(68, 51) = 17, который будет длиной нашей повторяющейся подстроки.

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

И вот мы идем: строка "aaabasdfwasfsdtas".

P.S. этот метод позволяет находить повторы, даже если они слегка изменены.

Для людей, которые хотели бы поиграть здесь, это python script (который был создан в сутолоке, поэтому не стесняйтесь улучшать):

def longest_common_substring(s1, s2):
    m = [[0] * (1 + len(s2)) for i in xrange(1 + len(s1))]
    longest, x_longest = 0, 0
    for x in xrange(1, 1 + len(s1)):
        for y in xrange(1, 1 + len(s2)):
            if s1[x - 1] == s2[y - 1]:
                m[x][y] = m[x - 1][y - 1] + 1
                if m[x][y] > longest:
                    longest = m[x][y]
            else:
                m[x][y] = 0
    return m

s = "aaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtas"
m = longest_common_substring(s, s)
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.cm as cm
M = np.array(m)
print m[-1]
arr = np.asarray(M)
plt.imshow(arr, cmap = cm.Greys_r, interpolation='none')
plt.show()

Я рассказывал про легкий путь и забыл написать о трудном пути. Уже поздно, поэтому я просто объясню эту идею. Реализация сложнее, и я не уверен, даст ли она вам лучшие результаты. Но вот он:

Используйте алгоритм самая длинная повторяющаяся подстрока (вам нужно будет реализовать trie или дерево суффикса, что не так просто в php).

После этого:

s = "aaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtas"
s1 = largest_substring_algo1(s)

Взял здесь most_substring_algo1. На самом деле это не самое лучшее (просто для показа идеи), поскольку оно не использует вышеупомянутые структуры данных. Результаты для s и s1:

aaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtas
aaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtasaa

Как вы видите, разница между ними на самом деле является подстрокой, которая была дублирована.

Ответ 9

У вас есть сложная проблема на ваших руках, прежде всего потому, что ваши требования несколько неясны.

Вы указываете, что хотите запретить повторный текст, потому что это "плохо".

Подумайте о том, кто ставит последнюю строфу Роберта Мороза, останавливающуюся Вудсом на Снежном Вечере в их профиле:

These woods are lovely, dark and deep
but I have promises to keep
and miles to go before I sleep
and miles to go before I sleep

Вы можете считать это хорошим, но у него есть повторение. Так что хорошего, и что плохого? (обратите внимание, что это еще не проблема реализации, вы просто ищете способ определения "плохих повторений" )

Непосредственное обнаружение дубликатов, таким образом, оказывается сложным. Поэтому давайте перейдем к трюкам.

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

реализация:

$THRESHOLD = ???;
$bio = ???;
$zippedbio = gzencode($bio);
$compression_ratio = strlen($zippedbio) / strlen($bio);
if ($compression_ratio >= $THRESHOLD) {
  //ok;
} else {
  //not ok;
}

Несколько экспериментальных результатов из примеров, найденных в этом вопросе/ответах:

• "Любовь и мир любить и мир любить и мир любить и мир любить и мир любить и мир": 0.3960396039604
• "Эти леса прекрасные, темные и глубокие но у меня есть promises, чтобы и мили, чтобы идти, прежде чем я сплю и мили, чтобы идти, прежде чем я сплю ": 0.78461538461538
• "aaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtas": 0.58823529411765

предложите пороговое значение около 0,6, прежде чем отклонить его как слишком повторяющееся.