PHP - 比较多维 sub-arrays 并在相似度阈值上合并
PHP - Compare multidimensional sub-arrays to each other and merge on similarity threshold
简介 - 此问题已于 2018 年 5 月 27 日更新：
我有1个PHPmultidimensional-array，包含6个sub-arrays，每个包含20个子sub-arrays，其中反过来，每个包含2个子sub-arrays，一个是字符串（header），另一个是不特定数量的关键词（keywords）。
我希望将 120 个子 sub-arrays 中的每一个与其余 5 sub-arrays 中包含的 100 个其他子 sub-arrays 进行比较。这样 sub-sub-array1 在 sub-array1 与 sub-array1 相比较并包括 sub-array20 在 sub-array2 到 sub-array6,等等.
如果有足够的关键字在两个子sub-arrays中被认为是相同的并且headers也是一样，都是使用Levenshtein距离，子sub-arrays会合并。
示例脚本
我已经编写了一个脚本来执行此操作，但要使用两个单独的数组来演示我的目标：
<?php
// Variable deciding maximum Levenshtein distance between two words. Can be changed to lower / increase threshhold for whether two keywords are deemed identical.
$lev_point_value = 3;
// Variable deciding minimum amount of identical (passed the $lev_point_value variable) keywords needed to merge arrays. Can be changed to lower / increase threshhold for how many keywords two arrays must have in common to be merged.
$merge_tag_value = 4;
// Variable deciding minimum Levenshtein distance between two headers needed to merge arrays. Can be changed to lower / increase threshhold for whether two titles are deemed identical.
$merge_head_value = 22;
// Array1 - A story about a monkey, includes at header and keywords.
$array1 = array (
"header" => "This is a story about a monkey.",
'keywords' => array( "Trees", "Monkey", "Flying", "Drink", "Vacation", "Coconut", "Big", "Bonobo", "Climbing"
));
// Array1 - Another, but slightly different story about a monkey, includes at header and keywords.
$array2 = array (
"header" => "This is another, but different story, about a monkey.",
'keywords' => array( "Monkey", "Big", "Trees", "Bonobo", "Fun", "Dance", "Cow", "Coconuts"
));
// Function comparing keywords between two arrays. Uses levenshtein distance lesser than $lev_point_value. Each pass increases $merged_tag, which is then returned.
function sim_tag_index($array1, $array2, $lev_point_value) {
$merged_tag = 0;
foreach ($array1['keywords'] as $item1){
foreach ($array2["keywords"] as $item2){
if (levenshtein($item1, $item2) <= $lev_point_value) {
$merged_tag++;
};
}
};
return $merged_tag;
}
// Function comparing headers between two arrays using levenshtein distance, which is then returned as $merged_head.
function sim_header_index($array1, $array2) {
$merged_head = (levenshtein($array1['header'], $array2['header']));
return $merged_head;
}
// Function running sim_tag_index against $merge_tag_value, if it passes, then running sim_tag_index against $merge_head_value, if this passes aswell, merge arrays.
function merge_on_sim($array1, $array2, $merge_tag_value, $merge_head_value, $lev_point_value) {
$group = array();
if (sim_tag_index($array1, $array2, $lev_point_value) >= $merge_tag_value) {
if (sim_header_index($array1, $array2) >= $merge_head_value) {
$group = (array_unique(array_merge($array1["keywords"],$array2["keywords"])));
}
}
return $group;
}
// Printing function merge_on_sim.
print_r (merge_on_sim($array1, $array2, $merge_tag_value, $merge_head_value, $lev_point_value));
?>
问题：
我如何扩展或重写我的脚本以通过多个子 sub-arrays，将它们与所有其他子 sub-arrays 进行比较，在其他 sub-arrays 中找到，然后合并sub-sub-arrays 被认为足够相同？
多维数组结构
$array = array (
// Sub-array 1
array (
// Story 'Monkey 1' - Has identical sub-sub-arrays 'Monkey 2' and 'Monkey 3' and will be merged with them.
array (
"header" => "This is a story about a monkey.",
'keywords' => array( "Trees", "Monkey", "Flying", "Drink", "Vacation", "Coconut", "Big", "Bonobo", "Climbing")
),
// Story 'Cat 1' - Has identical sub-sub-array 'Cat 2' and will be merged with it.
array (
"header" => "Here's a catarific story about a cat",
'keywords' => array( "meauw", "raaaw", "kitty", "growup", "Fun", "claws", "fish", "salmon")
)
),
// Sub-array 2
array (
// Story 'Monkey 2' - Has identical sub-sub-arrays 'Monkey 1' and 'Monkey 3' and will be merged with them.
array (
"header" => "This is another, but different story, about a monkey.",
'keywords' => array( "Monkey", "Big", "Trees", "Bonobo", "Fun", "Dance", "Cow", "Coconuts")
),
// Story 'Cat 2' - Has identical sub-sub-array 'Cat 1' and will be merged with it.
array (
"header" => "Here's a different story about a cat",
'keywords' => array( "meauwe", "ball", "cat", "kitten", "claws", "sleep", "fish", "purr")
)
),
// Sub-array 3
array (
// Story 'Monkey 3' - Has identical sub-sub-arrays 'Monkey 1' and 'Monkey 2' and will be merged with them.
array (
"header" => "This is a third story about a monkey.",
'keywords' => array( "Jungle", "tree", "monkey", "Bonobo", "Fun", "Dance", "climbing", "Coconut", "pretty")
),
// Story 'Fireman 1' - Has no identical sub-sub-arrays and will not be merged.
array (
"header" => "This is a story about a fireman",
'keywords' => array( "fire", "explosion", "burning", "rescue", "happy", "help", "water", "car")
)
)
);
求多维数组
$array = array (
// Story 'Monkey 1', 'Monkey 2' and 'Monkey 3' merged.
array (
"header" => array( "This is a story about a monkey.", "This is another, but different story, about a monkey.", "This is a third story about a monkey."),
'keywords' => array( "Trees", "Monkey", "Flying", "Drink", "Vacation", "Coconut", "Big", "Bonobo", "Climbing", "Fun", "Dance", "Cow", "Coconuts", "Jungle", "tree", "pretty")
),
// Story 'Cat 1' and 'Cat 2' merged.
array (
"header" => array( "Here's a catarific story about a cat", "Here's a different story about a cat"),
'keywords' => array( "meauw", "raaaw", "kitty", "growup", "Fun", "claws", "fish", "salmon", "ball", "cat", "kitten", "sleep", "fish", "purr")
)
);
据我了解你的情况，你只有一个多维数组。第一级有6个数组，每个第一级数组包含20个（第二级）数组。每个第二级数组包含 1 个（第三级）数组和 2 个元素：string 和 keywords.
您希望将每个 string 和 keywords 与存在于多维数组中的所有其他 string 和 keywords 进行比较。
让我们用 array_diff_key() & range()
做一些深思熟虑的循环
foreach($L1arrays as $index=>$L1focus){ // 6 arrays with indexes 0 - 5
// now we want to check against all siblings that haven't been checked yet
foreach(array_diff_key($L1arrays,range(0,$index)) as $L1comparison){ // no dupe loops
// When $index=0, second foreach will only loop through $L1arrays indexed 1-5
// When $index=1, second foreach will only loop through $L1arrays indexed 2-5
// When $index=2, second foreach will only loop through $L1arrays indexed 3-5
// When $index=3, second foreach will only loop through $L1arrays indexed 4-5
// When $index=4, second foreach will only loop through $L1arrays[5]
// When $index=5, it will not loop because it has already been compared
// to all other indexes via previous loops.
/*
... in this section you can loop through the 20 sub-arrays of $L1focus
and compare them against the 20 sub-arrays of each $L1comparison
*/
}
}
现在讨论比较逻辑。根据您问题中的当前信息，我不明白您希望如何区分一个阵列是否与另一个阵列足够相似。我希望你能更加努力地创建一个现实的 Wanted Multidimensional Array -- 第二个数组有一个重复的键 0 并且其中有两个空元素，所以它是相当无用的。
您要比较 keywords 或 string 值，还是两者都比较？比较的严格程度（'similarity threshold'是什么）？
PHP 是这类工作的出色表演者。我已经从你的问题中删除了 javascript 标签。
请做一些 work/research（利用我的循环建议）并准确改进您希望如何比较最深的数组值并编辑您的问题。为了再次引起我对这个问题的注意，写一个以 @mickmackusa
开头的评论
祝你好运！
我来试试！
我使用 preg_grep 来查找其他子数组中相同的项目。然后我用count看看有多少匹配的关键字。
这就是门槛所在。目前我将它设置为2，这意味着两个匹配的关键字是匹配的。
//flatten array to make it simpler
$new =[];
foreach($array as $subarr){
$new = array_merge($new, $subarr);
}
$threshold = 2;
$merged=[];
foreach($new as $key => $story){
// create regex pattern to find similar items
$words = "/" . implode("|", $story["keywords"]) . "/i";
foreach($new as $key2 => $story2){
// only loop new items and items that has not been merged already
if($key != $key2 && $key2 > $key && !in_array($key2, $merged)){
// If the count of words from preg_grep is above threshold it's mergable
if(count(preg_grep($words, $story2["keywords"])) > $threshold){
// debug
//echo $key . " " . $key2 . "\n";
//echo $story["header"] . " = " . $story2["header"] ."\n\n";
// if the item does not exist create it first to remove notices
if(!isset($res[$key])) $res[$key] = ["header" => [], "keywords" =>[]];
// add headers
$res[$key]["header"][] = $story["header"];
$res[$key]["header"][] = $story2["header"];
// only keep unique
$res[$key]["header"] = array_unique($res[$key]["header"]);
// add keywords and remove duplicates
$res[$key]["keywords"] = array_merge($res[$key]["keywords"], $story["keywords"], $story2["keywords"]);
$res[$key]["keywords"] = array_unique($res[$key]["keywords"]);
// add key2 to merged so that we don't merge this again.
$merged[] = $key2;
}
}
}
}
var_dump($res);
输出与您的 "wanted" 有问题。
简介 - 此问题已于 2018 年 5 月 27 日更新：
我有1个PHPmultidimensional-array，包含6个sub-arrays，每个包含20个子sub-arrays，其中反过来，每个包含2个子sub-arrays，一个是字符串（header），另一个是不特定数量的关键词（keywords）。
我希望将 120 个子 sub-arrays 中的每一个与其余 5 sub-arrays 中包含的 100 个其他子 sub-arrays 进行比较。这样 sub-sub-array1 在 sub-array1 与 sub-array1 相比较并包括 sub-array20 在 sub-array2 到 sub-array6,等等.
如果有足够的关键字在两个子sub-arrays中被认为是相同的并且headers也是一样，都是使用Levenshtein距离，子sub-arrays会合并。
示例脚本
我已经编写了一个脚本来执行此操作，但要使用两个单独的数组来演示我的目标：
<?php
// Variable deciding maximum Levenshtein distance between two words. Can be changed to lower / increase threshhold for whether two keywords are deemed identical.
$lev_point_value = 3;
// Variable deciding minimum amount of identical (passed the $lev_point_value variable) keywords needed to merge arrays. Can be changed to lower / increase threshhold for how many keywords two arrays must have in common to be merged.
$merge_tag_value = 4;
// Variable deciding minimum Levenshtein distance between two headers needed to merge arrays. Can be changed to lower / increase threshhold for whether two titles are deemed identical.
$merge_head_value = 22;
// Array1 - A story about a monkey, includes at header and keywords.
$array1 = array (
"header" => "This is a story about a monkey.",
'keywords' => array( "Trees", "Monkey", "Flying", "Drink", "Vacation", "Coconut", "Big", "Bonobo", "Climbing"
));
// Array1 - Another, but slightly different story about a monkey, includes at header and keywords.
$array2 = array (
"header" => "This is another, but different story, about a monkey.",
'keywords' => array( "Monkey", "Big", "Trees", "Bonobo", "Fun", "Dance", "Cow", "Coconuts"
));
// Function comparing keywords between two arrays. Uses levenshtein distance lesser than $lev_point_value. Each pass increases $merged_tag, which is then returned.
function sim_tag_index($array1, $array2, $lev_point_value) {
$merged_tag = 0;
foreach ($array1['keywords'] as $item1){
foreach ($array2["keywords"] as $item2){
if (levenshtein($item1, $item2) <= $lev_point_value) {
$merged_tag++;
};
}
};
return $merged_tag;
}
// Function comparing headers between two arrays using levenshtein distance, which is then returned as $merged_head.
function sim_header_index($array1, $array2) {
$merged_head = (levenshtein($array1['header'], $array2['header']));
return $merged_head;
}
// Function running sim_tag_index against $merge_tag_value, if it passes, then running sim_tag_index against $merge_head_value, if this passes aswell, merge arrays.
function merge_on_sim($array1, $array2, $merge_tag_value, $merge_head_value, $lev_point_value) {
$group = array();
if (sim_tag_index($array1, $array2, $lev_point_value) >= $merge_tag_value) {
if (sim_header_index($array1, $array2) >= $merge_head_value) {
$group = (array_unique(array_merge($array1["keywords"],$array2["keywords"])));
}
}
return $group;
}
// Printing function merge_on_sim.
print_r (merge_on_sim($array1, $array2, $merge_tag_value, $merge_head_value, $lev_point_value));
?>
问题：
我如何扩展或重写我的脚本以通过多个子 sub-arrays，将它们与所有其他子 sub-arrays 进行比较，在其他 sub-arrays 中找到，然后合并sub-sub-arrays 被认为足够相同？
多维数组结构
$array = array (
// Sub-array 1
array (
// Story 'Monkey 1' - Has identical sub-sub-arrays 'Monkey 2' and 'Monkey 3' and will be merged with them.
array (
"header" => "This is a story about a monkey.",
'keywords' => array( "Trees", "Monkey", "Flying", "Drink", "Vacation", "Coconut", "Big", "Bonobo", "Climbing")
),
// Story 'Cat 1' - Has identical sub-sub-array 'Cat 2' and will be merged with it.
array (
"header" => "Here's a catarific story about a cat",
'keywords' => array( "meauw", "raaaw", "kitty", "growup", "Fun", "claws", "fish", "salmon")
)
),
// Sub-array 2
array (
// Story 'Monkey 2' - Has identical sub-sub-arrays 'Monkey 1' and 'Monkey 3' and will be merged with them.
array (
"header" => "This is another, but different story, about a monkey.",
'keywords' => array( "Monkey", "Big", "Trees", "Bonobo", "Fun", "Dance", "Cow", "Coconuts")
),
// Story 'Cat 2' - Has identical sub-sub-array 'Cat 1' and will be merged with it.
array (
"header" => "Here's a different story about a cat",
'keywords' => array( "meauwe", "ball", "cat", "kitten", "claws", "sleep", "fish", "purr")
)
),
// Sub-array 3
array (
// Story 'Monkey 3' - Has identical sub-sub-arrays 'Monkey 1' and 'Monkey 2' and will be merged with them.
array (
"header" => "This is a third story about a monkey.",
'keywords' => array( "Jungle", "tree", "monkey", "Bonobo", "Fun", "Dance", "climbing", "Coconut", "pretty")
),
// Story 'Fireman 1' - Has no identical sub-sub-arrays and will not be merged.
array (
"header" => "This is a story about a fireman",
'keywords' => array( "fire", "explosion", "burning", "rescue", "happy", "help", "water", "car")
)
)
);
求多维数组
$array = array (
// Story 'Monkey 1', 'Monkey 2' and 'Monkey 3' merged.
array (
"header" => array( "This is a story about a monkey.", "This is another, but different story, about a monkey.", "This is a third story about a monkey."),
'keywords' => array( "Trees", "Monkey", "Flying", "Drink", "Vacation", "Coconut", "Big", "Bonobo", "Climbing", "Fun", "Dance", "Cow", "Coconuts", "Jungle", "tree", "pretty")
),
// Story 'Cat 1' and 'Cat 2' merged.
array (
"header" => array( "Here's a catarific story about a cat", "Here's a different story about a cat"),
'keywords' => array( "meauw", "raaaw", "kitty", "growup", "Fun", "claws", "fish", "salmon", "ball", "cat", "kitten", "sleep", "fish", "purr")
)
);
据我了解你的情况，你只有一个多维数组。第一级有6个数组，每个第一级数组包含20个（第二级）数组。每个第二级数组包含 1 个（第三级）数组和 2 个元素：string 和 keywords.
您希望将每个 string 和 keywords 与存在于多维数组中的所有其他 string 和 keywords 进行比较。
让我们用 array_diff_key() & range()
做一些深思熟虑的循环foreach($L1arrays as $index=>$L1focus){ // 6 arrays with indexes 0 - 5
// now we want to check against all siblings that haven't been checked yet
foreach(array_diff_key($L1arrays,range(0,$index)) as $L1comparison){ // no dupe loops
// When $index=0, second foreach will only loop through $L1arrays indexed 1-5
// When $index=1, second foreach will only loop through $L1arrays indexed 2-5
// When $index=2, second foreach will only loop through $L1arrays indexed 3-5
// When $index=3, second foreach will only loop through $L1arrays indexed 4-5
// When $index=4, second foreach will only loop through $L1arrays[5]
// When $index=5, it will not loop because it has already been compared
// to all other indexes via previous loops.
/*
... in this section you can loop through the 20 sub-arrays of $L1focus
and compare them against the 20 sub-arrays of each $L1comparison
*/
}
}
现在讨论比较逻辑。根据您问题中的当前信息，我不明白您希望如何区分一个阵列是否与另一个阵列足够相似。我希望你能更加努力地创建一个现实的 Wanted Multidimensional Array -- 第二个数组有一个重复的键 0 并且其中有两个空元素，所以它是相当无用的。
您要比较 keywords 或 string 值，还是两者都比较？比较的严格程度（'similarity threshold'是什么）？
PHP 是这类工作的出色表演者。我已经从你的问题中删除了 javascript 标签。
请做一些 work/research（利用我的循环建议）并准确改进您希望如何比较最深的数组值并编辑您的问题。为了再次引起我对这个问题的注意，写一个以 @mickmackusa
祝你好运！
我来试试！
我使用 preg_grep 来查找其他子数组中相同的项目。然后我用count看看有多少匹配的关键字。
这就是门槛所在。目前我将它设置为2，这意味着两个匹配的关键字是匹配的。
//flatten array to make it simpler
$new =[];
foreach($array as $subarr){
$new = array_merge($new, $subarr);
}
$threshold = 2;
$merged=[];
foreach($new as $key => $story){
// create regex pattern to find similar items
$words = "/" . implode("|", $story["keywords"]) . "/i";
foreach($new as $key2 => $story2){
// only loop new items and items that has not been merged already
if($key != $key2 && $key2 > $key && !in_array($key2, $merged)){
// If the count of words from preg_grep is above threshold it's mergable
if(count(preg_grep($words, $story2["keywords"])) > $threshold){
// debug
//echo $key . " " . $key2 . "\n";
//echo $story["header"] . " = " . $story2["header"] ."\n\n";
// if the item does not exist create it first to remove notices
if(!isset($res[$key])) $res[$key] = ["header" => [], "keywords" =>[]];
// add headers
$res[$key]["header"][] = $story["header"];
$res[$key]["header"][] = $story2["header"];
// only keep unique
$res[$key]["header"] = array_unique($res[$key]["header"]);
// add keywords and remove duplicates
$res[$key]["keywords"] = array_merge($res[$key]["keywords"], $story["keywords"], $story2["keywords"]);
$res[$key]["keywords"] = array_unique($res[$key]["keywords"]);
// add key2 to merged so that we don't merge this again.
$merged[] = $key2;
}
}
}
}
var_dump($res);
输出与您的 "wanted" 有问题。