标签： 智能提示

需求

假设某个时间段内输入历史为:

'ab', 'ac', 'aa', 'aa', 'aa', 'ab', 'ac', 'ac', 'ac', 'aa'

现用户输入a

系统应自动提示下一个用户可能输入的字母a、b或者c。

解决方案

这个问题可以简化成一个排序问题。对用户的每个输入历史进行权重计算，最后按权重排序，输出排序高的项。

关键在于怎么计算这个权重。

权重计算考虑的因素有以下几个：

1. 因子的组成
2. 因子的权重计算
3. 各因子的权重如何组合成总权重

这里考虑3种因子：

1. 出现的次数
2. 出现的时间
3. 是否连续出现

出现的次数

设为 occ_w

, occ_w=该项在统计的历史中出现的次数

出现的时间

设为 pos_w, pos_w=(该项在统计历史中出现的位置/总统计数量)^2

是否连续出现

设为 ctu_w, 如果上一个项跟本项相同，则ctu_w=上一项的总权重/2。否则ctu_w=0

设总权重为w, w = occ_w + pos_w + ctu_w

实现

参考以下python代码：

	#!/usr/bin/python
	# -*- coding: utf-8 -*-
	from collections import deque, Counter
	import random
	__author__ = 'xinyu.he'
	def add_history(src, q, cutr):
	if len(q) == q.maxlen:
	cutr[q.popleft()] -= 1
	q.append(src)
	cutr.update([src])
	def get_promote(q, src, counter):
	q_len = len(q)
	group = {}
	last_value = ''
	last_w = 0.0
	for idx, value in enumerate(q):
	if value.startswith(src):
	# pos weight
	pos_w = (idx + 1)*1.0/q_len
	pos_w = pow(pos_w, 2)
	# occ weight
	occ_w = counter[value]*1.0/q_len
	# ctu weight
	if last_value == value:
	ctu_w = last_w/2
	else:
	ctu_w = 0.0
	last_w = 0.0
	if value in group:
	each_value = group[value]
	each_value[0] += pos_w
	each_value[1] += occ_w
	each_value[2] += ctu_w
	else:
	group[value] = [pos_w, occ_w, ctu_w]
	print value, pos_w, occ_w, ctu_w
	last_value = value
	last_w = pos_w + occ_w + ctu_w
	ret = sorted(group.items(), key=lambda x: sum(x[1]), reverse=True)
	return ret
	if __name__ == '__main__':
	pool = ['ab', 'ac', 'aa', 'ad', 'ae', 'af', 'ag', 'ah', 'ai', 'aj']
	history = []
	for i in range(0, 100):
	idx = int(random.gauss(0.5, 0.1)*10)
	print idx
	history.append(pool[idx])
	src = "a"
	history_q = deque(maxlen=30)
	history_q.extend(history)
	counter = Counter(history_q)
	print history
	print get_promote(history_q, src, counter)

view raw promote.py hosted with by GitHub

ps：没有跟其他方法进行效果对比，纯做着玩。