Как найти самую длинную подстроку, которая встречается в каждом элементе массива?

У меня есть коллекция текстов от некоторых авторов. Каждый автор имеет уникальную подпись или ссылку, которая встречается во всех их текстах.

Пример для 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'];

Ожидаемый результат для Author1: @jhsad.sadas.com

Пример для 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.'];

Ожидаемый результат для Author2:

This is the
 *author's* signature.

Обратите особое внимание на то, что нет надежных идентифицирующих символов (или позиций), которые обозначают начало или конец подписи. Это может быть URL, упоминание в Твиттере, любой вид простого текста и т. Д. Любой длины, содержащей любую последовательность символов, встречающуюся в начале, конце или середине строки.

Я ищу метод, который извлечет самую длинную подстроку, которая существует во всех $text элементы для одного автора.

Предполагается, что для выполнения этой задачи все авторы будут иметь подстроку подписи, которая существует в каждом посте / тексте.

ИДЕЯ: Я думаю о преобразовании слов в векторы и нахождении сходства между каждым текстом. Мы можем использовать косинусное сходство, чтобы найти подписи. Я думаю, что решение должно быть чем-то вроде этой идеи.

Прокомментированный код mickmackusa отражает суть желаемого, но я хотел бы посмотреть, есть ли другие способы достижения желаемого результата.

Источник

2 ответа

Решение

Вот мое мышление:

  1. Сортируйте коллекцию сообщений автора по длине строки (по возрастанию), чтобы вы работали от небольших текстов к большим текстам.
  2. Разделите текст каждой записи на один или несколько символов пробела, чтобы во время обработки вы обрабатывали только полностью не пробельные подстроки.
  3. Найти подходящие подстроки, которые встречаются в каждом последующем сообщении, в сравнении с постоянно сужающимся массивом подстрок (overlaps).
  4. Сгруппируйте последовательные совпадающие подстроки, проанализировав их значение индекса.
  5. "Восстановить" сгруппированные последовательные подстроки в их исходную строковую форму (конечно, обрезать начальные и конечные пробельные символы).
  6. Сортировать восстановленные строки по длине строки (по убыванию), чтобы самой длинной строке была назначена 0 индекс.
  7. Выведите на экран подстроку, которая предположительно является авторской подписью (в лучшем случае) на основе общности и длины.

Код: ( Демо)

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

Выход:

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.
Источник

Ты можешь использовать preg_match() с помощью регулярного выражения для достижения этой цели.

$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
Источник
Другие вопросы по тегам