玩转外卖订餐, ctheyvs go~go~go~

[abbshr]

今年外卖平台火遍大江南北.诸如饿了么,美团外卖,百度外卖,淘点点,超人外卖等等等等层出不穷,校园周边小餐馆的生意也做的是风生水起.各种打折,各种送饮料,各种首单立减,真让整日宅在寝室和实验室的家伙欲罢不能啊~

不过呢好日子总会有到头哪一天.随着饮料越送越差,折扣也越来越少,我们开始埋怨吃不到物美价廉的美食了. 于是乎,借着某位室友创业的热情,在另一位猥琐室友的怂恿下,走上了一条"革命之路", 因为当时常送果粒橙, 于是我们为这个计划起名为果粒橙保卫战.

不扯淡了,其实就是"外卖比价". 我们设计应用架构, 分解任务模块, 规划一系列前进流程, 差不多当晚就开始敲代码.

...当然,代码还要靠我来写-_-,这是既苦逼又令人兴奋的工作.(你能理解为什么)

我把应用核心逻辑模块分为两部分, 一块是爬虫,用于抓取各大外卖平台的网页数据;另一块是数据处理,把爬虫爬来的数据做清洗,格式转换和聚类.

架构分为定时更新任务和web服务.

后台更新任务单独启用一个进程,定时(根据正常人的进食时间统计, 设定约每3个小时更新一次)向一组外卖平台网站请求所需数据,经过清洗和转化,分类存储到数据库中.

web服务提供一个面向用户的接口,接收用户查询的地点,返回数据库中整理过的周边餐饮.

爬取数据是个体力活, 你首先要打开控制台看着DOM树一个一个的找父子节点,记id,class,tagname.换句话说写出每家平台通用的CSS path,如果是动态加载的数据,就要找到那个请求地址, 如果数据是JavaScript动态生成的, 你还要模拟执行一次以得出想要的结果. 前台测试通过后,还要用curl之类的工具通过non-browser测试,这是个技术活,因为几乎所有网站都对爬虫做了防范,你要想方设法欺骗web服务器,至于如何做就不谈了(详见之前写的一篇"crawl前端攻防战"), 总之,request模块不适用这个抓取过程, 因此我写了一个简版request专门应付我们要爬的网站server.

得到了原始的html,就可以做数据清洗了,这里使用了Node第三方cheerio模块. 提取必要信息形成一个二维数组,每个元素是一个JSON对象:

  [ 
    // platform 1
    [ 
      // restaurant 11
      {
        name: '',
        proxy: '',
        others: ...
      },
      // restaurant 12
      {
        name: '',
        proxy: '',
        others: ...
      }, ...
    ],
    // platform 2
    [
      // restaurant 21
      {
        name: '',
        proxy: '',
        others: ...
      },
      // restaurant 22
      {
        name: '',
        proxy: '',
        others: ...
      }, ...
    ],
    ...
  ]

这个数据结构的核心字段是name和proxy, 分别标识某个餐馆和对应的外卖平台,用于后期的数据处理.

进行数据处理的下一步:格式化. 因为web服务是依据用户的地点查询获取周边餐饮, 所以我们最重要返回一组周边餐饮信息, 那么考虑设计合适的数据存储schema对查询性能的提升十分重要.

我反反复复设计了几种格式,最终综合格式处理的方便和数据库读写操作的方便,我把schema规定为如下:

  {
    name1: [proxy1, proxy2, ..],
    name2: [proxy1, proxy2, ..],
    ... 
  }

每次抓取的数据经过处理, 得到如上格式存入数据库中, 这样每次查询时直接抽取周边店名,返回为其代理的外卖平台和每个平台的对这家店的优惠信息.

那么如何有效的转化数据呢? 我设计了一个转化算法. 我们通过爬虫和数据清洗,首先得到那个二维数组, 然后去掉对此步骤不重要的信息, 将二维数组的每个元素映射成对应的name字段的值:

  var result = restaurants.map(function (proxy) {
    return proxy.map(function (restaurant) {
      return restaurant.name;
    });
  });

