用户名自动完成算法

本贴最后更新于 2921 天前,其中的信息可能已经时过境迁

概述

发帖、回帖有时需要 @ 用户,这个时候需要用自动完成来辅助用户输入。

总的来说有两种思路:

  1. 纯前端:自动完成候选数据在前端渲染时就给定,比如回帖时 @ 本贴的参与者,参与者相对与较少,是可以在帖子渲染时就填充好的
  2. 后端交互:发送请求到后端,由后端在整个用户列表中做匹配

社区目前选择的是第二种思路。

关键点

后端在进行用户名匹配时需要到整个用户列表中进行搜索,如果直接查库性能上肯定是不能接受的,所以这个时候引入一个缓存来解决性能问题。

因为需求比较简单,不涉及到写数据和一致性,所以也没必要引入分布式缓存这样高大上的产品,直接从数据库用户表中将所有用户名捞出放后放内存,并定时重捞(新用户注册、用户名变更等)。

目前感觉还是蛮好用的,但是有个问题一直没解决好:用户名匹配算法。

整体流程

用户输入 @ 并打出 A 时将发送一个自动完成请求到后端,后端接收到这个查询前缀为 A 的用户名时在缓存的用户名列表(按字母排序)中进行二分查找,然后选择命中条目和后面 4 个条目:

public List<JSONObject> getUserNamesByPrefix(final String namePrefix) {
    final List<JSONObject> ret = new ArrayList<JSONObject>();

    final JSONObject nameToSearch = new JSONObject();
    nameToSearch.put(User.USER_NAME, namePrefix);

    // 二分查找,userNames 是缓存好的用户名列表
    final int index = Collections.binarySearch(userNames, nameToSearch, new Comparator<JSONObject>() {
        @Override
        public int compare(final JSONObject u1, final JSONObject u2) {
            final String u1Name = u1.optString(User.USER_NAME).toLowerCase();
            final String inputName = u2.optString(User.USER_NAME).toLowerCase();

            if (u1Name.startsWith(inputName)) {
                return 0;
            } else {
                return namePrefix.compareTo(u1Name);
            }
        }
    });

    if (index >= 0) {
        final int max = index + 5 <= userNames.size() - 1 ? index + 5 : userNames.size() - 1;

        for (int i = index; i < max; i++) {
            ret.add(userNames.get(i));
        }
    }

    return ret;
}

至此,@ 时用户名自动完成的基本原理阐述完毕,下面分享一个细节。

前缀匹配

在进行二分查找时,上面的代码用了 startsWith 进行前缀匹配,乍一看感觉没错,因为自动完成时用户就是按照从左到右的输入顺序进行。

实际上,漏了一个非常重要的前提。前面提到过用户名列表是按字母排序的,但这还不够,还需要再按长度再排序,否则按前缀匹配就不可能准确。

总结

分享完了,大家还有什么要了解的请跟帖,非常欢迎任何改进!

