大师网-带你快速走向大师之路 解决你在学习过程中的疑惑,带你快速进入大师之门。节省时间,提升效率

多标签(组)运算

一、概述

标签是精细化运营必不可少的工具,常见的使用场景有标签推送,千人千面的广告展示等。在实际的业务中,标签往往是通过交并差非运算组合在一起使用,比如:标签组合是 A ∪ B ∩ C,需要判断用户在不在这个集合中。

以千人千面展示广告为例,我们会有这样的需求:

  1. (美甲师或者美甲店主)且参与了开店计划的广州用户展示A广告。
  2. (美甲师或者美甲店主)且参与了开店计划的深圳用户展示B广告。

标签说明:这里的标签都是用户标签,英文标签:美甲师( identity_1)、美甲店主( identity_2)、参与了开店计划( shop_setup_user)、广州( guangzhou)、深圳( shenzhen)。

二、实现思路

首先,从需求可以得出广告展示的标签表达式:

A 广告: (identity_1 ∪ identity_2) ∩ shop_setup_user ∩ guangzhou
B 广告: (identity_1 ∪ identity_2) ∩ shop_setup_user ∩ shenzhen

为了方便表示「交并差非」所有运算,将「交并差非」分别用「+-!」表示*,其中运算没有优先级区别,于是上面的表达式可以写成:

A 广告: (identity_1+identity_2)*shop_setup_user*guangzhou
B 广告: (identity_1+identity_2)*shop_setup_user*shenzhen

分析:一个用户包含多个标签,判断「一个用户」是否存在「一个标签运算的集合」中,从而来展示广告,其核心就是:判断一个并集集合与另一个(多个运算的)集合的交集关系。

1. 表达式分析

表达式含义

结合「交并差非」的含义,以及(除了「!」)符号左右结合运算的原理,可以明确符号连接左右两个的标签(表达式)的含义:

  1. 由「+」连接的两个标签(表达式)是或的关系,只要有一个与用户的标签有交集即为true。
  2. 由「*」链接的两个标签(表达式)是交的关系,左右两个都与用户的标签有交集才为true。
  3. 由「-」链接的两个标签(表达式)是交的关系,左边与用户的标签有交集且右边与用户的标签没有交集,才为true。
  4. 「!」比较特殊,它是使得其后跟着的标签(表达式)相反。

转成二叉树

理清楚含义以后,可以看出只要用递归的方式对其左右运算,就可以得到「用户是否在标签表达式」集合里的结果。左右运算的一个很合适的数据结构就是二叉树,大致思路就是:

  1. 将表达式转成二叉树
  2. 递归二叉树判断


    image.png

2. 表达式解析

关于表达式的解析,与基本的四则运算表达式解析基本一致,只不过我们的含义不一样,以及没有符号的优先级区别。

a. 中缀表达式与后缀表达式

