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

Question

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

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

Пример для 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 элементы для одного автора.

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

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

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

0

arrays longest-substring php search similarity

Решение

Другие решения

Ты можешь использовать 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

2

Источник

Accepted Answer

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

Сортируйте авторскую коллекцию постов по длине строки (по возрастанию), чтобы вы работали от небольших текстов к большим текстам.
Разделите текст каждой записи на один или несколько символов пробела, чтобы во время обработки вы обрабатывали только полностью не пробельные подстроки.
Найти подходящие подстроки, которые встречаются в каждом последующем сообщении, в сравнении с постоянно сужающимся массивом подстрок (overlaps).
Группируйте последовательные совпадающие подстроки, анализируя их значение индекса.
«Восстановить» сгруппированные последовательные подстроки в их исходную строковую форму (конечно, обрезать начальные и конечные пробельные символы).
Сортировать восстановленные строки по длине строки (по убыванию), чтобы самой длинной строке была назначена 0 индекс.
Выведите на экран подстроку, которая считается подписью автора (в качестве наилучшего предположения) на основе общности и длины.

Код: (демонстрация)

$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.

2