PHP Rileva testo duplicato

Question

Ho un sito in cui gli utenti possono inserire una descrizione su se stessi.

La maggior parte degli utenti scrive qualcosa di appropriato ma alcuni semplicemente copia/incolla lo stesso testo un numero di volte (per creare l'aspetto di una buona quantità di testo).

ad esempio: "L'amore di pace e di amore una pace e l'amore di una pace e di amore di una pace e di amore una e l'amore di pace di e di pace"

C'è un buon metodo per rilevare il testo ripetitivo con PHP?

L'unico concetto che ho attualmente sarebbe quello di suddividere il testo in parole separate (delimitate dallo spazio) e quindi cercare di vedere se la parola è ripetuta più di un insieme limitato. Nota: non sono sicuro al 100% su come codificherei questa soluzione.

Pensieri sul modo migliore per rilevare il testo duplicato? O come codificare l'idea sopra?

Answer 1

Si tratta di un problema di fondo di classificazione del testo. Ci sono lots di articles là fuori su come determinare se un testo è spam/non spam che consiglierei di scavare dentro se vuoi davvero entrare nei dettagli. Molto probabilmente è eccessivo per ciò che devi fare qui.

Concedere un approccio sarebbe quello di valutare il motivo per cui si richiede alle persone di immettere più bios, ma presumo che tu abbia già deciso che forzare le persone a inserire più testo è la strada da percorrere.

Ecco uno schema di quello che vorrei fare:

1. Costruisci un istogramma di occorrenze di parole per la stringa di input
2. studio gli istogrammi di una parte di testo validi e non validi
3. trovare una formula per classificare un istogramma valido o no

Questo approccio richiederebbe di capire cosa c'è di diverso tra i due set. Intuitivamente, mi aspetterei che lo spam mostri un numero inferiore di parole univoche e se si tracciano i valori dell'istogramma, un'area più alta sotto la curva si concentra verso le parole in alto.

Ecco alcuni esempi di codice per farti andare:

$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); 

Quando si esegue questo codice su alcune stringhe ripetitive, vedrete la differenza. Ecco un terreno di matrice $vals dalla stringa esempio che ha dato:

Confronti che, con i primi due paragrafi di Martin Luther King Jr.'s bio da Wikipedia:

Una lunga coda indica un sacco di parole uniche C'è ancora qualche ripetizione, ma la forma generale mostra qualche variazione.

FYI, PHP ha un pacchetto stats che è possibile installare se si stanno facendo molti calcoli come la deviazione standard, la modellazione di distribuzione, ecc.

Answer 2

Si potrebbe usare una regex, come questo:

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

Spiegazione:

• (.{10,}) cerca e cattura una stringa che è lunga almeno 10 caratteri
• \\1{2,} guarda per la prima stringa almeno altre 2 volte

Possibili ritocchi in base alle proprie esigenze:

• Change 10 ad un numero maggiore o minore per abbinare le stringhe più o meno ripetuti. Ho appena usato 10 come esempio.
• Se si desidera rilevare anche una ripetizione (love and peace love and peace), eliminare {2,}. Se si desidera ottenere un numero maggiore di ripetizioni, aumentare lo 2.
• Se non ti interessa quante volte si verifica la ripetizione, solo che si verifica, eliminare il , in {2,}.

Answer 3

Penso che tu sia sulla strada giusta, spezzando la corda e guardando le parole ripetute.

Ecco il codice però che non utilizza un PCRE e sfrutta PHP funzioni di stringa nativa (str_word_count e 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) 
    } 
    */ 

Alcune modifiche potrebbero essere a:

• impostare una lista di parole comuni da ignorare
• guardare l'ordine delle parole (precedente e successivo), non solo il numero di occorrenze

Answer 4

Penso che l'approccio di trovare parole duplicate, sarà disordinato. Molto probabilmente otterrai parole duplicate in descrizioni reali "Io davvero, davvero, davvero, come la crema di gelato, in particolare la crema di gelato alla vaniglia".

Un approccio migliore consiste nel dividere la stringa per ottenere le parole, trovare tutte le parole univoche, aggiungere tutti i conteggi dei caratteri delle parole univoche e impostare anche questo limite. Supponi, hai bisogno di 100 descrizioni di caratteri, richiedono circa 60 caratteri univoci dalle parole.

Copia approccio di @ 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) } 

Answer 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 
} 

Answer 6

Ecco un codice della funzione che stai cercando nella descrizione:

<?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(); 
?> 

Answer 7

Un'altra idea potrebbe essere quella di utilizzare substr_count iterazione:

$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'"; 

che sarebbe uscita

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

Answer 8

