本网站仅单台服务器: 2核2G 99¥包年,集成兼容 MySQL 的 MyTopling 高压缩高性能数据库

多音字 搜索词纠错: 匹配简拼(汉字数≥5时才有效)  单字的拼音来自:这里(最全的多音字)...     

本网站仅单台服务器: MyTopling 2核2G 99¥包年


当搜索词中有错别字时,搜索引擎会尝试纠错

通过相似拼音纠错

搜索引擎把这些字还原成拼音,用一个拼音相同的已知的搜索词代替。

这是一种众所周知的纠错策略,但是,当输错的字是多音字,特别是有多个这样的错误输入时,所有的搜索引擎都尽量绕开这个问题,或者仅使用最常用的那些音去纠错。 因为要考虑所有可能的拼音组合,在极端情况下会导致指数爆炸! 例如某互联网大厂的实现(枚举多音字全排列)

基于自动机的算法可以完美解决这个指数爆炸问题

  • 这是自动机应用的又一个绝佳范例,作为演示,这个页面只收录了 800万搜索词+词频,数据也不太干净
  • 该算法全部在内存中运行,使用了 293M 内存,这个数据量,如果用传统方法暴力实现,并且达到这个性能,需要 几十G 的内存
  • 暴力方法是 Query 越长越可怕,该算法则是 Query 越长,优势越大
  • 纠错耗时仅供参考(2核2G 99¥包年),如果你看到搜索耗时过长,很可能是 mmap 数据被 swap 到了硬盘上,再搜索一次会得到客观的搜索耗时

这个算法也可以用来解决用户输入预测(智能提示)功能

用户只输入Query开头部分,就自动提示出整个Query,例如用户输入举头望,就提示出举头望明月。就像现在各种搜索引擎做的那样。

基于编辑距离的纠错

在已知的搜索词中寻找编辑距离与用户 Query 最小的词,使用我的算法也可以高效解决(还没做演示页面)


创建 DFA Key 与 搜索 DFA Key 的 耗时 包含了 收集网页展示需要的信息,耗时占比90%以上!

靠谱的程序员太少了

阅读更多关于《靠谱的程序员太少了》

 

最近几个月,面试了不少的程序员,更好听的名字叫做软件工程师,甚至高级软件工程师。

我一般会针对面试者的特长,问一些相关的问题。有说擅长算法的,图像处理的,图形学的,数学的,C++的,Java,Perl 的,Shell 的,Linux内核的……

到目前为止,面试的人不算太多,但少说也过100了,基本上,语言方面和其它特长兼有的,一个也还没碰到过。

靠谱的C++程序员,所谓的靠谱,其实也就是:

  1. 了解 STL 的常用组件,能正确使用 STL
  2. 知道 type_traits ,以及如何使用 type_traits
  3. 对虚函数、重载、虚表有一定了解
  4. 能正确认识C++的异常
  5. 了解 Pure C 和 C++ 的 C 子集中比较常见的、明显的区别

基本上,就这 5 点,能有两点比较突出的,也就那么两三个人,而这两三个人里面,C++差不多就是他们唯一的特长了。

 

Java 上,我问的问题比较少,远不如 C++ 多,并且更简单,也就是:

  1. int/long 的二进制位数,jvm 是否在不同平台 int/long 的二进制位数是否相同
  2. 对于 StringBuilder,每次追加一个字符,当其长度长到 n 时,时间复杂度是多少
  3. 能否把一个 String 对象,添加到一个 List<Integer> 中
  4. Comparable 和 Comparator 有何区别,如何把非 Comparable 的对象作为 TreeMap 的 Key
  5. GC 的基本原理(大部分人的回答是调节 gc 参数)

目前还没碰到一个人能回答第 4 个问题!呜呼!

 

算法+Coding:

  1. 90%以上的人不知道 make_heap 的时间复杂度,知道的人,也都是背的答案。
  2. 完全无 bug 的 binary_search ,只有 3% 。
  3. std::lower_bound 类似功能的函数,目前还没一个人写得出来。
  4. 从一组 IP range –> value 的数据中查找单个 IP,允许使用 C++ stl 或 java 基础类,还没一个能给出解决办法。
  5. QuickSort 的最好情况,和 MergeSort 的最好情况,哪个的 KeyCompare 次数更少,目前只有一个人答出。

如果在这些之外,还熟悉 perl, bash, python 等脚本语言的,更是凤毛麟角。

 

要知道,这些职位可都是年薪20w以上的!

欢迎同道之士加盟,可以站内联系我,有内部推荐机会。

是个软件都想强奸用户

阅读更多关于《是个软件都想强奸用户》

Windows 7 资源管理器反应超慢已经很久了,刚刚这个问题被我彻底解决。使用 Autoruns 查看 Explorer 页,删掉所有可疑的王八蛋继续阅读

一个变态C/C++面试题的变态解法

阅读更多关于《一个变态C/C++面试题的变态解法》

这是源自某论坛的一个问题,原帖如下(#########分隔) 继续阅读

服务器超时管理问题

阅读更多关于《服务器超时管理问题》
  1. 有一个最多能处理N个客户连接的服务器,活跃的连接总是少数;
  2. 为了能够处理更多的连接,需要对每个连接都增加一个超时机制,当总连接数达到N时,某个连接一旦超时,有新的连接请求时,就把超时的关掉,并处理新连接; 继续阅读

使用 std::map 查找 IP 范围

阅读更多关于《使用 std::map 查找 IP 范围》

给定这样一个问题:

有一组从IP范围到地理位置信息的数据,不同地点的IP范围没有重叠,实现从单个IP地址查到相应的地理位置。 继续阅读

对数复杂度的聚集算法

阅读更多关于《对数复杂度的聚集算法》

SQL 有5个标准聚集函数:SUM, AVG, MIN, MAX, COUNT, 一般情况下,这几个函数的时间复杂度至少都是O(n), n是结果集的尺寸。然而,给定表:

继续阅读

解决amule脱机下载问题

阅读更多关于《解决amule脱机下载问题》

新买的廉价路由器,可以脱机下载,但只内置了bt,没有内置amule。先自己装了amule,router上的falsh太小,装不下那么多软件,就装到移动硬盘上,格式化成ext3。 继续阅读

read/write&mmap&aio

阅读更多关于《read/write&mmap&aio》

read/ReadFile 系统调用默认有预读
write/WriteFile 默认是异步写
mmap 使用缺页中断,实现预读/异步写比较困难
aio 对磁盘调度做特殊优化,在随机访问较多时,理论上性能最好(如果操作系统真正实现了aio) 继续阅读

随机数生成算法

阅读更多关于《随机数生成算法》

本文来源: http://www.zhihu.com/question/22818104
见到这个随机数生成算法好几次了,乍看有点鸡肋本来用Math.random()就可以的事。想不清楚为什么他要用9301,49297,233280这三个数字? 继续阅读

C陷阱:判断宏是否等于一个常数

阅读更多关于《C陷阱:判断宏是否等于一个常数》

下面这段代码有啥错误?

 

 

当 ULONG_MAX 未定义时,被判断为假!多么危险的一个陷阱!

增加以下验证即可查错:

 

这个 bug 耗费了我两个小时!