打赏 10 积分后可见
10 积分 • 4 打赏

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • someone1764

    给个赏金以示鼓励

  • 714593351

    这是饺子发现的新 bug 么

  • 88250

    @714593351 嗯,有一部分是

  • flhuoshan

    重捞是用的什么机制?定时器吗

  • 88250

    @flhuoshan 是的呢,一小时一把

  • R

    感觉用户名不要只限于英文,比如一些工作室想在论坛注册交易,用户名是一个很好的品牌展示。

  • kevinle

    敲个字符就 ajax,服务器顶得住吗?

  • LyZane 1

    我补充一个性能优化方案,在百万级别用户的时候也可以轻松应对:

    将目前的缓存按用户名首字符分为多个缓存表,如果用户名全部是字母的话,会分出 26 个表,如果中英文混搭,预计会分出一千个表左右(常用汉字很少的),这完全是可以接受的。

    Dic<首字符,缓存表>

    先根据用户名首字符获取到缓存表,再在子表中搜索,由于字典的时间消耗为常量 1,所以拿到子表的时间消耗忽略不计,成本仅仅只是在于代码复杂度略有增加。


    如果以上方案都觉得不够快的话,可以增加冗余来继续提升性能,例如:

    Dic<前两个字符,缓存表>

    Dic<前三个字符,缓存表>


    一个想法,不一定对。

  • ouzhouyou

    这种是否有泄露注册帐号的风险

  • ouzhouyou 1

    比如 @ 的时候有一个范围

    • 好友
    • 当且帖子所有讨论者
  • 88250

    @ouzhouyou 嗯,是存在泄漏账号的风险,后续优化将考虑你的建议

    @DevAPI @kevinle 目前达不到这个用户量级,暂时没有性能问题

  • 88250

    @R 后期考虑加入昵称

  • ss

    最近正在研究算法,有一个专门用于字符串查找匹配的一章,回去先研究,研究完了再继续回答

  • flhuoshan

    @88250 覆盖后的 Collections.binarySearch 要是能返回一组命中 index 而不是一个 index,这个问题不就没有了

  • 88250

    @flhuoshan 最终改进如下:

    public List<JSONObject> getUserNamesByPrefix(final String namePrefix) {
        final JSONObject nameToSearch = new JSONObject();
        nameToSearch.put(UserExt.USER_T_NAME_LOWER_CASE, namePrefix.toLowerCase());
    
        int index = Collections.binarySearch(userNames, nameToSearch, new Comparator<JSONObject>() {
            @Override
            public int compare(final JSONObject u1, final JSONObject u2) {
                String u1Name = u1.optString(UserExt.USER_T_NAME_LOWER_CASE);
                final String inputName = u2.optString(UserExt.USER_T_NAME_LOWER_CASE);
    
                if (u1Name.length() < inputName.length()) {
                    return u1Name.compareTo(inputName);
                }
    
                u1Name = u1Name.substring(0, inputName.length());
    
                return u1Name.compareTo(inputName);
            }
        });
    
        final List<JSONObject> ret = new ArrayList<JSONObject>();
    
        if (index < 0) {
            return ret;
        }
    
        int start = index;
        int end = index;
    
        while (start > -1 && userNames.get(start).optString(UserExt.USER_T_NAME_LOWER_CASE).startsWith(namePrefix.toLowerCase())) {
            start--;
        }
        
        start++;
    
        if (start < index - 5) {
            end = start + 5;
        } else {
            while (end < userNames.size() && end < index + 5 && userNames.get(end).optString(UserExt.USER_T_NAME_LOWER_CASE).startsWith(namePrefix.toLowerCase())) {
                end++;
            }
        }
    
        return userNames.subList(start, end);
    }
    	
    

    二分命中 index 后再向前、向后扩大。

  • flhuoshan 1

    @88250 写了个递归的方法,效率可能没上面那个好。

    public class CollectionTest {

    public static void main(String args[]) {
    	ArrayList<String> arlst = new ArrayList<String>();
    
    	arlst.add("PRPOVIDES");
    	arlst.add("TP");
    	arlst.add("QUALITY");
    	arlst.add("TUTORIALS");
    
    	List<String> results = new ArrayList<String>();
    	getUserNamesByPrefix(arlst, "TP", results);
    	for (String str : results) {
    		System.out.println(str);
    	}
    }
    
    public static void getUserNamesByPrefix(List<String> users,
    		final String target, List<String> results) {
    	final Comparator<String> comparator = new Comparator<String>() {
    		@Override
    		public int compare(final String u1, final String u2) {
    			if (u1.length() >= u2.length()
    					&& u1.substring(0, u2.length()).equals(u2)) {
    				return 0;
    			}
    			return -1;
    		}
    	};
    	Collections.sort(users, comparator);
    	int result = Collections.binarySearch(users, target, comparator);
    	if (result >= 0) {
    		results.add(users.get(result));
    		users.remove(result);
    		getUserNamesByPrefix(users, target, results);
    	}
    }
    

    }
    有点奇怪,以 TU,TUT,TUTO 这几个为目标搜索 TUTORIALS 时没法命中目标,其他的几个测试词都正常。看不出来是什么地方有误

  • 88250

    @flhuoshan 好用心(代码我没看,见谅)

  • flhuoshan

    @88250 有时间帮看看下面说的问题

  • zempty

    前排混脸熟😇

  • Chinese

    前排混脸熟😇

  • blague 1

    我觉得可以前端加载一点:

    1. 参与帖子的人
    2. 帖子参与过帖子里关键词的
    3. 回帖人的圈子里的人
请输入回帖内容 ...