Non sono sicuro se sia una buona idea combattere questo problema. Se una persona vuole mettere delle cianfrusaglie in un campo comune, verrà sempre in mente l'idea di come farlo. Ma voglio ignorare questo fatto e combattere il problema come una sfida algoritmico:

Avere una stringa S, che consiste delle stringhe (che può apparire molte volte e non si sovrappongono) trovare la stringa che consiste di.

La definizione è pidocchio e presumo che la stringa sia già stata convertita in lettere minuscole.

Prima un modo più semplice:

---

Uso modifica di un longest common subsequence che ha una semplice soluzione di programmazione DP. Ma invece di trovare una sottosequenza in due sequenze diverse, è possibile trovare la sottosequenza comune più lunga della stringa rispetto alla stessa stringa LCS(s, s).

Sembra stupido all'inizio (sicuramente LCS(s, s) == s), ma in realtà non ci interessa la risposta, ci interessa la matrice DP che ottiene. sguardo

Let l'esempio: s = "abcabcabc" e la matrice è:

[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] 

Nota le belle diagonali lì. Come vedi la prima diagonale finisce con 3, la seconda con 6 e la terza con 9 (la nostra soluzione DP originale che non ci interessa).

Questa non è una coincidenza. Spero che dopo aver esaminato maggiori dettagli su come viene costruita la matrice DP, puoi vedere che queste diagonali corrispondono a stringhe duplicate.

Ecco un esempio per s = "aaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtas" e l'ultima riga della matrice è: [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].

Come si vedono i numeri grandi (17, 34, 51, 68) corrispondono alla fine delle diagonali (c'è anche un po 'di rumore solo perché ho aggiunto in particolare piccole lettere duplicate come aaa).

Che suggeriscono che possiamo trovare lo gcd dei due numeri più grandi gcd(68, 51) = 17 che sarà la lunghezza della nostra sottostringa ripetuta.

Qui solo perché sappiamo che l'intera stringa consiste di sottostringhe ripetute, sappiamo che inizia nella posizione 0 ° (se non lo sappiamo dovremmo trovare l'offset).

E qui andiamo: la stringa è "aaabasdfwasfsdtas".

P.S. questo metodo consente di trovare le ripetizioni anche se sono leggermente modificate.

Per le persone che vorrebbero giocare qui intorno è uno script python (che è stato creato in un caos quindi sentitevi liberi di migliorare):

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() 

---

ho parlato nel modo più semplice, e ho dimenticato di scrivere a proposito. Si sta facendo tardi, quindi spiegherò solo l'idea. L'implementazione è più difficile e non sono sicuro che vi darà risultati migliori. Ma eccolo:

Utilizzare l'algoritmo per longest repeated substring (sarà necessario implementare trie o suffix tree che non è facile in php).

Dopo questo:

s = "aaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtas" 
s1 = largest_substring_algo1(s) 

Ha preso l'attuazione di largest_substring_algo1 from here. In realtà non è il massimo (solo per mostrare l'idea) in quanto non utilizza le strutture dati sopra menzionate. I risultati per s e s1 sono:

aaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtas 
aaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtasaa 

Come si vede la differenza tra loro è in realtà la stringa che è stato duplicato.

Answer 9

Hai un problema difficile a portata di mano, soprattutto perché le tue esigenze non sono chiare.

Si indica che si desidera disabilitare il testo ripetuto, perché è "cattivo".

consideri qualcuno con chi mette l'ultima strofa di Robert Frosts arresto da Woods su uno Snowy Sera nel loro profilo:

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 

Si potrebbe considerare questo bene, ma ha una ripetizione. Allora, cosa c'è di buono, e cosa c'è di male? (nota che questo non è ancora un problema di implementazione, stai solo cercando un modo per definire "cattive ripetizioni")

Rilevare direttamente i duplicati risulta quindi difficile. Quindi deduciamo i trucchi.

La compressione consente di acquisire dati ridondanti e di comprimerli in qualcosa di più piccolo. Un testo molto ripetitivo sarebbe molto facilmente compresso. Un trucco che potresti eseguire, è prendere il testo, comprimerlo e dare un'occhiata al rapporto di compressione. Quindi modifica il rapporto consentito in qualcosa che trovi accettabile.

implementazione:

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

Un paio di risultati sperimentali da esempi si trovano in questa domanda/risposta:

• "L'amore di una pace e di amore di una pace e di amore una e l'amore di pace a e la pace amore e pace pace amore e pace ": 0.3960396039604
• "Questi boschi sono belle, scuri e profondi ma devo promesse da mantenere e miglia da percorrere prima di dormire e miglia da percorrere prima di dormire": 0.78461538461538
• "aaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtasaaabasdfwasfsdtas": 0,58823529411765

suggerire un valore di soglia di circa 0,6 prima di rifiutarlo come troppo ripetitivo.