Wie findet man den längsten Teilstring, der in jedem Element eines Arrays vorkommt?

Question

Ich habe eine Sammlung von Texten von einigen Autoren. Jeder Autor hat eine eindeutige Signatur oder einen Link, der in allen seinen Texten vorkommt.

Beispiel für Author1:

$texts=['sdsadsad daSDA DDASd asd aSD Sd dA SD ASD sadasdasds sadasd 

@jhsad.sadas.com sdsdADSA sada', 
'KDJKLFFD GFDGFDHGF GFHGFDHGFH GFHFGH Lklfgfd gdfsgfdsg df gfdhgf g 
hfghghjh jhg @jhsad.sadas.com sfgff fsdfdsf', 
'jhjkfsdg fdgdf sfds hgfj j kkjjfghgkjf hdkjtkj lfdjfg hkgfl 
@jhsad.sadas.com dsfjdshflkds kg lsfdkg;fdgl']; 

erwarteten Ausgabe für Author1 ist: @jhsad.sadas.com

---

Beispiel für Author2:

$texts=['This is some random string representative of non-signature text. 

This is the 
*author\'s* signature.', 
'Different message body text.  This is the 
*author\'s* signature. 

This is an afterthought that expresses that a signature is not always at the end.', 
'Finally, this is unwanted stuff. This is the 
*author\'s* signature.']; 

Erwartete Ausgang für Author2 ist:

This is the 
*author's* signature. 

Pay insbesondere Hinweis Es auf die Tatsache, gibt es keine zuverlässige Identifizierung von Zeichen (oder Positionen), die den Anfang oder das Ende der Signatur bedeuten. Es kann eine URL sein, eine Twitter-Erwähnung, irgendeine Art von einfachem Text usw. beliebiger Länge, die eine Folge von Zeichen enthält, die am Anfang, am Ende oder in der Mitte der Zeichenfolge auftritt.

Ich suche eine Methode, die die längste Teilzeichenfolge, die in allen $text Elemente für einen einzelnen Autor existiert extrahieren wird.

Es wird erwartet, dass alle Autoren für diese Aufgabe einen Signatur-Teilstring haben, der in jedem Post/Text existiert.

IDEA: Ich denke über die Umwandlung von Wörtern in Vektoren und Suche nach Ähnlichkeit zwischen den einzelnen Texten. Wir können Kosinusähnlichkeit verwenden, um die Signaturen zu finden. Ich denke, die Lösung muss eine Sache wie diese Idee sein.

mickmackusa's commented code erfasst die Essenz dessen, was gewünscht wird, aber ich würde gerne sehen, ob es andere Möglichkeiten gibt, das gewünschte Ergebnis zu erzielen.

Answer 1

Hier ist mein Denken:

1. Sortierung einer Sammlung des Autors Beiträge von String-Länge (aufsteigend), so dass Sie von kleineren Texten zu größeren Texten arbeiten.
2. Teilen Sie den Text jedes Posts auf ein oder mehrere Leerzeichen, so dass Sie während der Verarbeitung nur vollständig Nicht-Leerzeichen-Teilstrings behandeln.
3. Finden Sie übereinstimmende Teilstrings, die in jedem nachfolgenden Post im Vergleich zu einem immer enger werdenden Array von Teilstrings auftreten (overlaps).
4. Gruppieren Sie die aufeinander folgenden übereinstimmenden Teilstrings, indem Sie deren Indexwert analysieren.
5. "Rekonstituieren" Sie die gruppierten aufeinander folgenden Teilzeichenfolgen in ihre ursprüngliche Zeichenfolgenform (natürlich abgeschnitten von führenden und nachfolgenden Leerzeichen).
6. Sortieren Sie die wiederhergestellten Zeichenfolgen nach Zeichenfolgelänge (absteigend), sodass die längste Zeichenfolge dem 0-Index zugewiesen wird.
7. Drucken, um den Teilstring zu screenen, von dem angenommen wird, dass er die Signatur des Autors ist (als beste Schätzung), basierend auf Gemeinsamkeit und Länge.

Code: (Demo)

$posts['Author1']=['sdsadsad daSDA DDASd asd aSD Sd dA SD ASD sadasdasds sadasd 

@jhsad.sadas.com sdsdADSA sada', 
'KDJKLFFD GFDGFDHGF GFHGFDHGFH GFHFGH Lklfgfd gdfsgfdsg df gfdhgf g 
hfghghjh jhg @jhsad.sadas.com sfgff fsdfdsf', 
'jhjkfsdg fdgdf sfds hgfj j kkjjfghgkjf hdkjtkj lfdjfg hkgfl 
@jhsad.sadas.com dsfjdshflkds kg lsfdkg;fdgl']; 

$posts['Author2']=['This is some random string representative of non-signature text. 

This is the 
*author\'s* signature.', 
     'Different message body text.  This is the 
*author\'s* signature. 

    This is an afterthought that expresses that a signature is not always at the end.', 
     'Finally, this is unwanted stuff. This is the 
*author\'s* signature.']; 

foreach($posts as $author=>$texts){ 
    echo "Author: $author\n"; 

    usort($texts,function($a,$b){return strlen($a)-strlen($b);}); // sort ASC by strlen; mb_strlen probably isn't advantageous 
    var_export($texts); 
    echo "\n"; 

    foreach($texts as $index=>$string){ 
     if(!$index){ 
      $overlaps=preg_split('/\s+/',$string,NULL,PREG_SPLIT_NO_EMPTY); // declare with all non-white-space substrings from first text 
     }else{ 
      $overlaps=array_intersect($overlaps,preg_split('/\s+/',$string,NULL,PREG_SPLIT_NO_EMPTY)); // filter word bank using narrowing number of words 
     } 
    } 
    var_export($overlaps); 
    echo "\n"; 

    // batch consecutive substrings 
    $group=null; 
    $consecutives=[]; // clear previous iteration's data 
    foreach($overlaps as $i=>$word){ 
     if($group===null || $i-$last>1){ 
      $group=$i; 
     } 
     $last=$i; 
     $consecutives[$group][]=$word; 
    } 
    var_export($consecutives); 
    echo "\n"; 

    foreach($consecutives as $words){ 
     // match potential signatures in first text for measurement: 
     if(preg_match_all('/\Q'.implode('\E\s+\Q',$words).'\E/',$texts[0],$out)){ // make alternatives characters literal using \Q & \E 
      $potential_signatures=$out[0]; 
     } 
    } 
    usort($potential_signatures,function($a,$b){return strlen($b)-strlen($a);}); // sort DESC by strlen; mb_strlen probably isn't advantageous 

    echo "Assumed Signature: {$potential_signatures[0]}\n\n"; 
} 

Ausgang:

Author: Author1 
array (
    0 => 'sdsadsad daSDA DDASd asd aSD Sd dA SD ASD sadasdasds sadasd 

@jhsad.sadas.com sdsdADSA sada', 
    1 => 'jhjkfsdg fdgdf sfds hgfj j kkjjfghgkjf hdkjtkj lfdjfg hkgfl 
@jhsad.sadas.com dsfjdshflkds kg lsfdkg;fdgl', 
    2 => 'KDJKLFFD GFDGFDHGF GFHGFDHGFH GFHFGH Lklfgfd gdfsgfdsg df gfdhgf g 
hfghghjh jhg @jhsad.sadas.com sfgff fsdfdsf', 
) 
array (
    11 => '@jhsad.sadas.com', 
) 
array (
    11 => 
    array (
    0 => '@jhsad.sadas.com', 
), 
) 
Assumed Signature: @jhsad.sadas.com 

Author: Author2 
array (
    0 => 'Finally, this is unwanted stuff. This is the 
*author\'s* signature.', 
    1 => 'This is some random string representative of non-signature text. 

This is the 
*author\'s* signature.', 
    2 => 'Different message body text.  This is the 
*author\'s* signature. 

    This is an afterthought that expresses that a signature is not always at the end.', 
) 
array (
    2 => 'is', 
    5 => 'This', 
    6 => 'is', 
    7 => 'the', 
    8 => '*author\'s*', 
    9 => 'signature.', 
) 
array (
    2 => 
    array (
    0 => 'is', 
), 
    5 => 
    array (
    0 => 'This', 
    1 => 'is', 
    2 => 'the', 
    3 => '*author\'s*', 
    4 => 'signature.', 
), 
) 
Assumed Signature: This is the 
*author's* signature. 

Answer 2

Sie können preg_match() mit einem Regex verwenden, um dies zu erreichen.

$str = "KDJKLFFD GFDGFDHGF GFHGFDHGFH GFHFGH Lklfgfd gdfsgfdsg df gfdhgf g hfghghjh jhg @jhsad.sadas.com sfgff fsdfdsf"; 

preg_match("/\@[^\s]+/", $str, $match); 

var_dump($match); //Will output the signature