【阿里笔试】阿里妈妈关键词热度排行（PHP版）

偏执的太偏执、 2022-05-19 07:44 228阅读 0赞

阿里不招PHP！

重要的事情说三遍。。。

看到室友在做一个阿里巴巴一个笔试题，只能用C/C++,JAVA,Clang,Clang++什么的，没有Python和PHP，感觉有点懵逼。

题目大致是这样的：

**阿里妈妈有个关键词列表，每行记录由 “关键词+空格+热度值“ 组成，如 ”连衣裙 96“，现在商家给商品添加一个关键词，要求在商家输入这个关键词后，显示类关键词的热度排行，由高到低。**

题目还有定义，什么是**类关键词**？即组成汉字完全一样，顺序不一样，即”连衣裙“和”裙连衣“是类关键词关系，和”长裙“就不是类关键词关系

**输入**：一个关键词热度列表，商家关键词，所有的汉字使用GBK编码

**输出**：类关键词热度排行

思路很简单，奈何java和C已经还给老师了，只能php写一波。

**思路 ：将关联词列表没个元素分割成关键词和热度值，作为数组A的两个元素。对关键词的每个汉字取其编码的十进制值，按照数值大小降序拼接为字符串K，对K取其MD5摘要值，作为一个新数组的的Key，A作为该数组的一个子数组。对于Key相同的数组都放到一个同一个数组单元，最终将所有的Key对于的数组合并为一个数组D（合并之前需要对每个Key对应的子数组按照热度进行二位数组排序）,则该数组即为查询字典。商家输入关键词后，我们计算该关键词的Key，再去D中按Key去子数组即可。**

**以上只是我个人的思路，目光短浅，只看到了实现方式，没有深入思考算法的优化，如果有不恰当的地方，欢迎大佬们批评指正**

**\_(:з」∠)\_**

废话就不多说了，看代码：

<?php   
    class Test{
            
        public static function run()
        {
            $list = [
                '连衣裙 19',
                '连裙衣 97',
                '裙连衣 28',
                '衣裙连 14',
                '可乐口可 34',
                '可口可乐 74',
                '小米手机 78',
                '小手米机 98',
                '小米机手 63',
                '阿里巴巴 47',
                '阿巴里巴 71',
                '巴阿巴里 71',
            ];
    
            $key = '连衣裙';
            $re = $this->similarityKeys($list, $key);
            print_r(json_encode($re));
        }
    
        
        /**获取相似关键词的热度排序
         * @param $list
         * @param $key
         * @return array|mixed
         */
        private function similarityKeys($list,$key)
        {
            $encoding = 'GBK';
            $dictionary = $this->preProcessor($list,$encoding);
            print_r($dictionary);
            $key = $this->getKeyMd5String($key,$encoding);
            if(key_exists($key,$dictionary))
                return $dictionary[$key];
            else
                return [];
        }
    
        /**关键词列表预处理
         * @param $list
         * @param $encoding
         * @return array
         */
        private function preProcessor($list,$encoding)
        {
            $data = [];
            //将key的dec降序排列组成的字符串的MD5值相同的项放到一个数组内
            foreach ($list as $item)
            {
                $re = explode(' ',$item);//分割出关键字key 和他的热度值hot
                $hash_key = $this->getKeyMd5String($re[0],$encoding);
                $data[$hash_key][] = $re;//将该记录加入数组中
            }
    
            foreach ($data as $k=>&$v)//对每个类关键词数组按照热度值倒序排列
                $v = $this->twoDimensionArraySort($v,1,false,false);
    
            return $data;
        }
    
        /**将关键词的每个字转为十进制数字，按由大到小顺序拼接后取其MD5摘要值
         * @param $key
         * @param $encoding
         * @return string
         */
        private function getKeyMd5String($key,$encoding)
        {
            $len = mb_strlen($key,$encoding);
            $tmp_keys = [];
            for ($i=0;$i<$len;$i++) //记录关键字中每个字的hex所对应的十进制值
                array_push($tmp_keys,hexdec(bin2hex(mb_substr($key,$i,1,$encoding))));
            arsort($tmp_keys);//数组按照其value降序
            $new_key = '';
            foreach ($tmp_keys as $k)
                $new_key .= '_'.$k;
            return md5($new_key);
        }
    
    
        /**二维数组排序
         * @param $data array 输入数组
         * @param $key string 内部数组的排序键
         * @param bool $asc 是否升序
         * @param bool $keep_key 是否保留原来的键
         * @return array
         */
        function twoDimensionArraySort($data,$key,$asc=true,$keep_key=true)
        {
            $keys = [];
            foreach ($data as $k=>$v)
            {
                $keys[$k] = $v[$key];
            }
            if($asc)
                asort($keys);
            else
                arsort($keys);
    
            $re = [];
            foreach ($keys as $k=>$v)
            {
                if($keep_key)
                    $re[$k] = $data[$k];
                else
                    array_push($re,$data[$k]);
            }
            unset($data,$keys);
            return $re;
        }
    }
    
    Test::run();

处理之后的关键词列表如下所示：

{
    	"58eed1a48f954e80f259ffd7bdca334c": [
    		["连裙衣", "97"],
    		["裙连衣", "28"],
    		["连衣裙", "19"],
    		["衣裙连", "14"]
    	],
    	"2a47cf89f52470a936ff0ff4567b75e3": [
    		["可口可乐", "74"],
    		["可乐口可", "34"]
    	],
    	"e1600cc8d3dd627209cb843d82e78b74": [
    		["小手米机", "98"],
    		["小米手机", "78"],
    		["小米机手", "63"]
    	],
    	"54cf875aaa8f111aaf12fc2d75cc5948": [
    		["巴阿巴里", "71"],
    		["阿巴里巴", "71"],
    		["阿里巴巴", "47"]
    	]
    }

输入搜索关键词”连衣裙“，得到结果：

[
    	["连裙衣", "97"],
    	["裙连衣", "28"],
    	["连衣裙", "19"],
    	["衣裙连", "14"]
    ]