处理后得到如下格式:

[
  [
    name1, name2, ...
  ], 
  [
    name1, name2, ...
  ],
  ...
]

这样看着就方便多了不是? 然后进行reduce操作:

  result.reduce(function (a, p, i, map) {
    var o = {};
    p.forEach(function (n, j) {
      o[n] = [ [i, j] ];
      for (var l, m = i + 1; m < map.length; m++)
        if ((l = map[m].indexOf(n)) != -1)
          o[n].push([m, l]);
    });

    // 合并
    var keys = Object.keys(a);
    keys.length && keys.forEach(function (k) {
      if (o[k])
        o[k] = a[k].length > o[k].length ? a[k] : o[k];
      else
        o[k] = a[k];
    });

    return o;
  }, {});

上面这个函数是整个算法的核心. 最外层reduce整个result数组. 每次reduce调用会新建一个JSON对象, 对于每个子数组, 也就是包含一个平台下所有餐馆名字的数组, 遍历他们, 将不同的名字和对应在二维数组中的位置保存在外层建立的JSON对象里, 并循环后面的子数组, 如果子数组中包含重名的元素,也就是同一家店,也把它的位置push到JSON对象的对应名字的数组里. 在这轮reduce的最后, 合并上一次reduce的结果: 向JSON对象中添加不存在的name, 对于已存在的name, 选取数组长度较大的保存, 最后把这个JSON对象作为这轮reduce的结果返回.

这样, 经过几次reduce, 就筛选出所有店家和他们在原始二位数组中所在的位置:

  {
    name1: [[x1, y1], [x2, y2], ...],
    name2: [[x1, y1], [x2, y2], ...],
    ...
  }

最后把位置替换成详细信息:

  for (var i in result)
    result[i] = result[i].reduce(function (arr, b) {
      arr.push(restaurants[b[0]][b[1]]);
      return arr;
    }, []);

就得到了我们想要的格式:

  {
    name1: [proxy1, proxy2, ..],
    name2: [proxy1, proxy2, ..],
    ... 
  }

整个算法代码如下:

  function normalize (restaurants, callback) {
    var result = restaurants.map(function (proxy) {
      return proxy.map(function (restaurant) {
        return restaurant.name;
      });
    }).reduce(function (a, p, i, map) {
      var o = {};
      p.forEach(function (n, j) {
        o[n] = [ [i, j] ];
        for (var l, m = i + 1; m < map.length; m++)
          if ((l = map[m].indexOf(n)) != -1)
            o[n].push([m, l]);
      });

      // 合并
      var keys = Object.keys(a);
      keys.length && keys.forEach(function (k) {
        if (o[k])
          o[k] = a[k].length > o[k].length ? a[k] : o[k];
        else
          o[k] = a[k];
      });

      return o;
    }, {});

    for (var i in result)
      result[i] = result[i].reduce(function (arr, b) {
        arr.push(restaurants[b[0]][b[1]]);
        return arr;
      }, []);

    return callback(result);
  };

但是随着我们观察解析结果, 发现有的商家在不同平台上注册的店名是不一样的! 举个栗子: 在饿了么上名为"辣婆婆川味馆"的一家店, 到了美团上是"辣婆婆川菜馆", 而事实上这两个都是同一家,只是注册的名字不同罢了. 那么问题就来了: 通过我们上面的算法无法识别这些名字上的差异, 最终会将诸如"川菜馆"和"川味馆"视为两家店.

这属于字符串近似匹配. 说来也巧, 正在我寻找解决方案时, 算法分析的最后一课恰好提到了"文本的近似匹配问题". PPT里提供了三种思路, 为了尽快实现, 我简单的看了一下基于编辑距离的近似匹配原理.

何为编辑距离? 简单说就是 "由字符串A变换到字符串B需要的最少步数"--wikipadia. 比如:

  A = "abcbab"
  B = "abcad"

