最近最少使用（LRU）分页算法对网页去噪的启示

LRU(Least Recently Used),最近最少使用方法.由于基于DOM树的方法通常复杂度比较高,并且时间代价也很大,所以本文提出了LRU的方法以期来改善网页去噪.本文并没有详细介绍LRU在网页去噪的算法实现及具体实施过程,只是在理论上给出了可行性论述.

LRU的启示

只有一少部分指令(instructions)会被经常重复使用,另外,如果一个页面长时间没被使用那么它将越来越不会被使用. 鉴于此可以建立一个链表用于存放页面,最常用到的页面放在链表前面,不常用的放在最后,当页面出错时(when a page fault occurs),扔掉末尾的页面.该方法的复杂性就是要时刻对链表中的页面进行排序的更新,文中提出用64-bit的计数器(counter)来记录页面.下图所示,蓝线表示LRU的复杂性,红线表示DOM的复杂性.

LRU优劣势并存,如果能较好地将该方法移植到网页去噪中,那么它会有很好的表现.

参考文献

[1] Sharma, Rajni, MaxBhatia. "Eliminating the Noise from Web Pages using Page ReplacementAlgorithm.”International Journal of Computer Science and Technology,Vol.5(3),2014,3066-3068.