用户名自动完成算法

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

概述

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

总的来说有两种思路:

  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 via N97-1

    前排混脸熟😇

  • Chinese via N97-1

    前排混脸熟😇

  • blague 1

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

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