这个变换是单个字符的"添加,剔除,修改", 那么从A到B最少需要两次变换, 描述如下:

  function computeEditd(p, t) {
    var plen = p.length + 1;
    var tlen = t.length + 1;
    var i, j;

    var matrix = new Array(plen);
    // 初始化矩阵
    for (i = 0; i < plen; i++)
      matrix[i] = new Array(tlen + 1);

    // 动态规划方法填充矩阵
    for (i = 0; i < plen; i++)
      for (j = 0; j < tlen; j++)
        if (i == 0)
          matrix[i][j] = j;
        else if (j == 0)
          matrix[i][j] = i;
        else
          matrix[i][j] = Math.min.apply(null, [
            matrix[i][j - 1] + 1, 
            matrix[i - 1][j] + 1, 
            (function () {
              if (p[i] == t[j])
                return matrix[i - 1][j - 1];
              else
                return matrix[i - 1][j - 1] + 1;
            })()
          ]);

    return matrix[p.length][t.length];
  };

由于满足"优化子结构"与"重叠子问题", 因此算法属于动态规划策略的应用.

采用这个方法修改原有算法:

function normalize(restaurants, callback) {
  var result = restaurants.map(function (proxy) {
    return proxy.map(function (restaurant) {
      return restaurant.name;
    });
  }).reduce(function (a, p, i, map) {
    var o = {};
    p.forEach(function (n, j) {
      o[n] = [ [i, j] ];
      for (var l, m = i + 1; m < map.length; m++) {
        // 近似匹配
        var likely = map[m].reduce(function (tuple, e, l) {
          // 计算并更新编辑距离
          var newEditd = editdUpdate(computeEditd(e, n), tuple.editd);
          tuple.pair = newEditd < tuple.editd ? [m, l] : tuple.pair;
          tuple.editd = newEditd;
          return tuple;
        }, { editd: Infinity });
        // 找到其他组中的近似元素
        if (likely.editd < 6)
          o[n].push(likely.pair);
      }
    });

    // 合并
    var keys = Object.keys(a);
    keys.length && keys.forEach(function (k) {
      if (o[k])
        o[k] = a[k].length > o[k].length ? a[k] : o[k];
      else
        o[k] = a[k];
    });

    return o;
  }, {});
  console.log(result);
  for (var i in result)
    result[i] = result[i].reduce(function (arr, b) {
      arr.push(restaurants[b[0]][b[1]]);
      return arr;
    }, []);

  return callback(result);
};

这里面仍有一个问题, 既然新的算法是根据编辑距离来判定商家的, 那究竟如何定义editd的下限? 这个没有固定标准, 取决于实际测试, 根据解析结果手动调整min_editd的大小. 运行了修改后的程序, 果然很多"有绰号"的餐馆都各自归为一类了, 但又发现了新的问题: 有的店名本身就很短, 这样的话如果低于edited, 两家不同的店就会自动被判为同一家店. 还有, 某些店属于那种连锁机构, 比如"枫林黄米饭(工大店)", "枫林黄米饭(贵新店)", 他们本身就差两个字, 这样也很容易被归为同一家, 可是按照地点的不同又不属于同一家. 看来我们的算法还需要进一步改进. 但是就算是改进, 也只能解决第一种问题, 第二个问题不是那么简单就能解决的, 这涉及到了一个智能识别的问题, 甚至还需要人工参与调整. 由于时间关系暂时也没有进一步研究.

经过数据处理阶段的数据, 就可以将其存入数据库了. 我选用leveldb作为数据持久化方案.一是因为小巧,对系统资源占用很少;二是读性能颇高.如何将格式化的数据存入leveldb? 我仍是按照查询性能优先的原则设计了存储方案.:

  {
    key: location-restaurantName,
    value: [proxy1, proxy2, ...]
  }

因为value中的值不是经常变化的(与同一家餐馆合作的外卖平台也就那么几家, 基本上不会变, 变化的是各平台的优惠政策),所以直接保存在value的数组里.

到此为止, 整个后台定时任务模块就设计完了.