中缀表达式就是常说的算数表达式,比如:1+2*3/(2+1)。后缀表达式(也叫逆波兰表示法)就是运算符在运算数之后的表达式,比如上述的表达式写成:12321+/*+。也可是实现去掉括号的作用。转化过程,会用到栈去保存运算符号。

转化过程
读取的字符 分解中缀表达式 求后缀表达式(output) 栈中内容
1 1 1
+ 1+ 1 +
2 1+2 12 +
* 1+2* 12 +*
3 1+2*3 123 +*
/ 1+2*3/ 123 +*/
( 1+2*3/( 123 +*/(
2 1+2*3/(2 1232 +*/(
+ 1+2*3/(2+ 1232 +*/(+
1 1+2*3/(2+1 12321 +*/(+
) 1+2*3/(2+1) 12321+ +*/(
1+2*3/(2+1) 12321+ +*/
1+2*3/(2+1) 12321+/ +*
1+2*3/(2+1) 12321+/* +
1+2*3/(2+1) 12321+/*+

可以看出转化规则是,按顺序读取字符:

  1. 遇到操作数,写入output。
  2. 遇到(+-*/,写入操作符栈中。
  3. 遇到),从非空的操作符栈,中弹出一项;若项不为(,则写至输出,若项为(,则退出循环。
  4. 循环读取结束后,将操作符栈逐个弹出拼在output后即可。
代码实现(PHP)
function expressionToSuffixExpressionArray($expression)
{
    $charArray = array_reverse(str_split($expression));
    $operationArray = [];
    $output = [];

    while (($c = array_pop($charArray)) != '') {
        if (in_array($c, ['(', '+', '-', '*', '/'])) {
            array_push($operationArray, $c);
        } elseif (in_array($c, [')'])) {
            while ($op = array_pop($operationArray)) {
                if ($op == '(') {
                    break;
                }
                array_push($output, $op);
            }
        } else {
            array_push($output, $c);
        }
    }

    return array_merge($output, $operationArray);
}

//测试代码
$expression = '3*(2+1)';
$result = expressionToSuffixExpressionArray($expression);

echo "expression: {$expression}" . PHP_EOL;
print_r($result);

输出:

expression: 3*(2+1)
Array
(
    [0] => 3
    [1] => 2
    [2] => 1
    [3] => +
    [4] => *
)
解析标签表达式

基础的表达式解析实现了,针对我们的标签表达式(多个字符组成一个标签),以及去掉「/」,加上「!」的逻辑,稍作修改:

function expressionToSuffixExpressionArray($expression)
{
    $charArray = array_reverse(str_split($expression));
    $operationArray = [];
    $output = [];

    $expression = '';
    while (($c = array_pop($charArray)) != '') {
        if (in_array($c, ['(', '+', '-', '*'])) {
            if (!empty($expression)) {
                array_push($output, $expression);
                $expression = '';
            }
            array_push($operationArray, $c);
        } elseif (in_array($c, [')'])) {
            if (!empty($expression)) {
                array_push($output, $expression);
                $expression = '';
            }
            while ($op = array_pop($operationArray)) {
                if ($op == '(') {
                    break;
                }
                array_push($output, $op);
            }
        } elseif (in_array($c, ['!'])) {
            if (!empty($expression)) {
                array_push($output, $expression);
                $expression = '';
            }
            array_push($output, $c);
        } else {
            $expression .= $c;
        }
    }

    return array_merge($output, $operationArray);
}

//测试代码
$expression = '(identity_1+identity_2)*shop_setup_user*guangzhou';
$result = expressionToSuffixExpressionArray($expression);

echo "expression: {$expression}" . PHP_EOL;
print_r($result);

输出:

expression: (identity_1+identity_2)*shop_setup_user*guangzhou
Array
(
    [0] => identity_1
    [1] => identity_2
    [2] => +
    [3] => shop_setup_user
    [4] => guangzhou
    [5] => *
    [6] => *
)

b. 后缀表达式转二叉树

分析:根据后缀表达式的含义,符合表示前面两个元素的运算。因此在遍历时,可以利用一个栈去暂存标签表达式,当遍历到符号,就弹出两个标签作为其运算的左右元素,形成一个新的节点放回到栈中,如此循环就能形成一个完整的二叉树。

//转后缀表达式的方法
...


//基础节点
class TreeNode
{
    public static function create(string $root = '')
    {
        return [
            'root' => $root,
            'left' => '',
            'right' => '',
            'opposite' => false,
        ];
    }
}


//后缀表达式数组转成二叉树
function suffixExpressionArrayToBinaryTree($suffixExpressionArray)
{
    $stack = [];
    $suffixExpressionArray = array_reverse($suffixExpressionArray);

    while ($item = array_pop($suffixExpressionArray)) {
        if (in_array($item, ['+', '-', '*'])) {
            $node = TreeNode::create($item);
            $node['right'] = array_pop($stack);
            $left = array_pop($stack);
            if ($left['root'] == '!') {
                $node['right']['opposite'] = true;
                $node['left'] = array_pop($stack);
            } else {
                $node['left'] = $left;
            }

            array_push($stack, $node);
        } else {
            array_push($stack, TreeNode::create($item));
        }
    }

    return $stack;
}


//测试代码
$expression = '(identity_1+identity_2)*shop_setup_user*guangzhou';
$result = expressionToSuffixExpressionArray($expression);

echo "expression: {$expression}" . PHP_EOL;
print_r($result);

$tree = suffixExpressionArrayToBinaryTree($result);
print_r($tree);

输出:

Array
(
    [0] => Array
        (
            [root] => *
            [left] => Array
                (
                    [root] => +
                    [left] => Array
                        (
                            [root] => identity_1
                            [left] =>
                            [right] =>
                            [opposite] =>
                        )

                    [right] => Array
                        (
                            [root] => identity_2
                            [left] =>
                            [right] =>
                            [opposite] =>
                        )

                    [opposite] =>
                )

            [right] => Array
                (
                    [root] => *
                    [left] => Array
                        (
                            [root] => shop_setup_user
                            [left] =>
                            [right] =>
                            [opposite] =>
                        )

                    [right] => Array
                        (
                            [root] => guangzhou
                            [left] =>
                            [right] =>
                            [opposite] =>
                        )

                    [opposite] =>
                )

            [opposite] =>
        )

)

3. 判断标签组是否包含用户

回顾一下符号的含义:

  1. 由「+」连接的两个标签(表达式)是或的关系,只要有一个与用户的标签有交集即为true。
  2. 由「*」链接的两个标签(表达式)是交的关系,左右两个都与用户的标签有交集才为true。
  3. 由「-」链接的两个标签(表达式)是交的关系,左边与用户的标签有交集且右边与用户的标签没有交集,才为true。
  4. 「!」比较特殊,它是使得其后跟着的标签(表达式)相反。

说明:

  1. 这里函数传入参数设计为「用户标签」和上一步构成的「树」。
  2. 「用户标签」是个数组。
  3. 判断逻辑先简单判断是否存在于「用户标签」数组中。

实现

//接上面的代码
//...

function isContained(array $userTags, array $rootNode): bool
{
    $result = false;
    if (in_array($rootNode['root'], ['+', '-', '*'])) {
        switch ($rootNode['root']) {
            case '+':
                $result = (isContained($userTags, $rootNode['left']) || isContained(
                        $userTags,
                        $rootNode['right']
                    ));
                break;
            case '-':
                $result = ((isContained(
                            $userTags,
                            $rootNode['left']
                        ) === true) && (isContained(
                            $userTags,
                            $rootNode['right']
                        ) === false));
                break;
            case '*':
                $result = (isContained($userTags, $rootNode['left']) && isContained(
                        $userTags,
                        $rootNode['right']
                    ));
                break;
        }
    } else {
        $result = in_array($rootNode['root'], $userTags);
    }

    if ($rootNode['opposite']) {
        $result = !$result;
    }

    return $result;
}

//测试代码
//$tree 是上一步的tree
$userTags1 = ['tag1', 'tag2', 'identity_1', 'guangzhou', 'shop_setup_user'];
$result1 = isContained($userTags1, $tree[0]);

$userTags2 = ['tag1', 'tag2', 'identity_2', 'shop_setup_user'];
$result2 = isContained($userTags2, $tree[0]);

$userTags3 = ['tag1', 'tag2', 'identity_3', 'guangzhou', 'shop_setup_user'];
$result3 = isContained($userTags3, $tree[0]);

var_dump($result1, $result2, $result3);

输出:

bool(true)
bool(false)
bool(false)

三、场景扩展

在实际的业务中,标签组合会更加复杂。除了「标签」与「标签」组合,还可会有「标签」与「标签组」,「用户标签」与「设备标签」。下面谈谈这些需求如何支持。

1. 标签与标签组互相嵌套

标签组实质也是通过标签的运算组合在一起,举个例子:
标签组1:Atag1+Atag2*Atag3
标签组2:Btag4-[标签组1]
结果:Btag4-(Atag1+Atag2*Atag3)

2. 多种类型的标签组合运算

假如有用户标签与设备标签组合,目前没做过这样的需求哈,如果要做可以考虑isContained的参数用一个「包含用户标签数组和设备标签数组的对象」代替数组,然后标签表达式中的标签带上前缀:用户标签(u|)、设备标签(d|)。
举个例子:
标签表达式:(u|identity_1+u|identity_2)*u|shop_setup_user*d|guangzhou
判断时,根据前缀来选择使用用户标签还是设备标签做判断。

四、结语

除了「判断标签组是否包含用户」这个需求,还有另外一个需求也很常用:「判断标签表达式包含多少用户」,这个需求除了逻辑还涉及到数据库的设计,实现方案跟实际场景也有关系,就不在这里讨论啦。

以上的代码段为缩减版,可能存在问题哈,如有错漏望指正。