Web服务上, 我使用了比较熟悉的express框架提供用户接口. 最初的打算是让用户自己输入查询地点, 直接传到server执行查询逻辑, 但这个方法的弊端逐渐显露出来. 一次测试中, 我输入了一个新的查询地点, 按正常的程序逻辑来说, 这一请求首先会到达数据库, 如果未在数据库中找到该地点, 则调用爬虫模块, 执行"抓取-清洗-格式化"流程, 然后把结果数据先返回给客户端, 随后异步写入leveldb.

这一过程看似合情合理: 采用类似DNS服务器的原理, 根据用户的请求缓存新的信息. 但查询某些学校时程序会crash, 有两种情况:

1. 学校名的错误输入. 可能是错别字(比如"哈尔滨工业大学"写成"哈尔兵工业大学"), 或者是没有按地图数据库中详细地点查询(比如你输入"哈尔滨工业大学", 而数据库中存储的是"哈尔滨工业大学(一校区)"和"哈尔滨工业大学(二校区)")
2. 学校名字输入正确了, 但无奈这个外卖平台没有与其周边合作

由于周边信息是通过对应平台使用的地图服务获取的, 而这些平台的位置查询服务均是按选项提供的, 也就是说他会对你的输入做近似匹配, 并提供几个地点数据库中相似结果供你选择, 这样就避免了无效输入导致的错误结果. 但是对我们这些靠爬取数据为生的家伙来说, 我们往往会忽视无效输入的后果: 我们潜意识认为地图API会提供给我们需要的一切信息! 而用户输入可能不准确, 当我们用这些不准确的结果调用API时, 就会得到"空结果", 空结果在外卖平台网页端上的呈现为"未找到"等等错误提示. 如果我们对这样一个网页执行"抓取-清洗-格式化", 那么在清洗的过程中就会crash!

我想干脆也模仿那些外卖平台那样, 提供选择性查询, 对于查询结果的差别, 取并集就可以了. 但暂时也是没那工夫, 也怕由此衍生出更多未知的问题. 后来还是启用了HTTP服务器集群, 采用那种经典的"Master-Slaver"架构监听crash情况并平滑重启, 貌似将来也能成为个备选方案啥的~.

有一段时间我几乎每个三小时刷一次, 看看三大外卖主力有木有什么新优惠政策, 心想再做一个trending系统就更好了, 看看外卖优惠哪家强? 找ctheyvs来帮忙啊~

当时列出的还有稳定性,安全性测试以及新功改进/添加什么的, 都还没开始. 前端页面让室友来写, 这都一个多月了还没搞定这让我情何以堪... 我也是醉啦~

跟我料想的差不多, 大多数人都是三分钟热血, 在热血中豪情壮志,指点山河,激扬文字,舍我其谁. 但三分钟过后血压又下来了.. 这尼玛, 哎. 不过也无所谓喽, 我这个人呢很随性, 向来对很多事都无所谓的啦. 不是什么原则问题, 爱干嘛干嘛吧~.

但毕竟这也算一个酷酷的玩意儿, 里面也涉及到不少好玩的东西和技术, 涨涨经验还是不错的嘛~~~ 你说是不?

[terry-fei]

用issue写博客也是醉了，同店不同平台比价？细想想要做好复杂度还真是不低，爬店家菜单价的时候也应该把优惠信息爬下来，顺便给用户推荐几种优惠的组合方式，但是从业务角度来讲感觉也没什么竞争力，大家公认的就一个标准，谁家优惠大就用谁家，so，只需要一个对比各家优惠信息的cronJob就够了，加油，博文排版能提高一下就好了，密集恐惧症啊亲

[abbshr]

@ifeiteng 这个.. 他们的优惠总会变呀, 也是在互相竞争中你高我低的~~ 消费者的标准也会跟着外卖优惠一起变, 所以嘛,其实比价的作用就是为他们动态定义一个标准嘛 ~~

后来我也懒得搞了,这东西也就是玩玩行,要想真的让人用还差得远那...

哎对了,今天美团出来个满10减5和首单立减15...

[abbshr]

@ifeiteng 确实...写log排版是个大问题...忽视了